Représentations algébriques des codes convolutifs et desturbocodes pour le décodage par Propagation de

Croyance

Rodrigue Imad

26 octobre 2006

Encadrants : Charly PoulliatDavid Declercq

Laboratoire d’accueil : ETIS - UMR 8051

Introduction

Décodeur MAP : décodeur à sortie souple pour les codes convolutifset les turbocodes

Décodeur BP pour les codes en bloc linéaires définis par une matricede parité creuse

Matrice de parité des codes convolutifs et des turbocodes calculée

−→ Décodage des codes convolutifs et turbocodes par le BP

Rodrigue Imad () Séminaire TAMCIC 26 octobre 2006 2 / 31

Plan

1 Représentations Algébriques des codes convolutifs

2 Décodage des codes convolutifs

3 Turbocodes : Représentation algébrique et décodage associé

4 Conclusion et perspectives

Rodrigue Imad () Séminaire TAMCIC 26 octobre 2006 3 / 31

Plan

1 Représentations Algébriques des codes convolutifs

2 Décodage des codes convolutifs

3 Turbocodes : Représentation algébrique et décodage associé

4 Conclusion et perspectives

Rodrigue Imad () Séminaire TAMCIC 26 octobre 2006 4 / 31

Introduction

Principe et définitions :

codage de K bits d’information en N bits à l’aide d’un registre àdécalage

Rendement : R = K/NLongueur de contrainte : ν = m + 1Polynômes générateurs

Représentation :

Diagramme d’étatsDiagramme en treillisDiagramme en arbre

Rodrigue Imad () Séminaire TAMCIC 26 octobre 2006 5 / 31

Matrice génératrice du code convolutif

Entrées et sorties du codeur sous forme polynômiale

u(D) = · · ·+ u−1D−1 + u0 + u1D + u2D2 + · · ·v(D) = · · ·+ v−1D−1 + v0 + v1D + v2D2 + · · ·

Fonction de transfert pour un codeur à une entrée et une sortie :

��������

����

��������

����

����

�� ���� ���� ������������u w w w

f f

q q

v

j

j

fm−1 m

f

21

0 1

j−2j−1 j−m

qm

v(D) = u(D)f (D)/q(D) = u(D)f0 + f1D + · · ·+ fmDm

1 + q1D + · · ·+ qmDm= u(D)g(D)

Rodrigue Imad () Séminaire TAMCIC 26 octobre 2006 6 / 31

Matrice génératrice du code convolutif

En généralisant à un codeur de rendement K/N, ayant K entrées etN sorties

v(D) = u(D)G (D)

v(1)

v(2)

u

Exemples :code (1,5/7) systématique, récursif

G(D) =

„1 1+D

2

1+D+D2

«

v(1)

v(2)

u code (15,17)G(D) =

“1 + D + D3 1 + D + D2 + D3

”

Rodrigue Imad () Séminaire TAMCIC 26 octobre 2006 7 / 31

Forme de Smith de la matrice génératrice

G (D) = A(D)Γ(D)B(D)

G (D) −→ Γ(D) :Permutation de deux lignes (ou colonnes)Addition des éléments d’une ligne (ou colonne) multipliés par unpolynôme p(D), aux éléments d’une autre ligne (ou colonne)

Γ(D) =

γ1(D)γ2(D)

. . .

γr (D)0

. . .

0 . . . 0

Rodrigue Imad () Séminaire TAMCIC 26 octobre 2006 8 / 31

Matrice de Parité d’un code convolutif

B(D) : (produit des matrices post-multiplicatrices) inversible

HT (D) = dernières (N − K ) colonnes de B−1(D)HT (D) = HT0 + H

T1 D + · · ·+ HTms D

ms

où HTi , 0 ≤ i ≤ ms , est une matrice de dimensions N × (N − K )

=⇒ HT =

HT0 H

T1 . . . H

Tms

HT0 HT1 . . . H

Tms

. . .. . .

. . .

Autre représentation de la matrice de parité

bits non altérnés : H = [H2 H1]

Rodrigue Imad () Séminaire TAMCIC 26 octobre 2006 9 / 31

Matrice de Parité d’un code convolutif

Exemple : code (15,17)

G(D) =“1 + D + D3 1 + D + D2 + D3

”⇒ HT (D) =

„1 + D + D2 + D3

1 + D + D3

«

1re représentation :

H =

0BBBBBBBBBBB@

1 11 1 1 11 0 1 1 1 11 1 1 0 1 1 1 1

1 1 1 0 1 11 1 1 0

1 1

. . .. . .

1CCCCCCCCCCCA

2e représentation : H = [H2 H1] où

H2 =

0BBBBBBBBB@

11 11 1 11 1 1

1 11

. . .

1CCCCCCCCCAet H1 =

0BBBBBBBBB@

11 10 1 11 0 1

1 01

. . .

1CCCCCCCCCA

Rodrigue Imad () Séminaire TAMCIC 26 octobre 2006 10 / 31

Plan

1 Représentations Algébriques des codes convolutifs

2 Décodage des codes convolutifs

3 Turbocodes : Représentation algébrique et décodage associé

4 Conclusion et perspectives

Rodrigue Imad () Séminaire TAMCIC 26 octobre 2006 11 / 31

Algorithmes de décodage

Algorithme de Viterbi

Recherche de la séquence des blocs d’information la plus vraisemblable

Algorithme BCJR

A chaque instant, symbole d’information le plus probable→ Minimisation de la probabilité d’erreur sur les symboles

Critère MAP :d̂k = arg max

dkp(d̂k/y)

Algorithme simplifié : Max-Log-MAP

Rodrigue Imad () Séminaire TAMCIC 26 octobre 2006 12 / 31

Décodage par Propagation de Croyance (BP)

Matrice de parité des codes convolutifs déterminée→ Décodage par BP

Algoritme BP classique

Propagation des messages tout au long du graphe factoriel associé à Hitératif :

noeud de variable

noeud de parité

v

u

Mise à jour des noeuds de variableMise à jour des noeuds de parité→ Probabilité a posteriori de chaque bit

Graphe avec cycles→ Dégradation des performances du BP classique

Rodrigue Imad () Séminaire TAMCIC 26 octobre 2006 13 / 31

BP sur les groupes 1

Représentation des mots de code dans un groupe G = Zp2Nouvelle forme de l’équation de parité :∑

i

hi (vi ) ≡ 0

Bit Clustering → Résolution conjointe de p équations de paritéRéduction du nombre de cycles → Amélioration des performances

1A. GOUPIL, M. COLAS, G. GELLE, D. DECLERCQ, ’FFT-based BP Decoding ofGeneral LDPC Codes over Abelian Groups’, à parâıtre dans IEEE Trans. Comm.

Rodrigue Imad () Séminaire TAMCIC 26 octobre 2006 14 / 31

Résultats et comparaison

Code convolutif de rendement 1/2 : pmin =ν−1R = 2(ν − 1)

Code (1,5/7) systématique récursif

0BBBBBBBBBBBBBBBBB@

1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 01 1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 1 1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 1 1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 1 1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 1 1 0 1 1 1 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 1 1 0 1 1 1 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 1 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 1 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 1 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 1

1CCCCCCCCCCCCCCCCCA

Rodrigue Imad () Séminaire TAMCIC 26 octobre 2006 15 / 31

Résultats et comparaison

Blocs de 432 bits d’information

1 2 3 4 5 6 7 810

−4

10−3

10−2

10−1

100

Eb/No(dB)

Fra

me

Err

or R

ate

BCJRBP sur Z

22

BP sur Z24

BP sur Z29

BP sur Z22, bits non alter.

BP sur Z24, bits non alter.

Rodrigue Imad () Séminaire TAMCIC 26 octobre 2006 16 / 31

Résultats et comparaison

Code (1,23/35) : HT (D) =„

1 + D3 + D4

1 + D + D2 + D4

«Graphe sans cycle :pmin = 8

1 2 3 4 5 6 7 810

−4

10−3

10−2

10−1

100

Eb/No(dB)

Fra

me

Err

or R

ate

BCJRBP sur Z

22

BP sur Z24

BP sur Z28

BP sur Z29

Rodrigue Imad () Séminaire TAMCIC 26 octobre 2006 17 / 31

Résultats et comparaison

Code (561,753) : HT (D) =„

1 + D + D2 + D3 + D5 + D7 + D8

1 + D2 + D3 + D4 + D8

«Graphe sans cycle :pmin = 16

1 2 3 4 5 6 7 810

−4

10−3

10−2

10−1

100

Eb/No(dB)

Fra

me

Err

or R

ate

BCJRBP sur Z

22

BP sur Z24

BP sur Z29

BP sur Z22, bits non alter.

BP sur Z24, bits non alter.

Rodrigue Imad () Séminaire TAMCIC 26 octobre 2006 18 / 31

Résultats et comparaison

Code convolutif duo-binaire :

��

��

��

��

��

��

����������di,1

i,2d

yi

G (D) =

(1 0 1+D

2+D3

1+D+D3

0 1 1+D+D2+D3

1+D+D3

)

HT (D) =

1 + D2 + D31 + D + D2 + D31 + D + D3

H =

0BBBBBBBBBBBBBBBBB@

1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 01 1 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 01 1 1 1 1 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 00 0 0 1 1 1 1 1 0 0 1 1 1 1 1 0 0 0 0 0 00 0 0 0 0 0 1 1 1 1 1 0 0 1 1 1 1 1 0 0 00 0 0 0 0 1 0 0 0 1 1 1 1 1 0 0 1 1 1 1 10 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 1 10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1

. . .. . .

1CCCCCCCCCCCCCCCCCA

Rodrigue Imad () Séminaire TAMCIC 26 octobre 2006 19 / 31

Résultats et comparaison

1 2 3 4 5 6 710

−4

10−3

10−2

10−1

100

Eb/No(dB)

Fra

me

Err

or R

ate

BCJRBP sur Z

29

BP sur Z29, bits non alter.

Rodrigue Imad () Séminaire TAMCIC 26 octobre 2006 20 / 31

Plan

1 Représentations Algébriques des codes convolutifs

2 Décodage des codes convolutifs

3 Turbocodes : Représentation algébrique et décodage associé

4 Conclusion et perspectives

Rodrigue Imad () Séminaire TAMCIC 26 octobre 2006 21 / 31

Introduction aux turbocodes

��������

��������

��������

��������

code RSC C

code RSC C

redondance

uniforme

entrelaceur

non

X k

Y1k

Y2k

dn

sortie systématiquedonnée dk

1

2

Codage

Concaténation de deux codeurs RSC

Décodage : MAP itératif

Echange d’information extrinsèque

Turbocodes non binaires

Meilleure convergence du processus itératif → Meilleures performances

Rodrigue Imad () Séminaire TAMCIC 26 octobre 2006 22 / 31

Matrice de parité des turbocodes

Matrice de parité des codes élémentaires :

Hconv = [H2 H1]

mot de code :[u v v ′]u :entrée du turbocodeurv , v ′ :sorties des deux codeurs RSC

Matrice de parité du turbocode :

H =

[H2 H1 0

H2ΠT 0 H1

]ΠT :transposée de la matrice de permutation.

Dégradation possible des performances du BP

Rodrigue Imad () Séminaire TAMCIC 26 octobre 2006 23 / 31

Résultats et comparaison

Turbocode binaire de polynômes générateurs (1,23/35)

H2 =

0BBBBBBBBBBBBB@

10 10 0 11 0 0 11 1 0 0

1 1 01 1

1

. . .

1CCCCCCCCCCCCCAet H1 =

0BBBBBBBBBBBBB@

11 11 1 10 1 1 11 0 1 1

1 0 11 0

1

. . .

1CCCCCCCCCCCCCA

Rendement en abscence de poinçonnage : R = 1/3K bits d’information → dimensions de H :2K × 3K

H2 H1

H=

H H0π2 1T

K

K

3K

K KK

0

Permutation quasi-régulière :i = π(j) = (P.j + Q(j) + 1) mod K

Rodrigue Imad () Séminaire TAMCIC 26 octobre 2006 24 / 31

Résultats et comparaison

FER pour des blocs de 432 bits d’information

0 0.5 1 1.5 2 2.5 3 3.5 410

−6

10−5

10−4

10−3

10−2

10−1

100

Eb/No(dB)

Fra

me

Err

or R

ate

BCJR (3 iter.)BP sur Z

24

Rodrigue Imad () Séminaire TAMCIC 26 octobre 2006 25 / 31

Résultats et comparaison

Turbocode duo-binaire

H2 =

0BBBBBBBBBBB@

1 10 1 1 11 1 0 1 1 11 1 1 1 0 1 1 1

1 1 1 1 0 11 1 1 1

1 1

. . .

1CCCCCCCCCCCAet H1 =

0BBBBBBBBBBB@

11 10 1 11 0 1 1

1 0 11 0

1

. . .

1CCCCCCCCCCCA

Rendement en abscence de poinçonnage : R = 1/2

H1H2

H π2 T 0 1

0

H=

K

2K

K/2 K/2

K/2

K/2H

Permutation inter-symbole quasi-régulière

Rodrigue Imad () Séminaire TAMCIC 26 octobre 2006 26 / 31

Résultats et comparaison

FER pour des blocs de 424 bits d’information

0 0.5 1 1.5 2 2.5 3 3.5 410

−6

10−5

10−4

10−3

10−2

10−1

100

Eb/No(dB)

Fra

me

Err

or R

ate

BCJR (8 iter.)BP sur Z

22

BP sur Z24

BP sur Z28

Rodrigue Imad () Séminaire TAMCIC 26 octobre 2006 27 / 31

Résultats et comparaison

FER pour des blocs de 432 bits d’information

0 0.5 1 1.5 2 2.5 3 3.5 410

−6

10−5

10−4

10−3

10−2

10−1

100

Eb/No(dB)

Fra

me

Err

or R

ate

BCJR (8 iter.)BP sur Z

22

BP sur Z28

BP sur Z29

Rodrigue Imad () Séminaire TAMCIC 26 octobre 2006 28 / 31

Plan

1 Représentations Algébriques des codes convolutifs

2 Décodage des codes convolutifs

3 Turbocodes : Représentation algébrique et décodage associé

4 Conclusion et perspectives

Rodrigue Imad () Séminaire TAMCIC 26 octobre 2006 29 / 31

Conclusion et perspectives

Nombre important de cycles si BP ’classique’ utilisé→ Décodage BP sur les groupes

codes convolutifs : performances quasi identiques en absence de cycles

Turbocodes : Dégradation dans les performances du BP qui diminueavec p

Suite à ce stage...

Recherche d’un entrelaceur spécifique

Application du ’Tail-Biting’

Etude de la complexité du BP

Rodrigue Imad () Séminaire TAMCIC 26 octobre 2006 30 / 31

Questions ?

Rodrigue Imad () Séminaire TAMCIC 26 octobre 2006 31 / 31

Représentations Algébriques des codes convolutifsDécodage des codes convolutifsTurbocodes: Représentation algébrique et décodage associéConclusion et perspectives