Cours G

Question 1

Qu’est-ce qu’un code correcteur ?

Answer 1

Un ensemble de vecteurs (mots) et un couples de fonction (Enc, Dec) qui gèrent la transmission des mots sur un canal de communication bruité

Question 2

Qu’est ce qu’un bruit additif ?

Answer 2

Un bruit qui transforme un vecteur c en vecteur c’ où il existe e tel que c’ = c + e

Question 3

Rapport entre la taille d’un vecteur c et la taille de Enc(c)

Answer 3

Soit c un vecteur de dimension k, c’est-à-dire que c ∈ ({F}₂)^k, alors Enc(c) ({F}₂)ⁿ, il est donc de taille n avec n ≥ k

Question 4

À quoi sert un code correcteur ?

Answer 4

• À récupérer de l’information mal transmise
• À concevoir des systèmes de stockage de données distribués
• À concevoir des algorithmes tolérants aux erreurs

Question 5

Cas des codes correcteurs dans le cadre des transmissions

Answer 5

On veut pouvoir assurer l’intégrité de l’information pour les communications importants, ou alors pouvoir corriger un message bruité lors de sa transmission sous forme de signal

Question 6

Cas des codes correcteurs dans le cadre du stockage de données

Answer 6

On veut savoir combien de fois on a besoin de stocker une information pour être sûrs de pouvoir la retrouver en cas d’aléa

Question 7

Cas des codes correcteurs dans le cadre des algorithmes tolérants aux fautes

Answer 7

On veut pouvoir par exemple faire du calcul distribué et retrouver le résultat même si une partie des machine a transmis le mauvais résultat

Question 8

Qu’est-ce qu’un BSC ?

Answer 8

un “Bynary Symmetric Channel” est un canal de transmission sans mémoire dans lequel le bruit agit indépendamment sur chaque bit : la probabilité que le i-ème bit de x soit différent du i-ème bit de y, où x est le message envoyé et y le message reçu, est la même que leur (i+1)-ème bits soient différents

Question 9

Qu’est-ce qu’une matrice de transition binaire ?

Answer 9

Une matrice M_x,y = Pr(y | x), c’est-à-dire qui calcule la probabilité que y soit reçu sachant que x est envoyé :

0 –(1 - p)–> 0
1 –(1 - p)–> 1
et sur les diagonales de 0 vers 1 et de 1 vers 0, p

Question 10

Que signifie la symétrie de la matrice de transition binaire ?

Answer 10

La symétrie de la matrice de transition binaire représente la symétrie de l’erreur : il y a la même probabilité qu’un 0 devienne un 1 et qu’un 1 devienne un 0

Question 11

Matrice de transition dans le cas q-aire

Answer 11

M(x, y) =
- 1-p si x = y
- p/(q-1) si x != y

Question 12

Étapes d’une communication

Answer 12

• Message m
• Encodage Enc(m) = c avec Enc : {0, 1}^k → {0, 1}ⁿ injective (n ≥ k)
• Transmission y = Channel(c) où y = c + e avec e l’erreur additive ∈ {0, 1}ⁿ (et y ∈ {0, 1}ⁿ)
• Décodage Dec(y) = Dec(c) = m (dans le cas idéal)

Question 13

Théorème de Shannon (énoncé en formules)

Answer 13

• Soit 0 ≤ p ≤ 1/2, ϵ ≤ 1/2 - p et n&raquo_space; 0, alors
  
  • ∃ δ > 0 tel qu’il existe
    
    • Enc : {0, 1}^k → {0, 1}ⁿ
    • Dec : {0, 1}ⁿ → {0, 1}ⁿ
    • avec k ≤ ⌊(1 - H(p) + ϵ) × n⌋ tel que ∀ m ∈ {0, 1}^k, Pr(Dec(Enc(m) + e) != m) ≤ 2^-δn
  • Pour k > ⌈(1 - H(p) + ϵ) × n ⌉, pour n’importe quel (Enc, Dec)+ ϵ) × n, ∃ m ∈ {0, 1}^k tel que Pr(Dec(Enc(m) + e) != m) ≥ 1/2

Question 14

Théorème de Shannon (énoncé en langage naturel)

Answer 14

Soit 1 - H(p) la capacité du canal, alors si un code (ou son rendement) ne dépasse pas cette capacité, il est possible de trouver une fonction de code qui corrige autant d’erreur qu’on veut, c’est-à-dire que la probabilité de mal décoder tend vers 0

Question 15

Qu’est-ce que le rendement du code c ?

Answer 15

n / k avec n la taille de c et k la taille de m tel que Enc(m) = c, il mesure la redondance du message m (de taille k) dans c (de taille n) et indique la capacité de correction

Question 16

Qu’est-ce que la capacité d’un canal ?

Answer 16

Soit p la probabilité liée à un canal, alors la capacité de ce canal est 1 - H(p)

Question 17

Qu’est-ce que la linéarité de fonction ?

Answer 17

Le fait que ces fonctions puissent être vues comme des matrices

Question 18

Exemples de fonctions linéaires

Answer 18

Enc et Dec sont des fonctions linéaires : Enc(m) = v_m × M_Enc = v_c

Question 19

Qu’est-ce que la matrice génératrice du code ?

Answer 19

M_Enc telle que Enc(m) = v_m × M_Enc = v_c

Question 20

Qu’est-ce que la matrice de parité du code ?

Answer 20

La matrice orthogonale à la matrice génératrice du code, de dimensions (n × n - k)

Question 21

Définition de la distance de Hamming

Answer 21

La distance de Hamming est le nombre de bits qui sépare deux vecteurs : d_H(x, y) = |{i | x_i != y_i}|

Question 22

Caractérisation de la distance de hamming (schéma de preuve)

Answer 22

La distance de Hamming est bien une distance puisqu’elle respecte les trois critères d’une distance :
- d_H(x, y) ≥ 0 avec égalité si et seulement si x = y
- d_H(x, y) = d_H(y, x)
- d_H(x, z) ≤ d_H(x, y) + d_H(y, z) (inégalité triangulaire), car x_i != z_i ⇔ x_i != y_i XOR z_i != y_i

Question 23

Qu’est-ce que le poids d’un vecteur ?

Answer 23

Poids(x) = |{i | x_i != 0}|

Question 24

Lien entre le poids et la distance de Hamming

Answer 24

d_H(x, y) = Poids(x - y)

Question 25

Distance de Hamming d’un code

Answer 25

d_H(C) = min_{C1 != C2 ∈ C}d_H(C₁, C₂)

Question 26

Qu’est-ce qu’un code linéaire ?

Answer 26

Le code C est linéaire si Enc(m₁) + Enc(m₂) = Enc(m₁ + m₂)

Question 27

Distance de hamming pour un code linéaire (énoncé)

Answer 27

Si C est linéaire d_H(C) est le mot de plus petit poids != (0, 0, …, 0)

Question 28

Distance de hamming pour un code linéaire (schéma de preuve)

Answer 28

On veut montrer que pour C linéaire, minD = min_{c1 != c2 ∈ C}d_H(c₁, c₂) = min_{c ∈ C} w(c) = minW :
- Si d_H(c₁, c₂) = L, il existe c₃ = c₁ + c₂ tel que w(c₃) = L, donc minD ≥ minW
- Si w(c) = L, il existe c₁ = (0, 0, …, 0) et c₂ = c tels que d_H(c₁, c₂) = L, donc minW ≥ minD

Question 29

Qu’est-ce que le code de parité ?

Answer 29

C_⊕ : Enc(m) = (m, ⊕) donc n = k + 1 → très bon rendement, mais trop bon car on ne peut corriger quasiment aucune erreur

Question 30

Quelle est la distance de Hamming du code de parité ?

Answer 30

d_H(C_⊕) = 2 car le plus petit mot non nul de C_⊕ est (1, 1)

Question 31

Le code de parité est-il linéaire ?

Answer 31

Oui, car 0 ∈ C_⊕ et Enc(c₁) + Enc(c₂)
= m_{1, 1}, m_{1, 2}, …, m_{1, k}, Σm_{1, i}
+
m_{2, 1}, m_{2, 2}, …, m_{2, k}, Σm_{2, i}
= m_{1, 1} + m_{2, 1}, m_{1, 2} + m_{2, 2}, …, m_{1, k} + m_{2, k}, Σm_{1, i} + Σm_{2, i}
= Enc(c₁ + c₂)

Question 32

Qu’est-ce que le code de répétition ?

Answer 32

C_{r, rep} : Enc(m) =(m, m, …, m) donc n = r × k → rendement r

Question 33

Le code de répétition est-il linéaire ?

Answer 33

Oui, car 0 ∈ C_{r, rep} et Enc(c₁) + Enc(c₂)
= c₁, c₁, …, c₁
+
c₂, c₂, …, c₂
= c₁ + c₂, c₁ + c₂, …, c₁ + c₂
= Enc(c₁ + c₂)

Question 34

Quelle est la distance de Hamming du code de r répétition ?

Answer 34

d_H(C_{r, rep}) = r car le plus petit mot non nul de C_{r, rep} est (1, 1, …, 1)

Question 35

Qu’est-ce qu’un MLD ?

Answer 35

Un Maximum Likehood Decoder : il s’agit de corriger avec le mot qui a le plus de probabilité d’avoir été envoyé

Question 36

Lien entre MLD et BSC (énoncé)

Answer 36

Sur un canal BSC, un décodage MLD équivaut à chercher le mot de code à distance la plus proche

Question 37

Lien entre MLD et BSC (schéma de preuve)

Answer 37

Pr(y reçu | c transmis)
= Π_i=1..n Pr(y_i reçu | c_i transmis)
= (1 - p) × … × (1 - p) × p × … × p (autant que de non-erreurs puis autant que d’erreurs)
= (1 - p)^{n - d_H(y, c)} × p^{d_H(y, c)}
= (1 - p)ⁿ/(1 - p)^{d_H(y, c)} × p^{d_H(y, c)}
= (1 - p)ⁿ × (p/(1 - p))^{d_H(y, c)} donc en prenant d_H(y, c) le plus petit possible, on a bien la meilleure probabilité de recevoir le bon mot

Question 38

Avantage du MLD décodeur

Answer 38

On sait que la bonne chose à faire est de trouver le mot à plus proche distance

Question 39

Inconvénient du MLD décodeur

Answer 39

Trouver le mot à plus proche distance est un problème NP-difficile, même dans les codes linéaires

Question 40

Qu’est-ce qu’un BDD ?

Answer 40

Un Bounded Distance Decoder prend en entrée le mot y reçu, le code C donné et t une borne sur le nombre d’erreurs faites, et renvoie c ∈ C tel que d_H(y, c) ≤ t

Question 41

Dans quel cas un BDD est-il particulièrement efficace ?

Answer 41

S’il y a un seul mot de code c ∈ C tel que d_H(y, c) ≤ t la borne sur le nombre d’erreurs, alors on sait que c est forcément le bon mot

Question 42

Évaluation du code de 3-répétition

Answer 42

Le code de 3-répétition peut corriger 1 erreur, puisqu’il n’y a pas d’ambiguïté pour le décoder : il existe un unique mot à distance 1 pour un y donné

Question 43

Évaluation du code de parité

Answer 43

Le code de parité peut détecter un nombre impair d’erreurs

Question 44

Quatre assertions équivalentes pour évaluer un code C

Answer 44

• C a distance minimale d ≥ 2
• C peut corriger ⌊(d - 1) / 2⌋ erreurs
• C peut détecter d - 1 erreurs
• C peut corriger d - 1 effacements

Question 45

C a distance minimale d ≥ 2 si et seulement si C peut détecter d - 1 erreurs (schéma de preuve)

Answer 45

Si d ≥ 2, qu’on reçoit y et qu’on sait qu’il y a eu e ≤ d - 1 erreurs, on peut déterminer quel mot c a été envoyé car d_H(c, y) ≤ d - 1, mais s’il y a eu plus de d erreurs, alors y peut appartenir aux boules de plusieurs mots différents et on ne peut pas savoir de laquelle il vient

Question 46

C a distance minimale d ≥ 2 si et seulement si C peut corriger d - 1 effacements (schéma de preuve)

Answer 46

Si d ≥ 2 et que C ne peut pas corriger d - 1 effacements, c’est-à-dire qu’il hésite entre c₁ et c₂, alors c’est que d_H(c₁, c₂) ≤ d -1, ce qui est contradiction avec la distance d de C

Question 47

C a distance minimale d ≥ 2 si et seulement si C peut corriger ⌊(d - 1) / 2⌋ erreurs (schéma de preuve)

Answer 47

Si d ≥ 2 et qu’on reçoit y, on cherche c unique tel que d_H(y, c) ≤ t = ⌊(d - 1) / 2⌋ : si c₁ et c₂ sont candidats, alors c’est que d_H(c₁, y) = d_H(c₂, y) ≤ t, donc d_H(c₁, c₂) ≤ d_H(c₁, y) + (y, c₂) (par inégalités triangulaires) ≤ 2t = d - 1, ce qui n’est pas possible car C a distance d

Question 48

Qu’est-ce que B_t(x) ?

Answer 48

B_t(x) est la boule de centre x et de rayon t qui contient tous les mots y tels que d_h(x, y) ≤ t

Question 49

Quelles sont les trois espérances pour un bon code ?

Answer 49

• Ne pas avoir trop de redondance : R = n / k doit être le plus proche de 1 possible
• Corriger beaucoup d’erreurs (donc avoir une grande distance)
• Avoir des algorithmes efficaces d’encodage et de décodage

Question 50

Comment se comporte les codes de Hamming vis-à-vis des trois espérances pour un bon code ?

Answer 50

Ils sont un bon compromis entre un rendement de code faible et des algorithmes efficaces

Question 51

Comment se comporte les codes de Reede-Solomon vis-à-vis des trois espérances pour un bon code ?

Answer 51

Ils sont un bon compromis pour les trois espérances à la fois

Question 52

Comment évaluer si un code donné respecte les trois espérances pour un bon code ?

Answer 52

Pour les deux premières espérances sur le rendement et le nombre d’erreurs corrigées, on utilise des bornes sur les paramètres pour les étudier

Question 53

Qu’est-ce que que le code de Hamming pour k = 4 ?

Answer 53

C_H : Enc(m = (x₁, x₂, x₃, x₄)) = (x₁, x₂, x₃, x₄, x₁ + x₂ + x₄, x₁ + x₃ + x₄, x₂ + x₃ + x₄)

Question 54

Le code de Hamming pour est-il linéaire pour k = 4 ?

Answer 54

Oui, car 0 ∈ C_H et pour c₁ et c₂ ∈ C_H, c₁ + c₂ ∈ C_H, Enc(c₁) + Enc(c₂) =
c_{1, 1}, c_{1, 2}, c_{1, 3}, c_{1, 4}, c_{1, 1} + c_{1, 2} + c_{1, 4}, c_{1, 1} + c_{1, 3} + c_{1, 4}, c_{1, 2} + c_{1, 3} + c_{1, 4}
+
c_{2, 1}, c_{2, 2}, c_{2, 3}, c_{2, 4}, c_{2, 1} + c_{2, 2} + c_{2, 4}, c_{2, 1} + c_{2, 3} + c_{2, 4}, c_{2, 2} + c_{2, 3} + c_{2, 4}
= c_{1, 1} + c_{2, 1}, c_{1, 2} + c_{2, 2}, c_{1, 3} + c_{2, 3}, c_{1, 4} + c_{2, 4}, c_{1, 1} + c_{2, 1} + c_{1, 2} + c_{2, 2} + c_{1, 4} + c_2,4, c_{1, 1} + c_{2, 1} + c_{1, 3} + c_{2, 3} + c_{1, 4} + c_{2, 4}, c_{1, 1} + c_{2, 1} + c_{1, 3} + c_{2, 3} + c_{1, 4} + c_{2, 4}
= Enc(c₁ + c₂)

Question 55

Quelle est la distance de Hamming du code de Hamming pour k = 4 ?

Answer 55

d_H(C_H) = 3

Question 56

Évaluation du code de Hamming pour les 3 critères d’évaluation d’un bon code

Answer 56

• R = 4/7, c’est mieux que le 1/3 de C_{3, rep}
• t = ⌊(d - 1) / 2⌋ = 1
• ?

Question 57

Matrice génératrice du code de parité

Answer 57

[1 0 0 … 0]
[0 1 0 … 0]
[0 0 1 … 0]
[…………….]
[0 0 0 … 1]
[1 1 1 … 1]

Question 58

Matrice génératrice du code de répétition

Answer 58

[Id_k]
[Id_k]
[……………………….]
[Id_k] r fois

Question 59

Matrice génératrice du code de Hamming pour k = 4

Answer 59

[1 0 0 0 1 1 0]
[0 1 0 0 1 0 1]
[0 0 1 0 0 1 1]
[0 0 0 0 1 1 1]

Question 60

Matrice de parité du code de Hamming pour k = 4

Answer 60

[0 0 0 1 1 1 1]
[0 1 1 0 0 1 1]
[1 0 1 0 1 0 1]

Question 61

Propriété de la matrice de parité H par rapport à la matrice génératrice G

Answer 61

Hy = 0 si et seulement si c ∈ C, c’est-à-dire si y est bien engendré par G

Question 62

Évaluation de l’encodage du code de Hamming

Answer 62

Encodage efficace car on a une matrice génératrice (Hamming linéaire) donc on peut juste effectuer un produti matrice-vecteur-

Question 63

Évaluation de la détection d’erreurs du code de Hamming

Answer 63

Efficace avec l’utilisation de la matrice de parité

Question 64

Évaluation du décodage du code de Hamming

Answer 64

Le décodage d’un code linéaire est NP-difficile

Question 65

Qu’est-ce qu’un code parfait ?

Answer 65

Un code de paramètres (n, k, d) tels que 2^kΣ_i=0..t (n i) = 2ⁿ (borne d’empilement de sphères atteinte)

Question 66

Propriété d’un code parfait

Answer 66

Si C est parfait, alors pour tout y, il existe un unique c tel que d_H(y, c) ≤ t

Question 67

Nombre de mots dans une même boule B_t

Answer 67

2^kΣ_i=0..t (n i)

Question 68

Exemple de code parfait

Answer 68

Le code de Hamming est parfait, et c’est le seul à l’être sur {F}₂ en dehors des codes triviaux

Question 69

Comment corriger une erreur avec les codes de Hamming ?

Answer 69

• Détecter une erreur en se servant de la matrice de parité : Hy = b != 0
• Calculer la valeur binaire du vecteur b
• Changer le b-ième bit du vecteur y

Question 70

Paramètres du code de Hamming généralisé

Answer 70

Pour un paramètre r, (n = 2^r - 1, k = 2^r - r - 1, d = 3)

Question 71

Qu’est-ce qu’un code MDS (Maximum Distance Separable) ?

Answer 71

Un code de paramètres (n, k, d) tels que d = n - k + 1 (borne singleton atteinte)

Question 72

Lien entre la linéarité et la borne singleton

Answer 72

Tous les codes linéaires atteignent la borne singleton

Question 73

Encodage des codes de Reede-Solomon

Answer 73

• On considère f ∈ {F}_q[X]_<k l’espace des polynômes à coefficients dans {F}_{q et de degré < k}}
• Encodage : A = {α₁, …, α_n} un ensemble de n points disjoints dans {F}_q, et f → (f(α₁), …, f(α₁))

Question 74

Reede-Solomon atteint la borne singleton (schéma de preuve)

Answer 74

• Prendre f et g différents et f_A et g_A les vecteurs d’évaluations de f et g en A = {α₁, …, α_n}
• d_H(f, g) = |{i | f(α_i) != g(α_i)}| et n - d = |{i | f(α_i) = g(α_i)}| = |{i | (f - g)(α_i) = 0}| ≤ k - 1 sinon f = g, et d ≤ n - k + 1 par définition, donc d = n - k + 1

Question 75

Évaluation du décodage des codes de Reede-Solomon

Answer 75

• Si aucune erreur, on calcule Lagrange(α_i, y_i)
• S’il y a des effacements (d - 1), il nous reste n - (d - 1) = n - d + 1 = k évaluations et f est de degré < k, donc on peut aussi utiliser Lagrange(α_i, y_i)

Question 76

Polynôme locateur d’erreur

Answer 76

Π_{i tel que yi!=f(αi)} (X - α_i), ainsi Π_i=1..n(α_i)(f(α_i) - y_i) = 0