+ All Categories
Home > Documents > Turbo Codici

Turbo Codici

Date post: 16-Jul-2015
Category:
Upload: iaia-amadani
View: 309 times
Download: 0 times
Share this document with a friend

of 54

Transcript

TURBO CODICI E DECODIFICA ITERATIVA

Lo sviluppo pi interessante e potenzialmente pi importante nella teoria dei codici negli ultimi anni certamente stata lintroduzione dei cosiddetti turbo codici da parte di Berrou ed altri a ICC nel 1993. Le prestazioni, verificate ben presto anche da altri gruppi di ricercatori, sono promettenti in quanto effettivamente vicine ai limiti teorici previsti da Shannon.

TURBO CODICI E DECODIFICA ITERATIVA I turbo codici devono il loro nome allalgoritmo di decodifica, che usa una retroazione, come il motore turbo: tale algoritmo prende il nome di decodifica iterativa.

TURBO CODICI E DECODIFICA ITERATIVA Vi sono alcune questioni che emergono dal lavoro presentato a ICC93, e cio: Le prestazioni dei turbo codici decodificati a ML comparate con quelle ottenibili applicando un algoritmo di decodifica iterativa. Il fatto che le prestazioni migliorino con la lunghezza dellinterleaver (fenomeno noto come interleaver gain). Luso di codici costituenti sistematici e ricorsivi (RSC): sono strettamente necessari? Il ruolo dei codici costituenti nel determinare la prestazione di un turbo codice e il loro progetto.

TURBO CODICI E DECODIFICA ITERATIVA Un turbo codice sostanzialmente costituito dalla concatenazione parallela di due codici convoluzionali (PCCC: Parallel Concatenated Convolutional Codes) per mezzo di un interallacciatore non uniforme.

TURBO CODICI E DECODIFICA ITERATIVA I due codici costituenti sono codici convoluzionali sistematici ricorsivi (RSC: Recursive Systematic Convolutional Codes) concatenati secondo lo schema mostrato in figura. Laspetto pi significativo di questi codici la loro ricorsivit, mentre la sistematicit non vincolante. La sequenza dei simboli di ingresso viene codificata una prima volta da un codice RSC, mentre una sua versione interallacciata codificata dal secondo codice (dello stesso tipo del primo).

TURBO CODICI E DECODIFICA ITERATIVA

Codice PCCC. Tasso di codifica: 1/3

TURBO CODICI E DECODIFICA ITERATIVA

Codice non sistematico e non ricorsivo. G(D)=[(1+D+D2), (1+ D2)] Tasso di codifica: 1/2

Codice sistematico e ricorsivo (RSC). G(D)=[1, (1+ D2)/ (1+D+D2)] Tasso di codifica: 1/2

TURBO CODICI E DECODIFICA ITERATIVA La matrice G(D)=[g(1)(D), g(2)(D)] la generica matrice generatrice di un codice a tasso 1/2 non sistematico non ricorsivo. Le sue parole di codice sono esprimibili come: V(D )=[v(1)(D), v(2)(D)] )=[u(D)g(1)(D), u(D)g(2)(D)] dove u(D) la sequenza dinformazione. La matrice G(D)=[1, g(2)(D)/ g(1)(D) ] la generica matrice generatrice di un codice a tasso 1/2 sistematico ricorsivo equivalente al precedente. Le sue parole di codice sono esprimibili come: V(D )=[v(1)(D), v(2)(D)] )=[u(D), u(D)g(2)(D)/ g(1)(D)] dove u(D) la sequenza dinformazione.

TURBO CODICI E DECODIFICA ITERATIVA I due codici di figura sono equivalenti, nel senso che hanno la stessa distanza libera, la stessa distribuzione dei pesi duscita e lo stesso traliccio, per quanto riguarda le transizioni di stato e i corrispondenti bit duscita. Tuttavia la mappatura tra le sequenze dingresso e quelle duscita differente per i codici ricorsivi e non ricorsivi. Come conseguenza, le probabilit derrore sulla parola saranno le stesse, mentre le probabilit derrore sul bit saranno diverse.

TURBO CODICI E DECODIFICA ITERATIVA Infatti, si considerino i due codici equivalenti riportati in figura. Il primo un codice a tasso 1/2 non sistematico non ricorsivo dato da: Gns(D)=[(1+D+D2), (1+ D2)] Il secondo un codice a tasso 1/2 sistematico ricorsivo dato da: Gs(D)=[1, (1+ D2)/ (1+D+D2)]

TURBO CODICI E DECODIFICA ITERATIVA La sequenza dingresso u(D)=1 al codice non sistematico genera la parola di codice V(D)=u(D) Gns(D)=[1+D+D2, 1+ D2] La sequenza dingresso u(D)= 1+D+D2 al codice sistematico genera la parola di codice V(D)=u(D) Gns(D)=[1+D+D2, 1+ D2] Si noti che, sebbene la parola di codice sia la stessa in entrambi i casi, la sequenza dingresso ha peso 1 nel caso non sistematico e peso 3 nel caso sistematico.

CODICE NON RICORSIVO

Codice non sistematico e non ricorsivo. G=[(1+D+D2), (1+ D2)] Tasso di codifica: 1/2

Suo diagramma di stato

CODICE NON RICORSIVOa i:00D 2B

b:10DB

D B

c:01D

D2

a f :00

d:11DB

Diagramma di stato modificato

T (D , B ) =

k =0

2 k D k + 5 B k +1

CODICE NON RICORSIVO

T ( D ) = T ( D , B ) B =1 =

= D + 2D6 + 4D7 + L Lesponente della variabile D nel primo termine dello sviluppo (k=0) permette di determinare la distanza libera dfree (free distance) del codice (nellesempio dfree=5).

k =0 5

2 k D k +5

CODICE NON RICORSIVO

Ingresso al codice 1: a b c 0 0 1 0 0 0 0

Se il codice non ricorsivo, un ingresso di peso unitario produrr sempre una parola di codice di peso basso alluscita.

CODICE NON RICORSIVO

Ingresso al codice 2: a b c 0 0 0 0 0 0 1 0 0

Se il codice non ricorsivo, un ingresso di peso unitario produrr sempre una parola di codice di peso basso anche alluscita del secondo codice costituente.

CODICE NON RICORSIVO

Se i codici costituenti sono non ricorsivi, un ingresso di peso unitario produrr sempre una parola di codice di peso basso sia alluscita del primo che del secondo codice costituente.

Linterleaver non ha nessun effetto sulla distribuzione dei pesi delle parole del codice concatenato.

CODICE RICORSIVO

10

01

Codice sistematico e ricorsivo (RSC). G=[1, (1+ D2)/ (1+D+D2)] Tasso di codifica: 1/2

Suo diagramma di stato

CODICE RICORSIVO

a i:00

D 2B

b:10D

DB

c:01D

D 2B

a f :00

d:11DB

Diagramma di stato modificato

CODICE RICORSIVOIngresso al codice 1: a b c d 0 0 1 0 0 0 0 0 0

Se il codice ricorsivo, un ingresso di peso unitario produrr una sequenza infinita di 1 alluscita.

CODICE RICORSIVO

Se il codice ricorsivo, un ingresso di peso unitario provoca uno scostamento dallo stato nullo (a) senza possibilit di ritornarvi.

Non ci possono essere errori dovuti a un ingresso di peso unitario.

Dobbiamo preoccuparci degli ingressi di peso 2 (sequenza dingresso con due 1).

CODICE RICORSIVO Laffermazione Non ci possono essere errori dovuti a un ingresso di peso unitario dimostrata in: S. Benedetto and G. Montorsi, Design of Parallel Concatenated Convolutional Codes, IEEE Trans. on Communications, Vol. 44, No. 5, May 1996, pp. 591-600.

La matrice G(D)=[1, g(2)(D)/ g(1)(D) ] la generica matrice generatrice di un codice a tasso 1/2 sistematico ricorsivo. Per questo codice, eventi derrore di peso finito sono prodotti da polinomi multipli di g(1)(D). Ogni polinomio g(1)(D) divide un polinomio nella forma 1+Di. Daltra parte, poich g(1)(D) ha forma 1+D+...+Dn, esso non pu dividere un polinomio nella forma Di per ogni i.

CODICE RICORSIVO

Una sequenza dingresso al primo codice costituente con due 1 produce:Ingresso al codice 1: a b c d 0 0 1 0 0 1 0 0 0

CODICE RICORSIVO

Se linterleaver mantiene le posizioni dei due 1 inalterate, alluscita del secondo codice ottengo la stessa parola di codice. Altrimenti, ci che si ottiene :Ingresso al codice 2: a b c d 0 0 1 0 0 0 0 0 1 0

IL RUOLO DEL CODICE RICORSIVO

Paragone delle BER di PCCC utilizzanti codici sistematici ricorsivi (SR) e non ricorsivi (SNR).Tratto da: S. Benedetto and G. Montorsi, Unveiling Turbo Codes: some results on Parallel Concatenated Coding schemes, IEEE Transactions on Information Theory, Vol. 42, No. 2, March 1996, pp. 409-428.

IL RUOLO DEL CODICE RICORSIVOLa curva A corrisponde alla modulazione BPSK non codificata. Le curve B e C si riferiscono ai codici costituenti (CC) non ricorsivi. Curva B: semplice duplicazione del bit di ridondanza in uscita dal primo CC. Curva C: uso di un interleaver di lunghezza 1000. Le curve D ed E si riferiscono ai codici costituenti (CC) ricorsivi. Si nota un significativo miglioramento per N=1000: guadagno di 3 dB a 10-5.

IL RUOLO DEL CODICE RICORSIVOIl guadagno di interleaver N -1 per sequenze dingresso di peso 2 e, in generale, N (1-w) per sequenze di peso dingresso w. Il parametro wmin (minimo w in ogni evento derrore di peso finito) cruciale nel progetto dei codici costituenti.

Codici convoluzionali ricorsivi: wmin =2 Codici convoluzionali non ricorsivi: wmin =1

Guadagno di interleaver: N -1 Guadagno di interleaver indipendente da N

PRESTAZIONI DEI CODICI: la Probabilit derrore sulla parola Per un codice (n, k) di tasso Rc=k/n, la funzione enumeratrice dei pesi duscita (OWEF: Output Weight Enumerating Function) definita come: B(W ) = Bh H h n

h =0

dove Bh il numero di parole di codice con peso di Hamming h.

PRESTAZIONI DEI CODICI: la Probabilit derrore sulla parola Assumendo che il codice binario lineare sia trasmesso su un canale AWGN, con una modulazione PSK/PAM binaria, e decodificato a Massima Verosimiglianza (ML), a partire dalla OWEF, lapplicazione del limite dellunione conduce a un limite superiore alla Word Error Probability dato da: hRc Eb 1 Bh erfc N < 2 [B(H ) 1] H =exp( Rc Eb / N0 ) 0 h = d min 2 erfc( x ) = n

1 Pw (e ) 2

dove

t 2 dt e

e

erfc( x )


Recommended