Il codificatore “turbo” è composto da due codificatori convoluzionali posti in parallelo e
separati da un interleaver, il quale gioca un ruolo fondamentale nelle prestazioni
dell’intero sistema.
Le strategie di decodifica sono essenzialmente due: una basata sull’algoritmo SOVA
( soft output Viterbi Algorithm ) e l’altra basata su un algoritmo MAP ( maximum a
posteriori probability ). Su qualsiasi dei due ricada la scelta nel turbo decoder sono pre-
senti due decodificatori in cascata che operano in maniera iterativa. Nel nostro lavoro
tali decodificatori utilizzano l’algoritmo MAP di Bahl et al. scoperto nel 1974 [Bah74].
Questo è lo stesso algoritmo adoperato nel primo articolo sui turbo codici comparso nel
1993 [Ber93].
Veniamo adesso alla descrizione della tesi.
Nel primo Capitolo si descrivono i principi fondamentali della (de)codifica turbo. Ini-
zialmente viene spiegato il funzionamento di un particolare tipo di codificatori convolu-
zionali, gli RSC (Recursive Systematic Convolutional). Sono questi i codificatori con
cui viene assemblato il turbo encoder, di cui viene descritta la struttura e viene calcolata
una stima delle prestazioni. Il quarto paragrafo è dedicato all’interleaver, di cui vengono
descritte le tipologie più note per chiarire quali di queste sono state utilizzate nelle si-
mulazioni. Infine è stato illustrato il funzionamento della decodifica iterativa per poi ar-
rivare a definire la struttura del turbo decoder.
Il secondo Capitolo è incentrato sull’algoritmo MAP di decodifica . Nel primo paragra-
fo viene presentata una descrizione dell’algoritmo di Bahl et al., chiamato anche BCJR
dalle iniziali dei suoi scopritori. La versione di tale algoritmo da noi illustrata non è
quella originale ma una modificata, in modo da tener conto della ricorsività dei codifi-
catori convoluzionali presenti nel turbo encoder. A seguire sono presentate le prime si-
mulazioni concernenti la decodifica di un RSC a 64 stati tramite l’algoritmo introdotto.
Quindi si spiega come viene sfruttato il BCJR nella decodifica iterativa e si mostra
un’implementazione software del turbo decoder. Nel quarto paragrafo ci soffermiamo
sul “tail”, ovvero su quei bit che, posti in coda alle sequenze informative in ingresso,
decidono lo stato finale dei codificatori RSC. Infine vengono illustrati i risultati delle
prime simulazioni eseguite sui turbo codici, scegliendo come modulazione la BPSK e
variando il rate del turbo encoder.
Nel terzo Capitolo i turbo codici sono associati a modulazioni a efficienza spettrale
maggiore. Inizialmente si descrive in che modo effettuare questa associazione per una
M-QAM con M = p22 , p qualsiasi. Poi si illustrano i risultati delle simulazioni da noi
effettuate basate sulla 4-QAM e sulla 16-QAM. Nel primo caso sono stati anche intro-
dotti degli errori di fase per giudicare la sensibilità del sistema a questi eventi. Infine
abbiamo voluto osservare come sono distribuiti nel tempo gli errori commessi dal deco-
dificatore.
In coda al lavoro è stata anche inserita un’Appendice Software. In essa vengono mostra-
ti, oltre ad alcune semplici funzioni di base, due interi programmi: il primo riguarda la
decodifica di un codificatore RSC tramite l’algoritmo MAP; il secondo descrive un col-
legamento “turbo” che utilizza la modulazione 16-QAM.
Tutti i programmi con cui abbiamo eseguito le simulazioni sono stati redatti in linguag-
gio C nel Laboratorio di Sistemi di Trasmissione del Dipartimento di Ingegneria
dell’Informazione .
1
CAPITOLO 1
Generalità sui Turbo Codici
1.1 Introduzione
Nel 1993 C. Berrou,A.Glavieux e P.Thitimajshima pubblicarono il primo articolo sui
turbo codici. Questi rappresentano sicuramente la scoperta più importante nel campo
della codifica dall’introduzione dei codici a traliccio da parte di Ungerboeck nel 1982.
L’invenzione dei turbo codici coinvolge nuove idee insieme ad alcuni vecchi concetti e
algoritmi (l’algoritmo BCJR che noi applicheremo è del 1974).
Il concetto base di tale nuovo schema di (de)codifica è l’uso di una concatenazione in
parallelo di almeno due codificatori, con un interleaver posto fra essi. In fase di decodi-
fica abbiamo dei decoder ( di solito sono due ) che ricevono campioni continui sulle
ampiezze ( soft-in ) e producono campioni ancora continui ( soft-out ) e che operano as-
2
sieme ed in maniera iterativa. Per chiarire meglio la loro struttura, vediamo una prima
schematizzazione del turbo encoder e del turbo decoder.
Dati
Turbo Encoder Turbo Decoder
Sono due le strategie di decodifica fondamentali per i turbo codici: il SOVA (soft out-
put Viterbi algorithm) e il symbol-by-symbol MAP algorithm (il BCJR o algoritmo di
BAHL et al.). Quest’ultimo è ottimo nella stima degli stati o delle uscite di un processo
di Markov con rumore bianco. Esso minimizza la probabilità di errore sul simbolo (o sul
bit), mentre il SOVA fornisce una stima della sequenza di bit trasmessa e quindi non ga-
rantisce una BER minima. Comunque le prestazioni del SOVA si avvicinano a quelle
dell’algoritmo MAP ad alti rapporti segnale/rumore ed ha dalla sua la notevole minor
complessità.
Nel caso però della decodifica iterativa a cui siamo interessati, il piccolo vantaggio in
prestazioni ad ogni iterazione che il MAP accumula sul SOVA porta ad un guadagno
considerevole per l’intero decoder. In questa tesi è il BCJR l’algoritmo prescelto.
Fra l’altro dovremmo specificare che non vi è niente di “turbo” nel codificatore, solo il
decodificatore utilizza un “turbo” feedback ed infatti alcuni chiamano questo metodo
Encoder 1
Encoder 2
Interleaver
Decoder 1
Decoder 1
Interleaver Deinterleaver
3
“Turbo-Principle” [Hag97], poichè esso può essere applicato a vari problemi riguardanti
la ricezione/decodifica: concatenazione seriale di codificatori, equalizzazione, coded
modulation, etc. Il nome “turbo” si giustifica osservando che il decoder utilizza le sue
uscite come ingressi a priori nell’iterazione successiva, come in un motore turbo.
Ricordiamo infine che, sebbene i suoi componenti siano abbastanza semplici, il “turbo”
schema è capace di raggiungere prestazioni molto vicine al limite di Shannon, special-
mente con interleaver con “N” abbastanza elevato (i permutatori operano su blocchi di
N bit) e probabilità di errore sul bit di almeno 510− .
Descriveremo ora, nei vari paragrafi di questo capitolo, le varie parti che costituiscono il
“turbo” schema.
1.2 Codificatori convoluzionali ricorsivi sistematici
Un codificatore convoluzionale introduce bit ridondanti nella sequenza di dati attraverso
l’uso di shift registers come mostrato nello schema di fig.1.1. Ad ogni istante i entrano
nel codificatore k cifre binarie u )( p
i
(p = 0,1...k-1) provenienti dalla sorgente di infor-
mazione. Abbiamo poi k linee di ritardo, le quali possono avere lunghezze diverse
m 0 ,m1 ,...,m 1−k . Fra l’altro quella massima è detta memoria del codificatore: m =
max
l
}{
l
m . Quindi ci sono n sommatori modulo 2 ai quali arrivano alcune compo-
nenti dei vettori u
li− (l = 0,1,...m). Le connessioni fra i sommatori e tali vettori cambia-
no da un codificatore all’altro. Infine, all’uscita dei sommatori ho n cifre binarie c )(r
i
(r = 0,1,...n-1).
4
u )0(
i
u )0( mi− c
)0(
i
u )1(
i
u )1( mi− c
)1(
i
u )1( −k
i
u )1( −
−
k
mi c
)1( −n
i
Fig. 1.1
Vediamo ora qualche definizione base riguardante i convoluzionali.
Il constraint length per un codificatore convoluzionale è K= m+1. Esso ci informa sul
numero di bit da cui dipende l’uscita.
Il tasso di codifica ( rate ) è invece r = k/n. Esso indica il numero di bit di informazione
per bit di codice. Valori tipici sono 1/3,1/2, 2/3, 3/4, 7/8.
La memoria totale del codificatore è ∑
−
=
=
1
0
k
l
ltot mm . Il codificatore può quindi trovarsi in
2 totm stati distinti.
Un qualsiasi codificatore convoluzionale si può rappresentare in vari modi: attraverso i
suoi Generatori, attraverso un Diagramma di Stato, con un Diagramma a Traliccio.
D
z
D D
D
D
+
+
+ D
D D
D
5
La rappresentazione con i generatori mostra le connessioni hardware fra le celle di ritar-
do ed i sommatori modulo 2 che producono le uscite. Ogni componente di un vettore
generatore vale 1 o 0 a seconda che ci sia o no connessione. Ad esempio il codificatore
di fig. 1.2,avente r =1/2 e K=3,ha generatori g 1 = [1 1 1] e g 2 =[1 0 1] e può essere rap-
presentato dalla matrice
G = [g 1 ,g 2 ].
c )1(
i
u
i
c )2(
i
Fig 1.2
Se invece consideriamo un RSC, ovvero un codificatore Convoluzionale Ricorsivo Si-
stematico, esso ha una matrice dei generatori, sempre con rate ½, siffatta: G = [1,
1
2
g
g
] .
Il primo termine è dovuto al fatto che il codificatore è sistematico: essendo tale infatti
una delle sue uscite è uguale all’ingresso. Il secondo termine è invece dovuto alla ricor-
sività: un codificatore ricorsivo si ottiene da uno non ricorsivo riportando in ingresso
una delle uscite ( in pratica una retroazione ). Nel caso di fig. 1.3 la prima uscita del co-
D D
+
+
6
dificatore non ricorsivo, rappresentata da g1 , è riportata in ingresso. Il codificatore è di-
venuto ricorsivo e anche sistematico, in quanto una delle sue uscite (qui è c )1( ) è rappre-
sentata dal bit informativo di ingresso.
c )1(
i
u
i
c )2(
i
Fig. 1.3
Spesso si esprimono i generatori mediante polinomi nella variabile D. Ad esempio
g 1 = [1 1 1 ] equivale a g1 = 1+D+D 2 e g 2 = [ 1 0 1 ] equivale a g 2 = 1+ D 2 . Per ottenere
buoni codici importante è che g1 sia un polinomio primitivo . Inoltre c’è da notare che,
per un codificatore ricorsivo, se e solo se la sequenza di ingresso è divisibile per g1 (D)
la sequenza di codice avrà peso finito, dove il peso è il numero di 1 contenuti nella se-
quenza, ovvero il numero di discordanze dalla sequenza di riferimento composta da tutti
0. Quindi una sequenza di ingresso u(D) di peso 1 produrrà una sequenza di uscita di
peso infinito, cioè crea sul traliccio un percorso che diverge dalla sequenza di riferimen-
to e mai più ci si riconnette. Al contrario esiste sempre un percorso che diverge e poi ri-
+
+
+ D D
7
confluisce che corrisponde a una sequenza di ingresso di peso 2. Tale sequenza di in-
gresso ha una forma del tipo D j (1+D 1−q ), con j ≥ 0 e, con g1 primitivo di grado m,
q = 2 m .
Nel turbo encoder vengono utilizzati i codificatori RSC. Già Forney in un articolo del
1970 aveva sottolineato l’importanza di tali codici, paragonandoli con quelli non siste-
matici (NSC). Ma Viterbi, poco dopo, fece un’analisi comparativa fra codificatori si-
stematici e non, tralasciando la ricorsività e , poichè in effetti i codici convoluzionali si-
stematici non ricorsivi non sono molto attraenti per la loro piccola distanza ( ovvero
producono sequenze simili fra loro, con poche discordanze ), i codici sistematici, ricor-
sivi o no, vennero messi da parte.
Invece è stato poi mostrato che, a bassi rapporti segnale/rumore e con rate minori di 2/3,
le prestazioni di un RSC sono migliori di un NSC, mentre per rate maggiori lo sono a
qualsiasi SNR [Ber96].
Nelle nostre simulazioni sui turbo codici abbiamo utilizzato due encoder diversi a 16
stati. In fig. 1.4 è rappresentato il primo, che abbiamo chiamato cod. Barbu [Bar96] che
ha rate = ½ e generatori, espressi in ottali, g1 = 37 e g 2 = 21.
In fig 1.5 è invece rappresentato il codificatore che abbiamo chiamato Ryan [Rya98] ,
sempre con rate ½ e generatori g1 = 31, g 2 = 33.
In questo lavoro non ci siamo dedicati alla ricerca di un codificatore RSC ottimo ma na-
turalmente la scelta del codificatore è, anche se non tanto come quella dell’interleaver,
molto importante per l’ottenimento di più o meno buone prestazioni del sistema.
8
u
k
u
k
c
k
Fig. 1.4
u
k
u
k
c
k
Fig. 1.5
Poniamo infine l’attenzione sul “Trellis termination”, ovvero su come far terminare le
sequenze di ingresso al codificatore affinchè esso finisca nello stato 0, condizione che
+ D D D D
+
+ + +
+ D D D D
+
+
9
considereremo in seguito. Per il codificatore convoluzionale convenzionale basta ag-
giungere m ( m è la memoria dell’encoder) zeri alla fine della sequenza informativa di
ingresso. Si tratta del cosiddetto “tail”. Negli RSC tale strategia non è possibile a causa
della presenza del feedback e i bit di coda sono molto difficili da predire, dipendendo
dallo stato dell’encoder. Un semplice modo per superare questo problema è mostrato in
fig. 1.6 per il codificatore di fig. 1.3. Ammettiamo di dover inviare un blocco di N dati.
I primi N-2 (ovvero i bit informativi ) saranno codificati con lo switch in posizione A;
gli ultimi due bit, costituenti il tail, si trovano ponendo lo switch in posizione B. In
questo caso infatti nella prima cella di ritardo dell’encoder entra sempre uno 0 : con due
ingressi ho il codificatore nello stato 0.
B
u
A
c 2
c1
Fig. 1.6
D D
+
+
+
10
1.3 Struttura del turbo encoder e sue prestazioni
1.3.1 Struttura del codificatore
Come già accennato, il turbo encoder si basa sulla concatenazione di più codificatori
RSC. Esistono due modi per concatenare i codificatori, concatenazione seriale e paralle-
la. Consideriamo il caso di un solo bit in ingresso ad ogni colpo di clock. In quella seria-
le il codice totale è prodotto da due codificatori: l’uscita del primo codificatore è
l’ingresso del secondo. In quella parallela tengo invece conto di (n-1) codificatori ed il
bit informativo viene simultaneamente applicato in ingresso a tutti gli (n-1) encoder. In
fig. 1.7 e 1.8 rispettivamente illustriamo le due tecniche.
u
k
c
k
Fig. 1.7
c 0
k
u
k
c1
k
c 2
k
c 1−n
k
Fig. 1.8
Encoder 1 Interleaver Encoder 2
Encoder 1
Interleaver 2
Interleaver 3
Encoder 2
Interleaver n-1
Encoder n-1
11
Per entrambi i metodi, un interleaver è inserito fra i codificatori per dare casualità alle
sequenze in ingresso ad essi e migliorare la capacità di correzione degli errori.
C’è da dire che il rate complessivo nei due casi è ben diverso. Nella concatenazione se-
riale è il prodotto dei due rate dei singoli codificatori: R = r1 r 2 . In quella parallela ri-
sulta essere R = 1/n.
I turbo codici utilizzano la concatenazione parallela in fase di codifica. Invece, il turbo
decoder si basa su una concatenazione seriale di decodificatori. Infatti tale tecnica fun-
ziona meglio di un eventuale schema in parallelo perchè in quest’ultimo caso i due
decoder lavorerebbero indipendentemente l’uno dall’altro mentre nel caso seriale con-
dividono le informazioni.
Vediamo ora, in figura 1.9, la struttura del classico turbo encoder che abbiamo utilizzato
nelle nostre simulazioni. I nomi delle variabili sono quelli che useremo in seguito.
u = x s
x p1
x p1 , x p2
u’ x p2
Fig. 1.9
puncturing
RSC Encoder 1
RSC Encoder 2
N bit
Interleaver
12
Nel codificatore di figura 1.9 i due convoluzionali sono considerati, senza perdita di ge-
neralità, identici ed inoltre hanno rate ½ . Ci sono quindi a disposizione due uscite si-
stematiche e due non sistematiche, chiamate “parity”. Soltanto una delle uscite sistema-
tiche viene però utilizzata, dato che l’altra è soltanto una versione permutata di quella
scelta, che nel nostro caso è quella relativa al primo codificatore (poteva anche tranquil-
lamente essere l’altra). In pratica perciò in fig. 1.9 x
s
e x
p1
sono le due uscite
dell’encoder1 ( anche in letteratura negli schemi del turbo encoder gli RSC sono sempre
raffigurati con una uscita, la parity ).Quindi, non tenendo conto del meccanismo di pun-
cturing, il nostro turbo encoder avrebbe rate 1/3 e perciò mapperebbe N bit informativi
in 3N bit codificati (lavorando l’interleaver su blocchi di N bit). Col puncturer invece
riusciamo ad ottenere rate diversi. Infatti, ad esempio, per questioni di efficienza spet-
trale un rate r = ½ o maggiore è preferibile. Il ruolo del puncturer è quindi quello di e-
liminare periodicamente alcuni bit selezionati per ridurre la ridondanza introdotta dal
codificatore. Solitamente si preferisce cancellare soltanto i parity bit. Ad esempio, per
ottenere un rate di ½ possiamo eliminare tutti i parity bit di posto pari che escono
dall’encoder 1 e tutti quelli di posto dispari che escono dall’encoder 2. Quindi, riferen-
dosi alla figura 1.9, in uscita al codificatore avrei alternativamente ( x
s
= u, x
p
= x
p1
)
nelle posizioni dispari e (x
s
= u, x
p
= x
p2
) nelle posizioni pari. Un modo per evidenzia-
re il rate di un codificatore è quello di definire le matrici di punturazione. In esse i bit
che dovranno essere eliminati sono evidenziati tramite uno 0, quelli che faranno parte
del codice con un 1.
Ricevi informazioni sui nostri servizi, sulle offerte e non perdere news e consigli su università e lavoro.
