s
19 708 Pages

en La théorie du codage, la Code Reed-Solomon Il est un type de code linéaire (Cyclique) non binaire détection et correction d'erreur, inventé par Irving S. Reed et Gustave Solomon.

Il est utilisé pour corriger des erreurs dans le flux de nombreuses applications importantes communication numérique et mémoriser données. Ses utilisations vont de 'l'électronique grand public les communications espace profonde.

Il est basé sur un suréchantillonnage polynôme construit à partir de données à transmettre. Le polynôme est alors calculé que plus de points seraient suffisants pour identifier de manière unique; la valeur de ces points est transmis ou enregistré. Lors de la réception ou la lecture, il est possible de reconstituer le polynôme d'origine, et par conséquent les données, même avec des erreurs.

histoire

Le code a été inventé en 1960 par Irving S. Reed et Gustave Solomon, qui travaillait à l'époque à laboratoire Lincoln la Massachusetts Institute of Technology (MIT). Le travail a été publié dans l'article codes polynomiale sur certains champs finis (Codes polynomiale sur certains domaines finis).[1]

Mais en 1960, la technologie numérique n'a pas été assez avancée pour réaliser le concept. L'application des codes de Reed-Solomon a été rendu possible en 1969, grâce au travail de Elwyn Berlekamp et James Massey, qui a inventé un algorithme de décodage efficace.

en 1977 Les codes de Reed-Solomon ont été appliqués admirablement dans le programme spatial voyageur, sous la forme de codes concaténés pour la vérification des erreurs.

Théorie de base

L'idée clé derrière le code de Reed-Solomon est de voir les données pour « protéger » comme polynôme. L 'algèbre linéaire dit qu'un certain nombre k des points distincts déterminent de façon unique un polynôme de degré au plus k-1.

Le polynôme est ensuite « codé » à travers le calcul de plusieurs de ses points et les valeurs de ces points sont ce qui est effectivement transmis. Au cours de l'émission, certains de ces points peuvent être soudoyés. Pour cette raison, il est transmis k + n points avec n qui sont les données ajoutées à la protection des informations. Le récepteur analyse les points reçus et détermine le polynôme de degré k-1 qui représente le mieux la séquence de points reçus. Tant que « pas trop de » points sont reçus corrompus, le récepteur peut reconstruire ce que le polynôme d'origine, puis décrypter les données. Dans le cas d'un nombre excessif d'erreurs, cependant, le décodeur reconstitue un polynôme « similaire » à celui de départ. Ainsi, l'algorithme montre une faible dépendance du nombre d'erreurs, il y a un certain nombre d'erreurs au-delà duquel la reconstruction échoue, mais l'algorithme reconstitue toujours un polynôme probable, la probabilité du polynôme reconstruit dépend du nombre d'erreurs reçues.

opération

Au cours de la transmission de tout signal analogique ou numérique de nombreux facteurs externes, tels que bruit électrique, interférence, lignes sur les écorchures de surface CD / DVD ou des taches sur les codes-barres, de créer une série d'erreurs qui peuvent compromettre la bonne transmission ou la lecture données.

Le fonctionnement du code de Reed-Solomon peut se résumer dans les actions suivantes:

  • Sortie de données
  • codage Reed-Solomon
  • La transmission de données (avec des erreurs)
  • Décodage Reed-Solomon (détection et correction d'erreur)
  • réception de données correcte

Par exemple, lors de la gravure séquence des CD audio d'échantillons (PCM 16 bits) est divisée en blocs de 24 octets à laquelle est appliqué un code de correction Reed-Solomon de 4 octets qui permet la correction d'erreurs dans des positions connues 4 ou 2 erreurs dans les positions inconnues pour chaque bloc. Par la suite 112 blocs contigus sont regroupés et échangés entre eux d'une manière telle que deux blocs successifs dans le flux de données ne sont jamais à proximité de l'autre. Cette disposition (désentrelacement) Est utilisé pour faire des erreurs consécutives sur le CD (en raison des rayures ou des empreintes digitales) lors de la lecture, ils doivent être répartis le long du flux de données reconstruit, augmentant ainsi les chances de correction.[2]

applications

Le code Reed-Solomon est utilisé dans technologies de communication et d'information pour le codage et le décodage des données.

L'outil est également utilisé dans certaines applications à des appareils avec des fonctions scanner comme Nintendo e-Reader ou téléphones mobiles et smartphone.

Stockage des données

Dans le cadre de 'l'électronique grand public le code est utilisé pour corriger les erreurs de décodage dues à des défauts dans les supports de stockage tels que DAT, CD, DVD, Blu-ray Disc et les normes RAID.

Le code Reed-Solomon est également utilisé dans codes à barres Postbar ou dans le code à barres en deux dimensions comme code aztèque, la QR code,[3] la Data Matrix, la MaxiCode et PDF-417, pour la restauration des données dans le cas où une partie du code est endommagé, ce qui permet une lecture correcte.

transmission de données

Dans le domaine de télécommunications Le code Reed-Solomon est utilisé pour la transmission et la réception données dans les communications satellite; dans les connexions large bande et sans fil comment DSL ou WiMAX; dans des systèmes de transmission ATSC et Digital Video Broadcasting; et de contourner la nature peu fiable des données transmises sur des canaux de communication BEC.

La première application majeure dans le domaine des communications par satellite était celui utilisé pour décoder photos numériques envoyé par le vaisseau spatial voyageur.

Dans les systèmes Comité consultatif pour l'espace Protocole Data Systems et aux communications spatiales Spécifications pour l'estimation et l'élimination des erreurs est utilisé diverses applications (FEC).

D'autres versions du code sont utilisés dans les missions spatiales Mars Pathfinder, Galileo, Mars Exploration Rover et Cassini, dont le fonctionnement est comprise entre 1 et 1,5 décibel de la limite imposée par la capacité du canal.

notes

  1. ^ Irving S. Reed, Gustave Solomon. Codes polynomiale sur certains domaines finis. « Journal de la Société de mathématiques appliquées et industrielles (SIAM), Juin 1960. Vol 8. (2), pp 300-304. DOI 10,1137 / 0108018
  2. ^ Kees Immink, codes Reed-Solomon et le Compact Disc, en Codes Reed-Solomon et leurs applications, Wiley-IEEE Press, 1994.
  3. ^ (FR) QR Code Outline Spécification Denso-Wave. Consulté le 30 Juillet, 2010

bibliographie

Articles connexes

D'autres projets

liens externes