158

]~TUDE DE CODES DI~TECTEURS ET CORRECTEURS D'ERREURS DE GLISSEHENT

p a r

J ~ r S m e de R E F F Y E Ing6nieur E.S.I.E.E., D.E.A., th6orie de l ' information des signaux et de la rdgulation *

ANALYSE. - - Cet article esl une synth~se des travaux effecluds sur la ddlection et la correction des erreurs de glis- semenl. L'auleur rappelte d'abord Ia position du probt~me. Puts, une approche thdorique lui permel de metlre en dvidence des classes de glissement. Sont ddcrites ensuite deux mdthodes de construction de codes synchronisables

pour la ddteclion el la correction des erreurs de glissement

ABSTnACT. - - This paper is a synthesis of studies conducled on detection and correction of slip errors. First, the author provides a slatement of the problem. Then, a theorical approach permits one to evidence classes of slip. Two

melhods of construction of synchronizable codes are described, for the detection and correction of slips.

CONTENTS. - - �9 I : Introduction. �9 I I : Ddfinition des classes eycliques d'un code cgclique. �9 I I I : Etude de codes ddlecteurs el correcteurs d'erreurs selon la technique de Tavares el Fuchada. �9 IV : Elude de codes ddlecteurs el correcteurs d' erreurs de glissement d' apr~s la technique de Bose, Caldwell el Weldon. �9 V : Commenlaires sur

les diffdrenls codes. �9 V I : Conclusion. Bibliographie (6 rdf.)

I. INTRODUCTION

D a n s la m a j o r i t 4 des cas [1], on n e cons id~re d a n s

u n c a n a l b i n a i r e de t r a n s m i s s i o n de l ' i n f o r m a t i o n que

les e r r eu r s a d d i t i v e s . Celles-ci s ' a j o u t e n t au m e s s a g e

u t i l e de d e u x famous d i f f4 ren tes :

�9 soi t i n d 4 p e n d a m m e n t les uues des a u t r e s : on d i t

q u ' o n a a f fa i re h des e r r e u r s isol6es ;

�9 soi t en g r o u p e : a u q u e l eas on a a f fa i re h des e r r eu r s

en p a q u e t s .

D e p u i s u n e d i za ine d ' a n n 4 e s , p a r su i t e d u d4ve lop -

p e m e n t de la t r a n s m i s s i o n d ' i n f o r m a t i o n s en n u m 4 -

r ique , des 6 t u d e s o n t dt4 m en4es , s u r t o u t a u x U.S .A. ,

su r u n n o u v e a u t y p e d ' e r r e u r s : les e r r eu r s de glis-

s e m e n t .

1.1. D6finition d'un glissernent et de l'erreur eorrespondante.

Soit : (% . . . . . an_ l ) , (b o . . . . . bn 1) ' ( C o ' ' ' " Cn--1) . . . . des m o t s de n 616ments b i n a i r e s a p p a r t e n a n t h u n

message . On d i t qu ' i l s ' e s t p r o d u i t u n g l i s s e m e n t de

p 614merits b i n a i r e s su r u n m o t d u message , si l ' o r i -

g ine de ce m o t s ' e s t d4calde de p 416ments b i n a i r e s

ve r s la d r o i t e on ve r s la gauche . S u p p o s o n s p a r e x e m p l e

qu ' i l se so i t p r o d u i t u n g l i s s e m e n t de p 616ments

b i n a i r e s su r le m o t (b 0 , ..., bn_ 0 , et que ce g l i s s e m e n t

n i t eu l ieu ve r s la d ro i te .

Le m o t re~u c o r r e s p o n d a n t h (b o . . . . . bn-1) se ra

(bp . . . . . bn-i , C 0 . . . . . Cp--1)"

L ' e r r e u r de g l i s s e m e n t su r le m o t r e q u e s t ddf inie

p a r l ' e f fe t t o t a l du g l i s s e m e n t su r le m o t 4mis.

1.2. D~composition de l'erreur de glissement.

P o s o n s : c o = b 0 + or o ,

cp_, = bp_ 1 + ~p_, ,

B o = (bo . . . . . bn-1),

Bp = (bp . . . . . bn_l , b o . . . . . bp_l),

' = ( b p b n _ 1 c o , Bp , ..., , ..., Cy_l) ,

A = (0 . . . . . 0, o~ o .... , 0r ,

off A r e p r ~ s e n t e u n p a q u e t d ' e r r e u r s de p 614meuts

b ina i r e s , qu i s ' a j o u t e au m o t dmis, en p lus du d4ca lage

c i rcu la i re .

I! e s t c la i r que le m o t re~u Bp es t 4gal ~ :

B~ = By + A .

By se d 4 d u i t du m o t 4mis B o p a r un d6ca lage

c i r cu la i r e (ou p e r m u t a t i o n c i r cu la i r e ) de p 616ments

b i n a i r e s ve r s la d ro i te .

P a r c o u s 4 q u e n t , l ' e r r e u r de g l i s s e m e n t qu i t r a n s -

f o r m e B o en B~ p e u t se d 6 c o m p o s e r en la s o m m e

d ' u n d6ca lage c i r cu la i r e e t d ' u n p a q u e t d ' e r r c u r s

a d d i t i v e s .

e t

* Au C N E T - Issy-les-Moutiaeaux, Assistance technique internationale.

ANN, TIi:LI~;COMMUNIC., 32, n ~ 3-4, 1977 U8

J . D E R E F F Y E . -- ]~TUDE D E C O D E S D I ~ T E C T E U R S E T C O R R E C T E U R S D ' E R R E U R S D E G L I S S E M E N T 159

1.3. Rappels sur les codes lin6aires r

1.3.1. Ddfinition d'un code Undaire.

Dans toute la suite, CG (2 n) sera une extension du corps de Galois CG (2) ~ deux dl6ments (0, 1).

Soit K un espace vectoriel de dimension n sur CG (2).

Un code lin6aire (n, k) est un sous-espace vectoriel

de dimension k sur CG (2). Soient V c K un code lin6aire (n, k) et x et y deux

vecteurs de V. K va 6tre murLi d 'une distance grfice h la distance

de H a m m i n g ddfinie par :

d(x, y) = p ( x + g) ,

off p(x) est le poids de Hamming du vecteur x (somme des composantes non nulles de x).

Alors V pourra corriger t erreurs si, et seulement si :

V ( x , g ) ~ V 2 , d(x,g) /> 2 l + 1.

1.4. D6finition d'un code lin6aire eyclique.

1.4.1. Ddfinition.

Un code lin6aire est cyclique si, et seulement si, il est invar ian t par pe rmuta t ion circulaire.

Soit V un code lindaire cyclique (n, k).

Le code d6duit de V par pe rmuta t ion circulaire sur les composantes de chaque 616ment de V est iderltique h V.

Soit P[x] l ' anneau des polynbmes h coefficients sur CG (2) et y(xn + 1) l ' id6al engendr6 par xn § 1.

Mors l 'ensemble quot ient E ( x ) = P(x)/Y (xn + 1) est isomorphe h K.

1.4.2. Thdordme.

V c K est un code cyclique (n, k) si l 'ensemble

V(x) ddduit de V par l ' isomorphisme canonique d6fini pr6c6demment, est un id6al de E(x).

L4.3. Polyn6me gdndrateur d'un code cyclique.

Soit ~ une racine primit ive n e de l 'unit~. Considdrons le polyn6me de plus bas degr6 h coeffi-

cients sur CG (2), dont a est la racine, soit ml(x ). Soit Vml le code engendr6 par ml(x ) ; le polynbme

a(x) appar t ien t ~ Vml si, et seulement si, a ( ~ ) = 0. Soit CG (2 n) l 'extension du corps de Galois CG (2),

c 'est-h-dire la sa turat ion de l 'ensemble (0, 1, ~) par les operations du corps (ce qui est 6quivalent aux puissances de l'(!16ment primitif ~).

Nous obtenons alors un corps de Galois f i n did-

meats . Soit n - - k le degr6 du polynbme ml(x).

L4.4. Thdordme.

Le code Vml est un code cyclique (n, k), dont le polynbme gdndrateur est ml(x ). Le polyn6me de plus bas degrd, orthogonal h ml(x), est appel~ polynSme

v~rificateur de paritd. Tout mot appar t enan t fi Vml aura ml(x ) comme facteur et sera orthogonal au

polyuSme vdrificateur de paritd. Tout polynbme de l 'id~al Vm 1 engendrd par ml(x )

admet une racine darzs CG (2n), qui nous permet

d 'obteni r la matrice de vdrification de parit6 et le polynSme vdrificateur de paritd.

(II est rappel~ que tou t mot d 'un code lindaire est

engendrd par la matrice g6ndratrice et est perpendi- culaire h t o u s l e s dl~ments de la matrice v6rificatrice

de paritd.)

1.5. Sensibilit6 d'un mode cyclique aux erreurs de glissement.

Soit V urr code cyclique (n, k) et a(x) un polynSme

avec a(x) r V. Supposons que le canal de t ransmission induise

des erreurs additives et des erreurs de glissement.

Les erreurs additives t ransforment a(x) en a(x)+ E(x) off E(x) repr6sente le polynbme de toutes les erreurs

additives. Les erreurs de glissement changent a ( x ) + E(x) en

xs[a(x) § E(x)] § Us(x), off x s repr6sente le d~calage

circulaire total dfi aux erreurs de glissement et Us(x) le polyn6me d'erreurs additives en blocs, correspon- dan t aux glissements.

Si le poids total des erreurs additives ne ddpasse pas la capacit6 de correction du code, ces erreurs sont corrig~es et le mot obtenu est xs a(x). Malheureuse-

ment , le code 6tant cyclique, ce mot est consid6r6

comme bon. Comme il est int6ressant de conserver les codes cycliques du fair de leurs nombreuses qua- lit~s, il faudra doric 61iminer autour d 'uu mot de code, ses voisins par rappor t h certaines permuta t ions circulaires, par un proc6d6 h d6terminer.

II. DI~FINITION DES CLASSES CYCLIQUES D'UN CODE CYCLIQUE [2]

II.1. Rappel de la d6finition de l'exposant d'un mot de code.

Soit V un code cyclique (n, k) et h(x) un polynSme appa r t enan t fi V, tel que h(x) divise x n + 1.

Le plus pet i t hombre entier e tel que h(x) divise x e + 1 s'appelle l 'exposant de h(x).

II.2. D6finition d'une classe cyclique d'un code cycllque.

Une classe cyclique est l 'ensemble de t o u s l e s mots qui sont des permuta t ions circulaires d 'un autre mot.

2/8 A~N. TELI~COMMUNIC., 32, n ~ 3-4, 1977

160 J . D E R E F F Y E . I ~ T U D E D E C O D E S D E T E C T E U R S ET C O R R E C T E U R S D ' E R R E U R S D E G L I S S E M E N T

La tai l le de la classe, appel6e p6riode, est n6cessai- r e m e n t u n d iv iseur de la l ongueu r du bloc.

11.3. D6finit ion d'un cycle.

Soit V u n code cycl ique (n, k), d o n t g(x) est le p o l y n 6 m e gdndra teur (pg) et h(x) le p o l y n 6 m e v~rifi- c a t e u r de par i t~ (pvp) .

D e u x po lyn6me s a p p a r t e n a n t h V, fl(x)g(x) et f2(x)g(x) a p p a r t i e n n e n t au mfime cycle si, et seule- m e n t si :

3 s ~ N , 0 ~< s ~< n,

xsf2(x)g(x ) = fl(x)g(x) rood. (x n + 1) ,

ce qui est 6qu iva l en t h :

x S f 2 ( x ) - h ( x ) = 0 modu lo [h(x)l .

Soit f(x)g(x) u n m o t du code V e t b le plus pe t i t

cut ler , tel que :

xbf(x)g(x) = f(x)g(x) modu lo (x n § 1) ,

alors ( x b - 1) f i x ) = 0 mod. [h(x)] . Pa r c o n s e q u e n t f(x) repr~sente u n cycle de p6riode b

et f(x)g(x) engendre une classe cycl ique de pdriode b.

PPCM (el , ei+l . . . . . er) >/ P P C M (el+ 1 . . . . . er) �9

D6finissons m a i n t e n a n t V i - 1 - - Vi com m e Fen- semble de tous les roots de code qu i son t duns V~_~, mais pas darts Vi .

Alors { V o - V1, V 1 - - V~ , . . . , V r - 1 - - V r , Vr} , off Vr reprdsente le m o t zdro, forme une p a r t i t i o n du

code cyel ique (n, k ) V o . T o u s l e s roots de code dans V l _ ~ - - Vi son t de la

forme f(z)g(~-l)(x), oh f(x) n ' e s t pas divis ible pa r h~ (x). A cause de (1) (cf. plus hau t ) , t o u s l e s cycles darts

Vi-1 o n t des pdriodes qui son t des mul t ip l e s de e i .

I I . 5 . L e m m e .

Dans V t _ ~ - Vi avec i <~ r, tous les cycles ou t des p6riodes qui son t des mul t ip les de el et qu i son t bor- rides supd r i eu remen t par PPCM (ei , ..., er) .

Cette p6riode m a x i m a l e est a t t e i n t e pou r que lques

cycles de V i_~- - Vi . E u par t icul ier , s i e i = n, tous les cycles ou t c o m m e

pdriode n.

I I . 6 . L e m m e .

11.4. Propri6t6s usuel les d 'une partit ion codes cycl iques.

de

Ddcomposons h(x) en fac teurs i r reduct ib les :

h(x) = h i (x ) ... hr(x) ,

tels qu ' i l s soient o rdonnds pa r ordre d ' e x p o s a n t

ddcroissant :

e i >1 el+ t a v e c i = 1 . . . . . r - 1.

E t a n t i r r6duct ib les , ils son t premiers en t re eux

s i n est impai r , et hl+l ... hr(x) a co mme exposan t

e = PPCM ( e f + 1 . . . . . er).

Soit VI u n sous-code de V0, tel que son p o l y n 6 m e

gdn6ra teur s '6crive :

g(O(x) = g(x) h~(z) . . . . . h~(z).

Le p o l y n S m e v6r i f ica teur de par i t6 de Vi est d o u c :

H(x) = hl+l(X).. , hr(X), et l ' on a : Vi c Vl-1 .

La pdriode des cycles darts Vi est dd te rminde pa r

le r a p p o r t :

(1) I(x) (xs - - 1)/hi+ 1 (x) ... hr(x)

(cf. Tavares el al., [2, 3, 4]).

Du f a r que H(x) a c o mme e x p o s a n t :

e = PPCM (el+ 1 . . . . , er) ,

t o u s l e s cycles dans Vt o u t comme p~riode e ou des diviseurs de e.

P a r un r a i s o n n e m e n t ana logue , on en d6dui t que tous les roots de code duns V~_ 1 o n t une pdriode 6gale h PPCM (el , ..., er) ou ~gale h des diviseurs de celui-ci.

On a ~ v i d e m m e u t :

T o u t m o t de code, dans l ' en semble V f _ 1 - - V i ,

p e u t ~tre 6crit sous la forme :

~(x) = [fix) hi(x) § a(x)] g(x) hl(x ) ... h~_l(x ) ,

avec : i ~< r , a(x) :7~ 0 , deg [a(x)] < m~,

i

off m i = deg [h(x)] et deg [f(x)] < k - - ~ m j . /=t

Ces cond i t ions mises h par t , f(x) et a(x) son t a rb i -

t ra ires .

Pou r q u ' u n m o t a p p a r t i e n n e fi V i - 1 - V i , il est

ndcessaire et suf i i sant qu ' i l soit d ivis ible par hi_l(x), mais pas pa r hi(x).

Or ~(x) a p p a r t i e n t h Vl_ 1 , car g(i-X)(x) e n e s t u n fac teur , mais r t ' appa r t i en t p a s h V i , car a u c u n de ses t ac teurs n ' e s t divis ible pa r g(O(x).

R 6 c i p r o q u e m e n t , si l ' on a : ~(x) E V i - 1 - - Vi , alors ~(x) poss~de g(i-1)(x) com m e facteur . D ' a u t r e par t , le second fac teur ne dolt pus ~tre divis ible pa r hi(x), et se m e t pa r cons6quen t sous la forme :

f(x) h~(z) + a (x ) ,

off : deg [a(x)] < deg [h i (x) ] .

Le l emme est ddmontr6 .

II.7. Th6orbme.

Soit V o u n code cycl ique (n, k) d o n t le p o l y n S m e vdr i f ica teur de par i td h(x) a u n fac teur i r r6duc t ib le

h~(x), d ' e x p o s a n t n e t de degr6 m I

ANN, T~:LI~EOMMUNIC., 32, n ~ 3-4, 1977 3/8

J . DE R E F F Y E . I~TUDE D E CODES DI~TECTEURS ET C O R R E C T E U R S D ' E R R E U R S D E G L I S S E M E N T 161

Quel que soit le choix de f(x), de degr6 s t r ic tement

inf6rieur h k - - m ~ , l 'expression :

(2) If(x) h~(x) § 1] g(x)

donne un repr&entan t d 'un cycle dist inct (car tons les cycles out alors comme p6riode n).

II.8. Remarque 1.

Si hl(x ) a comme exposant n 1 avec n 1 ~ n, tou t choix de f(x), de degr6 inf6rieur h k - - m ~ , donrte

dans l 'expression (2) un repr6sentant d 'un cycle dist inct t au t que la p4riode de ce cycle est inf6rieure

n~.

II.9. Remarque 2.

Si l 'on veut rester darts les condit ions du th6o- r6me III-7, et si hl(x ) a u n exposant inf6rieur h n, il suffit de prendre dans le polyn6me v6rificateur de

parit6 un autre facteur irr6ductible h2(x), de degr6 m 2 et d 'exposant n 2 , tel que : PPCM (n 1 , n2) = n. Alors tou t choix de f(x), de degr4 infdrieur ~ k - m 1 - - m 2 ,

daus [f(x) hi(x ) h2(x ) + 1] g(x) , donne un repr6sen- t a n t d 'un cycle distinct. Si h2(x ) n 'existe pas, il faudra

prendre a u t a n t de facteurs du polyn6me v6rificateur de parit6 qu'i l est n6cessaire, afin que l 'exposant de leur produit soit n.

I I I . ]~TUDE DE C O D E S D I ~ T E C T E U R S ET COBBECTEUB8 D'EBBEUBS

S E L O N LA T E C H N I Q U E D E T A V A B E S ET F U C H A D A [~]

III.1. Cas d'un canal sans bruit dans lequel il n'apparait pas d'erreurs purement additives.

111.1.1. Thdordme 1.

Soit un code cyclique (n, k) dont le polyn6me v6rifi- cateur de parit6 a u n facteur irr4duetible de degr6 m e t d 'exposant u. Alors il existe un sous-code (n, k - - m ) , qui peut d6tecter route combinaison de s 616ments binaires de glissement, pourvu que s ~< u - - 1 et que s ~ n - - k.

Soit F(x) ce facteur irr6ductible. Consid6rons tous les mots du code cyclique initial de la forme :

a(x) = [j(x) F(x) § 11 g(x),

off g(x) cst le polyn6me g6n6rateur du code cyclique

(n, k) et j(x) un polyubme arbitraire avec :

deg [j(x)] < k - - m.

L'ensemble de ces mots forme un sons-code. Pour u = n, on obt ient pour chaque j(x) des repr6sentants

de cycles distincts (cf. th6or6me III.7). La pdriode de ces cycles est ici au moins u e t l 'on a u ~< n. On n 'es t

donc plus assur6 d 'avoir des reprdsentants de cycles

distincts pour chaque j(x), sauf si la longueur des glissements reste inf6rieure h u.

Soit a(x) le mot 6mis. Apr6s passage darts le canal

de transmission, le mot obtenu h la rdception est :

xSa(x) q- Us(x),

off Us(x) correspond aux erreurs additives en paquet

de longueur s dues au chevauchement s i r le mot su ivant ou pr6c6dent, selon que le glissement est h droite ou h gauche (on suppose qu'i l ne s'est produi t

qu ' un seul glissement) ;

x s correspond aux glissements de s dl6meats binaires gauche s i s ~ 0, et h droite s i s ~ 0.

Pour d6tecteur les erreurs, on forme le syndrome g6n6ral :

{xs (x) + vs(x)}g, off ~g(x)} a d&igne le reste de la division de 0~(X) par g(x).

Or : {x sa(x)} a 0 et {Us(x)} a ~ 0 si Us(x) :fi 0 et si deg [Us(x)] ~ n - k. En effet, un code cyclique (n, k) d6tecte tons les paquets d 'erreurs de degr6 inf6rieur ~ n - k, c'est-fi-dire s i s ~ n - k.

Si Us(x) = 0, on forme le syndrome de giissemertt :

{xSa(x)}F,

Off ~:r d&igne le reste de la divisiou de 0r par F(x) et l 'on a :

{xSa(x)}F = {xS(j(x) F ( x ) § 1)}F = {x s }F .

I1 existe une erreur de glissement si {XS}F :fi 1, ce qui s'dcrit aussi {x s -- 1}F :7~ 0.

F(x) ne divise pus x s - 1 s i s ~ u.

Si F(x) est primit if et si deg IF(x)] = m, il ne divise pas x s - 1 s i s ~ 2 m - 1 .

Le min imum r6pondant h la condit ion est :

m = [log2(s + 1)] + 1,

off [E] = partie enti6re de E.

OrL aura donc int6r~t h choisir au t aa t que possible F(x) primitif.

111.1.2. Thdordme.

Ce th4or6me est l 'analogue du th6or6me I I I . l .1 pour la correction d 'erreurs additives.

Soit un code cyclique (n, k) dont le polyn6me vdrificateur de parit6 a u n facteur de degr4 m et d 'exposant u ; il existe un sons-code (n, k - - m ) qui

pent corriger au moins s 616ments binaires de glis-

sement si le canal n ' a pas d'erreurs additives, pourvu que s ~ [ ( n - - k ) / 2 ] et 2 s ~ u.

Un code cyclique pent corriger tou t paquet d 'erreurs de longueur infdrieure h [ ( n - k)/2].

On dolt donc avoir s ~ [(n - - k)/2].

L '6met teur envoie le mot w(x), et on revolt :

x~w(x) + U~(x).

4/8 ANN. T~LIs :12, n ~ 3-4, 1977

162 J . D E R E F F Y E . -- ] ~ T U D E D E C O D E S D I ~ T E C T E U R S E T C O R R E C T E U R S D ' E R R E U R S D E G L I S S E M E N T

La correction se fait en deux temps :

- - on corrige tou t d 'abord le paquet d'erreurs Up(x) de mani~re classique. I1 reste xVw(x), off w(x) est de Ia forme j(x) F(x) § 1 ;

- - on calcule alors le syndrome de synchronisat ion :

=

La direction et l ' ampl i tude du glissement seront ddtermindes si p ~ Z et r ~ Z , avec p =/=r, ce qui

entra ine (X'}F # {xr}F, et qui s'dcrit :

{xP- Xr}F ~/= O.

Ceci sera vdrifid si :

Ipl , . < s Ip- 1 -< 2 s < u .

Si F(x) est primitif de degrfi m, alors :

I p - r l .< 2 s < .

Dans ce cas, la relat ion entre m e t s s'dcrit :

m = 1 + [ l o g ~ ( 2 s + 1)1.

III .2 . Cas du c a n a l brui t6 .

dont le polyn6me v~rificateur de parit~ a u n degr6 m

d 'exposant u avee t < u. I1 existe alors un sous-eode (n, k - - m) qui peut corriger toute configuration d'erreurs additives que Ie code paren t pouvai t cor- riger en l 'absence de glissement, et d~tecter la prd- sence d 'un glissement de s dldments binaires quand celui-ci arrive s imul tan~ment avec des erreurs addi- tives, si e + s <~ t.

~(x), mot dmis, devient xSa(x) + Us(x) § E(x) h la r6ception.

�9 s = 0 : on corrige E(x) de la marti6re habituelle ;

�9 s 7/= 0 : on corrige E(x )§ Us(x) de la mani6re habi- tuelle si e § s ~< l ; mais on retombe sur xSa(x). Nous formons doric le syndrSme de glissement {XS}F.

On d6tecte la presence de glissement si ]s I < u. Si F(x) est primitif de degr6 m, la relat ion pr6c6dente

devient : [s I < u = 2 m - - 1, le plus pet i t m r6pondant la question 6tant donn6 par :

m = 1 § log2(s+ 1)] .

S'il n ' y a pas d 'erreur de glissement, on interpr6te

alors le mot corrig~ comme bon.

111.2.1. Thdordme.

Soit un code cyclique (n,k) dont le polyn6me v6rificateur de parit6 a un facteur de degr6 m e t d 'exposant u; il existe un sous-code (n, k - - m ) avec d ~< Inf (u, n - - k ) , qui peut d6tecter des combi-

naisons de s dl6ments binaires de glissement et e elements binaires d 'erreurs additives, si e+ s ~ d--1.

Rappelons qu 'un code cyclique (n, k) d6tecte toute

configurat ion de paque t d 'erreurs inf6rieure h n - k.

Le mot 6mis est w(x).

Le mot re~u est xVw(x)§ Uv(x ) + E(x) , off :

E(x) : erreurs addit ives ind6pendantes dues au canal,

Up(x) : erreurs additives en paquet dues au glisse- merit,

xv : d@alage circulaire dO au glissement.

On commerrce par ddtecter E(x) + Uv(x). Ceci n 'es t possible que si la longueur du paquet est iufdrieure

h n - - k . Si E ( x ) § U p ( x ) = 0, le syndrome par rappor t au

polynbme g6n6rateur g(x) est toujours nul. Darts ce cas, on calcule le syndr6me de glissement qui est

aiors :

{XP}F =7 ~ 1 si 0 < ]p[ < d - - 1 < u avec p E Z .

Lorsque F(x) est primitif, la condit ion devient :

Ip[ < 2 m - - l , et l 'on a : Ipl < 2 ~ - - 1 ~ a < 2~.

La valeur de m qui convient alors est :

m = 1 § [log 2 d ] .

111.2.2. Thdor~.me.

Soit un code cyclique (n, k) correcteur de t erreurs

111.2.3. Thdor~me.

Soit un code cyclique (n, k) correcteur de ! erreurs

dont le polyn6me v6rificateur de parit~ a u n facteur de degrd m e t d 'exposant u ; il existe alors un sous- code (n, k - - m) avec 2 t < u qui peut corriger toute combinaison de e erreurs additives et p ~ldments

binaires de glissement, pourvu que e + tp I <~ t. Supposons e erreurs additives et p ~ldments binaircs

de glissement avec e + Ip t ~ t. La correction porte d 'abord sur les erreurs additives

dues au brui t et au glissement, E ( x ) + Up(x). I1 reste xPw(x), off w(x) est le mot qui a dtd 6mis.

Le syndrome de glissement e s t {ZP}F. Pour d6terminer p, on doit avoir :

, [rl < " avec p ~ r ~ {XP}F= {xr}F.

Or: Z t s

z t a v e c : ~ F I

D'oh : ] p - - r I ~< 2 l < u. %

Si F(x) est primitif de degr~ In, on peut prendre

m = I § [log s (2 t § 1)] ; C.Q.F.D.

IV. E T U D E D E C O D E S D ~ . T E C T E U R S E T C O B B E C T E U B S

D ' E R R E U B S D E G L I S S E M E N T D ' A P R ~ S L A T E C H N I Q U E D E B O S E

C A L D W E L L E T W E L D O N [5, 6]

La technique de construct ion reste semblable h celle de Tavares et Fuchada [4]. I1 s 'agi t de construire

un sous-code dont les roots sont chacun un reprd- sen tan t d 'une classe cyclique. Aucun mot ne peut se

ANN. T]~L~COMMUNIC., 32, n ~ 3-4, 1977 5 / 8

J . D E R E F F Y E . -- I ~ T U D E D E C O D E S D E T E C T E U R S E T C O R R E C T E U R S D ' E R R E U R S D E G L I S S E M E N T 163

ddduire d 'un autre par glissement. Mais l 'originalit5 rdside dans l 'addi t ion d'dl~ments binaires h droite et

gauche du mot de ddpart, afin de le prdserver des erreurs additives en bloc ar r ivant des mots adjacents.

I1 convient de remarquer que ces codes sont an td- rieurs h ceux de Tavares et Fuchada. Nous les intro- dnisons apr~s, car ils sour plus diffmiles h expliquer

du fair de connaissances insuflisantes h l '~poque sur les classes cycliques.

Soit V o un code cyclique (n, k) dont le polyn6me gdndrateur est g(x), le polyn6me v~rificateur de parit~

h(x) et a(x) G V o , a(x) ~tant de la forme (% . . . . . a n - l ) .

Nous construisons un nouveau mot de la fa~on suivante : le mot a(x) est augmentd de r t dl~ments binaires h gauche et de r~ ~ldments binaires h droite, de fa~on h obtenir :

( a n ~ t - r l , . . . , a 0 , a t , . . . , a n - i , a o , . . . , a r ~ ) �9

Les m~mes 616ments binaires que ceux du mot de d6part sont r6pdtds fi droite et h gauche par permu- ta t ion circulaire.

Nous supposons que V 0 est un code correcteur de t erreurs. Soit ~ un 616ment primitif du corps de Galois CG(2 n) et n = 2 m+l.

Soit ~ une racine de l '6quat ion x n q - 1 = 0

telle que ~ ne soit pas racine de l '6quat ion g ( x ) = 0. Par cons6quent, ~ est racine de l 'dquat ion h ( x ) = 0,

Soit f(x) le polyn6me minimal [c'est-h-dire le poly- n6me de plus has degrd] de ~, tel que :

ve 0 et 1 et d e g [ f ( x ) ] = m l ,

off m I e s t un diviseur de m. Le polyn6me f(x) sera un diviseur de h(x).

�9 Soit n t l 'ordre de ~, ce qui veut dire que n I e s t le plus peti t entier ~ 0 tel que ~n~ § 1.

Alors n t divise n.

Rappelons ici que ces codes ont 6t6 6tudids avan t les codes Tavares et Fuchada. Les hypotheses faites sont douc moins g6n6rales que celles qui ddcoulent de l '6tude des classes cycliques d 'un code cyclique, car elles en t ra inen t que n I e s t l ' exposant de f(x).

f(x) divise x n l § 1. En effet ~n~ § 1 = 0 et f(~) = 0 et eeci entra ine : f(x) ~ h(x).

f(x), polyn6me minimal de ~ et irrdductible, divise xn~ § 1, mais pas xa § 1, pour tou t entier a infdrieur h n t , n~ est donc bieu l 'exposant de f(x).

Soit V* le sous-code engendr6 par g(x) f(x). Tout

mot v ' = (v0, v I , ..., vn_ l ) de V* satisfait v ' [ H , H1] = 0, off [H, Ht] est compos6e de la matrice de vdrification de parit6 [H] et du vecteur colonne (1, ~, ~ . . . . . ~n-t)t avec ~ racine de f(x).

Soit C ' = ( % , . . . , cn-1) un mot fix6 avec C' Ve 0 ;

C' ~ V o ; C' @ V*. Par cons6quent : C' ~ V o - V*.

On suppose que r tq- r 2 ~ n t avec :

r t : glissement maximal h gauche,

r~ : glissement maximal fi droite

(hypoth~se destin6e h avoir des repr6sentants de classes eycliques diffdrentes).

C' (x ) est de la forme :

C'(x) = [f(x) g(x) -4- a(x)] g(x),

avec : a(~) =fi 0. De m~me : V ' ( x ) = ~ (x )g (x ) f (x ) ,

d 'of l : V'(x) + C'(x) = ((co(x) + ~(x)) f(x) -f- a(x)) g(x).

Si l 'on calcule alors le syndrome g~ndral :

1 ((~(x) + ~(x)) fix) + a(x)) g(x) ! g(x) i"

Puis le syndrome de glissement :

I (~(x) + [~(x)) f(x) + a(x) f(x) I"

On retrouve les codes de Tavares et Fuchada. Bose, Caldwell et Weldon ont procddd diffdremment :

A part i r de C' et V', on construi t deux autres roots

en a jou t an t r I ~l~ments binaires h gauche et r 2 dld- ments binaires h droite (compte tenu de l 'hypoth6se pr6c~dente) de la mani~re expos~e au d6but de ce paragraphe.

Y ' = ( % , V l , . . . , Vn-1) donne Va = ( V n _ l _ r 1 . . . . .

V n - - 1 , l) 0 , l) 1 , . . . , I )~ - - 1 ~ I) 0 , . . . , I)r 2) �9

C' = (c o , Ca , . . . , cn_ l ) donne Ch = (Cn_l_rl . . . . .

Cr$--I ~ C O , C 1 , . . . , O n - - 1 , C O , . . . , Cr2) �9

Soit Ca le nouveau code dont les roots sont de la forme Va + Ca �9 On remarque qu'i l y a u n e bi ject ion entre V et Ca et que Ca est un code ( n § r l + r ~ , k - - m ) .

P r o c d d u r e de ddcodage.

Va + C'a ~tant t ransmis , soit E a = ( f a _ l _ r 1 , ....

f n - t , eo . . . . . e n - 1 , fo . . . . . fr2) le mot d 'erreur additive.

E n l 'absence d 'erreur de glissement, le mot reCu est doric : Y a = V ' a + C a + E a .

On commence par enlever h gauche et h droite le mSme nombre d'dl~ments binaires qu 'on avai t ajout~s au codage. Le ddcodage permet done tou t d 'abord de se ddbarrasser des erreurs par paquets dues aux mots adjacents. On obt ient :

Y ' = V ' q- C' -k E ' , of f E ' : (e o . . . . . en_ l ) .

S'il y a des erreurs de glissement h gauche, on obt ient :

Y~ = V~(L)+ C~(L)+ E~(L)

qui devient :

Y = V(L)q- C(L)~- E(L) ,

O t l V ( L ) : ( 1 ) L , / ) L + t . . . . , O r t - l . , I)0 . . . . . V L - - 1 ) ,

C ( L ) = ( e L , C L + 1 . . . . , c n _ t , C O . . . . . C L _ I ) ,

E(L) = (e L , eL+ 1 . . . . , e n - t , eo . . . . . eL--l) �9

De m~me, si on subit un glissement h droite, on obt ient :

r a = Va( n - - R) § Ca(n - - R ) q- E a ( n - - R ) ,

qui devient :

Y = V ( n - - R ) q- C ( n - - R ) q- E ( n - - R ) ,

6 / 8 ANN. TI~L~COMMUNIC., 32, n ~ 3-4, 1977

164 J. DE REFFYE. -- I~TUDE DE CODES DI~TECTEURS ET CORRECTEURS D~ERREURS DE GLISSEMENT

oll V(n - - R) = v n _ R . . . . , v n - 1 , v,) . . . . . v n - ~ - l ) ,

C(n - - R) = ( C n - R . . . . , C n - 1 , co . . . . . c n - R - 1 ) ,

E(n - - R) = ( e n _ R . . . . . e n _ l , e o . . . . . e n _ R _ l ) ,

avec L ~ r 1 ,

R ~ r 2 �9

Les erreurs addit ives sont corrig6es selon la m6thode

classique.

I1 reste h corriger une permuta t ion circulaire, s'il

y a eu un glissement h gauche ou ~ droite. Selon le

cas, on obt ient :

Z = V §

ou z = V ( L ) + C ( L ) ,

ou Z = V ( n - - R ) + C ( n - - R ) .

Formons le syndrome des erreurs de glissement :

Z H 1 = Zo + Z1 ~ ~_ ... @ Zn_x ~n-1.

O r V H I = /)oAf- /)1 ~ - ... ~- / )~-1 ~ n - l = 0, c a r f (~)= 0

et f(x) est un facteur de v(x).

I1 reste d o n c :

(1) C H ~ = c o + c 1 ~-}- . . . - ~ Cn_ 1 ~ n - l =

en l 'absence d 'er reur de glissement.

Si, au contraire, il y a des erreurs de glissement,

on obt ient selon le cas :

(2) C (L)H1 ~ eL _~ CL+I ~ _~ ... _~ eL+n_l ~n-1 , OU

(3) C(n--~)H1= Cn_R~- Cn_R+I ~2~_ ..._~ C~_R+~_I~n-I.

est connu par hypoth6se, puisque C et H 1 sont

connus.

Selon le cas, le syndr6me d 'erreur sera (1), (2) ou

(3). En le divisant par ~, on obt ient 1, ~L OH ~ 1 -R,

respect ivement . On en d~duit donc le glissement qui

s 'est produit . Comme dans les codes pr6c6dents, c 'est

la r6f6rence h 1 qui indique si, oui ou non, il y a eu

glissement du mot.

La correction h par t i r de ce momen t est 6vidente.

V. G O M M E N T A I I ~ E S S U B L E S D I F F ' . R E N T S G O D E S

Tout d 'abord, il convient de remarquer que Tavares

et Fuchada ont consid6r6 l 'erreur addi t ive apr~s

l 'erreur de synchronisat ion, tandis que Bose et

Caldwell ont proc~d6 d 'une fa~on contraire.

Que l 'er reur addi t ive suive le d6calage circulaire,

selon le cas, ne modifie en rien les procedures de

ddtection st de correction.

En comparan t les codes Tavares, Fuchada et les

codes Bose, Caldwell et Weldon, nous remarquons

que ceux-ci sont protgg~s contre les erreurs en paquet

dues h l ' empi~tement des mots adjacents, tandis que

ceux-lh ont une procddure a lgor i thmique plus simple.

Pour faire une synth~se des deux, on peut donc uti-

liser ia m6thode B.C.W. de const ruct ion des roots

allong6s et la proc6dure de d6codage T.F., pour conci-

lier les avantages respectifs des deux codes. Le fait

d 'ut i l iser l ' a l longement des mots des codes B.C.W.

6vite d 'avoi r h corriger le paque t d 'erreurs addit ives

dues au glissement. I1 ne reste plus qu 'h corriger (ou

h d~tecter seulement, selon le cas) les erreurs addi-

t ives isol6es de la fa~on habituelle.

Cet avantage ne sera ~videmment obtenu qu ' au

prix d 'une baisse de rendement du code.

Quant aux proc6dures de d~tection et de correction

des erreurs de glissement, il est impor t an t de remar-

quer qu'elles sont, en fait, assez ressemblantes.

En effet, Bose, Caldwell et Weldon consid~rent le

code cyclique comme un sous-espace vectoriel et, de

ce fait, leur procedure est matricielle. Tavares et

Fuchada, au contraire, consid~rent le code cyclique

comme un id6al, et de ce fait, ut i l isent une proc6-

dure polyn6miale, qui est pr6f6rable, car elle est plus

simple h met t re en oeuvre.

La ressemblance des procddures appara i t de la

fagon suivante :

f(x) peut s '6crire f ( x ) = f o § f l x § ... § f v x p et

l 'on fl :

(i) f (~ ) = o ~=> (fo . . . . . fp) = o . P

Par cons6quent, il est clair que si l 'on analyse les

syndromes dans les codes T.F. et dans les codes

B.C.W., on a la correspondance suivante entre les

deux :

Z H 1 = ~

{z (x ) + c ' ( x ) } i = o .

o ~ { a ( x ) } f d e s i g n e ]e r e s t s de la d iv i s ion de a(z) p a r f(x).

Mais Tavares et Fuchada, par leur connaissance

des classes cycliques, ont g randement all6g6 la pro-

cddure de ddtection et de correction. De plus, ils ont donrL6 une borne minimale sur le

degr6 du facteur irr~ductible du polyn6me vdrif icateur

de parit6 utilis6 pour construire le sons-code quand

ce facteur est primitif. Si, en plus, on t ravai l le en

longueur pr imit ive, on est dans les conditions d 'appl i -

cations du th6or~me II-7. La remarque II.9 mont re en outre qu 'on peut se

rapprocher des conditions du th6or~me II-7, h condi-

t ion que le rendement du sous-code obtenu ne soit

pas trop faible.

VI. G O N C L U S I O N

La d6tection ct la correction des erreurs de glisse-

men t pr6sente un int~r~t cer ta in dans les syst~mes

numdriques h faible et moyen ddbit binaire. En effet,

la procedure de ddtection et de correction des glis-

ANN. TI}L~COMMUNIC., 32, n ~ 3-4, 1977 7/8

J . DE REFFYE. -- I2TUDE DE CODES DI~TECTEURS ET CORRECTEURS D 'ERREURS DE GLISSEMENT 1 6 5

sements parai t a priori difficilement compatible avec

les cadences impos6es par les forts d6bits. Pour ceux- ci, on a pr6f6r6 les syst6mes de t ransmission h ver- rouillage de trame, oh la phase des s ignaux est cons- t a m m e n t v6rifi4e et corrig6e tout au long du canal de transmission. Par contre, les codes d6tecteurs et

correcteurs d'erreurs de glissement peuven t 4tre tr6s

utiles en radiot616phonie num6rique locale, ou dans des r6seaux locaux h faible coht, car ils ne modif ient en rien le canal de transmission. Ils n 'agissent , en effet, que sur le ddbit de t ransmission des donn6es et ne modifient que les syst6mes de codage et de d6codage.

On peut tr6s bien cnvisager des syst6mes off la d6tection et la correction des glissements seraient assurdes par une carte enfichable, en suppl6ment de la d6tection et de la correction des erreurs addi-

tives. Le simple fait de d6brancher cette carte ne modifierait pas les autres param6tres , le syst6me corrigeant alors seulement les erreurs additives. On b6n6ficierait par contre d 'un d6bit binaire plus

impor tant .

Comme on le volt, du fait que, par principe, on utilise toute l ' infras t ructure existante pour d6tecter et corriger les erreurs additives, la d6tection et la correction d'erreurs de glissement ne repr6sentent

qu ' un faible invest issement dans tou t un syst6me de t ransmission binaire. La d6cision de d6tecter et, 6ventuellement, de corriger les glissements, se fera sur tout en fonction du type d'erreurs rencontr6 le

plus f r6quemment et du d6bit binaire minimal

admissible. Manuscri t rer le 2 juillet 1976,

r~visd le 25 janvier 1977.

BIBLIOGRAPH IE

[1] VAN LINT (J. H.). Coding theory (th6orie du codage). Lecture notes in Mathematics, n ~ 201, Springer Verlag, Berlin, (1971), 136 p.

[2] TAVAR~.S (S. E.), ALLARD (P. E.), SnlvA (S. G. S.). On the decomposition of cyclic codes into cyclic classes (De la d6composition des codes cycliques en classes cylindriques), In/or. and control, U.S.A. (mai 1971), 18, n ~ 4, pp. 342-355.

[3] ALLARD (P. E.), SHIVA (S. G. S.), TAVAnES (S. E.). A note on the decomposition of cyclic codes into cyclic classes (Une note sur la d6composition de codes cycliques en classes cycliques) In/orm. and control, U.S.A. (f6v. 1973), 22, n o 1, pp. 100-106.

[4] TAVARES (S. E.), FUCHADA (M.). Synchronization of a class of codes derived from cyclic codes (Synchroni- sation d'une classe de codes d6riv6s de codes cycliques), InJorra and control, U.S.A. (avr. 1970), 16, n ~ 2, pp. 153- 167.

[5] BOSE (R. C)., CALDWELL (J. Cx.). Synchronizable error correcting codes (Codes correcteurs d'erreurs syn- chronisables). In/orm. and control, U. S. A. (juin 1967), 10, n ~ 6, pp. 616-631.

[6] WELDON (E. J. Jr.), A note ou synchronization reco- very with extended cyclic codes (Une note sur la r6cup6ration de la synchronisation avec des codes cycliques 6tendus) In/orm. and control, U.S.A. (oct. 1968), 13, n ~ 4, pp. 354-367.

8/8 ANN. TELECOMMUNIC., 32, n ~ 3-4, 1977