View
78
Download
0
Category
Preview:
Citation preview
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 BCH, Reed Solomon et leurs applications p.2/29
Codes cycliquesUn code cyclique est :
un code linaire si (x1 , . . . , xn ) C alors (xn , x1 , . . . , xn1 ) C
Codes BCH, Reed Solomon et leurs applications p.3/29
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
Codes BCH, Reed Solomon et leurs applications p.3/29
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
Proprit C est cyclique ssi : si P (X) (C) pour tout polynme Q,Q(X) P (X)[X n 1] (C)
Codes BCH, Reed Solomon et leurs applications p.3/29
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 BCH, Reed Solomon et leurs applications p.4/29
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
Codes BCH, Reed Solomon et leurs applications p.5/29
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
Codes BCH, Reed Solomon et leurs applications p.5/29
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
C de dimension k = n t
Codes BCH, Reed Solomon et leurs applications p.5/29
Codes cycliques
CodageKk1 [X] Kn1 [X] P P P0
Codes BCH, Reed Solomon et leurs applications p.6/29
Codes cycliquesComme P0 | X n 1 :P0 Q = X n 1
Codes BCH, Reed Solomon et leurs applications p.7/29
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 BCH, Reed Solomon et leurs applications p.7/29
Codes cycliques
G : encodeur non systmatique
Codes BCH, Reed Solomon et leurs applications p.8/29
Codes cycliques
G : encodeur non systmatique
Distance minimale ? Capacit de correction
Codes BCH, Reed Solomon et leurs applications p.8/29
Codes cycliques
G : encodeur non systmatique
Distance minimale ? Capacit de correction Codes BCH
Codes BCH, Reed Solomon et leurs applications p.8/29
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 BCH, Reed Solomon et leurs applications p.9/29
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, Reed Solomon et leurs applications p.9/29
Codes BCH
appel distance construite
Codes BCH, Reed Solomon et leurs applications p.10/29
Codes BCH
appel distance construite
Code BCH
Codes BCH, Reed Solomon et leurs applications p.10/29
Codes BCH
appel distance construite
Code BCH
Les plus utiliss : codes primitifn = qt 1 L = Fq t
Codes BCH, Reed Solomon et leurs applications p.10/29
Codes de Reed Solomon
Un code de Reed-Solomon est un code BCH de longueur 2m 1 sur F2m .
Codes BCH, Reed Solomon et leurs applications p.11/29
Codes de Reed Solomon
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 )
Codes BCH, Reed Solomon et leurs applications p.11/29
Codes de Reed Solomon
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 BCH, Reed Solomon et leurs applications p.11/29
Codes de Reed SolomonRsum : n = 2m 1, k = 2m r 1, d=r+1
d=nk+1
Codes BCH, Reed Solomon et leurs applications p.12/29
Codes de Reed SolomonRsum : n = 2m 1, k = 2m r 1, d=r+1
d=nk+1
Codes maximaux
Codes BCH, Reed Solomon et leurs applications p.12/29
Qui sert quoi ...
Codes BCH, Reed Solomon et leurs applications p.13/29
Codage des CDs
Bas sur un code de Reed-Solomon sur F8[255, 251, 5]
Codes BCH, Reed Solomon et leurs applications p.14/29
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]
Codes BCH, Reed Solomon et leurs applications p.14/29
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)
Codes BCH, Reed Solomon et leurs applications p.14/29
Codage des CDs
Entrelacement simple :
mot
envoi colonne par colonne
Codes BCH, Reed Solomon et leurs applications p.15/29
Codage des CDs
Entrelacement simple :
mot
envoi colonne par colonne
Codes BCH, Reed Solomon et leurs applications p.16/29
Codage des CDs
Entrelacement avec retard :
Codes BCH, Reed Solomon et leurs applications p.17/29
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]
Codes BCH, Reed Solomon et leurs applications p.18/29
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
Codes BCH, Reed Solomon et leurs applications p.18/29
Codage Minitel
Mode de transmission assez able.
Codes BCH, Reed Solomon et leurs applications p.19/29
Codage Minitel
Mode de transmission assez able. Codes de Hamming
Codes BCH, Reed Solomon et leurs applications p.19/29
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)
Codes BCH, Reed Solomon et leurs applications p.19/29
Codages utiliss pour la transmission dimages
Transmission dimages noire et blanc : Reed-Muller [32, 6, 16]
Codes BCH, Reed Solomon et leurs applications p.20/29
Codages utiliss pour la transmission dimages
Transmission dimages noire et blanc : Reed-Muller [32, 6, 16] Assez efcaces sur des mots courts Codage/Dcodages efcaces
Codes BCH, Reed Solomon et leurs applications p.20/29
Codages utiliss pour la transmission dimages
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
Codes BCH, Reed Solomon et leurs applications p.20/29
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
Codes BCH, Reed Solomon et leurs applications p.21/29
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
Codes BCH, Reed Solomon et leurs applications p.21/29
Et les codes de Hamming ...
Utiliss pour la correction sur :
supports assez ables mots courts ncessitant des taux bas (ajout de peu de bits)
Codes BCH, Reed Solomon et leurs applications p.22/29
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
Codes BCH, Reed Solomon et leurs applications p.22/29
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
Codes BCH, Reed Solomon et leurs applications p.23/29
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 Sil est facile de retransmettre :
Codes BCH, Reed Solomon et leurs applications p.23/29
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 Sil est facile de retransmettre : detection retransmission si ncessaire
Codes BCH, Reed Solomon et leurs applications p.23/29
Checksum et CRCBut : dtection derreurs retransmission plus simple que correction
Codes BCH, Reed Solomon et leurs applications p.24/29
Checksum et CRCBut : dtection derreurs retransmission plus simple que correction Checksum : somme des bits du message modulo 256
Codes BCH, Reed Solomon et leurs applications p.24/29
Checksum et CRCBut : dtection derreurs retransmission plus simple que correction Checksum : somme des bits du message modulo 256 augmenter la complexit
Codes BCH, Reed Solomon et leurs applications p.24/29
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]
Codes BCH, Reed Solomon et leurs applications p.24/29
Checksum et CRCMessage mot binaire polynme F2 [X]
Codes BCH, Reed Solomon et leurs applications p.25/29
Checksum et CRCMessage mot binaire polynme F2 [X] 6 23
Codes BCH, Reed Solomon et leurs applications p.25/29
Checksum et CRCMessage mot binaire polynme F2 [X] 6 23 00000110 00010111
Codes BCH, Reed Solomon et leurs applications p.25/29
Checksum et CRCMessage mot binaire polynme F2 [X] 6 23 00000110 00010111 M (X) = X 10 +X 9 +X 4 +X 2 +X +1
Codes BCH, Reed Solomon et leurs applications p.25/29
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
Codes BCH, Reed Solomon et leurs applications p.25/29
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 rT (X) = (X r M (X))/G(X)
Codes BCH, Reed Solomon et leurs applications p.25/29
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 rT (X) = (X r M (X))/G(X)
Message transmisM (X) T (X)
Codes BCH, Reed Solomon et leurs applications p.25/29
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
Codes BCH, Reed Solomon et leurs applications p.26/29
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
Codes BCH, Reed Solomon et leurs applications p.26/29
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 (X 22 + X 21 + X 16 + X 14 + X 13 + X 12 )/CRC-12 = X 10 + X 7 + X 3
Codes BCH, Reed Solomon et leurs applications p.26/29
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 (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
Codes BCH, Reed Solomon et leurs applications p.26/29
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 (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
Codes BCH, Reed Solomon et leurs applications p.26/29
Checksum et CRC
En gnral : transmission dans les rseaux dtection derreurs checksum ou CRC protocole inclut acquittement
Codes BCH, Reed Solomon et leurs applications p.27/29
PAR et RAR
Mcanisme des RAR et PAR :
archives compresses et coupes dtection derreurs correction derreurs
Codes BCH, Reed Solomon et leurs applications p.28/29
PAR et RARFichiers SFV (Simple File Verication) CRC des chiers RAR dtection derreurs
Codes BCH, Reed Solomon et leurs applications p.29/29
PAR et RARFichiers SFV (Simple File Verication) CRC des chiers RAR dtection derreurs Fichiers REV (RAR Recovery Volumes) Correction interne des chiers RAR
Codes BCH, Reed Solomon et leurs applications p.29/29
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
Codes BCH, Reed Solomon et leurs applications p.29/29
Recommended