Viterbis Algorithmus brachte jedes Mobiltelefon dazu, sein eigenes Signal zu dekodieren

Die digitale Kommunikation über eine Funkverbindung ist ein Kampf gegen Rauschen, das die von einer Antenne empfangenen Bits verfälschen kann. Die naheliegende Abhilfe ist das Hinzufügen einer Fehlerkorrekturcodierung, doch deren Dekodierung erfordert eine Möglichkeit, aus einem verrauschten empfangenen Datenstrom zu ermitteln, welche Nachricht tatsächlich gesendet wurde.

Viterbis Algorithmus von 1967 leistete genau das. Ein Faltungscodierer zwingt den Sender, sich durch eine endliche Menge von Zuständen zu bewegen, und der Empfänger führt ein Trellis dieser Zustände; bei jedem Schritt behält er nur den günstigsten Pfad in jeden Zustand, sodass er am Ende die eine wahrscheinlichste Nachricht gefunden hat, statt jedes Bit unabhängig zu wählen.

Indem er praktikable Codes mit kurzer Constraint-Länge ermöglichte, machte der Algorithmus die Vorwärtsfehlerkorrektur so kostengünstig, dass sie in echten Funkgeräten eingesetzt werden konnte. Er verwandelte ein vages „Was war die Nachricht?“ in eine saubere Suche mittels dynamischer Programmierung, und heute wird er eingesetzt, um Sprache und Daten vom Hintergrundrauschen zu trennen.

Die wahrscheinlichste verborgene Zustandsfolge auswählen

Indem nur der einzelne günstigste Pfad in jeden Zustand beibehalten wird, benötigt die Suche eine Zeit, die linear zur Nachrichtenlänge ist.

Er rekonstruiert die Maximum-Likelihood-Sequenz aus verrauschten Daten ohne Raten pro Bit.

Faltungscodes gewinnen echte Fehlerkorrekturleistung erst, wenn sie auf diese Weise dekodiert werden.

Wenn ein Signal zu verrauscht ist, um es direkt zu lesen, rekonstruiere die eine wahrscheinlichste Sequenz, aus der es stammen könnte; die von dir hinzugefügte Struktur macht diese Suche nahezu mühelos.

Der Viterbi-Algorithmus wird in der überwiegenden Mehrheit der Mobiltelefone weltweit sowie in Satellitenempfängern, der magnetischen Aufzeichnung, der Spracherkennung und der DNA-Analyse eingesetzt; Viterbi war später 1985 Mitbegründer von Qualcomm, und der Algorithmus trug dazu bei, CDMA und die digitale Mobilfunktelefonie praktikabel zu machen.