Représentations matricielles

Soit \(C\) un \([n,k]\)-code. On a deux manières de représenter le sous-espace vectoriel \(C\)

  • via une base formée de \(k\) vecteurs

  • via un système de \(n-k\) équations linéaires

Dans tout ce qui suit, on représente les vecteurs en ligne.

Définition

On appelle matrice génératrice de \(C\) une matrice \(G\in M_{k,n}(\F_q)\) dont les lignes forment une base de \(C\).

En d’autres termes, \(C=\F_q^kG=\set{mG,m\in\F_q^k}\).

Définition

On appelle matrice vérificatrice de \(C\) une matrice \(V\in M_{n-k,n}(\F_q)\) telle que \(C=\ker(V)\).

En d’autres termes, \(c\in C\) si et seulement si \(V^tc=0\).

Exemples

Pour le code de parité \(C_1\), on obtient \(G_1\) en prenant l’image de la base canonique.

\[G_1 = \begin{bmatrix} 1&0&0&0&0&0&0&1\\ 0&1&0&0&0&0&0&1\\ 0&0&1&0&0&0&0&1\\ 0&0&0&1&0&0&0&1\\ 0&0&0&0&1&0&0&1\\ 0&0&0&0&0&1&0&1\\ 0&0&0&0&0&0&1&1\\ \end{bmatrix}\]

\(V_1\) est la matrice de l’équation \(\sum x_i=0\) qui définit \(x_8\)

\[V_1=\begin{bmatrix}1&1&1&1&1&1&1&1\end{bmatrix}\]

Le code par triple vérification \(C_2\) est défini par les équations \(x_4=x_2+x_3\), \(x_5=x_1+x_3\), \(x_6=x_1+x_2\), d’où la matrice vérificatrice \(V_2\)

\[V_2=\begin{bmatrix} 0&1&1&1&0&0\cr 1&0&1&0&1&0\cr 1&1&0&0&0&1\cr \end{bmatrix}\]

tandis qu’une génératrice est

\[G_2=\begin{bmatrix} 1&0&0&0&1&1\cr 0&1&0&1&0&1\cr 0&0&1&1&1&0\cr \end{bmatrix}\]

Si vous suivez...

Si \(G\) et \(V\) sont génératrice et vérificatrice de \(C\), que vaut \(G^tV\) ?

  1. \(0\)

  2. \(I_k\)

  3. \(I_{n-k}\)

Formes systématiques

Une matrice génératrice de la forme

\[G = \left(I_k A\right), A\in M_{k,n-k}(\F_q)\]

est dite sous forme systématique : cela correspond au fait que le code consiste à concaténer des bits de contrôle au message initial.

Proposition

Si \(G=\left(I_k A\right)\) est génératrice du \([N,k]\)-code \(C\), alors

\[V = \left(-^tA I_{n-k}\right)\]

est vérificatrice de \(C\)

Démonstration

en effet elle est de rang \(n-k\) et vérifie \(G^tV=0\).

Proposition

Quitte à changer l’ordre des indices, on peut toujours déterminer une matrice génératrice sous forme systématique.

Démonstration

On réalise un pivot de Gauss sur les lignes, en s’autorisant à décaler les colonnes.

Géométriquement, cela correspond au fait qu’il existe un supplémentaire \(F\) de \(C\) engendré par des vecteurs de la base canonique qu’on peut renuméroter \(e_{n-k+1},\dots e_n\), auquel cas \(C\) est engendré par les projetés de \(e_1,\dots e_k\) parallèlement à \(F\).

Vérificatrice et distance minimale

Proposition

Soit \(C\) un code de matrice vérificatrice \(V\), et soit \(d>0\) minimal tel qu’il existe \(d\) colonnes de \(V\) liées. Alors \(d(C)=d\).

Démonstration

C’est une reformulation : \((x_1,\dots x_n)\in C\) ssi \(Vx=\sum x_i V_i=0\), donc \(C\) a un mot de poids \(d\) s’il existe \(d\) colonnes liées.

Remarque

Comme tout ensemble de plus de \(n-k\) colonnes est nécessairement lié dans \(\F_q^{n-k}\), on retrouve en particulier la borne de Singleton.