Codes BCH, exemples

Soient \(q\) et \(n\) fixés (premiers entre eux), on cherche de bons codes BCH de longueur \(n\) sur \(\F_q\).

Calcul d’orbites

On examine les \(q\)-orbites modulo \(n\), donc les ensembles de la forme \(\set{a q^k \bmod n}\).

[q, n] = [2, 7]

On calcule la suite des puissances de \(q\) avec powers

powers(q,n)
[1, 2, 4, 8, 16, 32, 64, 128]

en réduisant modulo \(n\) la suite est périodique

powers(q,n) % n
[1, 2, 4, 1, 2, 4, 1, 2]

on récupère l’orbite en prenant les éléments sans répétition

Set( powers(q,n) % n )

Pour avoir une autre orbite, on part d’un autre élément

Set( 3 * powers(q,n) % n )

Pour \(q=3\) et \(n=11\), on retrouve les orbites du code de Golay

[q,n] = [3,11]
Set(powers(q,n) % n)
Set(2*powers(q,n) % n)

Bons paramètres BCH

Un code de longueur 17

On cherche des orbites contenant beaucoup d’éléments consécutifs. Prenons \(q=2\) et \(n=17\).

[q,n] = [2,17]
Set(powers(q,n) % n)

L’orbite de 1 n’est pas très intéressante… mais elle contient deux blocs de deux éléments séparés par 0. Si on ajoute l’orbite nulle on obtient la suite consécutive 15,16,0,1,2

Ig = concat(0, Set(powers(q,n) % n))

D’où un \([17,8,d]\) code avec \(d\geq 6\). Calculons son polynôme générateur. On a besoin d’une racine 17ième de l’unité

factormod(x^17-1,2)
alpha = Mod(x,x^8 + x^5 + x^4 + x^3 + Mod(1, 2))
alpha^17

On a alors \(g(x) = \prod_{k\in Ig}(x-\alpha^k)\)

g = liftall(prod(i=1,#Ig, X-alpha^Ig[i]))

Il se trouve qu’on obtient un polynôme de poids 6, de sorte que le code est bien de distance \(d=6\).

Avec des coefficients dans \(\F_4\)

On changeons de corps en posant \(q=4\). Cela casse les orbites en 2

[ Set(a*powers(q,n) % n) | a <- [1,2,3,6] ]

Cette fois on a une autre solution intéressante : combiner les orbites de \(2\) et \(6\) donne la suite de 6 éléments consécutifs 6,7,8,9,10,11.

Le code correspondant a distance au moins 7, il est 3-correcteur !

Ig = Set( concat(2*powers(q,n),6*powers(q,n)) % n)

On détermine un polynôme générateur de ce code en introduisant une racine \(\alpha\) définie sur \(\F_4\).

y = ffgen(4,y)
factormod(x^17-1,y)

Prenons une racine \(17\)-ième

alpha = Mod(x, x^4 + x^3 + y*x^2 + x + 1)
alpha^17

et le polynôme générateur qu’elle induit

g = lift(prod(i=1,#Ig,X-alpha^Ig[i]))

Cette fois on obtient un polynôme générateur de poids \(9\), cela ne permet pas de déterminer la distance du code.

Cependant, si l’on prend une racine \(\beta\) pour établir la correspondance entre générateur et racines

beta=Mod(x,x^4 + y*x^3 + x^2 + y*x + 1)
beta^17

On obtient un autre polynôme générateur, qui est lui de poids \(7\), de sorte que le code correspondant est de distance \(7\) exactement.

g2 = lift(prod(i=1,#Ig,X-beta^Ig[i]))

Le premier code est-il aussi de distance \(7\) ?

Ce n’est pas évident a priori. Mais il se trouve que ces deux codes sont équivalents par la permutation \(x\maspto x^u\) de \(\Fq[x]/(x^n-1)\), où \(u\) est l’exposant tel que \(\alpha = \beta^u\).

En effet, les mots de \(C\) sont les polynômes qui s’annulent en \(\alpha^2=\beta^{2u}\) et \(\alpha^6=\beta^{6u}\). Ainsi, si \(m(x)\) est un mot de \(C\), \(m(x^u)\) s’annule en \(\beta^2\) et \(\beta^6\), c’est donc un mot de \(C'\).

Ainsi, on a un isomorphisme entre ces codes, qui préserve le poids.

Autres paramètres

La Borne BCH fonctionne avec toute suite arithmétique. En examinant toutes les décompositions en orbites, on repère

  • \(n=10, q=7\)

    [[0], [5], [1, 3, 7, 9], [2, 4, 6, 8]]
    

    la suite 2, 4, 6, 8, donne un \([10, 6, 5]\) code sur \(\F_7\).

  • \(n=18, q=7\)

    [[0], [3], [6], [9], [12], [15], [1, 7, 13], [2, 8, 14], [4, 10, 16], [5, 11, 17]]
    
  • \(n=18, q=5\)

    [[0], [9], [3, 15], [6, 12], [1, 5, 7, 11, 13, 17], [2, 4, 8, 10, 14, 16]]
    
  • \(n=20, q=7\)

    [[0], [10], [5, 15], [1, 3, 7, 9], [2, 6, 14, 18], [4, 8, 12, 16], [11, 13, 17, 19]]
    

    d’où le code [2, 6, 10, 14, 18]

{ for(n=10,20,forprime(p=2,7,q=p;if(n%q,
     while(q<n,print([n,q],
       Set([ Set(a*powers(q,n) % n) | a <- [1..n] ]))
       ;q*=p)
   ))) }