Codes linéaires, codes cycliques sur corps finis

Primitivité d’un polynôme irréductible sur un corps fini

Définition 1.2.1 Soit T un polynôme irréductible de degré r > 1 sur F2: La primitivité de T est le plus petit entier positif t tel que T divise xt 1: Certains auteurs appellent la primitivité de T l’exposant ou l’ordre. La primitivité de T(x) peut être dé…nie comme étant l’ordre de x dans le  groupe multiplicatif F2[x]=(T(x)):
Exemple 1.2.2 Considérons le polynôme T = x4 + x3 + x2 + x + 1 irréductible sur F2 et faisons les divisions successives de x t 1 par T pour t = 2; 3; 4; 5; :::; sur F2

Condition nécessaire de divisibilité des trinômes par un polynôme irréductible

-Etude des familles F(a; b) telles que xa + xb + 1 soit irréductible sur F2
Soit (a; b) 2 N2; nous considérons la famille de polynômes F(a; b) = {xam + xbs + 1,0 < bs < am} avec a; b des entiers positifs et m; s des entiers tels que le trinôme xa+xb+1 soit irréductible sur le corps …ni F2. Soit M(a; b) le nombre de trinômes T irréductibles de la famille F(a; b) de degré 6 M.
-Condition nécessaire de divisibilité des trinômes par un polynôme irréductible
Concepts généraux Le théorème suivant dû à Swan est un important résultat sur la non-existence, dans certains cas, de trinômes irréductibles sur F2
Théorème de Swan [65] Soit n > m > 0 et supposons que soit n est impair, soit m est impair. Alors le trinôme xn + xm + 1 admet un nombre pair de facteurs irréductibles sur F2 si et seulement si, nous sommes dans l’une des situations suivantes :
(i) n est pair, m est impair, n 6= 2m, et nm=2 0; 1(mod 4)
(ii) n est impair, m est pair, m – 2n, et n 3(mod 4)
(iii) n est impair, m est pair, m j 2n, et n 1(mod 8)
Maintenant nous allons faire une recherche expérimentale des trinômes irréductibles sur F2 de la forme xam + xbs + 1 pour tous les couples d’entiers (a; b) tels que a 10 et b 10:
Résultats obtenus Notre étude est axée sur la recherche de familles de trinômes sur le corps …ni F2 qui produisent une grande proportion de polynômes irréductibles. Une recherche expérimentale a été faite, en particulier sur les trinômes du type x5m + x3s + 1, x7m + x3s + 1 ou x7m + x5s + 1, ce qui a permis d’explorer plusieurs pistes. Le calcul systématique de la densité, c’est-à-dire le rapport du nombre de trinômes irréductibles au nombre de trinômes quelconques (i.e., a = b = 1) de la forme xam + xbs + 1; 0 < bs < am M pour a; b entiers positifs, et M une borne …xée, M = 100; 300; 500 a été fait (voir tableau en annexe 1), ce qui a donné les résultats suivants où nb représente le nombre de trinômes irréductibles et total indique le nombre de trinômes quelconques de la famille F(a; b).

Généralisations apportées à notre résultat sur la divisibilité des trinômes

   En voici le texte intégral des ra¢nements apportées à notre résultat sur la divisibilité des trinômes xam + xbs + 1 sur F2 et la présentation de l’extension du critère de Welch pour ce type de trinômes : Nous allons faire l’extension du critère de Welch [28] pour tester si un polynôme irréductible sur F2 divise les trinômes xam + xbs + 1. Nous donnons un ra¢nement de la condition nécessaire de divisibilité des trinômes xam+xbs+1 par un polynôme irréductible quelconque présentée dans [49].
Divisibilité des trinômes xam + xbs + 1 Dans cette section nous considérons les conditions de divisibilité des trinômes xam+xbs+1 par un polynôme irréductible. Soit f un polynôme irréductible de degré n sur F2 et a; b des entiers positifs. Dans [49] il a été prouvé que s’ils existent des entiers positifs m et s tel que f divise xam + xbs + 1, alors a et b ne sont pas divisible par 2n 1. Dans ce qui suit nous donnons un ra¢nement de ce résultat.
Théorème [5, 39] Soit f un polynôme irréductible d’ordre e > 1 sur F2 et a, b des entiers positifs. S’ils existent des entiers positifs m et s tel que f divise le trinôme xam + xbs + 1 (am > bs), alors am, bs et am bs ne sont pas divisibles par e .

Codes cycliques optimaux sur F3 [52]

   Nous adaptons les notations et définitions indiquées dans [42; 46]. Les éléments de C sont appelés des mots de code et le poids wt(x) d’un mot de code x est le nombre de positions non nuls dans x. La distance d(x; y) de Hamming entre deux mots de codes est définie par : d(x; y) = wt(x y). La distance minimale d’un code linéaire C est : d(C) = minfd(x; y) =x; y 2 C; x 6= yg: Un code linéaire C[n; k; d] , sur un corps …ni F , est un code C[n; k] de distance minimale d. Pour un code linéaire, la distance minimale est égale au plus petit des poids de tous ses mots de codes non nuls. Le problème central dans la théorie des codes est d’optimiser un des paramètres n; k et d pour des valeurs données des deux autres, q étant …xé. Une des deux versions est : Trouver dq(n; k), la plus grande valeur de d pour laquelle un code C[n; k; d]q existe. Un code qui atteint cette valeur est appelé un code optimal. La recherche des codes ternaires optimaux a été initiée par Hill et Newton [37]. Ils ont trouvé les valeurs de n3(k; d) pour k 4 pour tout d, et les valeurs de n3(5; d) pour 30 valeurs de d. L’état de l’art et tables pour n3(6; d) et d3(n; 6) est dans [34]. Maruta [48] a prouvé l’inexistence de certains codes de dimension 6 sur F3 et a présenté une nouvelle table pour n3(6; d) à l’adresse suivante : http://www.geocities.com/mars39. geo/griesmer.html. Grassl [26] maintient à jour une table des bornes supérieures et inférieures de d3(n; k) pour n 243. Des bornes pour des valeurs numériques de d3(n; 7) ont été améliorées ou établies à travers la construction des codes quasi cycliques(multicycliques) par Gulliver et Ostergard.

Table des matières

Introduction générale
Chapitre 1 Divisibilité des trinômes xam+xbs+1 par un polynôme irréductible sur F2
1.1 Introduction
1.2 Théorèmes de base sur la divisibilité des trinômes xm + xs + 1 par un polynôme irréductible sur F2
1.3 Polynômes cyclotomiques et divisibilité des trinômes x m + x s + 1 sur F2
1.4 Polynômes réciproques et divisibilité des trinômes x m + x s + 1 sur F2
1.5 Condition nécessaire de divisibilité des trinômes x am + x bs +1 par un polynôme irréductible sur F2
1.6 Conjecture
1.7 Généralisations apportées à notre résultat sur les trinômes xam+x bs+1
Chapitre 2 Codes linéaires, codes cycliques sur corps finis
2.1 Introduction
2.2 Paramètres d’un code
2.3 Codes linéaires sur Fq
2.4 Codes cycliques sur Fq
2.5 Exemples historiques de codes correcteurs
Chapitre 3 Codes cycliques optimaux, iso-duaux sur F3
3.1 Introduction
3.2 Codes cycliques iso-duaux sur F3
3.3 Codes cycliques optimaux sur F3
3.4 Table des valeurs de dI (n) et dC(n)
Chapitre 4 Codes cycliques optimaux, iso-duaux sur F5
4.1 Introduction
4.2 Codes cycliques iso-duaux sur F5
4.3 Codes cycliques optimaux sur F5
4.4 Table des valeurs de dI (n) et dC(n)
Annexe 1 Calcul de la densité des trinômes xam+xbs+1 sur F2
Annexe 2 Programme de recherche de la distance minimum
Conclusion
Bibliographie

Télécharger le rapport complet