Corriger les erreurs

Reed-Solomon : QR codes, CD et RAID

Corriger des rafales entières

Hamming corrige une erreur isolée, mais sur un CD rayé ou un QR code déchiré, ce sont des blocs entiers qui disparaissent. Le code de Reed-Solomon est conçu pour cela : il travaille non pas sur des bits isolés mais sur des symboles (des paquets de bits), et corrige des symboles entièrement effacés ou faux. C'est lui qui rend les QR codes, les CD, les DVD et le stockage RAID si robustes.

L'idée : sur-déterminer une courbe

L'intuition géométrique est belle. Deux points suffisent à définir une droite ; mais si on transmet plus de points que nécessaire, tous situés sur cette même droite, alors on peut perdre quelques points et retrouver quand même la droite d'origine à partir de ceux qui restent.

Idee de Reed-Solomon (sur-determiner une courbe) :

donnees -> definissent une courbe (polynome)

   *       *                        (points de donnees)
      *       *   *     *            (+ points redondants, sur la MEME courbe)
   ----------------------
   |  X  |     |  X  |               (X = points perdus ou abimes)

-> il reste assez de points valides pour reconstruire la courbe entiere,
   donc pour retrouver les points perdus

Effacements et erreurs

Reed-Solomon distingue deux cas. Un effacement est un symbole dont on sait qu'il est perdu (position connue) : facile à reconstruire. Une erreur est un symbole faux dont on ignore la position : plus coûteux, car il faut d'abord la localiser. Avec r symboles de redondance, on corrige jusqu'à r effacements, ou r/2 erreurs.

Pourquoi il est partout

Sa force est de résister aux dégâts groupés, exactement ce qui arrive en vrai : une rayure abîme des symboles voisins, un QR code peut perdre jusqu'à 30 % de sa surface et rester lisible. On combine souvent Reed-Solomon avec un entrelacement qui disperse les symboles, pour qu'une rafale physique se traduise par des erreurs isolées, plus faciles à corriger.

Piège classique