INPTIC/IGE03
Théorie de l’information II
: Codes cycliques-codes
convolutionnels
Dr Djeddou Mustapha
Codes Polynômiaux et codes
Cycliques
Codes polynomiaux
• Un mot binaire a=a0a1….an-1 , ai{0,1} peut être représenté
sous forme d’un polynôme Pa:
a Pa(x)=a0+a1x+a2x2+…+an-1xn-1
Pa : polynôme de degré < n à coefficients dans F2={0,1}
L’ensemble de ces polynômes possède les propriétés
suivantes :
a. b = b.a commutatif
1 A, a.1 = 1.a = a unitaire
a.b = 0 a = 0 ou b = 0 intègre
3
Codes polynomiaux
• Sur cet ensemble de polynômes on peut effectués
plusieurs opérations:
• Addition :(1 + x + x2) + (x + x3) = 1+x + x2 + x3
• Multiplication (1 + x)2 = 1+x2.
• Division (x3 + x2 + x) = (x2 + 1)(x + 1) + 1.
Plus généralement, on peut diviser un polynôme p(x) par un
polynôme d(x). Il existe une décomposition unique en p(x) =
q(x)d(x) + r(x).
• Le code polynomiale d’ordre n généré par un polynôme
g(x) de degré m est le code constitué par l’ensemble de
mots associés aux polynômes de degré <n divisible par
g(x) (r(x)=0).
4
Codes polynomiaux
• Un codeur polynômiale opère comme suite:
a(x) codeur b(x)
g(x)
degré < m degré < n
degré r = n-m
g0 = 1
a(x) = a0 + a1x + … am-1xm-1 polynôme à coder
b(x) = b0 + b1x + …… bn-1xn-1 polynôme du code
g(x) = 1 + g1x + … xr polynôme générateur
b(x) = g(x).a(x)
5
Codes polynomiaux
• Exemple : on veux crée un code polynômiale (n=5,m=3) en
utilisent le polynôme générateur g(x)=1+x+x2. Le code sera
constitué des mots suivants :
0.g(x),1.g(x),x.g(x), (1+x).g(x), x2.g(x), (1+X2).g(x), (x2+x).g(x), (x2+x+1).g(x)
0 , x2+x+1, x3+x2+x, x3+1, x4+x3+x2, x4+x3+x+1, x4+x, x4+x2+1
Ceci donne la codification suivante :
Séquence source Polynôme Seq. Source Code Séquence Polynôme du code
000 0 00000 0
001 1 00111 x2+x+1
010 x 01110 x3+x2+x
011 1+x 01001 x3+1
100 x2 11100 x4+x3+x2
101 1+x2 11011 x4+x3+x+1
110 x+x2 10010 x4+x
111 1+x+x2 10101 x4+x2+1 6
Codes polynomiaux
• Tout code polynomial est linéaire
Preuve
g(x).(a(x) + a’(x)) = g(x).a(x) + g(x).a’(x)
• Tout code polynomial C (n,m) admet comme base
g(x), x g(x), x2 g(x),… xm-1 g(x)
Preuve
g(x), x.g(x), x2.g(x),… xk-1.g(x) linéairement indépendants
b(x)C:b(x) = a(x).g(x) =a0.g(x)+a1.x.g(x)+… am-1.xm-1.g(x)
b(x) est une combinaison linéaire de ces polynômes
7
Polynôme et matrice générateurs
• Un code polynômiale peut être représenté par une
matrice génératrice de la forme :
g ( x)
x.g ( x )
G x 2 .g ( x )
x m 1 .g ( x )
• Les lignes de G sont une base de C, le code n’est pas
systématique.
• Exemple 1 1 0 1 0 0
k=3 n=6
3 G 0 1 1 0 1 0
g(x) = 1 + x + x
0 0 1 1 0 1
8
Systématisation d’un code polynômiale
Théorème
G matrice génératrice d’un code polynomial
G’ G, G’ matrice génératrice systématique du même
code polynomial
Preuve
r = n-m
a(x) = a0 + … + am-1.xm-1 mot à coder
xr.a(x) = a0.xr + … + am-1.xn-1
t(x) = (xr.a(x)) mod g(x)
xr.a(x) = g(x).q(x) + t(x) degré(t(x)) < r
b(x) = xr.a(x) + t(x) = g(x).q(x)
9
Illustration de Systématisation
a(x) = a0 + … + am-1.xm-1 a0 ……………am-1
0 … 0 a0……………am-1
xr.a(x) = a0.xr + …+ am-1.xn-1
r
t0…tr-1
t(x) = xr.a(x) mod g(x)
t0…tr-1 a0……………am-1
b(x) = xr.a(x) + t(x)
10
Codage et décodage
Principe du codage
Le mot de code b(x) d'un code polynômial (n,m) de
polynôme générateur g(x) associé au mot initial a(x) est
défini par :
b(x) = a(x). xn-m + r(x), où r(x) est le reste de la division de
a(x).xn-m par le polynôme générateur g(x) (noté : r(x) =
(a(x).xn-m) mod g(x) ).
Remarques :
(i) Les r = n-m bits de r(x) (de degré =< n-m-1) forment les bits du
champ de contrôle.
(ii) Les bits de poids fort (de degré > n-m-1) forment le mot initial
(code systématique) .
(iii) L'opération de codage effectuée à l'émission est ramenée à une
division polynômiale.
11
Codage et décodage
Le codage se fait généralement en utilisent des circuits
électronique spécifiques (Registres à décalage), pour
effectuée la division polynômiale.
• Codage a(x) b(x)
– calcul de xr.a(x)
– calcul de t(x) = (xr.a(x)) mod g(x) degré < r
– b(x) = xr.a(x) + t(x)
12
Circuit de division
Circuit de division : exemple
Dr Djeddou M. 14
Codage et décodage
Principe du décodage
A la réception, chaque mot reçu b'(x) est divisé par le
polynôme générateur g(x).
Un reste non-nul indique qu'il y a eu erreur lors de la
transmission.
Syndrome de b'(x) : b'(x) mod g(x) ≠ 0 ==> Erreur !
Attention : la réciproque est fausse ! Si le reste est nul
cela ne veut pas dire qu'il n'y a pas eu d'erreurs.
15
Capacité de correction
Théorèmes
• C polynomial d (C) > 1
détecte toutes les erreurs de poids 1
• C (n,m) polynomial
Tout paquet d’erreur de longueur s ≤ n-m est détectable
• C polynomial générateur g(x) et g(x) multiple de (1+xk)
e(x), poids (e(x)) impair est détectable
• C polynomial générateur g(x) et (1+xk) n’est pas multiple
de g(x), 0 < k < n C détecte toutes les erreurs de
poids ≤ 2
16
Codes Cycliques
• Un code cyclique (n,m) est un code polynômial dont
le polynôme générateur divise xn + 1.
• Les dispositifs de codage et de décodage sont
identiques à ceux des codes polynômiaux.
• Les codes cycliques sont principalement utilisés pour
leur capacité de correction.
• Un code cyclique (n,m) est un code linéaire (n,m) tel
que toute permutation circulaire d'un mot du code
est encore un mot du code
17
Construction des Codes Cycliques
• Recherche d’un code cyclique C (n,m)
recherche des diviseurs de xn + 1
factorisation de xn + 1 extensions de F2
• Exemple :
x7+ 1 = (x + 1).(x3 + x + 1).(x3 + x 2 + 1)
g(x) = x3 + x + 1 et g’(x) = x3 + x 2 + 1
engendrent des codes de Hamming
• Codes polynomiaux normalisés
– UIT : x16 + x12 + x5 + 1
– Ethernet : x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 +
x 7 + x 5 + x 4 + x2 + x + 1
18
Codes convolutifs
Radio numérique
Téléphones mobiles
Bluetooth
Comm. Satellites
Dr Djeddou M. 19
Codes convolutifs
• Généralités
• Les symboles sont traités de manière continue (flux)
• k symboles d’informations en entrée et n symboles de sorties et n=x.k
• Les symboles de sorties dépendent des informations d’entrées
précédentes
k
n
Dr Djeddou M. 20
Codes convolutifs
• Codes convolutifs systématiques
• Mot de code :
C I1Y1I 2Y2 ....... I jY j .....
avec I j I1j...... I kj0 . Information
Y j Y j1......Y jm0 . Contrôle
• Codes convolutifs non systématiques
•Mot de code : CU1U2....... U j.....
Dr Djeddou M. 21
Codes convolutifs
•Codes convolutifs systématiques :
• Exemple : contrainte m=4, k=1, n=2
c n R4 .i n3 R3 .i R2 .i R1.i Avec R=[1011]
n2 n 1 n
Registre à décalage
In Cn
I = [10001]
z-1 z-2 z-3
R1=1 R2=0 R3=1 R4=1
Dr Djeddou M. 22
Codes convolutifs
• Codes convolutif non systématiques
• Exemple : m=3, k=1, n=2
Registre à décalage
U in in 2
n
2
z-1 z-2
Un2
U in in 1 in 2
1
n
Un1
1
R
2
2
Avec g2=[1 0 1]=5 et g1=[1 1 1]=7 Code (7,5)
U g ij .in j
i
n
j 0
Dr Djeddou M. 23
Codes convolutifs : non-récursifs,
récursifs
Non-récursif
En général, non systématique
z-1 z-2
Récursif En général, systématique
z-1 z-2
Dr Djeddou M. 24
Codes convolutifs
in in-1 in-2 n n+1 U1 n U2 n
• Codes convolutif non
systématiques : Machine d’états 0
1
0 0 A A
C
0
1
0
1
U n2 in in 2 0
1
0 1 B A
C
1
0
1
0
U n1 in in 1 in 2 0 1 0 C B 1 0
1 D 0 1
0 1 1 D B 0 1
1 D 1 0
Dr Djeddou M. 25
Analyse séquentielle
y
C B A
x
Remarque :
pas de changement de 00 à 11
changements sur un seul bit
Dr Djeddou M. 26
Analyse séquentielle : treillis
Présent -------------> Futur
BA -C--> CBA=(XY) next BA
-------------------------
00 -0--> 000=(00) ===> 00
00 -1--> 100=(11) ===> 10
-------------------------
01 -0--> 001=(11) ===> 00
01 -1--> 101=(00) ===> 10
-------------------------
10 -0--> 010=(10) ===> 01
10 -1--> 110=(01) ===> 11
-------------------------
11 -0--> 011=(01) ===> 01
Dr Djeddou M. 11 -1--> 111=(10) ===> 11 27
Exemple de codage
à transmettre : 100111011
BA -C--> CBA=(XY) next BA
00 -1--> 100=(11) ===> 10
10 -0--> 010=(10) ===> 01
01 -0--> 001=(11) ===> 00
00 -1--> 100=(11) ===> 10
10 -1--> 110=(01) ===> 11
11 -1--> 111=(10) ===> 11
11 -0--> 011=(01) ===> 01
01 -1--> 101=(00) ===> 10
10 -1--> 110=(01) ===> 11
--- vidange avec zeros à la fin
11 -0--> 011=(01) ===> 01
01 -0--> 001=(11) ===> 00
transmis : 11 10 11 11 01 10 01 00 01 01 11
Dr Djeddou M. 28
Exemple de codage 2
Bits d'entrée 1 0 1 1 1 0 1 1 0 0 0
Bits de sortie 11 10 11 11 01 10 01 00 01 01 11
Dr Djeddou M. 29
Codage
Bits de sortie 11 10 11 11 01 10 01 00 01 01 11
A la réception, on retrace le chemin.
La correction est possible puisqu'une erreur introduit une déviation dans ce chemin
Dr Djeddou M. 30
Algorithme de Viterbi
Le chemin le plus probable est celui qui est à distance minimale des
symboles reçus.
On suppose que chaque bit différent peut être corrigé
A chaque instant, le circuit de codage ne peut avoir que 4 états.
Chaque état ne peut conduire qu'à 2 autres états à l'instant suivant
Inversement, on ne peut arriver dans un état qu'à partir de 2 états.
Autrement dit, 2 chemins exactement conduisent à chacun des 4 états.
En général, un de ces 2 chemins aura la plus petite erreur jusqu'à ce point
dans le treillis.
En choisissant le 'meilleur chemin jusque là' et en passant à l'état suivant ,
le meilleur chemin complet est celui avec la plus petite erreur totale.
Dr Djeddou M. 31
Exemple
Dr Djeddou M. 32
Exemple
Dr Djeddou M. 33
Exemple
Dr Djeddou M. 34
