Algoritmo di Viterbi
L'algoritmo Viterbi è un algoritmo ideato da Andrew 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.
Algoritmo[modifica | modifica wikitesto]
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
- la distanza minima di Hamming rispetto alla sequenza ricevuta
- la distanza euclidea tra i segnali
Una volta scelto il criterio, è applicabile la stessa legge di decodifica. A 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 è il tempo di decodifica e maggiore è il dispendio di risorse. Si può stimare la complessità di calcolo del decodificatore calcolando che per un codice con i stati e t passi di osservazione si hanno cammini possibili. A ogni passo vi sono 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 wikitesto]
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 wikitesto]
- Stuart J. Russell, Peter Norvig, Capitolo 15 Ragionamento probabilistico nel tempo, in S. Gaburri (a cura di), Intelligenza artificiale. Un approccio moderno (2), 2ª edizione, Pearson Education Italia, 2005, ISBN 978-88-7192-229-4. URL consultato il 1º febbraio 2010.
- A.J. Viterbi, “Error bounds for convolutional codes and asymptotically optimum decoding algorithm,” IEEE Trans. Inform. Theory, pp. 260–269, April 1967
Altri progetti[modifica | modifica wikitesto]
Wikimedia Commons contiene immagini o altri file sull'algoritmo di Viterbi
