Algoritmo di Viterbi: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Nessun oggetto della modifica |
m ristrutturati alcuni periodi e corretto uso delle virgole |
||
Riga 1:
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 [[convoluzione|convoluzionali]] nel caso siano necessari
[[File:Hmm-Viterbi-algorithm-med.png|thumb|upright=1.4|Diagramma a ''traliccio'' della sequenza a distanza minima con i=5 stati al passo t=5]]
Riga 7:
* la [[distanza di Hamming|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.
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 <math>\mathrm {2^ {(i\cdot(t-1))}}</math> cammini possibili. A ogni passo vi sono <math>\mathrm {2^ {i}} </math> 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 ==
| |||