Worldlex Wiki En théorie du codage , les codes de Bose - Chaudhuri - Hocquenghem ( codes BCH ) forment une classe de codes correcteurs d'erreurs cycliques construits à l'aide de polynômes sur un corps fini (également appelé corps de Galois ). Les codes BCH ont été inventés en 1959 par le mathématicien français Alexis Hocquenghem , puis indépendamment en 1960 par Raj Chandra Bose et D.K. Ray-Chaudhuri . Le nom Bose - Chaudhuri - Hocquenghem (et l'acronyme BCH ) provient des initiales des noms de famille des inventeurs (à tort, dans le cas de Ray-Chaudhuri).
L'une des principales caractéristiques des codes BCH est le contrôle précis, lors de leur conception, du nombre d'erreurs de symboles corrigibles. Il est notamment possible de concevoir des codes BCH binaires capables de corriger plusieurs erreurs de bits. Un autre avantage des codes BCH réside dans la facilité de leur décodage, grâce à une méthode algébrique appelée décodage par syndrome . Cette méthode simplifie la conception du décodeur, qui peut être réalisée avec des composants électroniques compacts et basse consommation .
Les codes BCH sont utilisés dans des applications telles que les communications par satellite, les lecteurs de disques compacts , les DVD , les lecteurs de disques , les clés USB , les disques SSD , et les codes-barres bidimensionnels .
nombre premier une puissance première des entiers positifs corps fini (ou corps de Galois) une distance d'au moins élément primitif de entier positif polynôme minimal à coefficients dans polynôme générateur du code BCH est défini comme le plus petit commun multiple code polynomial défini parCodes généraux BCH
Les codes BCH généraux diffèrent des codes BCH primitifs au sens strict à deux égards.
Premièrement, la condition selon laquelle l'élément doit être primitif peut être assouplie. En assouplissant cette condition, la longueur du code passe de à l' ordre de l'élément
Deuxièmement, les racines consécutives du polynôme générateur peuvent provenir de au lieu de
Définition. Soit un corps fini où est une puissance d'un nombre premier. Choisissons des entiers positifs tels que et soit l' ordre multiplicatif de modulo
Comme précédemment, soit une racine primitive n-ième de l'unité dans et soit le polynôme minimal sur de pour tout . Le polynôme générateur du code BCH est défini comme le plus petit commun multiple
Remarque : si, comme dans la définition simplifiée, alors vaut 1, et l'ordre du modulo est . Par conséquent, la définition simplifiée est bien un cas particulier de la définition générale.
Cas particuliers
- Un code BCH avec est appelé un code BCH au sens strict .
- Un code BCH avec est appelé primitif .
Le polynôme générateur d'un code BCH a des coefficients appartenant à . En général, un code cyclique sur avec comme polynôme générateur est appelé un code BCH sur . Le code BCH sur et le polynôme générateur avec des puissances successives de comme racines est un type de code de Reed-Solomon où l'alphabet du décodeur (syndromes) est le même que l'alphabet du canal (données et polynôme générateur), tous les éléments de . L'autre type de code de Reed-Solomon est un code de Reed-Solomon à vue originale qui n'est pas un code BCH.
Propriétés
Chaque polynôme minimal est de degré au plus . Par conséquent, le plus petit commun multiple de ces polynômes est de degré au plus . De plus, si , alors pour tout . Par conséquent, est le plus petit commun multiple d'au plus polynômes minimaux d'indices impairs, chacun de degré au plus . |
Rappelons que sont des racines de donc de . Ceci implique que satisfont les équations suivantes, pour chaque :
Sous forme matricielle, nous avons
Le déterminant de cette matrice est égal à
On constate que la matrice est une matrice de Vandermonde , et son déterminant est
qui est non nul. Il s'ensuit donc que …
Codage
Étant donné que tout polynôme multiple du polynôme générateur constitue un mot de code BCH valide, le codage BCH consiste simplement à trouver un polynôme dont le générateur est un facteur.
Le code BCH lui-même ne donne aucune indication sur la signification des coefficients du polynôme ; conceptuellement, un algorithme de décodage BCH a pour seul objectif de trouver le mot de code valide dont la distance de Hamming avec le mot de code reçu est minimale. Par conséquent, le code BCH peut être implémenté comme un code systématique ou non, selon la manière dont l'implémenteur choisit d'intégrer le message dans le polynôme codé.
Encodage non systématique : le message en tant que facteur
La méthode la plus simple pour trouver un polynôme multiple du générateur consiste à calculer le produit d'un polynôme quelconque par le générateur. Dans ce cas, le polynôme peut être choisi en utilisant les symboles du message comme coefficients.
À titre d'exemple, considérons le polynôme générateur , choisi pour être utilisé dans le code BCH binaire (31, 21) utilisé par POCSAG et d'autres. Pour encoder le message de 21 bits {101101110111101111101}, nous le représentons d'abord comme un polynôme sur :
Ensuite, calculez (également sur ) :
Ainsi, le mot de code transmis est {1100111010010111101011101110101}.
Le récepteur peut utiliser ces bits comme coefficients et, après correction d'erreurs pour garantir un mot de code valide, peut recalculer
Encodage systématique : le message comme préfixe
Un code systématique est un code dans lequel le message apparaît textuellement quelque part dans le mot de code. Par conséquent, le codage BCH systématique consiste d'abord à intégrer le polynôme du message dans le polynôme du mot de code, puis à ajuster les coefficients des termes restants (non liés au message) afin de garantir que soit divisible par .
Cette méthode d'encodage exploite le fait que la soustraction du reste d'un dividende donne un multiple du diviseur. Par conséquent, si nous prenons notre polynôme de message comme précédemment et que nous le multiplions par (pour « décaler » le message par rapport au reste), nous pouvons alors utiliser la division euclidienne des polynômes pour obtenir :
Ici, nous constatons que est un mot de code valide. Comme est toujours de degré inférieur à (qui est le degré de ), nous pouvons le soustraire sans risque de sans modifier aucun des coefficients du message, d'où notre .
Sur (c'est-à-dire avec des codes BCH binaires), ce processus est indiscernable de l'ajout d'un contrôle de redondance cyclique , et si un code BCH binaire systématique est utilisé uniquement à des fins de détection d'erreurs, nous voyons que les codes BCH ne sont qu'une généralisation des mathématiques des contrôles de redondance cycliques .
L'avantage du codage systématique est que le récepteur peut récupérer le message original en supprimant tout ce qui suit les premiers coefficients, après avoir effectué la correction d'erreurs.
Décodage
Il existe de nombreux algorithmes pour décoder les codes BCH. Les plus courants suivent le schéma général suivant :
- Calculer les syndromes s j pour le vecteur reçu
- Déterminez le nombre d'erreurs t et le polynôme localisateur d'erreurs Λ(x) à partir des syndromes.
- Calculez les racines du polynôme de localisation d'erreur pour trouver les positions d'erreur X i
- Calculez les valeurs d'erreur Y i à ces emplacements d'erreur
- Corrigez les erreurs
Lors de certaines étapes de décodage, l'algorithme peut déterminer que le vecteur reçu comporte trop d'erreurs et ne peut être corrigé. Par exemple, si aucune valeur appropriée de t n'est trouvée, la correction échoue. Dans un code tronqué (non primitif), une erreur peut se situer hors limites. Si le vecteur reçu contient plus d'erreurs que le code ne peut en corriger, le décodeur peut, à son insu, produire un message apparemment valide qui n'est pas celui qui a été envoyé.
Calculer les syndromes
Le vecteur reçu est la somme du mot de code correct et d'un vecteur d'erreur inconnu. Les valeurs du syndrome sont formées en considérant comme un polynôme et en l'évaluant à Ainsi, les syndromes sont
pour
Puisque sont les zéros de dont est un multiple, l'examen des valeurs du syndrome isole ainsi le vecteur d'erreur afin que l'on puisse commencer à le résoudre.
S'il n'y a pas d'erreur, pour tous les syndromes, si tous sont nuls, alors le décodage est terminé.
Calculer le polynôme de localisation d'erreur
S'il existe des syndromes non nuls, alors il y a des erreurs. Le décodeur doit déterminer le nombre d'erreurs et leur emplacement.
S'il y a une seule erreur, indiquez-la sous la forme où représente l'emplacement de l'erreur et son amplitude. Les deux premiers syndromes sont alors :
Ainsi, ensemble, ils nous permettent de calculer et de fournir certaines informations à leur sujet (en le déterminant complètement dans le cas des codes Reed-Solomon).
S'il y a deux erreurs ou plus,
Il n'est pas immédiatement évident comment commencer à résoudre les syndromes qui en résultent pour les inconnues et
La première étape consiste à trouver, compatibles avec les syndromes calculés et avec le polynôme de localisation minimal possible :
Voici trois algorithmes populaires pour cette tâche :
- Algorithme de Peterson – Gorenstein – Zierler
- Algorithme de Berlekamp-Massey
- Algorithme euclidien de Sugiyama
Algorithme de Peterson – Gorenstein – Zierler
L'algorithme de Peterson constitue la deuxième étape de la procédure de décodage BCH généralisée. Il est utilisé pour calculer les coefficients polynomiaux du localisateur d'erreurs d'un polynôme.
Voici maintenant la procédure de l'algorithme de Peterson–Gorenstein–Zierler. Supposons que nous ayons au moins 2 t syndromes s c , ..., s c +2 t −1 . Soit v = t .
Polynôme de localisation d'erreur de facteur
Maintenant que vous avez le polynôme, ses racines peuvent être trouvées par force brute, par exemple à l'aide de l' algorithme de recherche de Chien . Les puissances exponentielles de l'élément primitif indiquent les positions où se produisent les erreurs dans le mot reçu ; d'où le nom de polynôme « localisateur d'erreurs ».
Les zéros de Λ( x ) sont α − i 1 , ..., α − i v .
Calculer les valeurs d'erreur
Une fois les emplacements des erreurs identifiés, l'étape suivante consiste à déterminer les valeurs d'erreur à ces emplacements. Ces valeurs d'erreur servent ensuite à corriger les valeurs reçues afin de retrouver le mot de code d'origine.
Dans le cas du BCH binaire (avec tous les caractères lisibles), c'est trivial : il suffit d'inverser les bits du mot reçu à ces positions pour obtenir le mot de code corrigé. Dans le cas plus général, les coefficients d'erreur peuvent être déterminés en résolvant le système linéaire.
Algorithme de Forney
Il existe cependant une méthode plus efficace, connue sous le nom d'algorithme de Forney .
Laisser
Et le polynôme d'évaluation d'erreur
Enfin:
où
Si les syndromes pouvaient s'expliquer par un mot d'erreur, qui ne pourrait être non nul qu'à certaines positions , alors les valeurs d'erreur sont
Pour les codes BCH au sens strict, c = 1, donc l'expression se simplifie à :
Explication du calcul de l'algorithme de Forney
Elle est basée sur l'interpolation de Lagrange et les techniques des fonctions génératrices .
Considérons et, par souci de simplicité, supposons que pour et pour . Alors
v, 
c+d-2. Nous souhaitons calculer des inconnues et nous pourrions simplifier le contexte en supprimant certains termes. Ceci conduit au polynôme d'évaluation d'erreur.
Grâce à nous avons
Grâce à (l'astuce d'interpolation de Lagrange), la somme se réduit à un seul terme pour
Pour obtenir ce résultat, il suffit de supprimer le produit. On pourrait le calculer directement à partir des racines déjà calculées , mais on peut utiliser une forme plus simple.
En tant que dérivé formel
nous n'obtenons à nouveau qu'un seul sommateur dans
Alors finalement
Cette formule est avantageuse lorsqu'on calcule la dérivée formelle de la forme
cédant :
où
Décodage basé sur un algorithme euclidien étendu
Une autre méthode pour déterminer à la fois le polynôme Λ et le polynôme localisateur d'erreurs est basée sur l'adaptation par Yasuo Sugiyama de l' algorithme d'Euclide étendu . La correction des caractères illisibles pourrait également être facilement intégrée à l'algorithme.
Soient les positions des caractères illisibles. On crée un polynôme localisant ces positions. On attribue la valeur 0 aux positions illisibles et on calcule les syndromes.
Comme nous l'avons déjà défini pour la formule de Forney, soit
Exécutons l'algorithme d'Euclide étendu pour trouver le plus petit commun diviseur de polynômes . L'objectif n'est pas de trouver le plus petit commun diviseur, mais un polynôme de degré au plus et des polynômes tels que . Un faible degré de garanties satisfait les conditions de définition étendues (par ) pour
Définir et utiliser à la place de dans la formule de Fourney nous donnera des valeurs d'erreur.
Le principal avantage de cet algorithme est qu'il effectue simultanément les calculs nécessaires à la formule de Forney.
Explication du processus de décodage
L'objectif est de trouver un mot de code qui diffère le moins possible du mot reçu sur les positions lisibles. En exprimant le mot reçu comme la somme du mot de code le plus proche et du mot d'erreur, on cherche à trouver le mot d'erreur contenant le moins de zéros possible sur les positions lisibles. Syndrom restreint le mot d'erreur par condition.
On pourrait écrire ces conditions séparément ou on pourrait créer un polynôme
et comparer les coefficients proches des puissances de
Supposons qu'il y ait une lettre illisible à la position ; nous pourrions remplacer l'ensemble des syndromes par l'ensemble des syndromes défini par l'équation. Supposons que, pour un mot erroné, toutes les restrictions de l'ensemble original des syndromes soient respectées.
Un nouvel ensemble de syndromes restreint le vecteur d'erreur
De la même manière que l'ensemble initial de syndromes restreignait le vecteur d'erreur, sauf à la coordonnée où nous avons un est nul, si, pour localiser les positions d'erreur, nous pourrions modifier l'ensemble de syndromes de manière similaire afin de prendre en compte tous les caractères illisibles. Cela raccourcit l'ensemble de syndromes de
Dans la formulation polynomiale, le remplacement de l'ensemble des syndromes par l'ensemble des syndromes conduit à
Donc,
Après le remplacement de par , il faudrait une équation pour les coefficients proches des puissances
On pourrait envisager de rechercher les positions erronées en éliminant l'influence de positions données, de la même manière que pour les caractères illisibles. Si l'on trouve des positions telles que leur élimination conduit à un ensemble de syndromes composés uniquement de zéros, alors il existe un vecteur d'erreur dont les erreurs ne portent que sur ces coordonnées. Si désigne le polynôme qui élimine l'influence de ces coordonnées, on obtient
Dans l'algorithme euclidien, on cherche à corriger au maximum les erreurs (sur les positions lisibles), car un nombre d'erreurs plus élevé pourrait indiquer la présence de plusieurs mots de code à la même distance du mot reçu. Par conséquent, pour la valeur recherchée, l'équation doit être vérifiée pour des coefficients proches des puissances commençant par
Dans la formule de Forney, on pourrait multiplier par un scalaire, ce qui donnerait le même résultat.
Il peut arriver que l'algorithme d'Euclide trouve un nombre de racines différentes supérieur à son degré, auquel cas la formule de Fourney pourrait corriger les erreurs dans toutes ses racines. Cependant, corriger autant d'erreurs peut s'avérer risqué (surtout sans autres restrictions sur le mot reçu). Généralement, lorsqu'un nombre de racines atteint un degré élevé, on décide de ne pas le corriger. La correction peut échouer si le nombre de racines est de multiplicité supérieure ou si le nombre de racines est inférieur au degré du nombre de racines. Cet échec peut également être détecté par la formule de Forney qui renvoie une erreur en dehors de l'alphabet transmis.
Corrigez les erreurs
À partir des valeurs d'erreur et de l'emplacement de l'erreur, corrigez les erreurs et formez un vecteur de code corrigé en soustrayant les valeurs d'erreur aux emplacements d'erreur.
Exemples de décodage
Décodage du code binaire sans caractères illisibles
Considérons un code BCH dans GF(2 4 ) avec et . (Ce code est utilisé dans les codes QR .) Soit le message à transmettre [1 1 0 1 1] , ou en notation polynomiale, . Les symboles de « somme de contrôle » sont calculés en divisant par et en prenant le reste, ce qui donne ou [ 1 0 0 0 0 1 0 1 0 0 ] . Ces symboles sont ajoutés au message, de sorte que le mot de code transmis est [ 1 1 0 1 1 1 0 0 0 0 1 0 1 0 0 ] .
Imaginons maintenant qu'il y ait deux erreurs de bits dans la transmission, de sorte que le mot de code reçu soit [ 1 0 0 1 1 1 0 0 0 1 1 0 1 0 0 ]. En notation polynomiale :
Afin de corriger les erreurs, calculez d'abord les syndromes. En prenant et , appliquez ensuite la procédure de Peterson en réduisant les lignes de la matrice augmentée suivante .
Du fait de la présence d'une ligne nulle, la matrice
Décodage avec des caractères illisibles
Supposons le même scénario, mais que le mot reçu contienne deux caractères illisibles [ 1 0 0 ? 1 1 ? 0 0 1 1 0 1 0 0 ]. Nous remplaçons ces caractères illisibles par des zéros lors de la création du polynôme reflétant leurs positions. Nous calculons les syndromes (en utilisant la notation logarithmique, indépendante des isomorphismes GF(2 4 )). Pour la vérification des calculs, nous pouvons utiliser la même représentation pour l'addition que dans l'exemple précédent. La description hexadécimale des puissances de est successivement 1, 2, 4, 8, 3, 6, C, B, 5, A, 7, E, F, D, 9, l'addition étant basée sur l'opérateur OU exclusif bit à bit.
Faisons du polynôme du syndrome
calculer
Exécutez l'algorithme d'Euclide étendu :
Nous avons atteint un polynôme de degré au plus 3, et comme
nous obtenons
Donc,
Ne vous inquiétez pas, trouvez par force brute une racine de . Les racines sont et (après avoir trouvé par exemple, nous pouvons diviser par le monome correspondant et la racine du monome résultant pourrait être trouvée facilement).
Laisser
Recherchons les valeurs d'erreur à l'aide de la formule
où sont les racines de Nous obtenons
En fait, cela ne devrait pas surprendre.
Le code corrigé est donc [ 1 1 0 1 1 1 0 0 0 0 1 0 1 0 0].
Exécutons l'algorithme d'Euclide étendu :
Nous avons atteint un polynôme de degré au plus 3, et comme
nous obtenons
Donc,
Ne vous inquiétez pas, la racine de est
Laisser
Cherchons les valeurs d'erreur à l'aide de la formule où sont les racines du polynôme
Nous obtenons
Ce qui ne devrait pas surprendre.
Le code corrigé est donc [ 1 1 0 1 1 1 0 0 0 0 1 0 1 0 0].Hocquenghem, A. ( septembre 1959), « Codes correcteurs d'erreurs », Chiffres (en français), 2 , Paris : 147-156
Sources secondaires
- Wayback Machine)
- Gorenstein, Daniel ; Peterson, W. Wesley ; doi : 10.1016/s0019-9958(60)90877-9
- Reed, Irving S. ; Chen, Xuemin (1999), Codage de contrôle d'erreurs pour les réseaux de données , Boston, MA : Kluwer Academic Publishers , ISBN0-7923-8528-4
Pour en savoir plus
- Blahut, Richard E. (2003), Codes algébriques pour la transmission de données (2e éd.), Cambridge University Press , ISBN0-521-55374-1
- Sloane, NJA (1977), La théorie des codes correcteurs d’erreurs , New York, NY : North-Holland Publishing Company
-
Plus d articles de Worldlex Wiki
Revenez a l index pour explorer davantage de pages sur l histoire, la science, la culture, la geographie et la societe en francais.
Explorer l index