83
Timisoara 18-20 mars 2003 ENST Bretagne 1 Turbo Turbo c odes odes ( convolutifs convolutifs) Timisoara 18-20 mars, 2003 Michel Jézéquel, Claude Berrou et Catherine Douillard ENST Bretagne [email protected] Plan 1. Les codes correcteurs d’erreurs 1. Généralités 2. Limites Théoriques 2. Les codes convolutifs 1. Les codes classiques 2. Les codes RSC 3. Poinçonnage et terminaison 3. Les algorithmes SISO 1. SOVA 2. MAP 3. SUB-MAP 4. Turbo codes La philosophie Les différents schémas Turbo décodage 5. Permutation Régulière Aléatoire Pseudo-aléatoire 6. Turbo codes duo-binaires Principe et avantages Performance 7. Conclusions et perspectives

Turbo codes (convolutifs) Plan

Embed Size (px)

Citation preview

Page 1: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 1

Turbo Turbo ccodesodes((convolutifsconvolutifs))

Timisoara18-20 mars, 2003

Michel Jézéquel,

Claude Berrou et Catherine Douillard ENST Bretagne

[email protected]

Plan

1. Les codes correcteurs d’erreurs 1. Généralités2. Limites Théoriques

2. Les codes convolutifs1. Les codes classiques2. Les codes RSC3. Poinçonnage et terminaison

3. Les algorithmes SISO1. SOVA2. MAP3. SUB-MAP

4. Turbo codes• La philosophie• Les différents schémas• Turbo décodage

5. Permutation• Régulière• Aléatoire • Pseudo-aléatoire

6. Turbo codes duo-binaires• Principe et avantages• Performance

7. Conclusions et perspectives

Page 2: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 2

Chapitre 1

Les codes correcteurs d’erreurs

Sourcenumérique Codage

Modulation et filtrage

Milieude

transmission

Filtrage etdémodulation

DécodageDestinataire

Canal de transmission

Di

Di

Une chaîne de transmission

Page 3: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 3

Codes correcteur d’erreurs Généralités

Codage de source : réduire le débit d’informationCodage de canal : ajouter de la redondanceSécurité, cryptographieAuthentification, watermarkingCDMA...

Différentes familles de codage

Codes correcteur d’erreurs GénéralitésSéquence d’information à transmettre : [d1 d2 ... di ... dk]

Addition d’une redondance linéaire : [r1 r2 ... rj ... rn-k](le code est dit systématique)

2mod ...1

, dprki

ijij ∑=

= (pi,j = 0 ou 1)

[r1 r2 ... rj ... rn-k] = [d1 d2 ... di ... dk]

p1,1

pk,1

p1,n-k

pk,n-k

Forme matricielle

Page 4: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 4

Rendement de codage : R =k/n

Code (n , k , dmin) de distance minimale dmin

Codes correcteur d’erreurs Généralités

Le code étant linéaire, la séquence « tout zéro » peut être prise comme référence

La distance dmin est le nombre minimum de « 1 » des mots de code [d1 d2 ... di ... dk] [r1 r2 ... rj ... rn-k]si [d1 d2 ... di ... dk] ≠ « tout zéro »

[d1 d2 ... di ... dk][r1 r2 ... rj ... rn-k] : mot de code

Un bon code est un code avec une grande distance dminmais ce n’est pas tout :• il doit pouvoir être décodé !

(contre-exemple : les codes aléatoires)• il doit exister un décodeur permettant d’utiliser

la capacité de correction du code

Exemple :

Codes correcteur d’erreurs Généralités

Page 5: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 5

5

5

5

5

5

5

5

5

10-1

10-3

10-4

10-6

10-7

10-8

20 1 3 4 5 6 7 8 9 10 11 12

Eb/N0 (dB)

TEB

non codé

mauvaise convergence, gain asymptotique élevé

Bonne convergence, faible gain asymptotique

10-2

10-5

Limite théorique(R=1/2, 188 octets)

MDP4, canal gaussien, taux d’erreurs cible : 10-8

Ga = 10 log (R.dmin)

dmin > 25

∫∞

=−=

xt

b

dttxerfc

avecNEerfc

)exp(2)(

)(21

2

0

π

distinction traditionnelle mais inappropriée entre

Les codes en « bloc » : Hamming, Golay, BCH, Reed-Solomon, ...

Les codes « convolutifs »

Une distinction plus naturelle prendrait en compte l’algorithmede décodage, en particulier :• hard – dur (algébrique)• soft – souple (probabiliste)

Exemple :

Codes correcteur d’erreurs Généralités

Page 6: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 6

di Hamming étendu

Yi di Hamming étendu

Yi

0000 0000 0000 1111 1111 11110001 0111 1011 1110 1000 01000010 1101 0111 1101 0010 10000011 1010 1100 1100 0101 00110100 1110 1110 1011 0001 00010101 1001 0101 1010 0110 10100110 0011 1001 1001 1100 01100111 0100 0010 1000 1011 1101

000001010011100101110111

di

(donnée)

Xi

s3s2s1

Yi

Etat

X=0, Y=0X=0, Y=1X=1, Y=0X=1, Y=1

Comment transformer un code de Hamming parfait (8,4,4)

(autre exemple : le code de Golay étendu (24, 12, 8) peut être représenté par un treillis circulaire 16 états)

Codes correcteur d’erreurs Généralités

Codes correcteur d’erreurs GénéralitésCode aléatoire (Shannon)

1 .... i ... kInformation Redondance

1 .... j ... n- k10000000 ... 0000000000000001000000 ... 0000000000000000100000 ... 000000000000001111010001...0001111011

00000000 ... 00000000000001

0010010111...01100001001001110100...0011101001

1010101110...1010111101.............

10010110 ... 100011000101010011101011...1110010100

Σ

dmin ≈ (n-k)/4 = k.(1-R)/4R où R = k/n

Page 7: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 7

Codes correcteur d’erreurs Généralités

dmin ≈ (n-k)/4 = k.(1-R)/4R où R = k/n

Exemple : k = 1504 (MPEG), R = 1/2dmin ≈ 375 !!

(un code convolutif 64 états a une distance dmin = 10 pour R = 1/2 !!)

Mais non décodable en pratique ...

Codes correcteur d’erreurs Généralités

extensionde la bande (dB)0 1 2 3

Limite (Eb/N0, dB) (k infini) [Shannon, Proakis]

0

1

2

3

canalcontinu

canalà entréebinaire

R=1/2R=2/3R=3/4R=4/5R=5/6

(sur la base d’un code aléatoire)

Page 8: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 8

Taille du bloc (k)

∆ Eb/N0 (dB)

1

2

3

4

5

100 101 102 103 104 105

(taux d’erreurs paquets = 10-4)

Correction à prendre en compte pour des bocks de taille k :[S. Dolinar, D. Divsalar and F. Pollara, "Code performance as afunction of block size", TMO progress report 42-133, JPL, NASA].

Codes correcteur d’erreurs Généralités

Calcul des limites

Un outil de calcul des limites théoriques a été développé par un étudiant en thèse il est disponible à l’adresse :http://www-elec.enst-bretagne.fr/~emaury/Capa_UI.html

Page 9: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 9

Chapitre 2

Codes convolutifs

Plan

• Codes convolutifs classiques– Représentations– Propriétés

• Codes convolutifs systématiques• Codes convolutifs récursifs systématiques• Rendement de codage et poinçonnage• Fermeture de treillis

Page 10: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 10

Codes convolutifs

b bits

d’information1 2 3 K=m+1

Registre à décalage (mb étages)

fonctions linéairesmot de code n symboles

K= longueur de contrainte

R=b/n (rendement de codage)

b b

di di-1 di-2D D

xi

yi

di di-1 di-2D D

yi

Elias, 1954

Forney, 1970

Mémoire du code : ν = 2

Longueur de contrainte :K = ν + 1 = 3

R = 1/2

Code convolutif classique

Page 11: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 11

Exemple

D Ddi di-1 di-2

xi

yi

• K=3

• b=1

• n=2

•R=b/n=1/2

Exemple

state 0 0 2 1 0 0 2 3 1 0 0 0 0 0

D Ddi di-1 di-2

di

xi

yi

xi

yi

Page 12: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 12

Générateurs

D Ddi di-1 di-2

∑=

−=2

0

1

jjiji dgx

∑=

−=2

0

2

jjiji dgy

[ ] [ ]1,0,1,, 12

11

10

1 == gggg ( ) 212

11

10

1 DgDggDG ++=

[ ] [ ]1,1,1,, 22

21

20

2 == gggg ( ) 222

21

20

2 DgDggDG ++=

Générateurs sous la forme octale : (5,7)

Représentation des codes convolutifs

• arbre• machine d’état• treillis

Trois formes :

Page 13: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 13

arbreD D

00

11

0

110

01 1100

00 00

11110110

1001

di di-1 di-2

xi

yixi yi

Machine d’états

D Ddi =0

di =1

00

01

10

1100

11 10

01

11

0001

10

xi yi

xi yi

di di-1 di-2

xi

yi

Page 14: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 14

TreillisD D

00

01

10

11

0011 11

011010

0001

0011 11

011010

0001

0011 11

011010

0001

0011

10

01

0011

di =0

di =1

xi yi

xi yi

di di-1 di-2

xi

yi

Treillis

D Ddi di-1 di-2

xi

yi

00

01

10

11

0011 11

011010

0001

di =0 xi yi

di =1 xi yi

Page 15: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 15

Distance

00

11 11

011010

00

01

00

11 11

011010

00

01

00

11 11

011010

00

01

00

11

10

01

00

1100

01

10

11

00

11

01

11

00 00 00

Distance de Hamming 0 0212+ ++ + + 0 =5

(K=3) (5,7) -> distance libre = dlibre=5(K=3) (5,7)

Poids=P=1

Distance

00

11 11

011010

00

01

00

11 11

011010

00

01

00

11 11

011010

00

01

00

11

10

01

00

1100

01

10

11

00

11

01

11

00 00 00

Distance de Hamming 0 2112+ ++ + + 0 =6

(K=3) (5,7) -> distance libre = dlibre=5

11

1010

11

00 00

Poids =P=2

Page 16: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 16

Poids =P=2+2=4Poids =P=2

Distance

00

11 11

011010

00

01

00

11 11

011010

00

01

00

11 11

011010

00

01

00

11

10

01

00

1100

01

10

11

00

11

01

11

00 00 00

Distance de Hamming 0 1012+ ++ + + 2 =6

(K=3) (5,7) -> distance libre = dlibre=5

11

1010

11

00 00

1111

00

0101

00

Distance

• Longueur de contrainte : K = 3• Générateurs (5,7)

– Distance libre minimale = 5 – Spectre des distances:

• Distance = 5 (1 cas), P=1• Distance = 6 (2 cas), P=4• Distance = 7 (4 cas), P=12• ….

Page 17: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 17

Codes systématiques

xi

D Ddi

yi

xi=di

NSC(Non Systematic Convolutional)

D Ddi

yiSC

(Systematic Convolutional)

Exemple : K=3, b=1, n=2, R=b/n=1/2

Codes systématiques(machine d’états)

xi

D Ddi

yi

xi=di

NSC

D Ddi

yiSC

10

00

01

1100 11 10

0111

0001

1000

01

10

1100 11 10

0101

1011

00

di =0 xi yi

di =1 xi yi

Page 18: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 18

Codes systématiques (treillis)

D D

NSC

D D

SC

di =0

di =1

00

01

10

11

0011 11

011010

0001

00

01

10

11

0011 01

011000

1001

xi

di

yi

xi=di

di

yi

xi yi

xi yi

Codes systématiques(distance)0000

01

10

11

00

11

01

11

00 00

Distance libre minimale

0 0212+ ++ + =5NSC

0 0112+ ++ + =4SC

01

01

11

00 00

11

00

1000

01

0 1012+ ++ + =4

Poids=P=1+2=3Poids=P=1

Page 19: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 19

Spectre des distances

4486400d=111923220134d=10801600d=93285813d=812400d=742155d=6

51205122052233d=14230425600d=13102412865589d=12

1100d=50032d=4P NSCnP SCn

n = nombre de cas

P = poids

Codes systématiques (Taux d’Erreurs Binaire)

1,E-08

1,E-07

1,E-06

1,E-05

1,E-04

1,E-03

1,E-02

1,E-01

1,E+00

0 2 4 6 8 10 12

Non codéSCNSC

Eb/N0

TEB

Page 20: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 20

Interprétation des résultats

Codes convolutifs

Existe-t-il un code convolutif combinant :

• les distances minimales des codes non systématiques• le bon comportement à faible rapport signal/bruit

????

La réponse est : OUI

Page 21: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 21

Codes récursifs systématiques

di

xi

D D

yiNSC

Exemple:K=3, b=1, n=2, R=b/n=1/2

D Ddi

yi

xi

[1,(1+D+D2)/(1+D2)]

D Ddi

yi

xi

[1,(1+D2)/(1+D+D2)]

[(1+D2),(1+D+D2)]

Codes récursifs systématiques (treillis)

xi

D Ddi

yiNSC RSC

di =0 xi yi

di =1 xi yi

00

01

10

11

0011 11

011010

0001

D Ddi

yi

xi

00

01

10

11

0011

10

01

11

00

01

10

Page 22: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 22

Codes Récursifs systématiques(machine d’états)

xi

D Ddi

yiNSC RSC

10

00

01

1100 11 10

0111

0001

1000

01

10

1100 11 10

0111

0001

10

di =0 xi yi

di =1 xi yi

D Ddi

yi

xi

Codes récursifs systématiques(distance)00

11

Distance libre minimale =5RSC

00

11

10

01

00

11 11

101001

00

01

00

11 11

101001

00

01

00

01

10

11

00

2+

11

2+

11

0+

00

0

00

1+

01

Poids=P=2

Page 23: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 23

Spectre des distances

76801024112641024d=155122561286432168421n

3584166476835216072321462P RSC

44864d=1119232d=108016d=9328d=8124d=742d=6

5120512d=142304256d=131024128d=12

11d=5P NSCn

n = nombre de cas

P = poids

Codes récursifs systématiques (Taux d’Erreurs Binaires)

1,E-08

1,E-07

1,E-06

1,E-05

1,E-04

1,E-03

1,E-02

1,E-01

1,E+00

0 2 4 6 8 10 12

Non codéSCNSCRSC

Eb/N0

TEB

Page 24: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 24

Rendement de codage et poinçonnage

D Ddi

yi

Multiplexage &Poinçonnage

Sortie

R=1/2 xi yi xi+1 yi+1 xi+2 yi+2 xi+3 yi+3 xi+4 yi+4

R=2/3 yi+5 xi+6xi xi+1 yi+1 xi+2 xi+3 yi+3 xi+4 xi+5

R=3/4 xi xi+1 xi+2 yi+2 xi+3 xi+4 xi+5 yi+5 xi+6 xi+7

R=3/5 xi xi+1 yi+1 xi+2 yi+2 xi+3 xi+4 yi+4 xi+5 yi+5

xi

Codes poinçonnés (Taux d’Erreurs Binaire)

1,E-08

1,E-07

1,E-06

1,E-05

1,E-04

1,E-03

1,E-02

1,E-01

1,E+00

0 2 4 6 8 10 12

Non codéNSCRSC

Eb/N0

TEB Rendement de codage =3/4

Page 25: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 25

1 2 ν

d X

Y

Générateurpseudoaléatoire

R = 1/2 R = 2/3 R = 3/4 R = 4/5

R = 5/6 R = 6/7 R = 7/8

-0.2 0.2 0.6

0.03

0.07

0.06

0.04

0.05

0.020.8 1.2 1.6

0.021.6 2.0 2.4

0.03

0.07

0.06

0.04

0.05

0.02

0.06

0.05

0.03

0.04

0.011.2 1.6 2.0

= 2 = 4

= 6

0.02

0.06

0.05

0.03

0.04

0.01

0.02

0.06

0.05

0.03

0.04

0.01

0.01

0.05

0.04

0.02

0.03

0.001.6 2.0 2.4 1.8 2.2 2.6 2.2 2.6 3.0

= 8

Limite de Shannon(canal gaussien entrée binaire)

ν ν

ν ν

0.05

0.09

0.08

0.06

0.07

0.04

TEBE /Nb 0

Plus le registreest grand, meilleur est le code convolutif

Fermeture de treillisdi =0

di =1

00

01

10

11

01

10

110 1 2 3 n-1 n

Bloc de k bits, 2k bits transmis → R=1/2

00

Initialisation

0 0D Ddi

yi

xi

Page 26: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 26

Fermeture de treillisdi =0

di =1

00

01

10

1100

01

10

110 1 2 3 n-1 n

Bloc de k bits, 2k+K-1 bits transmis → R=k/(2k+K-1)

Initialisation

0 0

Transmission de l’état final

(K-1 bits)

D Ddi

yi

xi

Fermeture de treillis

00

01

10

110 1 2 3 n-1 n

Initialisation

0 0Insertion

detail bits

00

D Ddi

yi

xi

Bloc de k bits, 2k+2(K-1) bits transmis → R=k/2(k+K-1)

0D Ddi

yi

xi

Page 27: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 27

D DD

000001010011100101110111

yi

di

Codes convolutifs circulaires

0 1 1 1 1 10 0

D DD

000001010011100101110111

yi

di

Codes convolutifs circulaires

Page 28: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 28

Calcul de l’état circulation

s1 s3s2AB

11. −− += iii XSGS

S X Gi

i

i

i

i

i i

i

i

sss

A BBB

=

=+

=

1

2

3

1 0 11 0 00 1 0

,

,

,

; ;

Mod 2 (1)

La période L du générateur est telle que (Identité)

En partant de (1), nous pouvons en déduire :

G IL =

11. −− += iii XSGS

221 . −−− += iii XSGS

001 . XSGS +=

Après codage d’une séquence de longueur k :

∑=

−−+=

kpp

pkkk

...110. XGSGS (2)

Si est inversible, il existe un tel que . est appelé état de circulation.

S S Sc k= = 0Sc

Sc

∑=

−−

+=kp

pk-pk

c...1

11

. XGGIS (3)

kGI +

Page 29: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 29

En pratique :

Le codeur est initialisé à ; la séquence de longueur k est codée donnant, d’après (2) :

(3) devient :

(4)

La correspondance entre est mémorisée dans une petite fonction combinatoire (3 bits en entrée, 3 bits en sortie).

S 00 =

∑=

−−=

kpp

pkk

...11

0 XGS

S I G Sck

k= +−1 0.

0et kSS

000001010011100101110111

Codes convolutifs circulaires

0 1 1 1 1 10 0

- Codage de la séquence d’information- Détermination de l’état de circulation

• Pré-codage :

• Initialisation à l’état de circulation• Codage

- Initialisation à l’état tout zéro

000

010

Page 30: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 30

Prologue

Codes convolutifs circulaires (comment décoder ?)

Fermeture de treillis

• “tail bits” rendement de codage

☺ facile à implémenter

• codes circulaires (“tail biting” NSC)pré-codage

☺ rendement de codage

Page 31: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 31

Chapitre 3

Algorithmes de décodage à entrée et sortie pondérées ou

SISO (Soft-In Soft-Out)

Codes convolutifs algorithmes SISO

Le turbo-décodage utilise des décodeurs élémentaires à entrées et sorties pondérées.

Deux familles d’algorithmes de décodage SISO pour les codes convolutifs :

• Les algorithmes basés sur l’algorithme deViterbi

• L’algorithme MAP (Maximum A Posteriori) et ses approximations

Page 32: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 32

Illustration avec le code suivant :

D Did

iX

iY

00 (0)

01 (1)

10 (2)

11 (3)

00 (0)

01 (1)

10 (2)

11 (3)

0=id1=id

i-1 i

Codes convolutifs algorithmes SISO

Modèle de la chaîne de transmission

Les symboles transmis Xi et Yi, i = 1…k prennent leurs valeurs dans {-1,+1}

Codeurconvolutif

Canalgaussien

decodeurSISO{ }kdd ,,1 L

{ }kXX ,,1 L

{ }kYY ,,1 L

{ }kxx ,,1 L

{ }kyy ,,1 L{ }kdd ˆ,,1̂ L

source destinataire

k1c k

1r

),( avec } ,,{ 11 iiikk YXccc == Lc

: séquence codée et modulée (MDP2)k1c

k1r : séquence bruitée reçue

),,( avec } ,,{ 11 iiikk yxrrr == Lr y

iiixiii nYynXx +=+= ,

Codes convolutifs algorithmes SISO

Page 33: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 33

Application de l’algorithme de Viterbi

Codes convolutifs algorithmes SISO : SOVA

• L’algorithme de Viterbi est utilisé pour chercher le chemin à vraisemblance maximale dans le diagramme en treillis.

• Critère de décodage : maximiser }{Pr 11kk|CR

( ) ( )

σ−−

σ−−∏

σπ=

∏=

=

=

2

2

2

22

1

111

2exp

2exp

21

}{Pr}{Pr

iiiik

i

k

iii

kk

YyXx

C|R|CR

• Maximiser minimiser }{Pr 11kk|CR [ ]∑ −+−

=

k

iiiii YyXx

1

22 )()(

22 )()( iiiii YyXxL −+−=x

xxxxii

i

jji LMLM +=∑= −

=1

1

• Calcul (récursif) de la métrique de chemin associée au chemin x.

xiM

• A chaque instant i, calcul de la métrique de branche associée à chaque chemin x dans le treillis, c-a-d de la distance euclidienne entre le symbole reçu ri et le symbole codé ci associé au chemin x.

xiL

Application de l’algorithme de Viterbi

Codes convolutifs algorithmes SISO : SOVA

Page 34: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 34

0

1

2

3

0

1

2

3

di = 0di = 1

i-1 i

(-1,-1)

(1,1)

(1,-1)

(-1,1)

(-1,-1)

(1,1)

(-1,1)

(1,-1)

(Xi, Yi)

Exemple22, )1()1( +++== iiii yxLL 00x

x00x1

22, )1()1( −++++== iiiii MyxMM

x

22, )1()1( ++−== iiii yxLL 12xx12x

122, )1()1( −+++−== iiiii MyxMM

x

Codes convolutifs algorithmes SISO : SOVA

Application de l’algorithme de Viterbi

• Pour chaque nœud s, recherche du chemin à métrique minimale (le survivant) et mémorisation de la métrique associée avec la valeur de di.

)(ssiM

0

1

2

3

0

1

2

3

i-1 i

(-1,-1)

(1,1)

(1,-1)

(-1,1)

(-1,-1)

(1,1)

(-1,1)

(1,-1)

(Xi, Yi)

01,iM

00,iM )(0s

iM⇒0

13,iM

12,iM )(1s

iM⇒121,

iM20,

iM)(2s

iM⇒2

32,iM

33,iM

)(3siM⇒3

Application de l’algorithme de Viterbi

Codes convolutifs algorithmes SISO : SOVA

Page 35: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 35

0

1

2

3i1−i2−i2−− Li1−− LiLi −

))((min)(,...,

s230s

si

si MM

==

• A l’instant i-L, la décision est la valeur binaire stockée dans le nœud appartenant au chemin survivant.

Lid −ˆ

Lid −ˆ

• A l’instant i, sélection du nœud à métrique minimale,

chemin survivant

Application de l’algorithme de Viterbi

Codes convolutifs algorithmes SISO : SOVA

• Remontée le long du chemin survivant (pour profiter du futur).

• L’algorithme de Viterbi ne peut pas être utilisé pour le décodage itératif !

Il produit des décisions binaires

Il doit être modifié pour produire des décisions pondérées=> SOVA (Soft-Output Viterbi Algorithm)

Codes convolutifs algorithmes SISO : SOVA

Page 36: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 36

0)()()( ≥−=∆= sss si

ciii MMMw

• Une première estimation de la fiabilité ou du poids de la décision peut être donnée par la différence entre les métriques du chemin survivant et de l’autre chemin ( le chemin concurrent):

• Mais cette estimation doit être affinée! => algorithmes de révision des poids

0)(Si 1 >>∆ − 1iM0)(et =∆ 2iM

=> le poids à l’instant i-1 doit être revu à la baisse

0

1

2

32−− Li1−− LiLi − i1−i2−i

survivant concurrent

Codes convolutifs algorithmes SISO : SOVA

• Encore appelé algorithme BCJR (Bahl, Cocke, Jelinek, Raviv), algorithme APP (A Posteriori Probability), ou algorithme Aller-Retour (Backward-Forward)

• But de l’algorithme : calcul du Logarithme de Rapport de Vraisemblance (LRV) relative à la donnée di

L’algorithme MAP (Maximum A Posteriori)

}0{Pr

}1{Prln)(

1

1k

i

ki

id

dd

r

r

=

==Λ

k1r désigne la séquence bruitée reçue

),( avec } ,,{ 11 iiikk yxrrr == Lr

signe ⇒ décision binairevaleur absolue ⇒ fiabilité

Codes convolutifs algorithmes SISO : MAP

Page 37: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 37

},,{Pr 11k

ii rsSsS =′=−

iS : état du codeur à l’instant i

0

1

2

3

0

1

2

3i-1 i

∈′−

∈′−

=′=

=′=

0

1

),(11

),(11

},,{Pr

},,{Pr

ln)(

i

i

T

kii

T

kii

id

ss

ss

rsSsS

rsSsS

=>

1,0}{Pr

},,{Pr

}{Pr1

),(11

1 =

=′=

==∑

∈′−

jjd kT

kii

ki

ji

r

rsSsS

r ss

• Chaque APP (A Posteriori Probability) est estimée par le biais des probabilités conjointes

}{Pr 1k

i jd r=

jiT : ensemble des transitions du treillis

associées à di = j

Codes convolutifs algorithmes SISO : MAP

• Principe de l’algorithme MAP : traiter séparément les données relatives aux instants compris entre 1 et i et celles relatives aux instants compris entre i +1 et k.

=> Introduction des probabilités « aller » (forward) et « retour » (backward)

relatives aux états du treilliskii L1),( =α s kii L1),( =β s

}{Pr)( 1 sSrs ==β + ikii

},{Pr)( 1i

ii rsSs ==α

=> et des probabilités relatives aux transitions du treillis

Codes convolutifs algorithmes SISO : MAP

},{Pr),( 1 sSsSss ′===′γ −iiii r

Page 38: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 38

• On peut montrer que

=>∑

∈′−

∈′−

β′γ′α

β′γ′α

=Λ0

1

),(1

),(1

)(),()(

)(),()(

ln)(

i

i

Tiii

Tiii

id

ss

ss

ssss

ssss

)(),()(},,{Pr 111 ssssrsSsS iiik

ii β′γ′α==′= −−

Codes convolutifs algorithmes SISO : MAP

Exemple 0

1

2

3

0

1

2

3

0=id1=id

i-1 i

L)(),()()(),()()(),()()(),()(ln)(

11

111133000011220011

iiiiii

iiiiiiid

βγα+βγαβγα+βγα=Λ

−−

−−

)(),()()(),()()(),()()(),()(

11

113322221133332200

iiiiii

iiiiiiβγα+βγα+βγα+βγα+

−−

−−L

)(),()(},,{Pr 111 2211r2S1S iiik

ii βγα=== −−** )(),()(},,{Pr 111 2200r2S0S iii

kii βγα=== −−

Codes convolutifs algorithmes SISO : MAP

Page 39: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 39

• Récursion aller : calcul de )(siα

Initialisation: si s0 est l’état initial du codeur

00

00

0)(1)(

ssss

≠∀=α=α

∑−

=

ν

α

α=α′12

0')'(

)()(

ss

ss

i

ii

NB: pour éviter les problèmes de précision, peut être normalisé à chaque étape de calcul ( est un rapport)

)(siα)( idΛ

∑−

=′−

ν

′γ′α=α12

01 ),()()(

sssss iii (ν = mémoire du code)

Codes convolutifs algorithmes SISO : MAP

)0(iα

)1(iα

)2(1+iα

)3(1−iα

)1(1−iα

)0(1−iα

)2(1−iα

0

1

2

3

0

1

2

3

0ou 1 =+ii dd1ou 1 =+ii dd

1−i 1+ii

Exemple:(sans normalisation)

* ),()(),()()( 11 1221331 iiiii γα+γα=α −−

),()(),()()( 11 0110000 iiiii γα+γα=α −−*

),()(),()()( 111 2002112 +++ γα+γα=α iiiii*

Codes convolutifs algorithmes SISO : MAP

Page 40: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 40

∑−

=++

ν

′γβ=′β12

011 ),()()(

sssss iii

• Récursion retour : calcul de )(s′βi

kkkk ssss ≠∀=β=β 0)(,1)(

Si l’état final est inconnu :

ss ∀=β ν21)(k

Normalisation:

∑−

=′

ν

β

β=β′12

0)'(

)()(

ss

ss

i

ii

Initialisation : si sk est l’état final du codeur

Codes convolutifs algorithmes SISO : MAP

)1(1−βi

0

1

2

3

0

1

2

3

0ou 1 =+ii dd1ou 1 =+ii dd

1−i 1+ii

)0(iβ

)2(iβ

)0(1+βi

)1(1+βi

)2(1+βi

)3(1+βi

Exemple:(sans normalisation)

* ),()(),()()( 1111 1213232 ++++ γβ+γβ=β iiiii

),()(),()()( 1111 2020000 ++++ γβ+γβ=β iiiii*

),()(),()()(1 0102121 iiiii γβ+γβ=β −*

Codes convolutifs algorithmes SISO : MAP

Page 41: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 41

• Calcul des probabilités de branches ),( ss′γi

S’il n’y a pas de transition entre s' et s dans le treillis.

sinon

si di = j est le bit d’information et ci le symbole codé et modulé correspondant à la transition s' → s du treillis et ri est le symbole reçu, à l’instant i .

Pour une transmission sur canal gaussien :

−−= 2

2

2 2exp

21}{Pr

σπσii

ii

crcr

σ2 : variance du bruit sur le canal

Codes convolutifs algorithmes SISO : MAP

0),( =′γ ssi

}{Prj}{Pr),( iiii crd ==′γ ss

σ−−

σ−−

πσ=′γ 2

2

2

2

2 2)(exp

2)(exp

41),( iiii

iYyXxss

Ν. Β. Λ(di) étant un rapport, K peut être omis dans les expressions de αi(s) et βi(s).

211}{Pr0}{Pret ),( ),,( Si ====== iiiiiiii ddyxrYXc

• Calcul des probabilités de branches ),( ss′γi

Codes convolutifs algorithmes SISO : MAP

)1,1(expexp),(

)1,1(expexp),(

)1,1(expexp),(

)1,1(expexp),(

22

22

22

22

+=+=

σ−

σ−=′γ

−=+=

σ

σ−=′γ

+=−=

σ−

σ

=′γ

−=−=

σ

σ

=′γ

iiii

i

iiii

i

iiii

i

iiii

i

YXyxK

YXyxK

YXyxK

YXyxK

ss

ss

ss

ss

Page 42: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 42

Solution 1: Log-MAP

Le terme est pré-calculé et stocké dans une table)1ln( bae −−+

Multiplications => additions Les exponentielles dans les probas de branches s’éliminentAdditions => ?

L’algorithme MAP dans le domaine logarithmique (Log-MAP)

☺ Performance MAPConnaissance de σ requise

)1ln(),max()ln( baba ebaee −−++=+

Codes convolutifs algorithmes SISO : Log-MAP et Sub-MAP

Performance < MAP (qqes dixièmes de dB)☺ Estimation de σ inutile

Solution 2: Sub-MAP (Max-Log-MAP)

),max()ln( baee ba ≈+

⇒ Algorithme « Dual Viterbi »

L’algorithme MAP dans le domaine logarithmique (Sub-MAP)

Codes convolutifs algorithmes SISO : Sub-MAP

Page 43: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 43

• Reformulation de Λ(di)

∑∑∈′

−∈′

− β′γ′α−β′γ′α=Λ01 ),(

1),(

1 )(),()(ln)(),()(ln)(ii T

iiiT

iiiidssss

ssssssss

( ){ }

( ){ })(),()(lnmax

)(),()(lnmax)(

1),(

1),(

0

1

ssss

ssss

ss

ss

iiiT

iiiT

i

i

i

d

β′γ′α−

β′γ′α≈Λ

−∈′

−∈′

Métriques de nœuds et de branches :

)(ln)(

)(ln)(

2

2

ss

ss

iBi

iFi

M

M

βσ−=

ασ−=∆

∆Métrique de nœud aller (forward)

Métrique de nœud retour (backward)

),(ln),( 2 ssss ′γσ−=′∆

iim Métrique de branche

Codes convolutifs algorithmes SISO : Sub-MAP

L’algorithme Sub-MAP calcule :)(2

)(2

ii dd Λσ=Λ′∆

{ }

( )

+′+′−

+′+′≈Λ′

−∈′

−∈′

)(),()(min

)(),()(min21)(

1),(

1),(

1

0

ssss

ssss

ss

ss

Bii

Fi

T

Bii

Fi

Ti

MmM

MmMd

i

i

+±−′−

+±+′≈Λ′

−∈′

−∈′

})()({min

})()({min21)(

1),(

1),(

1

0

ss

ss

ss

ss

Biii

Fi

T

Biii

Fi

Ti

MyxM

MyxMd

i

i

Codes convolutifs algorithmes SISO : Sub-MAP

Page 44: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 44

0

1

2

3

0

1

2

3i-1 i

([

)(

)])(),()(),(),()(

),(),()(,)(),()(min

)(),()(),(),()(

),(),()(),(),()(min21)(

11

11

11

11

33332200

11220011

33222211

11330000

Bii

Fi

Bii

Fi

Bii

Fi

Bii

Fi

Bii

Fi

Bii

Fi

Bii

Fi

Bii

Fii

MmMMmM

MmMMmM

MmMMmM

MmMMmMd

++++

++++−

++++

++++=Λ′

−−

−−

−−

−−

Exemple:

Codes convolutifs algorithmes SISO : Sub-MAP

})({min)(

}),()({min)(

1120

1120

iiFi

Fi

iFi

Fi

yxMM

mMM

±±′≈

′+′≈

−−=′

−−=′

ν

ν

ss

ssss

s

s

L

L

Codes convolutifs algorithmes SISO : Sub-MAP

sont calculés récursivement :)(et )( ss Bi

Fi MM

})({min)(

}),()({min)(

111120

11120

+++−=

++−=

±±≈′

′+≈′

ν

ν

iiBi

Bi

iBi

Bi

yxMM

mMM

ss

ssss

s

s

L

L

Page 45: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 45

0

1

2

3

0

1

2

3

0ou 1 =+ii dd1ou 1 =+ii dd

1−i 1+ii

Exemple

* ( )),()(),,()(min)( 11 1221331 iFii

Fi

Fi mΜmΜΜ ++= −−

( )),()(),,()(min)( 11 0110000 iFii

Fi

Fi mΜmΜΜ ++= −−*

( )),()(),,()(min)( 111 2002112 +++ ++= iFii

Fi

Fi mΜmΜΜ*

)(1 2FiM +

)(0FiM

)(1FiM

)(1 3FiM −

)(1 1FiM −

)(1 0FiM −

)(1 2FiM −

Codes convolutifs algorithmes SISO : Sub-MAP

0

1

2

3

0

1

2

3

0ou 1 =+ii dd1ou 1 =+ii dd

1−i 1+ii

)(0BiM

)(2BiM

)(1 0BiM +

)(1 1BiΜ +

)(1 2BiM +

)(1 3BiM +

* ( )),()(),,()(min)( 1111 3231212 ++++ ++= iΒii

Βi

Βi mΜmΜΜ

( )),()(),,()(min)( 1111 2020000 ++++ ++= iΒii

Βi

Βi mΜmΜΜ*

( )),()(),,()(min)(1 2120101 iΒii

Βi

Βi mΜmΜΜ ++=−*

)(1 1BiM −

Codes convolutifs algorithmes SISO : Sub-MAP

Exemple

Page 46: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 46

• Obtention de l’information extrinsèque pour le décodage itératif :

peut s’écrire :)( idΛ′

iii Zxd +≈Λ′ )(

est l’information extrinsèque produite par le décodeuriZ

+±−′−

+±+′≈Λ′

−∈′

−∈′

})()({min

})()({min21)(

1),(

1),(

1

0

ss

ss

ss

ss

Biii

Fi

T

Biii

Fi

Ti

MyxM

MyxMd

i

i

Codes convolutifs algorithmes SISO : Sub-MAP

Codes convolutifs algorithmes SISO : Biblio[1] G. Battail, “Pondération des symboles décodés par l’algorithme de Viterbi”, Ann.

Télécomm., vol. 42, N°1-2, pp. 31-38, Jan. 1987.[2] J. Hagenauer and P. Hoeher, “A Viterbi algorithm with soft-decision outputs and its

applications”, in Proc. IEEE Globecom’89, Dallas, Texas, Nov. 1989, pp. 4711-4717.

[3] C. Berrou, P. Adde, E. angui, and S. Faudeil, “A low complexity soft-output Viterbi decoder architecture”, in Proc. IEEE Int’l Conf. on Comm., Geneva, Switzerland, 1993, pp.737-740.

[4] L.R. Bahl, J. Cocke, F. Jelinek, and J. Raviv, “Optimal decoding of linear codes for minimizing symbol error rate”, IEEE Trans. Inform. Theory, vol. IT-20, pp. 284-287, 1974.

[5] P. Robertson, E. Villebrun, and P. Hoeher, “ A comparison of optimal and sub-optimal MAP decoding algorithms operating in the log domain”, in Proc. IEEE Int’l Conf. on Comm., Seattle, WA, 1995, pp.1009-1013.

[6] A. J. Viterbi, “An intuitive justification and a simplified implementation of theMAP decoder for convolutional codes”, IEEE Journal on Selected Areas in Comm.,Vol. 16, N°2, Feb. 1998.

[7] B. Vucetic, J. Yuan, Turbo Codes, Principles and Applications, Kluwer Academic Publishers, 2000.

Page 47: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 47

Chapitre 4

Turbo codes

Plan

• Mots croisés• “turbo codes historique”• Pourquoi de si bons résultats ?• Différents schémas

– Turbo Codes en bloc – Turbo Codes convolutifs

Page 48: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 48

☺☺☺☺☺☺☺☺☺☺

ETRESVTNESUIVRENIDIIIAGEMOIITAGEDI54321

Mots croisés

HorizontalI. DommageII. LettreIII. RepasIV. MinentV. Enchâssement

Vertical1. Gras2. Envoyée3. Indisposer4. Intermédiaire5. Gâteau

GIRADVTNRSUIVRENIDIIIAMMAGIITAGEDI54321☺☺☺

Turbo Codes

Inventés* en 1990, les Turbo Codes est une mise en oeuvre de la déclaration de Claude Shannon (1953) :

A scheme of coding and decoding can be found allowing correction of all transmission errors, if the information rate

is inferior or equal to the channel capacity.

* première publication à ICC’93 – Genève - Suisses

Travaux précédents : Tanner, Gallager, Battail, Hagenauer & Hoegher, …

Page 49: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 49

Turbo CodesCodeurCodeurUn Turbo codeur est constitué d’au moins deux codeurs élémentaires de codes convolutifs systématiques (RSC) codes séparés par un entrelaceur

Concaténation parallèle de 2 codes RSC

Code 1

Code 2

Données

diy1i

y2i

Redondance

xi

π Rendement naturel :1/3

Turbo CodesCodeurCodeurUn Turbo codeur est constitué d’au moins deux codeurs élémentaires de codes convolutifs systématiques (RSC) codes séparés par un entrelaceur

Concaténation parallèle de 2 codes RSC(R=1/2)

Code 1

Code 2π

Données

di

y1i

y2i

Poinçonnage

Redondanceyi

xi

Page 50: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 50

Xi = (2xi-1) + ni (xi=di)Y1i = (2y1i-1) + n1iY2i = (2y2i-1) + n2i

Décodeur 1 Décodeur 2Xi

Y1i

Y2i

π-1π di^

Code 1

Code 2π

Données

diy1i

y2i

Redondance

xi

Turbo CodesDécodeur

Construit sur la base de décodeurs élémentaires à entrées et sorties pondérées (Soft Input Soft Output SISO)Processus itératif (effet turbo)

Décodeur 1 Décodeur 2(SISO) (SISO)

Xi

Y1i

Y2i

π-1π

Xi = (2xi-1) + ni (xi=di)Y1i = (2y1i-1) + n1iY2i = (2y2i-1) + n2i

di^

π-1

Page 51: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 51

Turbo CodesDécodeur

Construit sur la base de décodeurs élémentaires à entrées et sorties pondérées (Soft Input Soft Output SISO)Processus itératif (effet turbo)

Décodeur 1 Décodeur 2

Z1i : information extrinsèque

(SISO) (SISO)

première itération

Xi

Y1i

Y2i

π-1π Z1i

Xi = (2di-1) + niY1i = (2xi-1) + n1iY2i = (2yi-1) + n2i

Turbo CodesDécodeur

Décodeur 1 Décodeur 2(SISO) (SISO)

Itération p

Xi

Y1i

Y2i

π-1π Zp i

Zp i : information extrinsèque associée à la donnée diZp i et Xi sont altérées par des bruits non corrélés (effet de la diversité)

Zp-1 i

π-1 di^

Page 52: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 52

xi

Code 1

Code 2

Données

diy1,i

y2,iπ

Décodeur 1

Décodeur 2

Xi

Y1,i

Y2,i

π -1π

π

Comment faire pour que les deux décodeurs travaillent conjointement, c’est à dire que le décodeur 1 profite de Y2et que le décodeur 2 profite de Y1 ?

« Message passing »« turbo »

Turbo décodage Information extrinsèque

X1

X2

• Critère de décodage : les deux décodeurs doivent converger vers la même solution (décision et probabilité associée)

X

Y1

Y2

π

O1 =X1+Z1

O2 =X2+Z2

Z1

Z2

π-1

Décodeur 1(SISO)

Décodeur 2(SISO)

Page 53: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 53

O2 =(X2+Z1)+Z'2

O1 =(X1+Z2)+Z'1

X1+Z2

X2+Z1

Turbo décodage Information extrinsèque

X

Y1

Y2

Décodeur 1(SISO)

Décodeur 2(SISO)π

Z1

Z2

π-1

• Critère de décodage : les deux décodeurs doivent converger vers la même solution (décision et probabilité associée)

Turbo décodage Le principe turbo

Décodeur 2G2

Décodeur 1G1 SNRZ1out

SNRZ2inSNRZ2out

SNRZ1in

Canal Eb/N0

Itérations et convergence d’un turbo décodeur

L’information Extrinsèque est approximée à une variableGaussienne de moyenne λ et de variance σλ

2

22 / λ∆

σλ=SNRChaque décodeur est considéré au travers d’une fonction de transfert non-linéaire de rapport signal à bruit (SNR)SNRZ1out=G1 (SNRZ1in , Eb/N0)SNRZ2out=G2 (SNRZ2in , Eb/N0)

Page 54: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 54

Turbo décodage Le principe turbo

Itérations et convergence d’un turbo décodeur

G1

G2-1

SNRin

SNRout

1ère itération2ème itération

3ème itérationtunnel

dépend de Eb/N0

D. Divsalar, S. Dolinar, F. Pollara, "Low Complexity Turbo-like Codes", Proc. 2nd International Symposium on Turbo Codes and Related Topics, Brest, France sept. 2000, pp. 73-80

Turbo codeur Turbo décodeur :une structure à contre-réaction

sortiedécodéeY2

Y1

LLR (d)

LLR (d)1

2

X1

X2

Z1

Z2

X

décodeurSISO8 états

Π

Π

Π−1

x

y1

y2

permutation

d(données)

C1

Π C2 décodeurSISO8 états

x β x β

Adaptée pour un circuit analogique, mais pas pour un circuit numérique !!⇒ Processus itératif

Page 55: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 55

Turbo codeur Turbo décodeur

sortiedécodéeY2

Y1

LLR (d)

LLR (d)1

2

X1

X2

Z1

Z2

X

décodeurSISO8 états

Π

Π

Π−1

x

y1

y2

permutation

d(données)

C1

Π C2 décodeurSISO8 états

x β x β

Information extrinsèque

Décodeurs à entrées et sortiespondérées

Réglage dugain de boucle

Pourquoi de si bons résultats ?

Page 56: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 56

Turbo codes :similaires à des RSC de grande longueur

Il peut être comparé à un code convolutif ayant une grande longueur de contrainte,qu’il est possible de décoder.

xi

Code 1

Code 2

Données

diy1i

y2iπ

Décodeur 1

Décodeur 2

Xi

Y1i

Y2i

π -1π

1 2 ν

d X

Y

Générateurpseudoaléatoire

R = 1/2 R = 2/3 R = 3/4 R = 4/5

R = 5/6 R = 6/7 R = 7/8

-0.2 0.2 0.6

0.03

0.07

0.06

0.04

0.05

0.020.8 1.2 1.6

0.021.6 2.0 2.4

0.03

0.07

0.06

0.04

0.05

0.02

0.06

0.05

0.03

0.04

0.011.2 1.6 2.0

= 2 = 4

= 6

0.02

0.06

0.05

0.03

0.04

0.01

0.02

0.06

0.05

0.03

0.04

0.01

0.01

0.05

0.04

0.02

0.03

0.001.6 2.0 2.4 1.8 2.2 2.6 2.2 2.6 3.0

= 8

Limite de Shannon(canal gaussien entrée binaire)

ν ν

ν ν

0.05

0.09

0.08

0.06

0.07

0.04

TEBE /Nb 0

Plus le registreest grand, meilleur est le code convolutif

Page 57: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 57

Code 1

Code 2π

Données

diY1,i

Y2,i

xi

Mémoire ν

k bits

Code simple

ν ≤ mémoire ≤ k +2ν

À prouver !

Turbo codes :similaires à des RSC de grande longueur

Pourquoi de si bons résultats ?Lorsqu’un paquet d’erreurs affecte “code 1”, les erreurs sont disséminées pour le “code 2” et vice versa.

xi

Code 1

Code 2

Données

diy1i

y2iπ

Décodeur 1

Décodeur 2

Xi

Y1i

Y2i

π -1π

Page 58: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 58

Turbo codes :une approche du codage aléatoire

Concaténation parallèle de N codes

CRSC:

Codage quasi-aléatoire

(pour N ≥ 4)

Et c’est décodable !!Tirés de manière aléatoire

Heureusement, N = 2 est suffisant:

turbo codes

permutationk donnéesbinaires

Mot

de

code

Partiesystématique

ΠCRSC

permutationΠ

CRSC

permutationΠ

CRSC

N

2

1(identity)

YN,i

Y1,i

Y2,i

Treilliscirculaire

0k-1

Y1,0

Y1,k/N-1

Y2,0

YN,0

YN,k/N-1

Y2,k/N-10k-1

0k-1

Treilliscirculaire

Treilliscirculaire

Xi = (2xi-1) + ni (xi = di)Y1,i = (2y1i-1) + n1iY2,i = (2y2i-1) + n2i

Code 1

Code 2π

Data

diy1,i

y2,i

xi

Le rôle fondamental de π :minimiser la probabilité que les 2 décodeurs défaillent

(un problème très complexe combinant algèbre, géométrie, ...)

Decodeur 1

Decodeur 2

Xi

Y1,i

Y2,i

π

Page 59: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 59

Différents schémas de turbo codes

Turbo code en blocCode 1(k , n) πDonnées

Code 2(k , n)

M1 C1 M2 C2

concaténation série de deux codes en bloc

Mot de

code

k colonnes

n colonnes

k lignesn lignes

Mot de code 2

Mot de code 1

Redondance 1

Redondance 2

Page 60: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 60

Turbo code en blocCode 1(k , n) πDonnées

Code 2(k , n)

M1 C1 M2 C2

Propriétés (sans poinçonnage) :• n = n1.n2• k = k1.k2• R = R1.R2• dmin = dmin1.dmin2

Turbo codes convolutifs auto-concaténés

Code 1

Code 2

Données

diy1i

y2iπ

xi

Code 1Données

diyi

xi

π

Page 61: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 61

Principe de décodage

1

Données Données entrelacées

k

Information extrinsèque (z)

Code 1

Code 2

données

diy1i

y2iπ

xi

Code 1données

diyi

π

xi

Quelques schémas Turbo codes convolutifs

Code 1

Code 2

données

ai,bi y1i

y2iπ

Code 1

Code 2

données

diy1i

y2iπ

xi

classique Auto-concaténé

duo-binaire série Et plein d’autres ...

Page 62: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 62

Chapitre 5

La permutation

Permutation(Permutation ≡ entrelacement)

C1

C2

Π

données A

Y1

Y2

Le comportement à faibleTEB (<10-5) est fonctionde la façon dont Π estconçu

Le rôle fondamental de la permutation : si une séquence directe est RTZ, il fautminimiser la probabilité que la séquence permutée soit aussi RTZ (et vice-versa).

Page 63: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 63

Illustration avec le code suivant :

Séquences RTZ

00

01

10

11

0011 11

01

10

00

di =0 xi yi

di =1 xi yi

D Ddi

yi

xi

10

01

Séquences RTZ00

11

Distance de Hamming =5

00

11

10

01

00

11 11

011010

00

01

00

11 11

011010

00

01

00

01

10

11

00

2+

11

2+

11

0+

00

0

00

1+

01

00

11 11

011010

00

01

0+

00

Page 64: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 64

Séquences RTZ00

11

Distance de Hamming =6

00

11

10

01

00

11 11

011010

00

01

00

11 11

011010

00

01

00

01

10

11

00

2+

11

1+

01

0

00

1+

01

00

11 11

011010

00

01

0+

00

2+

11

Séquences RTZ00

11

Distance de Hamming

00

11

10

01

00

11 11

011010

00

01

00

11 11

011010

00

01

00

01

10

11

00

2+

11

1+

01

0

00 00

11 11

011010

00

01

0+

00

0+

00

1+

01

Page 65: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 65

Séquences RTZ

D Ddi

yi

xidi =0 xi yi

di =1 xi yi

00

01

10

1100 11 10

0111

0001

10

Permutation Régulière

0010110010...0110001...................................0100100100...10010100011110100...10110110101000110...0101001

Écriture en

ligne

Lecture encolonne

M colonnes

N lignes

Condition : k = M.N

Ordre naturel :adresse k-1

Ordre naturel :adresse 0

Page 66: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 66

Permutation Régulière

0k-1Adresse naturelle : i0 ≤ i ≤ k-1

Adresse permutée : j0 ≤ j ≤ k-1

j = P.i mod. k

(P et k premiers entre eux)

Permutation Régulière

0100000010...0000000...................................0000000000...00000000000000000...00000000000000000...0000000

M colonnes

N lignespériode : 7

période : 7

La permutation régulière est adaptée aux poids 2

k → ∞ ⇒ d(w=2) → ∞

Page 67: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 67

D D

diyi

xi di =0 xi yi

di =1 xi yi

000

D

001 101

100111

010

011

110

0010

11 11

10

1111

00

0100

00

01

01

01

11

10

Permutation Régulière

M colonnes

N lignespériode : 7

période : 7

La permutation régulière est adaptée aux poids 3

k → ∞ ⇒ d(w=3) → ∞

0110100000...0000000...................................0000000000...00000000000000000...00000000000000000...0000000

Page 68: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 68

Permutation Régulière

0100000010...00000000000000000...00000000000000000...00000000000000000...00000000000000000...00000000000000000...00000000000000000...00000000100000010...0000000.....................................

M colonnes

N lignespériode : 7

période : 7

La permutation régulière n’est pas adaptée aux poids 4

k → ∞ ⇒ d(w=4) est limité

Permutation Régulière

M colonnes

N lignespériode : 7

période : 7

La permutation régulière n’est pas adaptée pour différents poids

0110100000...00000000110100000...00000000000000000...00000000110100000...00000000000000000...00000000000000000...00000000000000000...00000000000000000...0000000.....................................

Page 69: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 69

Il faut donc introduire du désordre, mais pas de n’importe quelle manière !!

Une bonne permutation doit assurer :(1) Un maximum de dispersion des données(2) Un maximum de désordre dans la séquence permutée

(ces deux conditions sont contradictoires)

Permutation Aléatoire

Page 70: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 70

Permutation AléatoirePermutation aléatoire selon S. Benedetto et G. Montorsi

Tous les entrelaceurs sont considérés, de manière statistique,en y incluant les pires

Quels sont les pires ?

0100000010...0000000...................................0000000000...00000000000000000...00000000000000000...0000000ce couple a une

probabilité de 1/kde rester inchangéaprès permutation

Permutation Aléatoire Permutation aléatoire selon S. Benedetto et G. Montorsi

0100000010...0000000...................................0000000000...00000000000000000...00000000000000000...0000000

Cette approche conduit naturellementà une borne qui a l’allure suivante :

0

min...1N

dERerfck

P be

Donnant une évaluation très pessimiste !

Page 71: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 71

Permutation pseudo-aléatoire (= désordre contrôlé)

Chacun a ses recettes

CCSDS 101.0-B-4: Telemetry Channel Coding.Blue Book. Issue 4. May 1999.

voir http://ftp.ccsds.org/all_books.html#telemetry

Par exemple, l’entrelacement du Consultative Committee forSpace Data Systems (CCSDS)

Permutation CCSDS

;67;61;59;53;47;43;37;31

)14(2)(8

mod 21

1 8 mod 4 mod 119

821

14

2 mod 1

8765

4321========

−++=Π

+=

+=+=

−=

=

−=

pppppppp

mcts

kmjpc

tqit

iks-j

ks- i

sm

q

0110101000...0100000110010011101001110110101...0010011000100011010011010001100...1000100111011001011101100101000...1100110000101010010110111101000...0100001110011110101010100010101...0010011000101011010011010001100...1000100011011001111101100101000...110011000000101001001.....................................0100101011...1100110100110010010101110101010...0101100110010110101100100010101...001001100010101101001

non-uniformité de degré 8

Page 72: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 72

Permutation

En conclusion :

•Pas de permutation idéale pour le moment (existe-t-elle ?)•Il n’est pas nécessaire de l’avoir

Page 73: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 73

Chapitre 6

turbo codes duo-binaires

Turbo codes duo-binaires

C1

C2

Π

données (bits)X

Y1

Y2

C1

C2

Π

données (couples) A

Y1

Y2

B

R = 1/3 (1/2 //1/2) R = 1/2 (2/3 //2/3)

binaire duo-binaire

Page 74: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 74

5

5

5

5

5

5

5

5

10-1

10-3

10-4

10-6

10-7

10-8

20 1 3 4 5 6 7 8 9 10 11 12

Eb/N0 (dB)

TEB

non codé

mauvaise convergence, gain asymptotique élevé

Bonne convergence, faible gain asymptotique

10-2

10-5

Limite théorique(R=1/2, 188 octets)

Rappel MDP4, canal gaussien, taux d’erreurs cible : 10-8

Ga = 10 log (R.dmin)

dmin > 25

∫∞

=−=

xt

b

dttxerfc

avecNEerfc

)exp(2)(

)(21

2

0

π

Contribution des codes duo-binaires sur la convergence

kk / 2

k / 2k

binaire

duo-binaire :Diminue la corrélationDurant le décodage

C1

C2

Π

C1

C2

Π

Turbo codes duo-binaires

cheminerroné

motifs deverrouillage

k

k

Page 75: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 75

Turbo codes duo-binaires Contribution des codes duo-binaires sur les distances minimales

C1

C2

Π

données (couple) A

Y1

Y2

BC1

C2

Π

données (bit)

Y1

Y2

Π : permutation inter-symbole Π : permutation inter-symbole + intra-symbole

Le rôle fondamental de la permutation : si une séquence directe est RTZ,il faut minimiser la probabilité que la séquence permutée soit aussi RTZ(et vice-versa).

Rappel :

X

Turbo codes duo-binaires Contribution des codes duo-binaires sur les distances minimales

000

001

010

011

100

101

110

111

000

001

010

011

100

101

110

111

Treillis binaire

Treillis Duo-binaire(partiel)

X AB

(a) (b)

AB

Y

X

Y

100000010 00 00 00 00 00 010000001

2010 00 00 00 00 00 0201

1300000000000013

1

2

3

0

00

0

k

kk / 2

k / 2

00 : 001 : 110 : 211 : 3

Périodicités du Code duo-binaire

exemples demotifs à faibles distances avec unepermutationrégulière

Page 76: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 76

Grâce à cette technique, les distances minimales sont généralementplus grandes que celles des concaténations séries (codes produits) !!!!

Turbo codes duo-binaires Contribution des codes duo-binaires sur les distances minimales

Permutation intra-symbole

2 0 10 00 00 00 00 00 02 0 1

1 30 00 00 00 00 00 01 3

3 0 0 0 0 0 0 30 00 00 02 0 0 0 0 0 0 2

3 0 0 0 0 0 0 30 00 00 00 00 00 03 0 0 0 0 0 0 3

1 30 00 00 00 00 00 00 00 00 00 00 00 00 01 3

Ces motifs ne sont pluspossibles si les couples sontInversés périodiquement

Motifs d’erreurs possiblesavec une grande distance

(A,B) devient (B,A)avant le codage vertical,une fois de temps en temps

(sans introduction de désordre aléatoire !)

• Latence divisée par 2 (codage et décodage)• Débit de traitement des données doublé (parallélisme intrisèque)• Plus faible dégradation MAP → SUB-MAP• Meilleur mapping pour constellations à grand nombre d’états

Turbo codes duo-binaires Autres avantages des codes duo-binaires

Page 77: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 77

Turbo codes duo-binairesStandard DBV-RCS (+RCT)

permutation(k/2)

k/2 couplesde données

MoT

de

code

partie systématique

redondance

1

2poinçon-nage

Y2 Y1

A

B

coupledécodé

, Y2Y1

LLR

LLR 1

2

Z1

Z2

A, B

SUB-MAP8 états4 chemins

SUB-MAP8 états4 chemins

Π

Π

Π

Π−1

1 1

, Y2Y12 2

s1 s3s2AB

Y1

partie systématique

redondance

Y2

Complexité≈ 20.000 portespar bit.itération@ horloge système+ mémoire

Turbo codes duo-binaires Standard DVB-RCS (+RCT)

Niveau 1 (intra-couple)if j=0 mod 2 (A,B)=(B,A) [inversion du couple]

Niveau 2 (inter-couple)if j=0 mod 4 P=0if j=1 mod 4 P=P1+ N/2if j=2 mod 4 P=P2if j=3 mod 4 P=P3 + N/2

i=π(j)=P0.j + P + 1 mod N

P0, P1, P2 et P3 sont des entiers, pour chaque N (nombre de couples).

Permutation générique Π

Page 78: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 78

Taille des blocs : 12, 16, 53, 55, 57, 106, 107, 108, 110, 188, 212, 214, 216 octets

Rendements : 1/3, 1/2, 2/3, 3/4, 4/5, 6/7

Turbo codes duo-binaires Standard DVB-RCS (+RCT)

Turbo codes duo-binaires Standard DVB-RCS (+RCT)

Exemple de performance : TC1000 (TurboConcept)(Mesures, 53 octets, SUB-MAP, 4 bits de quantification, 8 itérations)

1e-09

1e-08

1e-07

1e-06

1e-05

0.0001

0.001

0.01

0.1

1

0 1 2 3 4 5 6 7 8 9 10

Taux

d’e

rreur

s pa

quet

s

Eb/N0

Non codé53 octets 1/2 8 it.53 octets 2/3 8 it.53 octets 3/4 8 it.53 octets 4/5 8 it.53 octets 6/7 8 it.

Page 79: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 79

Turbo codes duo-binaires Standard DVB-RCS (+RCT)

Exemple de performances : TC1000 (TurboConcept)(Mesures, 188 octets, SUB-MAP, 4 bits de quantification, 8 itérations)

1e-09

1e-08

1e-07

1e-06

1e-05

0.0001

0.001

0.01

0.1

1

0 1 2 3 4 5 6 7 8 9 10

Taux

d’e

rreur

s pa

quet

s

Eb/N0

Non codé188 octets 1/3 8 it.188 octets 2/5 8 it.188 octets 1/2 8 it.188 octets 2/3 8 it.188 octets 3/4 8 it.188 octets 4/5 8 it.188 octets 6/7 8 it.

Duo-binaire turbo codesStandard DVB-RCS (+RCT)

Exemple de performances : mini-slots(simulation, SUB-MAP, 4 bits de quantification, 6 itérations)

Eb/N0 (dB)

Taux d’erreurs paquets

5

5

5

5

5

5

5

5

10-8

10-3

10-4

10-5

10-6

10-7

10-1

10-2

3 4 5 6

12 oct.

16 oct.

12 oct.14 oct.16 oct.

14 oct.

4 oct.

R = 1/2R = 1/2

R = 1/3

R = 2/3

7 8

12 oct.14 oct.16 oct.

4 oct.

R = 4/5

R = 4/5

12 oct.

16 oct.14 oct.

Page 80: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 80

Chapitre 7

Conclusions et perspectives

1e-09

1e-08

1e-07

1e-06

1e-05

0.0001

0.001

0.01

0.1

1

0 1 2 3 4 5 6 7 8 9 10

Taux

d’e

rreur

s pa

quet

s

Eb/N0

Non codé188 octets 1/3 8 it.188 octets 2/5 8 it.188 octets 1/2 8 it.188 octets 2/3 8 it.188 octets 3/4 8 it.188 octets 4/5 8 it.188 octets 6/7 8 it.

Conclusions et perspectives Codage

Limites théoriques

0.3 dB (turbo + it.) + 0.3 dB (SUB-MAP) + 0.15 dB (quantification) + 0.05 dB (matériel)+ 0.4 dB (?)

perte @ PER = 10-4

≈ 1.2 dB

Page 81: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 81

1e-09

1e-08

1e-07

1e-06

1e-05

0.0001

0.001

0.01

0.1

1

0 1 2 3 4 5 6 7 8 9 10

Taux

d’e

rreur

s pa

quet

s

Eb/N0

Non codé188 octets 1/3 8 it.188 octets 2/5 8 it.188 octets 1/2 8 it.188 octets 2/3 8 it.188 octets 3/4 8 it.188 octets 4/5 8 it.188 octets 6/7 8 it.

Conclusions et perspectives Codage Génération suivante (2002)1 dB gain @ TEP = 10-7

pour une complexité double

Standards actuels

Application turbo code terminaison polynômes rendements

CCSDS binaire,16 états

tail bits 23, 33, 25, 37 1/6, 1/4, 1/3, 1/2

IMT-2000 binaire,8 états

tail bits 15, 13, 17 1/4, 1/3, 1/2

DVB-RCS duo-binaire,8 états

circulaire 15, 13 de 1/3 à 6/7

DVB-RCT duo-binaire,8 états

circulaire 15, 13 1/2, 3/4

Inmarsat (mini M)

binaire,16 états

no 23, 35 1/2

Skyplex duo-binaire,8 états

circulaire 15, 13 4/5, 6/7

Page 82: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 82

Conclusions et perspectives turbo-X• Turbo (dé)modulation• Turbo égalisation• Turbo détection (CDMA)• Turbo synchronisation• Turbo (dé)codage de source

processeurprobabiliste

informationintrinsèquelocale

informationextrinsèque1

4

3

2

modèle général d’un turbo processeur

informationintrinsèquepartagée

Applications

1990 1995 2000

inventionpatents

publication

CCSDS

M4

UMTSCDMA2000

DVB-RCSDVB-RCT

HiperAccess

Disques durs ?CD-ROM ?

DVB-S ?DSL ?

turbo-égalisation,turbo-synchro,turbo-crypto,...

Page 83: Turbo codes (convolutifs) Plan

Timisoara 18-20 mars 2003

ENST Bretagne 83

Information générale à propos des Turbo codes

- C. Heegard, S. B. Wicker, Turbo Coding, Kluwer Academic Publishers, 1999- Branka Vucetic, Jinhong Yuan, Turbo Codes, Principles and Applications, Kluwer Academic Publishers, 2000- C. Schlegel, Trellis coding, IEEE Press, 1997- B.J. Frey, Graphical Models for Machine Learning and Digital Communication, MIT Press, 1998- R. Johannesson , K. Sh. Zignagirov, Fundamentals of Convolutional Coding, IEEE Press, 1999- Hanzo, Lajos, Adaptative wireless transceivers, John Wiley & sons, 2002 - Hanzo, Lajos, Turbo coding, turbo equalisation and space-time coding for transmission over fading channels, John Wiley & sons, 2002

- sites WEB : http://www-turbo.enst-bretagne.fr/2emesymposium/presenta/turbosit.htmest un bon point de départ

- base de données IEEE Xplore : mot clé : turbo, 1974 réponses le 13 mars, 2003