Andrew J. Viterbi (eigentlich Andrea Viterbi) wurde am 09. März 1935 in Bergamo, Italien, geboren. 1967 entwickelte er den Viterbi–Algorithmus zur
Decodierung
von
Faltungscodes;
dieser fiel quasi als Nebenprodukt bei der Analyse der Fehlerwahrscheinlichkeit von Faltungscodes ab. Der Viterbi–Algorithmus ist ein
Algorithmus
der
dynamischen Programmierung
zur Bestimmung der wahrscheinlichsten Sequenz von versteckten Zuständen bei einem gegebenen
Hidden Markov Model
und einer beobachteten Sequenz von Symbolen. Diese Zustandssequenz wird auch als Viterbi–Pfad bezeichnet. G. D. Forney leitete daraus 1972 den Optimalempfänger für verzerrte und gestörte Kanäle her. Der Viterbi–Algorithmus wird heutzutage zum Beispiel in Handys oder Wireless LANs zur Entzerrung oder Fehlerkorrektur der Funkübertragung verwendet. Ebenso in Festplatten, da bei der Aufzeichnung auf die Magnetplatten ebenfalls Verzerrungen entstehen.
Der Algorithmus ist in der Nachrichtentechnik und Informatik weit verbreitet: Die Informationstheorie, Spracherkennung, Bioinformatik und Computerlinguistik verwenden gerne den Viterbi–Algorithmus. Spracherkennung ohne diesen Algorithmus wäre schwer zu realisieren. Der Viterbi–Algorithmus ist der optimale Algorithmus zur Decodierung von Faltungscodes im Sinne der Blockfehlerrate (maximum likelihood sequence estimation). Der im Sinne der Symbolfehlerrate optimale Decodieralgorithmus ist der BCJR–Algorithmus.
Wie man aus der Beschreibung des Algorithmus sieht, kann er fast überall eingesetzt werden, um Muster zu erkennen. Das ist ein weites Feld, da Lebewesen ständig Sinnesreize interpretieren müssen und aus dem bereits Gelernten diese Signale einordnen. Der Viterbi–Algorithmus tut genau das auch und ist somit ein wichtiger Baustein der Künstlichen Intelligenz.
Einen wichtigen Stellenwert nimmt der Algorithmus in der Bioinformatik ein, denn anhand des Viterbi–Algorithmus kann unter anderem von der tatsächlichen Sequenz eines DNA–Abschnitts auf eventuelle versteckte Zustände geschlossen werden. So kann zum Beispiel untersucht werden, ob es sich bei einer vorliegenden Sequenz wahrscheinlich um ein bestimmtes Strukturmotiv handelt (CpG–Insel, Promotor, ...) oder nicht. Vorteil dieses rekursiven Algorithmus ist hierbei der linear mit der Sequenzlänge steigende Aufwand im Gegensatz zum exponentiellen Aufwand des zugrundeliegenden Hidden Markov Model.
Das Foto zeigt Andrew Viterbi zusammen mit seiner Ehefrau Erna.
