Introduction aux codes correcteurs d’erreurs
le cas du code de r´ep´etition pure (1,3), mais c’est impraticable d`es que k est grand Or, pour satisfaire le point 1, il est clair que k doit ˆetre grand b) A priori, rien ne garantit que le mot de code qui r´ealise le minimum de d(r,m) soit unique C’est le cas du code de r´ep´etition pure (1,3), mais les codes ayant
TIPE : Code correcteur derreurs
La capacité de détection d'erreurs d'un code est naturellement plus éle-vée : on peut détecter toute erreur evéri ant w(e)
CODES CORRECTEURS D’ERREURS
(527) Codes correcteurs d’erreurs Il est clair que ce jeu est un exemple de code correcteur d’erreurs : le spectateur envoie un message m 1 m7 (formé du nombre compris entre 0 et 15, dont l’écriture en base deux est
Codes correcteurs d’erreurs
code Soit C(p) = 1 + plog 2 p+ (1 p)log 2 (1 p): Un th eor eme de Shannon montre que pour une probabilit e d’erreur p
Codes Correcteurs dErreurs Cours 1 + Introduction + Codes
Exemple de code d´etecteur et correcteur d’erreur : le code de r´ep´etition Technique de codage : Pour un bit d’information, 3 bits sont envoy´es (cad cod´es) tels que: 0 → 000 1 → 111 Technique de d´ecodage : Le d´ecodage se fait par vote majoritaire Par exemple, si le mot re¸cu est 001, alors on d´eduit que le bit ´emis
Theorie des codes´ correcteurs d’erreurs I
est appelée probabilité d'erreur, elle dépend du canal de transmission et non du code 3) Si on code oui par 111 et non par 000 C= f000;111g Après transmission de 111, si on reçoit 111 on admet que c'est bon Si on reçoit 011, 110 ou 101 on constate qu'il y a erreur ce ne sont pas des mots de C 000 est peut probable de le recevoir
Codes correcteurs derreurs - u-bourgognefr
110101 Il ne s’agit pas d’un mot du code et on peut affirmer qu’au moins une erreur est apparue En ne changeant qu’un seul bit, on peut former le mot du code 010101 mais on peut egalement obtenir d’autres mots du code en changeant plus´ d’un bit On suppose donc que le mot du code correct est 010101 et on corrige donc 110101 en
TD : Codes de détection et de correction d’erreurs
3 Quel est le code du mot [1101011]? 4 Quelle condition vérifie le code s’il n’y a pas eu d’erreur? 5 Quelle condition vérifie le code si le bit k a été altéré? Comment fait-on pour le corriger? 6 Quel est le message correspondant au code [11111011100]? 4 Parité bidimensionnelle (block sum check)
[PDF] code bch pdf
[PDF] code en bloc linéaire exercice corrigé
[PDF] code cyclique
[PDF] matrice génératrice code hamming
[PDF] codex seraphinianus français
[PDF] rohonc codex pdf
[PDF] codex seraphinianus français pdf
[PDF] codex seraphinianus alphabet
[PDF] codex seraphinianus pdf
[PDF] codex seraphinianus fnac
[PDF] léonard de vinci et les secrets du codex atlanticus
[PDF] leonard de vinci codex atlanticus
[PDF] codex arundel
[PDF] leonard de vinci biographie pdf
![Codes correcteurs d’erreurs Codes correcteurs d’erreurs](https://pdfprof.com/Listes/17/32732-17code-correcteurs.pdf.pdf.jpg)
Codes correcteurs d'erreurs
Christophe Ritzenthaler
Sources.Le cours Codes correcteurs de Coste, Paugam et Quarez disponible sur le web a l'adressehttp://agreg-maths.univ-rennes1.fr/documentation/docs/codes.pdf. Les livres `An introduction to error correcting codes with applications' de Vanstone et van Oorschot et `Error-correcting codes and nite elds' de Pretzel. Les codes correcteurs ont ete introduits pour corriger les erreurs de transmission ou de lecture de donnees numeriques, ou les erreurs survenant au cours de leur inscription sur un support physique (bande, CD) ou encore lorsque les donnees subissent une alteration sur le support de stockage. Voici quelques domaines ou ils sont appliques : | transmissions spatiales; | minitel; | codes barres; | disque compact et DVD; | communications par internet.1 Codes et distance de Hamming
Les messages transmis sont supposes decoupes en blocs (ou mots) de longueurnecrits avec l'alphabetf0;1g. Uncode(binaire) est un sous-ensembleCde l'ensemblef0;1gnde tous les mots possibles. On dit quenest la longueur deC. Ladistance de Hammingentre deux motsx= (x1;:::;xn) ety= (y1;:::;yn), que l'on notera d(x;y), est le nombre d'indicesitels quexi6=yi. C'est bien une distance surf0;1gn. La distance minimumdu codeCest le minimum desd(x;y) pourxetydes mots dierents de C(on suppose queCa au moins 2 mots!). On la notera toujoursd.Exemple 1.ConsidereC=fc0;c1;c2;c3gavec
c0= (00000); c1= (10110); c2= (01011); c3= (11101):
C'est un code de longueur5et de distanced= 3.
Le motc2Cest emis et, apres d'eventuelles erreurs de transmission, le motr2 f0;1gn est recu. On decode le motrselon le principe du maximum de vraisemblance, c.-a-d. qu'on le decode comme un mot deCa distance minimum der. On dit queCestt-correcteur (ou corrigeterreurs) quand toute erreur portant sur au plustbits est corrigee correctement. On voit donc que le codeCestt-correcteur si et seulement si les boules fermees (dansf0;1gn muni de la distance de Hamming) de centres les elements deCet de rayontsont disjointes, ou encore si et seulement si la distance minimumddeCveried2t+ 1. Il est souvent dicile de calculer la distance minimale et plus encore de decoder un mot sans structure additionnel c'est pourquoi on prefere travailler avec des codes lineaires. 1 Remarque 1.Supposons que#C= 2k. Le rapportk=ns'appelle le taux de transmission du code. SoitC(p) = 1 +plog2p+ (1p)log2(1p):
Un theoreme de Shannon montre que pour une probabilite d'erreurp < :5a chaque bit, il existe un code dont le taux de transfert est inferieur mais arbitrairement proche deC(p)qui peut corriger tout message avec une probabilite arbitrairement proche de1. Par exemple si p=:001, on aC(p) =:986donc en ajoutant a peine15bits pour1000bits transmis on peut arriver a une correction arbitrairement proche de1. Bien s^ur le theoreme de Shannon ne dit pas comment construire de tels codes.2 Codes lineaires
2.1 Denitions
On noteF2le corps a deux elements 0 et 1. Les mots de longueursnsont les elements de F n2, que l'on ecrira comme des vecteurs lignes. Un code lineaire de longueurnest un sous- espace vectorielCFn2. La lettrekdesignera toujours la dimension deC(comme espace vectoriel). Le nombre de mots du codeCest 2k. Lepoidsd'un motx= (x1;::::;xn)2Fn2, notew(x), est le nombre d'indicesitels quexi6= 0. Commed(x;y) =w(xy), la distance minimumdd'un code lineaireCest le minimum des poidsw(x) pourx2Cnon nul. (On suppose queCn'est pas le code nul.) On regroupe les trois parametresn;ketdd'un code lineaireCen disant queCest de type (n;k;d). Lemme 2.1([Dem, Prop.9.1],[Pre, 18.4]).On a toujoursd+kn+1(borne de Singleton). Demonstration.SoitVle sous espace deFn2engendre par les vecteurs donc lesd1 premieres coordonnees sont nulles. Considerons le codeC\V. Sa longueur estnd+1. Montrons que sa dimension est toujoursk. En eet sinon, cela veut dire qu'il existe une relation lineaire entre leskvecteurs engendrantCa valeur dans un supplementaire deV. Mais ceci veut dire qu'il existe un element deCde poidsd1, ce qui est exclu. Ainsi on aknd+ 1, cequ'on voulait.La borne de Singleton quantie le fait qu'on ne peut pas avoir a la fois le beurre (une capa-
cite de correction importante) et l'argent du beurre (un nombre de mots de code important), pour une longueurnxee. Remarque 2.Il existe d'autres bornes. Par exemple la borne de Hamming. SiBest la boule de centre0et de rayonrdansFn2, elle contientR=Pr k=0 n kmots. Ainsi siCest un code de longueurnet de distance minimaled= 2r+ 1alorsCa au plus2n=Rmots de code. Lemme 2.2.SiCest un code lineaire de type(n;k;d), on denit le code etendu~Ccomme le code forme des mots(x1;:::;xn+1)2Fn+12tels que(x1;:::;xn)2CetPn+1 i=1xi= 0. Le type de ~Cest(n+ 1;k;d+ 1)sidest impair et(n+ 1;k;d)sidest pair. Demonstration.Le seul parametre a determine est la distance minimale. Soitxun mot de poidsddeC. Sidest pair alorsy= (x;0)2~Cetw(y) =d. Sidest impair alorsy= (x;1)2~C etw(y) =d+ 1.2