Exercices corrigés — Codes correcteurs

$n$ est la longueur (nombre de colonnes), $k$ le rang de $G$.

$\lvert C\rvert=2^{k}$ car $C$ est un sous-espace.

Les mots sont les combinaisons $u_1L_1+u_2L_2$, $u_i\in\{0,1\}$.

$G$ a $4$ colonnes donc $n=4$, et ses $2$ lignes sont indépendantes donc $k=\dim C=2$. Comme $C$ est un sous-espace de dimension $2$ sur $\mathbb{F}_2$ : $\lvert C\rvert=2^{2}=4$.

$00\mapsto 0000$, $10\mapsto 1011$, $01\mapsto 0110$, $11\mapsto 1101$. Le code est $C=\{0000,1011,0110,1101\}$.

$d(x,y)=w(x-y)$ pour la distance de Hamming.

Si $x,y\in C$ alors $x-y\in C$ (sous-espace).

Faire varier la paire $(x,y)$ et le mot $z=x-y$.

Par définition $d(x,y)=w(x-y)$. Quand $x,y$ parcourent $C$ avec $x\neq y$, $z=x-y$ parcourt exactement $C\setminus\{0\}$ (linéarité : $z\in C$, et tout $z\neq 0$ s'écrit $z=z-0$). Donc $\min_{x\neq y}d(x,y)=\min_{z\neq 0}w(z)$.

Poids des mots non nuls de $C=\{0000,1011,0110,1101\}$ : $w(1011)=3$, $w(0110)=2$, $w(1101)=3$. Le minimum est $2$, donc $d=2$ : le code est $[4,2,2]$.

Supposer deux mots $c\neq c'$ et un reçu $y$ avec $d(y,c)\leq t$ et $d(y,c')\leq t$.

Inégalité triangulaire : $d(c,c')\leq d(c,y)+d(y,c')$.

En déduire $d(c,c')\leq 2t\leq d-1<d$, contradiction.

Supposons $y$ à distance $\leq t$ de deux mots $c\neq c'$. Par l'inégalité triangulaire $d(c,c')\leq d(c,y)+d(y,c')\leq 2t$. Or $2t=2\lfloor(d-1)/2\rfloor\leq d-1<d\leq d(c,c')$ : contradiction. Donc tout mot reçu est dans au plus une boule de rayon $t$ : le décodage par plus proche voisin corrige $\leq t$ erreurs.

Le $[5,2,3]$ a $d=3$, donc $t=\lfloor 2/2\rfloor=1$ : il corrige $1$ erreur et en détecte $d-1=2$. (Le décodage unique a été vérifié : aucune collision de boules de rayon $1$.)

Répétition : un seul bit d'information répété $n$ fois.

Parité : $G=[I_3\mid \mathbf{1}]$, la dernière colonne est la somme des $3$ premières.

$d$ = poids minimal d'un mot non nul.

$\{00000,11111\}$ : $n=5$, $k=1$ ($1$ bit), seul mot non nul $11111$ de poids $5$ donc $d=5$. C'est un $[5,1,5]$ (il corrige $\lfloor 4/2\rfloor=2$ erreurs).

$G=\begin{pmatrix}1&0&0&1\\0&1&0&1\\0&0&1&1\end{pmatrix}$ : $n=4$, $k=3$. Tout mot non nul a $\geq 2$ coordonnées non nulles (la parité force un nombre pair de $1$), donc $d=2$. C'est un $[4,3,2]$ (détecte $1$ erreur).

Reprendre les $4$ mots de code et compter leurs poids.

$A_0=1$ (le mot nul).

$d$ est le plus petit indice $i>0$ avec $A_i>0$.

Mots : $0000$ (poids $0$), $1011$ (poids $3$), $0110$ (poids $2$), $1101$ (poids $3$). Donc $A_0=1$, $A_2=1$, $A_3=2$, et $A_1=A_4=0$.

$\sum_i A_i=1+1+2=4=2^{2}$ ✓. Le plus petit poids non nul est $2$ : $d=2$.

$\lvert C\rvert=q^k=3^2$.

$d$ = poids minimal d'un mot non nul (linéarité, valable sur tout $\mathbb{F}_q$).

Examiner par exemple la ligne $L_1=(1,0,1,2)$ et les combinaisons.

$C$ est un sous-espace de dimension $2$ sur $\mathbb{F}_3$, donc $\lvert C\rvert=3^{2}=9$.

Les mots non nuls ont tous au moins $2$ coordonnées non nulles (les lignes $1012$ et $0121$ ont poids $3$ ; aucune combinaison non nulle n'a poids $1$). Le minimum des poids vaut $2$, donc $d=2$.

Calculer $GH^{\mathsf T}=I_k(-A)+A\,I_{n-k}$ par blocs.

$\operatorname{rg}H=n-k$ car $H$ contient le bloc identité $I_{n-k}$.

Sur $\mathbb{F}_2$, $-A=A$.

Par blocs, $G=[I_k\mid A]$ et $H^{\mathsf T}=\begin{pmatrix}-A\\ I_{n-k}\end{pmatrix}$, d'où $GH^{\mathsf T}=I_k\cdot(-A)+A\cdot I_{n-k}=-A+A=0$. Le bloc $I_{n-k}$ assure $\operatorname{rg}H=n-k$. Comme $\dim\ker H=n-(n-k)=k=\dim C$ et $C\subseteq\ker H$, on a $C=\ker H$.

Sur $\mathbb{F}_2$, $-A^{\mathsf T}=A^{\mathsf T}$. Ici $A^{\mathsf T}=\begin{pmatrix}1&0&1\\1&1&0\\0&1&1\end{pmatrix}$, donc $H=\left[\begin{array}{ccc|ccc}1&0&1&1&0&0\\1&1&0&0&1&0\\0&1&1&0&0&1\end{array}\right]$. On vérifie $GH^{\mathsf T}=0$ : tout mot de code a syndrome nul.

$x\in C\iff Hx^{\mathsf T}=0$, i.e. les colonnes $H_j$ avec $x_j\neq 0$ sont liées.

$Hx^{\mathsf T}=\sum_j x_j H_j$.

Un mot de poids $w$ $\iff$ une relation de dépendance entre $w$ colonnes.

$Hx^{\mathsf T}=\sum_{j}x_jH_j$ où $H_j$ est la $j$-ème colonne. Un mot non nul $x\in C$ de poids $w$ correspond à une relation $\sum_{j\in S}x_jH_j=0$ avec $\lvert S\rvert=w$ : $w$ colonnes liées. Le plus petit poids non nul $=d$ est donc le plus petit nombre de colonnes liées.

Dans le $[6,3]$, aucune colonne n'est nulle et deux colonnes sont toujours distinctes (indépendantes), mais trois colonnes peuvent se sommer à $0$ : le minimum est $3$, donc $d=3$ (le code corrige $1$ erreur).

$Hr^{\mathsf T}=Hc^{\mathsf T}+He^{\mathsf T}$ et $Hc^{\mathsf T}=0$.

$He^{\mathsf T}$ = colonne de $H$ correspondant à la position erronée.

$e=100000$ pointe la 1ʳᵉ colonne.

$s=Hr^{\mathsf T}=H(c+e)^{\mathsf T}=\underbrace{Hc^{\mathsf T}}_{=0}+He^{\mathsf T}=He^{\mathsf T}$. Comme $e=100000$, $He^{\mathsf T}$ est la 1ʳᵉ colonne de $H$, soit $s=(1,1,0)^{\mathsf T}$.

Le syndrome ne dépend que de l'erreur $e$ (pas du mot émis $c$) : tous les mots reçus d'un même coset $c+e$ ont le même syndrome. C'est la base du décodage.

Il y a $q^{n-k}=2^{3}$ syndromes possibles.

Chaque erreur de poids $\leq 1$ a un syndrome distinct (colonnes de $H$ distinctes et non nulles).

On décode $\hat c=r-\text{(chef de classe de }s)$.

Le syndrome vit dans $\mathbb{F}_2^{\,n-k}=\mathbb{F}_2^{3}$ : il y a $2^{3}=8$ syndromes, un par coset.

Les erreurs de poids $0$ (syndrome $0$) et de poids $1$ (syndromes $=$ les $6$ colonnes de $H$, toutes distinctes et non nulles car $d=3$) ont des syndromes deux à deux distincts. On les prend comme chefs de classe : recevoir $r$ de syndrome $s$, c'est corriger $\hat c=r-e_s$. Toute erreur simple est donc corrigée.

$Hr_1^{\mathsf T}=Hr_2^{\mathsf T}\iff H(r_1-r_2)^{\mathsf T}=0$.

$H z^{\mathsf T}=0\iff z\in C$.

Le nombre de cosets de $C$ dans $\mathbb{F}_q^n$ est $q^n/q^k$.

$s_1=s_2\iff Hr_1^{\mathsf T}=Hr_2^{\mathsf T}\iff H(r_1-r_2)^{\mathsf T}=0\iff r_1-r_2\in C\iff r_1+C=r_2+C$. Le syndrome est donc un invariant complet du coset.

L'application « syndrome » $\mathbb{F}_q^{\,n}/C\to\mathbb{F}_q^{\,n-k}$ est une bijection (injective par ce qui précède, et surjective car $H$ est de rang $n-k$). Il y a donc $q^{\,n-k}$ cosets $=$ $q^{\,n}/q^{k}$.

$y\in C^{\perp}\iff y\perp$ toute ligne de $G$ $\iff Gy^{\mathsf T}=0$.

$H$ a pour lignes une base de $\ker G^{\mathsf T}=C^{\perp}$ (rôles de $G$ et $H$ échangés).

Dimensions : $\dim C+\dim C^{\perp}=n$.

$y\in C^{\perp}\iff y\cdot(uG)=0\ \forall u\iff (Gy^{\mathsf T})=0$. L'espace des solutions est de dimension $n-k$. Or les lignes de $H$ sont orthogonales à $C$ (car $GH^{\mathsf T}=0$) et indépendantes (rang $n-k$) : elles forment une base de $C^{\perp}$. Donc $C^{\perp}$ est le code de matrice génératrice $H$ (et de matrice de contrôle $G$).

$\dim C^{\perp}=n-k$, donc $\dim(C^{\perp})^{\perp}=n-(n-k)=k=\dim C$. Comme $C\subseteq(C^{\perp})^{\perp}$ (tout $x\in C$ est orthogonal à tout $C^{\perp}$) et que les dimensions coïncident, $(C^{\perp})^{\perp}=C$.

Il y a $2^3-1=7$ vecteurs non nuls dans $\mathbb{F}_2^3$.

$n-k=$ nombre de lignes de $H$ ; $k=n-\operatorname{rg}H$.

$d$ = plus petit nombre de colonnes liées.

$H$ est $3\times 7$ (colonnes $=$ les $7$ vecteurs non nuls de $\mathbb{F}_2^3$), donc $n=7$ et $\operatorname{rg}H=3$, d'où $k=7-3=4$ : code $[7,4]$.

Les colonnes sont non nulles (pas de mot de poids $1$) et deux à deux distinctes (pas de mot de poids $2$). Mais trois colonnes peuvent être liées, p.ex. $001+010+011=0$. Donc $d=3$ : le code de Hamming $[7,4,3]$, qui corrige $1$ erreur.

$V_2(7,1)=\binom{7}{0}+\binom{7}{1}$ (boule de rayon $1$).

Multiplier par le nombre $2^4$ de mots de code.

Comparer à $\lvert\mathbb{F}_2^7\rvert=2^7$.

Une boule de rayon $t=1$ contient le centre plus les $7$ mots à distance $1$ : $V_2(7,1)=\binom{7}{0}+\binom{7}{1}=1+7=8=2^{3}$.

Il y a $2^{4}=16$ mots de code, donc les boules couvrent $16\cdot 8=128$ mots. Or $\lvert\mathbb{F}_2^{7}\rvert=2^{7}=128$. Les boules étant disjointes (car $d=3>2t$), elles pavent tout l'espace : $2^4\cdot V_2(7,1)=2^7$. Le code est parfait.

Les boules de rayon $t$ centrées sur les mots de code sont disjointes.

Leur réunion est incluse dans $\mathbb{F}_q^n$.

Sommer les volumes.

Les $\lvert C\rvert$ boules de rayon $t$ sont disjointes (corrige $t$ erreurs) et contenues dans $\mathbb{F}_q^{\,n}$. En sommant les cardinaux : $\lvert C\rvert\cdot V_q(n,t)\leq q^{n}$.

Pour $n=7$, $t=1$, $q=2$ : $\lvert C\rvert\leq 2^{7}/V_2(7,1)=128/8=16$. Le code de Hamming a exactement $\lvert C\rvert=2^4=16$ mots : il atteint la borne, donc il est optimal (parfait).

Projeter les mots sur les $k-1$ premières coordonnées : l'application est injective ou non ?

Deux mots égaux sur $n-d+1$ positions sont égaux (sinon $d(x,y)<d$).

Argument de comptage / d'algèbre linéaire sur les coordonnées effacées.

Effaçons les $d-1$ dernières coordonnées : l'application $C\to\mathbb{F}_q^{\,n-(d-1)}$ est injective (deux mots distincts différant seulement sur ces positions seraient à distance $\leq d-1<d$). Donc $q^{k}=\lvert C\rvert\leq q^{\,n-(d-1)}$, d'où $k\leq n-d+1$, soit $d\leq n-k+1$.

Répétition $[n,1,n]$ : $n-k+1=n-1+1=n=d$ ✓ MDS. Parité $[n,n-1,2]$ : $n-k+1=n-(n-1)+1=2=d$ ✓ MDS. (Hamming $[7,4,3]$ n'est PAS MDS : $n-k+1=4\neq 3$.)

$n=7$, $k=4$, $d=3$.

Calculer $n-k+1$.

MDS $\iff d=n-k+1$.

$n-k+1=7-4+1=4$, alors que $d=3$. On a $d=3<4=n-k+1$.

L'écart à la borne de Singleton est $n-k+1-d=1$ : le code de Hamming n'est pas MDS (il sacrifie $1$ unité de distance par rapport à l'optimum de Singleton, mais reste parfait pour la borne de Hamming).

Le simplexe a $2^3=8$ mots, dont $7$ non nuls.

Chaque coordonnée d'un mot $=$ produit scalaire d'une colonne de $H$ avec le vecteur de coefficients.

Compter combien de colonnes donnent un produit scalaire non nul.

Un mot non nul du simplexe est $y=vH$ pour $v\in\mathbb{F}_2^{3}\setminus\{0\}$ : sa $j$-ème coordonnée est $v\cdot H_j$. Pour $v\neq 0$ fixé, l'hyperplan $v^{\perp}=\{x:v\cdot x=0\}$ a $2^{2}=4$ éléments, donc il existe $8-4=4$ vecteurs $x\in\mathbb{F}_2^{3}$ avec $v\cdot x=1$ ; comme $v\cdot 0=0$, ces $4$ vecteurs sont tous non nuls, donc tous parmi les $7$ colonnes $H_j$. D'où $w(y)=4$ pour tout mot non nul.

Tous les $7$ mots non nuls ont poids $4$ : $d^{\perp}=4$. Le simplexe est un $[7,3,4]$ équidistant (tous les mots non nuls ont le même poids). Il n'est pas MDS : $n-k+1=7-3+1=5>4$.