L'algoritmo di Viterbi è una procedura matematica che permete le comunicazioni digitali in quanto si occupa dell'efficienza delle stesse correggendone gli errori. Andrea VIterbi è di origine ebraiche ad ulteriore testimonianza di quanto riportato qui.
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
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 2 ( i ⋅ ( t − 1 ) ) {\displaystyle \mathrm {2^{(i\cdot (t-1))}} } {\displaystyle \mathrm {2^{(i\cdot (t-1))}} } cammini possibili. A ogni passo vi sono 2 i {\displaystyle \mathrm {2^{i}} } {\displaystyle \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
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).
Andrea Giacomo Viterbi anglicizzato in Andrew James Viterbi (Bergamo, 9 marzo 1935) è un ingegnere, accademico e imprenditore statunitense delle telecomunicazioni di origine italiana, noto per l'algoritmo che porta il suo nome.
Biografia
Nato in una famiglia ebraica, suo padre Achille era oftalmologo e cugino da parte di madre della moglie di Primo Levi. Nel 1938, quando l'Italia fascista promulgò le leggi razziali, Achille Viterbi ricevette dal suo concittadino Angelo Roncalli (futuro papa Giovanni XXIII) l'invito a trasferire la famiglia a Istanbul, dove Roncalli amministrava il vicariato, ma Viterbi preferì riparare negli Stati Uniti, dove giunse il 27 agosto 1939. Quando Andrea aveva sei anni i suoi genitori anglicizzarono il suo nome in Andrew per evitare confusione, essendo Andrea in inglese nome femminile.
Andrew studiò alla Boston Latin School e si diplomò nel 1952 quarto su 225 alunni; si iscrisse al Massachusetts Institute of Technology dove seguì i corsi di Claude Shannon, Norbert Wiener, Bruno Rossi, Roberto Fano e Paul Pontecorvo.
Attività accademica
È l'inventore dell'algoritmo di Viterbi, un algoritmo di uso generico diffusissimo nell'ambito dei codici a correzione d'errore e dei problemi di stima del canale. Trova impiego nelle trasmissioni digitali in sistemi come il GSM, UMTS e in sistemi basati sull'OFDMA, come xDSL, LTE, WiMAX e DVB-T.
Oltre ad aver collaborato con Wernher von Braun e partecipato a molti programmi della NASA, è stato uno dei consiglieri per le telecomunicazioni di Bill Clinton. Ha insegnato all'Università della California a Los Angeles (UCLA) e all'Università della California a San Diego.
Il 2 marzo 2004 la scuola di ingegneria dell'University of Southern California (USC), ove Viterbi aveva conseguito (nel 1962) il dottorato di ricerca (Ph.D.) è stata rinominata Andrew and Erna Viterbi School of Engineering. In quell'occasione, Viterbi ha devoluto alla USC la somma di 52 milioni di dollari.
Il 15 ottobre 2004, l'Università "La Sapienza" di Roma gli ha conferito una laurea honoris causa in Informatica.
L'8 ottobre 2007, l'Università degli Studi di Bergamo gli ha conferito una laurea honoris causa in Ingegneria informatica[1].
Attività imprenditoriale
Nel 1968 ha fondato, insieme a Irwin Jacobs, l'azienda Linkabit, un piccolo fornitore delle forze armate.
Nel 1985 ha fondato insieme a Jacobs l'azienda Qualcomm, produttrice del programma di posta elettronica Eudora e pioniera del CDMA.
Nella lista di Forbes del 28 settembre 2001 relativa ai 400 uomini più ricchi d'America, era classificato 386º con un patrimonio di 640 milioni di dollari.
Dal 2003 è il presidente della società di investimenti The Viterbi Group.
Fonte: wikipedia
