Codes Reed-Solomon. Un exemple simple. Code RedA

Les codes Reed-Solomon ont été proposés en 1960 par Irvin Reed et Gustav Solomon (Gustave Solomon), employés du MTI du laboratoire de Lincoln. La clé de l'utilisation de cette technologie était l'invention d'un algorithme de décodage efficace à Elvin Belikamf (Elwyn Berlekamp; http://fr.wikipedia.org/wiki/berlekamp-Messey_algorithm), professeur à l'Université de Californie (Berkeley) . Les codes Reed-Solomon (voir aussi http://www.4i2i.com/reed_solomon_codes.htm) sont basés sur le principe de bloc de la correction d'erreur et sont utilisés dans l'énorme nombre d'applications dans le domaine des télécommunications numériques et lorsque des dispositifs de stockage de bâtiment . Les codes Reed-Solomon sont utilisés pour corriger les erreurs dans de nombreux systèmes:

dispositifs de mémoire (y compris les rubans magnétiques, le CD, le DVD, les codes à barres, etc.);
communications sans fil ou mobiles (y compris téléphones portables, micro-ondes, etc.);
communications par satellite;
télévision numérique / DVB (diffusion vidéo numérique);
modems à grande vitesse, tels que ADSL, XDSL, etc.

Figure. 4.3.

Le système typique est présenté ci-dessous (voir http://www.4i2i.com/reed_solomon_codes.htm)

Figure. 4.4.

Le codeur REDA Solomon prend l'unité de données numériques et ajoute des bits supplémentaires. Les erreurs se produisent lorsqu'elles sont transmises sur des canaux de communication ou pour diverses raisons lors de la mémorisation (par exemple, due au bruit ou à un joint d'étanchéité, rayures sur CD, etc.). Le décodeur REDA Solomon traite chaque bloc, essayant de corriger les erreurs et de restaurer les données source. Le nombre et les types d'erreurs pouvant être corrigés dépendent des caractéristiques du code Reda Solomon.

Propriétés des codes de Solomon Reda

Les codes Reed-Solomon sont des codes Subnaborous BCH et sont des codes de blocs linéaires. Le code Reda Solomon est spécifié en tant que caractères Rs (N, K) S -BIT.

Cela signifie que le codeur perçoit les symboles d'informations K par bits chacun et ajoute des symboles de parité pour former un mot de code de caractères N. Il y a des caractères de parité NK sur S bits chacun. Le décodeur REDA-SOLOMON peut ajuster les caractères T contenant des erreurs dans le mot de code, où 2T \u003d N - K.

Le diagramme ci-dessous montre le mot de code typique de la Reda Solomon:

Figure. 4.5.

Exemple. Le code Populaire Rida Solomon est Rs (255, 223) avec des caractères 8 bits. Chaque mot de code contient 255 octets, dont 223 sont des octets d'information et de 32 partérérations. Pour ce code

n \u003d 255, k \u003d 223, S \u003d 8

2T \u003d 32, t \u003d 16

Le décodeur peut réparer 16 caractères avec des erreurs dans le mot de code: c'est-à-dire que les erreurs peuvent être corrigées si le nombre d'octets déformés ne dépasse pas 16.

Avec la taille du symbole S, longueur maximale Le mot de code (N) pour le code Rida-Solomon est N \u003d 2 S - 1.

Par exemple, la longueur maximale du code avec des caractères de 8 bits (S \u003d 8) est de 255 octets.

Les codes Reed-Solomon peuvent être en principe raccourcis en réinitialisant un certain nombre de symboles d'information à l'entrée du codeur (il n'est pas nécessaire de les transmettre dans ce cas). Lorsque le transfert de données sur le décodeur, ces zéros sont à nouveau introduits dans une matrice.

Exemple. Le code (255, 223), décrit ci-dessus, peut être raccourci (200, 168). Le codeur fonctionnera avec un bloc de données 168 octets, ajoutera 55 notes d'octets, formera un mot de code (255, 223) et transmettra seulement 168 octets d'information et 32 \u200b\u200boctets de parité.

Le volume de la puissance de calcul requise pour le codage et la décodage des codes de la Reda Solomon dépend du nombre de caractères de parité. Une valeur importante de T est qu'un nombre plus important d'erreurs peut être corrigé, mais il nécessitera une plus grande puissance de calcul par rapport à l'option à moins t.

Erreurs dans les symboles

Une erreur dans le symbole se produit lorsque 1 bit du symbole s'avère incorrect ou lorsque tous les bits sont incorrects.

Exemple. Le code RS (255.223) peut fixer jusqu'à 16 erreurs dans des caractères. Dans le pire des cas, il peut y avoir 16 erreurs de bits dans différents symboles (octets). Au mieux, 16 octets complètement incorrects sont corrigés, tandis que 16 x 8 \u003d 128 erreurs de bits sont corrigées.

Les codes Reed-Solomon sont particulièrement bien adaptés pour ajuster les grappes d'erreur (lorsque les grands groupes de bits de mot de code sont incorrects, ci-dessous dans une rangée).

Décodage

Les procédures de décodage algébrique de la Reda Solomon peuvent corriger les erreurs et les pertes. La perte est considérée comme une affaire lorsque la position du mauvais symbole est connue. Le décodeur peut résoudre les erreurs T ou jusqu'à 2t pertes. Les données sur la perte (effacement) peuvent être obtenues à partir d'un démodulateur d'un système de communication numérique, c'est-à-dire Le démodulateur marque les caractères résultants qui contiennent probablement des erreurs.

Lorsque le mot de code est décodé, trois options sont possibles.

Si 2s + r< 2t (s ошибок, r потерь), тогда исходное переданное кодовое слово всегда будет восстановлено. Sinon
Le décodeur détecte la situation lorsqu'il ne peut pas restaurer le mot de code source. ou alors
Le décodeur décode de manière incorrecte et incorrectement le mot de code sans indication de ce fait.

La probabilité de chacune de ces options dépend du type de code de Solomon REDA utilisé, ainsi que du nombre et de la distribution d'erreurs.

L'avantage de l'utilisation des codes Reda-Solomon est que la probabilité d'épargner des erreurs dans des données décodées est généralement beaucoup moins que la probabilité d'erreurs si les codes du Solomon Reda ne sont pas utilisés. Ceci est souvent appelé codage gagnant.

Exemple. Soit un système de télécommunication numérique qui fonctionne avec BER (ratio d'erreur bit) égal à 10 -9, c'est-à-dire Pas plus de 1 bits sur 10 9 sont transmis avec une erreur. Ce résultat peut être obtenu en augmentant la puissance de l'émetteur ou en appliquant des codes RIDA-SOLOMON (ou d'autres types de correction d'erreur). Algorithme de Reda Solomon Permet au système d'atteindre le niveau BR requis avec une puissance de sortie inférieure de l'émetteur.

Codes de codage et de décodage Architecture Reda Solomon Codes

Le codage et le décodage du Solomon Reda peuvent être effectués du matériel ou des logiciels.

Galua Fini Field Arithmétique

Les codes Reda-Solomon sont basés sur une section spéciale de mathématiques - champoi (GF) ou champs finis. Les actions arithmétiques (+, -, x, /, etc.) au-dessus des éléments du champ final donnent le résultat, ce qui est également un élément de ce champ. Le codeur ou le décodeur du Rydasolon devrait pouvoir effectuer ces opérations arithmétiques. Ces opérations nécessitent des équipements spéciaux ou spécialisés logiciel.

Polynôme

Le mot de code du Solomon Reda est formé avec l'implication d'un polynôme spécial. Tous les mots de code correct doivent être divisés sans équilibre à ces formage polynomial. Forme générale formage polynomial A l'apparence

g (x) \u003d (x - a i) (x - a i + 1) ... (x - a i + 2t)

et le mot de code est formé à l'aide de l'opération

c (x) \u003d g (x) .Je (x)

où g (x) est former des polynômes, I (x) est un bloc d'information, c (x) est un mot de code appelé élément simple du champ.

Exemple. Générateur pour Rs (255, 249)

g (x) \u003d (x - a 0) (x - a 1) (x - a 2) (x - a 3) (x - a 4) (x - a 5) g (x) \u003d x 6 + g 5 x 5 + g 3 x 3 + g 2 x 2 + g 1 x 1 + g 0

Architecture de codeur

Les symboles de parité 2T dans le mot de code Rida-Solomon sont déterminés à partir de la relation suivante:

Vous trouverez ci-dessous le schéma de mise en œuvre du codeur de la version RS (255.249):

Figure. 4.6.

Chacun des 6 registres contient un symbole (8 bits). Les opérateurs arithmétiques effectuent une addition ou une multiplication sur un symbole en tant qu'élément du champ final.

Décodeur d'architecture

Le schéma de décodage général des codes Reda-Solomon est présenté ci-dessous à la Fig. 4.7.

Figure. 4.7.

Désignation:

r (x) - le mot de code obtenu
SI - Syndromes
L (x) - Emplacement d'erreur polynomiale
XI - Positions d'erreur
Yi - Valeurs d'erreur
c (x) - mot de code restauré
v - Nombre d'erreurs

Le mot de code obtenu R (x) est le mot de code original (transmis) de code C (x) plus des erreurs:

r (x) \u003d c (x) + e (x)

Le décodeur REDA Solomon tente de déterminer la position et la valeur de l'erreur pour t erreurs T (ou 2t perte) et corriger les erreurs et les pertes.

Calcul du syndrome

Le calcul du syndrome est similaire au calcul de la parité. Le mot de code de Solomon Reda a 2T sindromeCela dépend uniquement des erreurs (et non des mots de code transmis). Les syndromes peuvent être calculés par substitution 2T racines formage polynomial G (x) dans r (x).

Trouver des postes d'erreur symbolique

Cela se fait en résolvant le système d'équations avec T inconnu. Il existe plusieurs algorithmes rapides pour résoudre cette tâche. Ces algorithmes utilisent les caractéristiques de la structure de la matrice des codes de rhyrasolone et réduisent vivement la puissance informatique nécessaire. Cela se fait en deux étapes.

1. Définition de l'emplacement d'erreur polynomiale.

Cela peut être fait à l'aide de l'algorithme Berlekamp-Massey ou d'un algorithme d'euclide. L'algorithme d'euklide est utilisé plus souvent dans la pratique, car il est plus facile de le mettre en œuvre, mais l'algorithme Berlekamp-Massey vous permet d'obtenir une mise en œuvre plus efficace des équipements et des programmes.

2. Trouver les racines de ce polynôme. Ceci est fait avec l'attraction de l'algorithme de recherche de chien.

Trouver des valeurs d'erreur symbolique

Il doit également résoudre le système d'équations avec T inconnu. Pour résoudre, un algorithme de Forney rapide est utilisé.

Mise en œuvre du codeur et du décodeur de Rida Solomon. Mise en œuvre du matériel

Il existe plusieurs implémentations matérielles commerciales. Il existe de nombreux circuits intégrés développés conçus pour coder et décoder des codes Reed-Solomon. Ces IP autorisent un certain niveau de programmation (par exemple, Rs (255, K), où T peut prendre des valeurs de 1 à 16).

Mise en œuvre du logiciel

Jusqu'à récemment, les mises en œuvre du programme dans le "temps réel" nécessitaient trop de puissance de calcul pour presque tous les codes de Solomon Reda. La principale difficulté de la mise en œuvre du programme des codes Reda-Solomon était le fait que les transformateurs usage général Ne supportez pas les opérations arithmétiques pour le champ de Galua. Toutefois, la compilation optimale des programmes associée à une puissance de calcul accrue vous permet d'obtenir des résultats assez acceptables pour des taux de transmission de données relativement élevés.

Le code RedA-Solomon a été inventé en 1960 par le laboratoire Lincoln Labolna Reed (anglais) et Gustav Solomon (ENG.). L'idée d'utiliser ce code a été présentée dans l'article "Codes polynomiaux sur certains champs finis". La première application du code de Reed - Solomon a reçu en 1982 dans libération en série CDS. L'algorithme de décodage efficace a été proposé en 1969 par Elvin Blekhemmp (anglais) et Jaims Messi (l'algorithme de Berlekampa - Massey).

Description formelle

Les codes de Reda - Solomon sont un cas privé important du CDC, les racines du polynôme dont elles se trouvent dans le même champ, sur quel code ( m. \u003d 1). Soit α un élément du champ de commande. Si α - primitif article, alors sa commande est égale q. - 1, c'est. Puis des polynômes normalisés g.(x.) Le degré minimum sur le terrain, dont les racines sont rÉ. - 1 dans une rangée des degrés de fonctionnement de l'élément α est le code polynomial générateur de la Reda - Solomon sur le terrain:

où l. 0 est un nombre entier (y compris 0 et 1), avec lequel il est parfois possible de simplifier le codeur. Dépend généralement l. 0 \u003d 1. Le degré de polynôme est égal rÉ. − 1 .

Longueur du code résultant n. , distance minimale rÉ. (La distance minimale D du code linéaire est minimale de toutes distances de la chimition de toutes paires de mots de code, voir code linéaire). Le code contient r = rÉ. - 1 \u003d DEG ( g.(x.)) les caractères de test où DEG () dénote le degré de polynôme; Nombre de symboles d'information k. = n. − r = n. − rÉ. + 1 . Ainsi, le code Reda - Salomon est code séparé avec une distance maximale (Il est optimal au sens de la frontière du singleton).

Code polynôme c.(x.) peut être obtenu à partir du polynôme d'informations m.(x.), en multipliant m.(x.) JE. g.(x.) :

c.(x.) = m.(x.)g.(x.)

Propriétés

Code Reda - Solomon sur, corriger t. Les erreurs nécessitent 2 t. Vérifiez les caractères et utiliser des packages d'erreur arbitraires longs t. et moins. Selon le théorème de la limite de régie, les codes de Reda-Solomon sont optimaux du point de vue du rapport de la longueur de l'emballage et de la capacité de correction d'erreur - en utilisant 2 t. Les caractères de chèques supplémentaires sont corrigés t. Erreurs (et moins).

Théorème (frontière REGLIGER). Chaque code de bloc linéaire, fixant la longueur de tous les paquets t. et moins devrait contenir au moins 2 t. Vérifiez les caractères.

Correction de plusieurs erreurs

Le code REDA-SOLOMON est l'un des codes les plus puissants qui corrigent plusieurs packages d'erreur. Il est utilisé dans les canaux où les packages d'erreur peuvent être formés de manière si souvent qu'ils peuvent déjà être corrigés à l'aide de codes qui corrigent des erreurs simples.

(q. m. − 1,q. m. − 1 − 2t.) -Kod Reed - Salomon sur le champ Distance de Coden rÉ. = 2t. + 1 peut être considéré comme ((q. m. − 1)m.,(q. m. − 1 − 2t.)m.) -code sur un champ qui peut corriger toute combinaison d'erreurs axées dans t. ou moins de blocs de M caractères. Le plus grand nombre de blocs de longueur m. qui peut affecter la longueur de la longueur l. jE. où ne dépasse pas t. jE. , par conséquent, le code qui peut corriger t. Blocs d'erreur, peut toujours réparer toute combinaison de p. Forfaits de longueur générale l. , si un .

Mise en œuvre pratique

Le codage utilisant le code REDA-SOLOMON peut être mis en œuvre de deux manières: systématique et non systématique (voir, la description du codeur).

Avec codage non systématique, un mot informationnel est multiplié par un certain polynôme irréductible dans le champ Galois. Le mot codé résultant est complètement différent de la source et d'extraire le mot d'information dont vous avez besoin pour effectuer l'opération de décodage et vous pouvez uniquement vérifier les données sur le contenu de l'erreur. Ce codage nécessite des coûts de ressources élevés uniquement pour extraire des données d'information, alors qu'ils peuvent être sans erreur.

Avec codage systématique au bloc d'information de k. Les symboles sont attribués à 2. t. Vérifiez les caractères, lors du calcul de chaque symbole de test, utilise tout k. Symboles du bloc d'origine. Dans ce cas, il n'y a pas de coûts de ressources lors de l'extraction du bloc source, si le mot d'information ne contient pas d'erreurs, mais le codeur / décodeur doit effectuer k.(n. − k.) Opérations d'addition et de multiplication pour générer des symboles de vérification. De plus, étant donné que toutes les opérations sont effectuées dans le champ Galois, les opérations de codage / décodage ont eux-mêmes besoin de nombreuses ressources et de nombreuses ressources. L'algorithme de décodage rapide basé sur la transformation rapide de Fourier est effectuée pendant la commande O.(l.n.(n. 2)) .

Codage

Dans l'opération de codage, le polynôme d'information est multiplié par le polynôme générateur. Multiplication du mot original S. Longueur k. Sur le polynôme irréductible avec un codage systématique peut être effectué comme suit:

Le codeur est construit à partir de registres de cisaillement, d'additionneurs et de multiplicateurs. Le registre de cisaillement consiste en des cellules de mémoire, chacune ayant un élément du champ de galoa.

Décodage

Calcule le syndrome d'erreur
Construit des erreurs polynônes
Trouve les racines de ce polynôme
Définit la nature de l'erreur
Corrige des erreurs

Calcul du syndrome d'erreur

Le calcul du syndrome d'erreur est effectué par le décodeur syndromique, qui divise le mot de code sur le polynôme générateur. Si le solde se produit pendant la division, le mot a une erreur. La balance de la division est un syndrome d'erreur.

Construire une erreur polynomiale

Le syndrome d'erreur calculé n'indique pas la position des erreurs. Le degré du polynôme du syndrome est de 2 t. beaucoup moins de mots de code n. . Pour obtenir une conformité entre l'erreur et sa position dans le message est construite par des erreurs polynomiales. Des erreurs polynomiales sont implémentées à l'aide de l'algorithme Berlekampa - Messi, ou à l'aide de l'algorithme d'euclide. L'algorithme Euclidée a une implémentation simple, mais nécessite des coûts importants des ressources. Par conséquent, un algorithme plus complexe, mais moins coûteux de Berlekampa - Messi est utilisé. Les coefficients du polynôme trouvé correspondent directement aux coefficients de caractères erronés dans le mot de code.

Trouver des racines

À ce stade, les racines de l'erreur polynomiale sont recherchées pour déterminer la position des caractères déformés dans le mot de code. Il est mis en œuvre à l'aide de la procédure Chan, équivalente à l'accouplement complet. Dans des erreurs polynomiales, toutes les valeurs possibles sont substituées séquentiellement lorsque le polynomique est dessiné à zéro - les racines sont trouvées.

Définition de la nature de l'erreur et de sa correction

Selon le syndrome d'erreur et les racines polynomiales trouvées à l'aide de l'algorithme de foren, la nature de l'erreur est déterminée et le masque des caractères déformés est construit. Ce masque est superposé au mot code à l'aide de l'opération XOR et des caractères déformés sont restaurés. Après cela, les caractères de test sont supprimés et un mot d'information restauré est obtenu.

Application

DANS actuellement Les codes Reed-Solomon ont une zone d'application très large en raison de leur capacité à trouver et à corriger plusieurs packages d'erreur.

Enregistrement et stockage d'informations

Le code REDA - Solomon est utilisé lors de l'enregistrement et de la lecture dans les contrôleurs mémoire vive, lors de l'archivage des données, enregistrez des informations sur disques durs (ECC), enregistrements sur les disques CD / DVD. Même si une quantité importante d'informations est endommagée, plusieurs secteurs du support de disque sont corrompus, les codes ReDA - Solomon vous permettent de restaurer la plupart des informations perdues. Également utilisé lors de l'enregistrement de ces supports comme des rubans magnétiques et des codes à barres.

Enregistrement sur CD-ROM

Les erreurs éventuelles en lecture du disque apparaissent déjà au stade de la production du disque, pour rendre le disque parfait lorsque technologies modernes C'est impossible. De plus, des erreurs peuvent être causées par des égratignures à la surface du disque, la poussière, etc. Par conséquent, dans la fabrication du CD lisible, le système de correction de circus est utilisé (code de solomon de roseau recoupé). Cette correction est implémentée dans tous les périphériques qui vous permettent de lire des données de CDS, sous la forme d'une puce avec le micrologiciel du microprogramme. La recherche et la correction des erreurs reposent sur la redondance et l'entrelacement (redondance et entrelacement). Redondance environ 25% des informations source.

Lors de l'enregistrement sur des accessoires audio numériques (audio numérique Compact Disc - CD-DA), la norme de livre rouge est utilisée. La correction d'erreur se produit sur deux niveaux C1 et C2. Lors du codage à la première étape, les caractères de test sont ajoutés aux données source, à la deuxième étape, les informations sont à nouveau codées. Outre l'encodage, les octets d'agitation (entrelacement) sont également faits pour que les blocs d'erreur soient brisés en bits distincts plus faciles à corriger. Au premier niveau, des blocs erronés d'un et de deux octets sont fixés et corrigés (un et deux symboles erronés, respectivement). Des blocs erronés de trois octets longs sont détectés et transmis au niveau suivant. Au deuxième niveau, des blocs erronés découlant de C2, 1 et 2 octets de long et 2 octets sont révélés. La détection de trois caractères erronées est erreur fatale Et il ne peut pas être corrigé.

Sans fil et mobile

Cet algorithme de codage est utilisé pour transmettre des données sur les réseaux WiMAX, dans des lignes de communication optique, dans la communication par satellite et relais radio. La méthode de correction d'erreur directe dans la transaction du trafic (correction d'erreur avant, FEC) est basée sur les codes de Rida - Solomon.

Exemples de codes

16-Rica (15,11) RedA Code - Salomon

Laisser être t. = 2,l. 0 \u003d 1. Puis

g.(x.) = (x. − α)( x. - α 2) ( x. - α 3) ( x. - α 4) \u003d x. 4 + α 13 x. 3 + α 6 x. 2 + α 3 x. + α 10.

Pouvoir g.(x.) égal à 4, n. − k. \u003d 4 I. k. \u003d 11. Chaque élément du champ GF (16) peut être comparé 4 bits. Le polynôme d'information est une séquence de 11 caractères de GF (16), ce qui équivaut à 44 bits, et l'ensemble du mot de code est un ensemble de 60 bits.

8-RICHE (7.3) Code RedA - Salomon

Laisser être t. = 2,l. 0 \u003d 4. Puis

g.(x.) = (x. - α 4) ( x. - α 5) ( x. - α 6) ( x. − α 0) = x. 4 + α 6 x. 3 + α 6 x. 2 + α 3 x. + α

Laisser le look polynomial informatif

m.(x.) \u003d α 4 x. 2 + x. + α 3.

Le mot code de code non systématique est enregistré comme

c.(x.) = m.(x.)g.(x.) \u003d (α 4 x. 2 + x. + α 3) ( x. 4 + α 6 x. 3 + α 6 x. 2 + α 3 x. + α) \u003d α 4 x. 6 + α. x. 5 + α 6 x. 4 + 0x. 3 + 0x. 2 + α 5 x. + α 4.

Grâce aux codes REDA-SOLOMON, vous pouvez lire un CD avec plusieurs rayures ou transférer des informations dans une connexion avec un grand nombre d'interférences. En moyenne, la redondance du code pour le CD (c'est-à-dire caractères supplémentairesGrâce aux quelles informations peuvent être restaurées) est d'environ 25%. Vous pouvez restaurer la quantité de données égale à la moitié de redondant. Si la capacité du disque est de 700 Mo, elle s'avère, elle s'avère théoriquement de restaurer jusqu'à 87,5 Mo sur 700. Dans ce cas, nous n'avons pas besoin de savoir quel symbole est transmis avec une erreur. Il convient de noter que, ensemble avec le codage, utilise Mewing lorsque les octets de différents blocs sont mélangés dans un certain ordre, ce qui vous permet de lire des disques avec des dégâts importants, localisés les uns des autres (par exemple, des rayures profondes), car après l'opération , la confiture inverse, des dégâts étendus se transforme en erreurs seulement dans une variété de blocs de code réduits.

Prenons un exemple simple et essayons d'aller tout le chemin - du codage jusqu'à ce que les données source soient obtenues au récepteur. Devons-nous transmettre le mot de code C composé de deux nombres - 3 et 1 dans une telle séquence, c'est-à-dire Nous devons transférer le vecteur C \u003d (3.1). Supposons que nous voulions corriger un maximum de deux erreurs, ne pas savoir exactement où ils peuvent apparaître. Pour ce faire, vous devez prendre 2 * 2 \u003d 4 symboles redondants. Nous les écrivons avec des zéros dans notre mot, c'est-à-dire C est maintenant égal (3,1,0,0,0). Ensuite, vous devez traiter un peu de fonctionnalités mathématiques.

Champs de Galua

Beaucoup connaissent l'histoire romantique sur un jeune homme qui n'a vécu que 20 ans et une fois que la nuit a écrit sa théorie mathématique et, le matin, il a été tué pour des duels. C'est l'évariateur de Galua. Il a également essayé d'entrer plusieurs fois dans des universités, mais les examinateurs ne comprenaient pas ses décisions et il a échoué aux examens. Je devais apprendre lui-même. Ni Gauss, ni Poisson, qu'il a envoyé son travail, ne les a également pas compris, mais sa théorie était parfaite dans les années 60 du XXe siècle et est activement utilisé à notre époque pour les calculs théoriques dans de nouvelles sections de mathématiques et de pratique .

Nous utiliserons des conclusions assez simples, à la suite de sa théorie du groupe. L'idée principale est le nombre final (et non infini) de nombres appelé le champ, avec lequel toutes les opérations mathématiques connues peuvent être effectuées. Le nombre de chiffres dans le champ doit être un nombre simple dans une mesure naturelle, mais dans le cas de simples codes de Rida-Solomon, considéré ici, la dimension de champ est un nombre simple à degré 1. Dans les codes étendus du Solomon Reda degré de plus de 1.
Par exemple, pour la dimension de champ de galois 7, c'est-à-dire GF (7), toutes les opérations mathématiques se produiront avec des chiffres 0,1,2,3,4,5,6.
Exemple d'ajout: 1 + 2 \u003d 3; 4 + 5 \u003d 9 MOD 7 \u003d 2. L'ajout dans les champs de Galoah est une addition de modulus. La soustraction et la multiplication sont également effectuées dans le module.
Un exemple de division: 5/6 \u003d 30/36 \u003d 30 / (36 MOD 7) \u003d 30/1 \u003d 30 \u003d 30 MOD 7 \u003d 2.
La construction du degré est similaire à la multiplication.

La propriété utile se trouve dans les champs Halua lors de son érection. Comme vous pouvez le constater s'il est élevé au degré de numéro 3 ou 5 dans le champ de Galois GF (7) sélectionné, il existe tous des éléments du champ de galoi actuel, sauf 0. Ces numéros sont appelés éléments primitifs. Dans les codes de Reed-Solomon, le plus grand élément primitif du champ choisi de Galua est généralement utilisé. Pour GF (7), il est 5.
On peut noter que les chiffres dans les champs de Galua sont simultanément les abstractions qui ont une connexion plus étroite entre eux que les chiffres habituels.

Interpolation

Comme beaucoup de gens le savent de l'année scolaire, l'interpolation est de trouver un degré minimum dans cet ensemble de points. Par exemple, il y a trois points et trois valeurs d'une sorte de fonction à ces points. Vous pouvez trouver une fonctionnalité qui répond à ces données d'entrée. Par exemple, il est très facile de faire avec la transformation de la Lagrange. Une fois la fonction trouvée, vous pouvez construire quelques points de plus, et ces points seront associés à trois points de départ. La formation d'excès de symboles lors de l'encodage est une opération similaire à celle d'une interpolation.

Transformation de Fourier discrète inverse (IDFT)

La transformation de Fourier, ainsi que la théorie des groupes de Galua, constitue un autre pic de pensée mathématique, qui est actuellement utilisé dans de nombreux domaines. Certains croient même que la transformation de Fourier décrit l'une des lois fondamentales de l'univers. L'essence principale: tout signal non périodique de la longueur finale peut être représenté comme la somme de la sinusoïde de différentes fréquences et phases, il est alors possible de reconstruire le signal source. Cependant, ce n'est pas la seule description. Les numéros dans les champs de galois ressemblent à la différence dans les différentes fréquences de la sinusoïde, de sorte que la transformation de Fourier peut également être utilisée pour eux.
La transformation discrète de Fourier est une formule de transformation de Fourier pour des valeurs discrètes. La transformation a deux directions - directes et inverse. La transformation inverse est plus facile mathématiquement, alors codifiez le mot c \u003d (3,1,0,0,0) avec elle. Les deux premiers symboles sont des informations, les quatre derniers sont redondants et toujours égaux à 0.
Nous écrivons le mot de code avec le polynôme: C \u003d 3 * x 0 + 1 * x 1 + 0 * x 2 + ... \u003d 3 + x. En tant que champ de galois, nous prenons le gf (7) mentionné, où l'élément primitif \u003d 5. Faire une ligne de façade est les valeurs du polynôme C pour un élément primitif z de différents degrés. Formule IDFT: C J \u003d C (z J). C'est-à-dire que nous trouvons les valeurs de la fonction C (z), où J est les éléments du champ Galois GF (7). Nous calculons à J \u003d N-2 \u003d 7-2 \u003d 5 degrés. En regardant la table de degrés, vous pouvez deviner pourquoi: en sixième, la valeur est à nouveau 1, c'est-à-dire Il est répété à la suite de laquelle il serait impossible de déterminer quel degré a été érigé - en 6ème ou 0.
C 0 \u003d C (z 0) \u003d 3 + 1 * Z 0 \u003d 3 + 1 * 5 0 \u003d 4
C 1 \u003d C (Z 1) \u003d 3 + 1 * Z 1 \u003d 8 \u003d 1
C 2 \u003d c (z 2) \u003d 3 + 1 * z 2 \u003d 0
…
Ainsi, avec (3,1,0,0,0,0) \u003d\u003e C (4,1,0,2,5,6).

Nous transmettons le mot c (4,1,2,5,6).

Erreur

Une erreur est un autre mot qui est résumé avec le transmis. Par exemple, une erreur F \u003d (0,0,0,2,6,6). Si vous faites C + F, nous obtenons avec F (4,1,5,5).

Transformation directe de Fourier (DFT). Décodage. Syndrome

Au récepteur, nous avons eu le mot C + F \u003d C F (4,1,5,5,5). Comment vérifier s'il y avait des erreurs pendant la transmission? On sait que nous avons codé des informations utilisant IDFT dans GF (7). DFT (transformation de Fourier discrète) est une conversion, inverse Idft. L'avoir fait, vous pouvez obtenir les informations originales et quatre zéro (c'est-à-dire avec (3,1,0,0,0,0,0)), au cas où il n'y avait pas d'erreurs. Si les erreurs étaient, alors au lieu de ces quatre zéros, il y aura d'autres numéros. Nous faisons DFT pour avec F et vérifie s'il y a des erreurs. Formule DFT: avec K \u003d N -1 * C (Z -KJ). L'élément primitif Z \u003d 5 des champs GF (7) est toujours utilisé.
C 0 \u003d C (5 -0 * J) / 6 \u003d (4 * 5 -0 * 0 + 1 * 5 -1 * 0 + 0 * 5 -2 * 0 + 4 * 5 -3 * 0 + 5 * 5 -4 * 0 + 5 * 5 -5 * 0) / 6 \u003d (4 + 1 + 4 + 0 + 5 + 5) / 6 \u003d 19/6 \u003d 5/6 \u003d 30/36 \u003d 30 \u003d 2;
C 1 \u003d C (5 -1 * J) / 6 \u003d (4 * 5 -0 * 1 + 1 * 5 -1 * 1 + 0 * 5 -2 * 1 + 4 * 5 -3 * 1 + 5 * 5 -4 * 1 + 5 * 5 -5 * 1) / 6 \u003d (4 + 3/15 + 24/750 + 20/2500 + 25/15625) / 6 \u003d (4 + 3 + 24 + 20 + 25) / 6 \u003d 76/6 \u003d 456/36 \u003d 456 \u003d 1;
C 2 \u003d C (5 -2 * J) / 6 \u003d (4 * 5 -0 * 2 + 1 * 5 -1 * 2 + 0 * 5 -2 * 2 + 4 * 5 -3 * 2 + 5 * 5 -4 * 2 + 5 * 5 -5 * 2) / 6 \u003d (4 + 2 + 4 + 10 + 20) / 6 \u003d 40/6 \u003d 240/36 \u003d 240 \u003d 2;
…
avec f (4,1,0,5,5) \u003d\u003e c f (2,1, 2,1,0,5 ). Les caractères sélectionnés seraient des zéros s'il n'y avait pas d'erreurs. Maintenant, il est clair que l'erreur était. Dans ce cas, les symboles de 2,1,0,5 sont appelés syndrome d'erreur.

ALGORITHM BERLECAMPAMA-MESTI pour calculer la position d'erreur

Pour corriger l'erreur, vous devez savoir quels caractères sont transmis avec une erreur. À ce stade, il est calculé là où il y a des caractères erronés, combien d'erreurs étaient, et il est également possible de réparer un tel certain nombre d'erreurs.
L'algorithme Berekampa-Messi est engagé dans une recherche polynomiale qui, lorsqu'il multiplie une matrice spéciale, préparé à partir des numéros de syndrome (exemple ci-dessous), donnera un vecteur zéro. La preuve de l'algorithme montre que les racines de ce polynôme contiennent des informations sur les positions des caractères avec des erreurs dans le code de texte reçu.
Comme quantité maximale Les erreurs pour le cas à l'étude peuvent être 2, nous écrivons la formule du polynôme souhaité sous forme de matrice pour deux erreurs (degré polynomial 2): \u200b\u200bg \u003d.
Maintenant, nous écrivons le syndrome (2,1,0,5) dans le format de la matrice de Töpliza. Si vous regardez le syndrome et la matrice résultante, vous remarquerez immédiatement le principe de création d'une telle matrice. La dimension de la matrice est due au polynôme R, désigné ci-dessus.

L'équation à résoudre:

Les éléments sous les signes de la question n'affectent pas le résultat. Il est nécessaire de trouver G1 et G2, ils sont responsables des positions d'erreur. Nous augmenterons progressivement la dimension avec laquelle nous travaillons. Nous commençons par 1 et du bord inférieur gauche de la matrice (vert marqué) avec une dimension minimale 1x1.

Augmenter la dimension. Supposons qu'il n'y ait aucune erreur dans la position de G1. Alors g1 \u003d 0.

Nous devons obtenir à droite, ou au moins un 0 en premier lieu pour augmenter la dimension des calculs, mais en premier lieu. Nous pouvons choisir une telle valeur pour G1 (qui est maintenant 0) à droite de Obtenez le requis 0. Le processus de sélection G1 dans l'algorithme est optimisé. Nous écrivons les deux équations considérées par votre et retirons également la troisième équation, qui calcule M1. Les fleurs montrent ce qui se passe.

Ceux. Г1 \u003d 3. Je vous rappelle que le comptage va à GF (7). Il convient également de noter que la valeur de G1 est temporaire. Pendant les calculs du G2, cela peut changer. Nous considérons le côté droit:

Reçu 0 droit, augmente maintenant la dimension. Nous le supposons par analogie que r2 \u003d 0. Nous utilisons le G1 trouvé \u003d 3.

Tout d'abord, au lieu de la troïka, vous devez obtenir 0. Les actions correspondent à la précédente. Ensuite, sélectionnez la valeur de G2.

Nous écrivons une nouvelle valeur de R2 \u003d 2 à l'équation principale et essayez à nouveau de trouver les valeurs à droite:

Tâche cette chasse Ce n'était que le premier zéro, mais la volonté du deuxième élément de la matrice s'est également révélée être zéro, c'est-à-dire La tâche est résolue. S'il n'était pas zéro, nous aurions une fois de nouveau sélectionné les valeurs (cette fois pour G1 et pour R2), augmentant ainsi la dimension de la sélection. Si vous êtes intéressé par cet algorithme, voici deux autres exemples.
Donc, R1 \u003d 3, G2 \u003d 2. Les valeurs non nulles pour G1 et G2 indiquent qu'il y avait 2 erreurs. Nous écrivons la matrice R sous forme de polynôme: g (z) \u003d 1 + 3x + 2x 2. Racines prenant en compte les degrés de l'élément primitif dans lequel le résultat est obtenu 0:
G (5 3) \u003d 1 + 3 * 6 + 2 * 6 2 \u003d 91 \u003d 13 * 7 \u003d 0.
G (5 5) \u003d 1 + 3 * 3 + 2 * 3 2 \u003d 28 \u003d 0.
Cela signifie que les erreurs dans les positions 3 et 5.
De même, vous pouvez trouver les valeurs restantes pour vous assurer qu'ils ne donneront pas à Zeros:
R \u003d\u003e g (z j) \u003d (3,5,5,0,4.0). Comme vous pouvez le constater, IDFT est utilisé à nouveau dans GF (7).

Correction d'erreur par forn

À l'étape précédente, la position d'erreur a été calculée, il reste maintenant à trouver les bonnes valeurs. Erreurs de décrivant polynôme: g (z) \u003d 1 + 3x + 2x 2. Nous l'écrivons sous forme normale, multipliant par 4 et en utilisant les propriétés de GF (7): g (z) \u003d x 2 + 5x + 4.
La méthode Forn est basée sur l'interpolation de Lagrange et utilise les polynômes que nous avons utilisés dans l'algorithme Berekampa-Messi.
La méthode est en outre calculée par ces symboles qui se tiennent sur des endroits qui ne sont pas liés au syndrome. Ce sont les positions correspondant à des valeurs réelles, cependant, d'autres valeurs sont calculées pour elles, qui sont obtenues à partir de la convolution du syndrome d'erreur et de polynôme. Ces nouvelles valeurs calculées avec le syndrome forment un masque d'erreur. Ensuite, IDFT est en cours d'exécution et le résultat est une erreur directe qui a déjà été résumée avec le mot de code transmis. Il sera déduit du mot résultant et nous obtenons le mot transmis initial. Ensuite, effectuez DFT pour le mot de code transmis et finalement obtenir des informations. Suivant - comme cela arrive dans le contexte de l'exemple à l'étude.

Nous écrivons le vecteur d'erreur F (les 4 derniers caractères - le syndrome, que nous utilisons constamment, deux signes de la question - sur les lieux de symboles d'information, il s'agit d'un masque d'erreur) et nous désignons chaque symbole de la lettre:

Les symboles du polynôme du localisateur de l'erreur G (z) \u003d x2 + 5x + 4 sont notés:
La multiplication du polynôme g sur la matrice Töplits dans le paragraphe précédent était, en fait, le fonctionnement de la convolution cyclique: si les équations linéaires obtenues à partir de la matrice peuvent être constatées que les valeurs extraites du syndrome ( Les valeurs de la matrice Töpliza), de l'équation à l'équation, changent simplement dans des endroits, se déplaçant séquentiellement de manière spécifique, ce qui s'appelle une convolution. J'ai spécifiquement affiché des polynômes F et G les uns des autres au début de ce paragraphe afin que vous puissiez faire des convilios (multiplier l'élément dans un certain ordre), déplacer les polynômes visuellement. Révélant l'équation matricielle du paragraphe précédent et en utilisant les désignations des polynômes F et R, l'introduit juste:
G0 * F4 + G1 * F3 + G2 * F2 \u003d 0
G0 * F5 + G1 * F4 + G2 * F3 \u003d 0
Auparavant, la convolution n'a été effectuée que pour le syndrome, dans la méthode Fori, vous devez faire une convolution pour F0 et F1, et après avoir trouvé leurs valeurs:
G0 * F3 + G1 * F2 + G2 * F1 \u003d 0
G0 * F2 + G1 * F1 + G2 * F0 \u003d 0
F0 \u003d -G0 * F3 - G1 * F2 \u003d 0
F1 \u003d -G0 * F2 - G1 * F1 \u003d 6
C'est-à-dire f \u003d (6,0,1,1,0,5). Nous effectuons l'ifft, car l'erreur résumée avec le mot, qui était sous la forme de ifft codée: F \u003d (0,0,0,2,0,6).
Nous soustrayons l'erreur F du mot de code CF obtenu: (4,1,0,5,5,5) - (0,0,0,2,6) \u003d C (4,1,0,5,5,6)
Nous ferons DFT pour ce mot: C (4,1,0,2,5,6) \u003d\u003e C \u003d (3,1,0,0,0,0). Et voici nos personnages 3 et 1 à transmettre.

Conclusion

Habituellement utilisé des codes étendus de Reda-Solomon, c'est-à-dire que le champ de galoah est un degré de deux (GF (2 m)), par exemple le codage des octets d'informations. Les algorithmes de travail sont similaires à ceux désassemblés dans cet article.
Il existe de nombreuses variétés de l'algorithme en fonction des applications, ainsi que de l'âge de chaque variété et de la société du développeur. L'algorithme plus jeune qu'il n'est plus difficile.

Aussi de nombreux appareils utilisent tables finies Erreurs calculées à l'avance. Sous l'utilisation de l'arithmétique de Galois, le montant final est obtenu erreurs possibles. Cette propriété est utilisée pour réduire la quantité de calculs. Ici, dans le cas où le syndrome s'avère non nul, il est simplement comparé à la table des syndromes erronés possibles.

Le cours de la théorie de codage pour beaucoup est souvent l'un des plus difficiles. Je serai heureux que cet article aidera à comprendre ce sujet plus rapidement.

Dans les systèmes modernes télévision numérique Pour assurer une transmission sans bruit des signaux de télévision numériques sur la chaîne radio, le plus parfait reda Solomon codes(Reed-Solomon), nécessitant l'ajout de deux caractères de contrôle par erreur unique corrigée. Les codes Reed-Solomon ont des propriétés correctives élevées, elles ont développé des méthodes de codage relativement simples et constructives. Les codes Reed-Solomon ne sont pas binaires. Cela doit être compris en ce sens que les symboles des mots de code ne sont pas des signes binaires, mais des éléments d'un ensemble de nombres constitué de plus de deux caractères (bien entendu, chaque symbole est remplacé par une combinaison binaire correspondante).

Reed-Solomon Codes liés à la classe codes cycliquesformer un sous-groupe codes de blocs. Ils sont obtenus à partir de toute combinaison autorisée par le décalage cyclique de ses décharges. Codage et décodage, détection et correction des erreurs - ce sont des procédures informatiques qui sont correctement implémentées pour les codes cycliques comme actions avec des polynômes et la mise en œuvre sous la forme de appareils numériques sur la base des registres de changement de vitesse avec obligations inverse.

Pour obtenir une idée plus détaillée des codes de Reda Solomon, voyons quel endroit ils occupent dans la classification des codes correctifs (Fig. 4.4).

Les codes correctifs sont divisés en bloc et convolutionnels (continu). Codes de blocsbasé sur le transcodage de la combinaison de code source (bloc) contenant k.symboles d'information dans la combinaison de code transmis contenant n.>k.symboles. Supplémentaire r = n. – k.les caractères ne dépendent que sur k.symboles de la combinaison de code source. Par conséquent, le codage et le décodage sont toujours effectués dans une combinaison de code (bloc). Contrairement à cela dans codes de convolutionnelsle codage et le décodage sont effectués en continu sur la séquence de caractères binaires.

Les codes de bloc sont séparables et indissociables. DANS codes séparablesvous pouvez spécifier dans chaque combinaison de code que les symboles sont informatifs et qui sont vérifiés. DANS codes inséparablesil n'y a pas de telle possibilité.

Prochaine étape de la classification - codes systématiques. Ils se distinguent par le fait qu'ils sont des symboles d'inspection formés à partir de symboles d'information en fonction de certaines règles exprimées par des ratios mathématiques. Par exemple, chaque symbole de test h. p J. Il s'avère une combinaison linéaire de symboles d'information

Figure. 4.4.Lieu de codes de Reda Solomon dans la classification des codes correctifs

où
- coefficients prenant des valeurs 0 ou 1;
. Le rapport pour la formation d'une vérification des bits pour la vérification de la parité est un cas particulier.

Passons à une connaissance plus détaillée. avec des codes cycliques.

Tout d'abord, nous introduisons un enregistrement de la combinaison de code ou, comme cela est souvent appelé dans la littérature, le vecteur de code sous forme de polynôme. Que la combinaison de code uNE. 0 uNE. 1 uNE. 2 ...uNE. n. -1, où mais 0 - code junior, uNE. n. -1 - Code de code senior. Le polynomique correspondant

où h.- une variable formelle entrée uniquement pour obtenir une combinaison de code sous la forme d'un polynôme.

Sur les polynômes représentant des combinaisons de code, une opération mathématique de multiplication est déterminée. La particularité de cette opération par rapport aux mensonges généralement acceptés dans le fait que les coefficients sont h.tous les degrés sont résumés par module 2 et les indicateurs degrés h.en multipliant, le module est résumé n., donc h. n. = 1.

Ensuite, nous introduisons le concept produisant du polynôme. Produire une commande polynomiale ( n. – k.) peut être polynôme avec un degré plus ancien h.égal n. – k.), qui est divisé sans résidu (1 + h. n.). Les combinaisons de code autorisées sont obtenues en multipliant la procédure k. - 1, exprimant des combinaisons de code source, sur la production de polynômes.

Les codes cycliques ont la propriété de base suivante. Si la combinaison de code uNE. 0 uNE. 1 uNE. 2 ...uNE. n. -1 est autorisé, puis la combinaison de code obtenue de celui-ci par décalage cyclique uNE. n. –1 uNE. 0 uNE. 1 ...uNE. n. -2 est également autorisé dans ce code. Lors de l'enregistrement sous forme de polynômes, le fonctionnement du décalage cyclique du mot de code est réduit à la multiplication du polynôme correspondant sur h.compte tenu des règles de l'exécution de l'opération de multiplication.

Code cyclique avec polynôme produisant
construit comme suit.

1. Les polynômes sont pris
,
,
, ...,
.

2. Les combinaisons de code correspondant à ces polynômes sont enregistrées sous forme de chaînes matricielles. G., appelé matrice de production.

3. Un ensemble de combinaisons de code autorisés est formé. Il comprend une combinaison de code zéro, k. Combinaisons de code spécifiés dans la clause 1, ainsi que les sommes de leur toutes sortes de combinaisons. La sommation est basée sur les bits, et chaque catégorie est additionnée par module 2. Le nombre total de combinaisons de code résolues obtenues de cette manière est 2 k. Ce qui correspond au nombre de décharges d'informations du code.

Pour la construction du décodeur, d'abord produits produisant du polynôme
ordre k.pour la construction matrice de fixationN.:

Lignes de matrice de fixation N.il y aura des combinaisons de code déterminées par des polynômes
,
, ...,
où
- Ceci est enregistré dans l'ordre inverse par Polynom
. La matrice de correction a n.colonnes I. n. – k.lignes.

Lors du décodage, la combinaison de code adoptée uNE. 0 uNE. 1 uNE. 2 ...uNE. n. -1 multiplié scellaire par chaque chaîne de correction de la matrice. Cette opération peut être enregistrée sous la forme d'une relation:

où h. ji. - Éléments j.Les lignes de la matrice N.. Obtenu n. – k.nombres c. j. Forme vecteur formantou alors syndrome. S'il n'y a pas d'erreurs, alors tous c. j. \u003d 0. Si une erreur se produit lors de la transmission de cette combinaison de code, certains numéros c. j. Pas égal à 0. Par quels éléments du vecteur correctif différent de zéro, on peut conclure que, dans quelles décharges de la combinaison de code acceptée, il existe une erreur et corrige donc ces erreurs.

Considérons un exemple qui se trouve souvent dans la littérature. Nous construisons un code cyclique avec n.= 7;k.\u003d 4. Pour ce faire, imaginez 1 + h. 7 sous la forme d'un travail:

Dans l'algèbre conventionnelle, cette égalité est bien entendu n'est pas exécutée, mais si elle est utilisée pour apporter une telle addition habituelle, le fonctionnement de la sommation MODULO 2, et lorsque les taux de diplôme sont additionnés, le fonctionnement de la résumé du module 7, Ensuite, l'égalité sera juste.

En tant que polynôme producteur, prenez 1 + h.+h. 3. Multipliez-le sur h.,h. 2 I. h. 3 et obtenir des polynômes h.+h. 2 +h. 4 ;h. 2 +h. 3 +h. 5 ;h. 3 +h. 4 +h. 6 Puis écrivez la matrice produite G.et dans chaque ligne de la matrice, la décharge junior de la combinaison de code est située d'abord à gauche.

Ensuite, nous formons un ensemble de 15 combinaisons de code autorisés: 00000000, 1101000, 0110100, 0011010, 0001101, 1011100, 0101101, 10111100, 0101110, 00101111111, 10100011, 1000110, 0100011, 1001011. Dans ces dossiers, plus jeunes bits suivants, et aînés - Droite.

En alternance des deux premiers êtres, nous obtenons le polynôme de production pour la matrice de correction: 1 + h.+h.+h. quatre. Puis multipliez-le sur h.et h. 2 et obtenez deux autres lignes de cette matrice, ce qui en résulte un tel type (par opposition à la matrice G.ici, les plus jeunes décharges des polynômes correspondants sont situés à droite):

Supposons que la combinaison de code 0001101 soit prise en un ensemble admissible. Trouver des œuvres scalaires de cette combinaison de code avec toutes les lignes de la matrice N.:

Laissez maintenant la combinaison de code de 0001100, dans laquelle le dernier bit (senior) contient une erreur. Les œuvres scalaires de la combinaison de code acceptée sur la ligne de matrices de fixation sont les suivantes:

Ainsi, le syndrome (1, 0, 0) est obtenu. Si l'erreur s'avère être dans un autre bit de la combinaison de code, elle éteint un autre syndrome.

L'un des avantages importants des codes cycliques est la possibilité de construire des dispositifs de codage et de décodage sous la forme de registres de cisaillement avec des réactions à travers les additionneurs du module 2.

Différents types de codes cycliques sont obtenus à l'aide de divers polynômes produisant divers polynômes. Il y a une théorie mathématique développée de ce problème. Parmi le grand nombre de codes cycliques au nombre de codes de Bose-Chowudhuri-Hokwingham les plus efficaces et largement utilisés, citons (Bose, Chaudhuri, Hockwinhami, dans le compte russophone des codes), figurent parmi les premières lettres. généraliser les codes d'hémingen cas d'envoi de plusieurs erreurs. Ils forment le meilleur parmi la classe célèbre codes non aléatoirespour les canaux dans lesquels des erreurs de caractères en série se produisent de manière indépendante. Par exemple, le code BCH (63, 44) utilisé dans le système de diffusion numérique par satellite vous permet de corriger 2 ou 3 erreurs, détecter des erreurs 4 ou 5 à chaque bloc de 63 caractères. La vitesse relative de ce code est égale R= 44/63 = 0,698.

L'un des types de codes Tous est les codes de Reda Solomon. Ces codes sont liés à proche codesPuisque les symboles d'entre eux peuvent être des nombres binaires à plusieurs chiffres, tels que des octets entiers. Dans la norme européenne de télévision numérique DVB utilisée code Reda Solomonenregistré comme (204, 188, 8), où 188 est la quantité d'informations d'octets dans le package de transport de transport MPEG-2, le nombre d'octets dans l'emballage après ajout de caractères de test, 8 est la distance minimale de code entre les combinaisons de code valides . Ainsi, des emballages de flux de transport entiers contenant 1888 \u003d 1504 de bits d'information sont pris sous forme de combinaisons de code et les caractères de test vérifiés ajoutent 168 \u003d 128 bits. La vitesse relative de ce code est de 0,92. Ce code REDA Solomon vous permet de corriger efficacement 8 erreurs d'octets dans chaque package de véhicule.

Nous notons également que le code Reda Solomon utilisé dans la diffusion de la télévision numérique est souvent appelé. raccourcir. La signification de ce terme est la suivante. À partir de la théorie des codes Reda-Solomon, il s'ensuit que si le symbole de code est octet, la longueur du mot de code doit être de 255 octets (239 informations et 16 tests). Cependant, le flux de transport PackAgempeg-2 contient 188 octets. Pour correspondre à la taille de l'emballage avec les paramètres de code, 51 informations d'information zéro sont ajoutés avant de coder au début de chaque package de transport et après le codage, ces octets zéro supplémentaires sont supprimés.

Dans le récepteur pour chaque package de transport reçu contenant 204 octets, les syndromes sont calculés et il existe deux polynômes: "localisateur", dont les racines montrent la position des erreurs et le "correcteur" (évaluateur), qui donne la valeur des erreurs. . Les erreurs sont ajustées si possible. Si la correction n'est pas possible (par exemple, l'octet erroneux de plus de 8) Les données de l'emballage ne changent pas et que le paquet lui-même est marqué en installant le drapeau (premier bit après synchrobate), comme contenant des erreurs déraisonnables. Dans les deux cas, 16 excédents d'octets sont éliminés et après décodage, la longueur de l'emballage de transport devient 188 octets.