Aller au contenu
ELECTRONICS ENGINEERINGelectronics-engineering.com
Communications électriques

Codes correcteurs d'erreurs : Hamming, CRC et codes modernes

Distance de Hamming et capacité de correction avec démonstration, le code de Hamming (7,4) avec un exemple, syndrome, CRC, codes convolutifs, Reed-Solomon, turbo, LDPC, codes polaires, entrelacement.

https://www.electronics-engineering.com/fr/codes-correcteurs-d-erreurs-hamming-crc-ldpc/

Cette page vous a-t-elle été utile ? Notez-la :
moyenne 5,0 sur 1 vote

Shannon a démontré que l’on peut envoyer des données presque sans erreur jusqu’à la capacité du canal, mais seulement en les codant : en ajoutant des bits de redondance calculés de façon que le récepteur puisse découvrir et corriger les erreurs. Les codes correcteurs d’erreurs sont dans toute communication numérique et toute mémoire : CD, QR codes, SSD, Wi-Fi, 5G, sondes spatiales. Dans cette leçon, nous traitons la distance minimale, le code de Hamming avec un exemple complet, les codes de détection CRC et les codes modernes.

La distance de Hamming

Un code en blocs (n, k) transforme k bits d’information en un mot de code de n bits ; le rapport k/n est le rendement du code. La distance de Hamming entre deux mots est le nombre de bits par lesquels ils diffèrent ; la distance minimale d_{min} du code est la plus petite sur toutes les paires de mots de code.

Théorème. Un code de distance minimale d_{min} détecte jusqu’à d_{min} - 1 erreurs et en corrige jusqu’à

    \[ t = \left\lfloor\frac{d_{min} - 1}{2}\right\rfloor \]

Démonstration. Si au plus d_{min} - 1 erreurs se produisent, le mot reçu ne peut pas coïncider avec un autre mot de code (qui est à au moins d_{min}), donc l’erreur se voit. Pour la correction, on choisit le mot de code le plus proche. S’il y a au plus t erreurs, avec 2t \lt d_{min}, le mot émis est à au plus t du mot reçu, tandis que tout autre mot de code est à au moins d_{min} - t \gt t (inégalité triangulaire). Le plus proche est donc le bon. ∎

Géométriquement : autour de chaque mot de code, il y a une « sphère » de rayon t, et les sphères ne se touchent pas.

Le code de Hamming (7,4)

Quatre bits d’information d_1d_2d_3d_4 et trois bits de parité p_1p_2p_3, chacun égal au OU exclusif de trois bits d’information. La façon la plus claire de le voir, ce sont trois cercles :

Code de Hamming (7,4) représenté avec trois cercles de parité
Trois cercles qui se chevauchent : chaque bit d’information se trouve dans une intersection différente de deux ou trois cercles, chaque bit de parité dans la partie exclusive de son cercle. Chaque cercle doit contenir un nombre pair de 1.

Chaque cercle doit contenir un nombre pair de 1. Une erreur sur un seul bit se localise d’après les cercles qui se révèlent impairs : chaque bit se trouve dans une combinaison de cercles différente.

Exemple. Données d_1d_2d_3d_4 = 1011. Les parités : p_1 = d_1 \oplus d_2 \oplus d_4 = 1 \oplus 0 \oplus 1 = 0, p_2 = d_1 \oplus d_3 \oplus d_4 = 1, p_3 = d_2 \oplus d_3 \oplus d_4 = 0. On envoie sept bits. Si le canal inverse d_3, le récepteur recalcule les parités : le cercle vert (p_2) et le rouge (p_3) se révèlent impairs, le bleu pair. Le seul bit qui est dans le vert et le rouge mais pas dans le bleu est d_3 : on le rétablit et les données sont correctes.

Sous forme algébrique, les trois contrôles forment le syndrome, un nombre de 3 bits qui est nul s’il n’y a pas d’erreurs et qui, sinon, indique lequel des 7 bits est faux. Le code a d_{min} = 3 : il corrige une erreur par mot, avec un rendement de 4/7. En ajoutant un bit de parité globale (code étendu, d_{min} = 4), il corrige les erreurs simples et détecte les doubles : c’est le code SECDED des mémoires ECC de serveur.

La détection : le CRC

Souvent, il suffit de remarquer l’erreur et de demander la retransmission. Le contrôle de redondance cyclique (CRC) traite le message comme un polynôme à coefficients binaires, le divise par un polynôme générateur fixe et ajoute le reste. Le récepteur répète la division : un reste non nul signifie une erreur. Un CRC de 32 bits (celui d’Ethernet, de ZIP, de PNG) détecte toutes les erreurs en rafale jusqu’à 32 bits et laisse passer une erreur aléatoire avec une probabilité d’environ 2^{-32}. Il se calcule avec un registre à décalage et quelques portes XOR, ou avec une table en logiciel.

Les codes modernes

  • Codes convolutifs avec décodage de Viterbi : ils codent le flux continu avec un petit registre à décalage ; utilisés depuis des décennies en téléphonie mobile et dans les satellites.
  • Reed-Solomon : ils travaillent sur des symboles de plusieurs bits et sont très forts contre les erreurs en rafale. On les trouve dans les CD et les DVD (où ils corrigent des rayures de la taille du millimètre), dans les QR codes (qui restent lisibles même partiellement recouverts) et dans les transmissions des sondes spatiales.
  • Codes turbo et LDPC : avec un décodage itératif, qui échange des probabilités au lieu de décisions fermes, ils s’approchent à quelques dixièmes de décibel de la limite de Shannon. Les codes LDPC sont dans le Wi-Fi, la 5G, la télévision par satellite et les SSD ; les codes polaires, les premiers codes dont on a prouvé qu’ils atteignent la capacité, dans les canaux de contrôle de la 5G.

L’entrelacement. Les codes corrigent bien les erreurs dispersées et mal les erreurs concentrées, et les canaux à évanouissements produisent justement des rafales d’erreurs. Avant la transmission, on mélange l’ordre des bits (entrelacement), et le récepteur le rétablit : une rafale sur le canal devient une série d’erreurs isolées, que le code corrige.

Ce que l’on gagne. Avec un bon code de rendement 1/2, une probabilité d’erreur de 10⁻⁵ s’atteint avec environ 1 à 2 dB de E_b/N_0 au lieu des 9,6 dB de la BPSK non codée : un gain de codage de 7 à 8 dB, qui vaut autant que multiplier la puissance émise par cinq, au prix de la bande et du calcul pour le décodage.

S’abonner
Notifier de
guest
1 commentaire
Le plus ancien
Plus récent Les plus votés
1
0
Vous avez apprécié cet article ? Merci de laisser un commentaire.x