Algoritmo di Viterbi

Da Wikipedia, l'enciclopedia libera.

L'Algoritmo Viterbi è un algoritmo ideato da Andrea Viterbi e generalmente utilizzato per trovare la migliore sequenza di stati (detta Viterbi path) in una sequenza di eventi osservati in un processo markoviano. L'algoritmo è usato per la decodifica di codici convoluzionali nel caso siano necessari elevati guadagni di decodifica del segnale.

Diagramma a traliccio della sequenza a distanza minima con i=5 stati al passo t=5

Algoritmo[modifica | modifica sorgente]

Basandosi su un processo markoviano, cioè un processo in cui la probabilità di essere in uno stato in un determinato istante dipende solo dallo stato all’istante precedente, l'algoritmo sceglie il percorso che è più vicino alla sequenza di simboli ricevuti all'interno del traliccio ovvero del campo di tutte le possibilità. Il criterio di scelta tra le possibilità può essere

Una volta scelto il criterio è applicabile la stessa legge di decodifica. Ad ogni passo, l'algoritmo elimina i percorsi meno probabili fino a rimanere con un solo superstite.

L'algoritmo è tanto più prestante quanto il numero di passi è alto. Ovviamente maggiore è il numero di passi e maggiore è la lentezza nella decodifica e maggiore è il dispendio di risorse. La complessità di calcolo del decodificatore si può immaginare calcolando che per un codice con i stati e t passi di osservazione, si hanno \mathrm {2^ {(i\cdot(t-1))}} cammini possibili. Ad ogni passo vi sono \mathrm {2^ {i}} cammini che raggiungono ogni singolo stato. Di tutti i cammini uno solo sarà quello a distanza minima fino a quel passo. La ricerca della soluzione ottima con una tecnica esaustiva diventa rapidamente inapplicabile al crescere di i e t al di sopra di valori abbastanza bassi. Sono invece applicabili tecniche come quella dell'Algoritmo di Viterbi che riducono la complessità del problema applicando tecniche di programmazione dinamica.

Applicazioni[modifica | modifica sorgente]

L'algoritmo di Viterbi è molto generale e dunque è possibile adeguarlo alla descrizione di fenomeni di diverso genere. Alcune tipiche applicazioni di questo sistema sono i problemi di trasmissione digitale nell'ambito delle telecomunicazioni, in particolare le trasmissioni spaziali dove le condizioni di rumorosità del canale sono tali da rendere difficile la ricezione dei dati. È applicato anche per il riconoscimento ottico di testi (OCR).

Bibliografia[modifica | modifica sorgente]

  • A.J. Viterbi, “Error bounds for convolutional codes and asymptotically optimum decoding algorithm,” IEEE Trans. Inform. Theory, pp. 260-269, April 1967
ingegneria Portale Ingegneria: accedi alle voci di Wikipedia che trattano di ingegneria