🧚 👨🏿‍🏭 🥤 Correction de plusieurs erreurs lors de l'encodage des messages 👩🏻‍🔧 🅰️ 🏀

Dans les systèmes d'information, l'échange de messages dans des réseaux de communication ou informatiques s'accompagne d'influences perturbatrices de l'environnement ou d'un intrus, ce qui conduit à l'apparition de distorsions de signal et à des erreurs de symboles lors de la transmission numérique. La lutte contre ce phénomène est réalisée à l'aide de codes de correction. Plus tôt, j'ai décrit le code de Hamming et montré comment corriger une seule erreur dans un mot de code. Naturellement, la question s'est posée sur les situations comportant un grand nombre d'erreurs. Aujourd'hui, nous allons considérer le cas de deux erreurs dans un mot de code (erreur multiple). D'une part, tout en théorie est plus ou moins simple et compréhensible, mais d'autre part, ce n'est pas du tout évident. La présentation du matériel est basée sur les travaux de E. Berlekamp.

Dispositions théoriques

L'idée d'utiliser la redondance organisée dans les messages a conduit R. Hamming à la construction du code de correction décrit ici . Le code de correction linéaire (n, k) est caractérisé par une matrice de contrôle (m × n) H.Les exigences de la matrice sont simples: le nombre de lignes coïncide avec le nombre de symboles de contrôle, ses colonnes doivent être différentes de zéro et toutes sont différentes. De plus, les valeurs de colonne décrivent les numéros de position occupés dans le mot de code par des caractères de mot qui sont des éléments du champ final.

Souvent, le décodeur utilise un calcul de syndrome calculé pour ce mot pour déterminer si un mot transmis est en erreur. Le syndrome est égal à la somme des colonnes de cette matrice multipliée par les composantes du vecteur d'erreur. Si H contient m lignes et que le code vous permet de corriger des erreurs uniques, alors la longueur du bloc (mot de code) ne dépasse pas

n \leq 2^{m} - 1

$n≤2^m-1$ ... La faisabilité de la distance requise entre les mots de code est également importante.

Les codes de Hamming atteignent cette limite. Chaque position du mot de code de Hamming peut être numérotée avec un vecteur binaire qui coïncide avec la colonne correspondante de la matrice H.Dans ce cas, le syndrome coïncidera directement avec le numéro de position où l'erreur s'est produite (s'il n'y a qu'une seule erreur) ou avec la somme binaire des nombres (s'il y a plusieurs erreurs).

La numérotation vectorielle est une idée très fructueuse. De plus, nous supposerons

n \leq 2^{m} - 1

$n≤2^m-1$ et que la i-ième position du mot est numérotée i.

La numérotation binaire (c'est-à-dire une telle représentation) est appelée localisateur de position. Supposons que vous souhaitiez corriger toutes les erreurs doubles et simples. Apparemment, cela nécessitera une grande redondance de code, c'est-à-dire la matrice H doit avoir plus de lignes (deux fois le nombre). Par conséquent, nous allons former une matrice H avec 2m lignes et avec

n \leq 2^{m} - 1

$n≤2^m-1$ colonnes, et il est sage de choisir différentes colonnes. Pour les m premières lignes, nous prendrons la matrice précédente du code de Hamming. Ce sont les vecteurs de mots de base de l'espace de mots.

Exemple 1

Soit m = 5 et n = 31. Il serait souhaitable d'obtenir un (n, k) -code qui corrige les doubles erreurs, avec une matrice de contrôle de parité H sous la forme:

Pour les fonctions fj (ξ) indiquées dans la matrice, il est souhaitable d'avoir une fonction qui mappe ensemble de vecteurs à 5 dimensions en lui-même. Les 5 dernières lignes de la matrice définiront le code de Hamming si et seulement si la fonction f est une bijection (permutation).

Si les 5 premières lignes et les 5 dernières lignes vous permettent de corriger séparément des erreurs uniques, elles vous permettront peut-être ensemble de corriger deux erreurs.

Il faut apprendre à additionner, soustraire, multiplier et diviser les vecteurs binaires à 5 dimensions, les représenter par des polynômes de degré au plus 4, afin de trouver la fonction recherchée fj (required).

Exemple 2

00000 ← → 0

00010 ← → 1

00011 ← → x

...

11011 \leftarrow\to х^{4} + х^{3} + х + 1

$11011 ←→ ^4 +^3++1$

La somme et la différence de tels polynômes correspondent à la somme et à la différence des vecteurs:

0 ± 0 = 0, 0 ± 1 = 1, 1 ± 0 = 1, 1 ± 1 = 0, les signes de ± ont la même signification dans le cas binaire. Ce n'est pas le cas avec la multiplication, l'exposant du résultat de la multiplication peut dépasser 4.

Exemple 3

(х^{3} + х + 1) х^{4} + х^{3} + х + 1) = х^{7} + х^{6} + х^{5} + 3 х^{4} + 2 х^{3} + х^{2} + 2 х + 1 =

$(^3++1)^4+^3++1)=^7+^6+^5+3^4+2^3+^2+2+1=$

= х^{7} + х^{6} + х^{5} + х^{4} + х^{2} + 1

$=^7+^6+^5+^4+^2+1$ ...

Il faut une méthode d'abaissement des degrés supérieurs à 4.

Elle est appelée (réduction) la construction de résidus modulo un polynôme irréductible M (x) de degré 5; la méthode consiste en la transition des polynômes des produits à leurs restes après division par

M (x) = x^{5} + x^{2} + 1

$M(x)=x^5+x^2 + 1$

Pour que

х^{7} + х^{6} + х^{5} + х^{4} + х^{2} + 1 = (х^{2} + х + 1) (х^{5} + х^{2} + 1) + х^{3} + х^{2} + х

$^7+^6+^5+^4+^2+1 =(^2+ + 1)(^5 +^2 +1) +^3 +^2 +$ ou

х^{7} + х^{6} + х^{5} + х^{4} + х^{2} + 1 \equiv (х^{3} + х^{2} + x) m o d (х^{5} + х^{2} + 1) .

$^7+^6+^5+^4+^2+1 ≡(^3+^2 + x)mod(^5 +^2 +1).$

Le symbole ≡ indique «comparable à».

Sous forme générale A (x) ≡a (x) mod M (x)

Si et seulement s'il existe un polynôme C (x) tel que

A (x) = M (x) C (x) + a (x) les coefficients des polynômes sont réduits modulo deux:

A (x) ≡ a (x) mod (2, M (x)).

Propriétés importantes des comparaisons

Si a (x) ≡A (x) mod M (x) et b (x) ≡ B (x) mod M (x), alors

a (x) ± b (x) ≡ A (x) ± B (x ) mod M (x) et

(x) b (x) ≡ (x) B (x) mod M (x).

De plus, si les degrés des polynômes a (x) et A (x) sont inférieurs au degré de M (x), alors

il résulte de la formule a (x) ≡ A (x) mod (2, M (x)) que a (x) = A (x).

Il existe 2 classes de résidus différentes en degré degM (x) - c'est-à-dire autant qu'il y a de polynômes différents de degré inférieur à m, i.e. combien de résidus de division différents peuvent être. La division est encore plus difficile.

Algorithme de division

Pour les chiffres.

Pour a et M donnés, il existe des nombres q et A définis de manière unique, tels que a = qM + A, 0 ≤ A ≤ M,

Pour les polynômes avec des coefficients d'un champ donné.

Pour a (x) et M (x) donnés, il existe des polynômes q (x) et A (x) définis de manière unique tels que a (x) = q (x) M (x) + A (x), degA (x ) <deg M (x).

La possibilité de diviser les polynômes est fournie par l'algorithme euclidien.

Pour les nombres, un exemple de GCD étendu est décrit ici .

Pour a et b donnés, il existe des nombres A et B tels que aA + bB = (a, b), où (a, b) est le GCD des nombres a et b.

Pour les polynômes avec des coefficients d'un champ donné.

Pour a (x) et b (x) donnés, il existe des polynômes A (x) et B (x) tels que

a (x) A (x) + b (x) B (x) = (a (x), b (X)),

où (a (x), b (x)) est le diviseur commun normalisé de a (x) et b (x) de plus grand degré.

Si a (x) et M (x) ont un diviseur commun d (x) ≠ 1, alors la division par a (x) mod M (x) n'est pas toujours possible.

Il est évident que la division par a (x) équivaut à une multiplication par A (x).

Puisque si (a (x), b (x)) = 1 = GCD, alors selon l'algorithme d'Euclide, il y a A (x) et B (x) tels que a (x) A (x) + b (x) B (x) = 1, de sorte que a (x) A (x) ≡ 1mod b (x). Vérifier qu'un polynôme binaire est irréductible sur le champ GF (

2^{5}

$2^5$ ), est effectuée par division directe par tous les diviseurs possibles avec des degrés inférieurs à deg M (x).

Exemple 4 .

M (x) = x^{5} + x^{2} + 1

$M(x) = x^5+x^2 +1$ divisé par x et (x + 1)

par des diviseurs linéaires. Le résultat de la division n'est pas nul. Diviser par des diviseurs carrés

х^{2}, х^{2} + х = х (х + 1), х^{2} + 1, х^{2} + 2 х + 1 = (х + 1)^{2}, х^{2} + х + 1.

$^2 , ^2 +=( +1),^2 +1, ^2 +2 +1= ( +1)^2, ^2 + + 1.$ ... Ils donnent des soldes non nuls. Les diviseurs de degré ≥ 3 n'existent pas, car leur produit donne le degré ≥ 6.

Ainsi, les polynômes peuvent être additionnés, soustraits, multipliés et divisés modulo

M (x) = x^{5} + x^{2} + 1

$M(x) = x^5+x^2 +1$ ...

Nous passons à la recherche d'une fonction pour la matrice de contrôle de parité H définissant un code de correction d'erreur double avec une longueur de bloc de 31 et un taux de 21/31; 31-21 = 10 = 2t - symboles de contrôle = 10. Une telle fonction doit avoir comme racines les nombres de positions erronées dans le mot de code, c'est-à-dire Lorsque les numéros de position sont remplacés dans cette fonction, elle la met à zéro.

Fonction de recherche

Supposons que β1 et β2 soient les nombres des caractères déformés (positions) du mot. En utilisant la notation binaire des nombres β1 et β2 , ces nombres peuvent être représentés comme des classes de résidus modulo M (x) i.e. établir la correspondance βi → β ⁽ⁱ⁾ (x) - polynômes binaires de degré <5.

Les 5 premières conditions de test déterminent β1 + β2 ; le deuxième ensemble d'équations de test doit déterminer f (β1) + f (β2) .

Le décodeur doit déterminer β1 et β2 selon le système donné:

quelle devrait être la fonction f (x) ?

La fonction la plus simple est la multiplication par une constante f (β) ≡ αβ () modM (x) .

Mais alors ξ2 = αξ1 , c'est-à-dire les équations du système dépendent. Les cinq nouvelles conditions de test ne donneront rien de nouveau au décodeur.

De même, la fonction f (β) = β + α ne change pas la situation, puisque ξ2 = ξ1 .

Essayer les fonctions de puissance: première prise

f (β) = β^{2}

$f(β) = β^2$ ... De plus,

ces équations sont également dépendantes, car

ξ 1^{2} = (β 1 + β 2)^{2} = β 1^{2} + 2 β 1 β 2 + β 2^{2} = β 1^{2} + β 2^{2} = ξ 2

$ξ1^2 =(β1 + β2)^2=β1^2 + 2β1β2 + β2^2 = β1^2 + β2^2 =ξ2$

La deuxième équation est donc le carré de la première.

En essayant

f (β) = β^{3}

$f(β) = β^3$ ... Changer la forme de l'équation du décodeur:

Emplacement

ξ 2 = β 1^{3} + β 2^{3} = (β 1 + β 2) (β 1^{2} - β 1 β 2 + β 2^{2}) = ξ 1 (β 1 β 2 - ξ 1^{2}) .

$ξ2 =β1^3 + β2^3=(β1 + β2)(β1^2 -β1β2+ β2^2)=ξ1(β1β2-ξ1^2).$

Donc pour ξ1 ≠ 0 nous avons

donc, β1 et β2 satisfont l'équation.

Ainsi, si exactement deux erreurs se sont produites, alors leurs localisateurs satisfont cette équation.

Puisque cette équation a exactement 2 racines dans le domaine des polynômes binaires modulo M (x) , le décodeur peut toujours trouver les deux localisateurs nécessaires.

Si une seule erreur se produit, alors β1 = ξ1 et $β1^2 = ξ2$ ... Par conséquent, dans ce cas, la seule erreur satisfait l'équation β + ξ1 = 0 ou 1+ ξ1β ^-1 = 0 .

Enfin, le décodeur effectue toujours le décodage, si aucune erreur ne s'est produite, dans ce cas ξ1 + ξ2 = 0 .

Il est plus pratique (en pratique) d'opérer non pas directement avec un polynôme dont les racines sont des localisateurs d'erreur, mais avec un polynôme dont les racines sont mutuelles aux localisateurs; ceux. sont des réciproques multiplicatifs pour eux.

Il est clair qu'avec pas plus de deux erreurs, le décodeur peut déterminer les numéros d'erreur. Si trois symboles ou plus sont déformés, une erreur de décodage ou un échec de décodage se produit.

Donc la fonction

f (x) = x^{3}

$f(x) = x^3$ approprié pour construire les cinq rangées inférieures de la matrice de contrôle H d'un code binaire avec une longueur de mot de code de 31 et 10 symboles de contrôle, corrigeant toutes les erreurs doubles.

Les cinq premiers contrôles spécifient la somme des nombres d'erreur (S1); les cinq secondes vérifications sont la somme des cubes de numéros d'erreur (S3).

La procédure de décodage comprend trois étapes principales:

chaque mot de code reçu est vérifié et S1 et S3 sont calculés;
trouver le polynôme de localisation d'erreur dans σ (z);
les valeurs mutuelles des racines σ (z) sont calculées et les symboles aux positions correspondantes du mot résultant sont modifiés.

Correction de plusieurs erreurs lors de l'encodage des messages

Dispositions théoriques

Propriétés importantes des comparaisons

Algorithme de division

Fonction de recherche

More articles: