67
Année 2011 - 2012 Transmission de l’information : Les codes convolutifs (A. Migan), S. Argentieri

Année 2011 - 2012

  • Upload
    samira

  • View
    44

  • Download
    0

Embed Size (px)

DESCRIPTION

Année 2011 - 2012. Transmission de l’information : Les codes convolutifs. (A . Migan ), S. Argentieri. Les codes convolutifs. I. Principe du codage convolutif. Les codes convolutifs forment une classe extrêmement souple et efficace de codes correcteurs d’erreur. - PowerPoint PPT Presentation

Citation preview

Page 1: Année  2011  -  2012

Année 2011 - 2012

Transmission de l’information :

Les codes convolutifs

(A. Migan), S. Argentieri

Page 2: Année  2011  -  2012

2/89Transmission de l’Information : les codes convolutifs

I. Principe du codage convolutif

Les codes convolutifs forment une classe extrêmement souple et efficace de codes correcteurs d’erreur.

Ce sont les codes les plus utilisés dans les communications fixes et mobiles.

Les codes convolutifs ont les mêmes caractéristiques que les codes en bloc sauf qu’ils s’appliquent à des séquences infinies de

symboles d’information et génèrent des séquences infinies de symboles de code.

Les codes convolutifs

Page 3: Année  2011  -  2012

3/89Transmission de l’Information : les codes convolutifs

I. Principe du codage convolutif

I. 1. Encodeurs

Le codeur qui engendre un code convolutif comporte un effet de mémoire :

Le mot code ne dépend pas que du bloc de k symboles entrant, mais aussi des m mots de code qui l’ont précédé, stockés dans un

registre.

Les codes convolutifs

Logique combinatoire

Registre à (m+1)k étages

Convertisseur Parallèle-

Série

EntréeBloc de k

éléments

binaires

SortieBloc de n

éléments

binaires

Page 4: Année  2011  -  2012

4/89Transmission de l’Information : les codes convolutifs

I. Principe du codage convolutif

I. 1. Encodeurs

Théorème fondamental du codage de canal

La complexité du codeur est nécessaire à l’obtention

de bonnes performances

Pour les codes en bloc : n et k doivent être grands

Pour les codes convolutifs : il suffit que m soit grand

Logique combinatoire

Registre à (m+1)k étages

Convertisseur Parallèle-

Série

EntréeBloc de k

éléments

binaires

SortieBloc de n

éléments

binaires

Les codes convolutifs

Page 5: Année  2011  -  2012

5/89Transmission de l’Information : les codes convolutifs

I. Principe du codage convolutif

I. 2. Propriétés

Mot code : C = (X1 Y

1 X

2 Y

2 … X

j Y

j …)

Avec Xj = Information

Yj = Contrôle

kj

2j

1j X...XX

kj

2j

1j Y...YY

Le rendement du code est :

La longueur de contrainte du code est :

Linéarité : les mots de code associés à une combinaison linéaire de séquences d’entrée correspondent à la combinaison

linéaire des mots de code de chacune des ces séquences.

Stationnarité : Lorsqu’un message source, décalé dans le temps, est envoyé sur l’encodeur, on doit retrouver à la sortie,

le mot de code correspondant décalé de la même manière dans le temps.

Code convolutif systématique :

nkR

km 1

Les codes convolutifs

Page 6: Année  2011  -  2012

6/89Transmission de l’Information : les codes convolutifs

I. Principe du codage convolutif

I. 3. Exemple

Exemple de codeur convolutif non systématique :

R = 1/2 ; m = 2 ; k = 1 ; n = 2

1je 2

je

2jj1j ssx

2j1jj2j sssx

js

A chaque pas de temps j :

On combine les valeurs de l’entrée et de la mémoire pour calculer

les sorties ;

Chaque registre à décalage est mis à jour par la valeur qui figure à

son entrée.

Les codes convolutifs

Page 7: Année  2011  -  2012

7/89Transmission de l’Information : les codes convolutifs

La distance libre est la borne inférieure des distances de Hamming entre toutes les séquences de sortie du codeur.

La distance minimale est la plus petite distance entre des chemins partant du même point et y revenant.

I. 4. Les distances dans les codes convolutifs

I. Principe du codage convolutif

Les codes convolutifs

Page 8: Année  2011  -  2012

8/89Transmission de l’Information : les codes convolutifs

Représentations numériques :

Transformée en D ;

Matrice de transfert ;

Représentations graphiques :

Diagramme d’état ;

Arbre ;

Treillis.

Les codes convolutifs

II. Représentations des codes convolutifs

Page 9: Année  2011  -  2012

9/89Transmission de l’Information : les codes convolutifs

II. 1. Représentations numériques : Transformée en D

Une séquence de symboles est représentée par une série formelle en la variable D. Cette variable représente

l’opérateur de retard unitaire :

...D.x...D.xD.xx)D(x

...D.s...D.sD.ss)D(sji

j2i

2i1

i0

i

jj

2210

La réponse impulsionnelle du ième module, hi(D), est la séquence de sortie produite lorsque le message d’entrée est une

suite commençant par le symbole ‘1’ et se terminant par une suite de ‘0’ de longueur infinie :

xi(D) = hi(D).s(D)

Les codes convolutifs

II. Représentations des codes convolutifs

Page 10: Année  2011  -  2012

10/89Transmission de l’Information : les codes convolutifs

1je 2

je

2jj1j ssx

2j1jj2j sssx

js

e1(D) = D.s(D)

e2(D) = D.e1(D) = D2.s(D)

x1(D) = s(D) + e2(D) = (1 + D2).s(D)

x2(D) = s(D) + e1(D) + e2(D) = (1 + D + D2).s(D)

Les codes convolutifs

II. 1. Représentations numériques : Transformée en D

II. Représentations des codes convolutifs

22 DD1D1DH

Page 11: Année  2011  -  2012

11/89Transmission de l’Information : les codes convolutifs

e1(D) = D.s(D)

e2(D) = D.e1(D) = D2.s(D)

e3(D) = D.e2(D) = D3.s(D)

x1(D) = s(D) + e2(D) + e3(D)

x1(D) = (1 + D2 + D3).s(D)

x2(D) = s(D) + e1(D) + e2(D) + e2(D)

x2(D) = (1 + D + D2 + D3).s(D)

k = 1 ; n = 2 ; m = 3

Les codes convolutifs

II. 1. Représentations numériques : Transformée en D

II. Représentations des codes convolutifs

3232 DDD1DD1DH

Page 12: Année  2011  -  2012

12/89Transmission de l’Information : les codes convolutifs

x1(D) = s1(D) + e12(D)

x1(D) = (1 + D2).s1(D) + 0.s2(D)

x2(D) = e11(D) + e12(D) + e21(D)

x2(D) = (D + D2).s1(D) + D.s2(D)

x3(D) = e11(D) + s2(D)

x3(D) = D.s1(D) + 1.s2(D)

k = 2 ; n = 3 ; m = 2

Les codes convolutifs

II. 1. Représentations numériques : Transformée en D

II. Représentations des codes convolutifs

1D0DDDD1DH

22

x1(D)

x2(D)

x3(D)

s1(D)

s2(D)

Page 13: Année  2011  -  2012

13/89Transmission de l’Information : les codes convolutifs

Les codes convolutifs

La matrice de transfert donne la relation entrée-sortie sous forme matricielle. On l’écrit pour chaque étage de sortie.

La matrice de transfert globale est la concaténation des matrices précédentes. Elle a k lignes et (m+1)n colonnes.

II. 2. Représentations numériques : Matrice de transfert

II. Représentations des codes convolutifs

La ième ligne donne la relation entre

et

La (i + 1)ème ligne donne la relation entre et

kjx i

jskjx 1i

js

Pour la kième sortie :

La 1ère colonne correspond à l’instant j,

La 2ème colonne correspond à l’instant (j – 1) …

...............

...............

...............

...ss

...1

1i

ijj

Page 14: Année  2011  -  2012

14/89Transmission de l’Information : les codes convolutifs

1jx

2jx

3jx

1js

2js

2j

11j

3j

21j

12j

11j

2j

12j

1j

1j

ssx

sssx

ssx

Relations entrée/sortie :

42

001010G

23

010110G

05

000101G

3

2

1

Matrices de transfert intermédiaires :

001010000

010110101T

Matrices de transfert :k = 2, n = 3, m = 2

Les codes convolutifs

II. 2. Représentations numériques : Matrice de transfert

II. Représentations des codes convolutifs

Page 15: Année  2011  -  2012

15/89Transmission de l’Information : les codes convolutifs

II. Représentations des codes convolutifs

Chaque bloc de n éléments binaires en sortie du codeur dépend :

Du bloc de k éléments binaires présents à son entrée ;

Des m blocs de k éléments binaires contenus dans sa mémoire.

Ces m.k éléments binaires définissent l’état du codeur.

1je 2

je

2jj1j ssx

2j1jj2j sssx

js

k = 1

n = 2

m = 2

Les codes convolutifs

Les quatre états possibles du codeur sont :

‘00’ ‘01’

‘10’ ‘11’

II. 3. Représentations graphiques

Page 16: Année  2011  -  2012

16/89Transmission de l’Information : les codes convolutifs

II. Représentations des codes convolutifs

II. 3. Représentations graphiques : Diagramme d’état

Les codes convolutifs

Les conventions adoptées :

Lorsque l’élément binaire d’entrée du codeur est égal à ‘0’ (resp. ‘1’), le couple binaire en sortie du codeur est porté par la

branche rouge (resp. verte).

Seules deux (q) transitions sont possibles à partir de chacun des états.

Les étiquettes de chaque branche correspondent aux sorties du codeur.

Page 17: Année  2011  -  2012

17/89Transmission de l’Information : les codes convolutifs

00

00

0

État a

‘00’

État ‘11’

État ‘10’ État ‘01’

0

0

0

Instant j

Instant j+1

Instant j+1 ?

Instant j

État ‘00’

00

Les codes convolutifs

II. Représentations des codes convolutifs

II. 3. Représentations graphiques :

Diagramme d’état

Page 18: Année  2011  -  2012

18/89Transmission de l’Information : les codes convolutifs

1

00

0

État a

‘00’

État ‘11’

État ‘10’ État ‘01’

État ‘00’

001

1

1

Instant j

Instant j+1Instant j

11

Les codes convolutifs

II. Représentations des codes convolutifs

II. 3. Représentations graphiques :

Diagramme d’état

Page 19: Année  2011  -  2012

19/89Transmission de l’Information : les codes convolutifs

00

00

État ‘00’

État ‘11’

État ‘10’ État b

‘01’

État ‘01’

100

1

1

Instant j

Instant j+1Instant j

11 11

Les codes convolutifs

II. Représentations des codes convolutifs

II. 3. Représentations graphiques :

Diagramme d’état

Page 20: Année  2011  -  2012

20/89Transmission de l’Information : les codes convolutifs

01

00

État ‘00’

État ‘11’

État ‘10’ État b

‘01’

État ‘01’

101

0

0

Instant j

Instant j+1Instant j

11

00

11

Les codes convolutifs

II. Représentations des codes convolutifs

II. 3. Représentations graphiques :

Diagramme d’état

Page 21: Année  2011  -  2012

21/89Transmission de l’Information : les codes convolutifs

00

État ‘00’

État ‘11’

État ‘10’ État ‘01’

11

00

11

10

1010

01

Les codes convolutifs

II. Représentations des codes convolutifs

II. 3. Représentations graphiques :

Diagramme d’état

Page 22: Année  2011  -  2012

22/89Transmission de l’Information : les codes convolutifs

00

État ‘00’

État ‘11’

État ‘10’ État ‘01’

11

00

11

10

1010

01

La distance minimale est le poids du chemin partant de

‘00’ et y revenant le plus vite possible :

Poids = 6

Les codes convolutifs

II. Représentations des codes convolutifs

II. 3. Représentations graphiques :

Diagramme d’état

Page 23: Année  2011  -  2012

23/89Transmission de l’Information : les codes convolutifs

00

État ‘00’

État ‘11’

État ‘10’ État ‘01’

11

00

11

10

1010

01

La distance minimale est le poids du chemin partant de

‘00’ et y revenant le plus vite possible :

Poids = 5

dmin

= 5

Les codes convolutifs

II. Représentations des codes convolutifs

II. 3. Représentations graphiques :

Diagramme d’état

Page 24: Année  2011  -  2012

24/89Transmission de l’Information : les codes convolutifs

II. Représentation des codes convolutifs

II. 4. Représentations graphiques : Arbre

Développement du diagramme d’état en fonction du temps discrétisé

Les conventions adoptées :

Le temps s’écoule de la gauche vers la droite

Lorsque l’élément binaire d’entrée du codeur est égal à ‘0’ (resp. ‘1’), le couple binaire en sortie du codeur est porté par la

branche supérieure (resp. inférieure).

Les branches se séparent en un point appelé nœud. Chaque nœud donne naissance à 2k (qk) branches.

Quelque soit l’état initial du codeur, après (m + 1) décalages à l’entrée du codeur, tous les états du codeur peuvent être atteints.

Les codes convolutifs

Page 25: Année  2011  -  2012

25/89Transmission de l’Information : les codes convolutifs

Instant j+1

Instant j

00

00

II. Représentation des codes convolutifs

II. 4. Représentations graphiques : Arbre

Les codes convolutifs

Page 26: Année  2011  -  2012

26/89Transmission de l’Information : les codes convolutifs

0

0

0

0

0

Instant j+1

Instant j

00

00

00

00

II. Représentation des codes convolutifs

II. 4. Représentations graphiques : Arbre

t = j+1

Les codes convolutifs

Page 27: Année  2011  -  2012

27/89Transmission de l’Information : les codes convolutifs

1

1

1

1

0

Instant j+1

Instant j

00

00

11

00

00

10

II. Représentation des codes convolutifs

II. 4. Représentations graphiques : Arbre

t = j+1

Les codes convolutifs

Page 28: Année  2011  -  2012

28/89Transmission de l’Information : les codes convolutifs

0

0

0

0

0

Instant j+1

Instant j

00

00

00

11

11

00

00

00

10

10

II. Représentation des codes convolutifs

II. 4. Représentations graphiques : Arbre

t = j+1 t = j+2

Les codes convolutifs

Page 29: Année  2011  -  2012

29/89Transmission de l’Information : les codes convolutifs

Instant j+1

Instant j

00

00

11

01

11

10

00

00

00

01

10

10

11

II. Représentation des codes convolutifs

II. 4. Représentations graphiques : Arbre

t = j+1 t = j+2

Les codes convolutifs

Page 30: Année  2011  -  2012

30/89Transmission de l’Information : les codes convolutifs

Instant j+1

Instant j

00

00

1100

0111

1000

1101

0011

1010

01

0011

1101

0100

1011

1110

0010

1001

01

00

00

00

00

00

00

00

00

00

01

01

01

01

01

01

01

10

10

10

10

10

10

1011

11

11

10

11

11

11

11

II. Représentation des codes convolutifs

II. 4. Représentations graphiques : Arbre

t = j+1 t = j+2 t = j+3 t = j+4

Les codes convolutifs

Page 31: Année  2011  -  2012

31/89Transmission de l’Information : les codes convolutifs

0000

1100

0111

1000

1101

0011

1010

01

0011

1101

0100

1011

1110

0010

1001

01

t = j t = j+1 t = j+2 t = j+3 t = j+4

00

00

00

00

00

00

00

00

00

01

01

01

01

01

01

01

10

10

10

10

10

10

1011

11

11

10

11

11

11

11

Partant de l’état ‘00’ à l’instant t = j, il existe deux chemins pour

atteindre l’état ‘00’ à l’instant t = j + 3

00 00 00 ® Chemin 1

II. Représentation des codes convolutifs

II. 4. Représentations graphiques : Arbre

Les codes convolutifs

Page 32: Année  2011  -  2012

32/89Transmission de l’Information : les codes convolutifs

00

00

1100

0111

1000

1101

0011

1010

01

0011

1101

0100

1011

1110

0010

1001

01

00

00

00

00

00

00

00

00

00

01

01

01

01

01

01

01

10

10

10

10

10

10

1011

11

11

10

11

11

11

11

11 01 11 ® Chemin 2

Partant de l’état ‘00’ à l’instant t = j, il existe deux chemins

pour atteindre l’état ‘00’ à l’instant t = j + 3

00 00 00 ® Chemin 1

II. Représentation des codes convolutifs

II. 4. Représentations graphiques : Arbre

t = j t = j+1 t = j+2 t = j+3 t = j+4

Les codes convolutifs

Page 33: Année  2011  -  2012

33/89Transmission de l’Information : les codes convolutifs

00

00

1100

0111

1000

1101

0011

1010

01

0011

1101

0100

1011

1110

0010

1001

01

00

00

00

00

00

00

00

00

00

01

01

01

01

01

01

01

10

10

10

10

10

10

1011

11

11

10

11

11

11

11

Distance minimale : dmin

= 5

II. Représentation des codes convolutifs

II. 4. Représentations graphiques : Arbre

11 01 11 ® w = 5

00 00 00 ®

t = j t = j+1 t = j+2 t = j+3 t = j+4

Les codes convolutifs

Page 34: Année  2011  -  2012

34/89Transmission de l’Information : les codes convolutifs

00

00

1100

0111

1000

1101

0011

1010

01

0011

1101

0100

1011

1110

0010

1001

01

00

00

00

00

00

00

00

00

00

01

01

01

01

01

01

01

10

10

10

10

10

10

1011

11

11

10

11

11

11

11

Si la séquence d’information est : ‘1001’

00

1

® 01

01

® 00

11

® 10

11

Le mot de code associé à ‘1001’ est ‘11011111’

® 10

11

0 0 1

01

11

1111

II. Représentation des codes convolutifs

II. 4. Représentations graphiques : Arbre

t = j t = j+1 t = j+2 t = j+3 t = j+4

Les codes convolutifs

Page 35: Année  2011  -  2012

35/89Transmission de l’Information : les codes convolutifs

II. Représentation des codes convolutifs

II. 5. Représentations graphiques : Treillis

Les conventions adoptées :

Lorsque l’élément binaire d’entrée du codeur est égal à ‘0’ (resp. ‘1’), le couple binaire en sortie du codeur est porté par la

branche rouge (resp. verte).

De chaque nœud partent 2k (qk) branches.

En chaque nœud convergent 2k (qk) branches.

Les étiquettes de chaque branche correspondent aux sorties du codeur.

Les codes convolutifs

Page 36: Année  2011  -  2012

36/89Transmission de l’Information : les codes convolutifs

00

0

0

0

0

II. Représentation des codes convolutifs

0

Instant j+1

Instant j

00 00

01

10

11

t = j t = j+1

Les codes convolutifs

II. 5. Représentations graphiques : Treillis

Page 37: Année  2011  -  2012

37/89Transmission de l’Information : les codes convolutifs

11

00

1

1

1

1

II. Représentation des codes convolutifs

0

Instant j+1

Instant j

00 00

01

10

11

t = j t = j+1 t = j+2

Les codes convolutifs

II. 5. Représentations graphiques : Treillis

Page 38: Année  2011  -  2012

38/89Transmission de l’Information : les codes convolutifs

11

00

11

00

01

II. Représentation des codes convolutifs

0

0

1

0

1

Instant j+1

Instant j

01 00

01

10

11

t = j t = j+1 t = j+2

Les codes convolutifs

II. 5. Représentations graphiques : Treillis

Page 39: Année  2011  -  2012

39/89Transmission de l’Information : les codes convolutifs

11

00

11

00

01

10

1

1

0

1

II. Représentation des codes convolutifs

1

Instant j+1

Instant j

01 00

01

10

11

t = j t = j+1 t = j+2

Les codes convolutifs

II. 5. Représentations graphiques : Treillis

Page 40: Année  2011  -  2012

40/89Transmission de l’Information : les codes convolutifs

II. Représentation des codes convolutifs

11

00

11

0011

00

11

00

01

10

01

10

11

00

11

00

01

10

00

01

10

11

t = j t = j+1 t = j+2 t = j+3 t = j+4

01 01

10 10

Après (m + 1) décalages, quelque soit l’état initial du codeur, le motif du

treillis se répète

Les codes convolutifs

II. 5. Représentations graphiques : Treillis

Page 41: Année  2011  -  2012

41/89Transmission de l’Information : les codes convolutifs

II. Représentation des codes convolutifs

Comme pour le diagramme en arbre, partant de l’état ‘00’ à

l’instant t = j, il existe deux chemins pour atteindre l’état ‘00’ à

l’instant t = j + 3

00 00 00 ® Chemin 1

11 01 11 ® Chemin 2 ; w = 5

11

00

11

0011

00

11

00

01

10

01

10

11

00

11

00

01

10

00

01

10

11

t = j t = j+1 t = j+2 t = j+3 t = j+4

01 01

10 10

dmin

= 5

Les codes convolutifs

II. 5. Représentations graphiques : Treillis

Page 42: Année  2011  -  2012

42/89Transmission de l’Information : les codes convolutifs

II. Représentation des codes convolutifs

La séquence d’information est ‘1001’

11

00

11

0011

00

11

00

01

10

01

10

11

00

11

00

01

10

00

01

10

11

t = j t = j+1 t = j+2 t = j+3 t = j+4

01 01

10 10

® 0100 ® 00 ® 10

1 0 0 1

01 11 11

Le mot de code associé à ‘1001’ est ‘11011111’

® 10

11

11

01

11

11

Les codes convolutifs

II. 5. Représentations graphiques : Treillis

Page 43: Année  2011  -  2012

43/89Transmission de l’Information : les codes convolutifs

III. Codes particuliers

Dédier une sortie aux bits d’information :

III. 1. Les codes systématiques

Les codes convolutifs

G = (4 5 3)octal

00

01

10

11

000

101

110

011

010

111

100

001

000

101

110

011

010

111

100

001

Réponse impulsionnelle :

Matrice de transfert :

Treillis :

22 DDD11DH

Page 44: Année  2011  -  2012

44/89Transmission de l’Information : les codes convolutifs

III. Codes particuliers

III. 2. Les codes récursifs systématiques

Les codes convolutifs

Réponses impulsionnelles :

Boucle de retour :

DsDx1

1j

2jj ees

1jj

2j

1j

2jj

2j

2j

esxeesex

j1j sx

DsDD1

DDsDx

DsDD1

DDe

Ds.DDe.DD1

DeDe.DDsDDe

DeDeDsDDe

DeDsDx

22

21

12

111

121

12

2

2

DD1D11DH

Page 45: Année  2011  -  2012

45/89Transmission de l’Information : les codes convolutifs

III. Codes particuliers

III. 2. Les codes récursifs systématiques

Les codes convolutifs

Réponses impulsionnelles :

Treillis :

00

01

10

11

00

11

11

00

10

01

01

10

00

11

11

00

10

01

01

10

Boucle de retour :

2

2

DD1D11DH

Page 46: Année  2011  -  2012

46/89Transmission de l’Information : les codes convolutifs

Un code catastrophique est un code qui génère un nombre infini d’erreurs

Une séquence d’information de poids infinie est codée par une séquence de poids fini

Le décodeur, recevant une séquence de poids fini, estimera que la séquence d’entrée était constituée d’un mot de poids fini suivi

de zéros.

Les codes convolutifs

III. Codes particuliers

III. 3. Les codes catastrophiques

Page 47: Année  2011  -  2012

47/89Transmission de l’Information : les codes convolutifs

00

État a

‘00’

État d

‘11’

État c

‘10’

État b

‘01’

11

10

01

10

0111

00

Les codes convolutifs

III. Codes particuliers

III. 3. Les codes catastrophiques

Page 48: Année  2011  -  2012

48/89Transmission de l’Information : les codes convolutifs

01

00

01

0011

00

11

00

10

01

10

01

11

00

11

00

10

01

00

01

10

1100 00

10 10

Appliquons à l’entrée de ce codeur une séquence constituée

d’un nombre infini de ‘1’.

A la sortie, apparaîtra le mot ‘1101’ suivi d’un nombre infini

de ‘0’

Le décodeur estimera que l’entrée était constitué d’un mot de

poids fini (par exemple ‘1010’) suivi d’un nombre infini de

‘0’

Les codes convolutifs

III. Codes particuliers

III. 3. Les codes catastrophiques

Page 49: Année  2011  -  2012

49/89Transmission de l’Information : les codes convolutifs

01

00

01

0011

00

11

00

10

01

10

01

11

00

11

00

10

01

00

01

10

1100 00

10 10

00

État a

‘00’

État d

‘11’

État c

‘10’

État b

‘01’

11

10

01

10

0111

00

Les codes convolutifs

III. Codes particuliers

III. 3. Les codes catastrophiques

Tous les codeurs catastrophiques ont :

Dans leur représentation en treillis : un arc horizontal produisant une sortie de poids

nul, pour une entrée de poids non nul

Dans leur diagramme d’état : une boule portant l’étiquette ‘00’ pour une entrée égale à

‘1’

Page 50: Année  2011  -  2012

50/89Transmission de l’Information : les codes convolutifs

IV. Décodage convolutif

Les codes convolutifs

Dans les canaux de communication sans mémoire, les systèmes utilisant le codage convolutif sont parmi les plus

intéressants tant du point de vue de leurs performances (s’approchant le plus des performances ultimes prévues par la théorie

de Shannon) que du point de vue de leur réalisation et implantation matérielle.

Les deux principales techniques de décodage des codes convolutifs sont le décodage de Viterbi et le décodage séquentiel.

Chacune de ses techniques consiste à trouver un chemin particulier (le message transmis), dans un graphe orienté où on

assigne aux branches des métriques ou valeurs de vraisemblance entre les données reçues et les données qui auraient pu être

transmises.

L’objectif général du décodeur se résume donc à déterminer avec la plus grande fiabilité et le minimum d’efforts le

chemin de métrique minimale. Ce chemin est la séquence décodée.

Page 51: Année  2011  -  2012

51/89Transmission de l’Information : les codes convolutifs

A chaque instant, deux branches appartenant à deux chemins différents, convergent vers chaque noeud.

De ces deux chemins, l’un est plus vraisemblable, c’est-à-dire se trouve à une distance plus petite de la séquence reçue, que

l’autre chemin.

Les distances étant additives, il est possible de ne conserver en chaque nœud que le chemin le plus vraisemblable, appelé

survivant.

Si deux chemins sont aussi vraisemblables, un seul chemin est arbitrairement conservé.

Les codes convolutifs

IV. Décodage convolutif

IV. 1. Algorithme de Viterbi

Page 52: Année  2011  -  2012

52/89Transmission de l’Information : les codes convolutifs

Supposons que la séquence à l’entrée du codeur soit ‘1 0 0 1’.

Si le codeur est dans l’état ‘00’ à l’instant initial,

la séquence correspondante en sortie du codeur est ’11 01 11 11’.

Considérons un canal binaire symétrique introduisant une erreur en position 4.

La séquence reçue à l’entrée du décodeur est ’11 00 11 11’.

Voici le déroulement de l’algorithme de Viterbi :

Les codes convolutifs

IV. Décodage convolutif

IV. 1. Algorithme de Viterbi

Page 53: Année  2011  -  2012

53/89Transmission de l’Information : les codes convolutifs

IV. Décodage convolutif

00

11

00

01

10

11

t = 0 t = 1

(2)

(0)

Mot reçu : ‘11’

A l’instant t = 0 :

Deux branches partent de l’état ‘00’. Elles sont respectivement à la distance 2 et 0 du

premier couple binaire reçu. Reportons ces deux distances, appelées métriques de

branche sur le treillis.

Les codes convolutifs

IV. 1. Algorithme de Viterbi

Page 54: Année  2011  -  2012

54/89Transmission de l’Information : les codes convolutifs

00

11

00

01

10

11

t = 0 t = 1

A l’instant t = 1 :

Évaluons la distance entre le deuxième couple binaire reçu et les quatre

branches qui partent des états ‘00’ et ‘10’, puis reportons ces quatre

métriques sur le treillis.

En sommant les métriques de branches appartenant à un même chemin, nous

obtenons les métriques cumulées.

Nous avons désormais quatre chemins qui permettent d’accéder, en t = 2,

aux quatre états possibles du codeur.

00

11

t = 2

(2)

(4)

(2)

(0)

(1)

(1)

01

10

Mot reçu : ‘11’ ‘00’

Les codes convolutifs

IV. Décodage convolutif

IV. 1. Algorithme de Viterbi

Page 55: Année  2011  -  2012

55/89Transmission de l’Information : les codes convolutifs

00

11

00

01

10

11

t = 0 t = 1

A l’instant t = 2 :

Il existe désormais deux chemins qui convergent vers chaque nœud du

treillis.

00

11

t = 2

(2)

(0)01

10

11

t = 3

(2)

(1)

11

(4)

(1)

01

10

Mot reçu : ‘11’ ‘00’ ‘11’

00

00

01

10

Les codes convolutifs

IV. Décodage convolutif

IV. 1. Algorithme de Viterbi

Page 56: Année  2011  -  2012

56/89Transmission de l’Information : les codes convolutifs

00

11

00

01

10

11

t = 0 t = 1

A l’instant t = 2 :

Il existe désormais deux chemins qui convergent vers chaque nœud du

treillis.

On va donc :

00

11

t = 2

(2)

(0)01

101. Calculer les métriques de branche.

11

t = 3

(2)

(1)

11

(4)

(1)

01

10

Mot reçu : ‘11’ ‘00’ ‘11’

00

00

01

10

(4)

(5)

(2)

(5)

(1)

(2)

(3)

(2)2. Calculer les métriques cumulées pour chaque chemin

atteignant en t = 3, un nœud donné du treillis.

Les codes convolutifs

IV. Décodage convolutif

IV. 1. Algorithme de Viterbi

Page 57: Année  2011  -  2012

57/89Transmission de l’Information : les codes convolutifs

00

11

00

01

10

11

t = 0 t = 1

A l’instant t = 2 :

Il existe désormais deux chemins qui convergent vers chaque nœud du

treillis.

On va donc :

00

11

t = 2

(2)

(0)01

101. Calculer les métriques de branche.

11

t = 3

(2)

(1)

11

(4)

(1)

01

10

Mot reçu : ‘11’ ‘00’ ‘11’

00

01

10

(5)

(2)

(5)

(2)

(3)

(2)2. Calculer les métriques cumulées pour chaque chemin

atteignant en t = 3, un nœud donné du treillis.

3. En chaque nœud, ne retenir que le survivant.

(1)

Les codes convolutifs

IV. Décodage convolutif

IV. 1. Algorithme de Viterbi

Page 58: Année  2011  -  2012

58/89Transmission de l’Information : les codes convolutifs

00

11

00

01

10

11

t = 0 t = 1

A l’instant t = 2 :

Il existe désormais deux chemins qui convergent vers chaque nœud du

treillis.

On va donc :

00

11

t = 2

(2)

(0)01

101. Calculer les métriques de branche.

11

t = 3

(2)

(1)

11

(4)

(1)

01

10

Mot reçu : ‘11’ ‘00’ ‘11’

00

10

(2)

(5)

(3)

(2)2. Calculer les métriques cumulées pour chaque chemin

atteignant en t = 3, un nœud donné du treillis.

3. En chaque nœud, ne retenir que le survivant.

(1)

(2)

Les codes convolutifs

IV. Décodage convolutif

IV. 1. Algorithme de Viterbi

Page 59: Année  2011  -  2012

59/89Transmission de l’Information : les codes convolutifs

00

11

00

01

10

11

t = 0 t = 1

A l’instant t = 2 :

Il existe désormais deux chemins qui convergent vers chaque nœud du

treillis.

On va donc :

00

11

t = 2

(2)

(0)01

101. Calculer les métriques de branche.

11

t = 3

(2)

(1)

11

(4)

(1)

01

10

Mot reçu : ‘11’ ‘00’ ‘11’

10(5)

(2)2. Calculer les métriques cumulées pour chaque chemin

atteignant en t = 3, un nœud donné du treillis.

3. En chaque nœud, ne retenir que le survivant.

(1)

(2)

(2)

Les codes convolutifs

IV. Décodage convolutif

IV. 1. Algorithme de Viterbi

Page 60: Année  2011  -  2012

60/89Transmission de l’Information : les codes convolutifs

00

11

00

01

10

11

t = 0 t = 1

A l’instant t = 2 :

Il existe désormais deux chemins qui convergent vers chaque nœud du

treillis.

On va donc :

00

11

t = 2

(2)

(0)01

101. Calculer les métriques de branche.

11

t = 3

(2)

(1)

11

(4)

(1)

01

10

Mot reçu : ‘11’ ‘00’ ‘11’

2. Calculer les métriques cumulées pour chaque chemin

atteignant en t = 3, un nœud donné du treillis.

3. En chaque nœud, ne retenir que le survivant.

(1)

(2)

(2)

(2)

Les codes convolutifs

IV. Décodage convolutif

IV. 1. Algorithme de Viterbi

Page 61: Année  2011  -  2012

61/89Transmission de l’Information : les codes convolutifs

00

11

00

01

10

11

t = 0 t = 1

A l’instant t = 3 :

On procède de la même façon

00

11

t = 2

(2)

(0)01

10

11

t = 3

(2)

(1)

11

(4)

(1)

01

10

11

t = 4

(1)

(2)

11

(2)

(2)

01

(2)

(3)

(1)

(3)

01

Mot reçu : ‘11’ ‘00’ ‘11’ ‘11’

Les codes convolutifs

IV. Décodage convolutif

IV. 1. Algorithme de Viterbi

Page 62: Année  2011  -  2012

62/89Transmission de l’Information : les codes convolutifs

00

11

00

01

10

11

t = 0 t = 1

Finalement, le chemin le plus vraisemblable est celui

qui arrive en ‘10’.00

11

t = 2

(2)

(0)01

10

11

t = 3

(2)

(1)

11

(4)

(1)

01

10

11

t = 4

(1)

(2)

11

(2)

(2)

01

(2)

(3)

(1)

(3)

01

Les codes convolutifs

IV. Décodage convolutif

IV. 1. Algorithme de Viterbi

Page 63: Année  2011  -  2012

63/89Transmission de l’Information : les codes convolutifs

00

11

00

01

10

11

t = 0 t = 1

Finalement, le chemin le plus vraisemblable est celui

qui arrive en ‘10’.00

11

t = 2

(2)

(0) 01

10

11

t = 3

(2)

(1)

11

(4)

(1)

01

10

11

t = 4

(1)

(2)

11

(2)

(2)

01

(2)

(3)

(1)

(3)

01

En remontant le treillis de la droite vers la gauche, on

voit que la séquence la plus vraisemblable est celle

qui part de ‘00’ à t = 0 et qui arrive à ‘10’ à t = 4. Elle

correspond au code vraisemblablement émis : ‘11 01

11 11’.

Ce code correspond à une séquence sur l’entrée du codeur égale à ‘1001’. L’erreur en position 4 est donc corrigée.

Les codes convolutifs

IV. Décodage convolutif

IV. 1. Algorithme de Viterbi

Page 64: Année  2011  -  2012

64/89Transmission de l’Information : les codes convolutifs

Viterbi : complexité de calcul en 2m

Amélioration des codes convolutifs si m augmente

→ Décodage séquentiel

Recherche d’un parcours optimal dans un graphe :

Viterbi : Evaluer la qualité de tous les chemins à une profondeur donnée

Séquentiel : Parcours d’un unique chemin tant qu’il paraît bon

IV. 2. Décodage séquentiel

Les codes convolutifs

IV. Décodage convolutif

Page 65: Année  2011  -  2012

65/89Transmission de l’Information : les codes convolutifs

Dans la structure d’arbre, à chaque nœud, on calcule les distances correspondantes aux deux successeurs et l’on poursuit

dans la direction de celle qui conduit au chemin le plus court.

Si on choisit une mauvaise route (la distance observée dépasse un seuil fixé) : on rebrousse chemin et on reprend dans

une autre direction

Mais cela peut arriver de nouveau

Jusqu’où faut-il remonter dans l’arbre ?

Mémoire tampon importante

Les codes convolutifs

IV. 2. Décodage séquentiel : Algorithme de Fano

IV. Décodage convolutif

Page 66: Année  2011  -  2012

66/89Transmission de l’Information : les codes convolutifs

Les codes convolutifs

Algorithme de Fano utilisant un système de pile pour gérer plus efficacement les retours en arrière. Le décodeur

consiste en une pile où sont stockés les chemins explorés :

Le stockage est effectué par ordre décroissant des valeurs de leurs métriques.

Le sommet de la pile contient le chemin de métrique minimale courant et sera donc prolongé en tous ses

descendants sur une profondeur égale à une branche.

IV. 2. Décodage séquentiel : Algorithme à piles

IV. Décodage convolutif

Page 67: Année  2011  -  2012

67/89Transmission de l’Information : les codes convolutifs

VI. Codes cycliques – Codes convolutifs

Rendement élevé (0,9)

Correction des paquets d’erreurs

Codes cycliques :

Rendement faible mais performances élevées grâce

au décodage à décision souple

Correction des erreurs isolées

Codes convolutifs :

Modifications de codes

Associations de codes

Comparaison des codes