25/05/2021

Théorie d’information et codage de canal

Codes correcteurs d’erreurs

(2ème partie)
Codes linéaires en blocs
-Codes Cycliques-

Pr. A. AIT MADI

RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 1

Plan

Principe
Polynôme générateur
Matrice génératrice
Codage des codes cycliques
Circuits de codage
Circuits de décodage

RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 2

1
 25/05/2021

Principe

 Les codes cycliques sont des codes en blocs ou les n symboles, qui
constituent un mot, sont considérés comme coefficients d’un polynôme de
degré n-1:
vx   an1 x n1  an2 x n2  ...  a2 x 2  a1 x  a0
 Comme dans le cas des codes groupe, les n symboles d’un mot code peuvent
être représentés sous la forme d’une matrice ligne

v  an1an2 a2 a1 a0 

 Les codes cycliques n’ont cette propriété (c-à-d cycliques) que si v est un
mot code, alors toute permutation cyclique (rotation à gauche) des symboles
de v est un mot code :
 Exemple pour une seul rotation
v1 an2 an3 a0 an1 

RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 3

Principe

 Chaque permutation circulaire est équivalente à une multiplication par x. Pour

l’exemple précédent nous avons :

 
v1 x   x.vx mod px   an1 x n  an2 x n1  ...  a1 x 2  a0 x mod px 
 Le polynôme  
p x  x 1 n

 Nous effectuons la division euclidienne suivante :

an 1 x n  an  2 x n 1  ...  a1 x 2  a0 x x n  1
an 1 x n  an 1 an 1
an  2 x n 1  ...  a1 x 2  a0 x  an 1
 Le polynôme qui va correspondre à cette permutation circulaire sera donc :

 
x.vx mod x n  1 an2 x n1  ...  a1 x 2  ...  a0 x  an1
 Le mot code obtenu sera : v1 an2 ...a1a0 an1 
RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 4

2
 25/05/2021

Principe
 Exemple :
• soit le mot code suivant composé de n=5 bits
v 10101
• Quel est le mot code engendré après 3 permutations circulaires ?
• Le polynôme correspondant au mot code engendré après 3 permutations sera :
   
v1 x   x3 .vx mod x5  1  x3 . 1x 4  0 x3  1x 2  0 x  1 mod x5  1 
 
v1 x   x  x  x mod x  1
7 5 3
 5

• Après la division euclidienne nous aurons
x7  x5  x3 x5  1
x7  x2 x2 1 • Le mot code engendré sera :
x5  x3  x 2 v1 01101
x 1
5

x3  x 2  1
RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 5

Polynôme générateur

 Tout code linéaire C contient un mot code non nul, dont le polynôme est de degré
inférieur aux degrés des polynômes associés à tous les autres mots non nuls du
code.
• Cet élément est unique, car s’il y en avait deux, leur somme serait de degré
inférieur.
• Examinons la matrice génératrice suivante :

• Les lignes de G forment la base canonique du sous espace vectoriel des mots
code.

RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 6

3
 25/05/2021

Polynôme générateur

• Le polynôme de degré le plus faible de cette base correspond à la ligne

inférieure de la matrice G. Ce polynôme de degré r est le polynôme de plus
faible degré de tous mots code.

• Dans le cas d’un code cyclique, on appelle ce polynôme g(x) le polynôme

générateur du code.

g x   g r x r  g r 1 x r 1  ...  g1 x  g0

avec g r  g 0  1

g x   x r  g r 1 x r 1  ...  g1 x  1

RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 7

Matrice génératrice
• Le code étant cyclique, les permutations circulaires sur les bits du mot code
correspondant au polynôme générateur g(x), sont aussi des mots du code.
• Ainsi, les polynômes g(x), x.g(x), x2g(x), … , xk-1g(x) correspondent à k mots
linéairement indépendants de C, donc forment une base pour le sous espace des
mots de C.
• Par la suite, tout mot code est une combinaison linéaire de g(x), x.g(x), x2 g(x), …,
xk-1g(x) , donc est le produit d’un polynôme quelconque et de g(x).
• Autrement dit : tout mot code cyclique est multiple de g(x). Donc la matrice
génératrice du code sera de la forme :

RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 8

4
 25/05/2021

Matrice de Contrôle de parité

• Un mot code est le produit de g(x) par un polynôme quelconque modulo xn + 1 ;

autrement dit c’est un multiple de g(x).

• Une condition nécessaire et suffisante pour qu’un polynôme g(x) soit polynôme
générateur (de d° minimal) d’un code cyclique est qu’il divise p(x)= xn + 1.

• C.-à-d. qu’il y’aura un polynôme h(x) de façon que :

px   x n  1  g x hx 
• Il résulte de cette relation que le polynôme générateur g(x) doit être un diviseur du
polynôme p(x)
xn 1
h x  
g x 
• Dans ce cas le mot code C(x) généré sera :

    
C x   x n  1 mod x n  1  g x hx  mod x n  1  0 
RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 10

Matrice de Contrôle de parité

 Soit le code cyclique C (n, k) engendré par le polynôme g(x), et un mot code c de ce
code. Le polynôme c(x) est un multiple de g(x)

• Le polynôme c(x) est un multiple de g(x)

cx   f x g x 
• Comme g(x) divise p(x) on a :

 
g x hx   0 mod x n  1  cx hx   f x g x hx   0 mod x n  1  
• Donc le polynôme h(x) continue à jouer un rôle analogue à la matrice de contrôle H

hx cx   0  H .cT  0

RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 12

5
 25/05/2021

Matrice de Contrôle de parité

• On obtient une matrice génératrice du code dual d’un code cyclique, à partir du
polynôme h(x) de degré k pris comme polynôme générateur, mais dans lequel on a
inversé le sens des coefficients.

0  0 h0 h1  hk 
0  h h1  0 
H  0

   
 
h0  hk 1 hk 0  0

RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 13

Matrice de Contrôle de parité

• Exemple :

 Soit un Code C(7,4). A partir de la décomposition en facteurs irréductibles de

x7 + 1
  
x 7  1  x3  x 2  1 x3  x  1 x  1

 En prenant :
g x   x 3  x 2  1
 Alors :

 
hx   x3  x  1 x  1  x 4  x3  x 2  1

RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 14

6
 25/05/2021

Matrice de Contrôle de parité

 Alors :

hx   1  x 2  x3  x 4

1 1 0 1 0 0 0
0 0 0 1 0 1 1 1 
1 1 0 1 0 0
G H  0 1 0 1 1 1 0
0 0 1 1 0 1 0
  1 0 1 1 1 0 0
0 0 0 1 1 0 1

g x   x 3  x 2  1

RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 15

Codage non systématique des codes cycliques

 Cas d’un code cyclique non systématique :

• Le mot code v(x) est un multiple d’un polynôme générateur g(x)

vx   qx g x 
Où
q(x) est un polynôme de degré k-1
g(x) est le polynôme générateur de degré m=n-k=r

g x   g0  g1 x   g m1 x m1  x m
• Si
i  x   q x 
Où
i(x) est le polynôme des symboles d’information qu’on note

ix   im  im1 x    imk 1 x k 1

RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 16

7
 25/05/2021

Codage des codes cycliques

-Usage de l’idéal généré par g(x)-
• Après le codage le mot code v(x) obtenu est
vx   i.G  im g x   im1 xg x     imk 1 x k 1 g x 
• Le mot code v(x) se trouve dans l’espace ligne de la matrice génératrice G (k
lignes n colonnes) notée :

 g ( X )   g0 g1  g m 0  0
 Xg  X    0 g 0  g m 1 gm  0 
G 
        
 k 1   
 X g  X   0 0  0 g0  gm 
• On rappelle que l’espace ligne d’une matrice est formé par l’ensemble des
combinaisons linéaires des vecteurs ligne de la matrice.
• Les éléments des lignes sont les coefficients d’un polynôme de degré n-1 et les
coefficients des puissances de x absentes ont été remplacés par des zéros
• Ce calcul conduit à un mot code de n symboles ou les k symboles d’informations
n’apparaissent pas en clair
RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 17

Codage systématique des codes cycliques

 Cas d’un code cyclique systématique

• Pour obtenir un code systématique on procède comme suit :

• Soit c(x) le polynôme des symboles de contrôle

cx   c0  c1 x    cm1 x m1

• Avec les notations introduites, le mot code (où les symboles d’information
apparaissent en clair) peut s’écrire sous la forme :

vx   cx   x mix   qx g x 

• D’où
x mix   qx g x   cx 
• Le polynôme des symboles de contrôle c(x) représente le reste de la division du
polynôme des symboles d’informations multiplié par xm, par le polynôme g(x)
RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 18

8
 25/05/2021

Codage systématique des codes cycliques

• Le degré de c(x)<m et celui de g(x)=m, il s ’ensuit que :

x mi x 
cx   reste
g x 
• Compte tenu du fait :
vx   qx g x 
Avec :
qx   q0  q1 x    qk 1 x k 1
• On peut écrire

vx   q0 g x   q1 xg x     qk 1 x k 1 g x 

RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 19

Codage systématique des codes cycliques

• Comme dans le cas des codes non systématique, le mot code v(x) se
trouve dans l’espace ligne de la matrice génératrice du code

 g ( X )   g0 g1  g m 0  0
 Xg  X    0 g 0  g m 1 gm  0 
G 
        
 k 1   
 X g  X   0 0  0 g0  gm 
• Le codage avec cette matrice, comme dans le cas des codes groupe, se fait
conformément à la relation

v  iG  a0  a1 x    an1 x n1

RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 20

9
 25/05/2021

Circuit de Codage
-- Cas des codes systématiques--
 Circuit de division

• Le circuit emploie des bascules bistables Ci (i=0 à m-1), des multiplieurs

à constantes gi appartenant au CG(2) et des additionneurs modulo 2.
• Le circuit divise un polynôme quelconque appliqué à l’entrée:
U x   a n x n a n1 x n1    a0
• Par le polynôme
g x   g m x m  g m1 x m1    g0
• Le reste de la division R(x) étant stocké dans les cellules Ci du registre

RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 24

Circuit de Codage
-- Cas des codes systématiques--

• Les coefficients du polynôme U(x), à savoir anan-1…a0 , sont appliqués à l’entrée du

circuit de division dans l’ordre décroissant des indices
• Analyse de fonctionnement :

Nous voulons faire la division de anan-1 … an-m…a0 par gmgm-1…g0.

Toutes les cellules Ci étant initialement initialisées à zéro
Tous les coefficients du résultat quotient sont récupérés, via la sortie Y, après
n coups d’horloge (le premier au mème coup d’horloge et le dernier au nème coup
d’horloge ).
Le reste de la division est stocké dans les cellules Ci après n+1 coups d’horloges

RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 25

10
 25/05/2021

Circuit de Codage
-- Cas des codes systématiques--
• Pour l’analyse du fonctionnement du circuit on adopte la représentation suivante :

U x   a n D0 a n1 D    a0 D n
ou D est un opérateur de retardement qui représente un retard d’un coup d’horloge

• Dans cette relation D0=I représente l’opérateur de retardement nul, ce qui indique le
fait qu’a l’origine le symbole an se trouve à l’entrée de la cellule C0

• Le terme a0Dn indique le fait que le symbole arrive à l’entrée de la cellule C0 après n
coups d’horloge

• Calculons la fonction de transfert du circuit de la forme :

Y
T
U

RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 26

Circuit de Codage
-- Cas des codes systématiques--
• Pour la détermination de cette fonction, nous allons considérer le cas particulier où :

U x   g m D0  g m1 D    g0 D m
• Le premier symbole gm appliqué à l’entrée arrive, après m coups d’horloge, à la
cellule Cm-1 et donc il va apparaitre à la sortie avec un retardement Dm, de sorte que
le premier terme de la séquence Y sera:
Y  g m D m  D m avec g m  1
• Une fois le symbole gm arrivé à la sortie:
 Il est multiplié par les connexions de réaction, par les coefficients g0, g1,…,gm-1
 Et puis additionné modulo 2 au dernier symbole g0 de la séquence U qui se trouve
à l’entrée de la cellule C0
 Et au contenu des cellules C0, C1,…Cm-2, autrement dit aux symboles g1,…,gm-1
• Comme résultat de cette addition modulo 2, à l’entrée de toutes les cellules apparaitra
le symbole « 0 ».

RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 27

11
 25/05/2021

Circuit de Codage
-- Cas des codes systématiques--
• Au coup d’horloge suivant, m+1, tout le registre arrive à zéro et par conséquent Dm
sera le seul terme de la séquence Y :

Y  Dm
• La fonction de transfert du circuit sera donc :
Y Dm
T 
U g m D 0  g m1 D1    g 0 D m
• Ou bien
Y I
T 
U g m D  g m1 D m1    g 0 I
m
• D’où :

U
Y
gm D m
 g m1 D m1    g 0 I

RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 28

Circuit de Codage
-- Cas des codes systématiques--
• Dans cette relation, U peut être une séquence quelconques, laquelle peut s’écrire :


U x   D n a n D  n a n1 D n1    a0 I 
• En substituant D-1=x, il s’ensuit que le circuit fera la division du polynôme U(x) par le polynôme
g(x).
• Le quotient de la division sera obtenu à la sortie avec un retard de Dn, plus précisément après n
coups d’horloge
• Le reste apparaitra stocké dans le registre au coup d’horloge « n+1 »
• Dans le cas particulier ou U(x)=g(x), comme on l’a vu, au coup d’horloge n+1(n=m) le contenu
du registre sera nul, le reste R(x) étant également nul.

• Ce résultat peut être généralisé pour tout polynôme U(x)=q(x)g(x) divisible par g(x)
• Lorsque le polynôme U(x) est de degré n<m, il sera précisément le reste, et au coup d’horloge
n+1 il sera stocké dans le registre, ayant le coefficient de x0 dans la cellule C0

RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 29

12
 25/05/2021

Circuit de Codage
-- Cas des codes systématiques--

 1er coup d’horloge

C0  an , C1  0,, Cm1  0
 2ème coup d’horloge

C0  an1 , C1  an ,, Cm1  0

 3ème coup d’horloge
C0  an2 , C1  an1 , C2  an , Cm1  0
 mème coup d’horloge
C0  anm1 , C1  anm2 , C2  anm3 , Cm1  an  Y
 m+1ème coup d’horloge

C0  anm  g0 an , C1  anm1  g1an , C2  anm2  g 2 an , Cm1  an1  g m1an

RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 30

Circuit de Codage
-- cas des codes systématiques--

 Exemple : U= 11101 (n+1=5 éléments binaires) et g=1001 (m+1=4 éléments

binaires)
11101: 1001=11 et le reste est 110

 Après m=3 coups d’horloge

C0  1, C1  1, C2  1, Y  1,U  0
 Après m+1=4 coups d’horloge

C0  0 11  1, C1  1 1 0  1, C2  1 1 0  1  Y ,U  1

 Après n+1=5 coups d’horloge
C0  1 11  0, C1  1 1 0  1, C2  1 1 0  1
 Le résultat de la division de 11101 par 1001 est 11 alors que le reste est
110

RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 31

13
 25/05/2021

Circuit de Codage
-- Cas des codes systématiques--
 Codage par circuit de division

• A fin d’obtenir les coefficients du reste suivant dans les cellules bistables
x mi x 
cx   reste
g x 
• Il faut introduire i(x)=U(x) au point A comme le montre la figure
• Pour démontrer cette affirmation, supposons que le polynôme U(x)=1.
 Au premier coup d’horloge, les contenus des cellules bistables sera g0, g1,…gm-1 c’est le
résultat du reste de xm (introduit par l’entrée) par g(x)
 Le déplacement au point A équivaut à la multiplication par xm
 Il s’ensuit donc que l’introduction du polynôme i(x) à la sortie au point A donnera le reste C(x)

RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 32

Circuit de Codage
-- Cas des codes systématiques--
• Le circuit « n-k stage shift register encoding circuit » qui effectuera le codage sera
comme suit:

• Phase1 :
Introduction des k symboles d’informations, la porte P1 reste ouverte et le
circuit calcule le reste qui apparait dans les cellules bistables après k+1 coups
d’horloge, puis on ouvre la porte P2 et on ferme la porte P1.
• Phase 2
La porte P2 reste ouverte durant m coups d’horloge pour évacuer les m
symboles de contrôle qui seront placés à la suite des symboles d’informations pour
compléter le mot code
RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 33

14
 25/05/2021

Circuit de décodage
-- Cas des codes systématiques--
 Calcul des correcteurs

• Pour les codes linéaires en bloc systématiques, le correcteur est donné en

fonction du mot reçu v’ et la matrice de contrôle H sous la forme :
zT  v' H T
• Ou bien

z T  c' i' I nk PT 
T

ou c’ est la matrice ligne des symboles de contrôle réceptionnés et i’ est la matrice

des symboles d’informations réceptionnés

• Par transposition :
I 
z T  c' i ' n  k   c'i ' P   c'c"
 P 
ou c’’ représente la matrice ligne des symboles de contrôle obtenue par
l’opération de codage des symboles d’informations i’ réceptionnés.

RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 34

Circuit de décodage
-- Cas des codes systématiques--

• Les opérations nécessaires à la réalisation du circuit du correcteur sont données

par la figure suivante. On réduit le nombre d’opérations de multiplication
nécessaires pour calculer le correcteur directement avec la multiplication des
matrices.

RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 35

15
 25/05/2021

Circuit de décodage
-- Cas des codes systématiques--
 Décodage par circuit de division
• Le problème de décodage consiste à trouver une correspondance entre le mot
erroné réceptionné v’(x) et le mot (x) (erreurs introduites par le canal)

v '  x   v x     x 
• Si on réceptionne v’(x) on peut calculer (x), alors la correction se réalisera par
l’addition modulo 2
v x   v'  x     x 
• Le correcteur (Syndrome) Z(x) s’obtient par la sommation :
 des symboles de contrôle réceptionnés c’(x)
 des symboles de contrôle obtenus par le codage des symboles d’informations
réceptionnés
x i' x 
c" x   reste
m

 Le correcteur sera alors g x 

zx   c' x   c" x 
RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 36

Circuit de décodage
-- Cas des codes systématiques--

x m i' x 
• Ou bien
z x   c' x   reste
g x 
• Puisque le polynôme c’(x) est de degré inférieur m, on peut écrire :

c'  x   x m i '  x  v'  x 

z x   reste  z x   reste
g x  g x 

• Ou bien

 x 
z x   reste
g x 

RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 37

16
 25/05/2021

Circuit de décodage
-- Cas des codes systématiques--

• Le degré du polynôme z(x) est tout au plus m-1, et donc le nombre des correcteurs
sera 2m (il y a m termes).

 Il résulte que l’ensemble des configurations possibles d’erreurs, à savoir ɛ(x), au

nombre de 2n,

 On ne peut corriger que celles qui peuvent être mises en correspondance

biunivoque avec les correcteurs z(x) à savoir un nombre de 2m configurations
d’erreurs.

RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 38

Circuit de décodage
-- Cas des codes systématiques--
• De ce fait le procédé de décodage sera :

Calculer le correcteur z pour chaque mot réceptionné v’

Trouver le mot erreur correspondant au correcteur z
Additionner le mot erreur  et v’; on obtient ainsi v

• Le principe de décodage est représenté schématiquement par la figure

suivante :

V’ V

Calcul du z 
ROM
correcteur

• La ROM, adressée par le correcteur z, contient tous les mots erreurs  en

correspondance avec les correcteurs.

RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 39

17
 25/05/2021

Circuit de décodage
-- Cas des codes systématiques--

• Le circuit de décodage est donné par la figure suivante :

 Le décodage consiste à calculer le correcteur z, à l’aide du circuit de division

v'  x 
z x   reste
g x 
Pour la correction des erreurs, il faut vérifier si le correcteur n’est pas nul. Ce qui
s’obtient par la sortie de la porte OR laquelle égale =1 si le correcteur n’est pas
nul.

RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 40

Circuit de décodage
-- Cas des codes systématiques--

• Pour que l’on obtient un circuit de décodage identique à celui utilisé pour
le codage, on aura recours à la figure suivante :

• Dans ce cas, le reste est la sortie de la figure précédente z multiplié par xm

ce qui n’a pas d’importance si on envisage uniquement la détection des
erreurs

RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 42

18
 25/05/2021

Références

• « Mathématiques autour de la cryptographie »,

[Link]

• Fondements de la théorie de la transmission de l’information , Alexandru Spataru,

Presses Polytechniques Romandes

RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 43

Annexes

RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 44

19
 25/05/2021

Rappels Mathématiques

 Soit K[x] l’ensemble des polynômes défini sur un corps K (poly. dont les
coefficients sont les éléments d'un corps K).

 K[x] est structuré en anneau par les lois d’addition et de multiplication des
polynômes.

 L’ensemble K[x]/(xn + 1) des restes de la division des polynômes par xn + 1 est

aussi un anneau, où la multiplication des polynômes se sous-entend modulo xn + 1.

 Un mot code v(x) est un multiple du polynôme g(x), donc le code cyclique est un
idéal de l’anneau K[x]/(xn + 1). Et réciproquement, tout idéal de K[x] /(xn + 1)
est un code cyclique.

 Lorsque tous les éléments d’un idéal sont des multiples d’un même élément, ont
dit que l’idéal est principal. Dans notre cas, tous les idéaux de l’anneau K[x] /(xn +
1) sont principal

RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 45

Rappels Mathématiques

• Une classe résiduelle, Cr(X), est l’ensemble des polynômes des multiples A(X) du
polynôme p(X) sachant que Cr(X) est le reste de la division euclidienne :
A X 
p X 
• Si on prend p(X)=A(X) alors le reste de la division euclidienne sera :
 p X    0 
Reste   Reste   0  p X   0
 p X    p X  
• Donc p(X) se trouve, comme premier élément , dans la première classe résiduelle 0.

• La première classe résiduelle 0 est formée par l’idéal généré par le polynôme
p(X) à savoir l’ensemble des multiples de p(X).

RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 46

20
 25/05/2021

RST(S9)-ENSA -KENITRA
RST(S8)-ENSA 47

21