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.
\(V_1\) est la matrice de l’équation \(\sum x_i=0\) qui définit \(x_8\)
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\)
tandis qu’une génératrice est
Si vous suivez...
Si \(G\) et \(V\) sont génératrice et vérificatrice de \(C\), que vaut \(G^tV\) ?
\(0\)
\(I_k\)
\(I_{n-k}\)
Formes systématiques¶
Une matrice génératrice de la forme
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
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.