---
jupytext:
text_representation:
extension: .md
format_name: myst
format_version: 0.13
kernelspec:
display_name: SageMath 10.2
language: sage
name: sagemath
rise:
auto_select: first
autolaunch: true
centered: false
enable_chalkboard: true
height: 100%
margin: 0
maxScale: 1
minScale: 1
scroll: true
slideNumber: true
start_slideshow_at: selected
theme: white
transition: none
width: 90%
---
+++ {"slideshow": {"slide_type": "slide"}}
# Codes correcteurs
Quelques Références:
- [Wikipedia: Codes correcteurs](http://fr.wikipedia.org/wiki/Code_correcteur)
- [Codes correcteurs dans SageMath](https://doc.sagemath.org/html/en/thematic_tutorials/coding_theory.html)
- Textes d’agrégation:
- [Code de Goppa](http://nicolas.thiery.name/Enseignement/Agregation/Textes/goppa.pdf)
- [Codes Correcteurs d’Erreurs, Agreg 2005](http://nicolas.thiery.name/Enseignement/Agregation/Textes/527-CodesCorrecteursShannon.pdf)
+++ {"slideshow": {"slide_type": "slide"}}
## Introduction
+++
### Objectif du codage
Un expéditeur Alice transmet un message $m$ à Bob sur un canal bruité.
+++ {"slideshow": {"slide_type": "fragment"}}
:::{admonition} Problématique
- Comment Bob peut-il *détecter* l’existence d’erreurs de
transmission
- Comment Bob peut-il *corriger* des erreurs éventuelles
:::
+++ {"slideshow": {"slide_type": "fragment"}}
:::{note}
Contrairement à la *cryptographie*, la problématique n’est pas de se
protéger d’un tiers malicieux, mais d’un bruit aléatoire.
:::
+++ {"slideshow": {"slide_type": "slide"}}
:::{admonition} Exemples d’applications
1. NASA/CNES/...: communication avec des sondes et satellites
2. CD / DVD
3. Transfert de données par Internet (TCP, CRC, MD5 checksum)
4. Téléphones portables
:::
Quelles sont les contraintes spécifiques à chacune de ces applications?
+++ {"slideshow": {"slide_type": "slide"}}
### Premiers exemples de codes
:::{admonition} Exemple: Langages humains!
Syntaxe: orthographe, grammaire, lexique
Anglais: $500000$ mots de longueur moyenne $10$ sur en gros $26^{10}$,
soit une proportion de $10^{-9}$
Exemple: pomme, abrucot, poime (pomme, poire, prime, poème)
Sémantique: sens, contexte, ...
:::
+++ {"slideshow": {"slide_type": "slide"}}
:::{admonition} Exemple: codage de parité sur 7 bits
Alice veut envoyer le message $m = 0100101$
Elle le code en un mot à 8 bit avec un nombre pair de 1,
en rajoutant *un bit de parité*: $c = 01001011$
Le code est transmis $c$ et éventuellement altéré
Bob reçoit $c'$ et regarde s'il y a un nombre pair de 1:
- Si non, comme pour $c' = 01101011$, Bob détecte qu'il y a eu erreur
- Si oui comme pour $c' = 10001011$, Bob suppose que $c=c'$
:::
+++ {"slideshow": {"slide_type": "slide"}}
## Premiers concepts
+++ {"slideshow": {"slide_type": "fragment"}}
:::{admonition} Définitions
Un *code* $C$ est un sous-ensemble de *mots* dans $M:=A^{n}$, où
- $A$ est un ***alphabet***, comme $A:=\mathbb{ZZ}/q\mathbb{ZZ}= \{0,1,...,q-1\}$ .
Typiquement $q=2$ (codes binaires).
- $n$ est un entier, la ***dimension*** du code
:::
+++ {"slideshow": {"slide_type": "fragment"}}
***Codage***: on transforme le message envoyé $m$ en un mot $c$ du code.
***Transmission***: en passant à travers le canal, $c$ devient $c'$.
***Détection d’erreur***: on essaye de déterminer si $c=c'$; approximation: on teste si $c'$ est dans $C$
***Correction d’erreur***: on essaye de retrouver $c$ à partir de $c'$.
***Décodage***: on retrouve le message $m$ à partir de $c$.
+++ {"slideshow": {"slide_type": "slide"}}
### Décodage par distance de Hamming
+++ {"slideshow": {"slide_type": "fragment"}}
:::{admonition} Définition
***Distance de Hamming*** entre deux mots: nombre de lettres qui diffèrent (en comparant lettre à lettre).
:::
+++ {"slideshow": {"slide_type": "fragment"}}
**Stratégie:**
1. Détection d’erreur: est-ce que $c'$ est dans le code $C$?
2. Correction d’erreur par distance minimale: on renvoie le mot de $C$
le plus proche de $c'$.
+++ {"slideshow": {"slide_type": "slide"}}
:::{admonition} Exercice: Est-ce raisonnable?
On suppose que lors de la transmission chaque lettre a une probabilité
$p$ d’être corrompue, indépendemment des autres.
Calculer la probabilité qu’un mot de longueur $n$ arrive intact? Avec
une erreur au plus? Avec deux erreurs au plus?
:::
+++ {"slideshow": {"slide_type": "fragment"}}
Application numérique:
```{code-cell} ipython3
---
slideshow:
slide_type: fragment
---
n = 7; p = 0.1
(1-p)^n
```
```{code-cell} ipython3
(1-p)^n + n*p*(1-p)^(n-1)
```
```{code-cell} ipython3
(1-p)^n + n*p*(1-p)^(n-1) + binomial(n,2) * p^2*(1-p)^(n-2)
```
```{code-cell} ipython3
---
slideshow:
slide_type: fragment
---
n = 7; p = 0.01
(1-p)^(n-1)
```
```{code-cell} ipython3
(1-p)^n + n*p*(1-p)^(n-1)
```
```{code-cell} ipython3
(1-p)^n + n*p*(1-p)^(n-1) + binomial(n,2) * p^2*(1-p)^(n-2)
```
+++ {"slideshow": {"slide_type": "slide"}}
:::{admonition} Définitions
- ***Capacité de détection***: $D(C)$ nombre maximal d’erreurs que l’on
est sûr de détecter
- ***Capacité de correction***: $e(C)$ nombre maximal d’erreurs que l’on
est sûr de corriger
- ***Distance*** $d(C)$ du code: distance minimale entre deux points
distincts du code
:::
+++ {"slideshow": {"slide_type": "fragment"}}
#### Formalisation
Pour formaliser cela, il est pratique d’introduire la notion
de boule naturellement associée à une métrique: étant donné $x\in M$ et
un entier $k\geq 0$, la ***boule de centre $x$ et de rayon $k$*** est:
$$B(x,k) = \{y\in M,\quad d(x,y) \leq k\}$$
+++ {"slideshow": {"slide_type": "fragment"}}
Alors:
$$D(C) := \max_{k\in \mathbb{N}\cup\{\infty\}} \quad \forall c\in C, \quad B(c,k) \cap C = \{c\}$$
$$e(C) := \max_{k\in \mathbb{N}\cup\{\infty\}} \quad \forall c_1\, c_2\in C, \quad
B(c_1,k) \cap B(c_2,k) \ne \emptyset \Longrightarrow c_1=c_2$$
$$d(C) := \min_{x\ne y\in C} d(x,y)$$
+++ {"slideshow": {"slide_type": "fragment"}}
#### Cas dégénérés
Lorsque $|C|\leq 1$, on prendra par convention
$d(C)=+\infty$. Cela peut paraître plus naturel en prenant la définition
alternative:
$$d(C) := \max_{k\in \mathbb{N}\cup\{\infty\}} \forall x\ne y \in C, \quad k\leq d(x,y)$$
+++ {"slideshow": {"slide_type": "slide"}}
**Exercice: en petite dimension**
On fixe $A=\mathbb{ZZ}/2\mathbb{ZZ}$ (codes binaires).
1. Trouver tous les codes de $M=A^n$ pour $n=1$,
$n=2$, $n=0$.
2. Pour chacun d’entre eux, donner la distance $d(C)$, la capacité de
détection $D(C)$, la capacité de correction $e(C)$. Dessiner les
boules de centres dans $C$ et de rayon $e(C)$.
3. Permettent-t’ils de corriger une erreur?
4. Donner un code de $M=A^3$ permettant de
corriger une erreur.
5. Peut-on faire mieux?
+++ {"slideshow": {"slide_type": "slide"}}
:::{admonition} Proposition
Capacité de détection: $D(C) = d(C) - 1$.
Capacité de correction: $e(C) = \llcorner\frac{d(C)-1}2\lrcorner$.
:::
+++ {"slideshow": {"slide_type": "slide"}}
### Borne de Hamming, codes parfaits
+++ {"slideshow": {"slide_type": "fragment"}}
:::{admonition} [Conjecture de Kepler](https://en.wikipedia.org/wiki/Kepler_conjecture)
![](media/Kepler_conjecture_2.jpg)
:::
+++ {"slideshow": {"slide_type": "fragment"}}
:::{admonition} Problème: Kepler discret
On se fixe un alphabet $A$ avec $q=|A|$, une dimension $n$ et une
capacité de correction $e$. Combien de mot peut on coder au maximum?
De manière équivalente: combien de boules non intersectantes de rayon
$e$ peut-on faire rentrer dans $M$?
:::
+++ {"slideshow": {"slide_type": "slide"}}
**Exemples: visualisation des boules de rayon $e$ autour de quelques
codes binaires**
Chargement de quelques fonctions,
et configuration des plots 3D:
```{code-cell} ipython3
---
slideshow:
slide_type: fragment
---
%run "codes_correcteurs.py"
from sage.plot.plot3d.base import SHOW_DEFAULTS
SHOW_DEFAULTS['frame'] = False
SHOW_DEFAULTS['aspect_ratio'] = [1,1,1]
SHOW_DEFAULTS['viewer'] = 'threejs'
```
+++ {"slideshow": {"slide_type": "fragment"}}
Les boules dans $M=A^3$ pour $A=\mathbb{Z}/q\mathbb{Z}$:
```{code-cell} ipython3
@interact
def _(r=slider(0,3,1), q=slider(2,7,1)):
A = IntegerModRing(q)
M = A^3
return dessin_boules([M.zero()], r)
```
+++ {"slideshow": {"slide_type": "fragment"}}
Le code binaire de triple répétition:
```{code-cell} ipython3
A = GF(2)
M = A^3
C = M.subspace([[1,1,1]])
C.list()
```
```{code-cell} ipython3
dessin_boules(C,1)
```
+++ {"slideshow": {"slide_type": "fragment"}}
et sur $A=\mathbb{Z}/3\mathbb{Z}$:
```{code-cell} ipython3
A = GF(3)
M = A^3
M.list()[:9]
```
```{code-cell} ipython3
C = M.subspace([[1,1,1]])
C.list()
```
```{code-cell} ipython3
dessin_boules(C,1)
```
+++ {"slideshow": {"slide_type": "fragment"}}
Le code de Hamming:
```{code-cell} ipython3
A = GF(2)
M = A^7
C = codes.HammingCode(A, 3)
C.cardinality()
```
```{code-cell} ipython3
---
slideshow:
slide_type: fragment
---
dessin_boules(C, 1, projection=projection_7_3)
```
+++ {"slideshow": {"slide_type": "slide"}}
**Exercice: Borne de Hamming sur $|C|$.**
Soit $A=\mathbb{Z}/q\mathbb{Z}$.
1. Taille de la boule $B(x,e):=\{y,\quad d(x,y)\leq e\}$ de $A^n$ de
centre $x$ et de rayon $e$? Indication: commencer par $q=2$ et
$x=0\cdots0$.
2. Taille de $A^n$?
3. Conclusion?
+++ {"slideshow": {"slide_type": "fragment"}}
:::{admonition} Solution
:class: dropdown
$$|B(x,e(C))| = \sum_{k=0}^{e(C)} \binom n k (q-1)^k \qquad \qquad |C||B(x,e)| \quad \leq \quad q^n$$
:::
+++ {"slideshow": {"slide_type": "fragment"}}
Application numérique:
```{code-cell} ipython3
---
slideshow:
slide_type: fragment
---
@interact
def _(q=slider(1,7,default=2), n=slider(0,10, default=3), e=slider(0,10,default=1)):
m = q^n
b = sum(binomial(n,k)*(q-1)^k for k in range(0, e+1))
print(f"|M|={m}, |B(x,e(C))|={b}, |C|≤ {1.0*m/b:.2}")
```
+++ {"slideshow": {"slide_type": "slide"}}
:::{admonition} Définition: code parfait
Un code $C$ est ***parfait*** si on a égalité: $|C| |B(x,e(C))| = |A^n|$, i.e.
$$|C| \sum_{k=0}^{e(C)} \binom n k (q-1)^k \quad = \quad q^n$$
:::
+++ {"slideshow": {"slide_type": "fragment"}}
:::{admonition} Exemples
Dans tous les exemples vus jusqu’ici, les seuls codes parfaits sont les
codes triviaux, le code de triple répétition sur un alphabet à deux
lettres et le code de Hamming.
:::
+++ {"slideshow": {"slide_type": "fragment"}}
:::{admonition} Problème
Algorithmes de codage? de décodage?
:::
+++ {"slideshow": {"slide_type": "slide"}}
## Codes linéaires
+++
Principe: on rajoute de la structure pour rendre les algorithmes plus
efficaces.
+++ {"slideshow": {"slide_type": "fragment"}}
:::{admonition} Définition
Un ***code linéaire*** est un sous-espace vectoriel de $A^n$, où $A$
est un corps fini.
:::
Commençons par un petit échauffement.
+++ {"slideshow": {"slide_type": "slide"}}
**Exercice: algèbre linéaire sur $A=\mathbb{Z}/2\mathbb{Z}$, à la main**
Soit $H$ la matrice:
```{code-cell} ipython3
A = GF(2); A
```
```{code-cell} ipython3
H = matrix(A, [[0,1,1,1, 1,0,0],
[1,0,1,1, 0,1,0],
[1,1,0,1, 0,0,1]]); H
```
+++ {"slideshow": {"slide_type": "fragment"}}
1. Appliquez le pivot de gauss à $H$.
2. Est-ce que les vecteurs $(1,1,0,0,1,1,0)$ et $(1,0,1,1,1,0,1)$ sont
dans le sous-espace vectoriel engendré par les lignes de $H$?
3. Conclusion?
+++ {"slideshow": {"slide_type": "slide"}}
**Solution:**
```{code-cell} ipython3
H
```
```{code-cell} ipython3
---
slideshow:
slide_type: fragment
---
H[1], H[0] = H[0], H[1]
H
```
```{code-cell} ipython3
---
slideshow:
slide_type: fragment
---
H[2] = H[2] + H[0]
H
```
```{code-cell} ipython3
---
slideshow:
slide_type: fragment
---
H[2] = H[2] + H[1]
H
```
```{code-cell} ipython3
---
slideshow:
slide_type: fragment
---
H[0] = H[0] + H[2]
H[1] = H[1] + H[2]
H
```
```{code-cell} ipython3
---
slideshow:
slide_type: slide
---
u = vector(A, (1,1,0,0,1,1,0))
v = vector(A, (1,0,1,1,1,0,1))
```
+++ {"slideshow": {"slide_type": "fragment"}}
:::{admonition} Question
Est-ce que $u$ est dans le sous-espace vectoriel engendré par les lignes de $H$?
:::
+++ {"slideshow": {"slide_type": "fragment"}}
On cherche $a,b,c$ tels que $u = a H[0] + b H[1] + c H[2]$
```{code-cell} ipython3
H
```
```{code-cell} ipython3
---
slideshow:
slide_type: fragment
---
u
```
```{code-cell} ipython3
---
slideshow:
slide_type: fragment
---
u = u - H[0]
u
```
```{code-cell} ipython3
---
slideshow:
slide_type: fragment
---
u = u - H[1]
u
```
Donc $u$ est dans le sous-espace engendré par les lignes de $H$
```{code-cell} ipython3
---
slideshow:
slide_type: fragment
---
v
```
```{code-cell} ipython3
H
```
```{code-cell} ipython3
---
slideshow:
slide_type: fragment
---
v = v - H[0]
v
```
```{code-cell} ipython3
---
slideshow:
slide_type: fragment
---
v = v - H[2]
v
```
+++ {"slideshow": {"slide_type": "fragment"}}
Donc $v$ n'est pas dans ce sous-espace
+++ {"slideshow": {"slide_type": "slide"}}
### Exemples
+++ {"slideshow": {"slide_type": "fragment"}}
:::{admonition} Exemple: bit de parité
Sept bits plus un huitième bit dit de ***parité*** tel que le nombre total
de bit à $1$ est pair.
v: mon mot
$v_0 + v_1 + v_2 + v_3 + v_4 + ... + v_7=0$ sssi le nombre de bit à est pair
:::
+++ {"slideshow": {"slide_type": "fragment"}}
:::{admonition} Exemple: code de Hamming $H(7,4)$
Quatre bits $\left(a_{1},a_{2},a_{3},a_{4}\right)$ plus trois bits de
redondance $\left(a_{5},a_{6},a_{7}\right)$ définis par:
$$\begin{aligned}
a_{5} = a_{2}+a_{3}+a_{4}\\
a_{6} = a_{1}+a_{3}+a_{4}\\
a_{7} = a_{1}+a_{2}+a_{4}
\end{aligned}$$
:::
+++ {"slideshow": {"slide_type": "slide"}}
### Algorithmes
+++ {"slideshow": {"slide_type": "fragment"}}
#### Comment tester si un mot appartient au code?
Avec Sage:
```{code-cell} ipython3
A = GF(2); A
```
```{code-cell} ipython3
n = 7
M = A^7; M
```
+++ {"slideshow": {"slide_type": "fragment"}}
***Matrice de contrôle*** (équations définissant le code):
```{code-cell} ipython3
H = matrix(A, [[0,1,1,1, 1,0,0],
[1,0,1,1, 0,1,0],
[1,1,0,1, 0,0,1]])
```
+++ {"slideshow": {"slide_type": "fragment"}}
Test d’appartenance au code:
```{code-cell} ipython3
---
slideshow:
slide_type: fragment
---
mot_du_code = M([1,0,1,1,0,1,0]);
H * mot_du_code
```
```{code-cell} ipython3
---
slideshow:
slide_type: fragment
---
mot_quelconque = M([1,1,0,1,0,1,1]);
H * mot_quelconque
```
+++ {"slideshow": {"slide_type": "fragment"}}
Refaites le à la main!
+++ {"slideshow": {"slide_type": "fragment"}}
Le code lui-même est le noyau de $H$:
```{code-cell} ipython3
C = H.right_kernel()
C
```
```{code-cell} ipython3
mot_du_code in C
```
```{code-cell} ipython3
mot_quelconque in C
```
+++ {"slideshow": {"slide_type": "fragment"}}
Refaites le à la main!
+++ {"slideshow": {"slide_type": "fragment"}}
Est-ce que l’on pourrait trouver $C$ encore plus rapidement?
+++ {"slideshow": {"slide_type": "fragment"}}
Oui:
```{code-cell} ipython3
MatrixSpace(A,4,4)(1).augment(H[:,0:4].transpose())
```
+++ {"slideshow": {"slide_type": "slide"}}
:::{admonition} Exercice
- Combien y-a-t’il de mots dans le code de Hamming $C=H(7,4)$?
- Calculer la distance de ce code (indice: se ramener en zéro!)
- Quelle est sa capacité de détection? de correction? Est-il parfait?
:::
+++ {"slideshow": {"slide_type": "fragment"}}
Solution:
```{code-cell} ipython3
C.cardinality()
```
```{code-cell} ipython3
---
slideshow:
slide_type: fragment
---
def poids(c): return len([i for i in c if i])
```
```{code-cell} ipython3
poids(M([0,1,0,0,0,0,0]))
```
```{code-cell} ipython3
poids(M([1,0,1,1,0,1,0]))
```
```{code-cell} ipython3
min(poids(m) for m in C if m)
```
+++ {"slideshow": {"slide_type": "slide"}}
#### Comment coder un message en un mot du code?
***Matrice génératrice*** (base du code):
```{code-cell} ipython3
---
slideshow:
slide_type: fragment
---
G = C.matrix(); G
```
```{code-cell} ipython3
---
slideshow:
slide_type: fragment
---
M = A^4
m = M([1,0,1,0])
c = m * G; c
```
+++ {"slideshow": {"slide_type": "slide"}}
#### Comment décoder un mot du code en un message?
Du fait de la forme de la matrice génératrice:
```{code-cell} ipython3
---
slideshow:
slide_type: fragment
---
G
```
+++ {"slideshow": {"slide_type": "fragment"}}
le mot du code `c` est simplement obtenu en ajoutant des bits
supplémentaires à la fin du mot original. C'est une propriété
souhaitable des codes correcteurs car elle permet de bien séparer
information originale et information redondante. En particulier,
décoder est trivial: il suffit de récupérer les quatre premiers bits.
**Exemple:** la clé de contrôle de votre numéro de sécurité sociale.
+++ {"slideshow": {"slide_type": "slide"}}
### Correction d'erreur par syndrome
+++ {"slideshow": {"slide_type": "fragment"}}
:::{admonition} Exercice
1. Partir du mot zéro, le coder, et faire alternativement une erreur
sur chacun des bits. Noter le résultat après multiplication par la
matrice de contrôle.
2. Prendre un mot à 4 bits de votre choix, le coder, faire une erreur
sur un des 7 bits, corriger et décoder. Vérifier le résultat.
3. Que se passe-t’il s’il y a deux erreurs?
:::
+++ {"slideshow": {"slide_type": "fragment"}}
Soit $c$ dans le code: alors $H c = 0$
Après transmission, on obtient $c' = c + ϵ$, où $ϵ$ est l'erreur.
Alors: $Hc' = H (c + ϵ) = Hc + Hϵ = Hϵ$
On interprète $ϵ$ comme une ***maladie*** et $Hϵ$ comme un
***syndrome*** de la maladie: ce que l'on vient de calculer, c'est que
deux malades ayant la même maladie auront le même syndrome. La
réciproque est vraie tant que $ϵ$ reste dans la capacité de correction
(prouvez le!).
Cela nous donne la stratégie du ***décodage par syndrome*** suivante:
- Précalculer tous les syndromes $Hϵ$ pour toutes les «maladies» $ϵ$
dans la capacité de correction, et en faire une table.
- Pour corriger $c'$, on calcule son syndrôme $Hc'$. S'il est nul,
$c'$ est déjà dans le code: $c=c'$. Sinon on retrouve dans la table
$ϵ$ tel que $Hc'=Hϵ$, et on corrige $c'$ par $c=c'-ϵ$.
+++ {"slideshow": {"slide_type": "slide"}}
## Codes cycliques
Principe: encore plus de structure pour être encore plus efficace.
+++ {"slideshow": {"slide_type": "slide"}}
:::{admonition} Définition
Un code $C$ est ***cyclique*** s’il est stable par rotation des mots:
$$1010010\in C \Longleftrightarrow 0101001\in C \Longleftrightarrow 1010100\in C \Longleftrightarrow \cdots$$
:::
+++ {"slideshow": {"slide_type": "fragment"}}
Les praticiens ont très tôt noté que les codes cycliques avaient de
bonnes propriétés.
Plus tard une explication algébrique a été découverte.
+++ {"slideshow": {"slide_type": "fragment"}}
Donnons une structure d’**anneau quotient** à $M=A^n$ en l’identifiant
avec $A[X]/(X^n-1)$.
Sous cette identification, les mots ci-dessus correspondent à
$$1 + X^2 + X^5, X+X^3+X^6, 1+X^2+X^4$$
+++ {"slideshow": {"slide_type": "slide"}}
:::{admonition} Remarque
Dans $A[X]/(X^n-1)$, décalage = multiplication par $X$.
Par exemple, pour $A[X]/(X^7-1)$:
$$\begin{aligned}
X(1+X^2+X^5) = X + X^3 + X^6\\
X(X + X^3 + X^6) = X^2+X^4+X^7 = 1+X^2+X^4
\end{aligned}$$
:::
+++ {"slideshow": {"slide_type": "fragment"}}
:::{admonition} Correspondance
Codes cycliques $\longleftrightarrow$ idéaux dans $A[X]/(X^n-1)$.
:::
+++ {"slideshow": {"slide_type": "fragment"}}
:::{admonition} Algorithmique
Soit $g$ un diviseur de $X^n-1$, et $h$ tel que $gh=X^n-1$.
- Code: idéal engendré par $g$
- Codage: $m\mapsto mg$
- Détection d’erreur: $c*h=0$
- Décodage: division par $g$ modulo $X^n-1$ (par ex. par Euclide
étendu)
:::
+++ {"slideshow": {"slide_type": "slide"}}
:::{admonition} Codes BCH
On peut construire des codes cycliques de capacité de correction
déterminée à l’avance. Pour en savoir plus, voir [Wikipedia, Codes
BCH](http://en.wikipedia.org/wiki/BCH_code).
:::
+++ {"slideshow": {"slide_type": "slide"}}
## Codage par interpolation (Reed-Solomon)
+++ {"slideshow": {"slide_type": "fragment"}}
### Mise en jambe
:::{admonition} Exercice (secret partagé)
Un vieux pirate est sur son lit de mort. Dans sa jeunesse il a enfoui
un Fabuleux Trésor dans la lagune de l’Ile de la Tortue, quelque part
à l’est du Grand Cocotier. Il a réuni ses dix lieutenants préférés
pour leur transmettre l’information secrète indispensable: la distance
entre le Grand Cocotier et le Trésor. Connaissant bien ses
lieutenants, et dans un étonnant dernier sursaut de justice, il ne
voudrait pas qu’une conjuration de quelques uns d’entre eux assassine
les autres pour empocher seuls le trésor. En tenant cependant compte
de la mortalité habituelle du milieu, il souhaite donner une
information secrète à chacun de ses lieutenants pour que huit
quelconques d’entre eux puissent retrouver ensemble le trésor, mais
pas moins. Comment peut-il s’y prendre?
:::
:::{admonition} Solution
:class: dropdown
Par interpolation!
:::
+++ {"slideshow": {"slide_type": "slide"}}
### Application aux CD/DVD: Codage [CIRC](https://en.wikipedia.org/wiki/Cross-interleaved_Reed%E2%80%93Solomon_coding)
Paramètres du système de codage:
- un alphabet donné par un corps fini $GF(q)$.
- trois entiers $k$, $d$, et $l$ avec $d\leq l$
- $l$ points d’évaluation $x_1,\ldots,x_l$ dans $GF(q)$
- un procédé D de codage sur $GF(q)^k$ avec bonne capacité de détection
+++ {"slideshow": {"slide_type": "fragment"}}
:::{admonition} Codage d'un message de longueur $kd$ (dans $GF(q)^{kd}$)
1. Découpage du message en $k$ blocs de longueur $d$, chaque bloc
étant interprété comme un polynôme de degré $