Codeurs BCH

Codes BCH, Reed Solomon et leurs applicationsAlexandra Bruasse-Bac

Codes BCH, Reed Solomon et leurs applications p.1/29

Rsum des codes BCH et Reed-Solomon


Codes cycliquesUn code cyclique est :

un code linaire si (x1 , . . . , xn ) C alors (xn , x1 , . . . , xn1 ) C




Reprsentation polynomiale :m = (a0 , . . . , an1 )

reprsent par(m) = a0 + a1 X + + an1 X n1




Reprsentation polynomiale :m = (a0 , . . . , an1 )

reprsent par(m) = a0 + a1 X + + an1 X n1

Proprit C est cyclique ssi : si P (X) (C) pour tout polynme Q,Q(X) P (X)[X n 1] (C)


Codes cycliques

Un code cyclique C est engendr par un polynme P0 unitaire tel que P0 | X n 1C = (P0 K[X])/(X n 1)


Codes cycliquesSi P0 (X) = a0 + a1 X + + at X t ,0 0 a0 a1 a2 a t 0 a 0 a1 a2 a t 0 0 . . . .. ... ... ... ... ... ... . G= . . . 0 0 a 0 a1 a2 a t 0 0 0 a 0 a1 a2 a t



Base de (C) :P0 , X P0 , . . . X nt1 P0



Base de (C) :P0 , X P0 , . . . X nt1 P0

C de dimension k = n t


Codes cycliques

CodageKk1 [X] Kn1 [X] P P P0


Codes cycliquesComme P0 | X n 1 :P0 Q = X n 1


Codes cycliquesComme P0 | X n 1 :P0 Q = X n 1

Si Q = b0 + b1 X + + bk X kbk bk1 bk2 b0 0 b0 0 bk bk1 bk2 0 . . .. ... ... ... ... ... H= . . 0 0 bk bk1 bk2 0 0 bk bk1 bk2 0 0 ... . . . b0 0 b0


Codes cycliques

G : encodeur non systmatique


Codes cycliques


Distance minimale ? Capacit de correction


Codes cycliques


Distance minimale ? Capacit de correction Codes BCH


Codes BCHThorme des codes BCHC code cyclique sur Fq :

longueur n, engendr par P0 .

pgcd(n, q) = 1,

L racines n-imes de lunit sur Fq ( lment primitif).


Codes BCHThorme des codes BCHC code cyclique sur Fq :

longueur n, engendr par P0 .

pgcd(n, q) = 1,

L racines n-imes de lunit sur Fq ( lment primitif).

Si r , r+1 , . . . , r+2 racines de P0 dans L,d(C)


Codes BCH

appel distance construite


Codes BCH


Code BCH


Codes BCH


Code BCH

Les plus utiliss : codes primitifn = qt 1 L = Fq t


Codes de Reed Solomon

Un code de Reed-Solomon est un code BCH de longueur 2m 1 sur F2m .



Un code de Reed-Solomon est un code BCH de longueur 2m 1 sur F2m . On a L = F2m (soit lment primitif de L) :P0 (X) = (X i )(X i+1 ) (X i+r1 )



Un code de Reed-Solomon est un code BCH de longueur 2m 1 sur F2m . On a L = F2m (soit lment primitif de L) :P0 (X) = (X i )(X i+1 ) (X i+r1 )

distance minimale : r + 1


Codes de Reed SolomonRsum : n = 2m 1, k = 2m r 1, d=r+1

d=nk+1


Codes de Reed SolomonRsum : n = 2m 1, k = 2m r 1, d=r+1

d=nk+1

Codes maximaux


Qui sert quoi ...


Codage des CDs

Bas sur un code de Reed-Solomon sur F8[255, 251, 5]


Codage des CDs

Bas sur un code de Reed-Solomon sur F8[255, 251, 5] Codes de Reed-Solomon [255, 251, 5] raccourcis : [28, 24, 5] et [32, 28, 5]


Codage des CDs

Bas sur un code de Reed-Solomon sur F8[255, 251, 5] Codes de Reed-Solomon [255, 251, 5] raccourcis : [28, 24, 5] et [32, 28, 5] Technique dentrelacement

Erreurs sur les Cds par paquets (rayures)


Codage des CDs

Entrelacement simple :

mot

envoi colonne par colonne


Codage des CDs

Entrelacement simple :

mot

envoi colonne par colonne


Codage des CDs

Entrelacement avec retard :


Codage des CDs

C.I.R.C. Cross Interleave Reed-Solomon Code[28, 24, 5] 6 32 bits = 24 octetsEntrelacement avec retard 4 (profondeur 8)

[32, 28, 5]


Codage des CDs

C.I.R.C. Cross Interleave Reed-Solomon Code[28, 24, 5] 6 32 bits = 24 octetsEntrelacement avec retard 4 (profondeur 8)

[32, 28, 5]

aussi utilis pour les DAT


Codage Minitel

Mode de transmission assez able.


Codage Minitel

Mode de transmission assez able. Codes de Hamming


Codage Minitel

Mode de transmission assez able. Codes de Hamming

Paquets de 15 octets (120 bits) Hamming sur F2 avec n = 7[127, 120, 3]

Ajout dun bit de parit (bit de validation)


Codages utiliss pour la transmission dimages

Transmission dimages noire et blanc : Reed-Muller [32, 6, 16]



Transmission dimages noire et blanc : Reed-Muller [32, 6, 16] Assez efcaces sur des mots courts Codage/Dcodages efcaces



Transmission dimages noire et blanc : Reed-Muller [32, 6, 16] Assez efcaces sur des mots courts Codage/Dcodages efcaces Images complexes : Reed-Solomon [255, 223, 33] plus compression


Le systme CDPD

CDPD (cellular digital packet data) construit sur AMPS

stations mobiles stations dinterconnexion stations de base

Les erreurs de transmission (base-mobile) ne sont pas acceptables


Le systme CDPD

CDPD (cellular digital packet data) construit sur AMPS

stations mobiles stations dinterconnexion stations de base

Les erreurs de transmission (base-mobile) ne sont pas acceptables Reed-Solomon sur code compress


Et les codes de Hamming ...

Utiliss pour la correction sur :

supports assez ables mots courts ncessitant des taux bas (ajout de peu de bits)


Et les codes de Hamming ...

Utiliss pour la correction sur :

supports assez ables mots courts ncessitant des taux bas (ajout de peu de bits)

Exemples :

mmoire DRAM (ECC : correction et dtection) disques durs bus SCSI, RAID


Autres codes correcteursLes grandes catgories dautres codes :

codes de Goppa (codes elliptiques) turbo codes (combinaison de plusieurs codes) codes de Golay (Hamming amliors)

Cependant de nombreuses transmissions nutilisent pas de correction




Cependant de nombreuses transmissions nutilisent pas de correction Sil est facile de retransmettre :




Cependant de nombreuses transmissions nutilisent pas de correction Sil est facile de retransmettre : detection retransmission si ncessaire


Checksum et CRCBut : dtection derreurs retransmission plus simple que correction


Checksum et CRCBut : dtection derreurs retransmission plus simple que correction Checksum : somme des bits du message modulo 256


Checksum et CRCBut : dtection derreurs retransmission plus simple que correction Checksum : somme des bits du message modulo 256 augmenter la complexit


Checksum et CRCBut : dtection derreurs retransmission plus simple que correction Checksum : somme des bits du message modulo 256 augmenter la complexit

CRC : Reste dune division par un polynme de F2 [X]


Checksum et CRCMessage mot binaire polynme F2 [X]


Checksum et CRCMessage mot binaire polynme F2 [X] 6 23


Checksum et CRCMessage mot binaire polynme F2 [X] 6 23 00000110 00010111


Checksum et CRCMessage mot binaire polynme F2 [X] 6 23 00000110 00010111 M (X) = X 10 +X 9 +X 4 +X 2 +X +1



Polynme gnrateur G(X) de degr r



Polynme gnrateur G(X) de degr rT (X) = (X r M (X))/G(X)



Polynme gnrateur G(X) de degr rT (X) = (X r M (X))/G(X)

Message transmisM (X) T (X)


Checksum et CRCPolynmes standardiss :

CRC-12 = X 12 + X 11 + X 3 + X 2 + X + 1 CRC-16 = X 16 + X 15 + X 2 + 1 CRC-CCITT = X 16 + X 12 + X 5 + 1




Exemple prcdent avec CRC-12 : X 12 (X 10 + X 9 + X 4 + X 2 + X + 1) = X 22 + X 21 + X 16 + X 14 + X 13 + X 12




Exemple prcdent avec CRC-12 : X 12 (X 10 + X 9 + X 4 + X 2 + X + 1) = X 22 + X 21 + X 16 + X 14 + X 13 + X 12 (X 22 + X 21 + X 16 + X 14 + X 13 + X 12 )/CRC-12 = X 10 + X 7 + X 3




Exemple prcdent avec CRC-12 : X 12 (X 10 + X 9 + X 4 + X 2 + X + 1) = X 22 + X 21 + X 16 + X 14 + X 13 + X 12 (X 22 + X 21 + X 16 + X 14 + X 13 + X 12 )/CRC-12 = X 10 + X 7 + X 3 Do CRC(6 23) = 10010001000




Exemple prcdent avec CRC-12 : X 12 (X 10 + X 9 + X 4 + X 2 + X + 1) = X 22 + X 21 + X 16 + X 14 + X 13 + X 12 (X 22 + X 21 + X 16 + X 14 + X 13 + X 12 )/CRC-12 = X 10 + X 7 + X 3 Do CRC(6 23) = 10010001000 Mot envoy : (X 10 + X 9 + X 4 + X 2 + X + 1) (X 10 + X 7 + X 3 ) = X 9 + X 7 + X 4 + X 3 + X 2 + X + 1


Checksum et CRC

En gnral : transmission dans les rseaux dtection derreurs checksum ou CRC protocole inclut acquittement


PAR et RAR

Mcanisme des RAR et PAR :

archives compresses et coupes dtection derreurs correction derreurs


PAR et RARFichiers SFV (Simple File Verication) CRC des chiers RAR dtection derreurs


PAR et RARFichiers SFV (Simple File Verication) CRC des chiers RAR dtection derreurs Fichiers REV (RAR Recovery Volumes) Correction interne des chiers RAR


PAR et RARFichiers SFV (Simple File Verication) CRC des chiers RAR dtection derreurs Fichiers REV (RAR Recovery Volumes) Correction interne des chiers RAR Fichiers PAR (Parchive les) Code de Reed-Solomon li larchive RAR Permet ventuellement de recrer lun des morceaux de larchive


Documents

Codeurs BCH