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.

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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 9.1 Borne supérieure de Singleton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 9.2 Borne inférieure de Varshamov-Gilbert . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 9.3 Borne supérieure de Hamming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 9.4 Borne supérieure de Plotkin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 9.5 Borne supérieure de McEliece-Rodemich-Rumsey-Welch . . . . . . . . . . . . . . . . . . . . . 20

10 NP-complétude de problèmes sur les codes . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 10.1 NP-complet ou NP-ardu? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 10.2 correction d’erreurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 10.3 NP-complétude de PMCS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 10.4 poids des mots de code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 10.5 NP-complétude de PC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 10.6 Équivalence de codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

11 Codes de Hadamard . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 11.1 Matrices de Hadamard . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 11.2 construction de Sylvester . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 11.3 construction de Paley . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 11.4 codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

12 Codes cycliques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 12.1 polynome générateur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 12.2 polynome de parité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 12.3 code dual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 12.4 facteurs de x^{n} − 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 12.5 cosets cyclotomiques et polynômes minimaux . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 12.6 borne de BCH . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

13 Codes BCH . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 13.1 Distance minimale effective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 13.2 Symboles d’information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 13.3 Les codes BCH sont mauvais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

14 Codes Reed-Solomon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 14.1 definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 14.2 codage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 14.3 codes binaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 14.4 les codes RS “binarisés” sont mauvais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 14.5 correction de paquets d’erreurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

15 Codes Concaténés et Justesen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 15.1 concaténation de codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 15.2 code interne aléatoire ou maximal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 15.3 codes multiplicatifs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 15.4 les Codes multiplicatifs sont bons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 15.5 codes de Justesen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 15.6 décodage des codes concaténés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

décodage naïf . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 décodage de Block-Zyablov . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

15.7 codes de Forney . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

16 Codes Reed-Solomon généralisés et Alternants . . . . . . . . . . . . . . . . . . . . . . . . . 34 16.1 le dual d’un code RSG est RSG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 16.2 décodage des codes Alternants: algorithme de Berlekamp . . . . . . . . . . . . . . . . . . . . 34 16.3 les Codes Alternants sont bons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

17 Codes Classiques de Goppa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

18 Codes Géométriques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

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

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

21 Codes quantiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

1 Introduction

La théorie des codes correcteurs étudie les façons de transmettre, sur un canal imparfait, des messages avec grande fiabilité. Soit A un ensemble de M mots à transmettre au moyen d’un canal imparfait. Un code C associé à A est un ensemble de M mots, nommés mots de code, sur un ensemble B. Dans la plupart des cas A sera l’ensemble des mots de k bits, A = {0, 1}^{k}, et B sera l’ensemble des mots de n bits, B = {0, 1}^{n}, mais dans certains cas il en sera autrement. On dénote les caratéristiques d’un code de M mots sur {0, 1}^{n} au moyen des trois paramètres (n, M, d) 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. En général, un code est défini au moyen d’une application d’encodage ϕ de A dans B, ayant C pour image. La fonction ϕ^{−1} de C dans A inverse de la fonction d’encodage ϕ, est dite de décodage.

Exemple Considérons le code suivant sur {0, 1}^{6} associé à l’ensemble {0, 1}^{2}:

C = {000000, 010101, 101010, 111111}

Il s’agit d’un code (6, 4, 3), puisque d = 3 comme le montre cette liste:

Δ (000000, 010101) = 3
Δ (000000, 101010) = 3
Δ (000000, 111111) = 6
Δ (010101, 101010) = 6
Δ (010101, 111111) = 3
Δ (101010, 111111) = 3.

Dans ce cas on peut définir les fonctions d’encodage ϕ : {0, 1}^{2} → {0, 1}^{6} et de décodage ϕ^{−1} : C → {0, 1}^{2} par

ϕ(x) = xxx,
ϕ^{−1}(xxx) = x.

Le sens des fonctions d’encodage et de décodage est que lorsqu’un mot x de A doit être transmis, le mot ϕ(x) sera transmis à sa place. Quand un mot c de C est reçu, on lui associe le mot ϕ^{−1}(c) de A. L’avantage de transmettre c plutot que x est que tous les mots de A sont des mots possibles et donc si x est reçu de façon erronée, un autre mot correct sera alors reçu. Au contraire, si c est reçu de façon erronée, il est probable que le mot ne sera pas dans C et sera alors identifié comme une erreur.

On nomme détection d’erreurs le processus par lequel on identifie qu’un mot reçu n’appartient pas à l’ensemble C. Dans l’exemple ci-haut, on détecte une erreur si un mot reçu n’a pas la forme xxx. On nomme enfin correction d’erreurs le processus par lequel le mot de code le plus probable est substitué à un mot reçu de façon erronée. On entend par “plus probable” le mot de code ayant la plus grande probabilité d’avoir produit le mot erroné reçu. Cette valeur dépendra en général du modèle d’erreur considéré. Dans la plupart des cas qui nous intéressent, le mot de code le plus probable est le plus proche au sens de Hamming.

1.1 Objectifs

Les objectifs premier de la théorie des codes est de trouver des constructions efficaces permettant d’obtenir des codes pour lesquels on sais réaliser de façon efficace les opération suivantes:

– encodage

– décodage

– détection d’erreurs

– correction d’erreurs.

De plus, la théorie des codes s’intéresse à des considération économiques relatives au taux d’expansion des mots transmis (k/n) par rapport au nombres d’erreurs qui peuvent être effifacement détectées et corrigées.

1.2 Codes linéaires

La plupart des codes que nous étudirons, sont de codes linéaires. Un code binaire est linéaire s’il satisfait la propriété de linéarité

c_{1}, c_{2} ∈ C ⇒ c_{1} ⊕ c_{2} ∈ C.

Il est à noter qu’il en découle qu’un code linéaire sur {0, 1}^{n} contient toujours le mot 0^{n}. De plus, la distance minimale du code est donnée par l’expression suivante 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.

Le code de l’exemple ci-haut est linéaire car

000000 ⊕ 010101 = 101010 ⊕ 111111 = 010101
000000 ⊕ 101010 = 010101 ⊕ 111111 = 101010
000000 ⊕ 111111 = 010101 ⊕ 101010 = 111111.

2 théorie des nombres et corps finis

2.1 définitions

a|b ⟺ ∃k ∈ Z [b = ak] a ≡ b (mod n) ⟺ n|(a − b)

b mod n ⟺ min{a > 0 : a ≡ b (mod n)}

b div n ⟺ \frac{b − (b mod n)}{n}

g = pgcd(a, b) ⟺ g|a, g|b et [g′|a, g′|b ⇒ g′|g]

2.2 opérations de base efficaces

Pour les opérations de base +, −, ×, mod, div il suffit d’utiliser les algorithmes ordinaires appris à l’école primaire en utilisant la règle suivante pour ne pas travailler inutilement:

a \{ \begin{matrix}+ \\ − \\ × \end{matrix} \} b mod n = ((a mod n) \{ \begin{matrix}+ \\ − \\ × \end{matrix} \} (b mod n)) mod n

Les algorithmes ordinaires sont décrit en détail dans Knuth (Vol 2). Pour les nombres très grands on peut utiliser des méthodes plus rapide pour ×. Pour ceci consulter le livre de Brassard-Bratley.

2.3 calcul d’une exponentiation rapide

L’idée de cet algorithme est de préserver à chaque itération la valeur de l’expression xa^{e} mod n tout en réduisant la valeur courante de e.

Algorithme 2.1 ( a^{e} mod n )

1: x ← 1,

2: WHILE e > 0 DO

3: IF e est impair THEN x ← ax mod n, 4: a ← a^{2} mod n, e ← e div 2, 5: ENDWHILE 6: RETURN x.

2.4 calcul du PGCD et d’inverses

L’idée de cet algorithme est de préserver à chaque itération les deux relations g = ax+by et g′ = ax′+by′tout en réduisant la valeur courante de g. À la fin de l’algorithme, la valeur de g est le pgcd(a, b). Du même coup la valeur finale de x est telle que ax ≡ g (mod b). Quand g = 1, on en déduit que x est l’inverse multiplicatif de a modulo b.

Algorithme 2.2 ( Euclide pgcd(a, b) )

1: g ← a, g′ ← b, x ← 1, y ← 0, x′ ← 0, y′ ← 1, 2: WHILE g′ > 0 DO 3: k ← g div g′, 4: (ĝ, x̂, ŷ) ← (g, x, y) − k(g′, x′, y′), 5: (g, x, y) ← (g′, x′, y′), 6: (g′, x′, y′) ← (ĝ, x̂, ŷ), 7: ENDWHILE 8: RETURN (g, x, y).

2.5 Nombres premiers

Si l’on désire vérifier la primalité d’un nombre n il est possible d’utiliserl’algorithme probabiliste de Miller-Rabin. Celui-ci repose sur la notion de nombres “pseudo-premier” base a.

Algorithme 2.3 ( pseudo(a, n) )

1: IF pgcd(a, n) ≠ 1 THEN RETURN “composé”,

2: Soient t un nombre impair et s un entier positif tels que n − 1 = t2^{s} 3: x ← a^{t} mod n, y ← 1, 4: FOR i ← 1 TO s 5: IF x = 1 AND y ≠ ±1 THEN RETURN “composé”, 6: y ← x, x ← x^{2} mod n, 7: ENDFOR 8: RETURN “pseudo”.

Rabin a montré que si n est premier, alors pseudo(a, n) retourne “pseudo” pour tous les a, 0 < a < n. Il a aussi montré que si n est composé, alors pseudo(a, n) retourne “composé” pour au moins 3n/4 valeurs de a, 0 < a < n.

Algorithme 2.4 ( Miller-Rabin prem(n, k) )

1: FOR i ← 1 TO k

2: choisir un élément a au hasard, 0 < a < n,

3: IF pseudo(a, n) = “composé” THEN RETURN “composé”, 4: ENDFOR 5: RETURN “premier”.

On en déduit facilement que si n est premier, alors prem(n, k) retourne toujours “premier” et que si n est composé, alors prem(n, k) retourne “composé” avec probabilité au moins 1 − (1/4)^{k}. Donc quand l’algo prem retourne “composé”, il dit toujours la vérité. Par contre, quand il retourne “premier” il reste une très faible probabilité qu’il se soit trompé.

Si l’on veut obtenir un nombre premier au hasard, on utilise le théorèmes suivant pour estimer le nombre de fois moyen qu’il nous faudra utiliser l’algorithme 2.4. Soit π(n) = #{a : 0 < a ≤ n et a est premier}.

Theorem 1. lim_{n→∞} \frac{π(n) log n}{n} = 1

2.6 corps premiers

Soit p un nombre premier. Les nombres 0, 1, 2, ..., p − 1 munis des opérations + mod p et × mod p forment un coprs de p éléments dénoté F_{p}.

– contient un élément neutre additif (0)

– chaque élément e possède un inverse additif −e

– contient un élément neutre multiplicatif (1)

– chaque élément non-nul e possède un inverse multiplicatif e^{−1}

– associativité

– commutativité

– distributivité

Exemples F_{2} = ({0, 1}, ⊕, ∧). F_{5} = ({0, 1, 2, 3, 4}, +, ×) définis par

+ 0 1 2 3 4 0 0 1 2 3 4 1 1 2 3 4 0 2 2 3 4 0 1 3 3 4 0 1 2 4 4 0 1 2 3  \begin{matrix}× & 0 & 1 & 2 & 3 & 4 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 2 & 3 & 4 \\ 2 & 0 & 2 & 4 & 1 & 3 \\ 3 & 0 & 3 & 1 & 4 & 2 \\ 4 & 0 & 4 & 3 & 2 & 1 \end{matrix}

2.7 polynômes sur un corps

Un polynômes sur F_{p} est spécifié par une suite finie (a_{n}, a_{n−1}, ..., a_{1}, a_{0}) d’éléments de F_{p}, avec a_{n} ≠ 0. Le nombre n est le degré du polynôme. On a sur les polynômes des opérations +, −, × analogues à celles sur les entiers.

Les sommes et différences se font composantes par composantes en utilisant alors le + et le − du corps considéré.

Les produits se font en sommant tous les produits croisés donnant un certain exposant. Exemple:

(x^{4} + x + 1) × (x^{3} + x^{2} + x) = x^{4} × (x^{3} + x^{2} + x) + x × (x^{3} + x^{2} + x) + 1 × (x^{3} + x^{2} + x)
= (x^{7} + x^{6} + x^{5}) + (x^{4} + x^{3} + x^{2}+) + (x^{3} + x^{2} + x)
= x^{7} + x^{6} + x^{5} + x^{4} + (1 + 1)x^{3} + (1 + 1)x^{2} + x
= x^{7} + x^{6} + x^{5} + x^{4} + x

De même les opérations g(x) mod h(x) et g(x) div h(x) sont définies comme les polynômes r(x) et q(x) tels que g(x) = q(x)h(x) + r(x) avec deg(r) < deg(h). On les obtient en faisant la division formelle de g(x) par h(x) semblable à celle sur les entiers. Exemple:

x^{7} + x^{6} + x^{5} + x^{4} + x = (x^{2}) × (x^{5} + x^{2} + 1) + (x^{6} + x^{5} + x^{2} + x)
= (x^{2} + x) × (x^{5} + x^{2} + 1) + (x^{5} + x^{3} + x^{2})
= (x^{2} + x + 1) × (x^{5} + x^{2} + 1) + (x^{3} + 1)

donc

(x^{7} + x^{6} + x^{5} + x^{4} + x) mod (x^{5} + x^{2} + 1) = x^{3} + 1
(x^{7} + x^{6} + x^{5} + x^{4} + x) div (x^{5} + x^{2} + 1) = x^{2} + x + 1

Les exponentiations pour des puissances entières modulo un certain polynôme peuvent s’effectuer au moyen de l’algorithme 2.1 et les pgcd de deux polynomes ou les inverses multiplicatifs peuvent être calculés grâce à l’algorithme 2.2.

2.8 polynômes irréductibles

Un polynôme g(x) est irréductible s’il ne peut s’écrire comme le produit de deux polynômes h(x), k(x) de degrés inférieurs. On utilise le théorème suivant pour trouver de tels polynômes.

Theorem 2. Soient l_{1}, l_{2}, ..., l_{k} les facteurs premiers de n et m_{i} = n/l_{i} pour 1 ≤ i ≤ k. Un polynôme g(x) de degré n est irréductible sur F_{p} si et seulement si

• g(x)|x^{p^{n}} − x

• pgcd(g(x), x^{p^{m_{i}}} − x) = 1 pour 1 ≤ i ≤ k Algorithme 2.5 ( Rabin Irr(p, n) )

1: soient l_{1}, l_{2}, ..., l_{k} les facteurs premiers de n et m_{i} = n/l_{i} pour 1 ≤ i ≤ k, 2: REPEAT 3: choisir un polynôme h(x) de degré n − 1 sur F_{p} au hasard, g(x) ← x^{n} + h(x), 4: UNTIL x^{p^{n}} mod g(x) = x et pgcd(g(x), x^{p^{m_{i}}} − x) = 1 pour 1 ≤ i ≤ k, 5: RETURN g.

On utilise le théorème suivant pour estimer le nombre d’itérations moyen de l’algorithme 2.5.

Theorem 3. Soit m(n) le nombre de polynômes irréductibles g(x) de degré n de la forme g(x) = x^{n} + h(x) où h(x) est un polynôme de degré n − 1. On a

\frac{p^{n}}{2n} ≤ \frac{p^{n} − p^{n/2} log n}{n} ≤ m(n) ≤ \frac{p^{n}}{n} .

F_{2}  F_{3}  F_{5}  F_{7}
x + 1  x^{9} + x^{4} + 1  x + 1  x + 1  x + 1
x^{2} + x + 1  x^{10} + x^{3} + 1 x^{2} + x + 2  x^{2} + x + 2 x^{2} + x + 3
x^{3} + x + 1  x^{11} + x^{2} + 1 x^{3} + 2x + 1  x^{3} + 3x + 2 x^{3} + 3x + 2
x^{4} + x + 1 x^{12} + x^{6} + x^{4} + x + 1 x^{4} + x + 2 x^{4} + x^{2} + x + 2
x^{5} + x^{2} + 1 x^{13} + x^{4} + x^{3} + x + 1 x^{5} + 2x + 1
x^{6} + x + 1 x^{14} + x^{10} + x^{6} + x + 1 x^{6} + x + 2
x^{7} + x^{3} + 1  x^{15} + x + 1
x^{8} + x^{4} + x^{3} + x^{2} + 1 x^{16} + x^{12} + x^{3} + x + 1

Fig. 1. polynômes irréductibles (primitifs) sur F_{2} et irréductibles sur F_{3},F_{5},F_{7}..

2.9 Corps quelconques

Soit p un nombre premier et n un entier positif. On construit le corps à p^{n} éléments à partir du corps à p éléments.

• Les éléments de F_{p^{n}} ont la forme e_{1}e_{2}...e_{n} où e_{i} est élément de F_{p}.

• La somme de deux éléments de F_{p^{n}} est définie par

e_{1}e_{2}...e_{n} + e′_{1}e′_{2}...e′_{n} = ê_{1}ê_{2}...ê_{n}

tels que ê_{i} = e_{i} + e′_{i} pour 1 ≤ i ≤ n.

• Le produit de deux éléments de F_{p^{n}} est défini par

e_{1}e_{2}...e_{n} × e′_{1}e′_{2}...e′_{n} = ê_{1}ê_{2}...ê_{n}

tels que

(ê_{1}x^{n−1} + ê_{2}x^{n−2} + ... + ê_{n}) = (e_{1}x^{n−1} + e_{2}x^{n−2} + ... + e_{n}) × (e′_{1}x^{n−1} + e′_{2}x^{n−2} + ... + e′_{n}) mod r(x)

avec r(x) un polynôme de degré n irréductible sur F_{p}.

Exemples calculs sur F_{2^{5}} 10011 + 01110 = (1 + 0)(0 + 1)(0 + 1)(1 + 1)(1 + 0) = 11101

10011 × 01110 = 01001 car (x^{4} + x + 1) × (x^{3} + x^{2} + x) mod (x^{5} + x^{2} + 1) = x^{3} + 1.

+ 000 001 010 011 100 101 110 111 000 000 001 010 011 100 101 110 111 001 001 000 011 010 101 100 111 110 010 010 011 000 001 110 111 100 101 011 011 010 001 000 111 110 101 100 100 100 101 110 111 000 001 010 011 101 101 100 111 110 001 000 011 010 110 110 111 100 101 010 011 000 001 111 111 110 101 100 011 010 001 000  \begin{matrix}× & 000 & 001 & 010 & 011 & 100 & 101 & 110 & 111 \\ 000 & 000 & 000 & 000 & 000 & 000 & 000 & 000 & 000 \\ 001 & 000 & 001 & 010 & 011 & 100 & 101 & 110 & 111 \\ 010 & 000 & 010 & 100 & 110 & 011 & 001 & 111 & 101 \\ 011 & 000 & 011 & 110 & 101 & 111 & 100 & 001 & 010 \\ 100 & 000 & 100 & 011 & 111 & 110 & 010 & 101 & 001 \\ 101 & 000 & 101 & 001 & 100 & 010 & 111 & 011 & 110 \\ 110 & 000 & 110 & 111 & 001 & 101 & 011 & 010 & 100 \\ 111 & 000 & 111 & 101 & 010 & 001 & 110 & 100 & 011 \end{matrix}

Fig. 2. opérations de F_{2^{3}}

2.10 Éléments primitifs

Il existe sur tout corps fini F_{q} un élément primitif, c’est-à-dire un élément g tel que g^{1}, g^{2}, ..., g^{q−1} énumère les q − 1 éléments non-nuls du corps. On utilise le théorème suivant pour trouver un élément primitif sur F_{q}.

Theorem 4. Soient l_{1}, l_{2}, ..., l_{k} les facteurs premiers de q − 1 et m_{i} = (q − 1)/l_{i} pour 1 ≤ i ≤ k. Un élément g est primitif sur F_{q} si et seulement si

• g^{q−1} = 1

• g^{m_{i}} ≠ 1 pour 1 ≤ i ≤ k

Algorithme 2.6 ( P rim(q) )

1: soient l_{1}, l_{2}, ..., l_{k} les facteurs premiers de q − 1 et m_{i} = \frac{q−1}{l_{i}} pour 1 ≤ i ≤ k, 2: REPEAT 3: choisir un élément non-nul g de F_{q} au hasard, 4: UNTIL g^{m_{i}} ≠ 1 pour 1 ≤ i ≤ k, 5: RETURN g.

On utilise les théorèmes suivant pour estimer le nombre d’itérations moyen de l’algorithme 2.6. Soit ϕ(n) = #{a : 0 < a < n et pgcd(a, n) = 1}.

Theorem 5. #{g : g est un élément primitif de F_{q}} = ϕ(q − 1).

Theorem 6. lim inf_{n→∞} \frac{ϕ(n) log log n}{n} = e^{−γ}

Exemples: 2 est un élément primitif sur F_{5} car {2, 2^{2}, 2^{3}, 2^{4}} = {2, 4, 3, 1}.

010 est un élément primitif sur F_{2^{3}} comme le montre ce tableau:

\begin{matrix}x & −∞ & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ (010)^{x} & 000 & 001 & 010 & 100 & 011 & 110 & 111 & 101 \end{matrix}

2.11 Factorisation de q − 1...

En général, il s’avère difficile de factoriser le nombre q − 1. Il ne sera donc possible de trouver un élément primitif que pour les nombres q − 1 dont les facteurs premiers sont connus. Une alternative existe néanmoins si l’on peut se contenter d’un corps contenant un nombre aléatoire d’éléments. Éric Bach [] a développé un algorithme probabiliste efficace capable de générer un entier aléatoire d’une certaine longueur avec sa factorisation. Supposons que l’on obtienne aléatoirement le nombre r avec sa factorisation grâce à l’algortihme de Bach. Il sera alors possible de tester si le nombre r + 1 est premier ou de la forme p^{n} pour p premier. Dans ce cas un corps fini de r + 1 éléments pourra être obtenu et un élément primitif pourra être découvert.

3 Espaces vectoriels

Un espace vectoriel est constitué d’un ensemble de vecteurs V muni d’une addition ⊕ ayant une structure de groupe abélien G = (V, ⊕) et d’un ensemble de scalaires S muni d’une addition + et d’un produit × ayant une structure d’anneau avec identité R = (S, +, ×):

• G est associatif, commutatif, possède un élément neutre et des inverses,

• R est associatif (+, ×), commutatif (+), possède un élément neutre (+, ×) et des inverses (+).

L’espace vectoriel possède également un produit entre les él’ements de S et ceux de V tel que:

• c(u ⊕ v) = (cu) ⊕ (cv),

• (b + c)v = (bv) ⊕ (cv),

• (b × c)v = b(cv),

• 1v = v où 1 est l’élément neutre multiplicatif de R.

• 0v = 0 où 0 est l’élément neutre additif de R et 0 l’élément neutre de G.

Exemple: On défini un espace vectoriel sur un corps fini F_{q} en prennant V = {(e_{1}, e_{2}, ..., e_{n}) : e_{i} ∈ F_{q}} et S = F_{q}.

3.1 Combinaisons linéaires

Une combinaison linéaire est une somme de la forme c_{1}v_{1} ⊕ c_{2}v_{2} ⊕ ... ⊕ c_{n}v_{n}. Un ensemble de vecteurs {v_{1}, v_{2}, ..., v_{n}} sont linéairement dépendent s’il existent des scalaires c_{1}, c_{2}, ..., c_{n} non tous nuls tels que c_{1}v_{1} ⊕ c_{2}v_{2} ⊕ ... ⊕ c_{n}v_{n} = 0. Sinon ils sont linéairement indépendent.

3.2 Produit Scalaire

Le produit scalaire (u · v) de deux vecteurs u = (u_{1}, u_{2}, ..., u_{n}) et v = (v_{1}, v_{2}, ..., v_{n}) est défini par

u · v = u_{1} × v_{1} + u_{2} × v_{2} + ... + u_{n} × v_{n}.

Deux vecteurs tels que (u · v) = 0 sont orthogonaux. Contrairement aux nombres réels où le seul vecteur orthogonal à lui même est le vecteur 0, sur un corps fini il peut exister plusieurs vecteurs orthogonaux à eux même.

Exemple: Les vecteurs (1, 0, 0, 1) et (1, 1, 1, 1) sont auto-orthogonaux sur F_{2} car (1, 0, 0, 1) · (1, 0, 0, 1) = (1, 1, 1, 1) · (1, 1, 1, 1) = 0.

4 Algèbre Linéaire

On défini des matrices sur F_{q} comme sur les nombres réels. Une matrice n × m (n par m) sur F_{q} est de la forme suivante où chaque a_{ij} ∈ F_{q}

A = [ \begin{matrix}a_{11} & a_{12} & … & a_{1m} \\ a_{21} & a_{22} & … & a_{2m} \\ ⋮ & ⋮ & ... & ⋮ \\ a_{n1} & a_{n2} & … & a_{nm} \end{matrix} ]

Note: Un vecteur v peut être considéré comme une matrice contenant une seule ligne.

4.1 opérations

La somme de deux matrices A, B n × m est défini par

A + B = [ \begin{matrix}a_{11} + b_{11} & a_{12} + b_{12} & … & a_{1m} + a_{1m} \\ a_{21} + b_{21} & a_{22} + b_{22} & … & a_{2m} + b_{2m} \\ ⋮ & ⋮ & ... & ⋮ \\ a_{n1} + b_{n1} & a_{n2} + b_{n2} & … & a_{nm} + b_{nm} \end{matrix} ] .

Le produit d’un scalaire et d’une matrice A n × m est défini par

cA = [ \begin{matrix}c × a_{11} & c × a_{12} & … & c × a_{1m} \\ c × a_{21} & c × a_{22} & … & c × a_{2m} \\ ⋮ & ⋮ & ... & ⋮ \\ c × a_{n1} & c × a_{n2} & … & c × a_{nm} \end{matrix} ] .

Le produit de deux matrices A, B respectivement n × k et k × m est défini par

AB = [ \begin{matrix}A_{1∗} · B_{∗1} & A_{1∗} · B_{∗2} & … & A_{1∗} · B_{∗m} \\ A_{2∗} · B_{∗1} & A_{2∗} · B_{∗2} & … & A_{2∗} · B_{∗m} \\ ⋮ & ⋮ & ... & ⋮ \\ A_{n∗} · B_{∗1} & A_{n∗} · B_{∗2} & … & A_{n∗} · B_{∗m} \end{matrix} ]

où A_{i∗} est la iième ligne de A et B_{∗j} est la jième colonne de B.

4.2 temps

L’addition de deux matrices n × m prend O(nm) additions du corps fini. Le produit d’un scalaire avec une matrice n × m prend O(nm) multiplications du corps fini. Le produit de deux matrices n × k, k × m prend O(nmk) multiplications du corps fini si implémenté de façon “naturelle”. Si implémenté de façon plus subtile on peut réduire ce temps de calcul pour des grandes matrices. Dans le cas où n = m = k on peut multiplier deux matrices par O(n^{2.376}) multiplications du corps fini au lieu de O(n^{3}). Consulter “Fundamentals of Algorithmics” par Brassard et Bratley pour plus de détails.

4.3 déterminant

Le déterminant d’une matrice A carrée n × n est défini par

det(A) = ∑_{(i_{1},i_{2},...,i_{n})∈π(1,2,...,n)} −1^{σ(i_{1},i_{2},...,i_{n})}a_{1i_{1}} × a_{2i_{2}} × ... × a_{ni_{n}}

où σ(i_{1}, i_{2}, ..., i_{n}) est la parité de la permutation (i_{1}, i_{2}, ..., i_{n}) et π(1, 2, ..., n) l’ensemble des permutations de 1, 2, ..., n.

On utilise le déterminant pour décider si une matrice est constituée de vecteurs linéairement dépendents (det(A) = 0) ou non (det(A) ≠ 0).

Temps: Si on utilise bêtement cette définition pour calculer le déterminant il en découle un algorithme qui prend un temps n!, ce qui est très mauvais. C’est aussi mauvais si l’on utilise le formule récursive bien connue. Si l’on utilise l’algorithme de Gauss-Jordan qui consiste à d’abord réduire la matrice pour rendre le calcul du déterminant trivial, il en résulte un algorithme en temps O(n^{3}). On peut faire mieux en utilisant des lagorithmes de multiplication rapide et descendre l’exposant à au plus O(n^{log_{2} 7}) ≈ O(n^{2.81}).

4.4 matrices échelonées réduites

L’espace linéaire engendré par une matrice A est l’ensemble des combinaisons linéaires de ses lignes. On peut faire trois types d’opérations à la matrice A qui ne modifie pas l’espace qu’elle engendre:

• permuter deux lignes,

• multiplier une ligne par un scalaire non nul,

• remplacer une ligne par elle-même à laquelle on ajoute un scalaire fois une autre ligne.

Il est souvent souhaitable de changer de matrice, tout en gardant le même espace engendré, et de l’avoir selon une forme dite échelonée réduite:

• la première valeur non nulle de chaque ligne est 1,

• les autres lignes contiennent 0 dans cette colonne,

• la première valeur non nulle de chaque ligne est à droite de celles des lignes plus hautes dans la matrice.

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_{q} 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}.

9 Limites sur les performances des codes

9.1 Borne supérieure de Singleton

Theorem 27 Borne de Singleton. Pour tout code (n, M, d) on a q^{n−d+1} ≥ M et en particulier pour tout code linéaire [n, k, d]

n − k ≥ d − 1.

9.2 Borne inférieure de Varshamov-Gilbert

Theorem 28. Soit H la matrice de parité d’un code linéaire de longueur n. La dimension de ce code est n − r où r est le nombre de colonnes linéairement indépendantes de H.

Theorem 29. Soit H la matrice de parité d’un code linéaire de longueur n. La distance minimale d de ce code est telle que tout ensemble de d − 1 colonnes de H sont linéairement indépendantes mais il existe d colonnes de H linéairement dépendantes.

Soit h_{q}(x) = x log_{q}(q − 1) − x log_{q} x − (1 − x) log_{q}(1 − x).

Theorem 30 Borne de Varshamov-Gilbert. Soit D_{q} le plus grand entier tel que

\binom{n − 1}{0} + \binom{n − 1}{1}(q − 1) + \binom{n − 1}{2}(q − 1)^{2} + ... + \binom{n − 1}{D_{q} − 2}(q − 1)^{D_{q}−2} < q^{n−k}

alors il existe sur F_{q} un code linéaire [n, k, d] pour d ≥ D_{q} et asymptotiquement, il existe un code linéaire [n, ρn, d] pour d ≥ ϵn si

ρ < 1 − h_{q}(ϵ).

Theorem 31 Borne de Varshamov-Gilbert. Soit ϵ et δ des constantes réelles. Soit ρ = 1 − h_{q}(ϵ). Soit C le [n, ρn, d] code sur F_{q} engendré par une matrice aléatoire de rang ρn et de dimensions ρn × n. Il existe un α < 1 tel que

P (d > (ϵ − δ)n) ≥ 1 − α^{n}

et

P (d > (ϵ + δ)n) ≤ α^{n}.

9.3 Borne supérieure de Hamming

Theorem 32 Borne de Hamming. Il n’existe pas sur F_{q} de code (n, M, 2t) ou (n, M, 2t + 1) dès que

\binom{n − 1}{0} + \binom{n − 1}{1}(q − 1) + \binom{n − 1}{2}(q − 1)^{2} + ... + \binom{n}{t}(q − 1)^{t} > q^{n}/M

et asymptotiquement, il n’existe pas de code (n, q^{ρn}, d) pour d ≥ ϵn si

ρ > 1 − h_{q}(ϵ/2).

9.4 Borne supérieure de Plotkin

Theorem 33 Borne de Plotkin. Pour tout code (n, M, d) pour lequel d > θn = \frac{q−1}{q}n on a

M ≤ \frac{d}{d − θn}.

9.5 Borne supérieure de McEliece-Rodemich-Rumsey-Welch

Theorem 34 Borne de McEliece-Rodemich-Rumsey-Welch. Asymptotiquement, il n’existe pas de code linéaire binaire [n, ρn, d] pour d ≥ ϵn dès que

ρ < h (\frac{1}{2} − \sqrt{ϵϵ̄}) .

IFT6170 Claude Crépeau. 21 Fig. 4. Bornes de Hamming et de V-G

Fig. 5. Bornes de McEliece-Rodemich-Rumsey-Welch et de V-G

10 NP-complétude de problèmes sur les codes

10.1 NP-complet ou NP-ardu?

Un problème X est NP-ardu si tout problème dans la classe NP se retrouve dans la classe P dès que X est dans P. Un problème X est NP-complet s’il est dans NP en plus d’être NP-ardu. Pour montrer un tel résultat, il faut d’abord donner un algorithme non-déterministe polynomial pour X puis montrer comment transformer les exemplaires de n’importe quel problème Y de NP en un exemplaire de X en temps polynomial. Bien sur, il est difficile de montrer une telle chose pour tous les problèmes de NP. Néanmoins, Cook a montré que le problème SAT est NP-complet. À partir d’un premier problème NP-ardu A on peut montrer qu’un autre problème B l’est en donnant une transformation polynomial des exemplaires du problème A aux exemplaires du problème B. Si B est dans P alors A l’est aussi, ainsi que tous les problèmes dans NP. On connait déja de nombreux problèmes NP-complets. Un exemple courant de problème NP-complet est 3DM:

Definition 35 Matching Tri-Dimensionel (3DM). Exemplaire:

Donnée: Un sous-ensemble U ⊆ T × T × T pour un ensemble fini T.

Problème: Existe-t-il un sous-ensemble W de U de taille |T | tel que pour tout (w_{1}, w_{2}, w_{3}), (w′_{1}, w′_{2}, w′_{3}) ∈ W on a w_{1} ≠ w′_{1}, w_{2} ≠ w′_{2}, w_{3} ≠ w′_{3}?

La réduction des exemplaires de SAT à ceux de 3DM est un résultat classique de NP-complétude. On peut le trouver dans le livre de Garey et Johnson. Afin de montrer la NP-complétude de certains problèmes sur les codes on va montrer comment transformer les exemplaires de 3DM en ceux des problèmes considérés.

10.2 correction d’erreurs

On montre dans cette section que le problème de la correction d’erreurs pour un code linéaire quelconque est NP-ardu. On défini d’abord formellement ce problème.

Notations: Pour une matrice binaire H et un mot binaire w on défini la distance au code engendreé par H par δ(w) = min{Δ (w, c) : w ≠ c, cH^{⊤} = 0}. Rappelons que le poids w(x) d’un mot binaire est le nombre de position non-nulles, c’est à dire w(x) = Δ (x, 0) .

Definition 36 plus proche mot de code (PPMC). Exemplaire:

Donnée: Une matrice binaire H, un mot binaire w.

Problème: Trouver c tel que cH^{⊤} = 0 et Δ (w, c) = δ(w).

Il est évident qu’un algorithme polynomial au problème PPMC nous donne également une solution au problème DC:

Definition 37 distance au code (DC). Exemplaire:

Donnée: Une matrice binaire H, un mot binaire w.

Problème: Trouver δ(w).

D’autre part, le problème DC est polynomialement équivalent au problème suivant:

Definition 38 poids minimal d’un coset (PMCS). Exemplaire:

Donnée: Une matrice binaire H, un mot binaire y, un entier k.

Problème: Existe-t-il un x ≠ 0 tel que xH^{⊤} = y et w(x) ≤ k?

Pour voir cette équivalence, il suffit de comprendre les deux réductions suivantes. On nomme DCP et P MCSP des algorithmes hypothétiques polinomiaux pour résoudre DC et PMCS.

Algorithme 10.1 ( P MCS(H, y, k) )

1: trouver un x tel que xH^{⊤} = y,

2: IF DCP(H, x) ≤ k THEN RETURN “oui” ELSE RETURN “non”.

Algorithme 10.2 ( DC(H, w) )

1: k ← 0, 2: y ← wH^{⊤}, 3: WHILE NOT P MCSP(H, y, k) DO k ← k + 1, 4: RETURN k.

On démontre en fait que PMCS est NP-Complet. Il en découle que DC et PPMC sont NP-ardu.

10.3 NP-complétude de PMCS

On montre d’abord que PMCS est dans NP grace à l’algorithme suivant:

Algorithme 10.3 ( P MCSNP(H, y, k) )

1: deviner un x,

2: IF xH^{⊤} = y et w(x) ≤ k THEN RETURN “oui”.

On donne ensuite une réduction de 3DM à PMCS. Soit T = {t_{1}, t_{2}, ..., t_{n}}. Pour un sous ensemble U = {(u_{1}^{1}, u_{1}^{2}, u_{1}^{3}), (u_{2}^{1}, u_{2}^{2}, u_{2}^{3}), ..., (u_{m}^{1}, u_{m}^{2}, u_{m}^{3})} de T × T × T on définie une matrice binaire H de dimension m × 3n de la façon suivante:

h_{ij} = \{ \begin{matrix}1 & si u_{i}^{1} = t_{j} \\ 0 & sinon \end{matrix} , h_{i(j+n)} = \{ \begin{matrix}1 & si u_{i}^{2} = t_{j} \\ 0 & sinon \end{matrix} , h_{i(j+2n)} = \{ \begin{matrix}1 & si u_{i}^{3} = t_{j} \\ 0 & sinon \end{matrix} .

Il suffit maintenant de remarquer que U possède un “matching” de T × T × T exactement s’il existe un x de poids n tel que xH^{⊤} = 111...1. Puisque tout x tel que xH^{⊤} = 111...1 doit avoir poids au moins n par construction de H, il suffit donc de savoir le résultat de P MCSP(H, 111...1, n).

10.4 poids des mots de code

Le problème le plus naturel à considérer est celui de trouver un mot de code de poids minimal ou simplement de déterminer le poids minimal des mots de code non-nuls. Ces problèmes sont PPCM et DC restreint aux mots du code. L’an dernier Moshe Vardy a montré que ces versions sont NP-ardu. Il en va donc de même pour PMCS restreint aux mots du code:

Definition 39 poids minimal du coset nul (PMCS0). Exemplaire:

Donnée: Une matrice binaire H, un entier k.

Problème: Existe-t-il un c ≠ 0 tel que cH^{⊤} = 0 et w(c) ≤ k?

Nous verrons plus tard la preuve que PMCS0 est NP-complet car elle demande passablement de techniques de codage. On va pour le moment se contenter de montrer q’un autre problème sur les codes qui est prèsqu’identique est NP-complet. Il s’agit de dire s’il existe ou non des mots de code d’un certain poids:

Definition 40 poids d’un code (PC). Exemplaire:

Donnée: Une matrice binaire H, un entier k.

Problème: Existe-t-il un c ≠ 0 tel que cH^{⊤} = 0 et w(c) = k?

10.5 NP-complétude de PC

On montre d’abord que PC est dans NP grace à l’algorithme suivant:

Algorithme 10.4 ( P CNP(H, k) )

1: deviner un c,

2: IF cH^{⊤} = 0 et w(c) = k THEN RETURN “oui”.

On donne ensuite une réduction de 3DM à PC. Soit H la matrice m × 3n construite à la section 10.3. On construit une nouvelle matrice M de dimensions (3nm + 3n + m) × 3n(m + 1) à partir de H de la façon suivante:

M = [ \begin{matrix}H & \overbrace{I_{m} I_{m} ... I_{m}}^{3n} \\ I & 3n(m+1) \end{matrix} ]

Il suffit maintenant de remarquer que U possède un “matching” de T × T × T exactement s’il existe un c de poids 3n^{2} + 4n tel que cM^{⊤} = 0. Il suffit donc de savoir le résultat de P CP(M, 3n^{2} + 4n), où P CP est un algorithme hypothétique polynomial pour résoudre PC.

10.6 Équivalence de codes

D’autre part, il est peu probable que le problème suivant soit NP-complet, bien qu’il est peu probable qu’il soit dans P:

Definition 41 équivalence de codes (ÉC). Exemplaire:

Donnée: Deux matrices binaires H_{0}, H_{1}.

Problème: Les matrices H_{0} et H_{1} sont-elles des matrices de parité de codes équivalents?

11 Codes cycliques

Les codes cycliques sont des codes linéaires tels que si le mot de code (c_{1}, c_{2}, ..., c_{n}) est dans le code, alors le mot (c_{n}, c_{1}, ..., c_{n−1}) l’est aussi.

On s’intéresse aux codes cycliques à cause de leurs propriétés algébriques. On va donc définir formellement les codes cycliques comme des objets algébriques.

Soit F_{q}[x] l’ensemble des polynomes de la variable x à coéfficients dans F_{q}. Soit R_{n} = F_{q}[x]/(x^{n} − 1) l’anneau des polynomes à coéfficients dans F_{q} modulo (x^{n} − 1).

Definition 42. Un idéal C de R_{n} est un sous-espace linéaire de R_{n} tel que pour tout c(x) ∈ C et r(x) ∈ R_{n}, on a c(x)r(x) ∈ C.

ou de façon équivalente

Definition 43. Un idéal C de R_{n} est un sous-espace linéaire de R_{n} tel que pour tout c(x) ∈ C, on a xc(x) ∈ C.

Definition 44. Un code cyclique C est un idéal de R_{n}.

11.1 polynome générateur

Pour tout code cyclique C il existe un polynome générateur g tel que C = ⟨g⟩, c’est-à-dire que C = {g(x)r(x) : r(x) ∈ R_{n}}.

Theorem 45. Soit C un code cyclique de R_{n}.

– il existe un unique polynome g(x) unitaire de degré minimal dans C,

– ce polynome g(x) est un générateur de C,

– g(x) est un facteur de x^{n} − 1,

– tout c(x) ∈ C peut s’écrire comme c(x) = f(x)g(x) avec deg(f) ≤ n − deg(g),

– si on pose g(x) = g_{0} + g_{1}x + ... + g_{r}x^{r} une matrice génératrice de C est

G = [ \begin{matrix}g_{0} & g_{1} & g_{2} & ... & g_{r} & 0 & 0 & ... & 0 \\ 0 & g_{0} & g_{1} & ... & g_{r−1} & g_{r} & 0 & ... & 0 \\ 0 & 0 & g_{0} & ... & g_{r−2} & g_{r−1} & g_{r} & ... & 0 \\ ... & ... & ... & ... & ... & ... & ... & ... & ... \\ 0 & 0 & 0 & ... & g_{0} & g_{1} & g_{2} & ... & g_{r} \end{matrix} ]

11.2 polynome de parité

Pour tout code cyclique C il existe un polynome de parité h tel que h(x) = (x^{n} − 1)/g(x), c’est-à-dire que C = {c(x) : c(x)h(x) ≡ 0 (mod x^{n} − 1)}.

Theorem 46. si on pose h(x) = h_{0} + h_{1}x + ... + h_{k}x^{k} une matrice de parité de C est

H = [ \begin{matrix}0 & ... & 0 & 0 & h_{k} & ... & h_{2} & h_{1} & h_{0} \\ 0 & ... & 0 & h_{k} & h_{k−1} & ... & h_{1} & h_{0} & 0 \\ 0 & ... & h_{k} & h_{k−1} & h_{k−1} & ... & h_{0} & 0 & 0 \\ ... & ... & ... & ... & ... & ... & ... & ... & ... \\ h_{k} & ... & h_{2} & h_{1} & h_{0} & ... & 0 & 0 & 0 \end{matrix} ]

11.3 code dual

Le code dual à un code cyclique C est également un code cyclique. Le polynome générateur g^{⊥} du code dual C^{⊥} est g^{⊥} = x^{deg(h)}h(1/x).

11.4 facteurs de x^{n} − 1

Soit F_{q} un corps fini quelconque et soit n relativement premier à q. Soit m le plus petit entier tel que q^{m} ≡ 1 (mod n). Alors sur F_{q^{m}} le polynome x^{n} − 1 est complètement factorisable sous la forme x^{n} − 1 = ∏_{i=0}^{n−1}(x − α^{i}) pour α une racine nième primitive de l’unité. En général, si γ est un élément primitif de F_{q^{m}} alors α = γ^{(q^{m}−1)/n} est une racine nième primitive de l’unité.

Puisque g(x)h(x) = x^{n} − 1, il existe K ⊆ {0, 1, 2, ..., n − 1} tel que

g(x) = ∏_{i∈K}(x − α^{i}) et h(x) = ∏_{i∉K}(x − α^{i}).

11.5 cosets cyclotomiques et polynômes minimaux

On définit sur F_{q}, le coset cyclotomique de s (mod n) comme

C_{s} = {s, sq, sq^{2}, …, sq^{m_{s}−1}}

où m_{s} est le plus petit entier tel que sq^{m_{s}} ≡ s (mod n).

Notons que m = m_{1} (cardinalité de C_{1}) nous donne le plus petit corps F_{q^{m}} où x^{n} −1 possède des racines. Le polynôme minimal de α^{s} est

M^{(s)}(x) = ∏_{i∈C_{s}}(x − α^{i}),

il est le polynôme de F_{q}[x] ayant degré minimal parmis tous ceux qui ont α^{s} comme racine. Il satisfait six propriétés importantes:

(M1) M^{(s)}(x) est irréductible sur F_{q}. (M2) si f(x) est un polynôme de F_{q}[x] tel que f(α^{s}) = 0 alors M^{(s)}(x)|f(x). (M3) M^{(s)}(x)|x^{n+1} − x. (M4) deg(M^{(s)}(x)) ≤ m. (M5) le polyôme minimal d’une racine primitive a degré m. (M6) α^{s} et α^{sq} ont le même polynôme minimal.

Exemple, code de Hamming: le code de Hamming H_{m} a pour matrice de parité

H = [ 1 α α^{2} ... α^{2^{m}−1} ]

où α est une élément primitif de F_{2^{m}}. c(x) est donc un mot de code si et seulement si c(α) = 0. Par la propriété (M2), ceci implique que c(x) est un multiple de M^{(1)}(x) et donc que le code est engendré par le polynôme g(x) = M^{(1)}(x) et a pour matrice génératrice:

G = [ \begin{matrix}M^{(1)}(x) & & … & 0 & 0 \\ 0 & M^{(1)}(x) & & … & 0 \\ 0 & 0 & M^{(1)}(x) \\ ... & ... & ... & ... & ... \\ 0 & 0 & 0 & ... & M^{(1)}(x) \end{matrix} ]

Exemple, BCH corrigeant 2 erreurs: le code de BCH corrigeant 2 erreurs a pour matrice de parité

H = [ \begin{matrix}1 & α & α^{2} & ... & α^{2^{m}−1} \\ 1 & α^{3} & α^{6} & ... & α^{3(2^{m}−1)} \end{matrix} ] .

c(x) est donc un mot de code si et seulement si c(α) = c(α^{3}) = 0. On conclut donc comme ci-haut qu’il est engendré par le polynôme g(x) = M^{(1)}(x)M^{(3)}(x).

11.6 borne de BCH

Theorem 47. Soit C un code cyclique généré par le polynome g(x) tel qu’il existe des entiers b ≥ 0, δ ≥ 1 et tel que

g(α^{b}) = g(α^{b+1}) = ... = g(α^{b+δ−2}) = 0.

Alors la distance minimale de C est d’au moins δ.

12 Codes BCH

Sur un corps fini F_{q}, on définit un code BCH de distance de design δ pour un entier b ≥ 0 à partir du polynome générateur

g(x) = ppcm {M^{(b)}(x), M^{(b+1)}(x), ..., M^{(b+δ−2)}(x)} .

Theorem 48. Un code BCH de longueur n et de distance de design δ a une distance minimale d ≥ δ et une dimension k = n − deg(g) ≥ n − m(δ − 1).

Remarques

– les codes BCH au sens restreint sont le cas b = 1,

– les codes BCH primitifs sont les cas n = q^{m} − 1,

– pour b fix, les codes BCH sont emboités c’est-à-dire que le BCH de distance de design δ_{1} est un sousensemble du BCH de distance de design δ_{2} si δ_{2} ≤ δ_{1},

– en général le dual d’un code BCH n’est pas un code BCH.

Exemple:

\begin{matrix}δ & g & i : g(α^{i}) = 0 & k & d \\ 1 & 1 & − & 15 & 1 \\ 3 & M^{(1)} & 1, 2, 4, 8 & 11 & 3 \\ 5 & M^{(1)}M^{(3)} & 1 − 4, 6, 8, 9, 12 & 7 & 5 \\ 7 & M^{(1)}M^{(3)}M^{(5)} & 1 − 6, 8 − 10, 12 & 5 & 7 \\ 9, 11, 13, 15 & M^{(1)}M^{(3)}M^{(5)}M^{(7)} & 1 − 14 & 1 & 15 \end{matrix}

\begin{matrix}δ & g & k & d \\ 1 & 1 & 23 & 1 \\ 3, 5 & M^{(1)} & 12 & 7 \\ 7 − 23 & M^{(1)}M^{(5)} & 1 & 23 \end{matrix}

\begin{matrix}δ & g & k & d \\ 1 & 1 & 31 & 1 \\ 3 & M^{(1)} & 26 & 3 \\ 5 & M^{(1)}M^{(3)} & 21 & 5 \\ 7 & M^{(1)}M^{(3)}M^{(5)} & 16 & 7 \\ 9, 11 & M^{(1)}M^{(3)}M^{(5)}M^{(7)} & 11 & 11 \\ 13, 15 & M^{(1)}M^{(3)}M^{(5)}M^{(7)}M^{(11)} & 6 & 15 \\ 17 − 31 & M^{(1)}M^{(3)}M^{(5)}M^{(7)}M^{(11)}M^{(15)} & 1 & 31 \end{matrix}

Fig. 6. codes BCH de longueur 15.

Fig. 7. codes BCH de longueur 23.

Fig. 8. codes BCH de longueur 31.

12.1 Distance minimale effective

Les quelques théoremes suivants nous donne une idée de la relation entre la distance de design d’un code BCH (δ) et sa distance minimale effective (d).

Theorem 49. Un code BCH de longueur n = q^{m} −1 et de distance de design δ = q^{h} −1 sur F_{q} a sa distance minimale effective d = δ.

Theorem 50. Un code BCH de longueur n = q^{m}−1 et de distance de design δ sur F_{q} a sa distance minimale effective d ≤ qδ − 1.

12.2 Symboles d’information

Soit I(n, δ) le nombre de symboles d’information dans un mot de code d’un code BCH primitif au sens restreint. Bien sur I(n, δ) = n − deg(g(x)) où g(x) est le polynome générateur du code. Néanmoins il est est préférable de trouver une borne générique sur I(n, δ) sans tenir compte du g(x) précis. C’est ce que fait le théoreme suivant.

Theorem 51. Le nombre de symboles d’information d’un code BCH au sens restreint de longueur n = q^{m}−1 et de distance de design δ = q^{λ} sur F_{q} est

I(q^{m} − 1, q^{λ}) ≤ ∑_{i=0}^{r} a_{i}ρ_{i}^{m}

pour r = m − λ et des constantes a_{1}, ..., a_{r}, ρ_{1}, ..., ρ_{r} qui ne sont fonctions que de r et telles que |ρ_{i}| < q.

12.3 Les codes BCH sont mauvais

Une famille de code {C_{i}} de paramètres [n_{i}, k_{i}, d_{i}] est bonne si

lim_{i→∞} k_{i}/n_{i} = R > 0 et lim_{i→∞} d_{i}/n_{i} = D > 0.

Sinon on dit de la famille qu’elle est mauvaise.

Theorem 52. Toute famille de codes BCH primitifs restreint est mauvaise.

Theorem 53 Berlekamp. Toute famille de codes BCH primitifs binaire de taux R possède assymptotiquement (n → ∞) une distance minimale

d ∼ 2n\frac{− log_{e} R}{lg n}.

13 Codes Reed-Solomon

13.1 definition

Un code Reed-Solomon (RS) sur F_{q} est un code BCH de longueur N = q − 1. Le polynome générateur du code RS de distance de design δ est

g(x) = M^{(b)}(x)M^{(b+1)}(x) ⋯ M^{(b+δ−2)}(x) = (x − α^{b})(x − α^{b+1}) ⋯ (x − α^{b+δ−2}).

La dimension d’un tel code est K = N − deg(g) = N − δ + 1 et sa distance minimale est D ≥ δ. Mais puisque d’autre part par la borne de Singleton on a que D ≤ N − K + 1 on a donc

D = δ = N − K + 1.

Theorem 54 RS étendus. Soit C un code RS de paramètres [N = q − 1, K, D] avec polynôme générateur

g(x) = (x − α)(x − α^{2}) ⋯ (x − α^{D−1}).

Le code C^{+} = {(c_{0}c_{1}c_{2}...c_{N−1}) : (c_{1}c_{2}...c_{N−1}) ∈ C, c_{0} = − ∑_{i=1}^{N−1} c_{i}} est un code [N + 1, K, D + 1].

13.2 codage

Theorem 55 interpolation de Lagrange. Soit α^{i_{1}}α^{i_{2}}...α^{i_{K}} des éléments distincts de F_{q} pour K < q et β_{1}β_{2}...β_{K} des éléments quelconques de F_{q}. Il existe un unique polynôme p(x) sur F_{q} tel que deg(p) < K et que pour 1 ≤ j < K

g(α^{i_{j}}) = β_{i}.

Preuve: considérons le système linéaire suivant:

[ \begin{matrix}1 & α^{i_{1}} & α^{2i_{1}} & ⋯ & α^{(K−1)i_{1}} \\ 1 & α^{i_{2}} & α^{2i_{2}} & ⋯ & α^{(K−1)i_{2}} \\ ⋮ & ⋮ & ⋮ & ... & ⋮ \\ 1 & α^{i_{K}} & α^{2i_{K}} & ⋯ & α^{(K−1)i_{K}} \end{matrix} ] [ p_{0} ; p_{1} ; ⋮ ; p_{K−1} ] = [ β_{1} ; β_{2} ; ⋮ ; β_{K} ]

puisque les α^{i_{j}} sont distincts, cette matrice est Vandermonde et donc elle est inversible. Il existe donc une et une seule solution (p_{0}p_{1}...p_{K−1}) pour chaque (β_{1}β_{2}...β_{K}).

Theorem 56. Consiérons le code définit ainsi

C = {(p(1)p(α)...p(α^{N−1})) : p est un polynôme de degré < K sur F_{q}}.

Le code C est un RS code [N = q − 1, K, N − K + 1].

Preuve: d’abord il est clair que la dimension de C est K car il existe q^{K} valeurs de p et p ≠ p′ implique que (p(1)p(α)...p(α^{N−1})) ≠ (p′(1)p′(α)...p′(α^{N−1})). Soient p et p′ deux polynômes tels que

Δ ((p(1)p(α)...p(α^{N−1}), (p′(1)p′(α)...p′(α^{N−1})) < N − K + 1.

Ceci implique qu’ils existent i_{1}, i_{2}, ..., i_{K} tels que p(α^{i_{j}}) = p′(α^{i_{j}}). Par le théoreme précédent ceci entraîne que p = p′. Donc il n’existe pas de pair c, c′ de mots distincts tels que Δ (c, c′) < N − K + 1.

13.3 codes binaires

On peut construire à partir d’un code RS C de paramètres [N, K, D] sur F_{2^{m}} un code binaire C^{#} de paramètres [n = N, K ≥ k ≥ n − m(N − K), d ≥ D] en considérant uniquement les mots de C ayant que des composantes dans F_{2}.

On peut également construire à partir d’un code RS C de paramètres [N, K, D] sur F_{2^{m}} un code binaire C^{→} de paramètres [n = Nm, k = Km, d ≥ D] en remplaçant dans les mots de code de C chaque symbole de F_{2^{m}} par m bits. Pour obtenir ces m bits il faut spécifier une base b_{1}, b_{2}, ..., b_{m} de F_{2^{m}} sur F_{2}.

On peut enfin construire à partir d’un code RS C de paramètres [N, K, D] sur F_{2^{m}} un code binaire C^{↑} de paramètres [n = N(m + 1), k = Km, d ≥ 2D] en remplaçant dans les mots de code de C chaque symbole de F_{2^{m}} par m bits et en ajoutant un bit de parité à chaque bloc de m bits.

13.4 les codes RS “binarisés” sont mauvais

Les codes binaires C^{→} et C^{↑} ne forment pas de famille de codes assymptotiquement bonne au sens déjà vu.

13.5 correction de paquets d’erreurs

Quand les erreurs se présentent par paquets plutot que de façon complètement indépendantes la structure de blocs obtenue en formant un code binaire d’un Reed-Solomon est propice à leur correction. Si le Reed-Solomon original a distance minimale D sur F_{2^{m}} alors le code binaire obtenu pourra corriger D/2 blocs erronnés. Un paquet de b bits erronnés pourra affecter r symboles sur F_{2^{m}} pour

(r − 2)m + 2 ≤ b ≤ (r − 1)m + 1.

De nombreux paquets peuvent être corrigés si r est beaucoup plus petit que D.

14 Codes Concaténés et Justesen

14.1 concaténation de codes

Un code concaténé C est obtenu à partir de deux codes C_{E} dit externe sur F_{q^{m}} de paramètres [n_{E}, k_{E}, d_{E}] et C_{I} dit interne sur F_{q} de paramètres [n_{I}, k_{I} = m, d_{I}]. Le code ainsi obtenu sera un code sur F_{q} de paramètres [n = n_{E}n_{I}, k = k_{E}k_{I} = mk_{E}, d ≥ d_{E}d_{I}].

14.2 code interne aléatoire ou maximal

Si l’on construit des codes concaténés en prenant comme code externe un Reed-Solomon [2^{m}, R2^{m}, (1 − R)2^{m} +1] et comme code binaire interne [σm, m, ρm] un code près de la borne de V-G (1/σ ≈ 1−h(ρ/σ)) on obtiendra des codes concaténés de paramètres [σm2^{m}, Rm2^{m}, (1 − R)ρm2^{m}]. En posant N = σm2^{m}, r = \frac{1}{σ} et en éliminant ρ on obtient

[N, RrN, (1 − R)h^{−1}(1 − r)N].

Si l’on fixe le produit γ = Rr il faudra prendre le r qui maximise l’expression suivante (1 − \frac{γ}{r})h^{−1}(1 − r) pour obtenir les meilleurs codes de ce type. La figure 9 nous montre le graphe de cette fonction comparé à la courbe de V-G.

On peut trouver les codes internes en prenant des matrices aléatoires de taille σm × m jsuqu’à ce que l’on en trouve une dont la distance minimale associée soit assez près de la borne de V-G.

14.3 codes multiplicatifs

Considérez les codes binaires C_{α} = {[u, αu] : u ∈ F_{2^{m}}} pour α ∈ F_{2^{m}} − 0. Pour α ≠ β on a C_{α} ⋂ C_{β} = {0} car un mot [u, v] ≠ 0 appartient seulement à C_{(vu^{−1})}.

14.4 les Codes multiplicatifs sont bons

Les codes de type C_{α} forment une bonne famille de codes. Pour voir ceci il suffit de remarquer d’abord qu’ils ont toujours un taux de transmission R = 1/2, puis de compter combien de codes peuvent avoir une distance minimale faible.

Il y a 2^{m} − 1 codes de type C_{α} au total. Il y a ∑_{i=1}^{λ2m} \binom{2m}{i} ≤ 2^{h(λ)2m} mot de longueur 2m de poids inféfieur ou égal à λ2m. Puisque chaque mot ne peut appartenir à plus d’un C_{α}, dès que ce nombre 2^{h(λ)2m} est inférieur à 2^{m} − 1, il doit exister des codes C_{α} de distance minimale supérieure à λ2m. Ceci sera le cas quand λ < h^{−1}(1/2) ≈ 0.11.

Fig. 9. Bornes de Zyablov et de V-G

14.5 codes de Justesen

L’idée de Justesen fut de concaténer les codes de type C_{α} avec un Reed-Solomon [2^{m} − 1, R(2^{m} − 1), (1 − R)(2^{m} − 1) + 1]. Justesen suggère d’utiliser comme codes internes tous les C_{α}. Selon moi, il est aussi efficace et plus simple de prendre le meilleur des C_{α}. Il suffit pour cela de les énumérer tous et de prendre celui qui a la plus grande distance minimale. On sais que cette distance minimale sera au moins h^{−1}(1/2)2m. Le code concaténé aura donc des paramètres

[N, R′N, (1 − 2R′)h^{−1}(1/2)N]

pour N = 2m(2^{m} − 1) et R′ = R/2. Ces codes sont sur la droite passant par les points (0, h^{−1}(1/2)) et (1/2, 0) et tangent au point (0.3, 0.4h^{−1}(1/2)) de la courbe de Zyablov.

14.6 décodage des codes concaténés

décodage naïf Consulter la thèse de Sendrier.

décodage de Block-Zyablov Consulter la thèse de Sendrier.

14.7 codes de Forney

Il est assez simple de constater que les codes concaténés contiennent des codes près de la borne de Shannon qui peuvent être construits, codés et décodés en temps polynomial. La construction utilise le théorème de Shannon que revoici.

Theorem 57. 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}.

De plus, pour n_{0} assez grand, un code aléatoire aura de tels paramètres sauf avec probabilité inférieure à 1/2.

Soit ϵ > 0 une probabilité d’erreur. Soit δ > 0 une costante positive. Soit q = 2^{m} pour un m assez grand. Soit R tel que 0 < R < C(BS_{ϵ}). Considérons un code aléatoire binaire de longueur m contenant M_{m} = ⌈2^{Rm}⌉ mots. Pour m assez grand, la probabilité d’erreur de décodage moyenne du code, ê(C_{m}) < α^{m}.

Si l’on concatène ce code avec un Reed-Solomon [2^{m}, 2^{m}(1−δ), 2^{m}δ +1], il en résulte un code de longueur N = m2^{m} ayant un taux de transmission au moins R(1 − δ). De plus, par la loi des grands nombres, la probabilité qu’une fraction δ/2 des 2^{m} blocs soient en erreur alors qu’une fraction α^{m} est espérée, est exponentiellement faible en 2^{m}, disons inférieure à β^{2^{m}} pour une constante positive β < 1. Donc le décodage successif des deux niveaux échouera seulement avec probabilité inférieure à β^{2^{m}}. Ceci n’est pas tout à fait exponentiellement faible en N, mais néanmoins, β^{2^{m}} est plus petit que n’importe quel inverse de polynôme en N:

Theorem 58. Por tout entier positif k et tout m assez grand

β^{2^{m}} < 1/N^{k}.

Ceci découle du fait que N = m2^{m} et donc que β^{2^{m}} = N^{−Θ(2^{m}/(m+lg m))}. L’exposant 2^{m}/(m + lg m) ne peut être borné par aucune constante.

15 Codes Reed-Solomon généralisés

Un code Reed-Solomon Généralisé (RSG) sur F_{q^{m}}^{N} est caractérisé par deux vecteurs α, v de longueur N avec α = (α_{1}, α_{2}, ..., α_{N}) ∈ F_{q^{m}}^{N} pour des α_{i} distincts et v = (v_{1}, v_{2}, ..., v_{N}) ∈ (F_{q^{m}} − {0})^{N}. Les mots d’un tel code sont obtenus à partir des polynômes F de degré < K par

c = (c_{1}c_{2}...c_{N}) = (v_{1}F (α_{1}), v_{2}F (α_{2}), ..., v_{N}F (α_{N})).

15.1 le dual d’un code RSG est RSG

À chaque RSG(α, v) de dimension K on peut associer un autre RSG(α, v′) de dimension N − K dual au premier. Ceci veut dire que la matrice de parité d’un code RSG(α, v) est donnée par

H = [ \begin{matrix}v′_{1} & v′_{2} & ... & v′_{N} \\ v′_{1}α_{1} & v′_{2}α_{2} & ... & v′_{N}α_{N} \\ ⋮ & ⋮ & ... & ⋮ \\ v′_{1}α_{1}^{N−K−1} & v′_{2}α_{2}^{N−K−1} & ... & v′_{N}α_{N}^{N−K−1} \end{matrix} ] .

16 Codes Alternants

Un code alternant A(α, v′) est un code sur F_{q} qui est obtenu du RSG(α, v) en conservant les mots ayant que des composantes dans F_{q}. La matrice H est aussi la matrice de parité du code A(α, v′) sur F_{q}.

16.1 décodage des codes Alternants: algorithme de Berlekamp

Soit C un code alternant A(α, v′) avec matrice de parité H. Soit r = N −K −1. Supposons que le mot c soit transmis et qu’un vecteur d’erreur e de poids t < r/2 lui soit ajouté. Appelons w = c ⊕ e le mot reçu. Soient X_{1} = α_{i_{1}}, X_{2} = α_{i_{2}}, …, X_{t} = α_{i_{t}} les t positions non-nulles de e, et soient Y_{1} = e_{i_{1}}, Y_{2} = e_{i_{2}}, …, Y_{t} = e_{i_{t}} les valeurs des erreurs en ces t positions.

On pose de façon formelle, le polynôme localisateur

σ(z) = ∏_{i=1}^{t}(1 − X_{i}z)

ainsi que le polynôme évaluateur

ω(z) = ∑_{j=1}^{t} Y_{j}v′_{i_{j}} ∏_{k=1,k≠j}^{t}(1 − X_{k}z)

Theorem 59.

Y_{j} = \frac{ω(X_{j}^{−1})}{v′_{i_{j}} ∏_{k=1,k≠j}^{t}(1 − X_{k}X_{j}^{−1})}

Theorem 60.

ω(x) ≡ σ(x)S(x) (mod x^{r})

Algorithme 16.1 ( Berlekamp decode(H, w) )

1: Calculer le syndrome S = [s_{0}, s_{1}, ..., s_{r−1}] = wH^{⊤}, 2: Définir un polynôme S(x) = s_{0} + s_{1}x + ⋯ + s_{r−1}x^{r−1}, 3: Appliquer l’algorithme Euclide(S(x), x^{r}) afin de trouver a_{k}, b_{k}, r_{k} tels que

r_{k}(x) = a_{k}(x)x^{r} + b_{k}(x)S(x) et deg(r_{k}) < r/2 mais deg(r_{k−1}) ≥ r/2,

4: Poser σ(x) = b_{k}(x)/b_{k}(0) et ω(x) = r_{k}(x)/b_{k}(0), 5: Trouver les racines de σ(x) par énumération.

16.2 les Codes Alternants sont bons

17 Codes Classiques de Goppa

34 IFT6170 Claude Crépeau

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)).

IFT6170 Devoir 2

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

Théorie de l’information [8 points]

Soit X une variable aléatoire prenant comme valeur à probabilité égale n’importe quel mot binaire de n bits. Soit f une quelconque fonction de n bits dans k bits telle que f(x_{1}x_{2}...x_{n}) = x_{i_{1}}x_{i_{2}}...x_{i_{k}} pour une certain liste d’indices i_{1}, i_{2}, ..., i_{k}. Soit BS_{ϵ}^{n} un canal binaire symétrique d’erreur ϵ. Soit hash la fonction de n bits dans 1 bit telle que hash(x_{1}x_{2}...x_{n}) = x_{1} ⊕ x_{2} ⊕ ... ⊕ x_{n}.

1. Quelles sont H(X), H(hash(X)), H(f(X)), H(BS_{ϵ}^{n}(X))?

2. Montrez que H(X|f(X)) et H(f(X)|X) sont les même quelque soit i_{1}, i_{2}, ..., i_{k} et donnez-en les valeurs.

3. Quelles sont H(X|BS_{ϵ}^{n}(X)) et H(BS_{ϵ}^{n}(X)|X)?

4. Quelles sont H(hash(X)|f(X)) et H(hash(X)|BS_{ϵ}^{n}(X))?

5. Prenons un exemple avec k = 0.99n et ϵ = 0.49. Considérez la situation suivante: Alice et Bob connaissent la valeur de X et Eve connait soit la valeur de f(X) pour un f de son choix comme ci-haut, soit celle de BS_{0.49}^{n}(X). Alice et Bob désirent obtenir un bit secret à partir de X. Pour cela ils utilisent B ← hash(X). Laquelle des deux stratégies possibles – voir n’importe quel 99% des bits de X ou voir X à travers un canal faisant 49% d’erreurs – donnera le plus d’information à Eve au sujet de B? (Comparez I(B; f(X)) et I(B; BS_{ϵ}^{n}(X)))

6. Est-il possible de trouver une quelconque fonction g de n bits dans 1 bit telle que I(g(X); BS_{ϵ}^{n}(X)) = 0? Démontrez votre réponse.

Canal d’Effacement Erroné [4 points]

Considérons le canal de la figure ci-haut. Supposons qu’en input P [X = 0] = p_{0} et P [X = 1] = 1 − p_{0}. Calculez l’information mutuelle entre l’input et l’output de ce canal en fonction de p, q, p_{0}, puis trouvez la capacité de ce canal et dites enfin quelle valeur de p_{0} produit la capacité.

PLUS et encore PLUS [4 points]

Démontrez que pour toutes variables aléatoires X et Y on a H(X + Y |Y) = H(X|Y) et que si X et Y sont indépendantes alors H(X + Y) ≥ max{H(X), H(Y)}. Donnez un exemple de variables dépendantes pour lesquelles cette inégalité ne tient plus.

IFT6170 Devoir 3

à rendre au début du cours le mercredi 5 novembre 1997

Équivalence de problèmes sur les codes [4 points]

Démontrez l’équivalence polynomiale des problèmes PMCS0 et PPMC restreints aux mots de codes (dans les deux directions).

Duaux [4 points]

Donnez pour chaque q, le plus grand ϵ_{q} que vous puissiez pour lequel il existe une famille de codes {C_{n}}_{n>n_{0}} et sa famille de codes duaux {C_{n}^{⊥}}_{n>n_{0}} constituées de codes linéaires C_{n}, C_{n}^{⊥} ⊆ F_{q}^{n} qui soient tous deux de distance minimale ϵ_{q}n. Justifiez votre réponse. Quelle est la valeur de lim_{q→∞} ϵ_{q}?

Donnez le plus petit ϵ que vous puissiez pour lequel il n’existe pas de famille de codes {C_{n}}_{n>n_{0}} et sa famille de codes duaux {C_{n}^{⊥}}_{n>n_{0}} constituées de codes linéaires C_{n}, C_{n}^{⊥} ⊆ F_{2}^{n} dont la distance minimale moyenne des deux soit ϵn. Justifiez votre réponse.

Codes Intersectants [8 points]

On dit qu’un code C engendré par G est intersectant si pour toute paire de mots de codes c_{0}, c_{1} ∈ C − {0} il existe une position i où c_{0}^{i} ≠ 0 ≠ c_{1}^{i}. Soit G la matrice génératrice n × k d’un code intersectant sur

F_{2}.Par exemple la matrice G = [ \begin{matrix}1 & 1 & 0 \\ 0 & 1 & 1 \end{matrix} ] engendre un code intersectant puisque ses mots de codes sont

000, 110, 011, 101 et que 110, 101 intersectent en position 1, 110, 011 intersectent en position 2, et 011, 101 intersectent en position 3.

1. Montrez que deux mots binaires c_{0}, c_{1} intersectent si et seulement si w(c_{0} ⊕ c_{1}) ≠ w(c_{0}) + w(c_{1}).

2. Donnez un code intersectant binaire de longueur n = 18 et dimension k = 6.

3. Montrez que pour un [n, k, d] code intersectant binaire on a toujours d ≥ k.

4. Montrez qu’asymptotiquement il n’existe pas de code intersectant binaire pour n < 3.53k.

5. Montrez qu’asymptotiquement il existe un code intersectant binaire pour n > 4.81k.

IFT6170 Devoir 4

à rendre au début du cours le mercredi 3 décembre 1997

Partage de secret [6 points]

Soit un code Reed-Solomon sur F_{q} ayant des paramètres [N = q − 1, K, N − K + 1]. On suppose que ses mots de code sont définis de façon standard

c = (c_{0} c_{1} ... c_{N−1}) = (F (1), F (α), ..., F (α^{N−1}))

pour les polynômes F sur F_{q} de degré < K. Supposons qu’Alice dispose d’un secret s ∈ F_{q}. Elle peut choisir un polynôme aléatoire

F (x) = s + f_{1}x + f_{2}x^{2} + ⋯ + f_{K−1}x^{K−1}

tel que F (0) = s, où chaque f_{i} est sélectionné au hasard dans F_{q}. Soit P_{0}, P_{1}, ..., P_{N−1} des personnes distinctes à qui Alice va distribuer des “ombres” de son secret: Alice donne c_{i} à P_{i}. Soit Φ ⊆ {0, 1, ..., N − 1}.

• Montrez que si |Φ| < K alors I(s; {(i, c_{i}) : i ∈ Φ}) = 0. C’est à dire que tout ensemble de personnes de taille inférieure à K n’a aucune information sur s.

• Montrez que si |Φ| ≥ K alors H(s | {(i, c_{i}) : i ∈ Φ}) = 0. C’est à dire que tout ensemble de personnes de taille au moins K peut déterminer s.

• Supposons que toutes les personnes se rencontrent et échangent leurs c_{i}. Considérons qu’un certain nombre t d’entre eux soit menteur et révèlent au contraire c̃_{i} ≠ c_{i}. Donnez une relation entre N, K et t qui donne les situations où l’on sera capable d’identifier les menteurs et de récupérer quand même le secret s. Comment peut-on identifier les menteurs efficacement?

Justesen généralisés [6 points]

Considérez sur F_{2} les codes C_{α,β} = {[u, αu, βu] : u ∈ F_{2^{m}}} pour α, β ∈ F_{2^{m}} − 0.

• Montrez qu’il existe parmis les codes C_{α,β} des codes de paramètres [3m, m, 3γm] pour γ ≥ h^{−1} (\frac{2}{3}) ≈ 0.1739523.

• Montrez qu’une construction semblable à celle de Justesen nous permet de construire à partir des codes C_{α,β} des codes sur F_{2} ayant des paramètres [N, RN, δN] pour N = 3m2^{m}, 0 ≤ R ≤ \frac{1}{3} et δ ≥ (1 − 3R)h^{−1} (\frac{2}{3}).

• Montrez qu’une construction semblable à la précédente nous permet de construire pour chaque entier a des codes sur F_{2} ayant des paramètres [N, RN, δN] pour N = am2^{m}, 0 ≤ R ≤ \frac{1}{a} et δ ≥ (1 − aR)h^{−1} (\frac{a−1}{a}).

• Tracez ces droites sur un graphique et montrez qu’elles forment un ensemble de tangentes à la courbe de Zyablov.

Codes réversibles [4 points]

Un code C ⊆ F_{q} est réversible si c_{0}c_{1} … c_{n−1} ∈ C implique c_{n−1}c_{n−2} … c_{0} ∈ C également. Montrez qu’un code cyclique C = ⟨g⟩ est réversible si et seulement si g(α) = 0 implique toujours g(α^{−1}) = 0. Montrez qu’un code cyclique C est réversible si et seulement si −1 est une puissance de q modulo n.

IFT6170 Devoir 5

à rendre avant la tombée de la nuit le vendredi 19 décembre 1997

Codes BCH sont Alternants [8 points]

Montrez de façon générale que les codes BCH sont des codes alternants. C’est-à-dire que les mots de codes peuvent être obtenus par la restriction sur F_{q} des mots d’un code RSG(α, v) sur F_{q^{m}}.

Prenez le code BCH binaire de longueur 23 et de distance de design 3. Un polynôme générateur de ce code est M^{(1)}(x). La dimension de ce code est de 12 et sa distance minimale réelle est de 7. En utilisant votre construction générale donnez le code RSG(α, v) dont ce code BCH est la restriction sur F_{2}.

Calculez le syndrome S du patron d’erreur (01000000000000000000000). Trouvez les polynômes σ et ω associés à ce patron. Vérifiez que ω(x) ≡ σ(x)S(x) (mod x^{r}).

Codes Intersectants [8 points]

1. Si on étend la définition de codes intersectants à tous les corps F_{q} il est possible sur certains corps de construire explicitement de tels codes. Montrez que pour des q > 2 assez grand certains codes Reed-Solomon sont intersectants sur F_{q}. suggestion: Tout code [n, k, d] pour d assez grand est intersectant.

2. Pourquoi est-ce que la suggestion du point ?? ne nous aide pas à montrer directement qu’il existe une bonne famille de codes intersectants sur F_{2}.

3. Montrez que la concaténation de deux codes intersectants est également un code intersectant.

4. Expliquez comment combiner les points précédents et ce que l’on connais déja sur les codes intersectants pour obtenir une construction efficace probabiliste d’une bonne famille de codes binaires (vérifiablement) intersectants. Donnez de façon explicite le lien entre k et n des codes binaires ainsi obtenus.

References

1. Alexi, W., B. Chor, O. Goldreich, and C. P. Schnorr, “RSA and Rabin Functions: Certain Parts Are as Hard as the Whole”. In Proceedings of the 25th Annual IEEE Symposium on Foundations of Computer Science, 1984, pp. 449-457.

2. Anderson, R. J., “Why Cryptosystems Fail”, In Proceedings of the 1993 ACM Conference in Computer and Communications Security, pp. 215–227.

3. Bennett, C.H., G. Brassard, C. Crépeau and M.–H. Skubiszewska, “Practical Quantum Oblivious Transfer”, In Advances in Cryptology: Proceedings of Crypto ’91, Lecture Notes in Computer Science, August 1991, Springer-Verlag, Berlin, pp. 351–366.

4. Blum, M., L. Blum and Shub, “A simple unpredictable pseudo-random number generator”, SIAM J. Computing, 15(2):364–383, May 1986.

5. Brassard, G., “On computationally secure authentication tags requiring short secret shared keys”, Advances in Cryptology: Proceedings of CRYPTO 82, Plenum Press, 1983, pp.79–86.

6. Brassard, G., C. Crépeau, and J.–M. Robert, “Information theoretic reductions among disclosure problems”, In Proceedings of the 27th Annual IEEE Symposium on Foundations of Computer Science, November 1986, pp. 168 – 173.

7. Carter, J.L., M. N. Wegman, “New Hash Functions and Their Use in Authentication and Set Equality”, Journal of Computer and System Sciences, Vol. 22, 1981, pp. 265–279.

8. Crépeau, C., “Equivalence between two flavours of oblivious transfers”, In Advances in Cryptology: Proceedings of Crypto ’87, Lecture Notes in Computer Science, August 1987, pp. 350 – 354.

9. Crépeau, C., “Quantum Oblivious Transfer”, Journal of Modern Optics, Dec. 1994.

10. Crépeau, C. and J. Kilian, “Achieving oblivious transfer using weakened security assumptions”, In 29^{th} Symposium on Foundations of Computer Science, pages 42–52. IEEE, 1988.

11. Crépeau, C. and L. Salvail, “Quantum Oblivious Mutual Identification”, Advances in Cryptology: Proceedings of EUROCRYPT ’95,Springer-Verlag, 1995.

12. Crépeau, C. and M. Sántha, “Efficient reductions among oblivious transfer protocols based on new selfintersecting codes”, In Sequences II, Methods in Communications, Security, and Computer Science, pp. 360–368. Springer-Verlag, 1991.

13. Even, S., O. Goldreich, and A. Lempel, “A randomized protocol for signing contracts”, Communications of the ACM, vol. 28, 1985, pp.637–647.

14. Fagin, R., M. Naor and P. Winkler, “Comparing Common Secret Information without Leaking it”, submitted for publication, Communications of the ACM, 1994.

15. Fiat, A. and A. Shamir, “How to prove yourself: practical solutions to identification and signature problems”, In Advances in Cryptology: Proceedings of Crypto ’86, Lecture Notes in Computer Science, August 1986 pp. 186–194. Springer, 1987.

16. Goldreich, O., S. Goldwasser, and S. Micali, “How to construct random functions”, Journal of the ACM, 133:792–807, 1986.

17. Goldreich, O., S. Micali and A. Wigderson, “How to play any mental game, or: A completeness theorem for protocols with honest majority”, In Proceedings of the 19th Annual ACM Symposium on Theory of Computing, May 1987, pp. 218 – 229.

18. Håstad, J., “Pseudo-random generation under uniform assumptions”, Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, May 1990, pp. 395 – 440.

19. Impagliazzo, R., L. A. Levin and M. Luby, “Pseudo-random generation from one-way functions”, Proceedings of the 21st Annual ACM Symposium on Theory of Computing, May 1989, pp. 12 – 24.

20. Kilian, J., “Founding cryptography on oblivious transfer”, In Proc. 20th ACM Symposium on Theory of Computing, pp. 20–31, Chicago, 1988. ACM.

21. Mac Williams, F. J. and N. J. A. Sloane, “The Theory of Error-Correcting Codes”, North-Holland, 1977.

22. Rabin, M. O., “How to exchange secrets by oblivious transfer”, Technical Memo TR–81, Aiken Computation Laboratory, Harvard University, 1981.

23. Spielman, D., “Linear-Time Encodable and Decodable Error-Correcting Codes”, In Proceedings of the 27th Annual ACM Symposium on Theory of Computing, 1995.

24. “One Less Thing to Believe In: Fraud at Fake Cash Machine”, New York Times, 13 May 1993, pp. A1 & B9.

25. Wiesner, S., “Conjugate coding”, Sigact News, vol. 15, no. 1, 1983, pp. 78 – 88; Manuscript written circa 1970, unpublished until it appeared in SIGACT News.

26. Yao, A. C.–C., “Protocols for secure computations”, In Proceedings of the 23rd Annual IEEE Symposium on Foundations of Computer Science, November 1982, pp. 160 – 164.

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