Codes correcteurs

Codes correcteurs [répertoire]

Polynômes à coef. dans F₂ :
degré 1 : x, x+1 (irréductibles puisque du premier degré)
un polynôme de d° ≥ 2 est irréductible s'il n'est divisible ni par x, ni par x+1
s'il ne contient pas de terme constant 1 : il est divisible par x
autrement, il faut faire la division euclidienne par x+1 : P(x) = Q(x) (x+1) + R avec R = 1 ou 0
x² + x + 1 = x (x+1) + 1
x² + 1 = x (x+1) + x + 1 = (x+1) (x+1)
en appliquant la règle : 1+1=0 ; x+x=0 ; x²+x²=0 ; . . . (xⁿ+xⁿ=0)
P(x) est irréductible ⇒ P(0) = 1 et P(1) = 1 (2 conditions nécessaires)
P(0) = 1 ⇒ il possède un terme constant 1
P(1) = 1 ⇒ il possède un nombre impair de termes

	1	x	x²	x³	commentaire
0	0	0	0	0	constante
1	1	0	0	0	constante
x	0	1	0	0	polynôme d°1
x+1	1	1	0	0	polynôme d°1
polynômes de d°2 : 4 cas possibles
x²	0	0	1	0	carré
x²+1	1	0	1	0	(x+1)²
x²+x	0	1	1	0	x(x+1)
x²+x+1	1	1	1	0	irréductible P₂
polynômes de d°3 : 8 cas possibles
x³	0	0	0	1	cube
x³+1	1	0	0	1	(x+1) (x²+x+1)
x³+x	0	1	0	1	x (x+1)²
x³+x+1	1	1	0	1	irréductible P_3.1
x³+x²	0	0	1	1	x² (x+1)
x³+x²+1	1	0	1	1	irréductible P_3.2
x³+x²+x	0	1	1	1	x (x²+x+1)
x³+x²+x+1	1	1	1	1	(x+1)³
polynômes de d°4 : 16 cas possibles

degré 4 : tous les produits de degré 4 entre x, x+1, P₂, P_3.1, P_3.2
puis 3 irréductibles : x⁴+x+1 ; x⁴+x³+1 ; x⁴+x³+x²+x+1

exemple de division euclidienne :

x⁶

x⁵

x⁴

x²

/ (x⁴ + x + 1) = x² + x + 1

x⁶

x³

x²

(produit par x²)

x⁵

x⁴

x³

(résultat de l'addition)

x⁵

x²

(produit par x)

x⁴

x³

x²

(résultat de l'addition)

x⁴

(produit par 1)

x³

x²

(résultat de l'addition)

Reste du quotient : x³ + x² + 1

Petit Théorème de Fermat :
Si : p premier et a ≢ 0 (mod p)
a^p ≡ a (mod p)
a^p−1 ≡ 1 (mod p)
Démonstration :
- Soit p un nombre premier et a un nombre entier, supérieur à 1, et non divisible par p.
- Considérons la suite des multiples de a : a, 2a, 3a, . . . , (p–1)a (1)
- Pour chacun d'eux, p ne divise ni a ni un nombre qui lui est inférieur.
  Conclusion: p ne divise aucun facteur de chacun de ces nombres.
  Les termes de la suite (1), divisés par p, donnent donc des restes non nuls.
- Si deux multiples ka et k'a donnaient le même reste, leur différence ka – k'a = (k – k')a donnerait un reste nul.
  Or, cette différence est un nombre de la suite (1) et, on a montré que les restes de la suite ne sont pas nuls.
  Ces restes sont distincts.
- Finalement, les (p–1) restes des divisions par p, des nombres de la suite (1) sont non nuls et distincts.
  Ces restes constituent donc, à l'ordre près, les nombres de la suite suivante: 1, 2, 3, 4, . . . , p–1 (2)
Anneaux des restes F₂[x]/p(x) où p(x) est un polynôme
restes modulo p(x)
p(x) de degré n ⇒ F₂[x]/p(x) possède 2ⁿ éléments
coef; de 1, x, x², . . . , xⁿ⁻¹
Soit {0, 1} + tous les polynômes de degrés ≤ n−1
http://robert.rolland.acrypta.com/telechargements/algebre/corpsfinis.pdf
1) F8 : extension de F2 : {0, 1, α, α², . . . , α⁶}
C'est le corps des polynômes de degré ≤ 2 quotient de l'anneau des polynômes F2[X]
modulo le polynôme irréductible (premier) : X³ + X + 1 = 0
α = X
α² = X²
α³ (= X³) = 1 + X
α⁴ = X + X²
α⁵ = X² + 1 + X
α⁶ = 1 + X + X + X² = 1 + X²
α⁷ = X + 1 + X = 1

1 X X²

0 0 0 0

1 1 0 0 α⁷ = α⁰

2 0 1 0 α¹

3 1 1 0 α³

4 0 0 1 α²

5 1 0 1 α⁶

6 0 1 1 α⁴

7 1 1 1 α⁵

Cardinal de F8 \ {0} = 7
Polynôme irrédutible : f(x) = x³ + x + 1 (n'a pas de racine dans ℤ/2)
P(0) = P(1) = 1 : pas de racine ⇒ racine α : P(α) = 0
donc α³ = 1 + α
Théorème de l'élément primitif :
Toute extension finie séparable est simple, c'est-à-dire engendrée par un seul élément, appelé élément primitif.
F8 \ {0, 1} est engendré par α, l'élément primitif
2) ordres possibles des éléments de F16 : 2⁴−1 = 15
ordres possibles 3, 5 : qui divisent 15
Théorème de Lagrange — Pour tout groupe fini G et tout sous-groupe H de G,
l'ordre de H (c'est-à-dire son cardinal) divise celui de G
α (0010) ; α² (0100) ; α³ (1000) ; α⁴=α³+1 (1001)
α⁵=α⁴+α (10010=0010+1001)=α³+α+1 (1011)
α⁶=α⁴+α²+α (10110=0110+1001)=α³+α²+α+1 (1111)
α⁷=α⁴+α³+α²+α (11110=1110+1001=0111)=α³+1+α³+α²+α=α²+α+1
α⁸=α³+α²+α (1110)
α⁹=α⁴+α³+α²=α²+1
α¹⁰=α³+α
α¹¹=α⁴+α²=α³+α²+1
α¹²=α⁴+α³+α=α+1
α¹³=α²+α
α¹⁴=α³+α²
α¹⁵=α⁴+α³=1
on part de α=0010
multiplication par α = shift à gauche : 0100
pour 1000 : multiplication par α = 10000 que l'on remplace par 1001
Soit : dès qu'un 1 sort à gauche, on le remplace en additionant 1001
α est d'ordre 15 ; α² est d'ordre 15 (car premier avec 15) . . .
α³ est d'ordre 5 (car 3 divise 15)
α⁵ est d'ordre 3 (car 5 divise 15)
3) 1, β, β², . . . , βⁿ avec q = 2ⁿ
exemple F₈ : n=3 ; α, α², α³ = 1 + α (VRAI)
exemple F₈ : n=3 ; α², α⁴ = α + α², α⁶ = 1 + α² (VRAI)
7 polynômes de degré 2 : F₈ = Z₂ / polynôme de degré 3 donc β³ = polynôme(1, β, β²)
F_q = Z₂ / polynôme de degré n
donc βⁿ = polynôme(1, β, . . . , βⁿ⁻¹)
la famille {1, β, . . . , βⁿ⁻¹, βⁿ} est liée
cardinal de F_q = 2ⁿ formé des polynômes de degrés ≤ n−1

	1	X	X²
0	0	0	0
1	1	0	0	α⁷ = α⁰
2	0	1	0	α¹
3	1	1	0	α³
4	0	0	1	α²
5	1	0	1	α⁶
6	0	1	1	α⁴
7	1	1	1	α⁵