Maîtrise Informatique 2000-2001, Université de Marne la Vallée

Codage et Cryptographie: Constructeur de Codes BCH

Daniele Raffo

12 février 2001

Présentation du projet

Ce programme réalise la construction d'un code BCH de longueur et capacité de correction desiré. Il peut être aussi utilisé pour la création et l'exploration d'un corps finis Fq (q = p^m), où Fq = Fp [x] / P(x) irréductible de Fp [x] de degré m, et donc aussi pour des opérations sur Fp = Z/pZ.
Un début du code pour l'implementation de l'algorithme de Berlekamp a eté aussi écrit.

Le projet (BCH.tar.gz, 17564 bytes) a été écrit en langage Java 1.1 sur Linux. Pour compiler les sources, donner la commande javac *.java.
Une documentation de toutes les classes en format javadoc a eté aussi engendrée.

NB: Dans ce rapport, j'ai indiqué enpolice fixe grasles noms de méthodes et de classes et en police fixe simple les noms de variable.

Corps finis Fq

Un corps fini est un anneau commutatif fini sans diviseurs de 0. Consideré un nombre p premier, on peut construire un corps Fq (q = p^m) comme Fq = Fp [x] / P(x) irréductible de Fp [x] de degré m. Les éléments de Fq seront alors tous les polynômes de degré m-1 à coefficients dans Fp (Fp = Z/pZ).

Un élément primitif d'un corps Fq est un élément alfa tel que tout élément non nul du corps s'écrit comme puissance de alfa. L'élément alfa est primitif ssi l'ordre de alfa divise q-1: ceci équivaut à dire que, pour tout i diviseur de q-1, alfa^i est différent de 1. On remarque que alfa^(q-1) est toujours égal à 1, pour les proprietés d'un corps fini.
A partir d'un élément primitif alfa, on peut engendrer la table des logarithmes, qui liste toutes les puissances de alfa^0 à alfa^(q-1). Alors, alfa est appelé un générateur.
Enfin, pour trouver l'inverse d'un élément B de Fq en connaissant un générateur alfa, il faut rechercher n tel que alfa^n = B (un tel n existe car on se trouve dans un corps fini). alfa^(q-1) = 1 et donc B = alfa^n = alfa^(n-(q-1)), ce qui nous donne B^(-1) = alfa^((q-1)-n).

Implementation

La tâche de la construction d'un corps fini est attribuée à la classe class Corps.
Un objet Corps a trois attributs entiers: p, m et q. p et m sont passés en paramètre (avec le polynômeirreductibleà utiliser comme générateur) au constructeur de la classe, tandis que q est initialisé comme q = p^m. Le deux autres variables globales qu'un Corps posséde sontprimitifs(un array de tous les polynômes primitifs) ettableLogs(un array contenant la table des logarithmes).

Les méthodes suivantes agissent sur les entiers dans Fp (c'est à dire Z/pZ ): int add(int a, int b) et int mult(int a, int b) retournent réspectivement le résultat de l'addition et de la multiplication de a et b (en faisant une opération modulo p). Ces deux méthodes sont utilisés par void affichetableAdd() et void affichetableMult() qui affichent respectivement la table de l'addition et la table de la multiplication.

public Polynome adjusteCoeffsPolynome(Polynome polyz)
Transforme dans Fp tous les coefficients du polynome polyz, en leur appliquant l'opération modulo p.

public Polynome[] divise(Polynome dividende, Polynome diviseur)
Divise deux polynômes. Avant de demarrer chaque cycle de la division, une boucle ajoute p au coefficient de la plus grande puissance de x du dividende, jusqu'il est multiple du coefficient de la plus grande puissance de x du diviseur; ceci pour assurer que le resultat de la division des deux nombres soit entier.
A chaque cycle, adjusteCoeffsPolynome est appelé sur le dividende partiel et le diviseur.
La méthode retourne un array de deux éléments qui sont, réspectivement, le resultat et le reste de la division.

public Polynome adjustePuissancesPolynome(Polynome polyz)
Transforme le polynôme polyz (dans Z) en un polynôme dans Fp^m (donc, de degré strictement inférieur à m); d'aprés la théorie, ce dernier n'est que le reste de la division de polyz par le polynôme irreductible.

public int adjuste(int exposant)
Adjuste une puissance en lui appliquant l'opération modulo q-1.

Polynome[] tousLesPolynomes()
Engendre tous les m*p polynômes du corps (qui ont pour coefficients toutes les combinaisons des entiers de Fp).

public void afficheTableAddPolynomes(Polynome[] tousPolys)
Affiche la table de l'addition des polynômes du corps, en appliquant la méthode add de la classe Polynome. La méthode adjusteCoeffsPolynome est en suite appelée pour retransformer en base p les coefficients du polynôme somme.

public void afficheTableMultPolynomes(Polynome[] tousPolys)
Affiche la table de la multiplication des polynômes du corps. La multiplication est effectuée par mult de la classe Polynome, qui travaille dans Z; le resultat, qui est donc plus géneralément un polynôme dans Z, est en suite transformé dans Fq par adjustePuissancesPolynome.

public Polynome[] recherchePrimitifs(Polynome[] tousPolys)
Retourne un array de polynômes contenant tous les primitifs du corps. Un polynôme P est primitif pour Fq si P^k0, P^k1, ..., P^kn sont tous differents de 1, où les ki sont les diviseurs (1 inclus, q-1 exclus) de q-1.
Les P sont cherchés parmi les éléments de tousPolys, l'array de tous les polynômes du corps retourné par tousLesPolynomes().

private Polynome[] tableLogs()
Engendre la table des logarithmes du corps, c'est à dire toutes les puissances (de 0 à q-1) d'un élément primitif. Le primitif qu'on utilise est le premier polynôme trouvé par recherchePrimitifs. La méthode utilise adjustePuissancesPolynomepour réduire dans Fq la puissance trouvée.

public int reverseTableLogs(Polynome polynome)
Recherche dans la table des logarithmes, qui contient toutes les puissances du polynôme primitif générateur alfa, l'élément alfa^i = polynome, et retourne la valeur de i. Si une telle puissance n'existe pas (ce qui est le cas si polynome est nul), la méthode retourne -1.
Cette méthode est beaucoup utilisé dansdecodedetcalculeSyndromesde class CodeBCH, qui l'utilisent pour retrouver les puissances du primitif qui composent le syndrome, et pour convertir les syndromes en puissances du primitif pour l'affichage du polynôme correcteur.

public Polynome enversPolynome(Polynome poly)
Trouve l'envers du polynôme poly.
La méthode utilise adjustePuissancesPolynome pour réduire dans Fq le polynôme trouvé.

public Polynome polynomeMinimal(Vector classeCyc)
Calcule le polynôme minimal d'un élément primitif, à partir de sa classe cyclotomique classeCyc.

Les codes BCH

Les codes BCH (Bose - Chaudluri - Hocquenghem) sont des codes cycliques construits en fonction de la capacité de correction désirée.

Construction d'un BCH d-correcteur de longueur n sur Fp

Pour la construction d'un BCH d-correcteur de longueur n sur Fp (avec n et p premiers entre eux), on procéde comme décrit.
Soit m l'ordre de q modulo n, c'est à dire m est le plus petit entier tel que p^m = 1 mod n.
On se place alors dans le corps fini Fq (q = p^m), id est Fq = Fp [x] / P(x) irréductible de Fp [x] de degré m. On trouve un élément primitif alfa du corps et on en considére les puissances alfa^1, alfa^2, ..., alfa^2d.
Pour chacune de ces puissances alfa^i, on en détermine la classe cyclotomique: {alfa^i, alfa^(i * 2), alfa^(i * 4), ..., alfa^(i * 2^j)}, et le polynôme minimal associé (x - alfa^i) * (x - alfa^(i * 2)) * (x - alfa^(i * 4)) * ... * (x - alfa^(i * 2^j)).
Le polynôme générateur g(x) du code BCH est le produit de tous les polynômes minimaux associés aux classes cyclotomiques.
La dimension du code construit est alors n moins le degré de g(x).
On dénote un code ainsi contruit avec la notation BCH (n, dimension du code, d).

Dans la suite, on simplifiera le problème en considerant que le code soit engendré sur F2. Les messages seront donc composés de bits = {0, 1}.

Codage d'un message (sur F2)

Le codage c(x) d'un message m(x) est tout simplement le reste de sa division pour g(x), ou m(x) mod g(x), ajouté au message originaire (opportunément décalé).

Décodage d'un message (sur F2)

Soit r(x) le message reçu; on sait qu'il peut être affecté par d erreurs. Pour en corriger les erreurs, on en calcule les 2d syndromes s: s1 = r(alfa), s2 = r(alfa^2), s3 = r(alfa^3), ...
Si le message reçu est correct, tous les syndromes sont nuls.
Si les syndromes ne sont pas nuls, on cherche le polynome correcteur sigma(x) = x^d + sigma1 * x^(d-1) + sigma2 * x^(d-2) + sigma3 * x^(d-3) + ..., où les valeurs de sigma sont trouvés selon les formules suivantes:

pour un BCH 1-correcteur: sigma1 = s1
pour un BCH 2-correcteur: sigma1 = s1, sigma2 = (s3 + (s1)^3) * s1^-1
pour un BCH 3-correcteur: sigma1 = s1, sigma2 = (s5 + (s1)^2 * s3) * (s1^3 + s3)^-1, sigma3 = s1^3 + s3 + s1 * sigma2

On calcule ensuite la valeur du polynôme correcteur dans alfa^0, alfa^1, alfa^2, ..., alfa^n (je rappelle que n est la longueur du code BCH). Cette valeur sigma(alfa^k) est nulle s'il y a un erreur dans le bit en position k, qui peut être alors corrigé (en 0 s'il est 1 et viceversa).
Remarque: Un code d-correcteur assure la détection et la correction d'un maximum de d erreurs, donc un message contenant plus de d erreur sera faussement identifié comme correct.

Implementation

Pour la construction d'un code BCH, j'ai écrit une classe class CodeBCH avec un constructeur public CodeBCH(int n, int d, Polynome irreductible). Ce dernier trouve la valeur de m et pense à créer un corps fini Fq (q = 2^m), avec le polynome irreductible comme générateur (il s'agit du générateur du corps, pas du générateur du BCH) pour les opérations nécessaires.

Le codage est effectué grace à public Polynome code(Polynome message) qui multiplie le message reçu, par x elévé au degré du polynôme générateur g(x) (le décalage dont j'ai parlé auparavant), et lui ajoute le reste de la division du message même par g(x).

Pour le décodage, la méthode public Polynome decode(Polynome messageCode) est appelée. Elle calcule les syndromes du message et ensuite appelle public int[] decode1(Polynome[] syndromes), public int[] decode2(Polynome[] syndromes) ou public int[] decode3(Polynome[] syndromes) selon la valeur de d corréspondante. Ces méthodes retournent la position de(s) l'erreur(s) trouvé(s). Pour corriger un erreur en position i dans r(x), on ajoute alors à r(x) la valeur x^i, en faisant donc changer son coefficient de 0 à 1 ou viceversa et en corrigeant l'erreur.

Chacun des trois méthodes decoded calcule les valeurs de tous les sigma et fait appel àcorps.reverseTableLogspour trouver dans la table des logarithmes la puissance du primitif alfa corréspondante. Le polynôme correcteur est finalement crée et calculé pour tous les valeurs nécessaires. A fur et à mesure que ce calcul procéde, les valeurs de l'indice i qui donnent un résultat nul (ce qui signifie un erreur en position i), sont stockés dans un array d'entiers erreurs , qui est à la fin retourné par la méthode.

Les syndromes nécessaires au décodage sont calculés, pour chaque messageCode, parprivate Polynome[] calculeSyndromes(Polynome messageCode). Pour clarté, je calcule toutes les syndromes même s'il n'a besoin que de celles d'ordre impair (car on travaille dans F2 et donc g(alfa^2) = g(alfa)^2 ).

Détails d'implementation

Opérations sur les polynômes

La classe Polynome défine un objet polynôme. Un array d'entiers coeff contient ses coefficients: la valeur dans chaque indice est le coéfficient de la correspondante puissance de x.
La constanteMAX_DEGREdéfine le nombre maximum d'elements dans cet array (qui pourra donc contenir un polynôme de degréMAX_DEGRE-1).
J'ai implementé cinq constructeurs: un des constructeurs prend en paramètre un array contenant un nombre quelconque d'elements, et qui sera consideré comme la liste des coefficients en ordre décroissante des puissances de x; donc en ordre inversé par rapport à l'ordonnancement des coefficients dans coeff. Un autre constructeur prends en paramêtre la chaîne de caractéres tapé par l'utilisateur au cours du programme (voire section "Utilisation du programme"). Les autres sont un constructeur qui crée un P(x) = constante, un constructeur sans paramètres qui construit le polynôme nul et un constructeur qui clone un polynôme.

Les méthodes de cette classe implémentent toutes les opérations principales sur les polynômes, dans Z. J'ai suivi le style de programmation de créer plusieurs méthodes élementaires (parfois triviales), en partageant les tâches en plusieurs sous-tâches; ceci afin d'obtenir un code soit plus simple à écrire, soit plus simple à examiner dans un deuxiéme temps.
Les méthodes suivantes sont déclarés:

public int degre()
Cette méthode trouve le degré d'un polynôme, c'est à dire la puissance la plus grande de x qui possède un coefficient non nul.

public Polynome addKXn(int k, int n)
Additionne la valeur k*x^n à un polynôme.

public Polynome add(Polynome poly)
Additionne deux polynômes.

public Polynome multKXn(int k, int n)
Multiplie un polynôme par k*x^n.

public Polynome mult(Polynome poly)
Multiplie deux polynômes.

public Polynome pow(int g)
Eleve un polynôme à la puissance g, au moyen de multiplication succéssives par soi-même.

public boolean equals0()
Retourne true si le polynôme sur lequel on a appelé la méthode est le polynôme nul.

public boolean equals1()
Retourne true si le polynôme sur lequel on a appelé la méthode est P(x) = 1.

public boolean equals(Polynome poly)
Vérifie si deux polynômes sont égaux, en vérifiant l'egalité de leurs coefficients.

public String toString()
Rédefinition de la méthode toString qui donne un affichage du type, pour exemple, 4X^7 6X^4 X^3 2X^2 1.

public String affiche(int degreMax)
Retourne une chaîne contenante la suite des coefficients du polynôme, sans espaces vides entre eux, selon l'ordre decroissante des puissances à partir du degré degreMax. (La chaîne contiendra donc degreMax+1 coefficients.) L'appel de cette méthode sur le polynôme précédente donnerait donc 40061201.
Ce format rends plus lisible certains affichages (comme les tables de l'addition/multiplication), mais présénte des inconvenients (notamment pour valeurs de p >= 11, car à ce moment les coefficients ne sont plus constitués d'une seule chiffre).

Gestion des erreurs

La class CorpsException défine l'exception qui est lancée en cas d'erreur.

Application principale

La classe Main contient la méthode principalepublic static void main(String args[]) , ainsi que d'autres méthodes statiques qui ont un rôle géneral:
public static int max(int arg1, int arg2) retourne le plus grand parmi arg1 et arg2.
public static boolean estPremier(int nombre) implémente un simple algorithme dû à Eratostene et retourne true si nombre est premier.
public static void out(String str),public static void outc(String str)etpublic static void outl(String str)sont de raccourcis pour System.out.println en formes variées, mais n'affichent le message str que si la variable drapeau verbose est true.

Bogues

Le code BCH 3-correcteur généré par le programme ne donne pas de résultats corrects sur de messages affecté par deux erreurs ou plus. Ceci est peut-être dû à une mauvaise définition des valeurs sigma.

Utilisation du programme

Pour démarrer le programme utiliser la commande java Main , avec des arguments obligatoires selon l'option choisie:

java Main corps <p> <m> <polynôme irréductible>
Construit un corps fini Fq = F<p>^<m> avec <polynôme irréductible> comme générateur.
java Main bch <n> <d> <polynôme irréductible>
Construit un code BCH de longueur <n> sur F2, <d>-correcteur, basé sur un corps fini généré par <polynôme irréductible>.
java Main berlekamp <p> <polynôme á factoriser>
(Permet de tester un morceau de code qui implemente l'algorithme de Berlekamp, pour un <polynôme á factoriser> sur F<p>. Non terminé.)
En outre, si on ajoute un argument supplementaire quelconque, le programme sera utilisé en "mode verbeux" (verbose), c'est à dire avec des affichages trés détaillés sur les calculs pendant les différentes étapes.

Dans le programme, on entrera un polynômes de degré m comme une chaîne de m+1 caractéres, corréspondants à ses coefficients par ordre décroîssant des puissances de x.
Ainsi pour indiquer le polynôme x^6 + 2x^3 + x^2 + 6x + 1 on tapera la chaîne de caractéres 1002161. Pourrait s'avérer nécessaire d'entrer des 0 supplémentaires en tête, pour atteindre à une longueur fixée (notamment dans le code BCH pendant le codage/decodage d'un message). En outre, si les coéfficients des polynômes ne sont pas dans Fp, ils seront convertis.

Si on a choisi de construire un corps fini, le programme affichera:

les tables de l'addition et de la multiplications des éléments de Fp
la liste de tous les polynômes de Fq, dans les deux formats
les tables de l'addition et de la multiplications des polynômes du corps
la liste des éléments primitifs
la table des logarithmes, engendrée à partir du premier élément primitif trouvé

L'affichage de ce texte se fait sur plusieurs écrans: pour pouvoir le lire aisément, je suggère d'utiliser la fonction de lecture dans le buffer des fênetres term Linux (Shift + PgUp/PgDown/CrsrUp/CrsrDown).
Enfin, le programme montrera un invite qui permet d'inverser un polynôme (de degré m-1) tapé au clavier. Taper quit ouqpour sortir.

Si on a choisi l'option BCH, le programme affiche des informations rélatives au BCH et un invite qui permet de saisir un message binaire à coder / décoder.
Pour coder un message (de longueur égale à la dimension du code), taper code ou c suivi du message.
Pour décoder un message (de longueur égale à n) et en corriger les erreurs eventuels, taper decode ou d suivi du message.
Taper quit ou q pour sortir.

Jeu d'exécution

Ci-dessus je montre un jeu d'exécution du programme. Les commandes tapés par l'utilisateur sont en gras et en couleur bleu.

$ java Main

================= Codes BCH =================
Daniele Raffo <draffo@etudiant.univ-mlv.fr>
      projet de Codage et Cryptographie
        Université de Marne la Vallée
                 11 FEV 2001
=============================================

Utilisation:
java Main corps <p> <m> <polynôme irréductible> [verbose]
      crée le corps fini Fq (q=p^m), ayant comme générateur
      le polynôme irreductible
java Main bch <n> <d> <polynôme irréductible> [verbose]
      costruit un code BCH de longueur n sur F2, d-correcteur,
      en utilisant un corps fini généré par le polynôme irreductible

Exemples:
java Main corps 2 4 10011    engendre F16 (2^4) par X^4 + X + 1
java Main bch 15 2 10011     construit un code BCH (15, x, 2)
                             sur un corps fini généré par X^4 + X + 1

$ java Main corps 2 4 11111

Génération du corps fini F16 (2^4), polynôme irreductible générateur P(X) = X^4 X^3 X^2 X 1

Table de l'addition sur F2
0 1
1 0

Table de la multiplication sur F2
0 0
0 1

Ensemble de tous les polynômes du corps
0000   0
0001   1
0010   X
0011   X 1
0100   X^2
0101   X^2 1
0110   X^2 X
0111   X^2 X 1
1000   X^3
1001   X^3 1
1010   X^3 X
1011   X^3 X 1
1100   X^3 X^2
1101   X^3 X^2 1
1110   X^3 X^2 X
1111   X^3 X^2 X 1

Table de l'addition des polynômes
0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
0001 0000 0011 0010 0101 0100 0111 0110 1001 1000 1011 1010 1101 1100 1111 1110
0010 0011 0000 0001 0110 0111 0100 0101 1010 1011 1000 1001 1110 1111 1100 1101
0011 0010 0001 0000 0111 0110 0101 0100 1011 1010 1001 1000 1111 1110 1101 1100
0100 0101 0110 0111 0000 0001 0010 0011 1100 1101 1110 1111 1000 1001 1010 1011
0101 0100 0111 0110 0001 0000 0011 0010 1101 1100 1111 1110 1001 1000 1011 1010
0110 0111 0100 0101 0010 0011 0000 0001 1110 1111 1100 1101 1010 1011 1000 1001
0111 0110 0101 0100 0011 0010 0001 0000 1111 1110 1101 1100 1011 1010 1001 1000
1000 1001 1010 1011 1100 1101 1110 1111 0000 0001 0010 0011 0100 0101 0110 0111
1001 1000 1011 1010 1101 1100 1111 1110 0001 0000 0011 0010 0101 0100 0111 0110
1010 1011 1000 1001 1110 1111 1100 1101 0010 0011 0000 0001 0110 0111 0100 0101
1011 1010 1001 1000 1111 1110 1101 1100 0011 0010 0001 0000 0111 0110 0101 0100
1100 1101 1110 1111 1000 1001 1010 1011 0100 0101 0110 0111 0000 0001 0010 0011
1101 1100 1111 1110 1001 1000 1011 1010 0101 0100 0111 0110 0001 0000 0011 0010
1110 1111 1100 1101 1010 1011 1000 1001 0110 0111 0100 0101 0010 0011 0000 0001
1111 1110 1101 1100 1011 1010 1001 1000 0111 0110 0101 0100 0011 0010 0001 0000

Table de la multiplication des polynômes
0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000
0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
0000 0010 0100 0110 1000 1010 1100 1110 1111 1101 1011 1001 0111 0101 0011 0001
0000 0011 0110 0101 1100 1111 1010 1001 0111 0100 0001 0010 1011 1000 1101 1110
0000 0100 1000 1100 1111 1011 0111 0011 0001 0101 1001 1101 1110 1010 0110 0010
0000 0101 1010 1111 1011 1110 0001 0100 1001 1100 0011 0110 0010 0111 1000 1101
0000 0110 1100 1010 0111 0001 1011 1101 1110 1000 0010 0100 1001 1111 0101 0011
0000 0111 1110 1001 0011 0100 1101 1010 0110 0001 1000 1111 0101 0010 1011 1100
0000 1000 1111 0111 0001 1001 1110 0110 0010 1010 1101 0101 0011 1011 1100 0100
0000 1001 1101 0100 0101 1100 1000 0001 1010 0011 0111 1110 1111 0110 0010 1011
0000 1010 1011 0001 1001 0011 0010 1000 1101 0111 0110 1100 0100 1110 1111 0101
0000 1011 1001 0010 1101 0110 0100 1111 0101 1110 1100 0111 1000 0011 0001 1010
0000 1100 0111 1011 1110 0010 1001 0101 0011 1111 0100 1000 1101 0001 1010 0110
0000 1101 0101 1000 1010 0111 1111 0010 1011 0110 1110 0011 0001 1100 0100 1001
0000 1110 0011 1101 0110 1000 0101 1011 1100 0010 1111 0001 1010 0100 1001 0111
0000 1111 0001 1110 0010 1101 0011 1100 0100 1011 0101 1010 0110 1001 0111 1000

Elements primitifs
X 1
X^2 1
X^2 X
X^2 X 1
X^3 1
X^3 X
X^3 X 1
X^3 X^2 X

Table des logarithmes
(X 1 )^0 = 1
(X 1 )^1 = X 1
(X 1 )^2 = X^2 1
(X 1 )^3 = X^3 X^2 X 1
(X 1 )^4 = X^3 X^2 X
(X 1 )^5 = X^3 X^2 1
(X 1 )^6 = X^3
(X 1 )^7 = X^2 X 1
(X 1 )^8 = X^3 1
(X 1 )^9 = X^2
(X 1 )^10 = X^3 X^2
(X 1 )^11 = X^3 X 1
(X 1 )^12 = X
(X 1 )^13 = X^2 X
(X 1 )^14 = X^3 X
(X 1 )^15 = 1

F16 (2^4) Polynôme à inverser > 0100
Invers de X^2 =
X^3

F16 (2^4) Polynôme à inverser > q
$ java Main bch 15 2 10011 verbose

Classe cyclotomique: [1, 2, 4, 8]
Polynôme minimal associé: X^4 X 1
Classe cyclotomique: [3, 6, 12, 9]
Polynôme minimal associé: X^4 X^3 X^2 X 1

Génération du code BCH (longueur 15, dimension 7, 2-correcteur) sur F2,
polynôme générateur G(X) = X^8 X^7 X^6 X^4 1
On utilise le corps F16 (2^4), polynôme irreductible générateur P(X) = X^4 X 1

BCH (15, 7, 2) Commande > code 0111001
Message : 0111001 X^5 X^4 X^3 1
Message codé: 011100110000010 X^13 X^12 X^11 X^8 X^7 X

BCH (15, 7, 2) Commande > decode 0111001
Erreur: Ce message est de dimension 7, on attend un message à decoder de dimension 15

BCH (15, 7, 2) Commande > decode 011100110000010

Calcul des 4 syndromes de X^13 X^12 X^11 X^8 X^7 X
syndrome #1: + alfa^13 + alfa^12 + alfa^11 + alfa^8 + alfa^7 + alfa^1 = 0000
syndrome #2: + alfa^26 + alfa^24 + alfa^22 + alfa^16 + alfa^14 + alfa^2 = 0000
syndrome #3: + alfa^39 + alfa^36 + alfa^33 + alfa^24 + alfa^21 + alfa^3 = 0000
syndrome #4: + alfa^52 + alfa^48 + alfa^44 + alfa^32 + alfa^28 + alfa^4 = 0000

Polynôme correcteur: X^2

Recherche exaustive des solutions:
sigma(alfa^0) = 0001
sigma(alfa^1) = 0100
sigma(alfa^2) = 0011
sigma(alfa^3) = 1100
sigma(alfa^4) = 0101
sigma(alfa^5) = 0111
sigma(alfa^6) = 1111
sigma(alfa^7) = 1001
sigma(alfa^8) = 0010
sigma(alfa^9) = 1000
sigma(alfa^10) = 0110
sigma(alfa^11) = 1011
sigma(alfa^12) = 1010
sigma(alfa^13) = 1110
sigma(alfa^14) = 1101
sigma(alfa^15) = 0001

Message       : 011100110000010    X^13 X^12 X^11 X^8 X^7 X
                                   0 erreur(s) trouvé(s)
Correction    : 011100110000010    X^13 X^12 X^11 X^8 X^7 X
Message decodé: 0111001            X^5 X^4 X^3 1

BCH (15, 7, 2) Commande > d 011100110010010

Calcul des 4 syndromes de X^13 X^12 X^11 X^8 X^7 X^4 X
syndrome #1: + alfa^13 + alfa^12 + alfa^11 + alfa^8 + alfa^7 + alfa^4 + alfa^1 = 0011 = alfa^4
syndrome #2: + alfa^26 + alfa^24 + alfa^22 + alfa^16 + alfa^14 + alfa^8 + alfa^2 = 0101 = alfa^8
syndrome #3: + alfa^39 + alfa^36 + alfa^33 + alfa^24 + alfa^21 + alfa^12 + alfa^3 = 1111 = alfa^12
syndrome #4: + alfa^52 + alfa^48 + alfa^44 + alfa^32 + alfa^28 + alfa^16 + alfa^4 = 0010 = alfa^1

Polynôme correcteur: X^2 + (alfa^4)X

Recherche exaustive des solutions:
sigma(alfa^0) = 0010
sigma(alfa^1) = 0010
sigma(alfa^2) = 1111
sigma(alfa^3) = 0111
sigma(alfa^4) = 0000 erreur en position 4
sigma(alfa^5) = 1101
sigma(alfa^6) = 1000
sigma(alfa^7) = 0111
sigma(alfa^8) = 1101
sigma(alfa^9) = 0101
sigma(alfa^10) = 1111
sigma(alfa^11) = 1010
sigma(alfa^12) = 1000
sigma(alfa^13) = 1010
sigma(alfa^14) = 0101
sigma(alfa^15) = 0010

Message       : 011100110010010    X^13 X^12 X^11 X^8 X^7 X^4 X
                          ^        1 erreur(s) trouvé(s)
Correction    : 011100110000010    X^13 X^12 X^11 X^8 X^7 X
Message decodé: 0111001            X^5 X^4 X^3 1

BCH (15, 7, 2) Commande > d 001100110000011

Calcul des 4 syndromes de X^12 X^11 X^8 X^7 X 1
syndrome #1: + alfa^12 + alfa^11 + alfa^8 + alfa^7 + alfa^1 + alfa^0 = 1100 = alfa^6
syndrome #2: + alfa^24 + alfa^22 + alfa^16 + alfa^14 + alfa^2 + alfa^0 = 1111 = alfa^12
syndrome #3: + alfa^36 + alfa^33 + alfa^24 + alfa^21 + alfa^3 + alfa^0 = 1011 = alfa^7
syndrome #4: + alfa^48 + alfa^44 + alfa^32 + alfa^28 + alfa^4 + alfa^0 = 1010 = alfa^9

Polynôme correcteur: X^2 + (alfa^6)X + alfa^13

Recherche exaustive des solutions:
sigma(alfa^0) = 0000 erreur en position 0
sigma(alfa^1) = 0010
sigma(alfa^2) = 1011
sigma(alfa^3) = 1011
sigma(alfa^4) = 1111
sigma(alfa^5) = 0100
sigma(alfa^6) = 1101
sigma(alfa^7) = 1001
sigma(alfa^8) = 0110
sigma(alfa^9) = 0100
sigma(alfa^10) = 1001
sigma(alfa^11) = 0010
sigma(alfa^12) = 1111
sigma(alfa^13) = 0000 erreur en position 13

Message       : 001100110000011    X^12 X^11 X^8 X^7 X 1
                 ^            ^    2 erreur(s) trouvé(s)
Correction    : 011100110000010    X^13 X^12 X^11 X^8 X^7 X
Message decodé: 0111001            X^5 X^4 X^3 1

BCH (15, 7, 2) Commande > d 010100010000010

Calcul des 4 syndromes de X^13 X^11 X^7 X
syndrome #1: + alfa^13 + alfa^11 + alfa^7 + alfa^1 = 1010 = alfa^9
syndrome #2: + alfa^26 + alfa^22 + alfa^14 + alfa^2 = 1000 = alfa^3
syndrome #3: + alfa^39 + alfa^33 + alfa^21 + alfa^3 = 0110 = alfa^5
syndrome #4: + alfa^52 + alfa^44 + alfa^28 + alfa^4 = 1100 = alfa^6

Polynôme correcteur: X^2 + (alfa^9)X + alfa^5

Recherche exaustive des solutions:
sigma(alfa^0) = 1101
sigma(alfa^1) = 0101
sigma(alfa^2) = 1011
sigma(alfa^3) = 0101
sigma(alfa^4) = 1110
sigma(alfa^5) = 1000
sigma(alfa^6) = 1000
sigma(alfa^7) = 1101
sigma(alfa^8) = 0000   erreur en position 8
sigma(alfa^9) = 0110
sigma(alfa^10) = 0011
sigma(alfa^11) = 1011
sigma(alfa^12) = 0000   erreur en position 12

Message       : 010100010000010    X^13 X^11 X^7 X
                  ^   ^            2 erreur(s) trouvé(s)
Correction    : 011100110000010    X^13 X^12 X^11 X^8 X^7 X
Message decodé: 0111001            X^5 X^4 X^3 1

BCH (15, 7, 2) Commande > d 011100110000111

Calcul des 4 syndromes de X^13 X^12 X^11 X^8 X^7 X^2 X 1
syndrome #1: + alfa^13 + alfa^12 + alfa^11 + alfa^8 + alfa^7 + alfa^2 + alfa^1 + alfa^0 = 0101 = alfa^8
syndrome #2: + alfa^26 + alfa^24 + alfa^22 + alfa^16 + alfa^14 + alfa^4 + alfa^2 + alfa^0 = 0010 = alfa^1
syndrome #3: + alfa^39 + alfa^36 + alfa^33 + alfa^24 + alfa^21 + alfa^6 + alfa^3 + alfa^0 = 1101 = alfa^13
syndrome #4: + alfa^52 + alfa^48 + alfa^44 + alfa^32 + alfa^28 + alfa^8 + alfa^4 + alfa^0 = 0100 = alfa^2

Polynôme correcteur: X^2 + (alfa^8)X + alfa^2

Recherche exaustive des solutions:
sigma(alfa^0) = 0000   erreur en position 0
sigma(alfa^1) = 1010
sigma(alfa^2) = 0000   erreur en position 2

Message       : 011100110000111    X^13 X^12 X^11 X^8 X^7 X^2 X 1
                            ^ ^    2 erreur(s) trouvé(s)
Correction    : 011100110000010    X^13 X^12 X^11 X^8 X^7 X
Message decodé: 0111001            X^5 X^4 X^3 1

BCH (15, 7, 2) Commande > q
$