A class of one-dimensional MDS convolutional codes

A class of one-dimensional convolutional codes will be presented. They are all MDS codes, i. e., have the largest distance among all one-dimensional codes of the same length n and overall constraint length delta. Furthermore, their extended row distances are computed, and they increase with slope n-delta. In certain cases of the algebraic parameters, we will also derive parity check matrices of Vandermonde type for these codes. Finally, cyclicity in the convolutional sense will be discussed for our class of codes. It will turn out that they are cyclic if and only if the field element used in the generator matrix has order n. This can be regarded as a generalization of the block code case.


Introduction
The main task of coding theory is the construction of powerful codes. This applies equally well to block codes and convolutional codes. In either case codes are required to have good error-correcting properties, i. e. a large distance, and an efficient decoding algorithm.
In block coding theory this goal has been achieved best by the class of Reed-Solomon codes along with their efficient algebraic decoding algorithm. These codes are in particular MDS (maximum distance separable), meaning that they have the largest distance possible among all codes with the same length and dimension. On the other hand there are convolutional codes, and despite their frequent and successful use in engineering practice, their mathematical theory is still in the beginnings. The algebraic theory of this class of codes has been initiated with the paper [2] of Forney and has seen a considerable development ever since.
In particular, quite some efforts have been made in the area of constructing convolutional codes with large distance. The first group of the according papers appeared in the seventies of the last century. In [10,13,11] quasi-cyclic block codes have been used in order to construct convolutional codes with good distance. The relation between the weights of the block codewords and the convolutional codewords is made by the weight-retaining property. This topic has been resumed later on in [22] where the ideas have been used to construct MDS convolutional codes with (almost) arbitrary algebraic parameters. Other more recent attempts of constructing good convolutional codes try to impose additional algebraic structure on the convolutional codes themselves. In [1] methods from algebraic geometry are used in order to construct convolutional codes of Goppa type. In the paper [8] system theoretic methods are used in order to analyze codes with optimal column distances. Finally, in [7] ideas from the seventies [16,18] have been resumed in order to impose a type of cyclicity on convolutional codes. The investigations of these cyclic convolutional codes have been continued in [5,4]. We will explain the notion of cyclicity later in Section 4 of this paper. At this moment we restrict ourselves to mentioning that cyclicity for convolutional codes is a more general notion than just the natural invariance of the code under cyclic shift.
In the present paper we will combine the two main lines mentioned above. We will present a class of one-dimensional codes that are not only MDS but also have extended row distances increasing with slope n − δ (where n is the length of the code and δ the overall constraint length). We will also compare the required field size needed for the construction with the field sizes of other constructions known in the literature. It will turn out that our field sizes are smaller for many parameters than what has been used before. For one set of parameters the field size is even only one above the theoretic minimum. In addition to these distance computations and field size investigations, we will also discuss the algebraic structure of these codes. As it turns out, for certain algebraic parameters the presented codes are cyclic in the sense mentioned above. In this case the codes can in fact be regarded as a generalization of (one-dimensional) Reed-Solomon codes. They even have a polynomial parity check matrix of Vandermonde type, showing that this class of codes are closely related to some of the codes given in [1].
The paper is organized as follows. In the rest of the introduction we will collect the preliminaries about convolutional codes. In Section 2 we will present the class of codes via their generator matrices along with their (extended row) distances and compare the field size to results from the literature. In Secton 3 various parity check matrices with Vandermonde structure are presented. In Section 4 we will introduce the notion of cyclicity for convolutional codes as it has been investigated in [7]. We will show that in a certain (to be expected) case our codes are cyclic, and we will present various representations of the codes. We will close with some open problems.
We end this introduction with the basic notions of convolutional coding theory. Convolutional codes are certain submodules of F[z] n , where F is a finite field. Before presenting the definition we wish to recall that each submodule S of F[z] n is free and therefore can be written as where k is the rank of S and G ∈ F[z] k×n is a matrix containing a basis of S. Hence, the matrix G is unique up to left multiplication by a matrix from Gl k (F[z]). Moreover, by resorting to the Smith normal form one easily shows that G is right-invertible, i. e., GG = I k for some matrixG ∈ F[z] n×k , if and only if the submodule im G is a direct summand of the module F[z] n . This in turn is equivalent to the existence of a matrix H ∈ F[z] (n−k)×n such that im G = ker H T := {v ∈ F[z] n | vH T = 0}. Using the theory of polynomial matrices it is easily seen that we may assume H to be right-invertible. Then it is unique up to left multiplication by a matrix from Gl n−k (F[z]). Obviously, the matrix H generates the dual module, i. e., im This makes all of the following notions well-defined.
k×n is a rightinvertible matrix such that δ = max{deg γ | γ is a k-minor of G}. We call G a generator matrix of the code. The number n is called the length, k is the dimension, and δ is called the overall constraint length of the code. Each right-invertible matrix H ∈ F[z] (n−k)×n satisfying C = ker H T is called a parity check matrix of C.
Thus, the convolutional codes of length n are the direct summands of F[z] n . It is worth mentioning that a code with overall constraint length zero can be regarded as a block code. In the coding literature a right invertible matrix is often called basic [2, p. 730] or delay-free and non-catastrophic, see [14, p.1102]. Sometimes in the literature convolutional codes are defined as subspaces of the vector space F((z)) n of vector valued Laurent series over F, see for instance [14] and [2]. However, as long as one restricts to right invertible generator matrices it does not make a difference whether one works in the context of infinite message and codeword sequences or finite ones, see also [20,19].
The most important concept for a code is its distance. It measures the error-correcting capability, hence the quality, of the code. The definition of the distance of a convolutional code is straightforward. For a polynomial vector v = N j=0 v j z j ∈ F[z] n the weight is defined as wt(v) = N j=0 wt(v j ), where wt(v j ) denotes the usual Hamming weight of v j ∈ F n . Then the (free) distance of a code C ⊆ F[z] n with generator matrix G ∈ F[z] k×n is given as Just like for block codes there exist quite some bounds on the distance of convolutional codes. One of them is the generalized Singleton bound [21,Thm. 2.2]. It states that the distance d of a code with parameters (n, k, δ) over any field satisfies d ≤ S(n, k, δ) := (n − k) δ k + 1 + δ + 1.

A class of one-dimensional MDS codes
In this section we present a construction of one-dimensional MDS convolutional codes. The distance will be computed straightforwardly. We will then compare our results with constructions known from the literature. Thereafter we will also compute the extended row distances. We will derive that they are increasing with a slope of n − δ.
Theorem 2.1 Let n ∈ N and 0 ≤ δ ≤ n − 1 and let q be a prime power such that n ≤ q − 1. Put F := F q and choose an element α ∈ F such that ord(α) ≥ n. Define and let C := im G ⊆ F[z] n . Then G is right invertible, i. e., the submodule C is a convolutional code, and dist(C) = n(δ + 1). In other words, C is an MDS code with parameters (n, 1, δ).
Notice that for δ = 0 the code is simply the n-fold repetition (block) code over F and the assertions are obvious.
Proof: In order to show that G is right invertible, we have to prove that the entries of the matrix G are coprime. In other words, it needs to be proven that the polynomials have no common root in any extension fieldF of F. In order to see this, assume β ∈F is such a common root. Then β, αβ, . . . , α n−1 β are roots of δ ν=0 z ν . Since β = 0 and ord(α) ≥ n, these numbers are pairwise different and δ < n leads to a contradiction.
, where t ≥ 0 and u 0 = 0 = u t , and put for ν = 0, . . . , δ + t. Notice that for ν ≤ δ the first row, G ν , ofG ν is nonzero while for ν ≥ t the last row, G ν−t , is nonzero. Since u 0 = 0 = u t this will provide us with a good estimate of the weight of v ν for these indices. In order to see this, note that for each index ν the nonzero rows ofG ν are consecutive and form a matrix of the type This will now be used for counting the weight of the vectors v ν for ν ∈ {0, . . . , δ, t, . . . , δ+t}.

case: t > δ
In this case the indices 0, . . . , δ, t, . . . , δ + t are all different and we havẽ and all displayed rows G ℓ are nonzero. Thus, using (2.2), and therefore where the last inequality follows from δ < n.
Remark 2.2 It is not hard to see that the matrix G in (2.1) is also right-invertible for all δ ≥ n for which ord(α) ∤ δ + 1. Examples show that these codes often have a large distance, too, but are not MDS in general. However, we can not provide any general result in this case.
We would like to comment on the field size required for the construction of the MDS codes in Theorem 2.1. In [11,Lemma 1] and [5,Thm. 3.7] it has been shown that if C is an (n, 1, δ)-MDS code over F q then q ≥ δ + 1. In Theorem 2.1 the field size q satisfies q ≥ n + 1 ≥ δ + 2. Thus, in the case n = ord(α) = q − 1 and δ = n − 1 our field size is just one above the lower bound given above. As to our knowledge it is not known in general whether there exist (n, 1, n − 1)-MDS codes over F n (in the case where n is a prime power).
We also would like to compare our results with previous constructions of MDS codes.
In [11] MDS codes with parameters (n, 1, δ) for certain combinations have been constructed. However, these combinations are different from ours. For instance, the result in [11, Thm. p. 580] does not contain the case of (q − 1, 1, q − 2)-MDS codes over F q and no On the other hand, the construction of that theorem allows the construction of a (17, 1, 20)-MDS code over F 32 which is not part of our Theorem 2.1. In [23] a construction of (n, 1, δ)-MDS codes is given over fields F q where q > δn+1. Except for the case δ = 1 this is a considerably bigger field size than ours where q ≥ n + 1. However, the construction in [23] works for all δ and not just for δ < n.
Another construction of MDS codes is given in [22]. Therein, MDS codes with (almost) arbitrary parameters (n, k, δ) are constructed over fields F q of size q ≥ δn 2 k(n−k) + 2. The construction is based on cyclic block codes with large distance. In the case k = 1 this again amounts to a considerably bigger field than in our construction. Alternatively, one can also see directly that our codes are not derived from good cyclic block codes in the sense of [22], i. e., the polynomial g = n j=1 z j−1 G j (z n ) derived from G = G 1 (z), . . . , G n (z) does not generate a good cyclic block code in general.
We want to go into more details about the weight distribution of these codes and therefore give also lower bounds for the extended row distances. The extended row distances have been introduced in [12, p. 541] and are very closely related to the trellis structure of the code and thus to its performance. Details on the importance of these distance parameters can be found in [12] 1 . The jth extended row distance amounts to the minimum weight of all paths through the state diagram starting at the zero state and which reach the zero state after exactly j steps for the first time. In other words, it is the minimum weight of all atomic codewords of degree j − 1 (i. e., length j) in the sense of [15]. The details are also explained in [9,Sec. 3.10]. In our case where the dimension of the code is k = 1, the atomic codewords are easily described. We will confine ourselves to the following property. It follows readily from the fact that the last δ coefficients of the message u ∈ F[z] make up the current state in the state diagram.
. Then the following are equivalent.
(i) The codeword uG is atomic (i. e., the associated path through the state diagram does not pass through the zero state except for its starting and end point). (ii) The polynomial u ∈ F[z] does not have δ consecutive zero coefficients.
Having this property in mind, the jth extended row distance of the code C = im G is defined to bê Notice that deg(u) = j − δ − 1 implies deg(uG) = j − 1 and thus the associated path has length j. As for the index notation we diverge somewhat from the paper [12] where the index j equals the degree of the associated codewords while in our case it reflects the length.
Hence the extended row distances are bounded from below by a linear function with slope n − δ.
Before we prove this result we wish to mention that in a certain sense this result is the best one can expect. As Equation (2.7) below shows, the "middle" coefficients of a codeword are contained in an (n, δ + 1)-block code. The distance of this code is therefore a lower bound for the slope. In our case this code has optimum distance n − δ, therefore the weight of codewords increases at least linearly in the length with slope n − δ. However, in specific cases certain constellations of consecutive coefficients of the generator matrix might even allow a better row distance. After the proof we will present examples for both cases, where the estimate in Proposition 2.4 is actually an identity and where it is a strict inequality.

Thus it remains to consider the coefficients
and v is atomic, the vector ( In the following examples we consider various cases of the parameters n and δ in Theorem 2.1. We computed the exact weight distribution (see [15,Sec. 3]) of the codes using Maple.
In this case one can show that the weight distribution is given by (see, e. g., [9, Sec. 3.10] and [15]) meaning that all atomic codewords of length j have weight 2 + 2j and that there exist 3 j−1 of such codewords for each j ≥ 2. As a consequence, the estimate in Proposition 2.4 is an equality, i. e.,d r j = 2 + 2j. One can also present explicitly an atomic codeword of length j and weight 2 + 2j. Indeed, it can be shown directly that wt ( j−2 i=0 z i )G = 2 + 2j for each j ≥ 2. (2) Let δ = 1, char(F) = 2 and n be arbitrary. Then it is easy to see that wt ( j−2 i=0 z i )G = 2 + j(n − 1) for each j ≥ 2, hence the estimate in Proposition 2.4 is an identity.
(3) Let δ = 2 and, again, n = 3, F = F 4 . Then G as defined in Theorem 2.1 is given by In this case the weight distribution is meaning, for instance, that there are 36 atomic codewords of length five, 9 of which have weight 11 and 14, respectively, and 18 have weight 13. Using induction it is easy to see that in the series expansion for each j ≥ 3 the coefficient of L j is divisible by W 6+j but not by W 7+j . Hence,d r j = 6 + j, and, like in (2), the estimate in Proposition 2.4 is an equality. Again, in this case one has wt ( j−3 i=0 z i )G = 6 + j for each j ≥ 3.
(4) In general however, the inequality for the jth extended row distance is not an equality and the growth rate can even be better. This happens for instance for n = 3, δ = 2 and F = F 8 with, of course, ord(α) = 7. In this case the weight distribution of the code in Theorem 2.1 is where each sum "+ . . ." is meant to contain only higher powers of W . This shows that the weight distribution is even better than the lower bound given in Proposition 2.4.

Parity check matrices with Vandermonde structure
In this section we will derive two types of parity check matrices for the codes of Theorem 2.1 in the case where ord(α) = n = δ + 1, one of them being minimal in the sense of [3, p. 459].
Both reveal a type of Vandermonde structure for these codes.
The condition ord(α) = n is necessary for the theorem to be true. As can easily be checked the product GH T is, in general, not zero if ord(α) > n.
Proof: (1) For j = 1, . . . , n let H (j) ∈ F[z] (n−1)×(n−1) be the submatrix of H obtained by omitting the jth column. Then, due to the Vandermonde structure of H, we obtain Since ord(α) = n, the last factor is nonzero for each j. But then the first factors show the coprimeness of the maximal minors of H, and thus H is right-invertible [14, Thm. A.1].
(2) Let G be given as above. Then for j = 1, . . . , n the jth entry G j is of the form where for the last equality we used ord(α) = n. Thus, Now we can prove GH T = 0. For easier indexing we will write down the sums of the matrix product backwards. Then we have to show that This is equivalent to In order to see this, compute Notice that for fixed µ = 0, . . . , j we have µ + 1 ∈ {1, . . . , j + 1} and j ≤ n − 2 yields α µ+1 = 1 due to ord(α) = n. Therefore, One should notice that the parity check matrix H is highly non-minimal, i. e., it is not a minimal basis for the dual code C ⊥ (for the notion of minimal basis see [3, p. 459] with 0 ≤ r ≤ s ≤ n − 1, i. e., with fewer rows than the matrix in Theorem 3.1, do not in general lead to good codes, even if ord(α) = n. This can easily be seen by running a few examples using, for instance, Maple. However, one should also notice the close relation of these matrices to those appearing in [1, Exa. 4.1]. In that paper methods from algebraic geometry are used to construct convolutional codes of Goppa type. A few examples of such matrices, but with different linear factors in the entries, are presented in [1] which are generator matrices of MDS convolutional codes. A deeper understanding as to whether there is a relation between the distance of the codes ker H T or im H and the Vandermonde structure of H must be considered as one of the main tasks in algebraic convolutional coding theory. It might also have some impact on the possibility of algebraic decoding of these codes.

Remark 3.2
With completely different methods it is possible to prove that also in the general case 0 ≤ δ < n = ord(α), the codes from Theorem 2.1 have a parity check matrix of a (somewhat modified) Vandermonde type. Indeed, in that case such a matrix is given by Hence H is right invertible and satisfies GH T = 0. The proof of this statement needs more detailed methods from the theory of cyclic convolutional codes as derived in [7] and will be omitted.
At the end of this section we will return to the case where δ = n − 1 and present a minimal parity check matrix, i. e., a right-invertible matrix with minimal row degrees in the sense of [3, p. 459] or [9,Sec. 2.5]. It shows that the dual code of im G has Forney index 1 (counted (n − 1) times) 2 and thus is a compact code in the sense of [14,Cor. 4.3]. Then H min is minimal and right-invertible and G H T min = 0, where G is again as in Theorem 3.1 (2). Hence in the case where ord(α) = n = δ + 1 the matrix H min is a parity check matrix of the code given in Theorem 2.1.
Proof: We use again the representation (3.1) for the matrix G. Writing down the sums of the product GH T min backwards again we obtain But the last expression is zero for all j = 1, . . . , n − 1 as we have shown in (3.3). From this we obtain that im H min ⊆ ker G T = (im G) ⊥ . Hence H min = BĤ, whereĤ is a parity check matrix of the code im G and B is some polynomial matrix. By [3,Thm. 3] the overall constraint length of imĤ is n − 1, too. On the other hand it is seen directly, that, firstly, the matrix H min has full row rank k and that, secondly, the overall constraint length of im H min is the sum of the row degrees of H min because the highest coefficient matrix of H min is a Vandermonde matrix with full row rank, see also [3, p. 495

Cyclicity
In this section we will show that for positive overall constraint length the codes given in Theorem 2.1 are cyclic if and only if ord(α) = n. Cyclic convolutional codes have been studied in detail in [7]. The first investigations in this direction have been made in the seventies by Piret [16] and Roos [18]. In both papers it has been shown (with different methods and in different contexts) that cyclicity of convolutional codes must not be understood in the usual sense, i. e. invariance under the cyclic shift, if one wants to go beyond the theory of cyclic block codes. As a consequence, Piret suggested a more complex notion of cyclicity which then has been further generalized by Roos. In both papers some nontrivial examples of cyclic convolutional codes in this new sense are presented along with their distances. All this indicates that the new notion of cyclicity seems to be the appropriate one in the convolutional case. Recently, in the paper [7] an algebraic theory of cyclic convolutional codes has been established which goes well beyond the results of the seventies. On the one hand it leads to a nice, yet nontrivial, generalization of the theory of cyclic block codes, on the other hand it gives a very powerful toolbox for constructing such codes. We will now give a very brief introduction into cyclicity for convolutional codes before investigating this additional structure for the codes of Theorem 2.1.
Just like for cyclic block codes we assume from now on that the length n and the field size |F| are coprime. Recall that a block code C ⊆ F n is called cyclic if it is invariant under the cyclic shift, i. e.
for all (v 0 , . . . , v n−1 ) ∈ F n . This is the case if and only if C is an ideal in the quotient ring identified with F n in the canonical way via In order to extend this situation to the convolutional setting, we have to replace the vector space F n by the free module F[z] n := { N ν=0 z ν v ν | N ∈ N 0 , v ν ∈ F n } and, consequently, the ring A by the polynomial ring A[z] := N ν=0 z ν a ν N ∈ N 0 , a ν ∈ A over A. Then we can extend the mapping p above coefficientwise to polynomials, thus p N ν=0 z ν v ν = N ν=0 z ν p(v ν ) where, of course, v ν ∈ F n and thus p(v ν ) ∈ A for all ν. At this point it is quite natural to declare a convolutional code C ⊆ F[z] n cyclic if it is invariant under the cyclic shift, i. e., if (4.1) holds true for all (v 0 , . . . , v n−1 ) ∈ F[z] n . Since, just like for block codes, the cyclic shift in F[z] n corresponds to multiplication by x in A[z], this amounts to the same as saying that C is called cyclic if p(C) is an ideal in A[z]. However, it has been shown in [16,Thm. 3.12] and [18,Thm. 6] that each convolutional code that is cyclic in this sense has overall constraint length zero, thus is a block code. An elementary proof can be found at [7,Prop. 2.7]. Due to this result Piret [16] introduced a different notion of cyclicity for convolutional codes which then was further generalized by Roos [18]. This concept is based on some automorphism of the F-algebra A. Thus, let Aut F (A) be the group of all F-automorphisms on A. It is clear that each automorphism σ ∈ Aut F (A) is uniquely determined by the single value σ(x) ∈ A, but not every choice for σ(x) determines an automorphism on A.
The main idea of Piret was to impose a new ring structure on A[z] and to declare a code cyclic if it is a left ideal with respect to that ring structure. The new structure is in general non-commutative and based on an (arbitrarily chosen) F-automorphism on A. In detail, this looks as follows.
A few comments are in order. First notice that, unless σ is the identity, the indeterminate z does not commute with its coefficients. Due to this very specific non-commutativity the ring A[z; σ] is also called a skew-polynomial ring. Since σ| F = id F , the classical polynomial ring F[z] is a commutative subring of A[z; σ], too. As a consequence, A[z; σ] is a left and right F[z]-module and it can easily be seen that the mapping p in (2) above is an isomorphism of left F[z]-modules. In the special case where σ = id A the ring A[z; σ] is the classical commutative polynomial ring and due to the results mentioned earlier this does not result in any convolutional codes other than block codes. In many cases where σ is not the identity there do indeed exist cyclic convolutional codes with positive overall constraint length. Characterizations along with several examples (actually all optimal with respect to their free distances) have been presented in [7,5,4]. Another class of such codes is given by some of the codes of Theorem 2.1. Indeed, we have the following. Proposition 4.2 Let n be a positive integer coprime with |F| and let α ∈ F be such that ord(α) = n. Furthermore, let δ ∈ N 0 and G be as in (2.1). Then the F-algebra homomorphism σ : A −→ A defined by σ(x) = αx is an F-automorphism on A and the submodule C = im G is σ-cyclic. In particular, if δ < n, then C is a cyclic MDS convolutional code.
Remember that only for specific values of δ these submodules are actually convolutional codes, i. e., the matrix G is right-invertible, see also Remark 2.2. Recall also from the last section that in the case ord(α) = n > δ the codes can be described by a certain Vandermonde parity check matrix. Therefore, in this case the codes have quite a rich structure.
Proof: First of all, since (αx) i , i = 0, . . . , n − 1 are linearly independent over F and (αx) n = 1, the mapping σ as defined above is indeed an automorphism on A. Consider now the submodule C = im G where G = δ ν=0 z ν 1 α ν α 2ν . . . α (n−1)ν . We have to prove that p(C) is a left ideal in A[z; σ]. Since p(C) is a left F[z]-module, it suffices to show that p(C) is closed with respect to left multiplication by x. Thus, consider the image of G under the mapping p, i. e., define (4.5) Now it suffices to show that p −1 (xg) ∈ im G, or, stated differently, that xg is a left F[z]multiple of g. But this can easily be seen since This result proves in particular that if ord(α) = n, then the codes in Theorem 2.1 are cyclic. In the sequel we want to show even more. Indeed, we will prove that the condition ord(α) = n is even necessary and sufficient for the codes of Theorem 2.1 to be cyclic with respect to some F-automorphism.
To this end we need some more details about the coefficient ring A. Due to the coprimeness of n and |F|, this ring is a direct product of fields. Indeed, let where π 1 , . . . , π r ∈ F[x] are irreducible, monic, and pairwise different. Then the Chinese Remainder Theorem tells us that ψ : A −→ K 1 × . . . × K r , a −→ a mod π 1 , . . . , a mod π r , (4.7) where K k = F[x]/ π k , is an isomorphism if × r i=1 K i is endowed with componentwise addition and multiplication. Notice that K k ∼ = K l if and only if deg x π k = deg x π l . The elements ε (k) := ψ −1 0, . . . , 0, 1, 0, . . . , 0 for k = 1, . . . , r (4.8) (where 0 and 1 have to be understood as the elements 0 mod π l and 1 mod π l in K l ) are particularly important since they form the uniquely determined set of primitive idempotents in A. The idempotents are pairwise orthogonal, thus ε (k) ε (l) = 0 for k = l. Observe that for any a ∈ A the products ε (l) a single out the various components of a. Precisely, ψ(ε (l) a) = (0, . . . , 0, a mod π l , 0, . . . , 0) for any l = 1, . . . , r. Therefore, ε (1) a + . . . + ε (r) a is a decomposition of a ∈ A just like the one in (4.7) and in the sequel we will use this representation rather than that from (4.7).
It is straightforward to see that a given automorphism σ ∈ Aut F (A) induces a permutation on the set of primitive idempotents. More precisely, σ(ε (k) ) = ε (l) for some l such that deg x π k = deg x π l . (4.9) The following example will be important for our purposes.
Proof: The if-part as well as the additional statement have been proven in Proposition 4.2. "Only-if-part": Let C = im G be σ-cyclic for some σ ∈ Aut F (A). Let x n − 1 = r i=1 π i be the prime factorization of x n − 1 such that π 1 = x − 1. Denoting the idempotents by ε (1) , . . . , ε (r) we have in particular ε (1) = 1 n x n −1 x−1 = 1 n n−1 i=0 x i . By assumption ord(α) ≥ n and we have to show that ord(α) = n, hence that r = n and, up to ordering, π i = x − α i−1 for i = 1, . . . , n. By assumption, p(C) is the left ideal generated by g as given in (4.5). Since rank C = 1, the generator matrix G is unique up to a nonzero constant in F. Thus, the generator of the left ideal is also unique up to a constant factor and, along with [7,Cor. 4.13 and Thm. 4.15(b)], this shows that the polynomial g is reduced in the sense of [7,Def. 4.9(b)]. Moreover, since the code is one-dimensional we obtain from [7, Thm. 7.13] that g = ε (k) g for some k = 1, . . . , r such that deg π k = 1. In particular we have g 0 = ε (k) g 0 for the constant coefficient g 0 of g. Since (4.5) yields g 0 = nε (1) and ε (k) ε (1) = 0 for k > 1, we conclude k = 1, thus g = ε (1) g. Therefore, where g ν is the coefficient of z ν in g. Hence, g ν = σ ν (ε (1) )g ν for all ν = 0, . . . , δ. Moreover, since δ > 0 we have σ(ε (1) ) = ε (1) for otherwise the code would have overall constraint length zero, see [4,Lemma 3.4]. Consider now the coefficient g 1 = n−1 i=0 (αx) i . The equation g 1 = σ(ε (1) )g 1 along with σ(ε (1) ) = ε (1) and the orthogonality of the idempotents implies ε (1) g 1 = 0. Substituting x = 1, we obtain n−1 i=0 α i = 0. But then n−1 i=0 α i (α−1) = α n − 1 = 0 which along with the assumption ord(α) ≥ n implies ord(α) = n. 2 We want to close the paper with yet another representation of the cyclic codes considered so far. In [7,Prop. 7.10] it has been shown that a polynomial g ∈ A[z; σ] with the property g = ε (k) g for some k = 1, . . . , r generates an ideal that is a convolutional code, i. e., a direct summand in the left F[z]-module A[z; σ], if and only if g = ε (k) u for some unit u ∈ A[z; σ]. More details about this can be found in [4]. From Example 4.3 we can easily derive how such a unit looks like in the case of the equivalent conditions of Theorem 4.4 if δ is not too big.
The representation on the right hand side of (a) justifies to call these codes one-dimensional Reed-Solomon convolutional codes.
In the paper [4] representations of cyclic codes via units like on the right hand side of (b) above have been studied in detail. Therein, it has been investigated as to which algebraic parameters (field size, dimension, overall constraint length, and Forney indices) can be realized by cyclic convolutional codes. In particular, a construction of certain compact cyclic convolutional codes (i. e., all Forney indices are the same) has been derived. However, no distance results have been obtained in that context. As has been shown in [6] the presentation as on the right hand side of (a) seems to be more suitable for a generalization to codes of higher dimension with good distance.

Open Problems
We have presented a class of one-dimensional convolutional codes with maximum possible distance. In the specific case where ord(α) = n these codes are cyclic and have a Vandermonde parity check matrix. Without using explicitly Vandermonde matrices, but highly the theory of cyclic convolutional codes, first attempts are currently under investigation of how to generalize the construction of cyclic convolutional codes with large distance to higher dimensions, see [6]. In general, we consider it most important to understand whether Vandermonde structure of a cyclic convolutional code can be exploited for distance computations and algebraic decoding algorithms. We think that the one-dimensional cyclic MDS codes with their rich structure as presented in this paper might be a good starting point in this regard.