Algoritmo di Viterbi: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Bibliografia |
|||
Riga 4:
== Algoritmo ==
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 di Hamming|distanza minima di Hamming]] rispetto alla sequenza ricevuta
* la distanza euclidea tra i segnali
Riga 11:
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 <math>\mathrm {2^ {(i\cdot(t-1))}}</math> cammini possibili. Ad 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 appliabili tecniche come quella dell'Algoritmo di Viterbi che riducono la complessità del problema applicando tecniche di [[Programmazione dinamica]].
== Applicazioni ==
| |||