1°) introduction

Hypothèse: le bruit ne touche pas plus de la moitier des bits
  1. bit de parité
  2. 2n bit > 1erreur detecter, pas toujours deux
  3. 3n bit > 2erreur detecter, on peu corriger 1 erreur
  4. Xn bit > ... etc
  5. code de hamming 4bit + 3bit

2°) rappel

B = {0, 1} est un corp, a+b = a^b et a*b = (a&b)==1
definition: code = enssemble fini de bit, mot = code de même taille
definition: la distance d'un code c'est le nombre minimal de bit qu'il faut modifier = nombre d'erreur detectable+1
theoreme: si un code d'erreur à la distance d alors il peu corriger (d-1)/2 erreur

3°) code linéaire

a°) présentation

on impose un propriété supplémentaire pour pouvoir l'étudier
definition: un code est linéaire si:
  1. il est un sous espace vectoriel de B*
  2. si 0 appartient a C alors si u et v appartienne à C -> u^v appartienne a C
definition: la distance d'un code c'est le nombre minimal de bit qu'il faut modifier = nombre d'erreur detectable+1
theoreme: si un code d'erreur à la distance d alors il peu corriger (d-1)/2 erreur
pour calculer la distance d'un code linéaire, il suffit de prendre le minimum des nombres de 1 dans les mots différentsz de 0

b°) matrice génération / parité

si C est linéaire, sont nombre d'éléments est une puissance de 2
c'est une représentation compact d'un code linéaire. Elle est représenté par une liste minimal qui permet d'obtenir tous les autres par xor
exemple:pour le code de parité on peu prendre {0011, 0101, 1001} > non unique
mots de départ = 001010 = w
on peu alors calculer comme ceci:

H = matrice génératrice
for(int i = 0; i<8; ++i) { result = (w&1)*H[i]; w >>= 1; }
remarque: si la matrice est de la forme identitaire, le resultat de w est w+quelque chose
vérification: pour vérifier si w est correct, on utilise une matrice de parité,
si le code transforme k en n bits, la matrice est de taille k*n
la taille de la matrice de parité est de taille n*(n*k), V*G=0 si V est correcte

Lorsque la matrice génératrice est de la forme [Id | A]
une matrice de parité est sous la forme [A / Id]

exemple: code de bit de parité sur 4bits
G = [Id | 1], matrice de parité = [1111/1]