[PDF] Codes Correcteurs dErreurs Les codes cycliques





Previous PDF Next PDF



1 Codes correcteurs derreurs

Exercice 1.1 Soit C le code binaire : C = {0000110000001111



TD Réseau Les codes correcteurs et les codes détecteurs Claude

Les codes correcteurs et les codes détecteurs un code détecteur et correcteur d'erreurs. ... Exercice : y a-t-il une erreur dans le mot suivant ?





Codes Correcteurs dErreurs Cours 1 + Introduction + Codes

12?/11?/2008 Capacité de détection et de correction des erreurs. Exercice. Code détecteur/correcteur d'erreur. Par codes on peut entendre plusieurs ...



Codes Correcteurs dErreurs Les codes cycliques

12?/11?/2008 Définition - Code Cycliques - Polynôme générateur. Codage et décodage avec les codes cycliques. Exercice. Détection d'erreurs - Correction ...



Exercices Codes Correcteurs

Exercices Codes Correcteurs On consid`ere le code binaire o`u on envoie 16 bits pour 9 bits significatifs de ... On rappelle qu'il corrige une erreur.



Codes correcteurs 1

24?/03?/2020 1.4 Construction des codes cycliques . ... A Corrigé des exercices ... + en?1xn?1 est le vecteur erreur de poids ? (d ? 1)2.



Chapitre12_IFT1215.ps (mpage)

CODES CORRECTEURS. Max Mignotte Détection d'erreurs groupés : Code CRC . ... sans les bits de contrôle le message corrigé est 1001. 6. CODES ...



TD. Codes correcteurs

Si on expédie des bits sur un canal binaire symétrique `a raison de 512 bits toutes les millisecondes avec une probabilité d'erreur de 1%



[PDF] Corrigé Exercice 1: 1a : P X = = C p 1 ? p = 012345 1b - LIRMM

Corrigé Exercice 1: 1 a : P X = = C p 1 ? p = 012345 1 b : L'erreur est détectée lorsque le nombre de bits erronés est 1 2 3ou 4 c-?à-?d



[PDF] 1 Codes correcteurs derreurs

1 Codes correcteurs d'erreurs Exercice 1 1 Soit C le code binaire : C = {00001100000011110101010111011101} 1 Quelle est la longueur de C ?



[PDF] TD Réseau Les codes correcteurs et les codes détecteurs Claude

? Utilisation de méthodes de détection des erreurs et éventuellement de correction des erreurs Méthodes mises en place au niveau de la couche 2 OSI ("liaison 



[PDF] codes correcteurs

Codes permettant de détecter des erreurs • Code auto correcteurs Détection et correction d'une ou plusieurs erreurs BER Bit Error Rate



[PDF] TIPE : Code correcteur derreurs

Nous allons nous pencher sur les principaux codes correcteurs binaires et voir comment se déroule le codage et la correction d'erreurs notamment pour les codes 





[PDF] Mathématiques des codes correcteurs derreurs - Institut Fourier

a l'écart de C d = 3 donc C corrige une erreur Exemple Soit C3 le code de Hamming binaire de longueur 7 et de dimension 4 Alors sa matrice de correction 



[PDF] Exercices Codes Correcteurs - ENSIIE

Exercice 2 On consid`ere le code binaire o`u on envoie 16 bits pour 9 bits Exercice 7 (Correction d'erreurs) On rappelle qu'il corrige une erreur



[PDF] codes correcteurs derreurs Les premiers exercices de cette feuille

Les codes binaires ayant une distance minimum égale à 3 sont très intéressants car ce sont les premiers codes permettant la correction d'erreur de transmission 



[PDF] Codes correcteurs derreurs

qu'on le décode comme un mot de C `a distance minimum de r On dit que C est t-correcteur (ou corrige t erreurs) quand toute erreur portant sur au plus t bits 

:
Codes Correcteurs dErreurs Les codes cycliques

Codes Cycliques

Fin de la partie code lin´eaire en blocs

Codes Correcteurs d"Erreurs

Les codes cycliquesMarc Chaumont

November 12, 2008

Marc ChaumontIntroduction

Codes Cycliques

Fin de la partie code lin´eaire en blocsRappel sur les polynˆomes D´efinition - Code Cycliques - Polynˆome g´en´erateur

Codage et d´ecodage avec les codes cycliques

Exercice

D´etection d"erreurs - Correction d"erreurs

Exercice

Plan

1Codes Cycliques

Rappel sur les polynˆomes

D´efinition - Code Cycliques - Polynˆome g´en´erateur

Codage et d´ecodage avec les codes cycliques

Exercice

D´etection d"erreurs - Correction d"erreurs

Exercice

2Fin de la partie code lin´eaire en blocs

Conclusion

Marc ChaumontIntroduction

Codes Cycliques

Fin de la partie code lin´eaire en blocsRappel sur les polynˆomes D´efinition - Code Cycliques - Polynˆome g´en´erateur

Codage et d´ecodage avec les codes cycliques

Exercice

D´etection d"erreurs - Correction d"erreurs

Exercice

D´efinition

Unpolynˆome`a coefficients dansF2est une fonction de la formeP(X) =a0+a1X+a2X2+...+anXnavec?i? {0,...,n},ai?F2;Sian?= 0, l"entiernest appel´e ledegr´edu polynˆomePet not´e

deg(P) ;Les entiersaisont appel´es les coefficients de P ;DansF2,(a+b)2=a2+b2.Marc ChaumontIntroduction

Codes Cycliques

Fin de la partie code lin´eaire en blocsRappel sur les polynˆomes D´efinition - Code Cycliques - Polynˆome g´en´erateur

Codage et d´ecodage avec les codes cycliques

Exercice

D´etection d"erreurs - Correction d"erreurs

Exercice

Division Euclidienne

Division polynomiale

SoitP1etP2deux polynˆomes `a coefficients dansF2. Il existe deux polynˆomes `a coefficients dansF2,QetR, uniques, tels queP1= P

2×Q+Retdeg(R) Rest appel´e lerestede la division euclidienne deP1parP2.Marc ChaumontIntroduction

Codes Cycliques

Fin de la partie code lin´eaire en blocsRappel sur les polynˆomes D´efinition - Code Cycliques - Polynˆome g´en´erateur

Codage et d´ecodage avec les codes cycliques

Exercice

D´etection d"erreurs - Correction d"erreurs

Exercice

Plan

1Codes Cycliques

Rappel sur les polynˆomes

D´efinition - Code Cycliques - Polynˆome g´en´erateur

Codage et d´ecodage avec les codes cycliques

Exercice

D´etection d"erreurs - Correction d"erreurs

Exercice

2Fin de la partie code lin´eaire en blocs

Conclusion

Marc ChaumontIntroduction

Codes Cycliques

Fin de la partie code lin´eaire en blocsRappel sur les polynˆomes D´efinition - Code Cycliques - Polynˆome g´en´erateur

Codage et d´ecodage avec les codes cycliques

Exercice

D´etection d"erreurs - Correction d"erreurs

Exercice

Code Cycliques

Code Cycliques

SoitCl"ensemble des mots de code d"un code [n,k,dmin]. Le code est ditcycliquesi l"ensemble des mots du code eststable pard´ecalage circulaire.Dit autrement Si l"on dispose d"une fonctionσde permutation circulaire telle que σ(c1,c2,...,cn) =cn,c1,c2,...,cn-1, un codeCest cyclique si?c?

C,σ(c)?CMarc ChaumontIntroduction

Codes Cycliques

Fin de la partie code lin´eaire en blocsRappel sur les polynˆomes D´efinition - Code Cycliques - Polynˆome g´en´erateur

Codage et d´ecodage avec les codes cycliques

Exercice

D´etection d"erreurs - Correction d"erreurs

Exercice

Les codes cycliques

Quelques codes cycliques ...

Les codes de r´ep´etitions pures [n,k,.] sont cyliques,Les codes par bit de parit´e est cyclique,

Le code de Hamming [7,4,3] est cyclique; et plus g´en´eralement certains codes de Hamming,Certains codes simplexes [2 k-1,k,2k-1] (Les colonnes de la matrice g´en´eratrice sont une ´enum´eration deFk2except´e le vecteur nul)

Marc ChaumontIntroduction

Codes Cycliques

Fin de la partie code lin´eaire en blocsRappel sur les polynˆomes D´efinition - Code Cycliques - Polynˆome g´en´erateur

Codage et d´ecodage avec les codes cycliques

Exercice

D´etection d"erreurs - Correction d"erreurs

Exercice

Les codes cycliques

Code cycliques engendr´e par un mot

(l"image d")Uncode cyclique engendr´epar un motm? {0,1}n est compos´e du vecteur nul ainsi que de tous les vecteurs obtenables par d´ecalage circulaire dem.Marc ChaumontIntroduction

Codes Cycliques

Fin de la partie code lin´eaire en blocsRappel sur les polynˆomes D´efinition - Code Cycliques - Polynˆome g´en´erateur

Codage et d´ecodage avec les codes cycliques

Exercice

D´etection d"erreurs - Correction d"erreurs

Exercice

Exercice :

Quel est le code lin´eaire (en bloc) cyclique engendr´e par 111 ?

Marc ChaumontIntroduction

Codes Cycliques

Fin de la partie code lin´eaire en blocsRappel sur les polynˆomes D´efinition - Code Cycliques - Polynˆome g´en´erateur

Codage et d´ecodage avec les codes cycliques

Exercice

D´etection d"erreurs - Correction d"erreurs

Exercice

Correction :

Marc ChaumontIntroduction

Codes Cycliques

Fin de la partie code lin´eaire en blocsRappel sur les polynˆomes D´efinition - Code Cycliques - Polynˆome g´en´erateur

Codage et d´ecodage avec les codes cycliques

Exercice

D´etection d"erreurs - Correction d"erreurs

Exercice

G´en´erateur d"un code cyclique

G´en´erateur d"un code cyclique

SoitC(l"image d") uncode cyclique[n, k, .]

Il existe ununique polynˆomeg(X) =a0+a1X+a2X2+...+an-kXn-k

avecan-k= 1 tel que :g(X) est un diviseur deXn+ 1,Cest le code cyclique engendr´e parm=a0a1...an-k0...0 (Il y ak-1

z´eros en fin dem),Les motsm=a0a1...an-k0...0;σ(m) = 0a0a1...an-k0...0; ...; σ(m)k-1= 0...0a0a1...an-kforment une base de C. La matrice g´en´eratrice de C est donc donn´ee par : ??a

0a1...an-k0 0... ...0

0a0...an-k-1an-k0... ...0

0 0...0a0a1... ...an-k?

??Marc ChaumontIntroduction

Codes Cycliques

Fin de la partie code lin´eaire en blocsRappel sur les polynˆomes D´efinition - Code Cycliques - Polynˆome g´en´erateur

Codage et d´ecodage avec les codes cycliques

Exercice

D´etection d"erreurs - Correction d"erreurs

Exercice

Polynˆome g´en´erateur

Repr´esentation polynomiale

Soitm=a0a1...anun mot de longueurn. On appelle

repr´esentation polynomialedemle polynˆomea0+a1X+...+anXn.Remarque 1: Dor´enavant, on identifiera syst´ematiquement un mot avec sa repr´esentation polynomiale.Polynˆome g´en´erateur

Soit C un codecyclique[n,k,dmin]. On appelle polynˆome g´en´erateur de C le polynˆomeg(X) d´efini par le th´eor`eme

pr´ec´edement.Remarque 1 : Dor´enavant, on identifiera syst´ematiquement un code cyclique par son polynˆome g´en´erateur.

Marc ChaumontIntroduction

Codes Cycliques

Fin de la partie code lin´eaire en blocsRappel sur les polynˆomes D´efinition - Code Cycliques - Polynˆome g´en´erateur

Codage et d´ecodage avec les codes cycliques

Exercice

D´etection d"erreurs - Correction d"erreurs

Exercice

Exemple de polynˆome g´en´erateur

Le polynˆome g´en´erateur du code de r´ep´etition pure [n, 1, .] est

1 +X+X2...+Xn-1Le polynˆome g´en´erateur du code par bit de parit´e [n, n-1, .] est

1 +XLespolynˆomes g´en´erateurs du code de Hamming [7, 4, 3] sont

1 +X+X3et 1 +X2+X3.Marc ChaumontIntroduction

Codes Cycliques

Fin de la partie code lin´eaire en blocsRappel sur les polynˆomes D´efinition - Code Cycliques - Polynˆome g´en´erateur

Codage et d´ecodage avec les codes cycliques

Exercice

D´etection d"erreurs - Correction d"erreurs

Exercice

Remarque sur l"occupation m´emoire des diff´erentes cat´egories de codes en blocsLes codesen blocs quelconquesn´ecessitent de d´esigner les 2k

mots de codes ainsi que la fonction de codage,Les codesen blocs lin´eaires quelconquessont d´ecrits par leur

matrice g´en´eratrice de dimensionn×k.Les codesen blocs cycliquessont d´ecrits par un polynˆome

compos´e den-kcoefficients.Marc ChaumontIntroduction

Codes Cycliques

Fin de la partie code lin´eaire en blocsRappel sur les polynˆomes D´efinition - Code Cycliques - Polynˆome g´en´erateur

Codage et d´ecodage avec les codes cycliques

Exercice

D´etection d"erreurs - Correction d"erreurs

Exercice

Plan

1Codes Cycliques

Rappel sur les polynˆomes

D´efinition - Code Cycliques - Polynˆome g´en´erateur

Codage et d´ecodage avec les codes cycliques

Exercice

D´etection d"erreurs - Correction d"erreurs

Exercice

2Fin de la partie code lin´eaire en blocs

Conclusion

Marc ChaumontIntroduction

Codes Cycliques

Fin de la partie code lin´eaire en blocsRappel sur les polynˆomes D´efinition - Code Cycliques - Polynˆome g´en´erateur

Codage et d´ecodage avec les codes cycliques

Exercice

D´etection d"erreurs - Correction d"erreurs

Exercice

Codage

Codage

SoitCun code cyclique de polynˆome g´en´erateur g(X). Soituun mot de source de repr´esentation polynomialePu(X). Le mot image correspondant (c"est-a-dire le mot de code correpondant) a pour repr´esentation polynomialePu(X)×g(X).Marc ChaumontIntroduction

Codes Cycliques

Fin de la partie code lin´eaire en blocsRappel sur les polynˆomes D´efinition - Code Cycliques - Polynˆome g´en´erateur

Codage et d´ecodage avec les codes cycliques

Exercice

D´etection d"erreurs - Correction d"erreurs

Exercice

Plan

1Codes Cycliques

Rappel sur les polynˆomes

D´efinition - Code Cycliques - Polynˆome g´en´erateur

Codage et d´ecodage avec les codes cycliques

Exercice

D´etection d"erreurs - Correction d"erreurs

Exercice

2Fin de la partie code lin´eaire en blocs

Conclusion

Marc ChaumontIntroduction

Codes Cycliques

Fin de la partie code lin´eaire en blocsRappel sur les polynˆomes D´efinition - Code Cycliques - Polynˆome g´en´erateur

Codage et d´ecodage avec les codes cycliques

Exercice

D´etection d"erreurs - Correction d"erreurs

Exercice

Exercice

Soit le polynˆome g´en´erateurg(X) = 1 +X+X3.1Donner lemot de codedu mot issu du codage deu= 1101,2Donner lamatrice g´en´eratrice Gassoci´ee au polynˆome g´en´erateur,3V´erifier que le mot de code obtenu paru×Gest le mˆeme que

celui obtenu en question 1.

Marc ChaumontIntroduction

Codes Cycliques

Fin de la partie code lin´eaire en blocsRappel sur les polynˆomes D´efinition - Code Cycliques - Polynˆome g´en´erateur

Codage et d´ecodage avec les codes cycliques

Exercice

D´etection d"erreurs - Correction d"erreurs

Exercice

Correction

Marc ChaumontIntroduction

Codes Cycliques

Fin de la partie code lin´eaire en blocsRappel sur les polynˆomes D´efinition - Code Cycliques - Polynˆome g´en´erateur

Codage et d´ecodage avec les codes cycliques

Exercice

D´etection d"erreurs - Correction d"erreurs

Exercice

Correction

Marc ChaumontIntroduction

Codes Cycliques

Fin de la partie code lin´eaire en blocsRappel sur les polynˆomes D´efinition - Code Cycliques - Polynˆome g´en´erateur

Codage et d´ecodage avec les codes cycliques

Exercice

D´etection d"erreurs - Correction d"erreurs

Exercice

Plan

1Codes Cycliques

Rappel sur les polynˆomes

D´efinition - Code Cycliques - Polynˆome g´en´erateur

Codage et d´ecodage avec les codes cycliques

Exercice

D´etection d"erreurs - Correction d"erreurs

Exercice

2Fin de la partie code lin´eaire en blocs

Conclusion

Marc ChaumontIntroduction

Codes Cycliques

Fin de la partie code lin´eaire en blocsRappel sur les polynˆomes D´efinition - Code Cycliques - Polynˆome g´en´erateur

Codage et d´ecodage avec les codes cycliques

Exercice

D´etection d"erreurs - Correction d"erreurs

Exercice

D´etection d"erreurs

D´etection d"erreurs

Un motcestun mot de codesi et seulement si sarepr´esentation polynomialeestdivisiblepar lepolynˆome g´en´erateurg(X) (le reste de la division par g(X) doit ˆetre nul).

Marc ChaumontIntroduction

Codes Cycliques

Fin de la partie code lin´eaire en blocsRappel sur les polynˆomes D´efinition - Code Cycliques - Polynˆome g´en´erateur

Codage et d´ecodage avec les codes cycliques

Exercice

D´etection d"erreurs - Correction d"erreurs

Exercice

Exercice : D´etection d"erreurs

Soit le polynˆome g´en´erateurg(X) = 1 +X+X3du code de Ham- ming C[7, 4, 3]. Le mot 1010001 est-il un mot de code ?

Marc ChaumontIntroduction

Codes Cycliques

Fin de la partie code lin´eaire en blocsRappel sur les polynˆomes D´efinition - Code Cycliques - Polynˆome g´en´erateur

Codage et d´ecodage avec les codes cycliques

Exercice

D´etection d"erreurs - Correction d"erreurs

Exercice

Exercice : Correction

Marc ChaumontIntroduction

Codes Cycliques

Fin de la partie code lin´eaire en blocsRappel sur les polynˆomes D´efinition - Code Cycliques - Polynˆome g´en´erateur

Codage et d´ecodage avec les codes cycliques

Exercice

D´etection d"erreurs - Correction d"erreurs

Exercice

Remarque

On vient de voir `a travers les exercices qu"il est possible de g´en´erer un code correcteur par multiplication par le poly- nome g´en´erateur,et qu"il est posible de d´etecter une erreur par division par le polynˆome g´en´erateur.

Marc ChaumontIntroduction

Codes Cycliques

Fin de la partie code lin´eaire en blocsRappel sur les polynˆomes D´efinition - Code Cycliques - Polynˆome g´en´erateur

Codage et d´ecodage avec les codes cycliques

Exercice

D´etection d"erreurs - Correction d"erreurs

Exercice

D´ecodage

Matrice de contrˆole

La matrice de contrˆole associ´ee `a la matrice g´en´eratriceG(cf. trans- parent pr´ec´edent) est : H=? ??b kbk-1...b00...0

0bkbk-1...b0...0

0...0bkbk-1...b0?

avech(X) =b0+b1X+...+bkXkle polynˆome d´efini par : h(X) =Xn+ 1g(X).Marc ChaumontIntroduction

Codes Cycliques

Fin de la partie code lin´eaire en blocsRappel sur les polynˆomes D´efinition - Code Cycliques - Polynˆome g´en´erateur

Codage et d´ecodage avec les codes cycliques

Exercice

D´etection d"erreurs - Correction d"erreurs

Exercice

Syndrome

Syndrome

Soitrun mot re¸cu de repr´esentation polynomialer(X) =c(X) + e(X), o`uc(X) est un mot de code en repr´esentation polynomiale, ete(X) est l"erreur en repr´esentation polynomiale. Le syndrˆome en repr´esentation polynomiale est : s(X) =r(X)mod g(X) =e(X)mod g(X)Le calcul du syndrome en repr´esentation polynomiale est : rapide (division de polynˆome), quand la capacit´e de d´ecodagetest faible (Hamming, Golay) il est peu couteux calculatoirement de remonter l"erreure(X).Marc ChaumontIntroduction

Codes Cycliques

Fin de la partie code lin´eaire en blocsRappel sur les polynˆomes D´efinition - Code Cycliques - Polynˆome g´en´erateur

Codage et d´ecodage avec les codes cycliques

Exercice

D´etection d"erreurs - Correction d"erreurs

Exercice

Plan

1Codes Cycliques

Rappel sur les polynˆomes

D´efinition - Code Cycliques - Polynˆome g´en´erateur

Codage et d´ecodage avec les codes cycliques

Exercice

D´etection d"erreurs - Correction d"erreurs

Exercice

2Fin de la partie code lin´eaire en blocs

Conclusion

Marc ChaumontIntroduction

Codes Cycliques

Fin de la partie code lin´eaire en blocsRappel sur les polynˆomes D´efinition - Code Cycliques - Polynˆome g´en´erateur

Codage et d´ecodage avec les codes cycliques

Exercice

D´etection d"erreurs - Correction d"erreurs

Exercice

Exercice

Soit le polynˆome g´en´erateurg(X) = 1 +X+X3du code de Ham- ming C[7,4, 3].1Donner le polynˆome permettant d"obtenir la matrice de contrˆole,

2puis donner la matrice de contrˆole,

3enfin, le mot 1010001 est-il un mot de code ?

Marc ChaumontIntroduction

quotesdbs_dbs29.pdfusesText_35

[PDF] code de hamming pdf

[PDF] code de l'éducation 2017

[PDF] code de l'éducation creation

[PDF] code de l'éducation pdf

[PDF] code de l'éducation punition

[PDF] code de l'éducation simplifié

[PDF] code de l'éducation sanctions

[PDF] confiscation téléphone portable au travail

[PDF] confiscation portable loi

[PDF] confiscation portable loi quebec

[PDF] nouveau code de la route maroc 2016 pdf

[PDF] projet de loi 116-14 pdf

[PDF] panneaux de signalisation routière ? imprimer

[PDF] signification des panneaux de signalisation routière

[PDF] tout les panneaux de signalisation a imprimer