TP: Autour de l'algorithme d'Euclide
Option Algèbre et Calcul Formel, Préparation à l'Agrégation de Mathématiques d'Orsay
TP: Programmation Linéaire
Document disponible au format: PDF, Postscript, DVI, Text, LaTeX, LyX.
Référence: Wikipedia: Codes correcteurs http://fr.wikipedia.org/wiki/Code_correcteur
1 Introduction
1.1 Objectif du codage
1.2 Exemples d'applications
-
NASA/CNES/...: communication avec des sondes et satellites
- CD / DVD
- Transfert de données par internet (CRC, MD5 checksum)
- Téléphones portables
1.3 Premiers exemples de codes
-
Langages humains!
Syntaxe: orthographe, grammaire
Anglais: 500000 mots de longueur moyenne 10, soit 1 mot valide sur
10^8 possibles
Exemple: pomme, abrucot, poime (pomme, poire, prime, poème)
Sémantique: sens, contexte, ...
- Codage de parité sur 7 bits.
2 Premiers concepts
Lecture rapide du texte
Contexte:
-
Alphabet A:=Z/qZ. Typiquement q=2 (codes binaires).
- Mots dans M:=An.
- n: dimension du code
Distance de Hamming entre deux mots: nombre de lettres qui
diffèrent.
Codage, décodage par distance minimale
Détection et correction d'erreurs
Exercice 1
Exemples en petite dimension:
Trouver tous les codes de (Z/2Z)n pour n=0,...,2.
Donner leur distance et leur capacité de détection.
Permettent-t'ils de corriger une erreur?
Donner un code de (Z/2Z)3 permettant de corriger une erreur.
Peut-on faire mieux?
2.1 Borne de Hamming, codes parfaits
Objectif: Redondance minimale pour une capacité de correction donnée?
Étant donnés un alphabet A avec q=|A|, une longueur
n et une capacité de correction e, trouver un code C ayant
le plus grand nombre possible de mots?
Exercice 2
Borne de Hamming sur |C|.
Nombre de points dans une boule B(x,d):={y,d(x,y)≤ d}
de An de centre x et de rayon d?
Taille de An?
Conclusion?
Application numérique: n=6,q=2,d=3: |C|≤?.
Codage? Décodage?
3 Codes linéaires
Principe: on rajoute de la structure pour rendre les algorithmes plus
efficaces.
Exemple 1
Bit de parité
Exemple 2
Code de Hamming H(7,4).
4 bits (a1,a2,a3,a4) plus trois bits
de redondance (a5,a6,a7) définis par:
| a5 |
= |
a2+a3+a4 |
| a6 |
= |
a1+a3+a4 |
| a7 |
= |
a1+a2+a4 |
-
export(linalg):
Z2:= Dom::IntegerMod(2): Z2::print := extop:
M := Dom::Matrix(Z2):
-
H := M([ [ 0,1,1,1,1,0,0 ],
[ 1,0,1,1,0,1,0 ],
[ 1,1,0,1,0,0,1 ] ]):
-
motDuCode := M([1,0,1,1,0,1,0]);
H * motDuCode;
motQuelconque := M([1,1,0,1,0,1,1]);
H * motQuelconque;
-
G := nullspace(H);
G := transpose(gaussJordan(transpose(_concat(op(G)))));
mot := matrix([1,0,0,0]);
G * mot;
Exercice 3
Combien y-a-t'il de mots dans le code de Hamming H(4,3)?
Calculer la distance de ce code (indice: se ramener en zéro!)
Quelle est sa capacité de detection? de correction?
Est-il parfait?
-
poids := mot -> nops(select([op(mot)], not iszero)):
mots := map(combinat::cartesianProduct([0,1] $ 4), M);
code := [ G * mot $ mot in mots ];
lesPoids := { poids( mot ) $ mot in code };
distance := min( lesPoids minus {0} );
3.1 Décodage par syndrome
Exercice 4
On part du mot zéro, le coder, et faire alternativement une erreur
sur chacun des bits.
Prendre un mot à 4 bits de votre choix, le coder, faire une erreur
sur un des 7 bits, corriger et décoder. Vérifier le résultat.
Que se passe-t'il s'il y a deux erreurs?
3.2 Codage par interpolation (Reed-Solomon)
CIRC, ...
4 TP: Codage et décodage
Mettre au point des démonstrations autour de codage, décodage, calcul
de distance, tests de perfection, pour des codes:
-
décrits par un ensemble de mots
- linéaire
- cycliques
- par interpolation
TP: Autour de l'algorithme d'Euclide
Option Algèbre et Calcul Formel, Préparation à l'Agrégation de Mathématiques d'Orsay
TP: Programmation Linéaire
Examples de codes correcteurs d'erreurs /
Option Algèbre et Calcul Formel /
Nicolas M. Thiéry
Dernière modification: Jeu 22 Fév 2007 11:05:20