Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Codes de Hamming AU 2021-2022 66  Code de Hamming (1948): • code linéaire • co

Codes de Hamming AU 2021-2022 66  Code de Hamming (1948): • code linéaire • corrigeant toutes les erreurs de poids 1 (de façon fiable) • de rendement ρ = k/n maximum pour une redondance fixée m = n-k  Théorème • un code c(n,k) est au moins 1-correcteur si et seulement si toutes les colonnes de sa matrice de contrôle sont distinctes et non nulles  Propriétés 1/ distance minimale 3 2/ capacité de correction 1 3/ parfait c-à-d toute erreur à distance 1 (c-à-d une erreur sur un seul bit) d'un code est corrigée Codes de Hamming (canaux bruités) AU 2021-2022 67  Rendement 1/ Les n colonnes de la matrice de contrôle H sont des vecteurs de taille m avec m= n-k, il y a 2m vecteurs possibles 2/ Si le code est de capacité de correction t≥1, les n colonnes de H sont non nulles et toutes distinctes. On a donc : n 2m -1 3/ rendement ρ = k/n= (n-m)/n = 1-m/n ρ est maximum si m/n minimum, c-à-d si n est maximum ce qui implique n = 2m -1 (et donc k = n-m = 2m - m -1)  H a donc pour colonnes tous les vecteurs de taille m sauf le vecteur nul Codes de Hamming (canaux bruités) AU 2021-2022 68 Codes de Hamming (canaux bruités)  Ce sont des codes (n,k,d)=(2m-1, 2m-m-1,3) avec m = la redondance • En pratique, on fixe la redondance m, ce qui donne k et n  On code donc chaque bloc de k=2m-m-1bits par un bloc de n=2m-1 bits  rem : la valeur de m est au moins 2 (si m=1, alors n=1, pas de sens)  H(7,4) : 7 bits de code, pour 4 bits à coder. il peut y avoir 7 erreurs de 1 bit => 3 bits pour les identifier => 4+3 = 7 m n = 2m-1 k = n-m 2 3 1 3 7 4 4 15 11 5 31 26 6 63 57 7 127 120 codes H(3,1) H(7,4) H(15,11) H(31,26) H(63,57) H(127,120) rendement 0,33 0,57 0,73 0,83 0,90 0,94 AU 2021-2022 69 Codes de Hamming : en pratique  Obtenus par la matrice de contrôle  H contient tous les vecteurs sauf le vecteurs nul  Par exemple la matrice de contrôle H de H(15,11) (m=4) est:  Par permutation des colonnes, on obtient toute une famille de codes de Hamming 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 AU 2021-2022 70 Codes de Hamming : en pratique := V               v1 v2 v3 := V'                     v1 v2 v3 v0 Rappel : les codes de Hamming permettent de coder des mots de longueur 1= (22-1-2) ou 4 (23-1-3) ou11 = (24-1-4) ou 26 = (25-1-5) ou 57 = (26-1-6) ou120 = (27-1-7),… Comment obtenir un code de Hamming pour les autres longueurs ? Soit par exemple des mots de longueur 3 : On agrandit le mot jusqu'à la dimension k' (4,11,26..) immédiatement supérieure. Pour k = 3, on considère que c'est un mot de longueur 4 ,dont le premier bit v0 est fixé à une valeur quelconque, par exemple 0. On effectue le codage sur la nouvelle forme, puis on fixe dans l'expression des bits de code la valeur de v0 choisie. AU 2021-2022 71 Codes de Hamming : en pratique La valeur de ce bit v0 restera inchangée. Soit alors les matrices de H(7,4) séparable, par exemple : := H               0 1 1 1 1 0 0 1 0 1 1 0 1 0 1 1 0 1 0 0 1 Par exemple, on fixe la valeur de v0 à 0 et on utilise un code de Hamming séparable := G                                       1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 1 1 1 1 0 1 1 1 1 0 1 = G.V'=C'                                       v0 v1 v2 v3 + + v1 v2 v3 + + v0 v2 v3 + + v0 v1 v3                                   v1 v2 v3 + + v1 v2 v3 + v2 v3 + v1 v3 C= v0= 0 AU 2021-2022 72 Codes de Hamming : en pratique En codage : la première colonne de G ajoute les termes en v0. := G                                       1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 1 1 1 1 0 1 1 1 1 0 1 := V                     0 v1 v2 v3 => En prenant v0 =0, on peut supprimer la première colonne et la première ligne de G                                       0 v1 v2 v3 + + v1 v2 v3 + v2 v3 + v1 v3 := G                                   1 0 0 0 1 0 0 0 1 1 1 1 0 1 1 1 0 1                                   v1 v2 v3 + + v1 v2 v3 + v2 v3 + v1 v3 := V               v1 v2 v3 AU 2021-2022 73 Codes de Hamming : en pratique résumé Pour des mots d'information de longueur k autre que 4,11,26, etc.., on considère un codage de Hamming séparable pour des mots de longueur k' = 4,11, 26 immédiatement supérieure (on "ajoute" k'-k bits). On supprime dans la matrice génératrice les (k'-k) premières lignes et (k'-k) premières colonnes. On supprime dans la matrice de contrôle les (k'-k) premières colonnes Le nombre de bits de redondance est le même que pour des mots d'information de longueur k' : - pour des mots de longueur 2 ou 3, on ajoute 3 bits comme pour des mots de 4 bits - pour des mots de longueur 5,6,7,8,9,10, on ajoute 4 bits comme pour des mots de 11 bits - etc… Codes Polynômiaux AU 2021-2022 75 Codes polynômiaux  Suite de p bits : a1,a2,…,ap coefficients du polynôme a1x(p-1)+a2x(p-2)+…+ap  Il faut faire attention à la numérotation des coef.  Ex : 1011 x3+x+1  Pp-1 (ensemble des polys de degré < p)  degré du poly = p-1 pour une suite de p bits  Base canonique : { xp-1, xp-2,…..,x2,x,1}  Division polynomiale  P(x) = D(x).Q(x)+R(x) avec R(x)≠0 où deg(R)<deg(D)  Ex : x3+x2+x=(x+1)(x2+1)+1 (1 1 1 0) = (0 0 1 1) (0 1 0 1) + (0 0 0 1) AU 2021-2022 76  Codage : polynôme de Pk-1 polynôme de Pn-1  Définition :  code linéaire  tous les mots de code sont des multiples de l'un d'eux noté g(x) (au sens produit de polynômes)  Le polynôme g(x) servant à construire le codage est appelé polynôme générateur  Un code servant à coder des mots de longueur k par des mots de longueur n est noté Cn,k(g) Codes polynômiaux AU 2021-2022 77  Fonction de codage  soit g(x) de uploads/S4/ s8-codage-canal2.pdf