MAXIMUM DISTANCE SEPARABLE CONVOLUTIONAL CODES

JOACHIM ROSENTHAL AND ROXANA SMARANDACHE

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 δ. 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.

1. Introduction

Let 𝔽 be a finite field and let C ⊂ 𝔽^{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 ∈ 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 [8], i.e. one has the inequality

d(C) ≤ n − k + 1. (1.1)

If the base field 𝔽 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 [5, 11] 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

Date: December 11, 1998. 1991 Mathematics Subject Classification. Primary: 94B10. Secondary: 94B65. Key words and phrases. Convolutional codes, MDS block codes. 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.

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 degree and we will define this parameter in a moment. The set of all convolutional codes of rate k/n and degree at most δ 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 δ 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 [15]. 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 [1, 10] will turn out to be minor.

Consider the polynomial ring R = 𝔽[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 [15] C is dual to a linear behavior C^{⊥} := B ⊂ 𝔽^{n}[[z]] and B has a well defined McMillan degree δ. Using this duality we will define the degree of the convolutional code C as the McMillan degree of the behavior C^{⊥}.

The degree is also easily computed from the module C directly. For this let G(z) be an n × 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 ×k full size minors of G(z). (See [15] 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 × 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 ν_{i} be the degree of the ith column of G(z). I.e. ν_{i} = max_{j} deg g_{ji}(z). We denote by G_{∞} the high order coefficient matrix of G(z). In general G_{∞} has not full rank k. Every module C of rank k has however an n×k generator matrix G(z) whose column degrees ν_{1}, …, ν_{k} are non-increasing and whose high order coefficient matrix G_{∞} has rank k. The degree δ is in this case equal to δ = ∑_{i} ν_{i} and we say that G(z) is in column proper form. The ordered indices ν_{1} ≥ ⋯ ≥ ν_{k} are invariants of the convolutional code and we call these indices the column degrees or Kronecker indices of the convolutional code C.

For any n-component vector v ∈ 𝔽^{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 𝔽^{n} is then the sum of the weights of all its coefficients. Finally we define the free distance of the convolutional code C ⊂ 𝔽^{n}[z] through:

d_{free} = min{wt(v(z)) | v(z) ∈ C, v(z) ≠ 0}.

Remark 1.1. The module theoretic approach as presented above is slightly nonstandard. In the coding literature [1, 3, 10] convolutional codes are usually defined as linear subspaces (i.e. submodules) of R^{n} where R is either the field of rationals 𝔽(z) or the field of formal Laurent series 𝔽((z)). If the code is defined over 𝔽((z)) it has to be required that the code is generated by an n × k polynomial generator matrix G(z). Over 𝔽(z) such a representation is guaranteed. The column span of G(z) with respect to 𝔽[z] corresponds then to the finite weight code words of the column span generated by G(z) with respect to 𝔽(z). The restriction to finite weight code words is of little significance. In fact McEliece [9, Section 2] 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 δ can be equipped with the structure of a variety and this explains our preference for the module theoretic approach.

The paper is structured as follows: In Section 2 we give a natural bound on the free distance which codes of rate k/n and degree δ must satisfy. This bound naturally generalizes the Singleton bound [8, Chapter 1] of linear block codes. The main theorem (Theorem 2.10) 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 3 we exhibit some first order representations for the convolutional codes that are used along the paper. In Section 4 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.

2. Main Results

Let C be a convolutional code of rate k/n and degree δ defined over an arbitrary base field 𝔽. Let G be a polynomial encoder in column proper form with ordered column degrees ν_{1} ≥ ⋯ ≥ ν_{k}. We have the following upper bound on the free distance of the code:

Lemma 2.1. Let ℓ be the number of indices ν_{i} among the ordered indices ν_{1} ≥ ⋯ ≥ ν_{k} having the value ν_{i} = ν_{k}. Then the free distance must satisfy

d_{free} ≤ n(ν_{k} + 1) − ℓ + 1. (2.1)

Proof. Let G_{∞} 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 ℓ columns of the matrix G_{∞} into a matrix \left[{I_{ℓ} \atop M}\right] where M is a matrix of size (n − ℓ) × ℓ over 𝔽. The transforming operations can be done by an invertible matrix T ∈ Gl_{ℓ} which acts on the last ℓ 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 ν_{i}.

After this transformation the last column of the new generator matrix G(z) will have (ℓ − 1) polynomials of weight strictly less than ν_{k} + 1, one with weight exactly ν_{k} + 1, and the remaining (n − ℓ) polynomials with weight less or equal than ν_{k} + 1. Therefore the input (0, 0, …, 0, 1)^{t} gives a codeword with weight less or equal than

(ℓ − 1)ν_{k} + (ν_{k} + 1) + (n − ℓ)(ν_{k} + 1) = n(ν_{k} + 1) − ℓ + 1.

This gives the upper bound (2.1).

The set of rate k/n convolutional codes of degree δ is partitioned into sets of codes with different column degrees ν_{1} ≥ ⋯ ≥ ν_{k}. Taking the maximum of the bound (2.1) over all such possible sets we obtain the following:

Theorem 2.2. For every base field 𝔽 and every rate k/n convolutional code C of degree δ, the free distance is bounded by:

d_{free} ≤ (n − k) (⌊δ/k⌋ + 1) + δ + 1. (2.2)

Proof. The upper bound (2.1) is largest if ν_{k} is as large as possible and ℓ as small as possible. The largest possible value for ν_{k} is ν_{k} = ⌊δ/k⌋. Minimizing ℓ results in the constraint length values

ν_{1} = ⌊δ/k⌋ + 1, ⋯, ν_{k−ℓ} = ⌊δ/k⌋ + 1, ν_{k−ℓ+1} = ⌊δ/k⌋ , ⋯, ν_{k} = ⌊δ/k⌋ .

Substituting ν_{k} = ⌊δ/k⌋ and ℓ = k − δ + k ⌊δ/k⌋ in (2.1) we get the bound (2.2).

Remark 2.3. In the systems literature, the above set of indices are sometimes referred to as the ‘generic set of column indices’. McEliece [9, Section 4] calls a code having a right prime generator matrix with the generic set of column indices ‘a compact code’.

Remark 2.4. The upper bound (2.2) on the free distance seems to be new. In the coding literature [2, 3, 9] 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 𝔽_{q}. In contrast to this, (2.2) is valid for any field (even an infinite field) and we believe that the bound naturally generalizes the Singleton bound.

The main theorem 2.10 will state that there exist always rate k/n convolutional codes of degree δ whose free distance is equal to the right hand side of (2.2). Based on this we define:

Definition 2.5. A rate k/n code of degree δ whose free distance achieves the upper bound given in (2.2) will be called an MDS convolutional code. The bound (2.2) will be called the generalized Singleton bound.

Remark 2.6. MDS convolutional codes were defined before in the literature. Justesen and Hughes [5] 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 [11] consider MDS convolutional codes with respect to a nonstandard Hamming metric. They consider subspaces of R^{n} where R = 𝔽(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 = 𝔽(z) and the standard Singleton bound (1.1) applies.

The concepts studied in [5, 11] are therefore different from the MDS concept we consider in this paper.

The following lemma gives sufficient conditions for a code to be an MDS convolutional code: Lemma 2.7. If a codeword v(z) in C has the property that any of its k components have weight at least (δ + 1) then the weight of the codeword v(z) is necessarily greater than or equal to (n − k) (⌊δ/k⌋ + 1) + δ + 1. (2.3)

We will refer to the property that any k components of an n component vector have weight more than δ + 1 as the weight property.

Proof. Let

v(z) = ( v_{1}(z) , …, v_{n}(z) )^{t} ∈ 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 ⌊δ/k⌋ + 1. Indeed, taking the first k components of v, by the weight property, the sum of their weight is ≥ δ + 1, therefore there is one component, say v_{1} , with the weight ≥ ⌊δ/k⌋ + 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 ≥ ⌊δ/k⌋ + 1. With this reasoning we obtain that at least n − k + 1 of the components must have the weight more or equal to ⌊δ/k⌋ + 1. We have now that n − k of the components have weight at least ≥ ⌊δ/k⌋ + 1, and from the weight property that the remaining k components have weight greater than δ + 1. Therefore

wt(v(z)) ≥ (n − k) (⌊δ/k⌋ + 1) + (δ + 1)

which is equal to the upper bound 2.2.

Before we state the main theorem we summarize some known results:

For δ = 0 the bound (2.2) coincides with the Singleton bound (see e.g. [8]). In this situation we therefore have: Lemma 2.8. If G is an n × k generator of an MDS block code then G generates also an MDS convolutional codes of rate k/n, degree δ = 0 and free distance n − k + 1. In particular if |𝔽| ≥ n, MDS convolutional codes of rate k/n and degree 0 do exist.

The next result implies that rate 1/n MDS codes do exist for every value of δ. The result was derived by Justesen [4]. A systems theoretic proof of this result is given in [18]. Theorem 2.9 ([4]). Let δ, n be fixed and assume that 𝔽 is a finite field with q := |𝔽| > 3δ elements. Then there exists a rate 1/n MDS convolutional code.

The main result of this paper now states: Theorem 2.10. For any rate k/n and any degree δ there exist MDS convolutional codes for sufficiently large field sizes.

The proof of Theorem 2.10 will be given in Section 4.

3. First order representations for convolutional codes

This section reviews some first order representations for convolutional codes that are heavily used in the next sections. As it was shown in [15] we have the following existence and uniqueness theorems:

Theorem 3.1. Assume C ⊂ 𝔽^{n}[z] is a rate k/n convolutional code of degree δ. Let 𝕂 be the algebraic closure of 𝔽. Then there exist matrices K, L ∈ 𝔽^{(δ+n−k)×δ} and M ∈ 𝔽^{(δ+n−k)×n} such that:

C = {v(z) ∈ 𝔽^{n}[z] | ∃x(z) ∈ 𝔽^{δ}[z] : (zK + L)x(z) + Mv(z) = 0}. (3.1)

Moreover, the following conditions are satisfied:

1. K has full column rank;

2. (K | M) has full row rank;

3. rank (z_{0}K + L | M) = δ + n − k, ∀z_{0} ∈ 𝕂.

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 δ = 0, (3.1) reduces to the parity check equation Mv(z) = 0. The representation (3.1) is unique in the following sense:

Theorem 3.2. 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

(K′, L′, M′) = (SKT^{−1}, SLT^{−1}, SM) (3.2)

for some T ∈ Gl_{δ+k}(𝔽) and S ∈ Gl_{δ+n−k}(𝔽).

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 [15, Section IV]):

K = [ \begin{matrix}I_{δ} \\ 0 \end{matrix} ] , L = [ \begin{matrix}−A \\ −C \end{matrix} ] , M = [ \begin{matrix}0 & −B \\ I_{n−k} & −D \end{matrix} ] .

In the partitioning, A ∈ 𝔽^{δ×δ}, B ∈ 𝔽^{δ×k}, C ∈ 𝔽^{(n−k)×δ} and D ∈ 𝔽^{(n−k)×k}. Let:

x(z) = x_{0}z^{γ} + x_{1}z^{γ−1} + … + x_{γ}; x_{t} ∈ 𝔽^{δ}, t = 0, …, γ,
v(z) = v_{0}z^{γ} + v_{1}z^{γ−1} + … + v_{γ}; v_{t} ∈ 𝔽^{n}, t = 0, …, γ.

If one partitions the vector v_{t} into v_{t} = \binom{y_{t}}{u_{t}}, 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{aligned}x_{t+1} & = & Ax_{t} + Bu_{t} \\ y_{t} & = & Cx_{t} + Du_{t}, x_{0} = 0, x_{γ+1} = 0. \end{aligned} (3.3)

This system is known as the input/state/output representation for a convolutional code. It describes the dynamics for a systematic and rational encoder. We refer to [15, 17, 19] for more details.

We say that the matrices (A, B) form a controllable pair if

rank (B AB … A^{δ−1}B) = δ,

and we say that (A, C) form an 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 [15, 17, 19] that the system (3.3) represents a non-catastrophic convolutional code of degree δ 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:

Theorem 3.3 ([15]). Let r := max{n − k, k}, and assume that the cardinality of the field 𝔽 satisfies

|𝔽| > δr ⌈\frac{δ}{n − k} ⌉ .

Then there exists a rate k/n convolutional code of degree δ having free distance

d_{free} ≥ δ + 1.

Remark 3.4. The proof of Theorem 3.3 as given in [15] 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 δ + 1 is only a fraction away from the optimal upper bound (2.2). For low rates the distance of δ + 1 is less than optimal.

In order to prove Theorem 2.10 we will need a strengthening of Theorem 3.3:

Theorem 3.5. Let δ, k, n, ρ be fixed and assume that

ρ = δ (2 ⌈\frac{δ}{n − k} ⌉ + ⌊\frac{δ}{k} ⌋ + 1) .

If the matrices A, B, C have the property that (B AB … A^{ρ−1}B) is the parity check of an MDS block code and that (C^{t} A^{t}C^{t} … A^{ρ−1}^{t}C^{t}) is the generator matrix of an MDS block code then for any codeword

v(z) = \binom{y(z)}{u(z)} ∈ 𝔽^{n}[z]

either

wt(u(z)) ≥ δ + 1 or wt(v(z)) ≥ (n − k) (⌊δ/k⌋ + 1) + δ + 1.

Before we give the proof we want to mention that the choice of ρ is not the minimum that we can have so that the result is correct. The proof for a smaller choice of ρ would involve more cases. For the purpose of this paper this is not necessary.

Proof. Assume

u(z) = u_{0}z^{γ} + u_{1}z^{γ−1} + ⋯ + u_{γ},
y(z) = y_{0}z^{γ} + y_{1}z^{γ−1} + ⋯ + y_{γ},

where γ is the degree of v, and that u_{0} ≠ 0. The first equations of the systems (3.3) give that (see [15]):

(u_{γ}, …, u_{0})^{t} ∈ ker (B AB … A^{γ}B) .

If γ < ρ then wt(u(z)) ≥ δ + 1 and the proof is complete.

We therefore assume that γ ≥ ρ and that wt(u(z)) ≤ δ. By the ‘pigeonhole principle’ there exist an index i < ρ − \frac{ρ}{δ} and an input sequence

u_{i+1} = u_{i+2} = ⋯ = u_{i+ \frac{ρ}{δ}} = 0.

In analogy to the proof of [17, Theorem 3.1] it follows that the state x_{i+1} ≠ 0 and that

( y_{i+1} ; y_{i+2} ; ⋮ ; y_{i+ \frac{ρ}{δ}} ) = ( C ; CA ; ⋮ ; CA^{\frac{ρ}{δ} −1} ) x_{i+1}.

The assumption on the matrix (C^{t} A^{t}C^{t} … A^{ρ−1}^{t}C^{t}) gives that

wt(y) ≥ (n − k) · \frac{ρ}{δ} − δ + 1 = (n − k) (2 ⌈\frac{δ}{n − k} ⌉ + ⌊\frac{δ}{k} ⌋ + 1) − δ + 1
≥ 2δ + (n − k) (⌊\frac{δ}{k} ⌋ + 1) − δ + 1 = (n − k) (⌊\frac{δ}{k} ⌋ + 1) + δ + 1.

In the proof of Theorem 2.10 the following lemma will be needed:

Lemma 3.6. Let δ, k, n, ρ be fixed, r = max{n−k, k} and assume that the cardinality of the field 𝔽 satisfies |𝔽| > rρ. Then there exist matrices A, B, C satisfying the conditions of Theorem 3.5.

Proof. Let α ∈ 𝔽 be an element of multiplicative order at least rρ. Then

A := ( \begin{matrix}α^{r} & 0 & ⋯ & 0 \\ 0 & α^{2r} & ... & ⋮ \\ ⋮ & ... & ... & 0 \\ 0 & ⋯ & 0 & α^{δr} \end{matrix} ) , B := ( \begin{matrix}1 & α & α^{2} & ⋯ & α^{k−1} \\ 1 & α^{2} & α^{4} & ⋯ & α^{2(k−1)} \\ ⋮ & ⋮ & ⋮ & & ⋮ \\ 1 & α^{δ} & α^{2δ} & ⋯ & α^{δ(k−1)} \end{matrix} ) ,

C := ( \begin{matrix}1 & ⋯ & 1 \\ α & ⋯ & α^{δ} \\ α^{2} & ⋯ & α^{2δ} \\ ⋮ & & ⋮ \\ α^{n−k−1} & ⋯ & α^{δ(n−k−1)} \end{matrix} )

satisfy the conditions of Theorem 3.5.

4. Proof of the main result

In this section we will give the proof for Theorem 2.10, 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 δ using a large 𝔽-vector space, where 𝔽 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 𝔽 which is itself a finite field.

For the parameterization we will use the first order representation as presented in Theorem 3.1 of Section 3. We do this by viewing a triple of matrices (K, L, M) as a point in the vector space 𝔽^{(δ+n−k)(2δ+n)}. By Theorem 3.2 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 δ exactly. We start the proof with a short Lemma:

Lemma 4.1. The set of matrices (K, L, M) satisfying the property 1, 2 and 3 of Theorem 3.1 is open and nonempty inside 𝔽^{(δ+n−k)(2δ+n)}.

Proof. We recall from the paper of Ravi and Rosenthal [13] that the conditions 2 and 3 can be equivalently written as the following rank condition:

\underbrace{[ \begin{matrix}K & 0 & … & 0 & M & 0 & … & … & 0 \\ L & K & ... & ⋮ & 0 & M & ... & & ⋮ \\ 0 & L & ... & 0 & ⋮ & ... & ... & ... & ⋮ \\ ⋮ & ... & ... & K & ⋮ & & ... & M & 0 \\ 0 & … & 0 & L & 0 & … & … & 0 & M \end{matrix} ]}_{2δ − 1 blocks} δ blocks (4.1)

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 (4.1) being 0. Therefore the set of all matrix 3-tuples (K, L, M) satisfying the conditions 1, 2, 3 is open in 𝔽^{(δ+n−k)(2δ+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.

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

Proof of Theorem 2.10. Let 𝔽 be a fixed finite field, with q elements, having characteristic p. Let 𝕂 denote the algebraic closure of 𝔽. As an algebraically closed field, 𝕂 is infinite. We will call a matrix with all full size minors invertible, an MDS matrix.

Consider now some fixed numbers δ, k, n, ρ with k < n and ρ chosen as in Theorem 3.5.

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 3.1, such that the matrix [K | M] 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 [K | M]. Over the algebraic closure 𝕂, the intersection of nonempty open sets is nonempty and V is therefore a nonempty Zariski open set in 𝕂^{(δ+n−k)(2δ+n)}.

Let now (K, L, M) be an element in V, and let

j = {1 ≤ j_{1} < j_{2} < … < j_{k} ≤ n}

be a subset of the set {1, …, 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) | i = 1, …, k}, of a code word v(z) ∈ C satisfy either

∑_{i=1}^{k} wt(v_{j_{i}}(z)) ≥ δ + 1 or wt(v(z)) ≥ (n − k) (⌊δ/k⌋ + 1) + δ + 1.

In order to apply Theorem 3.5, let P_{j} be an n × n permutation matrix such that

P_{j}v(z) = \binom{y(z)}{u(z)}

where the k components v_{j_{1}}(z), …, v_{j_{k}}(z) of v(z) are mapped onto the k components of u(z).

Partition the matrix MP_{j}^{−1} = [M_{1} | N] where M_{1} is the matrix formed by the first n − k columns of MP_{j}^{−1} and N denotes the rest of the columns in MP_{j}^{−1}. The property of V tells us that the matrix [K | M_{1}] is invertible.

For every K, L, M and every j we define matrices A_{j}, B_{j}, C_{j}, D_{j} in the following way:

[K | M_{1}]^{−1} [K | L | MP_{j}^{−1}] =: [ \begin{matrix}I_{δ} & −A_{j} & 0 & −B_{j} \\ 0 & −C_{j} & I_{n−k} & −D_{j} \end{matrix} ] . (4.2)

Rewriting the equation (3.1) in the new terms we obtain the (A, B, C, D) polynomial description from the previous chapter:

[ \begin{matrix}zI_{δ} − A_{j} & 0 & −B_{j} \\ −C_{j} & I_{n−k} & −D_{j} \end{matrix} ] [ \begin{matrix}x(z) \\ y(z) \\ u(z) \end{matrix} ] = 0. (4.3)

If the matrices A_{j}, B_{j}, C_{j} satisfy the conditions of Theorem 3.5 then the weight ∑_{i=1}^{k} wt(v_{j_{i}}(z)) ≥ δ + 1 or the weight of v(z) is larger than the bound (2.2).

The algebraic conditions on A, B, C expressed in Theorem 3.5 translate into algebraic conditions inside the parameter space 𝕂^{(δ+n−k)(2δ+n)}. Let

S_{j} = {(K, L, M) ∈ 𝔽^{(δ+n−k)(2δ+n)} s.t.
(B_{j} A_{j}B_{j} … A_{j}^{ρ−1}B_{j}) and (C_{j}^{t} A_{j}^{t}C_{j}^{t} … A_{j}^{ρ−1}^{t}C_{j}^{t}) are MDS}.

Applying Lemma 3.6 one sees that S_{j} ∩ V is a nonempty Zariski open subset of 𝕂^{(δ+n−k)(2δ+n)}.

Let J = {j = {1 ≤ j_{1} < j_{2} < … < j_{k} ≤ n}} be the set of all k-subsets of {1, …, n}, and consider all {S_{j} ∩ V | j ∈ 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_{j} ∩ V.

So far we obtained a vector x ∈ V having the components in 𝕂, the algebraic closure of 𝔽, and laying in the intersection

⋂_{j∈J}(S_{j} ∩ V) ⊂ V ⊂ 𝕂^{(δ+n−k)(2δ+n)}.

Since the extension 𝔽 ⊂ 𝕂 is algebraic, it implies that every component of x is algebraic over 𝔽, therefore in a finite extension. If we denote with x_{j} the components of x we have that all x_{j} ∈ 𝔽[x_{j}, 1 ≤ j ≤ (δ+n−k)(2δ+n)], which is a finite extension over 𝔽, 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 𝔽_{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 (2.2). Let

v(z) = ( v_{1}(z) , …, v_{n}(z) )^{t} ∈ C

be a nonzero code word. We will show that the weight of v(z) is larger than the upper bound by applying Lemma 2.7 and Theorem 3.5.

Since the code C belongs to the intersection of all the Zariski open sets S_{j} ∩ V, we can apply Theorem 3.5 for all the k-combinations of the components v_{1}, v_{2}, …, v_{n} to form the part u of the codeword. By construction of the sets S_{j}∩V, we get that either the weight of the k-combination of components v_{1}, v_{2}, …, v_{n} is more than δ + 1, or the weight of the whole codeword is larger than

(n − k) (⌊δ/k⌋ + 1) + δ + 1

which is the bound we want. If we have the first situation for all k-combinations of the components we get the conditions of Lemma 2.7. The weight of the codeword is therefore greater then the upper bound (2.2). In either case we predict the existence of an MDS code C over the finite field 𝔽_{q^{m}}.

Remark 4.2. The proof does not construct MDS convolutional codes in an explicit way. Concrete constructions exist when δ = 0 (Reed-Solomon construction) and when k = 1 (see Theorem 2.9).

5. 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 [7, 12, 13] a submodule of rank k and degree δ in 𝔽^{n}[z] describes a quotient sheaf of rank k and degree δ over the projective line ℙ^{1}. The column degrees ν_{1} ≥ ⋯ ≥ ν_{k} of the submodule C ⊂ 𝔽^{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 δ with the structure of a scheme. Such a scheme is referred to as a quot scheme in the algebraic geometry literature. The quot scheme which parameterizes the rank k submodules of degree δ turns out to be a smooth projective variety [12]. This variety has been of prominent interest recently in the area of conformal quantum field theory and we refer to [14] for more details.

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

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 [6]. It was pointed out by Lomadze [7] that a matrix pencil of the form [zK + L | M] 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 (3.2) as a group action of the reductive group Gl_{δ+k} × Gl_{δ} on the vector space consisting of all matrix triples (K, L, M) of a fixed size. The uniqueness Theorem 3.2 expresses the fact that the group orbits in (3.2) correspond to the submodules of 𝔽^{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 (3.2) is exactly the Grothendieck quot scheme. The minimality conditions provided in Theorem 3.1 and characterized by the set V ⊂ 𝔽^{(δ+n−k)(2δ+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 3.2. The reader who is interested in more details is referred to [13]. For the purpose of this paper the following is important. The open set V ⊂ 𝔽^{(δ+n−k)(2δ+n)} which we introduced in the proof of Theorem 2.10 describes exactly the stable orbits and the quotient of V under the group action (3.2) describes the Grothendieck quot scheme X_{k,n}^{δ}. The sets S_{j} induces Zariski open sets inside the scheme X_{k,n}^{δ} and by abuse of notation we will denotes these sets with S_{j} as well. The set of MDS convolutional codes contains then the Zariski open subset

⋂ S_{j} ⊂ X_{k,n}^{δ}.

The main result states that ⋂ S_{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 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 δ as soon as the field size is sufficiently large.

For δ = 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 |𝔽| ≥ n is sufficient to guarantee that the set is nonempty. In particular the existence of MDS block codes over the field 𝔽(z) as studied by Piret and Krol [11] follows from our theory.

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 δ > 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:

(5.1)  <, >: 𝔽^{n}[z] × 𝔽^{n}[z] ⟶ 𝔽[z]
(v(z), w(z)) ⟼ v(z)w(z)^{t}.

Using this bilinear form we define the dual of a code C as

C^{⊥} := {w(z) |< v(z), w(z) >= 0, ∀v(z) ∈ C}.

One always has that

C^{⊥⊥} ⊇ C.

If the code C has a minimal basis encoder (i.e. it is non-catastrophic) then C^{⊥⊥} = C.

The following two lemmas cover some cases where the dual of an MDS convolutional code is MDS.

Lemma 5.1. If C is a convolutional code of degree δ = 0 then C is MDS if and only if C^{⊥} is MDS.

Lemma 5.2. Assume k = 1, n = 2. A non-catastrophic code C of rate 1/2 is MDS if and only if C^{⊥} is MDS.

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 δ = 1 and the finite field is 𝔽_{3}:

Example 5.3. Let k = 1, n = 3, δ = 1 and consider the generator matrix

G(z) = ( (z + 2) (z + 1) (z + 1) )^{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) ∈ 𝔽^{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^{⊥} = ( \begin{matrix}z + 1 & 0 \\ 0 & 1 \\ 2z + 1 & 2 \end{matrix} ) ,

which is not MDS.

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 [16] more details on the issue of duality of MDS convolutional codes were given.

References

[1] G. D. Forney. Convolutional codes I: Algebraic structure. IEEE Trans. Inform. Theory, IT-16(5):720–738, 1970.

[2] R. Johannesson and K. Zigangirov. Distances and distance bounds for convolutional codes – an overview. In Topics in Coding Theory. In honour of L. H. Zetterberg., Lecture Notes in Control and Information Sciences # 128, pages 109–136. Springer Verlag, 1989.

[3] R. Johannesson and K. Sh. Zigangirov. Fundamentals of Convolutional Coding. IEEE Press, New York, 1999.

[4] J. Justesen. An algebraic construction of rate 1/ν convolutional codes. IEEE Trans. Inform. Theory, IT-21(1):577–580, 1975.

[5] J. Justesen and L.R. Hughes. On maximum-distance-separable convolutional codes. IEEE Trans. Information Theory, IT-20:288, 1974.

[6] M. Kuijper. First-Order Representations of Linear Systems. Birkhäuser, Boston, 1994.

[7] V. Lomadze. Finite-dimensional time-invariant linear dynamical systems: Algebraic theory. Acta Appl. Math, 19:149–201, 1990.

[8] F. J. MacWilliams and N. J.A. Sloane. The Theory of Error-Correcting Codes. North Holland, Amsterdam, 1977.

[9] R.J. McEliece. The algebraic theory of convolutional codes. In R. Brualdi, W.C. Huffman, and V. Pless, editors, Handbook of Coding Theory. Elsevier Science Publishers, Amsterdam, The Netherlands, 1998. To appear.

[10] Ph. Piret. Convolutional Codes, an Algebraic Approach. MIT Press, Cambridge, MA, 1988.

[11] Ph. Piret and T. Krol. MDS convolutional codes. IEEE Trans. Inform. Theory, 29(2):224–232, 1983.

[12] M. S. Ravi and J. Rosenthal. A smooth compactification of the space of transfer functions with fixed McMillan degree. Acta Appl. Math, 34:329–352, 1994.

[13] M. S. Ravi and J. Rosenthal. A general realization theory for higher order linear differential equations. Systems & Control Letters, 25(5):351–360, 1995.

[14] M. S. Ravi, J. Rosenthal, and X. Wang. Degree of the generalized Plücker embedding of a quot scheme and quantum cohomology. Math. Ann., 311(1):11–26, 1998.

[15] J. Rosenthal, J. M. Schumacher, and E.V. York. On behaviors and convolutional codes. IEEE Trans. Inform. Theory, 42(6):1881–1891, 1996.

[16] J. Rosenthal and R. Smarandache. On the dual of MDS convolutional codes. In Proc. of the 36th Annual Allerton Conference on Communication, Control, and Computing, 1998. To appear.

[17] J. Rosenthal and E.V. York. BCH convolutional codes. Technical report, University of Notre Dame, Dept. of Mathematics, October 1997. Preprint # 271. Available at http://www.nd.edu/˜ rosen/preprints.html.

[18] R. Smarandache and J. Rosenthal. A state space approach for constructing MDS rate 1/n convolutional codes. In Proceedings of the 1998 IEEE Information Theory Workshop on Information Theory, pages 116–117, Killarney, Kerry, Ireland, June 1998.

[19] E.V. York. Algebraic Description and Construction of Error Correcting Codes, a Systems Theory Point of View. PhD thesis, University of Notre Dame, 1997. Available at http://www.nd.edu/˜ rosen/preprints.html.

Department of Mathematics, University of Notre Dame, Notre Dame, Indiana 46556.

E-mail address: Rosenthal.1@nd.edu, Smarandache.1@nd.edu