Codice convoluzionale

Nelle telecomunicazioni, un codice convoluzionale è un tipo di codice per la correzione d'errore nel quale

• ogni simbolo d'informazione a m bit (ogni stringa a m bit) da codificare è trasformato in un simbolo a n bit, dove m/n è il rapporto (rate) del codice (n ≥ m) e
• la trasformazione è una funzione degli ultimi k simboli d'informazione, dove k è la lunghezza dei vincoli (constraint length) del codice.

Dove si usano i codici convoluzionali

I codici convoluzionali si utilizzano in numerose applicazioni allo scopo di ottenere un trasferimento di dati affidabile, comprese il video digitale, la radio, la telefonia mobile e le comunicazioni via satellite. Questi codici sono spesso implementati in concatenazione con un codice per le decisioni rigide (hard-decision code), particolarmente quello di Reed-Solomon. Anteriormente ai codici Turbo, tali costruzioni erano le più efficienti, avvicinandosi moltissimo al limite di Shannon.

Codifica convoluzionale

Per codificare convoluzionalmente i dati, si inizia con k registri di memoria, ognuno contenente 1 bit di input. A meno che non sia altrimenti specificato, tutti i registri di memoria iniziano con un valore di 0. Il codificatore ha n sommatori modulo 2 (un sommatore modulo 2 può essere implementato con una singola porta XOR booleana, dove la logica è: 0+0 = 0, 0+1 = 1, 1+0 = 1, 1+1 = 0), e n polinomi generatori — uno per ciascun sommatore (vedi figura sotto). Un bit d'ingresso m₁ è immesso nel registro più a sinistra. Usando i polinomi generatori e i valori esistenti nei rimanenti registri, il codificatore fornisce come risultato n bit. Ora sposta i bit di tutti i valori di registro a destra (m₁ si muove verso m₀, m₀ si muove verso m_-1) e attende il prossimo bit d'ingresso. Se non ci sono bit d'ingresso rimanenti, il codificatore continua a fornire risultati fino a quando tutti i registri sono ritornati allo stato zero.

La figura di sotto è un codificatore di rapporto 1/3 (m/n) con lunghezza dei vincoli (k) di 3. I polinomi generatori sono G₁ = (1,1,1), G₂ = (0,1,1) e G₃ = (1,0,1). Perciò, i bit di uscita sono calcolati (modulo 2) come segue:

n₁ = m₁ + m₀ + m_-1

n₂ = m₀ + m_-1

n₃ = m₁ + m_-1.

Fig. 1. Codificatore convoluzionale non ricorsivo, non sistematico di rapporto 1/3 con lunghezza dei vincoli 3

Codici ricorsivi e non ricorsivi

Il codificatore sulla figura di sopra è un codificatore non ricorsivo. Ecco un esempio di uno ricorsivo:

Fig. 2. Codificatore convoluzionale ricorsivo, sistematico di rapporto 1/2 con lunghezza dei vincoli 4

Si può vedere che anche l'ingresso (input) codificato è incluso nella sequenza in uscita (output) (si guardi l'output 2). Tali codici sono definiti sistematici; altrimenti il codice è chiamato non sistematico.

I codici ricorsivi sono sempre sistematici e, per converso, i codici non ricorsivi sono non sistematici. Non è un requisito rigido, ma una prassi comune.

Risposta impulsiva, funzione di trasferimento e lunghezza dei vincoli

Un codificatore convoluzionale è così chiamato perché esegue una convoluzione del flusso in ingresso con le risposte impulsive del codificatore:

$y_{i}^{j}=\sum _{k=0}^{\infty }h_{k}^{j}x_{i-k},$

dove $x$ è una sequenza d'ingresso, $y^{j}$ è una sequenza proveniente dall'uscita $j$ e $h^{j}$ è una risposta impulsiva per l'uscita $j$.

Un codificatore convoluzionale è un sistema dinamico lineare tempo invariante discreto. Ogni uscita di un codificatore può essere descritta dalla propria funzione di trasferimento, che è strettamente legata a un polinomio generatore. Una risposta impulsiva è connessa a una funzione di trasferimento attraverso la trasformata zeta.

Le funzioni di trasferimento per il primo codificatore (non ricorsivo) sono:

• $H_{1}(z)=1+z^{-1}+z^{-2},$
• $H_{2}(z)=z^{-1}+z^{-2},$
• $H_{3}(z)=1+z^{-2}.$

Le funzioni di trasferimento per il secondo codificatore (ricorsivo) sono:

• $H_{1}(z)={\frac {1+z^{-1}+z^{-3}}{1-z^{-2}-z^{-3}}},$
• $H_{2}(z)=1.$

Si definisca $m$ come

$m=\max _{i}polydeg(H_{i}(1/z))$

dove, per qualsiasi funzione razionale $f(z)=P(z)/Q(z)$,

$polydeg(f)=\max(deg(P),deg(Q))$.

Allora $m$ è il massimo dei gradi polinomiali del $H_{i}(1/z)$, e la lunghezza dei vincoli è definita come $K=m+1$. Ad esempio, nel primo caso sopra riportato la lunghezza dei vincoli è 3, e nel secondo è 4.

Diagramma a traliccio

Un codificatore convoluzionale è una macchina a stati finiti. Un codificatore con n celle binarie avrà 2ⁿ stati.

S'immagini che il codificatore (mostrato in Fig. 1, sopra) abbia '1' nella cella di memoria sinistra (m₀), e '0' in quella destra (m_-1). (m₁ non è realmente una cella di memoria perché rappresenta un valore corrente). Designeremo tale stato come "10". Secondo un bit d'ingresso il codificatore al prossimo turno può convertire o allo stato "01" o allo stato "11". Si può vedere che non tutte le transizioni sono possibili (ad es., un codificatore non può convertire dallo stato "10" a "00" o anche rimanere nello stato "10").

Tutte le possibili transizioni possono essere mostrate nel modo seguente:

Fig. 3. Un diagramma a griglia (trellis diagram) per il codificatore nella Fig. 1. Un percorso attraverso la griglia è mostrato come una linea rossa. Le linee intere indicano le transizioni dove l'ingresso è uno "0" e le linee spezzate dove l'ingresso è un "1".

Un'effettiva sequenza codificata può essere rappresentata come un percorso su questo grafico. Nell'esempio un percorso valido è mostrato in rosso.

Questo diagramma a griglia o a traliccio (trellis diagram) ci fornisce un'idea sulla decodifica: se una sequenza ricevuta non si adatta a questo grafico, allora è stata ricevuta con errori, e dobbiamo scegliere la sequenza corretta (che si adatta al grafico) più vicina. Gli algoritmi reali di decodifica sfruttano questa idea.

Distanza libera e distribuzione dell'errore

La distanza libera (d) è la distanza minima di Hamming tra differenti sequenze codificate. La capacità correttiva (t) di un codice convoluzionale è il numero di errori che possono essere corretti dal codice stesso. Essa può essere calcolata come

$t=\left\lfloor {\frac {d-1}{2}}\right\rfloor .$

Poiché un codice convoluzionale non usa blocchi, elaborando invece un flusso di bit continuo, il valore di t si applica a una quantità di errori localizzati relativamente l'uno vicino all'altro. Cioè, gruppi multipli di errori t possono solitamente essere aggiustati quando sono relativamente distanti.

La distanza libera può essere interpretata come la distanza minima di una "scarica" errata all'uscita di un decodificatore convoluzionale. Il fatto che gli errori appaiano come "scariche" dovrebbe essere tenuto in considerazione quando si progetta un codice concatenato con un codice convoluzionale interno. La soluzione popolare per questo problema è di "interfogliare" (interleave) i dati prima della codifica convoluzionale, in modo che il codice del blocco esterno (solitamente il Reed-Solomon) possa correggere la maggior parte degli errori.

Decodifica dei codici convoluzionali

Esistono parecchi algoritmi per decodificare i codici convoluzionali. Per valori relativamente piccoli di k, è universalmente utilizzato l'algoritmo di Viterbi in quanto fornisce una prestazione a massima verosimiglianza ed è altamente parallelizzabile. I decodificatori di Viterbi sono quindi facili da implementare nell'hardware VLSI e nel software su CPU con serie di istruzioni SIMD.

I codici con la lunghezza dei vincoli più lunga sono decodificati in maniera più pratica con uno qualsiasi dei vari algoritmi di decodifica sequenziale, dei quali l'algoritmo di Fano è quello meglio conosciuto. Diversamente dalla decodifica di Viterbi, la decodifica sequenziale non soddisfa la massima verosimiglianza ma la sua complessità aumenta solo leggermente con la lunghezza dei vincoli, consentendo l'uso di codici forti, con lunghezza dei vincoli lunga. Tali codici furono usati nel programma Pioneer dei primi anni 1970 su Giove e Saturno, ma diedero vita a codici più brevi, decodificati con Viterbi, solitamente concatentati con grandi codici di correzione d'errore di Reed-Solomon che rendono più ripida la curva complessiva della percentuale di errore per bit e producono percentuali di errore residuo non rilevato estremamente basse.

Sia gli algoritmi di Viterbi che quelli di decodifica sequenziale restituiscono decisioni rigide: i bit che formano la parola di codice più probabile. Una misura approssimativa di confidenza può essere aggiunta a ogni bit mediante l'uso dell'algoritmo di Viterbi per l'uscita morbida. Decisioni morbide maximum a posteriori (MAP) per ogni bit possono essere ottenute utilizzando l'algoritmo BCJR.

Popolari codici convoluzionali

Un codice convoluzionale decodificato con Viterbi particolarmente popolare, usato almeno a partire dal programma Voyager, ha una lunghezza dei vincoli k di 7 e un rapporto r di 1/2.

• Lunghezze dei vincoli più lunghe producono codici più potenti, ma la complessità dell'algoritmo di Viterbi aumenta esponenzialmente con le lunghezze dei vincoli, limitando questi codici più potenti alle missioni nello spazio profondo dove il rendimento extra vale facilmente l'accresciuta complessità del decodificatore.
• Mars Pathfinder, Mars Exploration Rover e la sonda Cassini per Saturno usano una k di 15 e un rapporto r di 1/6; questo codice esegue circa 2 dB meglio del più semplice codice k=7 a un costo di 256× in termini di complessità di decodifica (paragonato ai codici della missione Voyager).

Codici convoluzionali perforati

La perforazione (puncturing) è una tecnica usata per ricavare un codice con rapporto m/n da un codice con rapporto "basilare" 1/2. Si ottiene mediante cancellazione di alcuni bit nell'uscita del codificatore. I bit sono cancellati secondo una matrice di perforazione. Le seguenti matrici di perforazione sono quelle usate più frequentemente:

rapporto di codice	matrice di perforazione	distanza libera (per il codice convoluzionale standard NASA con K=7)
1/2 (Nessuna prestazione)	1 1	10
2/3	1 0 1 1	6
3/4	1 0 1 1 1 0	5
5/6	1 0 1 0 1 1 1 0 1 0	4
7/8	1 0 0 0 1 0 1 1 1 1 1 0 1 0	3

Ad esempio, se volessimo ricavare un codice con rapporto 2/3 usando la matrice appropriata dalla tabella precedente, dovremmo prendere un'uscita basilare del codificatore e trasmettere ogni secondo bit dal primo ramo e ogni bit dal secondo. L'ordine specifico di trasmissione è definito dal rispettivo standard di comunicazione.

I codici convoluzionali perforati sono ampiamente usati nelle comunicazioni via satellite, ad esempio nei sistemi INTELSAT e Digital Video Broadcasting.

I codici convoluzionali perforati sono chiamati in inglese punctured o anche perforated.

Codici turbo: sostituzione dei codici convoluzionali

I semplici codici convoluzionali decodificati con Viterbi stanno ora lasciando spazio ai codici turbo, una nuova classe di codici convoluzionali brevi iterati che si avvicinano strettamente ai limiti teorici imposti dal teorema di Shannon, con una complessità di decodifica molto minore dell'algoritmo di Viterbi sui lunghi codici convoluzionali che sarebbero richiesti per la stessa esecuzione. La concatenazione con un codice algebrico esterno (ad es., quello di Reed-Solomon) solleva la questione dei livelli minimi di errore o error floors insiti nei progetti dei codici turbo.

Bibliografia

• Questo articolo incorpora materiale di pubblico dominio tratto dal documento Federal Standard 1037C Archiviato il 2 marzo 2009 in Internet Archive. della General Services Administration del Governo federale degli Stati Uniti d'America

Voci correlate

• Codice convoluzionale quantistico
• WSPR

Collegamenti esterni

• Sandro Bellini, Teoria dell'informazione e codici (PDF), su scienze-como.uninsubria.it, Politecnico di Milano. URL consultato il 26 gennaio 2011.
• (EN) Tutorial sulla codifica e decodifica convoluzionale (PDF), su complextoreal.com.
• (EN) Il libro di testo in linea: Information Theory, Inference, and Learning Algorithms ("Teoria dell'informazione, inferenza e algoritmi di apprendimento"), di David MacKay, discute i codici convoluzionali nel Capitolo 48.
• (EN) La pagina degli Error Correcting Codes (ECC) ("Codici di correzione d'errore"), su eccpage.com.