IFT 6170 Théorie et pratique des codes correcteurs

Claude Crépeau

Département d’Informatique et R.O.,

Université de Montréal, C.P. 6128, succursale centre-ville,

Montréal (Québec), Canada H3C 3J7. e-mail: crepeau@iro.umontreal.ca.

IFT6170 Claude Crépeau. i

Table of Contents

1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Objectifs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Codes linéaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

2 théorie des nombres et corps finis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.1 définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.2 opérations de base efficaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.3 calcul d’une exponentiation rapide . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.4 calcul du PGCD et d’inverses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2.5 Nombres premiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.6 corps premiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2.7 polynômes sur un corps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.8 polynômes irréductibles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.9 Corps quelconques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.10 Éléments primitifs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.11 Factorisation de q − 1... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

3 Espaces vectoriels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3.1 Combinaisons linéaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3.2 Produit Scalaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

4 Algèbre Linéaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 4.1 opérations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 4.2 temps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 4.3 déterminant . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 4.4 matrices échelonées réduites . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

5 Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 5.1 taux de transmission d’un code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 5.2 distance minimale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 5.3 codes parfaits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 5.4 codes équivalents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

6 Codes Linéaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 6.1 distance minimale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 6.2 matrice génératrice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 6.3 codage et décodage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 6.4 forme systématique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 6.5 matrice de parité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 6.6 syndromes et cosets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 6.7 détection d’erreurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 6.8 correction d’erreurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 6.9 code dual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

7 Codes de Hamming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 7.1 construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 7.2 distance minimale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 7.3 correction d’erreurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

8 Théorie de l’information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 8.1 Modèles d’erreurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 8.2 Entropie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 8.3 Entropie conditionelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 8.4 Information mutuelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 8.5 Capacité d’un canal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 8.6 Objectifs de la théorie des codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 8.7 Théorèmes de Shannon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 8.8 Outils utiles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

9 Limites sur les performances des codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 9.1 Borne inférieure de Varshamov-Gilbert . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 9.2 Borne supérieure de Hamming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 9.3 Borne supérieure de Plotkin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 9.4 Borne supérieure de McEliece-Rodemich-Rumsey-Welch . . . . . . . . . . . . . . . . . . . . . 23

10 Codes de Hadamard . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 10.1 Matrices de Hadamard . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 10.2 construction de Sylvester . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 10.3 construction de Paley . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 10.4 codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

11 Codes cycliques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 11.1 polynome générateur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 11.2 polynome de parité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 11.3 code dual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 11.4 facteurs de x^{n} − 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 11.5 borne de BCH . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

12 Codes BCH . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 12.1 Distance minimale effective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 12.2 Symboles d’information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 12.3 Les codes BCH sont mauvais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

13 Codes Classiques de Goppa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

17 NP-complétude de problèmes sur les codes . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 17.1 NP-complet ou NP-ardu? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 17.2 correction d’erreurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 17.3 NP-complétude de PMCS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 17.4 poids des mots de code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 17.5 NP-complétude de PC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

18 Codes Géométriques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

19 Graphes et codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 19.1 Graphes Expandeurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 19.2 Codes expandeurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 19.3 Codes superconcentrateurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

20 Applications à la cryptographie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 20.1 partages de secrets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 20.2 Cryptosystème de McEliece . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 20.3 réductions entres protocoles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 20.4 Winer wire-tap channel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 20.5 Extension de Maurer et BBCM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 20.6 Protocoles cryptographiques à partir d’un canal bruyant . . . . . . . . . . . . . . . . . . . . . 37

21 Codes quantiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

5 Codes

Un (n, M, d) code C sur F_{q} est un ensemble de M mots de F_{q}^{n} où d est la distance minimale entre deux mots de C au sens de Hamming, d = min{Δ (c_{1}, c_{2}) : c_{1}, c_{2} ∈ C}. La distance de Hamming entre deux mots c_{1}, c_{2}, dénotée Δ (c_{1}, c_{2}), est le nombre de positions où c_{1} et c_{2} diffèrent.

5.1 taux de transmission d’un code

Le taux de transmission d’un (n, M, d) code est le ratio entre la longeur nécessaire pour exprimer les M mots de code de façon minimale et n:

R = \frac{log M}{n} .

5.2 distance minimale

Lors de la transmission d’un mot de code c ∈ C sur un canal imparfait, il est TOUJOURS possible de corriger ⌊(d − 1)/2⌋ erreurs, en choisissant le mot de code c^{∗} le plus près du mot reçu w. Si le nombre d’erreur est inférieur ou égal à (d − 1)/2 il ne peut y avoir d’ambigüité sur le mot de code original car il ne peut exister deux mots de codes c_{1} ≠ c_{2} tels que Δ (w, c_{1}) ≤ (d − 1)/2 et Δ (w, c_{2}) ≤ (d − 1)/2 étant donné que ces deux mots satisferait alors Δ (c_{1}, c_{2}) ≤ d − 1. On appèlle la sphère associée à un mot de code c l’ensemble des mots à distance inférieur ou égal à (d − 1)/2 de c:

Φ_{c} = {w ∈ F_{q}^{n} : Δ (w, c) ≤ (d − 1)/2}.

5.3 codes parfaits

Un code parfait est un code où tous les mots de F_{q}^{n} sont dans la sphère d’un mot de code.

Theorem 7. Un code (n, M, d) est parfait si et seulement si d est impair et

M ∑_{i=0}^{(d−1)/2} \binom{n}{i}(q − 1)^{i} = q^{n}.

Exemple: Le code C = {00000...0, 11111...1} où les mots sont de longueur impaire est parfait.

5.4 codes équivalents

Deux codes C, C′ ⊆ F_{q}^{n} sont équivalents s’il existe une permutation π des positions 1, 2, ..., n telle que

(c_{1}, c_{2}, ..., c_{n}) ∈ C ⟺ (c_{π(1)}, c_{π(2)}, ..., c_{π(n)}) ∈ C′.

Theorem 8. Si C est un code (n, M, d), C′ est un code (n, M′, d′) et C, C′ sont équivalent alors M = M′ et d = d′

6 Codes Linéaires

Un [n, k, d] code linéaire C sur F_{q} est un (n, q^{k}, d) code qui satisfait la propriété que si c_{1}, c_{2} ∈ C alors αc_{1} + βc_{2} ∈ C pour α, β ∈ F_{q}. Ou encore, C est un sous-espace vectoriel de dimension k de F_{q}^{n}. Les codes linéaires ont de nombreux avantages au niveau de leur représentation concise (il suffit de k mots de code pour specécifier une base de C) et leur codage/décodage efficace.

6.1 distance minimale

La distance minimale d’un code linéaire est donnée par d = min{w(c) : c ∈ C − {0^{n}}} où w(c) est le poids de c, c’est-à-dire le nombre de positions non-nulles de c.

6.2 matrice génératrice

Un [n, k, d] code linéaire C sur F_{q} est spécifié par une matrice génératrice G de dimensions k × n de rang k telle que

C = espace engendré par les lignes de G.

Exemple: la matrice suivante sur F_{3} [ \begin{matrix}2 & 0 & 1 \\ 0 & 0 & 1 \end{matrix} ] engendre le code

C = {(0 0 0), (0 0 1), (0 0 2), (2 0 1), (1 0 2), (2 0 2), (1 0 0), (2 0 0), (1 0 1)}.

6.3 codage et décodage

La matrice génératrice G nous donne une application de F_{q}^{k} → F_{q}^{n} qui défini le codage d’un mot w de F_{q}^{k} par un mot de code c de F_{q}^{n} par

c = wG.

Le décodage d’un mot de code c est le mot w qui satisfait l’équation précédente.

6.4 forme systématique

Une matrice G est en forme systématique si G = [I_{k}|A] où I_{k} est la matrice identité k × k et A une matrice k × (n − k) quelconque. Un code C possède une forme systématique s’il existe une matrice G en forme systématique qui l’engendre.

Theorem 9. Tout [n, k, d] code C est équivalent à un [n, k, d] code C′ qui possède une forme systématique.

Avantages: Quand on a un code C spécifié par un matrice G en forme systématique le codage et le décodage sont simplement sécifiés par l’équation

wG = [w|wA].

Pour coder un mot w il suffit donc de lui adjoindre wA et pour décoder un mot de code c = [w|x] il suffit d’extraire w.

6.5 matrice de parité

Un [n, k, d] code linéaire C, peut également spécifié par une matrice de parité H de dimensions (n − k) × n de rang n − k telle que

C = {c ∈ F_{q}^{n} : cH^{⊤} = 0_{n−k}}

où 0_{n−k} est le vecteur nul de F_{q}^{n−k}. Une relation simple relie la matrice génératrice G et la matrice de parité H:

GH^{⊤} = 0_{k×(n−k)} HG^{⊤} = 0_{(n−k)×k}.

Notons que pour un G donné, H n’est pas unique et vice vera. Néanmoins i G est en forme systématique [I_{k}|A], il est alors trivial de trouver un H correspondant en prenant

H = [−A^{⊤}|I_{n−k}].

6.6 syndromes et cosets

On utilise la matrice H pour définir une fonction de F_{q}^{n} → F_{q}^{n−k} que l’on nomme syndrome d’un mot w ∈ F_{q}^{n}:

Syn(w) = wH^{⊤}.

On appele coset l’ensemble des mots de même syndrome

Coset(w) = {x ∈ F_{q}^{n} : Syn(w) = Syn(x)}.

On note que C = Coset(0) et que Coset(w) = {x ∈ F_{q}^{n} : x = w + c, c ∈ C}.

6.7 détection d’erreurs

Dans un code linéaire il est très simple de détecter des erreurs puisqu’un mot reçu w est erroné si et seulement si wH^{⊤} ≠ 0_{n−k}. Si une erreur est assez importante pour provoquer qu’un mot de code soit projeté sur un autre mot de code, il n’y a aucune façon de le détecter.

6.8 correction d’erreurs

La correction d’erreur dépend généralement du modèle d’erreurs qui régit notre canal de communication imparfait, mais dans la plupart des cas les vecteurs d’erreur de poids inférieurs sont plus probable que ceux de poids supérieurs. Ceci induit le décodage à distance minimale, comme méthode de correction d’erreurs. Il s’agit de trouver le mot de code ayant la plus petite distance au mot reçu

corrige(w) = c t.q. Δ (w, c) ≤ Δ (w, c′) , c′ ∈ C.

Dans un code parfait, ce mot de code est défini de façon unique pour tous les mots possible.

En général, le probléme de la correction d’erreur est équivalent à celui de trouver un mot de poids minimum d’un certain syndrome.

Theorem 10. Étant donné un mot quelconque w, soit w^{∗} un mot de poids minimal dans Coset(w). Le mot w − w^{∗} est un mot de code à distance minimale de w.

En général, on ne connait pas de façon efficace de trouver un mot de poids minimal d’un certain syndrome. Si l’on énumère tous les mots d’un coset pour trouver celui de poids minimal, on utilisera un temps O(q^{k}). Si le poids minimal est relativement grand, une recherche exhaustive à partir des mots de poids 0, 1, 2, ... prendre également un temps exponentiel. On verra bientôt que ce problème est NP-complet.

6.9 code dual

À chaque [n, k, d] code linéaire C correspond un [n, n − k, d̂] code dual Ĉ engendré par la matrice H. La matrice G est sa matrice de parité. On ne connait que des relation triviales entre d et d̂. On verra plus tard des applications où on considèrera ces deux codes simultanément.

7 Codes de Hamming

Les codes de Hamming forment une famille infinie {H_{m}}_{m>0} de codes linéaires binaires ayant des paramètres [2^{m} − 1, 2^{m} − m − 1, 3].

7.1 construction

La matrice de parité du code H_{m} est

H_{m} = [β_{m}^{⊤}(1)|β_{m}^{⊤}(2)|...|β_{m}^{⊤}(2^{m} − 1)]

où β_{m}(i) est le vecteur binaire de longueur m représentant le nombre entier i. Exemple: β_{4}(5) = (0 1 0 1).

H_{3} = [ \begin{matrix}0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 \end{matrix} ]

7.2 distance minimale

La distance minimale de tels codes est 3. Supposons au contraire qu’elle soit 1 ou 2. Considérons d’abord un mot w de poids 1. Le produit wH^{⊤} = β_{m}(i) où i est la position du bit non-nul de w. Comme aucun β_{m}(i) n’est nul, il en découle qu’aucun w de poids 1 ne peut être un mot de code. Considérons similairement un mot w de poids 2. Le produit wH^{⊤} = β_{m}(i) ⊕ β_{m}(j) où i, j sont les positions des bits non-nuls de w. Comme aucun β_{m}(i) = β_{m}(j), il en découle que β_{m}(i) ⊕ β_{m}(j) ne peut être nul, et donc qu’aucun w de poids 2 ne peut être un mot de code. Par contre, le mot (1 1 1 \underbrace{0 0 0 ... 0}_{2^{m}−4}) de poids 3 est toujours un mot de

code car son syndrome est β_{m}(1) ⊕ β_{m}(2) ⊕ β_{m}(3) = 0.

On remarque que H_{m} est un code parfait puisque

M ∑_{i=0}^{(d−1)/2} \binom{n}{i}(q − 1)^{i} = 2^{2^{m}−m−1} ∑_{i=0}^{1} \binom{2^{m} − 1}{i}(1)^{i} = 2^{2^{m}−m−1}(1 + 2^{m} − 1) = 2^{2^{m}−1} = q^{n}.

7.3 correction d’erreurs

Un code de Hamming permet de corriger exactement une erreur. C’est de toute façon le mieux que l’on puisse s’attendre de ce code puisqu’il est parfait et que (d − 1)/2 = 1. Soit c un mot de code transmis et w = c + e le mot reçu, pour un certain mot d’erreur e de poids 1. Comme on le remarquait plus haut, le syndrome d’un mot de poids 1 est β_{m}(i) où i est la position du bit non-nul de e. Puisque w = c + e, w et e on le même syndrome car selui de c est nul. Il en découle que Syn(w) sera la représentation binaire de la position où l’erreur s’est produite. Pour corriger w il suffira donc d’inversion le bit à la position indiquée par le syndrome.

8 Théorie de l’information

La théorie de l’information formalise les notions d’incertitude et d’information de façon mathématique. On consère pour cela des variables aléatoires, que l’on nommera par des lettres majuscules ex: X, Y, Z, f(X), ... Rappelons qu’une variable aléatoire est un objet stochastique pouvant prendre des valeurs x_{1}, x_{2}, ..., x_{n} avec probabilités p_{1}, p_{2}, ..., p_{n} telles que ∑_{i=1}^{n} p_{i} = 1. On ne considère ici que les variables aléatoire prenantant qu’un nombre fini de valeurs. On dénotera P [X = x] ou P_{X}(x) la probabilité que la variable aléatoire X prenne la valeur x:

P_{X}(x) = P [X = x].

Rappelons que si l’on utilise deux ou plusieurs variables aléatoire (X, Y) distribuées selon P_{X,Y}, la probabilité marginale par rapport à X est donnée par

P_{X}(x) = ∑_{y} P_{X,Y} (x, y)

et que la probabilité conditionnelle de X par rapport à Y est donnée par

P [X = x|Y = y] = P_{X|Y =y}(x) = P_{X,Y} (x, y)/P_{Y} (y).

Afin d’alléger la notation on remplacera les expressions du type 1 − ϵ par ϵ̄ pour une valeur rélle ϵ et l’on définit la fonction h par:

h(ϵ) = −ϵ lg ϵ − ϵ̄lg ϵ̄, avec ϵ̄ = 1 − ϵ.

8.1 Modèles d’erreurs

On considere principalement deux modèles d’erreurs: le canal binaire symétrique et le canal d’effacement. Le premier (BS_{ϵ}) est un canal où une valeur de sortie est toujours disponible, mais elle sera erronnée avec probabilité ϵ.

\begin{matrix}P [BS_{ϵ}(x) = x] = ϵ̄ \\ P [BS_{ϵ}(x) ≠ x] = ϵ \end{matrix}

Dans le cas binaire, puisqu’il n’y a que deux possibilités pour la valeur de x on aura P [BS_{ϵ}(x) = x̄] = P [BS_{ϵ}(x) ≠ x]. Dans un cas non-binaire, sur un corps F_{q} pour q > 2 par exemple, on suppose une distribution uniforme des résultats erronnés, c’est à dire que P [BS_{ϵ}(x) ≠ x] est partagée également entre les y ≠ x:

\begin{matrix}P [BS_{ϵ}(x) = x] = ϵ̄ \\ P [BS_{ϵ}(x) = y] = \frac{ϵ}{q−1} & pour y ≠ x \end{matrix}

Le second canal ne donne jamais de résultat faux, mais parfois aucun résultat n’est obtenu en sortie:

\begin{matrix}P [EF_{ϵ}(x) = x] = ϵ̄ \\ P [EF_{ϵ}(x) = ε] = ϵ \end{matrix}

Généralisation Si l’on généralise ces deux canaux pour transmettre des mots de n symboles de façon indépendante par l’intermédiaire des canaux définis précédemment on obtient le canal binaire symétrique d’ordre n (BS_{ϵ}^{n}) et le canal d’effacement d’ordre n (EF_{ϵ}^{n}):

P [BS_{ϵ}^{n}(w) = w′] = ϵ̄^{n−Δ(w,w′)} (\frac{ϵ}{q − 1})^{Δ(w,w′)}

P [EF_{ϵ}^{n}(w) = w′] = ϵ̄^{n−ε(w′)}ϵ^{ε(w′)}

où ε(w′) = #{i : w′_{i} = ε}.

8.2 Entropie

H(p_{1}, p_{2}, ..., p_{n}) = − ∑_{i=1}^{n} p_{i} lg p_{i}

propriétés

1. H(p_{1}, p_{2}, ..., p_{n}) est maximum pour p_{1} = p_{2} = ... = p_{n} = 1/n,

2. H(p_{1}, p_{2}, ..., p_{n}) = H(p_{π(1)}, p_{π(2)}, ..., p_{π(n)}) pour toute permutation π,

3. H(p_{1}, p_{2}, ..., p_{n}) ≥ 0 et H(p_{1}, p_{2}, ..., p_{n}) = 0 exactement si un p_{i} = 1,

4. H(p_{1}, p_{2}, ..., p_{n}, 0) = H(p_{1}, p_{2}, ..., p_{n}),

5. H(\frac{1}{n}, \frac{1}{n}, ..., \frac{1}{n}) ≤ H(\frac{1}{n+1}, \frac{1}{n+1}, ..., \frac{1}{n+1}, \frac{1}{n+1}),

6. H est une fonction continue,

7. H(\frac{1}{mn}, \frac{1}{mn}, ..., \frac{1}{mn}) = H(\frac{1}{m}, \frac{1}{m}, ..., \frac{1}{m}) + H(\frac{1}{n}, \frac{1}{n}, ..., \frac{1}{n}),

8. H(p_{1}, p_{2}, ..., p_{m}, q_{1}, q_{2}, ...q_{n}) = H(p, q) + pH(\frac{p_{1}}{p} , \frac{p_{2}}{p} , ..., \frac{p_{m}}{p}) + qH(\frac{q_{1}}{q} , \frac{q_{2}}{q} , ..., \frac{q_{n}}{q}) où p = ∑ p_{i} et q = ∑ q_{i}.

Theorem 11. Soit une fonction H′(p_{1}, p_{2}, ..., p_{n}) satisfaisant les propriétés 1. à 8. ci-haut. Il existe toujours une constante positive λ telle que

H′(p_{1}, p_{2}, ..., p_{n}) = λH(p_{1}, p_{2}, ..., p_{n}).

Theorem 12.

H(p_{1}, p_{2}, ..., p_{n}) ≤ lg n.

Theorem 13. Pour toutes distribution de probabilité q_{1}, q_{2}, ..., q_{n} on a

− ∑_{i=1}^{n} p_{i} lg q_{i} ≤ − ∑_{i=1}^{n} p_{i} lg p_{i}.

On définit enfin l’entropie d’une variable aléatoire X pouvant prendre les valeurs x_{1}, x_{2}, ..., x_{n} par

H(X) = H(P_{X}(x_{1}), P_{X}(x_{2}), ..., P_{X}(x_{n})) = − ∑_{x} P_{X}(x) lg P_{X}(x)

Theorem 14.

H(X, Y) ≤ H(X) + H(Y)

avec égalité exactement si X et Y sont indépendantes.

Theorem 15.

H(X_{1}, X_{2}, ..., X_{n}) ≤ H(X_{1}) + H(X_{2}) + ...H(X_{n})

avec égalité exactement si X_{1}, X_{2}, ..., X_{n} sont mutuellement indépendantes.

8.3 Entropie conditionelle

H(X|Y) = ∑_{y} P_{Y} (y)H(X|Y = y) = − ∑_{y} ∑_{x} P_{Y} (y)P_{X|Y =y}(x) lg P_{X|Y =y}(x)

Theorem 16.

H(X|Y) = 0

exactement si X = f(Y) pour une certaine fonction f et

H(X|Y) = H(X)

lorsque X et Y sont indépendantes.

Theorem 17.

H(X, Y) = H(Y) + H(X|Y)

et donc

H(X|Y) ≤ H(X)

avec égalité lorsque X et Y sont indépendantes.

IFT6170 Claude Crépeau. 17

8.4 Information mutuelle

I(X; Y) = H(X) − H(X|Y)

Theorem 18.

I(X; Y) = I(Y; X).

Exemple:

option vs vote  OUI NON ind.
séparation  30% 60% 10%
offre de partenariat  39% 46% 15%
certitude de partenariat 54% 35% 11%

Fig. 3. Table de P [V OT E = vote|OP T ION = option]

P [OP T ION = “séparation”] = 1/4 P [OP T ION = “offre de partenariat”] = 1/2

P [OP T ION = “certitude de partenariat”] = 1/4

P [V OT E = “OUI”] = 40.5%
P [V OT E = “NON”] = 46.75%
P [V OT E = “ind.”] = 12.75%

H(V OT E) = −.405 lg .405 − .4675 lg .4675 − .1275 lg .1275 = 1.4198 H(OP T ION) = −.25 lg .25 − .5 lg .5 − .25 lg .25 = 1.5

H(V OT E|OP T ION = “séparation”) = −.3 lg .3 − .6 lg .6 − .1 lg .1 = 1.2955 H(V OT E|OP T ION = “offre de partenariat”) = −.39 lg .39 − .46 lg .46 − .15 lg .15 = 1.4557

H(V OT E|OP T ION = “certitude de partenariat”) = −.54 lg .54 − .35 lg .35 − .11 lg .11 = 1.3604

H(V OT E|OP T ION) = \frac{1.2955}{4} + \frac{1.4557}{2} + \frac{1.3604}{4} = 1.3918

I(V OT E; OP T ION) = H(V OT E) − H(V OT E|OP T ION) = 1.4198 − 1.3918 = 0.0280 8.5 Capacité d’un canal

Un canal de communication σ est une fonction stochastique qui associe à chaque élément x de son domaine une variable aléatoire σ(x). Il est naturel de se demander combien d’information un canal σ transmet au sujet d’une variable aléatoire X qui lui est fournie comme donnée. Cette valeur est I(X; σ(X)). Il est clair que plus cette valeur est grande, plus le canal communique beaucoup sur la source. On définit la capacité d’un canal σ par la quantité suprémum d’information qu’il peut transmettre pour toutes les variables aléatoires que l’on pourrait lui fournir en entrée:

C(σ) = sup_{X} I(X; σ(X)).

Theorem 19.

C(BS_{ϵ}) = 1 − h(ϵ).

Theorem 20.

C(BS_{ϵ}^{n}) = nC(BS_{ϵ}) = n − nh(ϵ).

8.6 Objectifs de la théorie des codes

Pour tout code C on définit la probabilité d’erreur du code par

e(C) = \frac{1}{M} ∑_{i=1}^{M} P [erreur|c_{i} transmis].

ê(C) = max_{i=1}^{M} P [erreur|c_{i} transmis].

La théorie des codes a pour but de construire des familles de codes {C_{n}}_{n>0} de paramètres (n, M_{n}, d_{n}) permettant de transmettre des informations au meilleur coût possible en obtenant le moins d’erreur possible à travers un BS_{ϵ}. On voudrait optimiser deux paramètres à la fois R_{n} = lg M_{n}/n et ê(C_{n}). En fait, on cherche le meilleur R pour lequel il existe une constante positive α < 1 telle que

lim_{n→∞} R_{n} = R et ê(C_{n}) < α^{n}.

8.7 Théorèmes de Shannon

Theorem 21. Soient ϵ et δ, tels que 0 < δ, ϵ < 1 et R tel que 0 < R < C(BS_{ϵ}). Pour tout ensemble {M_{n}}_{n>0}, tels que 0 < M_{n} ≤ 2^{Rn}, il existe un entier n_{0} et une famille de codes {C_{n}}_{n>n_{0}} de paramètres (n, M_{n}, d_{n}) tels que ê(C_{n}) < δ pour tout n > n_{0}.

Theorem 22. Soit ϵ, tel que 0 < ϵ < 1 et soit R tel que 0 < R < C(BS_{ϵ}). Il existe un entier n_{0}, une constante positive α < 1 et une famille infinie de codes {C_{n}}_{n>n_{0}} de paramètres (n, M_{n}, d_{n}) tels que

M_{n} = ⌊2^{Rn}⌋ et ê(C_{n}) < α^{n}

pour tout n > n_{0}.

8.8 Outils utiles

Loi des grands nombres de Bernstein

Theorem 23. Soient X_{1}, X_{2}, ..., X_{n} des variables aléatoires de Bernoulli indépendantes telles que P [X_{i} = 1] = ϵ pour 1 ≤ i ≤ n. Pour tout δ, 0 < δ ≤ ϵ(1 − ϵ) on a

P [|∑_{i=1}^{n} \frac{X_{i}}{n} − ϵ| ≥ δ] ≤ 2e^{−nδ^{2}}.

Approximation d’une binomiale

Theorem 24.

\frac{2^{h(λ)n}}{\sqrt{8nλ(1 − λ)}} ≤ \binom{n}{λn} ≤ \frac{2^{h(λ)n}}{\sqrt{2πnλ(1 − λ)}} .

Approximation de la somme des binomiales

Theorem 25. ∑_{i=0}^{λn} \binom{n}{i} ≤ 2^{h(λ)n}.

Preuve:

1 = [λ + (1 − λ)]^{n} ≥ ∑_{i=0}^{λn} \binom{n}{i}λ^{i}(1 − λ)^{n−i}

≥ (1 − λ)^{n} ∑_{i=0}^{λn} \binom{n}{i} (\frac{λ}{1 − λ})^{λn}

= λ^{λn}(1 − λ)^{n(1−λ)} ∑_{i=0}^{λn} \binom{n}{i}

Theorem 26 Elias. Soit ϵ, tel que 0 < ϵ < 1 et soit R tel que 0 < R < C(BS_{ϵ}). Il existe un entier n_{0}, une constante positive α < 1 et une famille infinie de codes linéaires {C_{n}}_{n>n_{0}} de paramètres [n, k_{n}, d_{n}] tels que

lim_{n→∞} \frac{k_{n}}{n} = R et ê(C_{n}) < α^{n}

pour tout n > n_{0}.

30 IFT6170 Claude Crépeau

13 Codes Classiques de Goppa

IFT6170 Claude Crépeau. 37

18 Codes Géométriques

19 Graphes et codes

19.1 Graphes Expandeurs 19.2 Codes expandeurs 19.3 Codes superconcentrateurs

20 Applications à la cryptographie

20.1 partages de secrets 20.2 Cryptosystème de McEliece 20.3 réductions entres protocoles 20.4 Winer wire-tap channel 20.5 Extension de Maurer et BBCM 20.6 Protocoles cryptographiques à partir d’un canal bruyant

21 Codes quantiques

IFT6170 Devoir 1

à rendre au début du cours le mercredi 1 octobre 1997

Polynôme Irréductible [4 points]

Considérez l’ensemble des nombres modulo 17 étiquetés ainsi:

{0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F,G},

les symboles “A,B,C,D,E,F,G” repésentant les nombres 10,11,12,13,14,15,16. On utilise sur ces nombres les opérations d’addition, soustraction et multiplication modulo 17. Par exemple F + 1 ≡ G (mod 17) et 3 ∗ A ≡ D (mod 17). On considère les polynômes sur F_{17} comme une suite finie de symboles parmis l’ensemble ci-haut. Par exemple (1 0 1 0 0 0 A B C D E F G) correspond à

1x^{12} + 1x^{10} + Ax^{6} + Bx^{5} + Cx^{4} + Dx^{3} + Ex^{2} + F x + G.

Donnez un polynôme irréductible sur F_{17} de degré 23 contenant votre date de naissance de façon consécutive dans sa représentation ainsi qu’une preuve de ce fait. Par exemple pour 17-02-62

(1 7 0 2 6 2 0 0 0 0 0 0 0 0 0 0 0 A 5 4 2 1 F 7)

pourrait être un tel polynôme contenant ma date de naissance. ( Je n’ai pas vérifié s’il est irréductible. )

Donnez également un élément primitif du corps fini engendré par votre polynôme. Pour vous aider, sachez que 17^{23} −1 = 2^{4} ∗47∗26552618219228090162977481. Vous pouvez utiliser les moyens (ordinateurs, logiciels, etc) que vous voudrez pour obtenir votre réponse.

Dual des codes de Hamming [4 points]

Les codes de Hamming forment une famille infinie {H_{m}}_{m>0} de codes linéaires binaires ayant les paramètres [2^{m}−1, 2^{m}−m−1, 3]. Donnez les paramètres [n_{m}, k_{m}, d_{m}] des codes {H_{m}^{⊤}}_{m>0} duaux des codes de Hamming en fonction de m. Ces codes sont-ils parfaits? Prouvez vos réponses.

Codes ISBN [4+1 points]

Le code ISBN que l’on trouve sur les livres est un code linéaire sur F_{11} où l’on utilise l’alphabet

{0,1,2,3,4,5,6,7,8,9,X},

le symbole “X” repésentant le nombre 10. Les paramètres de ce code sont [10, k, d]. Utilisez un certain nombre de livres (donnez les titres et numéro ISBN des livres utilisés) afin de déterminer une matrice génératrice pour ce code, sous forme systématique. Donnez les valeurs de k et d pour ce code. Démontrez finalement que ce code a la propriété supplémentaire que si l’on permute deux symboles différents d’un mot de code, le mot résultant n’est plus un mot de code. Justifiez vos réponses.

Un point supplémentaire à celui ou celle qui trouvera un plus petit ensemble de livres (je veux les titres et les codes ISBN) dont les codes ISBN sont linéairement dépendants...

Canaux de transmission [total 4 points]

–canal majorité [1.5 points]

Considérez le canal suivant:

MAJ_{ϵ}^{k}(x) = maj \{\overbrace{BS_{ϵ}(x), BS_{ϵ}(x), ..., BS_{ϵ}(x)}^{2k−1}\}.

C’est-à-dire que MAJ_{ϵ}^{k}(x) retourne le bit majoritaire parmis 2k − 1 exécutions indépendantes de BS_{ϵ}(x). Trouvez un ϵ_{k} tel que

MAJ_{ϵ}^{k}(x) = BS_{ϵ_{k}}(x).

Montrez que

lim_{k→∞} ϵ_{k} = 0.

–canal xor [1.5 points]

Considérez le canal suivant:

XOR_{ϵ}^{k}(x) = \overbrace{BS_{ϵ}(x) ⊕ BS_{ϵ}(x) ⊕ ... ⊕ BS_{ϵ}(x)}^{2k−1} .

C’est-à-dire que XOR_{ϵ}^{k}(x) retourne le ou–exclusif de 2k − 1 exécutions indépendantes de BS_{ϵ}(x). Trouvez un ϵ_{k} tel que

XOR_{ϵ}^{k}(x) = BS_{ϵ_{k}}(x).

Montrez que

lim_{k→∞} ϵ_{k} = 1/2.

–canal mixte [1 point]

Soient U = BS_{ϵ}(x) et V = BS_{ϵ}(x) deux échantillons indépendants obtenus à travers un canal bruyant de probabilité d’erreur ϵ. Considérez le canal suivant:

MIX_{ϵ}(x) = \{ \begin{matrix}b & si U = V = b \\ ε & si U ≠ V \end{matrix} .

C’est-à-dire que MIX_{ϵ}(x) retourne le bit commun obtenu de deux exécutions indépendantes de BS_{ϵ}(x), mais la chaîne nulle si ces deux exécutions ne donne pas la même réponse. Trouvez des α, β tels que

MIX_{ϵ}(x) = EF_{α}(BS_{β}(x)).

44 IFT6170 Claude Crépeau This article was processed using the L^{A}TEX macro package with LLNCS style