{\catcode`\^^M=\active %
  \gdef\adrbox{\catcode`\^^M=\active %
  \def^^M{\egroup\hbox\bgroup}}}
\def\adresse{\par\nobreak%
  \vskip 24pt plus 6pt minus 3pt%
  \hbox to \hsize\bgroup\hfill%
  \def\fin{\egroup\egroup\hskip2em\egroup\vfill\eject}%
  \adrbox\vbox\bgroup\hbox\bgroup}
\def\fin{\vfill\eject}

\catcode'32=9
\magnification=1200

% particularite du pilote canon

\voffset=1cm
\hoffset=0cm
%\hoffset=1cm
\font\tenpc=cmcsc10
%\font\eightpc=cmcsc8

% Charge des fontes de 8 et 6 points :
\font\eightrm=cmr8
\font\eighti=cmmi8
\font\eightsy=cmsy8
\font\eightbf=cmbx8
\font\eighttt=cmtt8
\font\eightit=cmti8
\font\eightsl=cmsl8
\font\sixrm=cmr6
\font\sixi=cmmi6
\font\sixsy=cmsy6
\font\sixbf=cmbx6

\skewchar\eighti='177 \skewchar\sixi='177
\skewchar\eightsy='60 \skewchar\sixsy='60

% Chargement des fontes AMS

\font\tengoth=eufm10
\font\tenbboard=msbm10
\font\eightgoth=eufm8
\font\eightbboard=msbm8
\font\sevengoth=eufm7
\font\sevenbboard=msbm7
\font\sixgoth=eufm6
\font\fivegoth=eufm5

\newfam\gothfam
\newfam\bboardfam

\catcode`\@=11

\def\raggedbottom{\topskip 10pt plus 36pt
\r@ggedbottomtrue}
\def\pc#1#2|{{\bigf@ntpc #1\penalty
\@MM\hskip\z@skip\smallf@ntpc #2}}

\def\tenpoint{%
  \textfont0=\tenrm \scriptfont0=\sevenrm \scriptscriptfont0=\fiverm
  \def\rm{\fam\z@\tenrm}%
  \textfont1=\teni \scriptfont1=\seveni \scriptscriptfont1=\fivei
  \def\oldstyle{\fam\@ne\teni}%
  \textfont2=\tensy \scriptfont2=\sevensy \scriptscriptfont2=\fivesy
  \textfont\gothfam=\tengoth \scriptfont\gothfam=\sevengoth
  \scriptscriptfont\gothfam=\fivegoth
  \def\goth{\fam\gothfam\tengoth}%
  \textfont\bboardfam=\tenbboard \scriptfont\bboardfam=\sevenbboard
  \scriptscriptfont\bboardfam=\sevenbboard
  \def\bboard{\fam\bboardfam}%
  \textfont\itfam=\tenit
  \def\it{\fam\itfam\tenit}%
  \textfont\slfam=\tensl
  \def\sl{\fam\slfam\tensl}%
  \textfont\bffam=\tenbf \scriptfont\bffam=\sevenbf
  \scriptscriptfont\bffam=\fivebf
  \def\bf{\fam\bffam\tenbf}%
  \textfont\ttfam=\tentt
  \def\tt{\fam\ttfam\tentt}%
  \abovedisplayskip=12pt plus 3pt minus 9pt
  \abovedisplayshortskip=0pt plus 3pt
  \belowdisplayskip=12pt plus 3pt minus 9pt
  \belowdisplayshortskip=7pt plus 3pt minus 4pt
  \smallskipamount=3pt plus 1pt minus 1pt
  \medskipamount=6pt plus 2pt minus 2pt
  \bigskipamount=12pt plus 4pt minus 4pt
  \normalbaselineskip=12pt
  \setbox\strutbox=\hbox{\vrule height8.5pt depth3.5pt width0pt}%
  \let\bigf@ntpc=\tenrm \let\smallf@ntpc=\sevenrm
  \let\petcap=\tenpc
  \normalbaselines\rm}
\def\eightpoint{%
  \textfont0=\eightrm \scriptfont0=\sixrm \scriptscriptfont0=\fiverm
  \def\rm{\fam\z@\eightrm}%
  \textfont1=\eighti \scriptfont1=\sixi \scriptscriptfont1=\fivei
  \def\oldstyle{\fam\@ne\eighti}%
  \textfont2=\eightsy \scriptfont2=\sixsy \scriptscriptfont2=\fivesy
  \textfont\gothfam=\eightgoth \scriptfont\gothfam=\sixgoth
  \scriptscriptfont\gothfam=\fivegoth
  \def\goth{\fam\gothfam\eightgoth}%
  \textfont\bboardfam=\eightbboard \scriptfont\bboardfam=\sevenbboard
  \scriptscriptfont\bboardfam=\sevenbboard
  \def\bboard{\fam\bboardfam}%
  \textfont\itfam=\eightit
  \def\it{\fam\itfam\eightit}%
  \textfont\slfam=\eightsl
  \def\sl{\fam\slfam\eightsl}%
  \textfont\bffam=\eightbf \scriptfont\bffam=\sixbf
  \scriptscriptfont\bffam=\fivebf
  \def\bf{\fam\bffam\eightbf}%
  \textfont\ttfam=\eighttt
  \def\tt{\fam\ttfam\eighttt}%
  \abovedisplayskip=9pt plus 2pt minus 6pt
  \abovedisplayshortskip=0pt plus 2pt
  \belowdisplayskip=9pt plus 2pt minus 6pt
  \belowdisplayshortskip=5pt plus 2pt minus 3pt
  \smallskipamount=2pt plus 1pt minus 1pt
  \medskipamount=4pt plus 2pt minus 1pt
  \bigskipamount=9pt plus 3pt minus 3pt
  \normalbaselineskip=9pt
  \setbox\strutbox=\hbox{\vrule height7pt depth2pt width0pt}%
  \let\bigf@ntpc=\eightrm \let\smallf@ntpc=\sixrm
  \normalbaselines\rm}

\let\bb=\bboard

\tenpoint

%���������������������� dactylographie fran�aise �����������������

\catcode`\;=\active
\def;{\relax\ifhmode\ifdim\lastskip>\z@
\unskip\fi\kern\fontdimen2 \font\kern -1.2 \fontdimen3 \font\fi\string;}

\catcode`\:=\active
\def:{\relax\ifhmode\ifdim\lastskip>\z@\unskip\fi\penalty\@M\ \fi\string:}

\catcode`\!=\active
\def!{\relax\ifhmode\ifdim\lastskip>\z@
\unskip\fi\kern\fontdimen2 \font \kern -1.1 \fontdimen3 \font\fi\string!}

\catcode`\?=\active
\def?{\relax\ifhmode\ifdim\lastskip>\z@
\unskip\fi\kern\fontdimen2 \font \kern -1.1 \fontdimen3 \font\fi\string?}

\def\^#1{\if#1i{\accent"5E\i}\else{\accent"5E #1}\fi}
\def\"#1{\if#1i{\accent"7F\i}\else{\accent"7F #1}\fi}

\frenchspacing

%���������������������� format de sortie �����������������

\newif\ifpagetitre
\newtoks\auteurcourant \auteurcourant={\hfil}
\newtoks\titrecourant \titrecourant={\hfil}

\def\appeln@te{}
\def\vfootnote#1{\def\@parameter{#1}\insert\footins\bgroup\eightpoint
  \interlinepenalty\interfootnotelinepenalty
  \splittopskip\ht\strutbox % top baseline for broken footnotes
  \splitmaxdepth\dp\strutbox \floatingpenalty\@MM
  \leftskip\z@skip \rightskip\z@skip
  \ifx\appeln@te\@parameter\indent \else{\noindent #1\ }\fi
  \footstrut\futurelet\next\fo@t}

\pretolerance=500 \tolerance=1000 \brokenpenalty=5000
\newdimen\hmargehaute \hmargehaute=0cm
\newdimen\lpage \lpage=13.3cm
\newdimen\hpage \hpage=20cm
\newdimen\lmargeext \lmargeext=1cm
\hsize=11.25cm
\vsize=18cm
\parskip 0pt
\parindent=12pt

\def\margehaute{\vbox to \hmargehaute{\vss}}%
\def\margebasse{\vss}

\output{\shipout\vbox to \hpage{\margehaute\nointerlineskip
  \corpsdepage\margebasse}
  \advancepageno \global\pagetitrefalse
  \ifnum\outputpenalty>-20000 \else\dosupereject\fi}

\def\corpsdepage{\hbox to \lpage{\hss\pagetexte\hskip\lmargeext}}
\def\pagetexte{\vbox{\makeheadline\pagebody\makefootline}}
\headline={\ifpagetitre\titleheadline \else
  \ifodd\pageno\rightheadline \else\leftheadline\fi\fi}
\def\leftheadline{\eightpoint\hfil\the\auteurcourant\hfil}
\def\rightheadline{\eightpoint\hfil\the\titrecourant\hfil}
\def\titleheadline{\hfill}
\pagetitretrue

\def\footnoterule{\kern-6\p@
  \hrule width 2truein \kern 5.6\p@} % the \hrule is .4pt high



\let\rmpc=\sevenrm
\def\pd#1#2 {\pc#1#2| }

\def\pointir{\discretionary{.}{}{.\kern.35em---\kern.7em}\nobreak
\hskip 0em plus .3em minus .4em }

\def\resume#1{\vbox{\eightpoint \pc R\'ESUM\'E|\pointir #1}}
\def\abstract#1{\vbox{\eightpoint \pc ABSTRACT|\pointir #1}}

\def\titre#1|{\message{#1}
              \par\vskip 30pt plus 24pt minus 3pt\penalty -1000
              \vskip 0pt plus -24pt minus 3pt\penalty -1000
              \centerline{\bf #1}
              \vskip 5pt
              \penalty 10000 }

\def\section#1|{\par\vskip .3cm
                {\bf #1}\pointir}

\def\ssection#1|{\par\vskip .2cm
                {\it #1}\pointir}

\long\def\th#1|#2\finth{\par\medskip
              {\petcap #1\pointir}{\it #2}\par\smallskip}

\long\def\tha#1|#2\fintha{\par\medskip
                    {\petcap #1.}\par\nobreak{\it #2}\par\smallskip}
\def\cf{{\it cf}}

\def\rem#1|{\par\medskip
            {{\it #1}\pointir}}

\def\rema#1|{\par\medskip
             {{\it #1.}\par\nobreak }}

%
\def\ieme{\raise 1ex\hbox{\pc{}i\`eme|}}
\def\omini{\raise 1ex\hbox{\pc{}o|}}
\def\emini{\raise 1ex\hbox{\pc{}e|}}
\def\ermini{\raise 1ex\hbox{\pc{}er|}}
\def\remini{\raise 1ex\hbox{\pc{}re|}}

%reference pour un article :
\def\article#1|#2|#3|#4|#5|#6|#7|
    {{\leftskip=7mm\noindent
     \hangindent=2mm\hangafter=1
     \llap{[#1]\hskip.35em}{#2}\pointir
     #3, {\sl #4}, t.\nobreak\ {\bf #5}, {\oldstyle #6},
     p.\nobreak\ #7.\par}}
%reference pour un livre :
\def\livre#1|#2|#3|#4|
    {{\leftskip=7mm\noindent
    \hangindent=2mm\hangafter=1
    \llap{[#1]\hskip.35em}{#2}\pointir
    {\sl #3}\pointir #4.\par}}
%reference complementaire :
\def\divers#1|#2|#3|
    {{\leftskip=7mm\noindent
    \hangindent=2mm\hangafter=1
     \llap{[#1]\hskip.35em}{#2}\pointir
     #3.\par}}
%
\mathchardef\conj="0365
\def\dem{\par{\it D\'emonstration}\pointir}
\def\qed{\quad\raise -2pt\hbox{\vrule\vbox to 10pt{\hrule width 4pt
\vfill\hrule}\vrule}}

\def\virg{\raise 2pt\hbox{,}}   % virgule apr�s une fraction

\def\cqfd{\penalty 500 \hbox{\qed}\par\smallskip}

\def\decale#1|{\par\noindent\hskip 28pt\llap{#1}\kern 5pt}
\def\decaledecale#1|{\par\noindent\hskip 34pt\llap{#1}\kern 5pt}
% pour les titres en deux lignes et les sections sans point-tiret :
\def\titrea#1|#2|{\message{#1 #2}
  \par\vskip.5cm plus .1cm minus .1cm\penalty -1000
  \centerline{\bf #1}
  \centerline{\bf #2}
  \vskip 5pt
  \penalty 10000 }
\def\sectiona#1|{\par\vskip .3cm
  {\bf #1.}
  \par\nobreak\vskip 3pt }
\def\ssectiona#1|{\par\vskip .2cm
  {\it #1.}
  \par\nobreak\vskip 2pt }

\catcode`\@=12


\pageno=71
\auteurcourant={U. OBERST AND A. D\"UR}
\titrecourant={MAXIMALE CODE}

\eightpoint
\leftline{Publ. I.R.M.A. Strasbourg, $\oldstyle 1984$, 229/S--08}
\leftline{Actes 8\emini\ S\'eminaire Lotharingien, p. 71--74}

\tenpoint
\let\it=\sl

\vglue 1.5cm
\centerline{{\bf DIE KONSTRUKTION ALLER MAXIMALEN CODE}}
\vskip 5pt
\centerline{{\bf MIT HILFE VON MDS-CODEN}}
\vskip 2.8mm
\centerline{\sevenrm VON}
\vskip 2.8mm
\centerline{{\petcap Ulrich} OBERST {\sevenrm UND}
{\petcap Arne} D\"UR}
\vskip 3mm
\section Einf\"uhrung (vergl. {\rm [1]}) und Motivation|Ein
{\it linearer} Code der L\"ange $n$ \"uber einem endlichen K\"orper
$F$ ist ein Unterraum $C$ von $F^n$. Das f\"ur die Anwendungen
wichtigste Beispiel eines solchen $F$ ist das bin\"are ``Alphabet''
$F=\{0,1\}$. Bezeichne $\dim(_FC)$ die Dimension von $C$.
Auf $F^n$ betrachtet man die Hamming-``Norm''

\vskip 5pt
\centerline{$\left\|x\right\|={}$Anzahl der von Null 
verschiedenen}
\centerline{Komponenten eines Vektors
$x=(x_1,\ldots,x_n)\in F^n$.} \vskip 5pt
\noindent 
Die normerhaltenden linearen Automorphismen von $F^n$ hei\ss en
Isometrien. Man kann die algebraische Codierungstheorie als Geometrie
bez\"uglich der Hammingmetrik oder als Invariantentheorie der Isometriegruppe
be\-trach\-ten.

Die Zahl
  $$d(C)=\min\{\left\|x\right\|\;;\;x\in D,\;x\not= 0\}$$
hei\ss t die {\it Distanz} des Codes $C$. Es gilt
  $$\dim(C)+d(C)\le n+1.\leqno(1)$$
Der Code $C$ hei\ss t {\it MDS-Code}, falls in (1)
die Gleichheit gilt. Der Code $C$ hei\ss t {\it maximal},
falls er unter allen Coden $\widetilde C\subseteq F^n$ mit
$d(\widetilde C)\ge d(C)$ maximal (bez\"uglich der Inklusion) ist.

Das Ziel der algebraischen Codierungstheorie ist es,
``gute'' (z.B. maxi\-male) Code zu finden, f\"ur welche sowohl die
Dimension als auch die Distanz m\"oglichst gro\ss\ sind.
Informationstheoretisch bedeutet dies, da\ss\ man mit Hilfe
dieser Code Nachrichten sowohl schnell wie m\"oglichst
fehlerfrei \"uber einen gest\"orten symmetrischen Kanal
\"ubertragen kann. Eine bedeutende Klasse von ``guten'' Coden
ist die der  {\it alternanten}, insbesondere der {\it Goppa} Code
: Seien $k$ und $n$ nat\"urliche Zahlen mit $2\le k\le n-2$.
Seien $K$ ein endlicher Erweiterungsk\"orper von $F$ mit
wenigstens $n$ Elementen und $a_1,\ldots,a_n$ $n$ paarweise
verschiedene Elemente von $K$. Die Vektoren
  $$(a_1^i,\ldots, a_n^i),\qquad i=0,\ldots,k-1$$
sind die Basis eines MDS-Codes der Dimension $k$ und Distanz
$d=n+1-k$ \"uber $K$. Jeder zu einem solchen isometrische Code
$Z\subseteq K^n$ hei\ss t {\it alternanter MDS-Code}. Der Code
  $$C:=F^n\cap Z$$
hat dann ebenfalls wenigstens die Distanz $d$, kann aber sehr klein sein.
Bei {\it geeigneter} Wahl von $Z$ erh\"alt man aber ``gute'' Code.
Die so erhaltenen Code hei\ss en {\it alternant}.

Die folgenden S\"atze zeigen, da\ss\ man in der Form
$C=Z\cap F_n$ {\it alle} maximalen Code erh\"alt, wenn man von
geeigneten MDS-Coden $Z$ ausgeht, und da\ss\ 
die Klasse der alternanten Code ``sehr klein'' ist.

\vskip 7pt
{\bf Ergebnisse.}

\th Satz 1|Seien $C\subseteq F^n$ ein Code der Dimension $l$ und
Distanz $d$ und $K$ ein endlicher Oberk\"orper von $F$ mit
wenigtens ${n-1\choose d-1}+{n-l-2\choose d-1}+1$
Elementen. Dann gibt es einen MDS-Code $Z\subseteq K^n$ der
gleichen Distanz $d$ mit
  $$C\subseteq Z\cap F^n.$$
Ist speziell $C$ maximal, so ist $C=Z\cap F^n$.
\finth

Die im vorigen Satz ben\"otigten MDS-Code $Z$ erh\"alt man auf
folgende Weise :
Sei weiter $2\le k\le n-2$. Ist
  $$B=\Bigl(B(i,j)\;;\;i=1,\ldots,k,\;j=k+1,\ldots,n\Bigr),
\quad B(i,j)\in K,$$
eine $k\times (n-k)$-Matrix mit Koeffizienten in $K$, so sei  
  $$Z(B)=\{x=(x_1,\ldots,x_n)\in K_n\;;\;
(x_1,\ldots,x_k)B=(x_{k+1},\ldots,x_n)\}.$$

\th Satz 2|Bezeichnungen wie oben. Die Abbildung
$B\rightarrow Z(B)$ induziert eine Bijektion der Menge
${\bf V}(K)$ aller $k\times (n-k)$-Matrizen mit Koeffizienten in $K$,
deren quadratische Unterdeterminanten ungleich $0$ sind, auf
die Menge ${\bf C}(K)$ aller MDS-Code der Dimension $k$ 
in $K^n$.
\finth

Wie uns die Kollegen \pd HEISE (M\"unchen) und \pd HERGERT
(Darmstadt) mitteilten, ist eine Version dieses Satzes bekannt
und insbesondere ent\-hal\-ten in dem Buch~[2]. Dieses war uns
bis jetzt nicht zug\"anglich. Von Interesse ist nach \pc SATZ|~1
die Dimension von $F_n\cap Z(B)$.

\th Satz 3|Sei $F\subset K$ eine Erweiterung der Dimension $m$ und
habe $F$ $q$ Elemente. Seien $Z=S(B)\subseteq K^n$ wie in
{\pc SATZ|~$2$} und $C:=Z\cap F^n$ wie in {\pc SATZ|~$1$}
definiert. Dann ist
  $$\dim(_FC)=k-{\rm Rang}(B^{(1)}-B,\ldots, B^{(m-1)}-B).\leqno(2)$$
Dabei ist
  $$B^{(l)}=\Bigl(B(i,j)^{q(l)};\;i=1,\ldots,k,\;
j=k+1,\ldots,n\Bigr),\quad q(l)=q^l.$$
Die Matrix auf der rechten Seite von $(2)$ hat die Gestalt
$k\times(m-1)(n-k)$.
\finth

Die Menge ${\bf V}(K)$ in \pc SATZ|~2 ist auf offensichtliche
Weise die Menge der $K$-rationalen Punkte der $k(n-k)$-{\it
dimensionalen affinen algebraischen Mannigfaltigkeit} ${\bf
V}(\widetilde F)$, wobei $\widetilde F\supseteq K$ der
algebraische Abschlu\ss\ von $F$ ist. Durch Strukturtransport
bildet dann auch die Menge  ${\bf C}(\widetilde F)$ der MDS-Code
der Dimension $k$ in $\widetilde F^n$ eine solche
Mannigfaltigkeit und ${\bf C}(K)$ ist deren Menge der
$K$-rationalen Punkte. Bezeichne ${\rm Alt}(K)$ die Menge der
alternanten MDS-Code der Dimension $k$ in $K^n$. Der n\"achste
Satz zeigt, da\ss\ eine ``kleine'' Untermannigfaltigkeit von ${\bf
C}$ ist. Sei
  $$Z=Z(B)\subseteq K^n,\quad B\in {\bf V}(K),$$
ein MDS-Code der Dimension $k$ in $K^n$. Betrachte die zugeh\"orige
nor\-ma\-li\-sierte Matrix
  $$\displaylines{A=\bigl(A(i,j)\;;\;i=2,\ldots,k,\;
j=k+2,\ldots,n\bigr),\cr
A(i,j):={B(i,j)\,B(1,k+1)\over B(i,k+1)\,B(1,j)}\cr}$$
und die $(k-2)(n-k-2)$ Relationen
  $$\displaylines{(3)\quad\qquad{A(i,j)-1 
\over  A(i,j)A(2,j)^{-1}-1}=
{A(i,j+1)-1 \over  A(i,j+1)A(2,j+1)^{-1}-1},\hfill\cr
i=3,\ldots,k,\quad j=k+2,\ldots,n.\cr}$$

\th Satz 4|Voraussetzungen und Bezeichnungen wie oben. Der Code
$Z(B)$ is genau dann ein alternanter MDS-Code, wenn die
Gleichungen $(3)$ erf\"ullt sind. Die Menge ${\rm Alt}(\widetilde
F)$ ist eine $(2n-4)$-dimensionale abgeschlossene
Untermannigfaltigkeit von ${\bf C}(\widetilde F)$. Insbesondere
ist
  $${\rm Alt}(\widetilde F)\mathrel{\mathop{\subset }
\limits_{\textstyle\not= }}
{\bf C}(\widetilde F)\qquad \hbox{\sl f\"ur}\ 3\le k\le n-3.$$
Dies bedeutet, da\ss\ es f\"ur $3\le k\le n-3$ sehr wenige 
alternante Code gibt oder, anders, da\ss\ die Alternanz keine
generische Eigenschaft von Coden ist.
\finth

Die S\"atze 1 und 4 machen die Suche nach neuen Klassen
von MDS-Coden auf neue Weise interessant.

\vfill\eject

\vglue 44pt
\eightpoint
\centerline{LITERATUR}
\vskip 10pt
\livre 1|\pd VAN \pd LINT (J.H.)|Introduction to coding
theory|Berlin, Springer-Verlag, $\oldstyle 1982$|
\livre 2|\pd MAC \pd WILLIAMS (F.J.) and \pd SLOANE
(N.J.A.)|The theory of error-correcting
codes|North-Holland, $\oldstyle 1977$|

\tenpoint
\adresse
Ulrich {\petcap Oberst} u. Arne {\petcap D\"ur},
Institut f\"ur Mathematik
der Universit\"at,
Innrain 52,
A-6020 Innsbruck.

\fin

\bye
