codes detecteurs et correcteurs d'erreurs de transmission - Td corrigé
et en déduit Rcorrigé = (0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0) par inversion des bits.
identifiés par .... Le bloc A est obtenu en calculant le produit scalaire (ET logique
et ) : A = M G ...... III.9.3.2 ) Décodage du code cyclique (341,331) du système
RDS.
part of the document
réémet le même symbole jusqu'à recevoir un ACK.
Continous ARQ : l'algorithme est identique mais le transmetteur n'attend pas ce qui permet de gagner du temps. Les contrôleurs de communication sont, par contre, plus complexes.
FEC : Forward Error Control. La détection et la correction des erreurs sont réalisées à la réception en utilisant les éléments de protection introduits à l'émission. Cette technique de protection est utilisée s'il n'y a pas de canal de retour.
I.2 ) Les erreurs de transmission
Les imperfections du canal de transmission entraînent des perturbations aléatoires :
disparition de bit
adjonction de bit
inversion de bit
Les deux premières sont facilement détectables mais non corrigibles.
La troisième n'est détectable et corrigible que grâce aux codes de protection, objets de ce document.
I.2.1 ) Distribution des erreurs
Les altérations peuvent être classées en 2 types :
indépendance totale des erreurs : le canal de transmission est qualifié de "Voie Binaire Symétrique" ou Binary Symetric Channel (BSC)
erreurs groupées ou "paquets d'erreurs" : une suite de bits plus ou moins longue est altérée.
Les quelques rares calculs statistiques proposés dans ce document ne traiteront que de la voie binaire symétrique.
I.2.1 ) Voie binaire symétrique
q : probabilité de recevoir le même état que celui transmis.
p : probabilité de recevoir un état opposé à celui transmis.
p = 1 - q
q = 1 - p
La voie binaire est dite "symétrique" car les probabilités de recevoir le même état ou un état opposé ne dépendent pas de l'état des bits.
La probabilité p caractérise le bruit sur la voie de transmission.
Si on transmet un bloc de n bits, la probabilité de le recevoir avec "d" erreurs est :
Pd = pd ( qn-d
Sans erreur :
PC = qn = (1 - p)n
Au moins une erreur :
PE = 1 - PC = 1- (1 - p)n ( 1 - (1-n ( p) = n ( p
I.3 ) Notions de codes redondants
Chaque symbole de l'information à transmettre est codé sur k bits. Le codage de protection ajoute des éléments à chaque symbole pour permettre la détection et/ou la correction, à la réception, des erreurs de transmission.
Les symboles protégés sont nommés blocs et ont une longueur de n bits.
Deux types de codes sont utilisés :
codes en bloc : la loi de codage est combinatoire
codes convolutionnels : la loi de codage est séquentielle. Ce type de code ne sera pas traité dans ce document.
Pour un code en bloc :
nombre de symboles maximums possible : 2k
nombre de symboles protégés (blocs) en sortie du codeur : 2k (loi combinatoire)
nombre de blocs possibles : 2n
Exemple : code de protection RDS :
k = 16 ( l'ensemble des blocs du code comporte 65536 éléments
n = 26 ( l'ensemble Cn comporte 67108864 éléments
On constate la grande redondance du code : l'ensemble Cun est 1024 fois plus petit que Cn
Cette redondance permet au récepteur de détecter, voire corriger, les erreurs de transmission.
I.4 ) Formats des blocs des codes de protection
Pour faciliter, à la réception, l'extraction des symboles dans les blocs reçus, la plupart des codes de protection placent dans chaque bloc le symbole associé non modifié. Deux formats sont utilisés :
format systématique : bloc AAAAAAA AAAAAAA(A A AA sur n bits
Info utile (symbole) Info de contrôle
sur k bits sur (n - k) bits
format non systématique : les bits d'info utile et de contrôle ne sont pas groupés.
Le format systématique est généralement préféré car plus simple à traiter.
Si on veut protéger l'information transmise contre le piratage, les codes correcteurs d'erreur peuvent être conçus de façon à cripter l'information utile. Mais ceci entraîne généralement une dégradation des performances en détection et correction d'erreur. On préfère ajouter la fonction de criptage en amont du codeur de protection contre les erreurs de transmission.
I.5 Exemples de codes protecteurs
I.5.1 ) Contrôle 2 sur 3
Le même symbole est transmis trois fois de suite. Un bloc du code est donc constitué de trois groupes de k bits et a une longueur de 3(k bits. A la réception, les cas suivants peuvent de présenter :
les 3 groupes du bloc reçu sont identiques ( il est fort probable que le symbole reçu est celui qui a été transmis.
2 groupes sont identiques, le 3° est différent ( il est probable que le symbole transmis soit celui associé aux 2 groupes identiques.
les 3 groupes sont différents : les erreurs sont détectées mais la correction est impossible.
Ainsi, suivant le nombre d'erreurs, le code est autocorrecteur (une seule erreur) ou simplement autovérificateur (plus d'une erreur).
I.5.2 ) Contrôle de parité
Schéma
Les générateurs de parité de l'émetteur et du récepteur sont identiques. Le bit de parité calculé à l'émission est ajouté au symbole pour constituer le bloc du code transmis. Le bit de parité calculé à la réception est comparé au bit de parité inclus dans le bloc reçu. Si les 2 états sont identiques, il est probable, mais pas sûr, qu'il n'y a pas d'erreur de transmission. Dans le cas contraire, il y a au moins une erreur.
I.6) Codes détecteurs d'erreurs
Par convention, l'émetteur n'envoie que des blocs appartenant au code. Les éventuelles erreurs de transmission font que le récepteur peut recevoir un bloc différent de celui émis. Dans ce cas :
si le bloc n'appartient pas à l'ensemble Cun du code ( détection d'au moins 1 erreur
si le bloc appartient au code, il est fort probable qu'il n'y a pas d'erreur de transmission. Cette probabilité est d'autant plus forte que le sous-ensemble Cun est petit devant Cn.
En effet, si on transmet le bloc A (donc appartenant à Cun), qu'il y a des erreurs de transmission et que l'on reçoit le bloc R, il est fort probable que R soit extérieur au sous-ensemble Cun à cause de sa taille par rapport à Cu.
I.7) Codes détecteurs et correcteurs d'erreurs
L'émetteur transmet le bloc A, mais le récepteur reçoit le bloc A' à cause d'erreurs de transmission. A un autre moment, l'émetteur envoie A1 et le récepteur reçoit A1'.
la correction des erreurs est possible si A' ne peut être obtenu qu'à partir du bloc du code A. L'implication est alors bidirectionnelle et le récepteur peut décider que le bloc transmis est A, alors qu'il a reçu A'.
Cette implication bidirectionnelle n'est possible que si le nombre d'erreurs est limité. En effet, avec beaucoup d'erreurs, le bloc peut se transformer en bloc A1' à la réception, et le récepteur décidera que c'est A1 qui a été transmis, ce qui est faux. La correction est mise en défaut.
la détection des erreurs reste possible tant que le nombre d'erreurs ne transforme pas le bloc transmis en un autre bloc du code (on transmet A et on reçoit A1, le récepteur ne peut pas détecter l'erreur).
I.8 ) Notion de voisinage - Poids et distance de Hamming
I.8.1 ) Vecteur d'erreur
Si A est le bloc émis et R le bloc reçu, le vecteur d'erreur E est :
E = A ( R
L'opérateur ( signifie "Ou exclusif bit à bit"
Le vecteur d'erreur E comporte autant de bits que les blocs A et R. Les positions des bits de E à "1" indiquent les positions des bits en erreur dans R.
La fonction du décodeur à la réception est de calculer la valeur la plus probable de E en fonction de R pour en déduire le bloc corrigé : Rcorrigé = R ( E.
Cette opération inverse l'état des bits en erreur et réalise ainsi la correction du bloc reçu.
Exemple : l'émetteur transmet A = (0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0)
le récepteur reçoit R = (0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0)
il calcule alors E = (0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0) s'il est capable de corriger 2
erreurs
et en déduit Rcorrigé = (0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0) par inversion des bits
identifiés par E
I.8.2 ) Poids de Hamming
Le poids de Hamming d'un bloc du code est le nombre d'états "1" dans ce bloc.
I.8.3 ) Distance de Hamming
La distance de Hamming entre 2 blocs du code est le nombre de bits différents entre ces 2 blocs.
La distance de Hamming minimum (notée dmin) est la plus petite distance de Hamming de toutes les paires de blocs du code possibles.
I.8.4 ) Notion de voisinage
La notion de voisinage définit les règles élémentaires de détection et de correction des erreurs de transmission.
Le bloc A appartient au sous-ensemble de codage Cun. Le voisinage de ce bloc est constitué des blocs de l'ensemble Cn ayant une distance de Hamming par rapport à A inférieure ou égale à d.
I.8.5 ) Principe de la correction
Soient A et B deux blocs appartenant au sous-ensemble de codage Cun. On peut définir un voisinage pour chacun de ces blocs :
Les voisinages représentés ci-dessus sont définis à la distance de Hamming minimum dmin. Lorsqu'ils se croisent, il existe des blocs communs aux 2 voisinages. La correction est impossible. En effet, si le récepteur reçoit le bloc C', il est incapable de décider quel est le bloc transmis, A ou B, car C' appartient aux 2 voisinages.
Par contre, si les voisinages des blocs A et B sont distincts, comme représentés ci-dessous, la correction devient possible.
Les voisinages représentés ci-dessus sont définis par la distance de Hamming tmin. Pour que ces voisinages soient distincts et donc permettre la correction des erreurs, la distance tmin doit être telle que :
2 ( tmin ( dmin
Si cette inégalité est respectée, le récepteur sera capable de :
corriger tmin erreurs simultanées,
détecter (dmin - 1) erreurs simultanées.
I.9 Exemple
Les symboles à transmettre ont une longueur k = 1 bit. Les blocs du code de protection associés ont une longueur n de 4 bits et sont (0,0,0,0) pour le symbole "0" et (1,1,1,1) pour le symbole "1".
La distance de Hamming minimum vaut donc dmin = 4. On en déduit tmin = 1. Ce codage est donc capable de :
corriger 1 erreur
détecter 3 erreurs
I.10 ) Capacités de la détection et de la correction des erreurs
Notation : le code de protection (n, k) produit des blocs de n bits à partir de symboles de k bits en ajoutant (n-k) bits de contrôle.
I.10.1 ) Capacité de détection
La fonction de détection est mise en défaut si, au cours de la transmission, un bloc du code se transforme en un autre bloc du code.
La probabilité que cela se produit est : PD = pdmin ( qn-dmin ( pdmin
En effet, dmin représente le nombre minimum de bits différents entre 2 blocs du code. Donc si dmin bits sont altérés au cours de la transmission, le bloc reçu peut faire partie du code.
Exemple : code de Hamming (7,4). Il est caractérisé par dmin = 3 et tmin = 1.
Si le canal de transmission est caractérisé par p = 10-2 (1 bit sur 100 inversé) :
( PD = 10-6
La probabilité de mettre la détection d'erreur en défaut est de 1 bit sur 1 million.
I.10.1 ) Capacité de correction
La fonction de correction est mise en défaut si le nombre d'erreurs au cours de la transmission est supérieur à tmin.
La probabilité que cela se produit est : PC = ptmin+1 ( qn-(tmin+1) ( ptmin+1
Exemple : code de Hamming (7,4). Il est caractérisé par dmin = 3 et tmin = 1.
Si le canal de transmission est caractérisé par p = 10-2 (1 bit sur 100 inversé) :
( Pc = 10-4
La probabilité de mettre la correction d'erreur en défaut est de 1 bit sur 10000.
II ) Codes linéaires
II.1 ) Généralités
Notations :
Code linéaire (n, k)
k = nombre de bits de chaque symbole
n = longueur des blocs du code
le codeur ajoute donc (n-k) bits de contrôle (ou redondants)
V = k/n : vitesse du code
Schéma :
II.2) Définitions
Le code est dit "linéaire (n, k)" si la somme modulo 2 bit à bit (opérateur () de deux blocs du code donne un autre bloc du code.
Note : le bloc (0,0,0,0,
,0) fait partie de tous les codes linéaires car il est le résultat de la somme d'un bloc du code avec lui-même.
Les codes linéaires utilisent le format systématique.
II.3 ) Codeur
La matrice de codage G défini entièrement le codeur linéaire (n, k) largeur = n, hauteur = k :
Sous-matrice diagonale (k)Sous-matrice de parité P (n-k, k)10
00pk-1,n-k-1pk-1,n-k-2
pk-1,1pk-1,001
00pk-2,n-k-1pk-2,n-k-2
pk-2,1pk-2,000
00pk-3,n-k-1pk-3,n-k-2
pk-3,1pk-3,0G =
00
00
00p2,n-k-1p2,n-k-2
p2,1p2,000
10p1,n-k-1p1,n-k-2
p1,1p1,000
01p0,n-k-1p0,n-k-2
p0,1p0,0
On y reconnaît :
une sous-matrice diagonale de dimension k
une sous-matrice de parité (coef. pi,j) de hauteur k et de largeur (n-k)
Le bloc A est obtenu en calculant le produit scalaire (ET logique et () :
A = M ( G
En notant :
M = (mk-1, mk-2,
, m1, m0),
A = (an-1, an-2,
, a1, a0).
On en déduit :
an-1 = mk-1
an-2 = mk-2
an-k+1 = m1
an-k = m0
an-k-1 = mk-1(pk-1,n-k-1 ( mk-2(pk-2,n-k-1 (
( m1(p1,n-k-1 ( m0(p0,n-k-1
an-k-2 = mk-1(pk-1,n-k-2 ( mk-2(pk-2,n-k-2 (
( m1(p1,n-k-2 ( m0(p0,n-k-2
a1 = mk-1(pk-1,1 ( mk-2(pk-2,1 (
( m1(p1,1 ( m0(p0,1
a0 = mk-1(pk-1,0 ( mk-2(pk-2,0 (
( m1(p1,0 ( m0(p0,0
On constate donc que :
les k premiers bits du bloc A représentent la copie du symbole M (an-1 à an-k)
les (n-k) derniers bits du bloc A sont les bits de contrôle (an-k-1 à a0)
C'est bien un format systématique.
Exemple : matrice génératrice du code linéaire de Hamming (7,4) :
INCORPORER Equation.3
Soit M = (m3, m2, m1, m0) le symbole à encoder
On en déduit :
a6 = m3
a5 = m2
a4 = m1
a3 = m0
a2 = m3 ( m2 ( m0
a1 = m3 ( m1 ( m0
a0 = m2 ( m1 ( m0
Si M = (1, 0, 1, 1) ( A = (1, 0 , 1, 1, 0, 1, 0)
II.4 ) Décodeur
Il n'y a pas de décodage du symbole à proprement parlé puisqu'il se trouve non modifié dans le bloc reçu. La fonction du décodeur est de détecter et éventuellement identifier les bits altérés au cours de la transmission.
Pour ce faire, on calcule le syndrome S, résultat du produit scalaire entre le bloc reçu (R) et la transformée de la matrice de vérification H (hauteur = n - k, largeur = n) :
S = R ( HT
Sous-matrice de parité PT (k, n-k)Sous-matrice diagonale (n-k)pk-1,n-k-1pk-2,n-k-1
p1,n-k-1p0,n-k-110
00pk-1,n-k-2pk-2,n-k-2
p1,n-k-2p0,n-k-201
00
H =
pk-1,1pk-2,1
p1,1p0,100
10pk-1,0pk-2,0
p1,0p0,000
01
La sous-matrice de parité PT de la matrice H est la transposée de la sous-matrice P de la matrice G, de telle façon que : G(HT = [0]k,n-k
En notant :
R = (rn-1,
, r1, r0), les n bits du bloc reçu et
S = (sn-k-1,
, s1, s0), les (n-k) bits du syndrome,
On en déduit :
sn-k-1 = (rn-1(pk-1,n-k-1 (
( rn-k+1(p1,n-k-1 ( rn-k(p0,n-k-1) ( rn-k-1
s1 = (rn-1(pk-1,1 (
( rn-k+1(p1,1 ( rn-k(p0,1) ( r1
s0 = (rn-1(pk-1,0 (
( rn-k+1(p1,0 ( rn-k(p0,0) ( r0
S'il n'y a aucune erreur au cours de la transmission, les blocs émis (A) et reçu (R ) sont identiques, soit rn-1 = an-1 = mk-1 ,
, an-k+1 = rn-k+1 = m1 , rn-k = an-k = m0 , rn-k-1 = an-k-1 ,
, r1 = a1, r0 = a0 et on en déduit :
(rn-1(pk-1,n-k-1 (
( rn-k+1(p1,n-k-1 ( rn-k(p0,n-k-1)
= mk-1(pk-1,n-k-1 (
( m1(p1,n-k-1 ( m0(p0,n-k-1 = an-k-1 = rn-k-1
(rn-1(pk-1,1 (
( r1(p1,1 ( r0(p0,1) = (mk-1(pk-1,1 (
( m1(p1,1 ( m0(p0,1) = a1 = r1
(rn-1(pk-1,0 (
( r1(p1,0 ( r0(p0,0) = (mk-1(pk-1,0 (
( m1(p1,0 ( m0(p0,0) = a0 = r0
Ce qui donne le syndrome suivant : S = (sn-k-1,
, s1, s0) = (0, 0, 0, 0,
, 0, 0)
Conclusion : si tous les bits du syndrome S sont à zéro, on peut en déduire qu'il est très fortement probable qu'il n'y a pas d'erreur de transmission.
En fait, chaque bit si du syndrome S est le résultat de la comparaison entre :
le bit de parité ai calculé à l'émission sur certains bits de l'information utile, et reçu sous l'indentificateur ri. L'indice i correspond à une des colonnes de la sous-matrice diagonale de H, soit i compris entre (n-k-1) et 0.
le bit de parité calculé à la réception sur les mêmes bits d'information utile reçus.
S'il n'y a aucune erreur, les 2 bits de parité ont le même état et si = "0". Dans le cas contraire, si = "1", ce qui signifie qu'il y a une altération sur l'un des bits contrôlés.
Exemple : La matrice de décodage (ou de vérification) H du code de Hamming (7,4) est
L'émetteur transmet le bloc A = (1, 0 , 1, 1, 0, 1, 0)
Le récepteur reçoit le bloc R = (1, 0 , 1, 1, 0, 1, 0) , donc sans erreur.
Le produit scalaire S = R ( HT donne :
s2 = (1(1 ( 1(0 ( 0(1 ( 1(1) ( 1(0 ( 0(1 ( 0(0 = 0
Calcul de parité sur Bit de parité entre m3, m2, m1 et m0 calculé
m3, m2, m1 et m0 reçus = 0 à l'émission et reçu sans erreur
s1 = (1(1 ( 0(0 ( 1(1 ( 1(1) ( 0(0 ( 1(1 ( 0(0 = 0
s0 = (0(1 ( 1(0 ( 1(1 ( 1(1) ( 0(0 ( 0(1 ( 1(0 = 0
Si maintenant le récepteur reçoit R = (1, 0 , 0, 1, 0, 1, 0) le bit r4 étant inversé, le produit scalaire S = R ( H donne :
s2 = (1(1 ( 1(0 ( 0(0 ( 1(1) ( 1(0 ( 0(1 ( 0(0 = 0
s1 = (1(1 ( 0(0 ( 1(0 ( 1(1) ( 0(0 ( 1(1 ( 0(0 = 1
s0 = (0(1 ( 1(0 ( 1(0 ( 1(1) ( 0(0 ( 0(1 ( 1(0 = 1
Soit S10 (équivalent décimal de S) = 3. Cette valeur permettra au décodeur d'identifier la position 4 pour corriger r4 (c'est à dire inverser son état).
On peut remarquer que les états de s2, s1 et s0 correspondent à la colonne d'indice 4 de la matrice H. Ce n'est pas un hasard !
II.5 ) Décodage des codes linéaires
Il s'agit d'étudier la manière d'utiliser le syndrome S pour évaluer la valeur la plus probable du vecteur d'erreur E.
Rappels : A = (an-1, an-2,
, a1, a0) est le bloc émis,
R = (rn-1, rn-2,
, r1, r0) est le bloc reçu,
E = (en-1, en-2,
, e1, e0) est le vecteur d'erreur.
Par définition : E = A ( R
On en déduit : R = A ( E
Le syndrome est : S = R ( HT = (A ( E) ( HT = (A ( HT) ( (E ( HT)
Or, par définition : A ( HT = 0 car A est un bloc du code et le produit scalaire avec la matrice de
vérification est toujours nul.
On en déduit : S = E ( HT
Le syndrome est le résultat du produit scalaire du bloc reçu R avec HT, mais c'est aussi, comme le montre la relation ci-dessus, le résultat du produit scalaire du vecteur E avec la transposée de la matrice de vérification.
En utilisant le contenu de la matrice H, on obtient :
sn-k-1 = en-1(pk-1,n-k-1 (
( en-k+1(p1,n-k-1 ( en-k(p0,n-k-1 ( en-k-1
s1 = en-1(pk-1,1 (
( en-k+1(p1,1 ( en-k(p0,1
( e1
s0 = en-1(pk-1,0 (
( en-k+1(p1,0 ( en-k(p0,0 ( e0
On constate que les états des bits du syndrome sont chacun une combinaison linéaire des bits d'erreur.
En conséquence, le syndrome contient une information sur les positions (les indices) des bits altérés.
Si on se contente d'une capacité de correction d'une seule erreur (un seul des bits de E est à "1"), un simple décodeur combinatoire permet d'identifier la position en erreur, et donc de déterminer la valeur du vecteur d'erreur E.
Schéma du détecteur/correcteur d'erreur
Le contenu de la matrice H peut maintenant être complètement défini :
Si on admet qu'il y a qu'une seule erreur dans le bloc reçu, le syndrome obtenu correspond à la colonne d'indice du bit altéré de la matrice H. Pour permettre l'identification de cet indice à partir de S, il suffit de choisir les états de la matrice de parité de manière à ce que les valeurs de S10 soient uniques. Les valeurs en puissance entières de 2 sont réservées par la matrice diagonale, les autres valeurs peuvent être choisies de manière quelconque.
II.6 ) Codes de Hamming corrigeant une erreur
Dans ce cas, le vecteur d'erreur obtenu après décodage aura au maximum une composante non nulle.
Puisque le syndrome S de (n-k) positions (nombre de bits redondants) doit permettre d'indiquer, soit l'absence d'erreur, soit la position altérée dans le bloc reçu, la valeur (n-k) de bits de contrôle doit respecter l'inégalité :
2n-k - 1 ( n
On en déduit le tableau suivant :
Nombres de positions de contrôlen-k2345678
Nombre maximum de positions dans le blocn =
2n-k - 137153163127255
Nombre maximum de bits d'information utilek14112657120
II.7 ) Exercice
Etude du code linéaire de Hamming (15,11)
Le code est capable de corriger une erreur. Quelle est sa capacité de détection d'erreur ?
En déduire sa distance de Hamming minimum.
Proposer le contenu de la matrice de vérification H. En déduire le contenu de la matrice génératrice G.
Proposer le schéma logique du codeur (entrée M sur 11 bits, sortie A sur 15 bits).
Proposer le schéma logique du décodeur (entrée R sur 15 bits, sortie corrigée sur 11 bits)
III ) Codes cycliques
III.1 ) Définitions
Un code linéaire est dit cyclique si une transposition circulaire à droite ou à gauche d'un bloc du code donne un autre bloc du code.
Ainsi si A(0) = (a0, a1,
, an-1) est un bloc du code
alors A(1) = (an-1, a0, a1,
, an-2) est aussi un bloc du code.
Les codes cycliques sont intéressants sur plusieurs points :
l'encodage à l'émission et le calcul du vecteur d'erreur à la réception sont facilement réalisables sous les formes logicielle ou matérielle,
ils sont capables de corriger les paquets d'erreurs. Un paquet d'erreurs de longueur L est une succession de L bits, corrects ou faux, le premier et le dernier étant toujours erronés.
III.2 ) Représentations
Le symbole M à protéger est représenté sous une forme polynomiale :
M(X) = mk-1(Xk-1 +
+ m1(X1 + m0(X0
Le polynôme associé au bloc du code A = (a0, a1,
, an-1) s'écrit :
A(X) = an-1(Xn-1 +
+ a1(X1 + a0(X0
A(X) est un bloc polynomial.
Notes : l'opérateur + est en fait l'opérateur (. Il n'a pas été utilisé pour améliorer la lisibilité.
l'opérateur ( est le ET logique.
III.3 ) Polynôme générateur
Les codes cycliques (n,k) sont entièrement définis par un polynôme générateur G(X) ayant la forme générale suivante :
G(X) = Xn-k + gn-k-1(Xn-k-1 +
+ g1(X1 + 1
G(X) doit posséder les propriétés suivantes :
non nul ce qui justifie le dernier terme (g0 = 1),
de degré (n-k), ce qui justifie le premier terme (gn-k = 1),
facteur de (Xn + 1),
premier.
Note : Les méthodes d'élaboration des polynômes générateurs sortent du domaine d'étude de ce document.
III.4 ) Définition de l'encodage
Chaque bloc du code est un multiple polynomial de G(X) : A(X) = f(X) ( G(X)
III.4.1 ) Encodage simple
Dans ce cas : f(X) = M(X)
Le bloc polynomial A(X) associé au symbole M est le résultat du produit polynomial de M(X) par G(X) :
A(X) = M(X) ( G(X)
Exemple : si on respecte cette définition mathématique, on peut calculer tous les blocs du code cyclique (7,4) défini par le polynôme générateur G(X) = X3 + X1 + 1 :
SymbolesBlocs du codem3m2m1m0a6a5a4a3a2a1a00000000000000010001011001000101100011001110101000101100010101001110110011101001110110001100010110001001101010111100110111101111
Exemples de calculs :
M(X) = 0 ( A(X) = M(X) ( G(X) = 0
M(X) = X2 + X ( A(X) = M(X) ( G(X) = X5 + X2 + X4 + X2 + X3 + X5
A(X) = X5 + X4 + X3 + X1 soit A = (0, 1, 1, 1, 0, 1, 0)
De ce tableau, on déduit dmin = 3 car, hormis le premier bloc, il y au moins 3 positions à 1 dans les autres blocs. Le code est donc capable de corriger 1 erreur et d'en détecter 2.
Cette méthode de codage n'est pas utilisée car le format obtenu n'est pas systématique (symboles non apparents dans les blocs du code).
III.4.2 ) Encodage des codes cycliques
Le polynôme f(X) est élaboré pour obtenir des blocs au format systématique.
Le symbole à encoder est M = (mk-1,
, m1, m0).
Le symbole polynomial correspondant est : M(X) = mk-1(Xk-1 +
+ m1(X1 + m0(X0
On multiple M(X) par Xn-k : Xn-k ( M(X) = mk-1(Xn-1 +
+ m1(Xn-k-1 + m0(Xn-k
C'est un polynôme de degré inférieur ou égal à (n-1).
Si maintenant on divise Xn-k ( M(X) par G(X), on obtient :
Xn-k ( M(X) = Q(X) ( G(X) + ((X)
avec : Q(X) : quotient de la division. Degré ( n-1-(n-k) = k-1
((X) : reste de la division. Degré ( (n-k-1)
Comme le degré de G(X) est (n-k), le degré de ((X) est nécessairement inférieur ou égal à
(n-k-1). En effet, le reste d'une division est toujours de degré inférieur au diviseur.
Soit : ((X) = (n-k-1(Xn-k-1 +
+ (1(X1 + (0
Le + de la relation (1) ci-dessus signifie en fait ( (ou exclusif sur les bits de même poids). Cette égalité peut alors s'écrire :
Xn-k ( M(X) + ((X) = Q(X) ( G(X)
Cette relation indique que " Xn-k ( M(X) + ((X) " est un multiple de G(X) et est de degré inférieur ou égal à (n-1).
Ainsi " Xn-k ( M(X) + ((X) " est le bloc polynomial A(X) associé au symbole M(X).
En développant " Xn-k ( M(X) + ((X) " , on obtient :
Xn-k ( M(X) + ((X) = mk-1(Xn-1 +
+ m1(Xn-k+1 + m0(Xn-k + (n-k-1(Xn-k-1 +
+ (1(X1 + (0
qui correspond au bloc du code : A = ( mk-1 ,
, m1 , m0 , (n-k-1 ,
, (1 , (0 )
k bits du symbole (n-k) bits de contrôle
On reconnaît un format systématique. Les (n-k) bits de contrôle sont les coefficients de ((X)
En résumé, le codage consiste en 3 étapes :
Multiplier le symbole M(X) par Xn-k. On obtient ainsi les k premiers bits du bloc du code A,
Calculer le reste ((X) de la division de Xn-k ( M(X) par G(X). On obtient ainsi les (n - k) bits de contrôle,
Concaténer Xn-k ( M(X) et ((X) pour obtenir les n bits du bloc du code A associé au symbole.
Exemple
Soit un code cyclique (7,4) défini par G(X) = X3 + X1 + 1
Le symbole à encoder s'écrit : M(X) = m3(X3 + m2(X2 + m1(X1 + m0(X0
Les blocs du code sont obtenus en calculant le reste ((X) de la division de X3(M(X) par G(X) :
A(X) = X3 ( M(X) + ((X)
Le tableau ci-dessous donne tous les blocs du code :
SymbolesXn-k ( M(X)ResteBlocs du codem3m2m1m0X3(M(X)((X)a6a5a4a3a2a1a000000000000000001X3X1 + X000010110010X4X2 + X100101100011X4 + X3X2 + X000111010100X5X2 + X1 + X001001110101X5 + X3X201011000110X5 + X4X001100010111X5 + X4 + X3X101110101000X6X2 + 110001011001X6 + X310011010X6 + X410101011X6 + X4 + X310111100X6 + X511001101X6 + X5 + X311011110X6 + X5 + X411101111X6 + X5 + X4 + X31111
III.5 ) Décodage des codes cycliques
Soient A = (a0, a1,
, an-1) le bloc du code émis
et R = (r0, r1,
, rn-1) le bloc reçu.
Ils sont associés aux polynômes :
A(X) = an-1(Xn-1 +
+ a1(X1 + a0(X0
R(X) = rn-1(Xn-1 +
+ r1(X1 + r0(X0
Comme dans les codes linéaires, on défini un vecteur d'erreur :
E = (en-1, en-2,
, e1, e0)
tel que E = A ( R
qui est associé au polynôme E(X) = en-1(Xn-1 +
+ e1(X1 + e0(X0
On en déduit : E(X) = A(X) + R(X)
En divisant R(X) par G(X) on obtient :
R(X) = Q'(X)( G(X) + S(X)
S(X) est le polynôme associé au syndrome S de degré strictement inférieur à celui de G(X).
Q'(X) est le quotient de la division de degré ( n-1-(n-k) = k-1
Soit E(X) = A(X) + Q'(X)( G(X) + S(X)
Or A(X) est, par définition, un bloc polynomial généré avec G(X), soit :
A(X) = Q(X) ( G(X) (voir relation (2) ci-dessus)
Et E(X) = [Q(X) + Q'(X)] ( G(X) + S(X)
On constate, avec cette dernière relation, que le syndrome S(X) est le reste de la division du polynôme d'erreur E(X) avec G(X), mais aussi (et c'est comme cela qu'il est calculé), le reste de la division du polynôme associé au bloc reçu, R(X), avec G(X).
Cette propriété permet de définir le type d'erreur pouvant être détectée :
Pas d'erreur : R(X) = A(X) ( E(X) = 0
Le reste de la division de E(X) par G(X) est nul ( S(X) = 0
S(X) = 0 est caractéristique d'une transmission sans erreur
Une seule erreur : E(X) = Xi avec 0 ( i ( n-1.
S(X) est nécessairement ( 0 (sauf si G(X) = 1 ou G(X) = Xj, ce qui ne peut être le cas car ces polynômes ne sont par facteurs de (Xn + 1)).
Paquet d'erreurs de longueur L. Un paquet d'erreurs de longueur L est une succession de L bits, corrects ou faux, le premier et le dernier étant toujours erronés.
Le degré de E(X) est nécessairement supérieur ou égal à (L-1). Ce polynôme peut donc se mettre sous la forme :
E(X) = Xi ( B(X)
B(X), de degré (L-1) est appelé modèle d'erreur :
B(X) = XL-1 + bL-2(XL-2 +
+ b1(X1 + X0
Or, tout polynôme générateur de degré supérieur à (L-1) ne peut diviser le modèle d'erreur. On choisira donc un polynôme générateur G(X) de degré (n-k) tel que (n-k) ( L pour détecter des paquets d'erreurs de longueur inférieure ou égale à L.
Exemple
Soit un code cyclique (7,4) défini par G(X) = X3 + X1 + 1
La distance minimum de Hamming (dmin) vaut 3. Le code est donc capable de détecter 2 erreurs et de corriger 1 erreur.
S'il y a une seule erreur, le vecteur d'erreur sera de la forme : E(X) = Xi, avec 0 ( i ( 6
Avec cette hypothèse, on peut calculer les syndromes obtenus pour chacune des erreurs possibles :
Erreur à l'indicePolynôme E(X) associéReste S(X) de E(X)/(X3 + X1 + 1)0X011X1X12X2X2 3X3X1 + 14X4X2 + X15X5X2 + X1 + 16X6X2 + 1
En rappelant que S(X) = s2(X2 + s1(X1 + s0, on peut réaliser un décodeur qui donne la position en erreur, donc qui élabore le vecteur d'erreur E :
s2s1s0S10Indice de l'erreurBit du symbole correspondant0000Pas d'erreur-00110Bit de contrôle01021Bit de contrôle10042Bit de contrôle01133m011064m111175m210156m3
Si la position pointée correspond à un des bits du symbole transmis, il suffira de l'inverser pour corriger l'erreur (voir schéma page 13).
III.6 ) Analogie avec les codes linéaires
Un code cyclique est un cas particulier de code linéaire. Les codes cycliques peuvent également être définis par leurs matrices de codage G et de vérification H.
En reprenant le code cyclique (7,4) de l'exemple ci-dessus, on déduit la matrice de vérification H en utilisant la méthode décrite pages 13 et 14 :
INCORPORER Equation.3
S10 5 7 6 3 4 2 1
On reconnaît la forme générale (sous-matrices de parité et diagonale). On en déduit :
INCORPORER Equation.3
III.7 ) Corrections d'erreurs multiples
Les méthodes de décodage décrites jusqu'ici ne permettent de corriger qu'une seule erreur dans chaque bloc reçu.
Pour augmenter cette capacité il faut augmenter la proportion de bits de contrôle. Le nombre de combinaisons du syndrome est : 2n-k. Pour que la correction soit possible, chacun de ces syndromes ne doit être obtenu qu'à partir d'un vecteur d'erreur unique. Dans ce cas, l'implication peut être inversée : le récepteur peut évaluer le vecteur d'erreur à partir du syndrome.
Pour corriger 1 erreur, il faut respecter : 2n-k -1 ( n (voir codes de Hamming page 14)
Pour corriger 1 ou 2 erreurs en positions quelconques, il faut respecter :
2n-k -1 ( n+(n-1)+(n-2)+
+(n-n+1)+(n-n) = n+n(n - (1+2+3+
+ n) = n((n+1)/2
Pour corriger 1 erreur isolée ou 2 erreurs groupées, il faut respecter :
2n-k -1 ( n + n - 1 = 2n - 1
Pour corriger 1 à 3 erreurs en positions quelconques, il faut respecter :
2n-k -1 ( n((n+1)/2 + n ( n ( n +
Pour corriger 1 à 3 erreurs groupées, il faut respecter :
2n-k -1 ( n + (n - 1) + (n - 2) = 3n - 3
Conclusion : la correction des erreurs isolées conduit rapidement à un nombre de bits de contrôle excessif.
Exemples :
pour n = 16 :
correction d'1 erreur isolée ( 2n-k -1 ( 16 ( n-k ( 5 et k ( 11
correction de 2 erreurs isolées ( 2n-k -1 ( 136 ( n-k ( 8 et k ( 8
Il y a déjà plus de bits de contrôle que de bits utiles !
pour n = 26 (code RDS par exemple)
correction d'1 erreur isolée ( 2n-k -1 ( 26 ( n-k ( 5 et k ( 21
correction de 2 erreurs isolées ( 2n-k -1 ( 351 ( n-k ( 9 et k ( 17
paquet d'erreurs de longueur ( 5 ( 2n-k -1 ( 26+25+24+23+22 = 120 soit n-k ( 7
Attention, les conditions établies ci-dessus sont nécessaires mais pas suffisantes.
III.8 ) Longueur du code
La quantité 2n-k - 1 est la longueur du code.
La plupart des codes cycliques n'exploitent pas toute la longueur du code pour corriger les erreurs car cela conduirait à des circuits très complexes. On les qualifie de codes cycliques abrégés.
III.9 ) Réalisation des codeurs et décodeurs
Les codeurs et les décodeurs sont généralement réalisés par des structures matérielles pour soulager le processeur de communication. Mais dans certains cas, on pourra préférer une structure logicielle.
Les structures matérielles sont très fréquemment basées sur des circuits séquentiels car :
les blocs sont toujours transmis au format série,
la réalisation est simple et facile à implanter dans des PLD.
III.9.1 ) Codage séquentiel
Principe général :
Les k bits du symbole M sont transmis en série sur Ms en synchronisme avec l'horloge. Le premier bit est toujours le poids le plus fort du symbole, à savoir mk-1.
Première étape :
L'inverseur SEL est en position "a" pour transmettre les bits d'information utile sur le canal.
Pendant ce temps, le diviseur élabore les (n-k) bits de contrôle à partir des k bits du symbole injectés au format série synchrone.
Deuxième étape :
Après k impulsions d'horloge, le commutateur est placé en position "b".
Le codeur fourni alors les bits de contrôle sur les (n-k) impulsions d'horloge suivantes.
Le chronogramme du signal As est donc le suivant :
mk-1
m0(n-k-1
(0 t (
Elaboration des bits de contrôle :
La structure proposée réalise la division de polynôme définie au chapitre III.4.2 :
Le reste ((X) de cette division donne les états des (n-k) bits de contrôle.
Schéma du codeur
Principe :
Rappels : Polynôme associé au reste : ((X) = (n-k-1(Xn-k-1 +
+ (1(X1 + (0
Polynôme générateur : G(X) = Xn-k + gn-k-1(Xn-k-1 +
+ g1(X1 + 1
En posant : ('(X) = (n-k-2(Xn-k-2 +
+ (1(X1 + (0
G'(X) = gn-k-1(Xn-k-1 +
+ g1(X1 + 1
on déduit : G(X) = G'(X) + Xn-k ou Xn-k = G(X) + G'(X)
((X) = ('(X) + (n-k-1(Xn-k-1
En multipliant par X les 2 expressions de cette dernière égalité, on obtient :
X(((X) = X(('(X) + (n-k-1(Xn-k
X(((X) = X(('(X) + (n-k-1([G(X) + G'(X)]
X(((X) = (n-k-1(G(X) + X(('(X) + (n-k-1(G'(X) (1)
On constate que le degré de [X(('(X) + (n-k-1(G'(X)] est toujours ( n-k-1
( Le reste de la division de X(((X) par G(X) est
X(('(X) + (n-k-1(G'(X) (2)
Soient P(X) un polynôme de degré ( (n-1) et ((X) le reste de la division de P(X) par G(X) :
P(X) = Q(X) (G(X) + ((X) (3)
Supposons qu'à l'instant considéré, les registres du diviseur contiennent le reste ((X). A l'impulsion d'horloge suivante, on introduit un nouveau bit mi du symbole M(X). Le polynôme associé au nouveau dividende est :
P1(X) = P(X)(X + mi (Xn-k (4)
Note : la pondération (n-k) de mi est due au niveau d'injection de Ms.
On cherche maintenant à exprimer le nouveau reste (1(X) de la division de P1(X) par G(X) en fonction du précédent ((X) pour justifier la structure utilisée.
D'après la relation (3) : X(P(X) = X(Q(X) (G(X) + X(((X) (5)
et, d'après (1) : X(P(X) = X(Q(X) (G(X) + (n-k-1(G(X) + X(('(X) + (n-k-1(G'(X)
soit : X(P(X)+ mi (Xn-k = G(X)([X(Q(X)+(n-k-1]+X(('(X)+(n-k-1(G'(X)+ mi (Xn-k
Or Xn-k = G(X) + G'(X) (voir ci-dessus)
On en déduit : X(P(X)+ mi (Xn-k = G(X)([X(Q(X)+(n-k-1+ mi]+X(('(X)+G'(X)(((n-k-1+ mi)
Le degré de [X(('(X) + G'(X)(((n-k-1 + mi)] est toujours inférieur à (n-k-1), c'est donc bien le reste de X(P(X)+ mi (Xn-k
Conclusion :
Si ((X) est le reste de la division de P(X) par G(X), alors le reste (1(X) de la division de
P1(X) = X(P(X) + mi (Xn-k par G(X) est :
(1(X) = X(('(X) + G'(X)(((n-k-1 + mi)
Ce traitement est réalisé par le circuit proposé. En effet, supposons que les registres contiennent les états de ((X) à un instant donné. Les entrées "datas" des registres valent alors :
Di(X) = X(('i(X) + (Ms + (i/n-k-1)(G'(X)
( ( (
Chaînage des Porte ( G(X) avec
registres bit MSB à "0"
A l'impulsion d'horloge suivante : (i+1(X) = Di(X)
On constate que (i+1(X) = (1(X) ( le circuit proposé réalise bien une division séquentielle
polynomiale par G(X).
Fonctionnement :
les registres sont initialement à "0"
le signal C est à "1" pendant les k premières impulsions d'horloge pour rendre le diviseur opérationnel.
Avant la 1° impulsion d'horloge :
P0(X) = 0
(0(X) = reste de P0(X) /G(X) = 0
As = Mk-1
Après la 1° impulsion d'horloge et avant la 2° :
P1(X) = X(P0(X) + Mk-1(Xn-k = Mk-1(Xn-k
(1(X) = X(('0(X) + G'(X)((0 + Mk-1) = G'(X)(Mk-1 = reste de P1(X)/G(X)
As = Mk-2
Après la 2° impulsion d'horloge et avant la 3° :
P2(X) = X(P1(X) + Mk-2(Xn-k = Mk-1(Xn-k+1 + Mk-2(Xn-k
(2(X) = X(('1(X) + G'(X)(( (1,n-k-1 + Mk-2) = reste de P2(X)/G(X)
As = Mk-3
Après la (k-1)° impulsion d'horloge et avant la dernière :
Pk-1(X) = Mk-1(Xn-k+k-2 + Mk-2(Xn-k+k-3 +
+ M1(Xn-k
(k-1(X) = reste de Pk-1(X)
As = M0
Après la k° impulsion d'horloge :
Pk(X) = Mk-1(Xn-k+k-1 + Mk-2(Xn-k+k-2 +
+ M1(Xn-k+1 + M0(Xn-k
= Mk-1(Xn-1 + Mk-2(Xn-2 +
+ M1(Xn-k+1 + M0(Xn-k
= M(X)(Xn-k
(k(X) = reste de Pk(X)/G(X) soit reste de M(X)(Xn-k/G(X)
As = 0
Ainsi, après la kième impulsion d'horloge, les registres contiennent le reste de :
INCORPORER Equation.3
c'est à dire les (n - k) bits de contrôle : (n-k-1 à (0.
le signal C est à "0" pendant les (n-k) impulsions suivantes. Le diviseur n'est plus opérationnel et les registres constituent un simple registre à décalage.
Ces (n-k) impulsions d'horloge vident le registre à décalage en commençant par (n-k-1 et jusqu'à (0 ce qui correspond au fonctionnement désiré.
Exemple : soit le code cyclique (7,4) défini par le polynôme générateur G(X) = X3 + X + 1
Avec le schéma de principe général, on obtient les blocs du code suivants :
SymbolesBlocs du codem3m2m1m0a6a5a4a3a2=(2a1=(1a0=(000000000000000100010110010001011000110011101010001001110101010110001100110001011101110101000100010110011001110101010100111011101100011001100010110111010011110111010011111111111
III.9.2 ) Décodage séquentiel simple
Comme cela a déjà été vu précédemment et à plusieurs reprises, la première étape du décodage consiste à élaborer le syndrome. Dans les codes cycliques, le syndrome S(X) est le reste de la division polynomiale du bloc reçu R(X) avec G(X). Le chapitre III.5 (page 18) démontre cette affirmation.
Ce calcul peut être aisément réalisé avec une structure très proche de celle utilisée dans le codeur. En effet, on réalise ici aussi une division par G(X).
Pour compléter le décodage, cette opération de division doit être associée à une fonction d'élaboration du vecteur d'erreur à partir du syndrome pour corriger les erreurs identifiées. Cette fonction peut devenir très complexe si les capacités de correction du code sont élevées.
On s'intéresse, dans un premier temps, aux décodeurs ayant une capacité de correction de 1 erreur seulement. Le chapitre suivant sera consacré à la correction des paquets d'erreurs.
Pour ne pas alourdir la notation, l'étude est faite sur un exemple, à savoir le décodage du code cyclique (7,4) défini par G(X) = X3 + X + 1.
Schéma complet
Rs : bloc reçu au format série (bit MSB d'abord)
Hs : horloge bits
La partie supérieure du schéma représente le diviseur séquentiel par G(X) et la partie inférieure, le registre de réception et le circuit de correction.
A noter que chaque bit ri du bloc est ici injecté à l'entrée du registre d'indice "0" du syndrome. Il n'y a donc pas de multiplication par Xn-k comme c'était le cas dans le codeur séquentiel.
Fonctionnement :
On suppose qu'une simple erreur apparaît en position "i" dans le bloc reçu R. Le vecteur d'erreur correspondant a donc toutes ses positions à "0", sauf la position "i" qui est à "1". Ce vecteur est associé au polynôme :
E(X) = Xi avec 0 ( i ( n-1
Première étape : C=1 et SEL en position "a"
Les "n" (7 dans l'exemple) bits du bloc reçu sont fournis sur Rs au format série en synchronisme avec l'horloge.
Le décodeur calcule le syndrome S(X) en divisant le bloc reçu R(X) par G(X). Cette opération est réalisée par le diviseur séquentiel dans lequel on injecte sous forme série les n bits du bloc R au rythme de l'horloge.
A la fin de cette étape :
Le registre de réception contient les 7 bits du bloc reçu. Un de ceux-ci est faux.
Les registres du diviseur contiennent les bits du syndrome.
L'état du syndrome obtenu permet d'identifier la position "i" en erreur. Un banal décodeur combinatoire associé à des inverseurs commandés pourrait être utilisé pour corriger l'état du bit altéré (voir page 13). En fait la structure séquentielle mise en uvre pour calculer le syndrome permet de réaliser un circuit de correction encore plus simple.
Deuxième étape : C=1 et SEL en position "b"
Le diviseur séquentiel est toujours opérationnel.
On applique n impulsions d'horloge supplémentaires au diviseur séquentiel, l'entrée Rs étant maintenue à "0".
A la première impulsion on peut considérer que le bloc reçu est décalé à gauche et a maintenant (n+1) bits, soit 8 pour l'exemple, et que l'erreur est en position (i +1). Le nouveau syndrome obtenu est donc le reste de la division de E(X) = Xi+1 par G(X). Il indique alors la position (i +1).
On continue d'activer le circuit de division jusqu'à ce que le syndrome indique la dernière position du bloc, soit (n-1), c'est à dire 6 dans notre exemple. Le nombre d'impulsions d'horloge supplémentaire est de (n-1-i). Ce nombre peut varier entre 0 (position 6 en erreur) et 6 (position 0 en erreur).
On utilise un décodeur combinatoire pour détecter le syndrome correspondant à une erreur en dernière position. Pour le code cyclique de notre exemple, le signal P passe à "1" si le syndrome prend la valeur 5, donc quand l'erreur est en position 6.
Pour chacune de ces impulsions d'horloge supplémentaire, le registre de réception du circuit de correction est bouclé sur lui-même via une porte "ou exclusif" de correction commandée par P. Ainsi, si l'erreur est en position "i" :
P est à "0" pendant les (n-1-i-1) premières impulsions d'horloge supplémentaire et passe à "1" à l'impulsion suivante. Le bit ri est alors dans la dernière position droite du registre de réception.
le bit ri est inversé, c'est à dire corrigé, avant d'être réinjecté dans le registre de réception.
Les (i +1) impulsions d'horloge restantes (sur n) replacent les bits du registre de réception à leurs places, le bit ri étant corrigé.
Remarque : l'économie de circuits autorisé par cette méthode de décodage devient nettement plus évidente quand la longueur des blocs est plus grande que l'exemple utilisé. Par contre, cette économie est faite au détriment de la vitesse, car il faut doubler les impulsions d'horloge pour réaliser la correction. Un circuit combinatoire réaliserait cette fonction beaucoup plus rapidement.
III.9.3 ) Décodage séquentiel des paquets d'erreurs (application au code RDS)
Certains codes cycliques sont très performants pour corriger les paquets d'erreurs.
Le support de l'étude qui suit est le code cyclique utilisé pour protéger les données numériques transmises dans le système RDS. Il est capable de :
détecter toutes les erreurs binaires simples et doubles dans un bloc de 26 bits,
détecter toute salve d'erreurs de longueur inférieure à 10 bits,
détecter 99,8% des salves d'erreurs de longueur inférieure à 11 bits,
détecter 99,9% des salves d'erreurs de longueur supérieure,
corriger des paquets d'erreurs de longueur inférieure ou égale à 5 bits.
Le code de protection RDS est basé sur le code cyclique (341,331) défini par le polynôme générateur suivant :
G(X) = X10 + X8 + X7 + X5 + X4 + X3 + 1
Un bloc du code d'origine est donc constitué de 331 bits d'information utile et de 10 bits de contrôle.
Le code réellement utilisé est le code cyclique (341,331) abrégé à 26 bits dans le but de réduire la complexité des codeurs et décodeurs.
L'étude qui suit traite les décodages des codes cycliques d'origine et abrégé. Le codage ne pose pas de problème particulier, on peut, par exemple, utiliser la structure du diviseur séquentiel vu au chapitre III.9.1 (page 22).
III.9.3.1 ) Outils théoriques
Rappels de notation :
R(X) : polynôme associé au bloc reçu R de degré ( n-1,
E(X) : polynôme associé au vecteur d'erreur de degré ( n-1,
G(X) : polynôme générateur de degré n-k,
S(X) : polynôme associé au syndrome de degré ( n-k-1.
La deuxième étape élabore la valeur la plus probable du vecteur d'erreur E(X) pour finalement corriger le bloc reçu en calculant : Rc(X) = R(X) + E(X).
L'étude qui suit montre comment est utilisé le diviseur séquentiel pour réaliser cette fonction.
Principe d'élaboration du vecteur d'erreur
La fonction du décodeur est d'élaborer la valeur la plus probable du vecteur d'erreur E(X).
Première étape :
La première étape du décodage consiste toujours à élaborer le syndrome S(X) en calculant le reste de la division polynomiale de R(X) par G(X). On utilisera pour cela la structure classique d'un diviseur séquentiel (le codeur utilise d'ailleurs la même):
R(X) = Q(X)(G(X) + S(X)
Cette première opération nécessite donc 341 (n) impulsions d'horloge.
Le syndrome est aussi le reste de la division de E(X) par G(X) (voir page 19) :
E(X) = QE(X)(G(X) + S(X)
Imaginons un vecteur d'erreur E*(X) tel que :
E*(X) = S(X)
Ce vecteur d'erreur a les particularités suivantes :
le degré est ( n-k-1 = 9 (le nombre d'erreurs est ( 10)
les k = 331 bits de poids forts sont à "0"
On en déduit que :
le syndrome de E*(X) est S(X) , à cause du degré de E*(X),
et que E(X) et E*(X) ont le même syndrome.
Si le poids de Hamming de E*(X) est inférieur ou égal à la capacité de correction "t" du code, alors :
le poids de Hamming de son syndrome S(X) est aussi ( t (car S(X) = E*(X))
E(X) = E*(X) car il ne peut exister deux vecteurs d'erreur différents ayant le même syndrome (voisinages distincts).
On en déduit une méthode de correction désignée sous le nom "error trapping" décrite ci-après.
Deuxième étape :
Le diviseur séquentiel par G(X) est toujours opérationnel dans cette 2° étape. L'entrée "datas" est simplement maintenue à "0".
Un nouveau syndrome est donc calculé à chaque impulsion d'horloge. A la ième impulsion, Si(X) est le reste de la division de Xi(R(X) par G(X) :
Xi(R(X) = Qi (G(X) + Si(X)
Une fonction évalue le poids de Hamming de chaque syndrome Si(X). Si ce poids est inférieur ou égal à la capacité de correction t du code, la correction est possible et est réalisée de la manière suivante :
A la ième impulsion : Si(X) : syndrome de Ri(X) = Xi(R(X)
: syndrome de Ei(X) = Xi(E(X)
Ri(X) : R(X) avec i transpositions circulaires à gauche
Ei(X) : E(X) avec i transpositions circulaires à gauche
Si le poids de Hamming de Si(X) est ( t, alors, d'après la règle ci-dessus (en italiques) :
Ei (X) = E*i(X) = Si(X) ( Xi(E(X) = Si(X)
Xn-i(Xi(E(X) = Xn-i(Si(X)
Or Xn(E(X) = E(X) car cette opération consiste en une rotation à gauche de n bits sur un mot de n bits.
Soit finalement : E(X) = Xn-i (Si (X) , le vecteur d'erreur est élaboré.
Pour corriger le bloc reçu il suffit de réaliser : Rc(X) = R(X) + E(X)
Cas particulier des paquets d'erreurs
Dans le cas de la correction de paquets d'erreurs de longueur inférieure ou égale à L, E(X) peut être mise sous la forme (on suppose que L ne dépasse pas la capacité "t" de correction du code) :
E(X) = Xj(B(X) avec B(X) = bL-1(XL-1 +
+ b1(X1 + b0(X0 le modèle d'erreur
Supposons qu'à la ième impulsion d'horloge, le bit altéré bL-1 se trouve à la position (n-k-1) de Ei(X), soit :
E*i(X) = Xn-k-L(B(X) de degré ( n-k-1 (degré d'un syndrome)
Dans ce cas, le syndrome Si(X) de E*i(X) est égal à Xn-k-L(B(X) et a nécessairement un poids de Hamming inférieur ou égal à L (donc à "t"). On peut alors appliquer la méthode de correction décrite ci-dessus :
Si(X) = E*i(X) = Xn-k-L(B(X) = Ei(X)
Le syndrome est donc égal au modèle d'erreur décalé de (n-k-L) positions à gauche,
Il en résulte que les (n-k-L) premières positions (de poids faible) du syndrome sont toutes à "0".
Cette dernière caractéristique permet d'élaborer un circuit de correction relativement simple :
à chaque impulsion d'horloge dans la 2° étape, on détecte si les (n-k-L) bits de poids faible du syndrome Si(X) sont à "0". Cette fonction est facilement réalisée par une porte OU de (n-k-L) entrées.
si c'est le cas, le modèle d'erreur B(X) est contenu dans les L bits de poids fort du syndrome Si(X).
on calcule alors E(X) = Xn-i(Si(X).
on corrige le bloc reçu en réalisant Rc(X) = R(X) + E(X)
III.9.3.2 ) Décodage du code cyclique (341,331) du système RDS
Le circuit séquentiel proposé utilise les résultats de l'étude théorique ci-dessus.
Le code cyclique (341,331) a les caractéristiques suivantes :
longueur des blocs : n = 341
nombre de bits utiles : k = 331
nombre de bits de contrôle : n-k = 10
capacité de correction : un paquet d'erreurs de longueur ( 5 (soit t = 5)
polynôme générateur : G(X) = X10 + X8 + X7 + X5 + X4 + X3 + 1
Schéma du décodeur
Note : l'horloge Hs n'a pas été représentée pour la clarté du schéma.
On reconnaît la structure d'un diviseur séquentiel déjà vue au chapitre III.9.1
Fonctionnement :
Première étape : C="1" et SEL1 et SEL2 en position "a".
Les 341 bits du bloc R(X) sont fournis sur Rs au format série synchrone, en commençant par les poids forts.
A la fin de cette étape :
les 10 registres du diviseur contiennent le syndrome S(X) de R(X),
le registre de réception contient les 341 bits de R(X).
Imaginons que le bloc reçu soit entaché d'un paquet d'erreurs de longueur inférieure ou égale à 5 en position "j". Le vecteur d'erreur associé est alors :
E(X) = Xj(B(X) avec B(X) = bL-1(XL-1 +
+ b1(X1 + b0(X0 le modèle d'erreur
B(X) = b4(X4 + b3(X3 + b2(X2 + b1(X1 + b0(X0
Le syndrome S(X) associé est tel que :
Xj(B(X) = QE(X)(G(X) + S(X)
Deuxième étape : SEL1 en position "b". L'entrée Rs est maintenue à "0".
L'inverseur SEL2 passe en position "b" et le signal C reste à l'état "1" jusqu'à la détection de la salve d'erreurs. Le diviseur est donc toujours opérationnel.
Le registre de réception est bouclé sur lui-même avec un circuit de correction entre les positions 9 et 10.
On continue d'appliquer des impulsions d'horloge jusqu'à ce que les 5 bits de poids faible du syndrome soient à "0". Soit "i", le nombre d'impulsions supplémentaires pour obtenir ce résultat.
Les registres du diviseur contiennent alors le syndrome Si(X) de Ei(X) = Xi (E(X),
et le registre de réception : Ri(X) = Xi (R(X) par transpositions circulaires.
D'après l'étude théorique, les 5 registres de poids fort du syndrome contiennent le modèle d'erreur B(X), soit :
Si(X) = Xn-k-L(B(X) = X5(( b4(X4 + b3(X3 + b2(X2 + b1(X1 + b0(X0)
Si(X) = b4(X9 + b3(X8 + b2(X7 + b1(X6 + b0(X5
On constate bien que les 5 bits de poids faible de Si(X) sont à "0" (indices 4 à 0).
Au même moment : Ei(X) = Si(X), ce qui signifie que la salve d'erreur se trouve entre les indices 9 et 5 de Ri(X).
A partir de ce moment, le signal logique C passe à "0" pour transformer le diviseur séquentiel en un registre à décalage à gauche non bouclé.
Durant les 5 impulsions d'horloge suivantes, le signal P prendra les états successifs des bits b4 à b0 du modèle d'erreur pour corriger les bits d'indice 9 à 5 de Ri(X) = Xi (R(X).
On termine le traitement en appliquant le reliquat d'impulsions d'horloge (sur n) avec SEL2 en position "a", pour que le bloc reçu et corrigé se retrouve en ordre dans le registre de réception.
III.9.3.3 ) Décodage du code abrégé (26,16) du système RDS
Le code de protection utilisé par le système RDS est issu du code cyclique (341,331) décrit ci-dessus. Il utilise le même polynôme générateur :
longueur des symboles : k = 16 bits,
longueur des blocs du code : n = 26 bits,
nombre des bits de contrôle : n - k = 10,
polynôme générateur : G(X) = X10 + X8 + X7 + X5 + X4 + X3 + 1
Notes sur le codeur :
La structure du codeur reste identique. En effet, on peut imaginer que l'on utilise le code cyclique (341,331) et que les 16 bits du symbole sont placés dans les 16 positions de poids faible des 331 bits d'information utile du code d'origine; les 315 bits de poids fort étant tous à zéro.
Ainsi, le diviseur séquentiel déduit du schéma général de la page 33 donnera les mêmes 10 bits de contrôle :
si on injecte les 331 bits du symbole du code cyclique (341,331) avec 331 impulsions d'horloge. Les 315 premières impulsions ne changent pas le contenu initial du registre car elles correspondent à des bits de données à "0".
si on injecte les 16 bits du symbole du code abrégé avec 16 impulsions d'horloge.
On préférera évidemment la deuxième méthode !
Décodeur :
On pourrait utiliser la structure classique du diviseur séquentiel pour calculer le syndrome du bloc R(X) de 26 bits reçu.
Par contre, le circuit de correction proposé au chapitre III.9.3.2 ne fonctionne plus car il exploite les propriétés cycliques du code d'origine. Et le code abrégé n'est plus cyclique.
Le problème peut être contourné en remarquant que seule la correction des 16 bits d'information utile est intéressante.
On peut imaginer de placer les 16 bits du bloc reçu R(X) dans un bloc virtuel de 341 bits comme s'il faisait partie du code d'origine :
( 0 ( ( 0 ( (
( ( 0 ( ( r25 ( ( r24 ( (
( ( r10 ( ( r9 ( ( r8 ( (
( ( r1 ( ( r0 (
Indice 340 339 26 25 24 10 9 8 1 0
( 16 bits d'info utile ( ( 10 bits de contrôle (
En utilisant le circuit de correction du chapitre III.9.3.2, les dix premières impulsions d'horloge de la phase de correction servent à identifier et corriger une salve d'erreurs dans les 10 bits de contrôle, ce qui est inutile.
A cause de la permutation circulaire sur 341 bits, il faudrait appliquer 315 impulsions d'horloge pour que le bit r25 se trouve en position 0. Du point de vue de la détection et de la correction des erreurs, ces impulsions sont inutiles car les positions traitées sont toutes à zéro.
La détection et la correction d'une salve d'erreurs sur les 16 bits d'information utile s'effectuera sur les 16 dernières impulsions d'horloge. Mais auparavant, il a fallut appliquer 325 impulsions inefficaces mais nécessaires !
Un pré-traitement adéquat sur le bloc reçu permet de détecter et corriger la salve d'erreur sur l'information utile sans appliquer les 325 impulsions d'horloge préliminaires : il suffit de réaliser une permutation circulaire de 325 positions sur le bloc de 341 bits, soit l'opération polynomiale :
R(X)(XN-k = R(X)(X325 avec N = 341 et k = 16
Malheureusement ce traitement nécessite une structure matérielle assez complexe, surtout si on choisit un traitement combinatoire pour diminuer le temps de calcul.
Nous allons montrer qu'une astuce permet de contourner le problème avec peu de moyens matériels :
En divisant XN-k par G(X), on obtient :
XN-k = QN(X)(G(X) + P(X)
Avec QN(X) : quotient de degré ( N-k-n+k = N-n
P(X) : reste de degré ( n-k-1
Soit P(X) = XN-k + QN(X)(G(X)
En divisant le produit R(X)(P(X) par G(X) on obtient :
R(X)(P(X) = QRP(X)(G(X) + SRP(X)
Avec R(X)(P(X) : dividende de degré ( n-1+n-k-1 = 2n-k-2
QRP(X) : quotient de degré ( 2n-k-2-n+k = n-2
SRP(X) : reste de degré ( n-k-1
En remplaçant P(X) par son expression :
XN-k(R(X) + R(X)(QN(X)(G(X) = QRP(X)(G(X) + SRP(X)
soit XN-k(R(X) = G(X)([ R(X)(QN(X) + QRP(X)] + SRP(X)
Avec XN-k(R(X) de degré ( N+n-k-1
R(X)(QN(X) + QRP(X) : quotient de degré ( n-1+N-n = N-1
SRP(X) : reste de degré ( n-k-1
Conclusions :
le reste SRP(X) de la division de R(X) (P(X) par G(X) est égal
au reste de la division de XN-k (R(X) par G(X)
SRP(X) est le syndrome de XN-k (R(X)
On en déduit la méthode de calcul du syndrome dans le code abrégé :
On élabore le produit polynomial R(X)(P(X)
P(X) est le reste de la division polynomiale de XN-k (= X325) par G(X), soit :
P(X) = X9 + X8 + X4 + X3 + X1 + 1
On calcule ensuite le reste de la division de ce produit par G(X) :
c'est le syndrome de XN-k (R(X).
En fait, les opérations de multiplication et de division polynomiales sont réalisées simultanément comme le montre le schéma ci-dessous :
Schéma du décodeur du code cyclique abrégé RDS
Fonctionnement :
Première étape : chargement du registre de réception et calcul du syndrome pendant les 26 premières impulsions d'horloge.
Les registres du diviseurs sont initialement à "0".
Les inverseurs SEL1 et SEL2 sont en position "a" et le signal C est à "1".
Les 26 bits du bloc reçu (r25 à r0) sont injectés sur Rs au rythme de l'horloge.
Les 16 bits d'information utile se trouvent dans le registre de réception après la 16ième impulsion d'horloge. Le registre de réception est alors bloqué pour les 10 impulsions restantes de cette première étape (cette fonction n'est pas représentée sur le schéma).
Rappels :
On note S(X) le polynôme associé au contenu des 10 registres du diviseur (partie supérieure du schéma).
Soit N(X) le dividende de la division tel que : N(X) = Q(X)(G(X) + S(X)
G'(X) = G(X) + Xn-k = G(X) + X10 = X8 + X7 + X5 + X4 + X3 + X0
Le reste de la division de X(S(X) par G(X) est : X(S'(X) + s9(G'(X)
Avec S'(X) = s8(X8+s7(X7+s6(X6+s5(X5+s4(X4+s3(X3+s2(X2+s1(X1+s0(X0
Le tableau ci-dessous donne les contenus successifs de S(X) à chaque impulsion d'horloge. On en déduit, à chaque étape, le dividende N(X) correspondant.
Impuls. d'horlogeSyndrome Si(X)Dividende Ni(X)Etat initialS0(X) = 0N0(X) = 01S1(X) = X(S'0(X)+s90(G'(X)+r25(P(X)
= r25(P(X)N1(X) = r25(P(X)2S2(X) = X(S'1(X)+s91(G'(X)+r24(P(X)N2(X) = X(N1(X)+r24(P(X)
= r25(X(P(X)+r24(P(X)3S3(X) = X(S'2(X)+s92(G'(X)+r23(P(X)N3(X) = X(N2(X)+r23(P(X)
= r25(X2(P(X)+r24(X1(P(X)+r23(P(X)
25S25(X) = X(S'24(X)+s924(G'(X)+r1(P(X)N25(X) = X(N24(X)+r1(P(X)
= r25(X24(P(X)+
+r2(X1(P(X)+r1(P(X)26S26(X) = X(S'25(X)+s925(G'(X)+r0(P(X)N26(X) = X(N25(X)+r0(P(X)
= r25(X25(P(X)+
+r1(X1(P(X)+r0(P(X)
= P(X)((r25(X25 +
+ r1(X1 + r0)
= P(X)(R(X)
Conclusion :
A la 26ième impulsion d'horloge, le syndrome de R(X)(P(X), donc de XN-k (R(X) se trouve dans les 10 registres du diviseur. CQFD.
Deuxième étape : correction du bloc reçu.
Le principe de fonctionnement est identique à celui déjà décrit pour le code cyclique non abrégé (page 32). Les différences sont :
la taille du registre de réception (16 bits à la place de 341),
quand une salve d'erreurs est détectée, celle-ci se trouve dans les 5 bits de poids fort du registre de réception. En effet, grâce à la transposition circulaire XN-k , le bit r25 se trouve en position 9 dans le bloc virtuel de 341 bits (25+325-341=9) au début de la phase de correction. Or, d'après l'étude théorique, quand les 5 bits de poids faible du syndrome sont à "0", la salve d'erreurs de longueur inférieure ou égale à 5 se trouve entre les indices 9 et 5 du bloc virtuel de 341 bits (voir page 32). La correction agit donc sur les bits d'information utile dès le début de cette 2° étape.
le nombre d'impulsions d'horloge nécessaire (16 maximum à la place de 341).
SymbolesBlocs du codem3m2m1m0a6a5a4a3a2=(2a1=(1a0=(000000000000000100010110010001011000110011101010001001110101010110001100110001011101110101000100010110011001110101010100111011101100011001100010110111010011110111010011111111111
Si le poids de Hamming de E*(X) est inférieur ou égal à la capacité de correction t du code, alors :
le poids de Hamming de son syndrome S(X) est aussi ( t (car S(X) = E*(X))
E(X) = E*(X) car il ne peut exister deux vecteurs d'erreur différents ayant le même syndrome (voisinages distincts).
Codes détecteurs et correcteurs d'erreurs de transmission
CREMMEL Marcel - DATE \@ "jj/MM/aa" 19/01/00 Page PAGE 40
Source de données
Contrôleur de communication
MOD
DEM
Contrôleur de communication
Collecteur de données
Introduit les caractères de service (dialogue) et les éléments de protection contre les erreurs
Canal de transmission
Adaptation au canal de transmission
0
1
0
1
q
q
p
Etat du bit transmis
Etat du bit reçu
X3
X3
Codage de protection contre les erreurs de transmission
Séquence de symboles
Séquence de symboles protégés
n bits
k bits
Cn : ensemble des 2n blocs possibles
Cun : ensemble des 2k blocs du code
n bits
k bits
Séquence de symboles corrigés
Séquence de symboles protégés reçus (blocs)
"Décodage" = détection/correction des erreurs de transm.
Erreur(s) détectées
Générateur de parité
Générateur de parité
Comp.
k
k+1
k+1
k+1
k
1
Symbole reçu
Symbole à transmettre
Erreur détectée
1
Canal
k
Cun : ensemble des 2k blocs du code
Cn : ensemble des 2n blocs possibles
Cun : ensemble des 2k blocs du code
Cn : ensemble des 2n blocs possibles
A
A1'
A1
A'
A
Bloc appartenant au code
Bloc hors sous-ensemble de codage Cun
d
dmin
B
dmin
A
>= dmin
Voisinage du bloc A
Voisinage du bloc B
C'
tmin
B
tmin
A
Voisinage du bloc B
Voisinage du bloc A
>= dmin
0001
0010
0100
1000
0000
Voisinage du bloc (0,0,0,0)
Zone de détection et de correction vers le bloc (0,0,0,0)
Voisinage du bloc (1,1,1,1)
Zone de détection et de correction vers le bloc (1,1,1,1)
1111
0111
1011
1101
1110
0011
0101
1001
0110
1010
1100
Zone de détection des erreurs sans correction
Codeur
Matrice G
Inverseurs
commandés
Décodeur
Matrice H
Décodeur combinatoire
k
k
n
n
n-k
k
S
M
R
A
Canal
en-1
a
INCORPORER Equation.3
rn-1
n
Mc
b
en-k+1
rn-k+1
en-k
rn-k
Calcul du vecteur d'erreur
Décodeur combinatoire
Calcul du syndrome S
Matrice H (logique combinatoire)
s0
s1
sn-k-1
Registre de réception du bloc R
r0
r1
rn-1
Symbole corrigé
1
0
0
.
.
.
.
.
0
rn-1 faux ( en-1 = 1 ( S10 = 3
rn-3 faux ( en-3 = 1 ( S10 = 6
indice n-3
rn-k faux ( en-k = 1 ( S10 = 2n-k - 1
0
1
0
.
.
.
.
.
0
.
.
.
.
.
.
.
.
0
0
0
.
.
.
.
.
1
0
0
0
.
.
.
.
.
0
1
0
0
.
.
.
0
0
1
1
0
0
.
.
.
0
1
0
1
rn-2 faux ( en-2 = 1 ( S10 = 5
indice n-2
rn-k+1 faux ( en-k+1 = 1 ( S10 = 2n-k - 2
0
0
.
.
.
0
1
1
0
.
.
.
.
.
.
.
.
.
1
1
.
.
.
1
1
1
0
1
1
1
1
.
.
.
.
1
.
.
.
.
.
.
.
.
.
indice n-1
rn-k-1 faux ( en-k-1 = 1 ( S10 = 2n-k-1
rn-k-2 faux ( en-k-2 = 1 ( S10 = 2n-k-2
r1 faux ( e1 = 1 ( S10 = 2
r0 faux ( e0 = 1 ( S10 = 1
indice n-k+1
indice n-k-1
indice n-k-2
indice 1
indice 0
indice n-k
Matrice de parité
[k ( (n-k)]
Matrice diagonale
[(n-k) ( (n-k)]
H =
a
b
S
S = a ( b
X8
Registre de réception
b
mck-1
mc0
mc1
a
Elaboration des bits de contrôle
Ms
As
a
SEL
b
1
1
1
Hs
Horloge
INCORPORER Equation.3
gn-k-1
Registre 1
Registre 0
g1
Registre n-k-1
Ms
(s
C
Hs
gi
= multiplication binaire par gi
= ou exclusif
Hs
C
a
Hs
C
(s
Registre 2
Ms
Registre 0
Registre 1
Registre 2
Rs
Registre 0
Registre 1
r6
r0
r1
r2
r3
r4
r5
b
SEL
P
Registre de réception
X
1
X
1
SEL1
8
9
10
11
339
340
7
( 1
C
9
Rs
8
P
0
1
&
0
6
X7
5
4
X5
3
X4
1
2
X0
SEL2
"0"
&
= multiplication binaire par gi
= ou exclusif
gi
Hs
C
(s
Registre n-k-1
Ms
Registre 0
Registre 1
gn-k-1
g1
1
X
Hs
C
(s
Registre 2
Ms
Registre 0
Registre 1
1
X
Registre de réception
P
b
a
SEL
r5
r4
r3
r2
r1
r0
r6
Hs
C
Registre 2
Rs
Registre 0
Registre 1
G'(X)
P(X)
X9
1
X3
X4
X8
X1
X3
&
"0"
SEL2
a
b
P
0
1
2
13
14
15
&
0
( 1
X0
1
2
3
X4
4
X5
5
6
X7
7
8
&
0
1
2
13
14
15
&
0
( 1
X0
1
X8
Registre de réception
b
"0"
a
SEL1
C
SEL2
9
a
Rs
X3
b
&
"0"
SEL2
2
a
b
P
P
0
1
3
X4
4
X5
5
6
X7
7
8
X8
Registre de réception
b
a
SEL1
C
9
Rs
X1
X8
P(X)
X4
X3
1
X9
8
G'(X)
9
10
11
339
340
&
0
( 1
X0
1
2
3
X4
4
X5
5
6
X7
7
8
X8
Registre de réception
b
a
SEL1
C
9
Rs
