Teoria dell'informazione e codici

parole:Calcolo delle metriche finché non sono stati raggiunti tutti gli stati possibili.

Passo 1: Calcolo delle distanze di Hamming dei rami uscenti da ogni stato precedente

Passo j-esimo:e somma di queste con le metriche dei superstiti. Comparazione tra tutti i percorsi che entrano in uno stesso stato e scelta di quello con metrica minore tra tutti.

7.8 Turbo codici se lo stato iniziale è noto si prende il percorso che finisce sullo stato, altrimenti

Passo finale: si prende il percorso a minor metrica tra tutti.

146 Elementi di Teoria dell'Informazione e Codici Capitolo 8 Turbo Codici

8.1. Introduzione alla codifica turbo

Un turbo codice base è costituito da 2 codici convoluzionali che operano in parallelo ai quali è stata tolta la parte sistematica che comunque viene spedita al destinatario a parte.

Più in generale, un turbo codice può essere formato da N codici convoluzionali posti in parallelo, come riportato nella figura 8.1(a), ma nel seguito si

Il testo formattato con tag HTML:

farà riferimento solo al caso base formato da un numero N=2 di strati. Come si può osservare dalla figura, la parte sistematica è una parte comune ad entrambi i filtri per cui viene inviata solo una volta al destinatario attraverso il ramo superiore del turbo codice.

All'uscita dei due codificatori, poiché la parte sistematica è inviata a parte, sono presenti solo i bit del controllo di parità (Y , Y ), che risultano essere differenti tra di loro perché a monte dei filtri sono posti dei blocchi di permutazione che verranno spiegati più in dettaglio nel paragrafo successivo. Questi blocchi di permutazione agiscono sulla sequenza di ingresso di bit e operano una mescolatura su questi in modo tale che la sequenza che finirà all'ingresso dei filtri convoluzionali sia

ordinata in modo diverso rispetto allasequenza originale. Tipicamente, il permutatore relativo al filtro convoluzionare numero 1non applica alcuna permutazione (permutazione che vale l'identità I), mentre gli altrieseguono le manipolazioni suddette prima di dare in ingresso ai filtri convoluzionalicorrispondenti la sequenza. Ne caso N=2, se in ingresso si hanno ad esempio 128 bit,questi vengono inviati cosi come sono al destinatario (parte sistematica), poi vengonoinviati al primo codificatore che dà in uscita la sequenza dei bit di parità Y e infine1vengono spediti al codificatore 2 passando prima attraverso il permutatore 2 cheprovvederà a scambiarli di posto. All'uscita del codificatore 2 si ha la sequenza di bit diparità Y . L'operazione di permutazione della sequenza è importante perché dopo di essa,2elementi che prima erano distanti tra di loro diventano vicini (o meglio lo possonodiventare), per cui quando si

elaborano attraverso i codici convoluzinali si distribuisce informazione su elementi che prima erano distanti e che ora sono vicini e questo porta ad un aumento notevole delle prestazioni.

8.2. Codificatori convoluzionali sistematici ricorsivi (RSC)

Dopo una prima panoramica sulla codifica turbo, se si entra più in dettaglio si scopre che in realtà i filtri convoluzionali usati non sono quelli classici visti nel capitolo 7, ma sono una loro versione controreazionata, cioè sono codici convoluzionali a risposta impulsiva infinita dovuta alla presenza di una controreazione che aumenta il numero di gradi di libertà. In figura 8.2 a sinistra è riportato un codificatore convoluzionale sul quale si ha un ingresso X e due celle di memoria D. Nei turbo codici non viene usato questo filtro ma la sua versione a destra ottenuta a partire dal filtro di sinistra riportando in ingresso come input uno degli output codificati. Questa versione di codice convoluzionale è

utile per avere un maggior grado di libertà perché tra tutti i codici, a parità di complessità, si è interessati ai codici che presentano una distanza minima maggiore tra le parole di codice. Avere una distanza minima maggiore significa che si è in grado di rivelare e correggere più errori, in accordo con quanto detto al paragrafo 6.6. Ecco allora che, a parità di ridondanza, si preferisce usare codici con algoritmi più complessi, quale l'algoritmo di Viterbi ad esempio, piuttosto che codici semplici come quelli a blocco, proprio per avere la possibilità di una distanza minima tra parole maggiore e quindi correggere più errori possibili.

Figura 8.2 Codificatore convoluzionale normale e retroazionato

8.3. Interleaver

Nel paragrafo 8.1 si è parlato di permutazione della sequenza di ingresso senza però entrare nel dettaglio. L'interleaver (o

La permutazione è un elemento fondamentale nei turbocodici e di questo se ne potrebbe anche parlare al di fuori del tema che si sta trattando in questo capitolo. Gli ingegneri sono molto bravi a trattare casi in cui gli errori hanno una distribuzione uniforme e sono statisticamente indipendenti ma questi casi non sempre sono realizzabili perché gli errori spesso sono addensati (dipendenti e distribuiti non uniformemente). È possibile mettersi nella situazione in cui gli errori abbiano le caratteristiche suddette? L'interleaver risponde alla necessità di rendere distribuita l'informazione in modo tale che, visto che gli errori arrivano sempre addensati, questi vengano distribuiti in modo più uniforme su tutta la sequenza. È evidente che in fase di decodifica deve essere applicata una procedura opposta di deinterleaver. Esistono più tecniche di interleaver tra le quali verranno citate

quella a blocco, random, circular shifting esemirandom.

8.3.1 Block Interleaver

Nel block interleaver si ha una matrice di dimensioni MxN sulla quale viene inserita la sequenza di ingresso per colonne ma viene poi letta per righe.

Se gli errori arrivano, interessano solo la riga perché sono addensati e quindi nel momento che la matrice viene letta per righe questi vengono distribuiti in modo più o meno uniforme.

Applicando due volte l'operazione di interleaver si ritorna al punto di partenza.