\documentclass[12pt]{amsart}
\headheight=8pt     \topmargin=0pt
\textheight=624pt   \textwidth=432pt
\oddsidemargin=18pt \evensidemargin=18pt
\renewcommand{\baselinestretch}{0.99}

\def\today{December 11, 1998}
%\usepackage{amssymb}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{co}[theorem]{Corollary}
\newtheorem{pr}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
   
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

%\newcommand{\mod}{{\rm mod}}
\newcommand{\F}{{\mathbb F}}
\newcommand{\K}{{\mathbb K}}
\newcommand{\Z}{{\mathbb Z}} 
\newcommand{\C}{{\mathcal C}} 
\newcommand{\wt}{{\rm wt}} 
\newcommand{\rank}{{\rm rank}\,}
\newcommand{\eqr}[1]{~\mbox{$(${\rm \ref{#1}}$)$}}
\newcommand{\Section}[1]{\section{#1}\setcounter{equation}{0}}
\renewcommand{\theequation}{\thesection.\arabic{equation}}


 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document} 
\title{Maximum Distance Separable
  Convolutional Codes}%
\date{\today}%
\author{Joachim Rosenthal \and Roxana Smarandache}
\address{\hskip-\parindent 
  Department of Mathematics,
  University of Notre Dame,
  Notre Dame, Indiana 46556.}
  \email{Rosenthal.1@nd.edu, Smarandache.1@nd.edu}

  
  \thanks{Both authors were supported in part by NSF grant
    DMS-96-10389. The first author acknowledges support from MSRI
    through NSF grant DMS-9701755. The second author was
    supported by a fellowship from the Center for Applied
    Mathematics at the University of Notre Dame.  A summary of
    this paper was presented at the 1998 IEEE International
    Symposium on Information Theory in Boston and at the 36-th
    Annual Allerton Conference on Communication, Control, and
    Computing in Monticello, Illinois, 1998.}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\subjclass{Primary: 94B10. Secondary: 94B65. }
\keywords{Convolutional codes, MDS block codes.}

\begin{abstract}
  A maximum distance separable (MDS) block code is a linear code
  whose distance is maximal among all linear block codes of rate
  $k/n$. It is well known that MDS block codes do exist if the
  field size is more than $n$. In this paper we generalize this
  concept to the class of convolutional codes of a fixed rate
  $k/n$ and a fixed code degree~$\delta$. In order to achieve
  this result we will introduce a natural upper bound for the
  free distance generalizing the Singleton bound. The main result
  of the paper shows that this upper bound can be achieved in all
  cases if one allows sufficiently many field elements.
\end{abstract}


\maketitle
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Introduction}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Let $\F$ be a finite field and let $\C\subset\F^n$ be an $[n,k]$
linear block code. Let $d(\C)$ be the distance of $\C$, i.e.
$d(\C)$ is equal to the minimum Hamming distance between any two
different code words $x,y\in\C$.

The main linear coding problem asks for the construction of
linear $[n,k]$ codes whose distance $d(\C)$ is maximal among all
linear $[n,k]$ codes.

The distance $d(\C)$ is always upper bounded by the Singleton
bound~\cite{ma77}, i.e. one has the inequality
\begin{equation}
  \label{singleton}
  d(\C)\leq n-k+1.
\end{equation}

If the base field $\F$ has sufficiently many elements then the
Reed Solomon construction shows that there are $[n,k]$ codes
whose distance is equal to $n-k+1$. Such codes are called maximum
distance separable (MDS) codes. It is the purpose of this paper
to derive a generalization for the Singleton bound which is valid
for convolutional codes and to prove that there exist codes which
achieve this generalized Singleton bound. We call then such a
convolutional code an MDS convolutional code.

In the literature there were already several
papers~\cite{ju74,pi83} which considered the concept of a maximum
distance separable convolutional code. In each of these
approaches it was necessary to restrict the total class of rate
$k/n$ convolutional codes to a suitable subclass. This is simply
due to the fact that there is in general no upper bound for the
free distance of a rate $k/n$ convolutional code.

We argue that the single most important parameter for a rate
$k/n$ convolutional code is the {\em degree} and we will define
this parameter in a moment. The set of all convolutional codes of
rate $k/n$ and degree at most $\delta$ forms a finite set and
consequently the free distances of these codes have to be bounded
from above.  The generalized Singleton bound which we are going
to derive will have the property that every convolutional code of
rate $k/n$ and degree $\delta$ will have a free distance of less
than this bound and the main result of this paper states that
there are codes which achieve this distance.

In the sequel we follow the module theoretic approach to
convolutional codes as it was described in~\cite{ro96a1}. This
has the advantage that we can utilize by duality well known first
order representations studied in the systems literature. The
difference to the classical approach as provided
in~\cite{fo70,pi88} will turn out to be minor.

Consider the polynomial ring $R=\F[z]$. For the purpose of this
paper we will define a convolutional code as an $R$ submodule of
the module $R^n$. Since $R$ is a principal ideal domain (PID) the
submodule $\C$ is free and it has therefore a well defined rank
$k$. If $\C$ has rank $k$ we will say that the convolutional code
$\C$ has transmission rate $k/n$.

As it was shown in~\cite{ro96a1} $\C$ is dual to a linear
behavior $\C^\perp := {\mathcal B}\subset \F^n[[z]]$ and
${\mathcal B}$ has a well defined McMillan degree $\delta$.
Using this duality we will define the degree of the convolutional
code $\C$ as the McMillan degree of the behavior $\C^\perp$.

The degree is also easily computed from the module $\C$ directly.
For this let $G(z)$ be an $n\times k$ polynomial matrix whose
columns form an $R$-basis of the submodule $\C$.  We say that
$G(z)$ is a generator matrix for the convolutional code $\C$. In
terms of $G(z)$ the degree is exactly equal to the maximal degree
of the $k\times k$ full size minors of $G(z)$.
(See~\cite{ro96a1} for details). Note that our definition is
independent of the particular choice of generator matrix. Indeed
if $G_1(z)$ and $G_2(z)$ are two generator matrices then there
exists a unimodular matrix $U(z)$ such that $G_2(z)=G_1(z)U(z)$
and the $k\times k$ full size minors of $G_2(z)$ correspond to
the full size minors of $G_1(z)$ multiplied by the constant
factor $\det U(z)$. In particular the highest degree of the
minors are the same.

Let $\nu_i$ be the degree of the $i$th column of $G(z)$. I.e.
$\nu_i=\max_j \deg g_{ji}(z)$.  We denote by $G_\infty$ the high
order coefficient matrix of $G(z)$. In general $G_\infty$ has not
full rank $k$. Every module $\C$ of rank $k$ has however an
$n\times k$ generator matrix $G(z)$ whose column degrees
$\nu_1,\ldots,\nu_k$ are non-increasing and whose high order
coefficient matrix $G_\infty$ has rank $k$.  The degree $\delta$
is in this case equal to $\delta=\sum_i\nu_i$ and we say that
$G(z)$ is in {\em column proper form}. The ordered indices
$\nu_1\geq \cdots\geq\nu_k$ are invariants of the convolutional
code and we call these indices the {\em column degrees} or {\em
  Kronecker indices} of the convolutional code $\C$.

For any $n$-component vector $v\in \F^n$, we define its weight
and denote it by $wt(v)$, the number of all its nonzero
components. The weight of a polynomial with coefficients in
$\F^n$ is then the sum of the weights of all its coefficients.
Finally we define the free distance of the convolutional code
$\C\subset \F^n[z]$ through:
$$
d_{free}=\min\{wt(v(z))\mid v(z)\in \C, v(z)\neq 0\}.
$$
\begin{remark}
  The module theoretic approach as presented above is slightly
  non-standard. In the coding literature~\cite{fo70,jo99,pi88}
  convolutional codes are usually defined as linear subspaces
  (i.e. submodules) of $R^n$ where $R$ is either the field of
  rationals $\F(z)$ or the field of formal Laurent series
  $\F((z))$. If the code is defined over $\F((z))$ it has to be
  required that the code is generated by an $n\times k$
  polynomial generator matrix $G(z)$. Over $\F(z)$ such a
  representation is guaranteed. The column span of $G(z)$ with
  respect to $\F[z]$ corresponds then to the finite weight code
  words of the column span generated by $G(z)$ with respect to
  $\F(z)$. The restriction to finite weight code words is of
  little significance.  In fact McEliece~\cite[Section 2]{mc98}
  points out that finite weight code words are the only ones that
  can occur in engineering practice. For this paper it is of
  importance that the set of rate $k/n$ convolutional codes of
  degree $\delta$ can be equipped with the structure of a variety
  and this explains our preference for the module theoretic
  approach.
\end{remark}

The paper is structured as follows: In Section~\ref{main-res} we
give a natural bound on the free distance which codes of rate
$k/n$ and degree $\delta$ must satisfy. This bound naturally
generalizes the Singleton bound~\cite[Chapter~1]{ma77} of linear
block codes.  The main theorem (Theorem~\ref{mainthm}) states
that there exists a code attaining this upper bound, as long as
we allow sufficiently large field sizes. We will call such codes
MDS convolutional codes.  In Section~\ref{FirstOrder} we exhibit
some first order representations for the convolutional codes that
are used along the paper.  In Section~\ref{ProofMain} we present
a detailed proof of the main result, that is, the existence of
MDS-convolutional codes.  Finally in the last section we explain
shortly the underlying geometric aspects of the construction.
    

 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\Section{Main Results}\label{main-res}   
 
Let $\C$ be a convolutional code of rate $k/n$ and degree
$\delta$ defined over an arbitrary base field $\F$. Let $G$ be a
polynomial encoder in column proper form with ordered column
degrees $\nu_1\geq \cdots \geq \nu_k$.  We have the following
upper bound on the free distance of the code:

\begin{lemma}
  Let $\ell$ be the number of indices $\nu_i$ among the ordered
  indices $\nu_1\geq \cdots \geq \nu_k$ having the value
  $\nu_i=\nu_k$. Then the free distance must satisfy
\begin{equation} \label{upper1}
    d_{free}\leq  n(\nu_k+1) -\ell+1.
\end{equation}
\end{lemma}
\begin{proof}
  Let $G_{\infty}$ be the high order coefficient matrix of
  $G(z)$. After some possible permutation of the rows of $G(z)$
  we can use elementary column operations and transform the last
  $\ell$ columns of the matrix $G_{\infty}$ into a matrix $\left[
    I_\ell \atop M\right]$ where $M$ is a matrix of size
  $(n-\ell)\times \ell$ over $\F$.  The transforming operations
  can be done by an invertible matrix $T\in Gl_\ell$ which acts
  on the last $\ell$ columns of the matrix $G(z)$. This
  transformation has no effect on the column space of $G(z)$ and
  it also does not affect the column degrees $\nu_i$.
  
  After this transformation the last column of the new generator
  matrix $G(z)$ will have $(\ell-1)$ polynomials of weight
  strictly less than $\nu _k +1$, one with weight exactly
  $\nu_k+1$, and the remaining $(n-\ell)$ polynomials with weight
  less or equal than $\nu_k +1$. Therefore the input
  $(0,0,\ldots,0,1)^t$ gives a codeword with weight less or equal
  than
  $$
  (\ell-1)\nu_k +(\nu _k +1)+(n-\ell)(\nu _k +1)= n(\nu _k
  +1)-\ell+1.
  $$
  This gives the upper bound\eqr{upper1}.
\end{proof}

The set of rate $k/n$ convolutional codes of degree $\delta$ is
partitioned into sets of codes with different column degrees
$\nu_1\geq \cdots\geq\nu_k$. Taking the maximum of the
bound\eqr{upper1} over all such possible sets we obtain the
following:
\begin{theorem}
  For every base field $\F$ and every rate $k/n$ convolutional
  code $\C$ of degree $\delta$, the free distance is bounded by:
  \begin{equation} \label{upper}
    d_{free}\leq 
    (n-k)\left(\left\lfloor \delta /k 
    \right\rfloor +1 \right)+\delta +1.
  \end{equation}
\end{theorem}
\begin{proof}
  The upper bound\eqr{upper1} is largest if $\nu_k$ is as large
  as possible and $\ell$ as small as possible. The largest
  possible value for $\nu_k$ is
  $\nu_k=\left\lfloor\delta/k\right\rfloor$.  Minimizing $\ell$
  results in the constraint length values
  $$
  \nu_1=\left\lfloor \delta/k \right\rfloor +1,\cdots,
  \nu_{k-\ell}=\left\lfloor \delta/k \right\rfloor
  +1,\nu_{k-\ell+1}= \left\lfloor \delta/k \right\rfloor,
  \cdots,\nu_k=\left\lfloor \delta/k\right\rfloor .
  $$
  Substituting $\nu_k=\left\lfloor \delta /k \right\rfloor$
  and $\ell=k-\delta+k\left\lfloor \delta /k \right\rfloor$
  in\eqr{upper1} we get the bound\eqr{upper}.
\end{proof}

\begin{remark}
  In the systems literature, the above set of indices are
  sometimes referred to as the `generic set of column indices'.
  McEliece~\cite[Section~4]{mc98} calls a code having a right
  prime generator matrix with the generic set of column indices
  `a compact code'.
\end{remark}
\begin{remark}
  The upper bound\eqr{upper} on the free distance seems to be
  new. In the coding literature~\cite{jo89,jo99,mc98} there are
  many known upper bounds for convolutional codes of a fixed rate
  and a fixed degree. These bounds usually are valid for a
  particular finite field $\F_q$. In contrast to this,\eqr{upper}
  is valid for any field (even an infinite field) and we believe
  that the bound naturally generalizes the Singleton bound.
\end{remark}

The main theorem~\ref{mainthm} will state that there exist always
rate $k/n$ convolutional codes of degree $\delta$ whose free
distance is equal to the right hand side of\eqr{upper}. Based on
this we define:
\begin{definition} 
  A rate $k/n$ code of degree $\delta$ whose free distance
  achieves the upper bound given in\eqr{upper} will be called an
  MDS convolutional code. The bound\eqr{upper} will be called the
  generalized Singleton bound.
\end{definition} 

\begin{remark}
  MDS convolutional codes were defined before in the literature.
  Justesen and Hughes~\cite{ju74} study maximum distance
  separable convolutional codes among the class of systematic
  polynomial encoders. Since systematic polynomial encoders
  represent a very restricted class of convolutional codes the
  results are quite different from the ones presented here.
  
  Piret and Krol~\cite{pi83} consider MDS convolutional codes
  with respect to a non-standard Hamming metric. They consider
  subspaces of $R^n$ where $R=\F(z)$ is the field of rationals.
  Their Hamming distance is then defined as the number of
  coordinates where two vectors inside $R^n$ differ. This
  definition amounts to a linear block code over the infinite
  field $R=\F(z)$ and the standard Singleton bound\eqr{singleton}
  applies.
  
  The concepts studied in~\cite{ju74,pi83} are therefore
  different from the MDS concept we consider in this paper.
\end{remark}

The following lemma gives sufficient conditions for a code to be
an MDS convolutional code:
\begin{lemma}\label{mainlem}
  If a codeword $v(z)$ in $\C$ has the property that any of its
  $k$ components have weight at least $(\delta +1)$ then the
  weight of the codeword $v(z)$ is necessarily greater than or
  equal to
\begin{equation} \label{upperweight}
    (n-k)\left(\left\lfloor \delta /k 
    \right\rfloor +1 \right)+\delta +1 .
\end{equation}
\end{lemma}
We will refer to the property that any $k$ components of an $n$
component vector have weight more than $\delta +1$ as the {\em
  weight property}.
\begin{proof} 
  Let
  $$
  v(z)=\left(
\begin{array}{ccc} 
 v_1(z) &, \ldots, & v_{n}(z)
\end{array}\right)^t\in \C.
$$
The weight property implies that at least $n-k+1$ of the
components of $v(z)$ must have the weight more or equal to
$\lfloor \delta /k \rfloor +1$. Indeed, taking the first $k$
components of $v$, by the weight property, the sum of their
weight is $\geq \delta +1$, therefore there is one component, say
$v_1$ , with the weight $\geq \lfloor \delta /k \rfloor +1$. Cut
$v_1$ from the sequence and add $v_{k+1}$.The new sequence of
components has again the weight property, so there is once again
a component, say $v_2$ with weight $\geq \lfloor \delta /k
\rfloor +1$. With this reasoning we obtain that at least $n-k+1$
of the components must have the weight more or equal to $\lfloor
\delta /k \rfloor +1$. We have now that $n-k$ of the components
have weight at least $\geq \lfloor \delta /k \rfloor +1$, and
from the weight property that the remaining $k$ components have
weight greater than $\delta +1.$ Therefore
$$
\wt (v(z))\geq (n-k)\left(\left\lfloor \delta /k \right\rfloor
  +1 \right) +(\delta +1)
$$
which is equal to the upper bound \ref{upper}.

\end{proof}
Before we state the main theorem we summarize some known results:

For $\delta=0$ the bound\eqr{upper} coincides with the Singleton
bound (see e.g.~\cite{ma77}). In this situation we therefore
have:
\begin{lemma}
  If $G$ is an $n\times k$ generator of an MDS block code then
  $G$ generates also an MDS convolutional codes of rate $k/n$,
  degree $\delta=0$ and free distance $n-k+1$. In particular if
  $|\F|\geq n$, MDS convolutional codes of rate $k/n$ and degree
  $0$ do exist.
\end{lemma}
The next result implies that rate $1/n$ MDS codes do exist for
every value of $\delta$. The result was derived by
Justesen~\cite{ju75}. A systems theoretic proof of this result is
given in~\cite{sm98p1}.

\begin{theorem}[\cite{ju75}]   \label{Thm:Just}
  Let $\delta,n$ be fixed and assume that $\F$ is a finite field
  with $q:=|\F |>3\delta$ elements. Then there exists a rate
  $1/n$ MDS convolutional code.
\end{theorem} 

The main result of this paper now states:
\begin{theorem}        \label{mainthm}
  For any rate $k/n$ and any degree $\delta$ there exist MDS
  convolutional codes for sufficiently large field sizes.
\end{theorem}
 
The proof of Theorem~\ref{mainthm} will be given in
Section~\ref{ProofMain}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{First order representations for convolutional codes}
\label{FirstOrder}

This section reviews some first order representations for
convolutional codes that are heavily used in the next sections.
As it was shown in~\cite{ro96a1} we have the following existence
and uniqueness theorems:
 
\begin{theorem} \label{klm}
  Assume $\C \subset \F^n[z]$ is a rate $k/n$ convolutional code
  of degree~$\delta$. Let $\K$ be the algebraic closure of $\F$.
  Then there exist matrices $K,L \in \F^{(\delta+n-k)\times
    \delta} $ and $M \in \F^{(\delta+n-k)\times n}$ such that:
\begin{equation}\label{eq-klm} 
 \C=\{ v(z) \in \F^n[z]\mid\exists  x(z)\in \F^\delta [z] :
 (zK+L)x(z)+Mv(z)=0 \}. 
\end{equation}
Moreover, the following conditions are satisfied:
\begin{enumerate}
\item $K$ has full column rank;
\item $(K \mid M) $ has full row rank;
\item rank $(z_0 K+L \mid M)=\delta+n-k, \forall z_0 \in \K.$
\end{enumerate}
\end{theorem} 
The theorem allows one to work with matrix triples $(K,L,M)$
instead of a polynomial description.  A convolutional code which
is described by the matrices $(K,L,M)$ will be simply denoted by
$\C(K,L,M)$. If $\delta =0,$\eqr{eq-klm} reduces to the parity
check equation $Mv(z)=0$. The representation\eqr{eq-klm} is
unique in the following sense:
\begin{theorem} \label{uniq}
  Let $(K,L,M)$ and $(K',L',M')$ be two matrix triples with the
  sizes as in the previous theorem and satisfying the minimality
  conditions $1, 2,3$.
  
  Then $\C(K,L,M)=\C(K',L',M')$ if and only if
\begin{equation} \label{sim}
(K',L',M')=(SKT^{-1},SLT^{-1},SM)
\end{equation}
for some $T\in Gl_{\delta +k}(\F)$ and $S\in
Gl_{\delta+n-k}(\F)$.
\end{theorem}
Starting with a $(K,L,M)$ representation for a convolutional code
$\C$ we can derive an input/state/output representation.
Performing a suitable similarity transformation and permutation
of the components of $v(z)$ we can rewrite the $(K,L,M)$ matrix
triple in the following way (compare
with~\cite[Section~IV]{ro96a1}):
$$
K=\left[\begin{array}{c} I_{\delta} \\ 0
\end{array}\right], L=\left[ 
\begin{array}{c} 
-A\\ -C  
\end{array}\right],M=\left[ 
\begin{array}{cc} 
0&-B \\ I_{n-k}& -D  
\end{array}\right].
$$
In the partitioning, $A\in \F^{\delta \times \delta},B\in
\F^{\delta \times k}, C\in \F^{(n-k)\times \delta}$ and $
D\in\F^{(n-k)\times k}$.  Let:
$$
x(z) = x_0z^{\gamma}+x_{1}z^{{\gamma}-1} + \ldots +
x_{\gamma};\ x_t\in\F^\delta, t=0,\ldots,\gamma,
$$
$$
v(z) = v_0z^{\gamma}+v_{1}z^{{\gamma}-1} + \ldots +
v_{\gamma};\ v_t\in\F^n, t=0,\ldots,\gamma.
$$
If one partitions the vector $v_t$ into $v_t=\left({y_t \atop
    u_t}\right)$, where $y_t$ has $n-k$ components and $u_t$ has
$k$ component then the convolutional code is equivalently
described by the familiar looking `$(A,B,C,D)$' representation:
\begin{equation}  \label{ABCD}
\begin{array}{rcl}
   x_{t+1} &= &Ax_{t} + Bu_{t} \\
   y_{t} &=&Cx_{t} + Du_{t},\ \    x_{0}=0,\ x_{\gamma+1}=0.
  \end{array} 
\end{equation}
This system is known as the input/state/output representation for
a convolutional code. It describes the dynamics for a {\em
  systematic and rational encoder}. We refer
to~\cite{ro96a1,ro97r1,yo97t} for more details.

We say that the matrices $(A,B)$ form a {\em controllable} pair
if
$$
\rank \left( B \ AB \ldots \ A^{\delta-1}B \right)=\delta,
$$
and we say that $(A,C)$ form an {\em observable pair} if
$(A^t,C^t)$ is a controllable pair.  Once $(A,B)$ form a
controllable pair and $(A,C)$ form an observable pair then it was
shown in~\cite{ro96a1,ro97r1,yo97t} that the system\eqr{ABCD}
represents a non-catastrophic convolutional code of degree
$\delta$ and rate $k/n$.

If one is interested in the construction of convolutional codes
with some designed distance there is no limitation if one
attempts to construct matrices $A,B,C,D$, with $(A,B)$
controllable and $(A,C)$ an observable pair.  The following
result was obtained by such a construction:

\begin{theorem}[\cite{ro96a1}]           \label{RSmats} 
  Let $ r:= \max\{ n-k,k \}$, and assume that the cardinality of
  the field $\F$ satisfies
  $$
  |\F| > \delta r\left\lceil {\frac{\delta}{n-k}}
  \right\rceil.
  $$
  Then there exists a rate $k/n$ convolutional code of degree
  $\delta$ having free distance
  $$
  d_{free}\geq \delta+1.
  $$
\end{theorem}
\begin{remark}
  The proof of Theorem~\ref{RSmats} as given in~\cite{ro96a1}
  came with a concrete construction of a set of matrices
  $A,B,C,D$.  The reader observes that for very high rates the
  free distance of $\delta +1$ is only a fraction away from the
  optimal upper bound\eqr{upper}. For low rates the distance of
  $\delta +1$ is less than optimal.
\end{remark}
In order to prove Theorem~\ref{mainthm} we will need a
strengthening of Theorem~\ref{RSmats}:
\begin{theorem}                      \label{thm-mds}
  Let $\delta,k,n,\rho$ be fixed and assume that
  $$
  \rho=\delta \left(2\left\lceil {\frac{\delta}{n-k}}
    \right\rceil+\left\lfloor \frac{\delta}{k}
    \right\rfloor+1\right).
  $$
  If the matrices $A,B,C$ have the property that $\left( B\ 
    AB\ldots \ A^{\rho-1}B\right)$ is the parity check of an MDS
  block code and that $\left( C^t \ A^t C^t \ldots \ 
    {A^{\rho-1}}^t C^t \right)$ is the generator matrix of an MDS
  block code then for any codeword
  $$
  v(z)=\left({y(z) \atop u(z)}\right) \in \F^{n}[z]
  $$
  either
  $$
  \wt(u(z))\geq \delta+1 \mbox{ ~or~ } \wt(v(z))\geq
  (n-k)\left(\left\lfloor \delta /k \right\rfloor +1
  \right)+\delta +1.
  $$
 \end{theorem}
 
 Before we give the proof we want to mention that the choice of
 $\rho$ is not the minimum that we can have so that the result is
 correct. The proof for a smaller choice of $\rho$ would involve
 more cases. For the purpose of this paper this is not necessary.
\begin{proof}
  Assume
\begin{eqnarray*}
  u(z)& =&
u_{0}z^{\gamma}+u_{1}z^{{\gamma}-1} + \cdots + u_{\gamma},\\
y(z)& = &y_{0}z^{\gamma}+y_{1}z^{{\gamma}-1} + \cdots +
y_{\gamma},
\end{eqnarray*}
where $\gamma$ is the degree of $v$, and that $u_0\neq 0$.  The
first equations of the systems\eqr{ABCD} give that
(see~\cite{ro96a1}):
$$
(u_{\gamma},\ldots,u_{0})^{t} \in \ker \left( B \ AB \ldots \ 
  A^{\gamma}B \right).
$$ 
If $\gamma< \rho$ then
$\wt(u(z))\geq \delta+1$ and the proof is complete.

We therefore assume that $\gamma\geq \rho$ and that
$\wt(u(z))\leq \delta$. By the `pigeonhole principle' there exist
an index $i<\rho-\frac{\rho}{\delta} $ and an input sequence
$$
u_{i+1}=u_{i+2}=\cdots=u_{i+\frac{\rho}{\delta}}=0.
$$
In analogy to the proof of~\cite[Theorem~3.1]{ro97r1} it
follows that the state $x_{i+1}\neq 0$ and that
$$
\left(
  \begin{array}{c}
y_{i+1}\\ y_{i+2}\\ \vdots \\
y_{i+\frac{\rho}{\delta}} 
  \end{array}\right)
=\left(
  \begin{array}{c}
C\\ CA \\ \vdots \\ CA^{\frac{\rho}{\delta}-1}
  \end{array}\right)x_{i+1}.
$$
The assumption on the matrix $\left( C^t \ A^t C^t \ldots \ 
  {A^{\rho-1}}^t C^t \right)$ gives that
\begin{eqnarray*}
 \wt(y)&\geq &(n-k)\cdot \frac{\rho}{\delta}-\delta +1=
(n-k)\left(2\left\lceil {\frac{\delta}{n-k}}
  \right\rceil+\left\lfloor \frac{\delta}{k}
  \right\rfloor+1\right)-\delta +1\\
& \geq & 2\delta+(n-k)\left(\left\lfloor \frac{\delta}{k} \right\rfloor +1
\right)-\delta +1=(n-k)\left(\left\lfloor \frac{\delta}{k} \right\rfloor
  +1\right)+\delta +1.
\end{eqnarray*}
\end{proof}

In the proof of Theorem~\ref{mainthm} the following lemma will be
needed:
\begin{lemma}                    \label{non-empty}
  Let $\delta,k,n,\rho$ be fixed, $ r= \max\{ n-k,k \}$ and
  assume that the cardinality of the field $\F$ satisfies $|\F|>
  r\rho$. Then there exist matrices $A,B,C$ satisfying the
  conditions of Theorem~\ref{thm-mds}.
\end{lemma}
\begin{proof}
  Let $\alpha\in\F$ be an element of multiplicative order at
  least $r\rho$. Then
  $$
  A:=\left(
\begin{array}{cccc}
\alpha^r     &    0     &       
\cdots  &    0 \\
0       &    \alpha^{2r}   &   
\ddots  &    \vdots \\
\vdots  &    \ddots   &    
\ddots  &    0 \\
0   &    \cdots   &    
0   &    \alpha ^{\delta r}
\end{array}
\right),\ B:=\left(
\begin{array}{ccccc}
1   &    \alpha   &    
\alpha^2   &    \cdots   &    
\alpha^{k-1} \\
1   &    \alpha^2   &    
\alpha^4   &    \cdots   &    
\alpha^{2(k-1)} \\
\vdots   &    \vdots   &    
\vdots   &       &    \vdots \\
1   &    \alpha^{\delta}   &    
\alpha^{2\delta}   &    \cdots   &    \alpha^{\delta (k-1)}
\end{array}
\right),
$$
$$
C:=\left(
\begin{array}{ccc}
1   &    \cdots   &    1 \\
\alpha    &    \cdots  &\alpha^\delta  \\
\alpha^2  &\cdots &   \alpha^{2\delta} \\
\vdots &       &   \vdots \\
\alpha^{n-k-1}  &\cdots   &    \alpha^{\delta (n-k-1)}
\end{array}
\right)
$$
satisfy the conditions of Theorem~\ref{thm-mds}.
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
\Section{Proof of the main result}\label{ProofMain}

In this section we will give the proof for Theorem~\ref{mainthm},
the main result of this paper.  The idea of the proof goes as
follows:

We exhibit a parameterization on the set of all rate $k/n$
convolutional codes of degree $\delta$ using a large $\F$-vector
space, where $\F$ is a finite field. Then we show that the set of
codes which are not MDS forms an algebraic subset. Over a finite
field an algebraic subset might be the whole parameter space.
Over the algebraic closure however the algebraic subset
describing the convolutional codes which are not MDS forms a
strictly proper subset. This reasoning will allow us to predict
an MDS convolutional code with entries in a finite extension of
the (finite) base field $\F$ which is itself a finite field.
 
For the parameterization we will use the first order
representation as presented in Theorem~\ref{klm} of
Section~\ref{FirstOrder}. We do this by viewing a triple of
matrices $(K,L,M)$ as a point in the vector space
$\F^{(\delta+n-k)(2\delta +n)}$. By Theorem~\ref{uniq} this
parameterization is not unique. This is however of minor
importance in the proof. In the last section we will show that
the proof can also be derived in a variety which parameterizes
the rate $k/n$ convolutional codes of degree $\delta$ exactly.
We start the proof with a short Lemma:
\begin{lemma}
  The set of matrices $(K,L,M)$ satisfying the property $1,2$ and
  $3$ of Theorem~\ref{klm} is open and nonempty inside
  $\F^{(\delta+n-k)(2\delta +n)}$.
\end{lemma}
\begin{proof} We recall from the paper of Ravi and
  Rosenthal~\cite{ra95} that the conditions $2$ and $3$ can be
  equivalently written as the following rank condition:
 \begin{equation}         \label{con-matrix}
 \underbrace{%
\left[ \begin{array}{cccc|ccccc}
  K   &   0   &\ldots&   0  &   M  &   0  &\ldots&\ldots&   0  \\
  L   &   K   &\ddots&\vdots&   0  &   M  &\ddots&      &\vdots\\
  0   &   L   &\ddots&   0  &\vdots&\ddots&\ddots&\ddots&\vdots\\
\vdots&\ddots &\ddots&   K  &\vdots&      &\ddots&   M  &   0  \\
  0   &\ldots &   0  &   L  &   0  &\ldots&\ldots&   0  &   M
\end{array}\right]}_{\mbox{$2\delta-1$ blocks}}  
\mbox{$\delta $ blocks}
\end{equation}
has full row rank. Thus all $(K,L,M)$ matrices satisfying the
conditions $1,2,3$ are in the complementary set of all zeros of
the polynomial equations describing the determinant of some full
size minors of the matrices $K$ and \eqr{con-matrix} being $0$.
Therefore the set of all matrix 3-tuples $(K,L,M)$ satisfying the
conditions $1,2,3$ is open in $\F^{(\delta+n-k)(2\delta +n)}$ and
it is obviously nonempty since there is an one to one
correspondence between this set and the set of all convolutional
codes as we defined them.
\end{proof}

The rest of the section will be devoted to the proof of the main
theorem.

\begin{proof}[Proof of Theorem \ref{mainthm}]
  Let $\F$ be a fixed finite field, with $q$ elements, having
  characteristic~$p$. Let $\K$ denote the algebraic closure of
  $\F$.  As an algebraically closed field, $\K$ is infinite. We
  will call a matrix with all full size minors invertible, an MDS
  matrix.
  
  Consider now some fixed numbers $\delta,k,n,\rho$ with $k<n$
  and $\rho$ chosen as in Theorem~\ref{thm-mds}.
  
  We are looking at the set of all $3$-tuple matrices $(K,L,M)$
  with the properties $1,2,3$ and of sizes as in
  Theorem~\ref{klm}, such that the matrix $\left[ K \mid M
  \right]$ is an MDS matrix. Let this set be denoted by $V$. $V$
  is the intersection of two open nonempty sets, one given by all
  $(K,L,M)$ such that the conditions $1,2,3$ are satisfied, and
  the other given by the complementary of the set of the zeros of
  all the full size minors of $\left[ K \mid M \right]$. Over the
  algebraic closure $\K$, the intersection of nonempty open sets
  is nonempty and $V$ is therefore a nonempty Zariski open set in
  $\K^{(\delta+n-k)(2\delta +n)}.$
  
  Let now $(K,L,M)$ be an element in $V$, and let
  $$
  {\mathbf j}=\{1\leq j_1<j_2<\ldots <j_k\leq n\}
  $$
  be a subset of the set $\{1,\ldots,n\}$ having cardinality
  $k$. We would like to show that the code $\C$ defined by
  $(K,L,M)$ has the property that the $k$ components $\{
  v_{j_i}(z)\mid i=1,\ldots,k\}$, of a code word $v(z)\in\C$
  satisfy either
  $$
  \sum_{i=1}^k\wt(v_{j_i}(z))\geq \delta+1 \mbox{ ~or~}
  wt(v(z))\geq (n-k)\left(\left\lfloor \delta /k \right\rfloor +1
  \right)+\delta +1.
  $$
  In order to apply Theorem~\ref{thm-mds}, let $P_{\mathbf j}$
  be an $n\times n$ permutation matrix such that
  $$
  P_{\mathbf j}v(z)=\left({y(z) \atop u(z)}\right)
  $$
  where the $k$ components $v_{j_1}(z),\ldots,v_{j_k}(z)$ of
  $v(z)$ are mapped onto the $k$ components of $u(z)$.
   
  Partition the matrix $MP_{\mathbf j}^{-1}= \left[ M_1\mid N
  \right]$ where $M_1$ is the matrix formed by the first $n-k$
  columns of $MP_{\mathbf j}^{-1}$ and $N$ denotes the rest of
  the columns in $MP_{\mathbf j}^{-1}$. The property of $V$ tells
  us that the matrix $\left[K \mid M_1\right]$ is invertible.
  
  For every $K,L,M$ and every ${\mathbf j}$ we define matrices
  $A_{\mathbf j},B_{\mathbf j},C_{\mathbf j},D_{\mathbf j}$ in
  the following way:
   \begin{equation}
     \label{corresp}
     \left[K \mid M_1\right]^{-1}\left[  
    K \mid L\mid MP_{\mathbf j}^{-1} \right]
     =: \left[\begin{array}{c|c|cc} 
    \hspace{1mm} I_{\delta}\hspace{1mm}&\hspace{1mm} -
    A_{\mathbf j} \hspace{1mm} &0&-B_{\mathbf j}\\
     0 &-C_{\mathbf j}&\hspace{1mm}I_{n-k}\hspace{1mm} &
     \hspace{1mm}-D_{\mathbf j} \hspace{1mm}
    \end{array}\right].
   \end{equation}
   Rewriting the equation\eqr{eq-klm} in the new terms we obtain
   the $(A,B,C,D)$ polynomial description from the previous
   chapter:
\begin{equation} 
  \label{kern2} 
  \left[ 
   \begin{array}{ccc} 
   zI_{\delta} -A_{\mathbf j}&0&-B_{\mathbf j}\\ 
   -C_{\mathbf j}&I_{n-k} &-D_{\mathbf j} 
   \end{array} 
 \right] 
 \left[\begin{array}{c} 
   x(z)\\ y(z)\\ u(z) 
   \end{array} 
 \right]=0 .
\end{equation}

If the matrices $A_{\mathbf j},B_{\mathbf j},C_{\mathbf j}$
satisfy the conditions of Theorem~\ref{thm-mds} then the weight
$\sum_{i=1}^k\wt(v_{j_i}(z))\geq \delta+1$ or the weight of
$v(z)$ is larger than the bound\eqr{upper}.

The algebraic conditions on $A,B,C$ expressed in
Theorem~\ref{thm-mds} translate into algebraic conditions inside
the parameter space $\K^{(\delta+n-k)(2\delta +n)}.$ Let
$$
S_{\mathbf j}= \{(K,L,M)\in \F^{(\delta+n-k)(2\delta +n)}\ 
{\rm s.t.}
$$
$$
\left(B_{\mathbf j} \ A_{\mathbf j}B_{\mathbf j} \ldots \ 
  A_{\mathbf j}^{\rho-1}B_{\mathbf j}\right) \mbox{ and } \left(
  C_{\mathbf j}^t \ A_{\mathbf j}^tC_{\mathbf j}^t \ldots \ 
  {A_{\mathbf j}^{\rho-1}}^t C_{\mathbf j}^t \right)\mbox{ are
  MDS} \}.
$$

Applying Lemma~\ref{non-empty} one sees that $S_{\mathbf j}\cap
V$ is a nonempty Zariski open subset of $\K^{(\delta+n-k)(2\delta
  +n)}$.
 
Let $J=\{ {\mathbf j}= \{1\leq j_1<j_2<\ldots < j_{k}\leq n\}\}$
be the set of all $k$-subsets of $\{1,\ldots,n\}$, and consider
all $\{S_{\mathbf j}\cap V \ |\ \mathbf j \in J\}$.  All of these
sets form a finite number of open nonempty sets in $V$, therefore
their intersection is nonempty. It implies the existence of a
vector $x=(K,L,M)$ having the property of all the sets
$S_{\mathbf j}\cap V$.
 
So far we obtained a vector $x\in V$ having the components in
$\K$, the algebraic closure of $\F$, and laying in the
intersection
$$
\bigcap_{{\mathbf j}\in J} (S_{\mathbf j}\cap V)\subset V
\subset \K^{(\delta+n-k)(2\delta +n)}.
$$
Since the extension $\F\subset \K$ is algebraic, it implies
that every component of $x$ is algebraic over $\F$, therefore in
a finite extension.  If we denote with $x_{j}$ the components of
$x$ we have that all $x_{j}\in \F[x_{j},1\leq j\leq
(\delta+n-k)(2\delta +n)]$, which is a finite extension over
$\F$, therefore is finite of degree say $m$. Therefore the code
$\C=\C(K,L,M)$ associated to the matrices $(K,L,M)$ will be a
code over a finite field $\F_{q^m}$, with $m$ possibly rather
large.
  
We will show that this code is actually an MDS convolutional
code, in other words it has the free distance equal to the upper
bound\eqr{upper}.  Let
$$
v(z)=\left(
\begin{array}{ccc} 
 v_1(z) &, \ldots, & v_{n}(z)
 \end{array}
\right)^t\in \C
$$
be a nonzero code word. We will show that the weight of $v(z)$
is larger than the upper bound by applying Lemma~\ref{mainlem}
and Theorem~\ref{thm-mds}.

Since the code $\C$ belongs to the intersection of all the
Zariski open sets $S_{\mathbf j}\cap V$, we can apply
Theorem~\ref{thm-mds} for all the $k$-combinations of the
components $v_1, v_2, \ldots ,v_{n}$ to form the part $u$ of the
codeword.  By construction of the sets $S_{\mathbf j}\cap V$, we
get that either the weight of the $k$-combination of components
$v_1,v_2,\ldots ,v_n$ is more than $\delta +1$, or the weight of
the whole codeword is larger than
$$
(n-k)\left( \lfloor \delta /k \rfloor +1 \right) +\delta +1
$$
which is the bound we want.  If we have the first situation
for all $k$-combina\-tions of the components we get the
conditions of Lemma~\ref{mainlem}. The weight of the codeword is
therefore greater then the upper bound\eqr{upper}. In either case
we predict the existence of an MDS code $\C$ over the finite
field $\F_{q^m}$.
\end{proof}
\begin{remark} The proof does not construct MDS convolutional
  codes in an explicit way. Concrete constructions exist when
  $\delta=0$~(Reed-Solomon construction) and when $k=1$~(see
  Theorem~\ref{Thm:Just}).
\end{remark}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Remarks on the geometry of the construction}

We conclude this paper with some remarks about the algebraic
geometric aspect of the constructions considered in the previous
section.


As it was explained in~\cite{lo90,ra94,ra95} a submodule of rank
$k$ and degree $\delta$ in $\F^n[z]$ describes a quotient sheaf
of rank $k$ and degree $\delta$ over the projective line
${\mathbb P}^1$.  The column degrees $\nu_1\geq \cdots \geq
\nu_k$ of the submodule $\C\subset \F^n[z]$ correspond then to
the Grothendieck indices of the quotient sheaf.  By a general
theorem of Grothendieck it is possible to equip the set of all
rank $k$ submodules (quotient sheaves) of degree $\delta$ with
the structure of a scheme.  Such a scheme is referred to as a
{\em quot scheme} in the algebraic geometry literature.  The quot
scheme which parameterizes the rank $k$ submodules of degree
$\delta$ turns out to be a smooth projective variety~\cite{ra94}.
This variety has been of prominent interest recently in the area
of conformal quantum field theory and we refer to~\cite{ra98} for
more details.

If the degree $\delta=0$ the Grothendieck quot scheme is exactly
the Grassmann variety Grass$(k,\F^n)$ consisting of all $k$
dimensional subspaces of the vector space $\F^n$. This variety
parameterizes the set of all linear block codes of rate
$\frac{k}{n}$ defined over the field $\F$. For an arbitrary
degree $\delta$ the Grothendieck quot scheme parameterizes in a
natural way all rate $\frac{k}{n}$ convolutional codes of degree
$\delta$.

Linear systems described by matrix triples $(K,L,M)$ have been
studied widely in the systems literature and probably the most
comprehensive account is given in the monograph of
Kuijper~\cite{ku94}. It was pointed out by Lomadze~\cite{lo90}
that a matrix pencil of the form $\left[ {zK+L\mid M}\right]$
represents exactly the linear free resolution of the associated
quotient sheaf and in this way such matrix pencils appear
naturally in the algebraic geometry literature as well.  Finally
we would like to note that we can view\eqr{sim} as a group action
of the reductive group $Gl_{\delta +k}\times Gl_{\delta}$ on the
vector space consisting of all matrix triples $(K,L,M)$ of a
fixed size. The uniqueness Theorem~\ref{uniq} expresses the fact
that the group orbits in\eqr{sim} correspond to the submodules of
$\F^n[z]$, i.e. the convolutional codes.

Actually much more is true: The geometric quotient in the sense
of GIT (=geometric invariant theory) induced by the group
action\eqr{sim} is exactly the Grothendieck quot scheme. The
minimality conditions provided in Theorem~\ref{klm} and
characterized by the set $V\subset \F^{(\delta+n-k)(2\delta +n)}$
appearing in the proof of the main theorem, guarantee that the
associated orbit is a `stable orbit' in the sense of GIT. This is
true for an arbitrary base field and this statement is a
geometric formulation of the uniqueness Theorem~\ref{uniq}. The
reader who is interested in more details is referred
to~\cite{ra95}.  For the purpose of this paper the following is
important. The open set $V\subset \F^{(\delta +n-k)(2\delta +n)}$
which we introduced in the proof of Theorem~\ref{mainthm}
describes exactly the stable orbits and the quotient of $V$ under
the group action\eqr{sim} describes the Grothendieck quot scheme
$X^{\delta}_{k,n}$. The sets $S_{\mathbf j}$ induces Zariski open
sets inside the scheme $X^{\delta}_{k,n}$ and by abuse of
notation we will denotes these sets with $S_{\mathbf j}$ as well.
The set of MDS convolutional codes contains then the Zariski open
subset
$$
\bigcap S_{\mathbf j}\subset X^{\delta}_{k,n}.
$$
The main result states that $\bigcap S_{\mathbf j}$ is
nonempty as soon as the field size is sufficiently large. A set
which contains a non-empty Zariski open subset is sometimes
referred to as a {\em generic set} and in this way we can say
that the set of MDS convolutional codes forms a generic set
inside the set of rate $k/n$ convolutional codes of degree
$\delta$ as soon as the field size is sufficiently large.

For $\delta=0$ the result says that the set of MDS block codes
viewed as a subset of the Grassmann variety forms a Zariski open
subset and that this set is nonempty as soon as the field is
sufficiently large. In the block code situation we know that
$|\F|\geq n$ is sufficient to guarantee that the set is nonempty.
In particular the existence of MDS block codes over the field
$\F(z)$ as studied by Piret and Krol~\cite{pi83} follows from our
theory.\medskip

After generalizing the notion of MDS block code it naturally
arises the question on the nature of the dual code. We know that
a dual of an MDS-block code is MDS, so we want to find out if
this generalizes to the case of general convolutional codes with
degree $\delta >0$.  In the sequel we cover two special cases
where this turns out to be true and then we give two examples of
MDS-convolutional codes whose dual is not MDS.
 
In order to introduce the notion of a dual convolutional code in
our module theoretical setting, consider the following bilinear
form:
\begin{eqnarray}
  \label{mapinner} 
 <,>:\  \F^n[z]\times \F^n[z] &\longrightarrow& \F[z]\\
\hspace{1cm}(v(z),w(z))& \longmapsto &v(z) w(z)^t \nonumber.
\end{eqnarray}
Using this bilinear form we define the dual of a code $\C$ as
$$
\C^{\perp}:=\{w(z)\mid <v(z),w(z)>=0,\forall v(z)\in \C\}.
$$
One always has that
$$
\C^{\perp \perp}\supseteq \C.
$$
If the code $\C$ has a minimal basis encoder (i.e. it is
non-catastrophic) then $\C^{\perp \perp}=\C.$

The following two lemmas cover some cases where the dual of an
MDS convolutional code is MDS.
\begin{lemma}
  If $\C$ is a convolutional code of degree $\delta =0$ then $\C$
  is MDS if and only if $\C^{\perp}$ is MDS.
\end{lemma}
\begin{lemma}
  Assume $k=1,n=2$. A non-catastrophic code $\C$ of rate $1/2$ is
  MDS if and only if $\C^{\perp}$ is MDS.
\end{lemma}

We will present now a very simple example of a rate $1/3$ MDS
convolutional code which has a non-MDS convolutional code of rate
$2/3$ as its dual. In this example the degree $\delta =1$ and the
finite field is $\F_3$:
\begin{example}
  Let $k=1$, $n=3$, $\delta =1$ and consider the generator matrix
  $$
  G(z)=\left(
   \begin{array}{ccc} (z+2) & (z+1) &(z+1)
   \end{array} \right)^t.
 $$
 Then the code generated by $G(z)$ is non-catastrophic and MDS
 but the dual code is not an MDS convolutional code.
  
 Indeed it is easy to see that any codeword $v(z)=G(z)i(z),
 i(z)\in \F^k[z]$ has weight at least $6$, so the code generated
 by $G(z)$ is MDS. The dual code has a generator matrix given by:
 $$
 G^{\perp}= \left(
  \begin{array}{cc}
      z+1 & 0  \\ 
      0 & 1 \\
     2z+1&2
  \end{array} 
\right),
$$
which is not MDS.
\end{example}

The above example shows that in general the dual code of an MDS
convolutional code is not an MDS convolutional code anymore in
contrast to the situation of block codes. In~\cite{ro98p3} more
details on the issue of duality of MDS convolutional codes were
given.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
%\bibliography{huge} \bibliographystyle{plain}
%\nocite{jo89,jo99,ro98p3,ra98}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\begin{thebibliography}{10}
  
\bibitem{fo70} G.~D. Forney.  \newblock Convolutional codes {I}:
  Algebraic structure.  \newblock {\em IEEE Trans. Inform.
    Theory}, IT-16(5):720--738, 1970.
  
\bibitem{jo89} R.~Johannesson and K.~Zigangirov.  \newblock
  Distances and distance bounds for convolutional codes -- an
  overview.  \newblock In {\em Topics in Coding Theory. In honour
    of L. H. Zetterberg.}, Lecture Notes in Control and
  Information Sciences \# 128, pages 109--136.  Springer Verlag,
  1989.
  
\bibitem{jo99} R.~Johannesson and K.~Sh. Zigangirov.  \newblock
  {\em Fundamentals of Convolutional Coding}.  \newblock IEEE
  Press, New York, 1999.
  
\bibitem{ju75} J.~Justesen.  \newblock An algebraic construction
  of rate $1/{\nu}$ convolutional codes.  \newblock {\em IEEE
    Trans. Inform. Theory}, IT-21(1):577--580, 1975.
  
\bibitem{ju74} J.~Justesen and L.R. Hughes.  \newblock On
  maximum-distance-separable convolutional codes.  \newblock {\em
    IEEE Trans. Information Theory}, IT-20:288, 1974.
  
\bibitem{ku94} M.~Kuijper.  \newblock {\em First-Order
    Representations of Linear Systems}.  \newblock
  Birkh\"{a}user, Boston, 1994.
  
\bibitem{lo90} V.~Lomadze.  \newblock Finite-dimensional
  time-invariant linear dynamical systems: Algebraic theory.
  \newblock {\em Acta Appl. Math}, 19:149--201, 1990.
  
\bibitem{ma77} F.~J. MacWilliams and N.~J.A. Sloane.  \newblock
  {\em The Theory of Error-Correcting Codes}.  \newblock North
  Holland, Amsterdam, 1977.
  
\bibitem{mc98} R.J. McEliece.  \newblock The algebraic theory of
  convolutional codes.  \newblock In R.~Brualdi, W.C. Huffman,
  and V.~Pless, editors, {\em Handbook of Coding Theory}.
  Elsevier Science Publishers, Amsterdam, The Netherlands, 1998.
  \newblock To appear.
  
\bibitem{pi88} Ph. Piret.  \newblock {\em Convolutional Codes, an
    Algebraic Approach}.  \newblock MIT Press, Cambridge, MA,
  1988.
  
\bibitem{pi83} Ph. Piret and T.~Krol.  \newblock {MDS}
  convolutional codes.  \newblock {\em IEEE Trans. Inform.
    Theory}, 29(2):224--232, 1983.
  
\bibitem{ra94} M.~S. Ravi and J.~Rosenthal.  \newblock A smooth
  compactification of the space of transfer functions with fixed
  {McM}illan degree.  \newblock {\em Acta Appl. Math},
  34:329--352, 1994.
  
\bibitem{ra95} M.~S. Ravi and J.~Rosenthal.  \newblock A general
  realization theory for higher order linear differential
  equations.  \newblock {\em Systems \& Control Letters},
  25(5):351--360, 1995.
  
\bibitem{ra98} M.~S. Ravi, J.~Rosenthal, and X.~Wang.  \newblock
  Degree of the generalized {P}l{\"u}cker embedding of a quot
  scheme and quantum cohomology.  \newblock {\em Math. Ann.},
  311(1):11--26, 1998.
  
\bibitem{ro96a1} J.~Rosenthal, J.~M. Schumacher, and E.V. York.
  \newblock On behaviors and convolutional codes.  \newblock {\em
    IEEE Trans. Inform. Theory}, 42(6):1881--1891, 1996.
  
\bibitem{ro98p3} J.~Rosenthal and R.~Smarandache.  \newblock On
  the dual of {MDS} convolutional codes.  \newblock In {\em Proc.
    of the 36-th Annual Allerton Conference on Communication,
    Control, and Computing}, 1998.  \newblock To appear.
  
\bibitem{ro97r1} J.~Rosenthal and E.V. York.  \newblock {BCH}
  convolutional codes.  \newblock Technical report, University of
  Notre Dame, Dept. of Mathematics, October 1997.  \newblock
  Preprint \# 271. Available at
  http://www.nd.edu/\~{}rosen/preprints.html.
  
\bibitem{sm98p1} R.~Smarandache and J.~Rosenthal.  \newblock A
  state space approach for constructing {MDS} rate $1/n$
  convolutional codes.  \newblock In {\em Proceedings of the 1998
    IEEE Information Theory Workshop on Information Theory}, pages
  116--117, Killarney, Kerry, Ireland, June 1998.
  
\bibitem{yo97t} E.V. York.  \newblock {\em Algebraic Description
    and Construction of Error Correcting Codes, a Systems Theory
    Point of View.}  \newblock PhD thesis, University of Notre
  Dame, 1997.  \newblock Available at
  http://www.nd.edu/\~{}rosen/preprints.html.

\end{thebibliography}

 
\end{document}