CNN e Viterbi: presente e passato (passato che ancora sopravvive)

Esiste un nesso tra l’algoritmo Viterbi e le CNN?

La risposta è Sì. Un nesso unicamente concettuale, dal momento che entrambi operano su sequenze di dati cercando pattern e dipendenze.
L'algoritmo Viterbi opera su una sequenza temporale di simboli/stati, trovando il percorso a massima verosimiglianza all’interno del famoso trellis (diagramma che rappresenta graficamente l'evoluzione temporale degli stati possibili di un sistema). 

È essenzialmente un algoritmo per decodificare sequenze codificate con codici convoluzionali.
Le CNN, sebbene tipicamente associate all'elaborazione di immagini, possono essere viste come un modo per estrarre caratteristiche gerarchiche da sequenze di dati spazialmente correlati attraverso operazioni di convoluzione.
Il nesso si rafforza quando consideriamo le CNN-1D (monodimensionali) che operano su sequenze temporali, proprio come l'algoritmo di Viterbi.
In questo caso i kernel scorrono lungo la sequenza dei dati e si comportano come l'algoritmo Viterbi mentre valuta le transizioni tra stati successivi. In altre parole, entrambi sfruttano la località temporale dei dati per fare predizioni.
Tuttavia, ci sono differenze fondamentali: il Viterbi è un algoritmo deterministico che trova la soluzione ottimale globale per un modello Markoviano¹, mentre le CNN sono modelli di apprendimento statistico che apprendono rappresentazioni dai dati attraverso l’addestramento ottimizzato.
Oggi, il decoder Viterbi è spesso integrato in blocchi più grandi all'interno di SoC (System on Chip) complessi che gestiscono l'intera catena di comunicazione digitale.

Sistema che implementa il Viterbi

Il codificatore convoluzionale:

• è come una macchina che prende una sequenza di bit (0 e 1) in ingresso

• usa due polinomi generatori, G1 = 111 e G2 = 101, per produrre due bit in uscita per ogni bit in ingresso

• usa un buffer di memoria (registri di scorrimento) per ricordare i bit precedenti

Il decoder di Viterbi:

• cerca di correggere gli errori di trasmissione

• per ogni bit ricevuto, considera tutti i possibili bit originali che potrebbero averlo generato

• sceglie il percorso più probabile basandosi sulla "distanza", detta di Hamming, tra ciò che riceve e ciò che si aspetterebbe di ricevere

Analizziamo il processo completo:

1. TRASMISSIONE:
   - Input originale: 1 (t₀) 0 (t₁) 1 (t₂) 0 (t₃)
   - Per ogni bit:
     * t=0: Input=1 → Registri=100 → Output=11
     * t=1: Input=0 → Registri=010 → Output=01
     * t=2: Input=1 → Registri=101 → Output=10
     * t=3: Input=0 → Registri=010 → Output=00
   - Sequenza trasmessa: 11 01 10 00

2. CANALE:
   - La sequenza attraversa il canale di comunicazione
   - Potrebbero verificarsi errori di trasmissione
   - In questo esempio la sequenza arriva senza errori

3. RICEZIONE:
   - Sequenza ricevuta: 11 01 10 00
   - Processo di Viterbi:
     * t=0: inizia dallo stato 00 (metrica=0)
     * t=1: calcola le metriche per due stati possibili (m=2, m=1)
     * t=2: aggiorna le metriche (m=3, m=2)
     * t=3: conclude nel miglior stato (m=3)
   - Percorso ottimo (blu) → Sequenza decodificata: 1 0 1 0

CARATTERISTICHE CHIAVE:

1. La codifica raddoppia la lunghezza del messaggio (4 bit → 8 bit)
2. Ogni bit di input influenza più bit di output
3. Il decoder può recuperare la sequenza originale anche in presenza di errori
4. Il percorso blu rappresenta la sequenza più probabile

4. RICEZIONE CON ERRORE:
    - Sequenza ricevuta: 11 11 10 00

    - Processo di Viterbi:

      * t=0: inizia dallo stato S0 (metrica=0).

      * t=1: quattro stati possibili dopo la prima transizione:

• S0 → S0 (input 0, output atteso 00) → m=2
• S0 → S1 (input 1, output atteso 11) → m=0 (migliore)
• S1 → S2 (input 0, output atteso 10) → m=3 (a causa dell'errore ricevuto)
• S1 → S3 (input 1, output atteso 01) → m=1

     * t=2: aggiornamento metriche nei quattro stati:

• S0 → S0 (input 0, output atteso 00) → m=4
• S0 → S1 (input 1, output atteso 11) → m=2
• S1 → S2 (input 0, output atteso 10) → m=3
• S1 → S3 (input 1, output atteso 01) → m=1 (migliore)

    * t=3:  dopo l'ultima transizione, le metriche finali nei quattro stati sono:

• S0 → S0 → m=3
• S0 → S1 → m=3
• S1 → S2 → m=1 (migliore)
• S1 → S3 → m=3

Conclusione: il miglior percorso termina in S2 con metrica 1, ed è quello selezionato dal Trellis (verde nel diagramma)

Sequenza decodificata: 1 0 1 1 (corretto, perché il decoder ha compensato l'errore!). Il primo bit ricevuto è il primo bit della coppia (1,1).

¹Un processo stocastico è un processo di Markov se per ogni tempo e per ogni possibile sequenza di stati, vale:

\begin{equation} P(X_{t+1} | X_t, X_{t-1}, ..., X_0) = P(X_{t+1} | X_t) \end{equation}

cioè il futuro dipende solo dal presente e non dalla storia passata.