Cos’è l’algoritmo di Viterbi?

Desidero ringraziare la mia collega Ing. Gerardina Faruolo (più esperta di me nell’argomento) per il suo prezioso aiuto nella parte più tecnica della risposta.

Andrea Viterbi è nato in Italia, ma la sua famiglia è dovuta fuggire in America per via delle persecuzioni razziali e si è stabilita a Boston. Viterbi ha frequentato il Massachusetts Institute of Technology (MIT) dove ha conosciuto i pionieri della teoria dell’informazione Claude Shannon e Robert Fano. I suoi interessi si indirizzarono verso le problematiche della comunicazione per mezzo di segnali digitali, in quegli anni una vera e propria disciplina di frontiera, in quanto le informazioni erano gestite, e quindi anche trasmesse, quasi esclusivamente in forma analogica.

Nel 1957 al Jet Propulsion Lab del California Institute of Technology iniziò a lavorare presso il settore di ricerca sulle telecomunicazioni concentrandosi su una innovativa e promettente tecnica trasmissiva chiamata “a spettro distribuito”.

Gli algoritmi esistenti per decifrare i codici a convoluzione, un particolare tipo di codici usati per la trasmissione digitale, erano estremamente complicati e difficili da spiegare agli studenti. Lavorando nel tentativo di superare queste limitazioni ottenne come risultato un algoritmo completamente nuovo e profondamente innovativo, che pubblicò nel 1967 [1], ora universalmente noto come Algoritmo di Viterbi.

L’algoritmo fu originariamente concepito per la trasmissione dati nello spazio, ove bisogna tener conto di condizioni avverse che possono produrre variazioni aleatorie del segnale trasmesso. Questo problema viene normalmente affrontato adoperando codici che introducono una opportuna ridondanza per proteggerli dagli errori. Una classe importante è costituita dai codici a convoluzione, nei quali i dati originali vengono trasformati e in un certo senso ripetuti tramite una opportuna operazione matematica. Infatti, mentre nei codici cosiddetti a blocco si applica la stessa codifica ai singoli blocchi in cui il flusso di dati viene partizionato, nei codici a convoluzione la codifica intreccia porzioni di blocchi dell’originario flusso di dati e ogni simbolo partecipa alla determinazione di simboli di codice un elevato numero di volte. Poiché la codifica a convoluzione rende il flusso di dati particolarmente interdipendente, la decodifica richiede calcoli molto più complessi di quanto sia necessario in una codifica a blocchi disgiunti. È qui che interviene l’algoritmo di Viterbi per determinare quale sequenza di dati trasmessi sia la più probabile causa del flusso osservabile in uscita. L’algoritmo calcola la probabilità dei diversi flussi in ingresso in modo ricorsivo, eliminando in blocco, ad ogni passo, quelli di probabilità minore. Tale eliminazione permette una cospicua riduzione della complessità delle relative operazioni di calcolo.

Nell’anno in cui l’algoritmo di Viterbi fu presentato, non esistevano elaboratori in grado di eseguirlo nei brevissimi tempi dettati dalle esigenze della comunicazione reale, ed infatti molti ricercatori criticarono le gravose richieste computazionali che esso presentava. D’altronde Viterbi stesso, alla fine dell’articolo, riconosceva che i requisiti di memoria e di tempi di esecuzione dell’algoritmo erano tali da renderlo impraticabile per le tecnologie del tempo. Ma, come tutte le grandi invenzioni che precorrono i tempi e che cambiano per sempre lo scenario di riferimento, anche l’algoritmo di Viterbi si rivelò affrontabile in pratica pochi anni dopo la sua introduzione, in particolare a partire dagli anni ’70; ai giorni nostri è continuamente eseguito da centinaia di milioni di apparecchiature in tutto il mondo.

Il modello stocastico cui si applica l’algoritmo di Viterbi è sufficientemente generale da adeguarsi alla descrizione di fenomeni di diversissimo genere. In conseguenza, man mano che lo sviluppo scientifico-tecnologico lo permetteva, l’uso dell’algoritmo si è esteso a molti altri campi, dove il fenomeno studiato è modellato tramite una cosiddetta catena nascosta di Markov che potremmo caratterizzare come una catena di Markov osservata attraverso un canale disturbato nel senso di Shannon. In particolare, la biologia computazionale, la linguistica computazionale ed il
riconoscimento vocale sono fra i campi di applicazione dell’algoritmo oggi di maggiore attualità.

Vediamo ora più in dettaglio come funziona l’Algoritmo di Viterbi. Innanzi tutto bisogna spiegare meglio cos’è un codice convoluzionale; la convoluzione è un’operazione matematica che sparpaglia il contenuto di un segnale secondo l’andamento di un altro, in pratica uno schema generale di un codificatore a convoluzione è rappresentato in figura 1.


Figura 1 – Schema generico di codificatore convoluzionale

Qui u rappresenta il flusso di dati in ingresso e x il flusso codificato, vengono letti k bit in ingresso ed entrano in un registro a scorrimento, una funzione combinatoria genera quindi n bit in uscita, che vengono poi trasmessi e subiscono in genere un certo processo di deterioramento.

L’algoritmo di Viterbi è il modo ottimo di decodifica, nel senso del criterio della massima verosimiglianza, ed è anche molto efficiente.

Uno schema del tipo di figura 1 può essere rappresentato anche come diagramma a stati; il numero di stati è pari a

s=2k(N-1)

il numero di transizioni da ogni stato è

2k

le transizioni da uno stato all’altro possono essere etichettate dal blocco di bit in uscita (per quello stato).

Ad esempio un diagramma per un codificatore con k=1 (un bit per volta entra nel registro), N=2 (registro a due locazioni) e n=3 (tre bit per volta in uscita) genera un diagramma degli stati del tipo di figura 2 (i rami del grafo e le relative etichette sono scelte dalla particolare funzione combinatoria implementata)

Figura 2 – Diagramma a stati di un codificatore convoluzionale con k=1; N=2, n=3.

Un modo per rappresentare dinamicamente il flusso di dati di un codificatore convoluzionale, molto utile per la decodifica con l’algoritmo di Viterbi, è il cosiddetto diagramma a traliccio: per ogni istante di tempo dall’inizio alla fine della ricezione vengono disegnati tutti gli stati possibili del codificatore; partendo dallo stato di reset si possono disegnare tutte le transizioni come cammini nel traliccio. Bisogna introdurre una metrica, cioè una distanza tra le transizioni tra gli stati e la sequenza di simboli ricevuta, ad esempio la distanza di Hamming, che si ottiene semplicemente contando il numero di bit errati.

Qui interviene l’algoritmo di Viterbi che opera iterativamente, alla ricezione di ogni simbolo (di n bit), valutando la distanza di al massimo s percorsi (sopravvissuti) e limitando quindi notevolmente la complessità di calcolo che sarebbe sL con L lunghezza della sequenza. L’animazione in figura 3 mostra il calcolo passo passo della distanza di ogni percorso nel traliccio e la scelta dei percorsi sopravvissuti fino alla fine della sequenza, dove il percorso con minore distanza indica la sequenza corretta.

La sequenza ricevuta è 110 111 011 001 000 000 000,
la sequenza corretta è 000 111 011 001 000 000 000, e ha corretto un doppio errore nel primo simbolo.

Figura 3 – Esempio di applicazione dell’algoritmo di Viterbi

Bibliografia e link
Oltre al già citato articolo di Viterbi:
[1] A.J.Viterbi, Error Bounds for Convolutional Codes and an Asymptotically Optimum Decoding Algorithm, IEEE Trans. on Information Theory, 1967

un ottimo tutorial è
[2] G.D.Forney, The Viterbi Algorithm, Proc. of the IEEE, vol 61, n. 3, March 1973

Molte delle notizie della prima parte della risposta sono state prese dall’
[3] Elogio della Prof.ssa Rossella Petreschi – Direttore Dipartimento di Informatica dell’Università di Roma La Sapienza per il Conferimento della laurea honoris causa in informatica ad Andrea Viterbi

Un testo molto completo e appassionante sulla vita dello scienziato è
[4] R. Chiaberge, L’algoritmo di Viterbi, da profugo a re dei cellulari, la straordinaria storia di un italiano in America, Longanesi

Per le informazioni tecniche ed eventuali approfondimenti si rimanda
alle dispense del prof. A.Neri dell’università di Roma 3, disponibili a
[5] http://www.comlab.ele.uniroma3.it/Comunicazioni.htm

e alla presentazione di Gerardina Faruolo disponibile a
[6] www.dspvlsi.uniroma2.it/ita/ archivio_tesi/Presentazione_Faruolo.ppt

si vedano anche i seguenti link a precedenti risposte su vialattea sulla modulazioni digitali
[7] http://www.vialattea.net/esperti/php/risposta.php?numero=6954
[8] http://www.vialattea.net/esperti/php/risposta.php?num=6290