Année 2011 - 2012
Transmission de l’information :
Les codes convolutifs
(A. Migan), S. Argentieri
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
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
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
5/89Transmission de l’Information : les codes convolutifs
I. Principe du codage convolutif
I. 2. Propriétés
Mot code : C = (X1
Y1
X2
Y2
… Xj 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 :
n
kR
km 1
Les codes convolutifs
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
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
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
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(s
jij
2i2
i1
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
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
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
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
1D0
DDDD1DH
22
x1(D)
x2(D)
x3(D)
s1(D)
s2(D)
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) …
...............
...............
...............
...
s
s
...1
1i
ijj
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
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
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.
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
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
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
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
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
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
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
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
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
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
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
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
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
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
10
11
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
31/89Transmission de l’Information : les codes convolutifs
00
00
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
10
11
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
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
10
11
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
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
10
11
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
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
10
11
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
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
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
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
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
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
40/89Transmission de l’Information : les codes convolutifs
II. Représentation des codes convolutifs
11
00
11
00
11
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
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
00
11
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
42/89Transmission de l’Information : les codes convolutifs
II. Représentation des codes convolutifs
La séquence d’information est ‘1001’
11
00
11
00
11
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
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
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
esx
eesex
j1j sx
DsDD1
DDsDx
DsDD1
DDe
Ds.DDe.DD1
DeDe.DDsDDe
DeDeDsDDe
DeDsDx
22
21
12
111
121
12
2
2
DD1
D11DH
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
DD1
D11DH
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
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
48/89Transmission de l’Information : les codes convolutifs
01
00
01
00
11
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
49/89Transmission de l’Information : les codes convolutifs
01
00
01
00
11
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’
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.
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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