Dénombrer les matrices génératrices d’un code

em2

Bonjour à tous

J’étudie en ce moment les codes correcteurs en licence 3.
Mon professeur nous a confié qu’un exercice intéressant aurait été de nous faire compter les matrices génératrices G’ (échelonnées réduites) d’un code C.
J’aurais aimé savoir comment m’y prendre s’il nous pose ce genre de question en examen, mais je ne sais pas par où commencer…

Quelqu'un ici aurait-il un exemple d’exercice dans ce style, ou alors une aide pour résoudre ce problème de dénombrement ?
Merci par avance pour votre aide !

biguine_equation

em2: je réponds vite fait mais j’y reviendrai.
J’imagine que tu parles d’un code linéaire… Sauf erreur, un code linéaire $C$ est un sous-espace vectoriel de $\mathbb{F}_q^n$. Il a donc une dimension $k$.
Sachant que les lignes de la $(k\times n)$-matrice génératrice  sont les bases de $C$ (i.e. les lignes sont linéairement indépendantes), le nombre de matrices génératrices d’un $(n,k)$-code sur le corps fini $\mathbb{F}_q$ est 
\begin{equation}
C_{k,n}=\frac{(q^n-1)(q^{n-1}-1)\cdots(q^{n-k+1}-1)}{(q^k-1)(q^{k-1}-1)\cdots(q-1)}
\end{equation}

biguine_equation

Le code $C$ est l’ensemble des combinaisons linéaires des lignes de la matrice génératrice $G$ \begin{equation}
C= \{uG \: | \: u \in \mathbb{F}_q^k\}
\end{equation} On peut aussi définir les éléments de $C$ comme les vecteurs du noyau d’une certaine matrice $H$ dite « matrice de parité » (parity check matrice en bon français).
$\dim(C)=k$ donc soit $(v_1, \dots, v_k)$ une base de $C$. Tout vecteur de $C$ s’écrit sous la forme $\lambda_1v_1+\dots+\lambda_kv_k, \  \lambda_i \in \mathbb{F}_q$. Donc $C$ est de cardinal $q^k$.

GaBuZoMeu

Bonsoir,

Je ne comprends pas très bien. Ètant donné une matrice $G$ quelconque sur un corps, il y a a une unique matrice échelonnée réduite $M$ équivalent à gauche à $G$ (c.--à-d. dont les lignes engendrent le même sous espace vectoriel que les lignes de $G$).

biguine_equation

GBZM: je ne suis pas sûr d’avoir compris ton incompréhension mais je crois que ce qui suit y répond: tout code linéaire, c’est-à-dire tout sous-espace engendré par une partie $S \subseteq K^n$ possède une matrice génératrice sous forme réduite échelonnée (par lignes).
Il y a donc autant de telles matrices que de bases de $\langle S \rangle$.
Réciproquement, toute matrice dont les lignes sont linéairement indépendantes est une matrice génératrice pour un certain code $C= \langle S \rangle$.

GaBuZoMeu

Non, @biguine_equation, ça ne répond pas à mon incompréhension.

Je répète: tout code linéaire $C$ a une unique matrice génératrice échelonnée réduite.

Si on veut compter les matrices génératrices de $C$ qui ne sont pas forcément échelonnées réduites, alors oui, il y en a autant que de bases de $C$ et dénombrer ces bases en fonction du cardinal du corps de base et de la dimension de $C$ est tout à fait classique.

Mais il s'agit bien dans le premier message de "compter les matrices génératrices G’ (échelonnées réduites) d’un code C." La réponse est donc 1.

S'il s'agissait de compter les codes linéaires de longueur et de dimension données, alors oui, c'est le résultat que tu donnes.