\documentclass[XUPS,XML,SOM,Unicode,francais, NoFloatCountersInSection]{cedram}
\usepackage{xups93-01}
\setcounter{tocdepth}{2}
%\XUPScorrections

\begin{document}
\frontmatter

\title{Codes géométriques}

\author[\initial{M.} \lastname{Martin-Deschamps}]{\firstname{Mireille} \lastname{Martin-Deschamps}}

\address{URA 762 du C.N.R.S., Département de Mathématiques et Informatique, Ecole Normale Supérieure,
45, rue d'Ulm, 75005 Paris, France}

\thanks{Journées X-UPS 1993. Codes géométriques algébriques et arithmétique sur les corps finis. Prépublication du Centre de mathématique de l'École polytechnique, 1993}

\maketitle
\vspace*{-\baselineskip}
\tableofcontents
\mainmatter

Les théorèmes généraux de théorie des codes qui ont
été montrés par Shannon assurent l'existence de codes très
performants (en ce sens qu'ils atteignent la borne de Varshamov-Gilbert
$$\textstyle
R = 1-\delta \log_{q}(q-1)+\delta\log_{q}\delta+ (1-\delta)\log_{q}(1-\delta)
$$
où $R$ et $\delta$ sont les paramètres asymptotiques du code).

Malheureusement, ces théorèmes ne fournissent aucune indication sur la manière effective de construire de tels codes. Un pas important dans cette direction a été fait avec la construction
des codes géométriques, construction qui utilise les objets et les
méthodes de la géométrie algébrique, et qui permet de retrouver les résultats prédits par la théorie.

\section{Exemple: Code de Reed-Solomon sur \texorpdfstring{$\FF_{q}$, $q=p^{m}$}{F}}

On note $(0,\alpha_{1},\ldots,\alpha_{q-1})$ les éléments de $\FF_{q}$. Par exemple, si $\alpha$ est un élément primitif, on pourra choisir $\alpha_{i}=\alpha^{i-1}$ pour $i=1,\ldots,q-1$.

Soit $\delta$ un entier compris entre 2 et $q-1$. Le code de Reed-Solomon sur
$\FF_{q}$ de paramètre $\delta$ est défini par la matrice de contrôle de
parité:
$$
H=\left(
\begin{array}{ccc}
\alpha_{1}&\cdots &\alpha_{q-1}\\
\vdots & &\vdots\\
\alpha_{1}^{\delta-1}&\cdots &\alpha_{q-1}^{\delta-1}
\end{array}
\right)
$$
Autrement dit, les mots du code sont les $q-1$-uples $(a_{1},\ldots,a_{q-1})$ de
$\FF_{q}^{q-1}$ tels que
$$\sum^{q-1}_{i=1}\alpha^{j}_{i}a_{i}=0
$$
pour $j=1,\ldots,\delta-1$. C'est un code de longueur $n=q-1$, de dimension $k=n-\delta+1$.

Un encodeur peut être défini de la manière suivante: on
considère l'espace vectoriel $\FF_{q}[x]_{k-1}$ des polynômes en une variable de degré $\leq k-1$ sur $\FF_{q}$, et l'application
linéaire d'\og évaluation:\fg
\begin{align*}
\FF_{q}[x]_{k-1}& \longrightarrow \FF_{q}^{n}\qquad n=q-1\\
f&\longmapsto (f(\alpha_{1}),\ldots,f(\alpha_{n})).
\end{align*}
En effet, on vérifie que c'est une injection, que l'image est contenue dans le code, donc lui est égale pour des raisons de dimension.
On peut alors calculer facilement la distance minimale $d$: un polynôme de degré $\leq k-1$ ayant au plus ($k-1$) zéros, le poids d'un mot du code est $\geq n-k+1=\delta$, donc on a: $d=\delta$.

\begin{remarque*}
Ces codes sont effectivement utilisés dans la pratique, par
exemple on utilise un Reed-Solomon sur $\FF_{64}$ pour corriger les informations contenues dans les disques numériques audio.
\end{remarque*}

Afin de généraliser cette construction, on va en donner une
interprétation un peu différente:

Soit $X=\PP^{1}_{\FF_{q}}$ la droite projective sur $\FF_{q}$. On peut regarder
$(\alpha_{1},\ldots,\alpha_{q-1})$ non plus comme des éléments de $\FF_{q}$, mais comme des
points rationnels de $X$. On note $P_{i}=(\alpha_{i},1)$ pour $i=1,\ldots,q-1$ et
$P_{\infty} =(1,0)$.

Un polynôme de $\FF_{q}[x]$ définit une fonction rationnelle sur $X$, ayant
en $P_{\infty}$ un pôle d'ordre égal à son degré. En
particulier, on identifie ainsi l'ensemble $\FF_{q}[x]_{k-1}-\{0\}$ avec
l'ensemble des fonctions rationnelles $f$ non nulles sur $X$ telles que le
diviseur $(f)+(k-1) P_{\infty}$ soit positif. Autrement dit, on a un isomorphisme linéaire:
\[
\FF_{q}[x]_{k-1} \isom H^{0}(X,\cO_{X}((k-1)P_{\infty})).
\]
On va alors pouvoir définir les codes géométriques.

\section{Codes géométriques de Goppa}

Soient $X$ une courbe lisse et projective sur $\FF_{q}$, de genre $g$, $(D,G)$
un couple de diviseurs sur $X$ satisfaisant les conditions suivantes:
\[\tag{$*$}
\begin{cases}
D=P_{1}+\cdots+P_{n}\quad\mbox{où $P_{1},\ldots, P_{n}$ sont}\\[-3pt]
\hspace*{5cm}\text{$n$ points distincts de $X(\FF_{q})$}\\
G > 0\\
\supp D\cap \supp G=\emptyset.
\end{cases}
\]

On considère l'application linéaire d'\og évaluation\fg:
\begin{align*}
H^{0}(X,\cO_{X}(G)) &\To{\varphi} \FF_{q}^{n}\\
f&\mto (f(P_{1}),\ldots,f(P_{n})).
\end{align*}
Elle est bien définie car toute fonction rationnelle $f\neq0$ qui
vérifie $(f)+G\geq 0$ n'a pas de pôle en $P_{1},\ldots,P_{n}$.
L'image de $\varphi$ est un code sur $\FF_{q}$, noté $C_{L}$, dont on va calculer les paramètres asymptotiques en utilisant des résultats de
géométrie algébrique.
\begin{prop}
Soit $[n,k,d]$ le type de $C_{L}$. Si $\deg G<n$, on a:
\begin{itemize}
\item
$k\geq \deg G+1-g$ avec égalité si $\deg G>2g-2$,
\item
$d\geq n-\deg G$.
\end{itemize}
\end{prop}

\begin{proof}
Soit $f\not=0$ qui vérifie les conditions:
$$
(f)+G\geq 0 \qquad f(P_{i})=0\qquad i=1,\ldots,n.
$$
Alors, puisque les supports de $D$ et $G$ sont distincts, on a aussi
$$
(f)+G-D\geq 0\qqbox{donc} \deg G\geq \deg D=n
$$
donc si on a $\deg G<n$, $\varphi$ est injective.

D'après le théorème de Riemann-Roch, on a:
$$
h^{0}(\cO_{X}(G))=\deg G+1-g+h^{0}(\omega_{X}\otimes \cO_{X}(-G))
$$
où $\omega_{X}$ est le faisceau des formes différentielles sur $X$,
$$
\deg(\omega_{X}\otimes \cO_{X}(-G))=2g-2-\deg G
$$
d'où l'assertion sur $k$.

Soit $f\not=0$, $f\in H^{0}(\cO_{X}(G))$, et $w(f)$ le poids de $\varphi(f)$. Il existe des indices $i_{1},\ldots,i_{n-w(f)}$ tels que:
$$
f(P_{i_{1}})=\cdots=f(P_{i_{n-w(f)}})=0
$$
donc le diviseur $(f)+G-(P_{i_{1}}+\cdots+P_{i_{n-w(f)}})$ est $\geq 0$, ainsi que son degré, d'où:
\begin{align*}
\deg G &\geq n-w(f),\\
w(f) &\geq n-\deg G.
\end{align*}
Pour obtenir une matrice génératrice, on choisit une base
$(f_{1},\ldots,f_{\ell})$ de $H^{0}(\cO_{X}(G))$, et on obtient:
\[
\begin{pmatrix}
f_{1}(P_{1}) &\cdots &f_{1}(P_{n})\\
\vdots & &\vdots \\
f_{\ell}(P_{1}) &\cdots &f_{\ell}(P_{n})
\end{pmatrix}.
\qedhere
\]
\end{proof}

\begin{exemple*}
Code sur la cubique d'équation:
$$
X^{3}+Y^{3}+Z^{3}=0\qqbox{sur} \FF_{4}=\{0,1,\alpha,\alpha^{2}\}.
$$
Elle est lisse de genre 1, elle a 9 points rationnels, dont 3 à l'infini.
$$\arraycolsep4.5pt
\begin{array}{cccccccccc}
&P_{1} &P_{2} &P_{3} &P_{4} &P_{5} &P_{6} &P_{7} &P_{8} &P_{9}\\
X &0 &0 &0 &\alpha^{2} &\alpha &1 &\alpha^{2} &\alpha &1\\
Y &\alpha^{2} &\alpha &1 &0 &0 &0 &1 &1 &1\\
Z &1 &1 &1 &1 &1 &1 &0 &0 &0
\end{array}
$$
On considère alors les diviseurs:
\begin{align*}
D&=P_{1}+\cdots+ P_{8},\\
G&=3P_{9}.
\end{align*}
Puisque $0<\deg G<8$, on a $h^{0}(\cO_{X}(G))=3$, donc il faut trouver 3 éléments indépendants de $H^{0}(\cO_{X}(G))$. On choisit
\begin{align*}
f&=1 &(f)&=0\\
g&={X\over X+Y} &(g)&=P_{1}+P_{2}+P_{3}-3P_{9}\\
h&={X\over X+Y} &(h)&=P_{1}+P_{2}+P_{3}-3P_{9}.
\end{align*}
On obtient alors la matrice génératrice:
$$\arraycolsep4.5pt
\begin{pmatrix}
1 &1 &1 &1 &1 &1 &1 &1\\
\alpha &\alpha^{2} &1 &\alpha &\alpha^{2} &1 &0 &0\\
0 &0 &0 &1 &1 &1 &\alpha &\alpha^{2}
\end{pmatrix}
$$
C'est un code de type [8,3,5] sur $\FF_{4}$.
\end{exemple*}

\begin{remarque*}
La courbe elliptique considérée est un cas particulier
de \og courbe d'Hermite\fg sur $\FF_{q}$. Lorsque $q$ est un carré et $d=\sqrt q +1$, la courbe d'Hermite est la courbe $X$ d'équation: $X^{d}+Y^{d}+Z^{d}=0$. C'est une courbe lisse de genre $$g={(d-1)(d-2)\over2}={q-\sqrt q\over2}.$$
Il est facile de voir qu'une telle courbe a $q\sqrt q +1$ points rationnels,
donc qu'elle atteint la borne de Weil:
$$
\# X(\FF_{q})\leq q+1+2g\sqrt q.
$$
\end{remarque*}

Il existe une deuxième manière d'associer à un couple de diviseurs
$(D,G)$ qui vérifie les conditions $(\ast)$ un code linéaire sur
$\FF_{q}$.
On considère l'application linéaire \og résidu\fg:
\begin{align*}
H^{0}(\omega_{X}\otimes \cO_{X}(D-G))&\To{\psi} \FF^{n}_{q}\\
\omega&\mto (\Res_{P_{1}}(\omega),\ldots,\Res_{P_{n}}(\omega)).
\end{align*}
L'image de $\psi$ est un code sur $\FF_{q}$, noté $C_{\Omega}$.

\begin{prop}
Soit $[n,k',d']$ le type de $C_{\Omega}$. Si $2g-2<\deg G$, on a:
\begin{itemize}
\item
$k'\geq n-\deg G-1+g$ avec égalité si $\deg G<n$,
\item
$d'\geq \deg G-2g+2$.
\end{itemize}
\end{prop}

\begin{proof}
Soit $\omega\not=0$ qui vérifie les conditions:
$$
(\omega)+D-G\geq 0 \qqbox{et}\Res_{P_{i}}\omega=0\qquad i-1,\ldots,n.
$$
Alors $\omega$ n'a pas de pôle en $P_{1},\ldots,P_{n}$, donc on a aussi:
$$
(\omega)-G\geq 0\qqbox{et} \deg G\leq 2g-2.
$$
Donc si on a $\deg G>2g-2$, $\psi$ est injective.

D'après le théorème de Riemann-Roch, on a:
$$
h^{0}(\omega_{X}\otimes \cO_{X}(D-G))=-\deg(G-D)+g-1+h^{0}(\cO_{X}(G-D)),
$$
d'où l'assertion sur $k'$.

Enfin, soit $\omega\not=0$, $\omega\in H^{0}(\omega_{X}\otimes \cO_{X}(D-G))$ et $w(\omega)$ le
poids de $\psi(\omega)$. Il existe des indices $i_{1},\ldots,i_{w(\omega)}$ tels que le diviseur $(\omega)+P_{i_{1}}+\cdots+P_{i_{w(\omega)}}-G$ soit positif ainsi que son degré, d'où:
\[
w(\omega)\geq \deg G+2-2g.\qedhere
\]
\end{proof}

Le fait que les démonstrations de ces deux propositions soient très
voisines n'est pas étonnant, car ces deux codes sont liés. Plus
précisément, on a le résultat suivant:
\begin{prop}
Si $2g-2<\deg G<n$, les codes $C_{L}$ et $C_{\Omega}$ sont
duaux l'un de l'autre.
\end{prop}

\begin{proof}
Soit $f\in H^{0}(\cO_{X}(G))$, $\omega\in H^{0}(\omega_{X}\otimes \cO_{X}(D-G))$,
alors
$$
f\omega\in H^{0}(\omega_{X}\otimes \cO_{X}(D))
$$
donc les pôles de $f\omega$ sont contenus dans le support de $D$.
Mais on a:
$$
(\varphi(f)\mid \psi(\omega)) = \sum^{n}_{i=1} f(P_{i})\Res_{P_{i}}\omega=\sum^{n}_{i=1}\Res_{P_{i}}(f\omega)=0
$$
d'après la formule des résidus. Donc $C_{L}$ et $C_{\Omega}$ sont orthogonaux. Dans le cas $2g-2<\deg G<n$, pour
des raisons de dimension, $C_{\Omega}$ {\em est} l'orthogonal de $C_{L}$.
\end{proof}

\begin{definit}
$C_{L}$ et $C_{\Omega}$ sont les codes
géométriques définis par le couple de diviseurs $(D,G)$.
\end{definit}

\pagebreak[2]
\skpt
\begin{remarques*}
\begin{enumerate}
\item
La dualité entre $C_{L}$ et $C_{\Omega}$ est une traduction
de la dualité de Serre sur $X$.
\item
Actuellement, on étudie plutôt les codes $C_{L}$.
Historiquement, les codes $C_{\Omega}$ ont été construits d'abord, sans doute parce que Goppa, qui les a inventés, n'est pas à l'origine un géomètre, ni un algébriste. La définition de $C_{\Omega}$ pose moins de problèmes que celle de $C_{L}$, car le résidu d'une forme différentielle existe toujours, alors qu'il n'en est pas de même de la valeur d'une fonction rationnelle, et il faut des outils algébriques pour contrôler les domaines de définition des fonctions rationnelles.
\end{enumerate}
\end{remarques*}

\section{Applications}

On dispose maintenant d'une nouvelle famille très vaste de codes
linéaires. Les problèmes qui les concernent se ramènent à des
problèmes d'arithmétique et de géométrie algébrique
(arithmétique en ce qui concerne les points rationnels d'une courbe sur un corps fini, géométrique pour la construction des systèmes
linéaires de diviseurs).

Nous allons montrer que la famille des codes géométriques a de bonnes propriétés asymptotiques.

Soit $X$ une courbe projective et lisse de genre $g$ sur $\FF_{q}$, $C_{L}$
un code obtenu en considérant un couple $(D,G)$ tel que $D$ contienne tous
les points rationnels de $X(\FF_{q})$, $[n,k,d]$ son type. On a:\vspace*{-3pt}\enlargethispage{.5\baselineskip}
\begin{itemize}
\item
$k\geq \deg G+1-g$,
\item
$d\geq n-\deg G$,
\end{itemize}
d'où\vspace*{-3pt}
$${k\over n}+{d\over n}\geq 1+{1-g\over n}
$$
avec $n=\# X(\FF_{q})=N_{q}(x)$.

On pose alors
\begin{align*}
N_{q}(g)&=\max\left\{ N_{q}(X)\mid X\mbox{ proj. lisse, genre $g$ sur
$\FF_{q}$}\right\},\\
A(q)&= \limsup {N_{q}(g)\over g}.
\end{align*}
On veut borner $A(q)$. Pour cela, on peut utiliser la borne
de Weil:
$$
|N_{q}(x)-(q+1)|\leq 2g\sqrt q
$$
et on obtient $A(q)\leq 2\sqrt q$.

Mais cette borne peut être améliorée:
\begin{th*}
On a $A(q)\leq\sqrt q-1$. De plus, si $q$ est un carré, on a
$A(q)=\sqrt q-1$.
\end{th*}

L'inégalité a été montrée par Drinfeld et Vladut.
L'égalité a été prouvée par Ihara, puis indépendamment
par Tsfasman, Vladut et Zink, qui en ont aussi déduit, en utilisant des
courbes modulaires, qu'il existe une famille de codes géométriques sur $\FF_{q}$ ayant une complexité polynomiale de construction et dépassant la borne de Varshamov-Gilbert, si $q$ est un carré $\geq 49$.

\section{Généralisation}

Cette construction peut être étendue à des variétés
algébriques de dimension supérieure. Pour le moment, ces techniques
n'ont pas permis de construire de \og meil\-leurs\fg codes que sur les courbes, mais on a pu dans certains cas, donner ainsi une interprétation géométrique de codes déjà connus. C'est le cas des codes de Reed-Muller:

\subsubsection*{Codes de Reed-Muller projectifs}
Soit $X=\PP^{r}$ l'espace projectif de dimension $r$ sur $\FF_{q}$. Soient $V$ l'ensemble des points rationnels de $X$, et $N$ son cardinal. On note $U_{i}$ l'ouvert de $X$ défini par $X_{i}\not=0$. On obtient ainsi un recouvrement ouvert de $X$: $X=\bigcup^{r}_{i=0}U_{i}$. On a:\vspace*{-3pt}
\begin{align*}
N &=\# X=\# U_{0}+\#(U_{1}-U_{0})+\cdots +\#
\Bigl( U_{r}-\bigcup^{r-1}_{i=0}U_{i}\Bigr) \\
&= q^{r}+q^{r-1}+\cdots +1\\
&= {q^{r+1}-1\over q-1}.
\end{align*}

Soit $\cL=\cO_{P}(1)$ le faisceau inversible correspondant aux diviseurs
hyperplans.

Pour $m\geq 1$, les sections globales de $\cL^{m}$ s'identifient aux
polynômes homogènes de degré $m$ en $X_{0},\ldots, X_{r}$.

Pour tout point $x$ de $V$, on peut définir une application linéaire
d'évaluation en $x$ $\varphi_{x}: H^{0}(X,\cL^{m})\to \FF_{q}$ de la
manière suivante:
\begin{enumerate}
\item[]
Si $x\in U_{0}$, $\varphi_{x}(f)=f(x)/x_{0}^{m}$
\item[]
Si $x\in U_{1}-U_{0}$, $\varphi_{x}(f)=f(x)/x_{1}^{m}$
\item[]
Si $x\in U_{2}-(U_{1}\cup U_{0})$, $\varphi_{x}(f)=f(x)/x_{2}^{m}$
\item[]
$\dots$
\end{enumerate}
On a alors une application linéaire d'évaluation:\vspace*{-3pt}
\begin{align*}
H^{0}(X,\cL^{m})&\To{\psi} \FF^{N}_{q}\\
f&\mto (\varphi_{x_{1}}(f),\ldots,\varphi_{x_{N}}(f))
\end{align*}
dont l'image est un code de Reed-Muller projectif.

On montre par récurrence sur $r$, que $\varphi$ est une injection si $m<q$. Dans ce cas, puisqu'un polynôme homogène a au plus $m(q^{r}-1)/(q-1)$ zéros dans $\PP^{r}(\FF_{q})$, les paramètres du code sont les suivants:
\[
\begin{cases}
n &=\displaystyle{q^{r+1}-1\over q-1}\\[10pt]
k &= \displaystyle\binom{r+m}{r}\\[12pt]
d &\geq\displaystyle{q^{r+1}-1-m(q^{r}-1)\over q-1}\quad \mbox{avec égalité quand $m=1$.}
\end{cases}
\]

\backmatter
\end{document}

