ISSN 2148-838Xhttp://dx.doi.org/10.13069/jacodesmath.645029 J. Algebra Comb. Discrete Appl. 7(1) • 73–84 Received: 21 June 2019 Accepted: 14 October 2019 Journal of Algebra Combinatorics Discrete Structures and Applications Constructions of MDS convolutional codes using superregular matrices∗ Research Article Julia Lieb, Raquel Pinto Abstract: Maximum distance separable convolutional codes are the codes that present best performance in error correction among all convolutional codes with certain rate and degree. In this paper, we show that taking the constant matrix coefficients of a polynomial matrix as submatrices of a superregular matrix, we obtain a column reduced generator matrix of an MDS convolutional code with a certain rate and a certain degree. We then present two novel constructions that fulfill these conditions by considering two types of superregular matrices. 2010 MSC: 94B10 Keywords: Convolutional codes, MDS codes, Superregular matrices 1. Introduction The (free) distance of a code measures its capability of detecting and correcting errors introduced during information transmission through a noisy channel. Maximum distance separable (MDS) block codes of rate k/n are the block codes with distance equal to the Singleton bound n−k + 1. The class of MDS block codes is very well understood and there exist prominent constructions of MDS block codes like the Reed-Solomon codes [12]. The theory of convolutional codes is more involved than the theory of block codes and there are not many known constructions of MDS convolutional codes. These codes have maximum free distance in the class of convolutional codes of a certain rate k/n and a certain degree δ, i.e., are the ones with free distance equal to the Singleton bound (n−k) (⌊ δ k + 1 ⌋) + δ + 1 [13]. The first construction of MDS convolutional codes was obtained by Justesen in [9] for codes of rate 1/n and restricted degrees. In [16] Smarandache and Rosenthal presented constructions of convolutional codes of rate 1/n and arbitrary ∗ This work was supported by Fundação para a Ciência e a Tecnologia (FCT) within project UID/MAT/04106/2019 (CIDMA) and the German Research Foundation (DFG) within grant LI3103/1-1. Julia Lieb (Corresponding Author), Raquel Pinto; Department of Mathematics, University of Aveiro, Portugal (email: jlieb@ua.pt, raquel@ua.pt). 73 https://orcid.org/0000-0003-4211-1596 https://orcid.org/0000-0002-8168-4023 J. Lieb, R. Pinto / J. Algebra Comb. Discrete Appl. 7(1) (2020) 73–84 degree using linear systems representations. However these constructions require a larger field size than the constructions obtained in [9]. Gluesing-Luerssen and Langfeld introduced in [6] a new construction of convolutional codes of rate 1/n that requires the same field sizes as the ones obtained in [9] but also with a restriction on the degree of the code. Finally, Smarandache, Gluesing-Luerssen and Rosenthal [15] constructed MDS convolutional codes for arbitrary parameters. We will define new constructions of convolutional codes of any degree and sufficiently low rate using superregular matrices with a specific property. A similar procedure was done for constructing two- dimensional MDS convolutional codes [3, 4] but it is not possible to derive 1D convolutional codes from the constructions of these papers. Moreover, the proof which we present in this paper that the obtained codes are MDS uses different tecniques from the corresponding ones in [3, 4]. We also provide explicit constructions of these codes using Cauchy circulant matrices [14] and superregular matrices as defined in [2]. The paper is organized as follows: In the next section we start by introducing some preliminaries on superregular matrices. We give the definition of these matrices and two different types of superregular matrices. Then we give some definitions and results on convolutional codes. In Section 3, we present a procedure to construct MDS convolutional codes using superegular matrices. We show that generator matrices whose coefficients of its entries fulfill certain conditions are generator matrices of an MDS convolutional code. In Section 4, we give two different constructions of MDS convolutional codes of an arbitrary degree and rate smaller than some upper bound. Finally, in Section 5, we compare the necessary field size and the restrictions on the parameters of our obtained constructions with those of already known constructions. 2. Preliminaries 2.1. Superregular matrices We denote, as usual, the finite field of order q as Fq. Definition 2.1 ([14]). A matrix A ∈ Fr×`q is said to be superregular if every minor of A is different from zero. The following lemma is easy to see and we will use it several times to derive our conditions for MDS convolutional codes. Lemma 2.2. (i) Let A ∈ Fr×`q be superregular. Then, each vector which is a linear combination of s columns of A has at most s− 1 zeros. (ii) Let A ∈ Fr×`q with r ≥ ` be such that all its fullsize minors are nonzero. Then, each vector which is a linear combination of ` columns of A has at most `− 1 zeros. There are many examples of superregular matrices. We will present two types of superregular matrices that we will use later for the constructions that we introduce in this paper. The first one will be the Cauchy circulant matrices. Theorem 2.3. [14] Let q be an odd number, let α be an element of order q−1 2 in Fq and let b be a nonsquare element in Fq. Then the (q−12 ) × ( q−1 2 ) matrix C = [ cij ] where cij = 1 1 − bαj−i , for 0 ≤ i,j ≤ q − 3 2 is superregular. The matrix considered in the above theorem is a Cauchy circulant matrix. Another type of super- regular matrix is given in the next theorem. 74 J. Lieb, R. Pinto / J. Algebra Comb. Discrete Appl. 7(1) (2020) 73–84 Theorem 2.4. [2] Let p be a prime number and α a primitive element of FpN and B = [νi`] a matrix over FpN with the following properties 1. νi` = αβi` for a positive integer βi`; 2. if ` < `′, then 2βi` ≤ βi`′; 3. if i < i′, then 2βi` ≤ βi′ `. Suppose N is greater than any exponent of α appearing as a nontrivial term of any minor of B. Then B is superregular. 2.2. Convolutional codes Let Fq[z] denote the ring of the polynomials with coefficients in Fq. A convolutional code of rate k/n is an Fq[z]-submodule of Fq[z]n of rank k. A generator matrix of a convolutional code C of rate k/n is any n×k matrix whose columns constitute a basis of C, i.e., it is a full column rank matrix G(z) such that C = ImFq[z]G(z) = {G(z)u(z) : u(z) ∈ Fq[z]k}. If G(z) ∈ Fq[z]n×k is a generator matrix of a convolutional code C, then all generator matrices of C are of the form G(z)U(z) for some unimodular matrix U(z) ∈ Fq[z]k×k, i.e. for a matrix that is invertible in the ring of polynomial matrices. Two generator matrices of the same code are said to be equivalent generator matrices. Since two equivalent generator matrices differ by right multiplication of a unimodular matrix, they have the same full size minors, up to multiplication by a nonzero constant. The complexity or degree of a convolutional code is defined as the maximum degree of the full size minors of a generator matrix of the code. Define the j-th column degree νj of a polynomial matrix G(z) ∈ Fq[z]n×k to be the maximum degree of the entries of the j-th column of G(z). Obviously, the sum of the column degrees of G(z) is greater or equal than the maximum degree of its full size minors. If the sum of the column degrees of G(z) equals the maximum degree of its full size minors, G(z) is said to be column reduced. A convolutional code always admits column reduced generator matrices and two column reduced generator matrices have the same column degrees up to a column permutation [5, 10]. Therefore, column reduced generator matrices are the ones that have minimal sum of the column degrees and thus the sum of its column degrees is equal to the degree of the code. Definition 2.5. For G(z) ∈ Fq[z]n×k, let [gij]hc denote the coeffcient of zνj in gij(z). Then, the highest column degree coeffcient matrix [G]hc ∈ Fn×kq is defined as the matrix consisting of the entries [gij]hc. A matrix G(z) ∈ Fq[z]n×k is column reduced if and only if [G]hc ∈ Fn×kq has full rank. The weight of a vector c ∈ Fnq , wt(c), is the number of its nonzero entries and the weight of a polynomial vector v(z) = ∑ i∈N0 viz i ∈ Fq[z]n is given by wt(v(z)) = ∑ i∈N0 wt(vi). The free distance of a convolutional code C is the minimum weight of the nonzero codewords of the code, i.e., dfree(C) = {wt(v(z)) : v(z) ∈C\{0}}. 75 J. Lieb, R. Pinto / J. Algebra Comb. Discrete Appl. 7(1) (2020) 73–84 In [13] Smarandache and Rosenthal obtained an upper bound for the free distance of a convolutional code C of rate k/n and degree δ given by dfree(C) ≤ (n−k) (⌊ δ k ⌋ + 1 ) + δ + 1. This bound is called the generalized Singleton bound. A convolutional code of rate k/n and degree δ with free distance equal to the generalized Singleton bound is called Maximum Distance Separable (MDS) convolutional code. If C is such a code and G(z) ∈ Fq[z]k×n is a column reduced generator matrix of C, its column degrees are equal to ⌊ δ k ⌋ + 1 with multiplicity t := δ −k ⌊ δ k ⌋ and ⌊ δ k ⌋ with multiplicity k − t; see [13]. 3. Conditions to obtain MDS convolutional codes Let C be a convolutional code of rate k/n and degree δ. In this section, we will derive conditions on a column reduced generator matrix G(z) of C that ensure that the code is an MDS convolutional code. To this end, we assume that G(z) has non-increasing column degrees with values ⌊ δ k ⌋ + 1 and ⌊ δ k ⌋ . We write G(z) = ∑µ i=0 Giz i with Gµ 6= 0, i.e. µ = deg G, and ν := ⌊ δ k ⌋ + 1, i.e. ν = µ if k - δ and ν = µ + 1 if k | δ. Furthermore, we write G(z) = [g1(z) . . .gk(z)] with gr(z) =   ∑ 0≤i≤ν gi,rz i, for r = 1, 2, . . . , t,∑ 0≤i≤ν−1 gi,rz i, for r = t + 1, t + 2, . . . ,k, i.e. Gi = [gi,1 · · ·gi,k] for i = 1, . . . ,ν − 1 and Gν = [gν,1 · · ·gν,t 0 · · ·0], where t = δ −k ⌊ δ k ⌋ . Set G = [ g0,1 · · ·gν,1 · · · g0,t · · ·gν,t g0,t+1 · · ·gν−1,t+1 · · · g0,k · · ·gν−1,k ] ∈ Fn×(kν+t)q . (1) Write u(z) = ∑ i∈N0 uiz i. If l := deg u ≤ µ, we have v(z) = G(z)u(z) = G0u0 + · · · [Gl · · ·G0]  u0... ul  zl + · · · + [Gµ · · ·Gµ−l]  u0... ul  zµ + · · · + Gµulzµ+l (2) For l ≥ µ, one obtains v(z) = G(z)u(z) = G0u0 + · · · + [Gµ · · ·G0]  u0... uµ  zµ + · · · + [Gµ · · ·G0]  ul−µ... ul  zl + · · · + Gµulzµ+l (3) As wt(G(z)u(z)) = wt(G(z)u(z)zr) for r ∈ N, throughout this paper, we assume, without loss of generality that u0 6= 0. Theorem 3.1. If the matrix G defined in (1) is superregular, G(z) is the generator matrix of an (n,k,δ) convolutional code. 76 J. Lieb, R. Pinto / J. Algebra Comb. Discrete Appl. 7(1) (2020) 73–84 Proof. Since the highest column degree coefficient matrix of G(z) is equal to[ gν,1 gν,2 · · · gν,t gν−1,t+1 · · · gν−1,k ] , it is a submatrix of the superregular matrix G and hence full rank. Consequently, G(z) is column reduced. Therefore, the degree of the code generated by G(z) is equal to the sum of the column degrees of G(z), which is νt + (ν − 1)(k − t) = δ. The generated code is an MDS convolutional code if and only if for each u(z) ∈ Fq[z]k \ {0} and v(z) = G(z)u(z), one has wt(v(z)) ≥ (n−k) (⌊ δ k ⌋ + 1 ) + δ + 1 = nν − (k − t) + 1. (4) Next, we will show that under certain conditions equation (4) is fulfilled by considering different cases for the value of δ. In any case, one of the conditions will always be the superregularity of G. However, this condition is not necessary to obtain an MDS convolutional code as the following example shows. Example 3.2. Let C be the convolutional code of rate 2/3 and degree 1 with generator matrix G(z) =   1 11 2 0 1  +   1 01 0 2 0  z. The free distance of this code is dfree(C) = 3 and hence it is an MDS convolutional code but G =  1 1 11 2 1 0 1 2   is not superregular. 3.1. Conditions for the case δ < k In this case, we have to prove that wt(v(z)) ≥ n−k + δ + 1. Theorem 3.3. Assume that δ < k and let G be superregular. If n ≥ δ + k−1, then G(z) is the generator matrix of an (n,k,δ) MDS convolutional code. Proof. As δ < k, we have ν = µ = 1 and t = δ. Case 1: l = 0 One has v(z) = G0u0 + G1u0z, where G0 and the δ nonzero columns of G1 form superregular matrices. If the first δ components of u0 are zero, i.e. G1u0 = 0, we have wt(v(z)) ≥ n−(k−δ) + 1, since G0u0 is a nonzero linear combination of k−δ columns of G0. If one of the first δ components of u0 is nonzero, one obtains wt(v(z)) = wt(G0u0) + wt(G1u0) ≥ n−k + 1 + n−δ + 1 ≥ n−k +δ + 1 as n ≥ δ +k−1 ≥ 2δ−1. Case 2: l ≥ 1 Here, one has v(z) = G0u0 +[G1 G0] ( u0 u1 ) z+· · ·+[G1 G0] ( ul−1 ul ) zl+G1ulz l+1. If the first δ components of ul are zero, one has wt(v(z)) ≥ wt(G0u0) + wt ( [G1 G0] ( ul−1 ul )) ≥ n − k + 1 + n − (k + δ − δ) + 1 ≥ n − k + δ + 1, since [G1 G0] ( ul−1 ul ) is a nonzero linear combination of δ columns of G1 and k − δ columns of G0 and n ≥ δ + k − 1. If one of the first δ components of ul is nonzero, one obtains wt(v(z)) ≥ wt(G0u0) + wt(G1ul) ≥ n−k + 1 + n−δ + 1 ≥ n−k + δ + 1 as n ≥ δ + k − 1 ≥ 2δ − 1. 77 J. Lieb, R. Pinto / J. Algebra Comb. Discrete Appl. 7(1) (2020) 73–84 3.2. Conditions for the case δ ≥ k For this subsection, we need the additional definitions G1 =  G0... Gν   ∈ F(ν+1)n×kq , G2 =   G0... Gν−1   ∈ Fνn×kq , Ḡ =  G0... Gµ   ∈ F(µ+1)n×kq . We have Ḡ = G1 for k - δ and Ḡ = G2 for k | δ and G(z) = [In Inz · · ·Inzµ]Ḡ. (5) Theorem 3.4. Assume that δ ≥ k and let G defined in (1) be superregular. Moreover, assume that all fullsize minors of Ḡ are nonzero. If n ≥ 2δ +k−ν, then G(z) is the generator matrix of an (n,k,δ) MDS convolutional code. Proof. We distinguish several cases. Case 1: l = 0 Case 1.1: k | δ In this case, the generalized Singleton bound is equal to nν − k + 1. If we define v = G2u, we obtain that v is a nonzero linear combination of the columns of a matrix with nonzero fullsize minors and hence wt(v) ≥ nν −k + 1. Case 1.2: k - δ Let us write u0 = [ u (1) 0 u (2) 0 ] , with u(1)0 ∈ F t q and u (2) 0 ∈ F k−t q , and set v = G1u. Then v = [ v(1) v(2) ] , with v(1) = G2u ∈ Fνnq and v(2) = Gνu(1) ∈ Fnq . Hence, v(1) is a nontrivial linear combination of columns of an nν ×k matrix with nonzero fullsize minors and v(2) is a linear combination of columns of an n× t matrix with nonzero fullsize minors. We distinguish two further subcases. Case 1.2.1: u(1) = 0. In this case, one has v = [ v(1) 0 ] where v1 is a nontrivial linear combination of the columns of an nν × (k− t) matrix with nonzero fullsize minors and k− t < nν. Applying Lemma 2.2, we obtain wt(v) ≥ nν − (k − t) + 1. Case 1.2.2: u(1) 6= 0. In this case, v(1) and v(2) are nontrivial linear combinations of the columns of an nν ×k and an n× t matrix with nonzero fullsize minors, respectively. Moreover, since nν > k and n > t, it follows from Lemma 2.2 that wt(v(1)) ≥ nν −k + 1 and wt(v(2)) ≥ n− t + 1 and thus we get wt(v) = wt(v(1)) + wt(v(2)) ≥ nν + n−k − t + 2 = nν − (k − t) + 1 + n− 2t + 1 ≥ nν − (k − t) + 1 where the last inequality follows from the fact that n ≥ 2δ+k−ν = δ+k−1 +δ−bδ k c≥ δ+k−1 ≥ 2t−1. Using equation (5), wt(G(z)u(z)) = wt(v) and the result follows. Case 2: 1 ≤ l < µ Note that for this case, one has n ≥ 2δ + k −ν ≥ k + δ − 1 = ( δ k − 1 k + 1 ) k ≥ µk ≥ (l + 1)k. (6) Case 2.1: k | δ 78 J. Lieb, R. Pinto / J. Algebra Comb. Discrete Appl. 7(1) (2020) 73–84 Using equations (2) and (6), the superregularity of G and that u0 and ul are nonzero, we obtain wt(v(z)) ≥ 2 l∑ i=1 (n− ik + 1) + ( δ k − l + 1)(n− (l + 1)k + 1) = = 2nl + 2l−k(l + 1)l + ( δ k + 1)(n−k) + ( δ k + 1)(−lk + 1) − ln + l(l + 1)k − l = ( δ k + 1)(n−k) + δ + 1 + nl + l + ( δ k + 1)(−lk + 1) − δ − 1. Consequently, in order to get wt(v(z)) ≥ ( δ k + 1)(n−k) + δ + 1, one needs n ≥ 1 l ( δ + 1 − l + lδ + lk − δ k − 1 ) = δ + k − 1 + 1 l ( δ − δ k ) . The result follows from δ + k − 1 + 1 l ( δ − δ k ) ≤ 2δ + k −ν. Case 2.2: k - δ Additionally to the previous subcase, here we have to regard that Gµul might be zero and that [Gµ · · ·Gi] for i = µ− l, . . .µ− 1 has k − t = kµ−δ zero columns. Therefore, we get wt(v(z)) ≥ 2 l∑ i=1 (n− ik + 1) − (n−k + 1) + (µ− l + 1)(n− (l + 1)k + 1) + (kµ−δ)l = µ(n−k) + δ + 1 + nl + l− lk + µ(−lk + 1) + (kµ−δ)l− δ − 1 = µ(n−k) + δ + 1 + nl + l− lk + µ− δl− δ − 1 Hence, one needs n ≥ k + δ− 1 + 1 l (δ + 1 −µ). This is true as k + δ− 1 + 1 l (δ + 1 −µ) ≤ k + 2δ−µ and µ = ν for k - δ. Case 3: l ≥ µ For this case, we consider equation (3). As it could happen that 2δ + k−ν is smaller than (µ + 1)k, the weight of vi might be zero for i = µ,. . . , l. However, one has µk ≤ ( δ k − 1 k + 1 ) k = δ +k−1 ≤ 2δ +k−ν. Case 3.1: k | δ Using equation (3) and the superregularity of G, we obtain wt(v(z)) ≥ 2 µ∑ i=1 (n− ik + 1) = 2nµ + 2µ− (µ + 1)µk = (n−k)(µ + 1) + n(µ− 1) + 2µ− (µ + 1)(µ− 1)k + δ + 1 − δ − 1. Hence, for µ ≥ 2, one needs n ≥ k(µ + 1) − 2 + δ−1 µ−1 = k + δ − 2 + δ−1 µ−1. This is true for µ ≥ 3 since k+δ−2+ δ−1 µ−1 ≤ k+ 3 2 δ−5 2 ≤ k+2δ−ν for k ≥ 2 and k+δ−2+ δ−1 µ−1 = k+δ−1 for k = 1. It is also true for µ = 2 since k + δ − 2 + δ − 1 = k + 2δ − 3 ≤ k + 2δ −ν. It remains to consider the case µ = 1. If we consider above estimation for the weight for µ = 1, we get the condition δ ≤ 1. Hence, for the following consideration, we could assume k = δ ≥ 2. For these parameters one has 2δ + k − ν ≥ k + δ and thus, we could exploit the superregularity of [G1 G0]. Doing this, we get wt(v(z)) ≥ 2(n−k + 1) + (n− 2k + 1) = 2(n−k) + δ + 1 −δ + 2 + n− 2k ≥ 2(n−k) + δ + 1 because n ≥ 2δ + k −ν = δ + 2k − 2. Case 3.2: k - δ If one of the first t components of ul is nonzero, we get wt(v(z)) ≥ 2 µ∑ i=1 (n− ik + 1) = (n−k)µ + nµ + 2µ−µ2k + δ + 1 −δ − 1. 79 J. Lieb, R. Pinto / J. Algebra Comb. Discrete Appl. 7(1) (2020) 73–84 Consequently, one needs n ≥ kµ− 2 + δ+1 µ , which is true as kµ− 2 + δ+1 µ ≤ k + δ − 3 + δ+1 2 ≤ k + 3 2 δ − 5 2 ≤ 2δ + k −ν because k - δ implies k ≥ 2. If the first t components of ul are zero, what changes in the previous estimation for the weight of v(z) is that we have to subtract n−k + 1 as Gµul = 0 but in turn we could add k − t = kµ− δ to each of the weights of vi for i = l + 1, . . . , l + µ− 1. Finally, we obtain wt(v(z)) ≥ (n−k)µ + n(µ− 1) + 2µ− 1 − (µ2 − 1)k + δ + 1 − δ − 1 + (kµ−δ)(µ− 1). Therefore, we need n ≥ (µ+ 1)k−2 +δ−kµ+ δ µ+1 = k +δ−2 + δ µ+1 , which is true since k +δ−2 + δ µ+1 ≤ k + 4 3 δ − 2 ≤ 2δ + k −ν because k - δ implies k ≥ 2. 4. Constructions of MDS convolutional codes In this section, we will use the results of the preceding section to obtain two different constructions for MDS convolutional codes. 4.1. Constructions for δ < k Theorem 4.1 (Construction 1). Assume δ < k, t and ν as defined before and n ≥ k + δ− 1. Moreover, let q be an odd number such that q ≥ 2 max{k + δ,n} + 1 and let C = [ cij ] be the Cauchy circulant matrix defined in Theorem 2.3 over Fq. Set G =   c0,0 · · · c0,k+δ−1... ... cn−1,0 · · · cn−1,k+δ−1   (7) Then, the matrix G is superregular. Let us write G = [ g0,1 · · ·gν,1 · · · g0,t · · ·gν,t g0,t+1 · · ·gν−1,t+1 · · · g0,k · · ·gν−1,k ] . Then, G(z) = ∑µ i=0 Giz i with Gi = [gi,1 · · ·gi,k] is the generator matrix of an (n,k,δ) MDS convolutional code. Proof. The proof of Theorem 4.1 follows immediately from Theorem 2.3. Example 4.2. In this example we use Theorem 4.1 to construct a (4, 3, 2) MDS convolutional code over F11. To this end, we choose a = 3 and b = 2 in Theorem 2.3 and get the superregular matrix C =   10 2 9 6 3 3 10 2 9 6 6 3 10 2 9 9 6 3 10 2 2 9 6 3 10  . Thus, considering G = [g0,1 g1,1 g0,2 g1,2 g0,3] =   10 2 9 6 3 3 10 2 9 6 6 3 10 2 9 9 6 3 10 2   it follows from Theorem 4.1 that G(z) =   10 9 3 3 2 6 6 10 9 9 3 2   +   2 6 0 10 9 0 3 2 0 6 10 0  z 80 J. Lieb, R. Pinto / J. Algebra Comb. Discrete Appl. 7(1) (2020) 73–84 is a generator matrix of a (4, 3, 2) MDS convolutional code. Theorem 4.3 (Construction 2). Assume that δ < k, n ≥ k + δ − 1 and N ≥ 2n+k+δ−1. Let α be a primitive element of a finite field FpN . Set G =   α · · · α 2k+δ−1 ... ... α2 n−1 · · · α2 n+k+δ−2   . Then, the matrix G is superregular. Let us write G = [ g0,1 · · ·gν,1 · · · g0,t · · ·gν,t g0,t+1 · · ·gν−1,t+1 · · · g0,k · · ·gν−1,k ] . Then, G(z) = ∑µ i=0 Giz i with Gi = [gi,1 · · ·gi,k] is the generator matrix of an (n,k,δ) MDS convolutional code over FpN . Proof. According to Theorem 2.4, G is superregular over FpN if N is greater than∑k+δ−1 i=0 2 k+δ+n−2−2i = 2n−k−δ ∑k+δ−1 i=0 2 2i < 2n+δ+k−1. For the last inequality, we used the geometric sum. Example 4.4. In this example we construct a (4, 3, 2) MDS convolutional code but now over F 22 8 . To this end, we choose a primitive element α of F28 and set G = [g0,1 g1,1 g0,2 g1,2 g0,3] =   α α2 α4 α8 α16 α2 α4 α8 α16 α32 α4 α8 α16 α32 α64 α8 α16 α32 α64 α128   and G(z) =   α α4 α16 α2 α8 α32 α4 α16 α64 α8 α32 α128   +   α2 α8 0 α4 α16 0 α8 α32 0 α16 α64 0  z, which, according to Theorem 4.3, is a generator matrix of a (4, 3, 2) MDS convolutional code. 4.2. Constructions for δ ≥ k Theorem 4.5. [Construction 1] Assume δ ≥ k, t, ν as defined before and n ≥ k + 2δ−ν. Moreover, let q be an odd number such that q ≥ 2n(ν + 1) + 1 and let C = [ cij ] be the Cauchy circulant matrix defined in Theorem 2.3 over Fq. Set gj,r =   cjn,r−1 cjn+1,r−1 ... c(j+1)n−1,r−1   (8) for (j,r) ∈ ({0, 1, . . . ,ν − 1}×{1, 2, . . . ,k}) ∪ ({ν}×{1, 2, . . . , t}) if t 6= 0 and for (j,r) ∈ ({0, 1, . . . ,ν − 1}×{1, 2, . . . ,k}) if t = 0. Then, the matrix G(z) = ∑µ i=0 Giz i with Gi = [gi,1 · · ·gi,k] is the generator matrix of an (n,k,δ) MDS convolutional code. Proof. By Theorem 2.3, C is a superregular matrix. Then the matrix Ḡ is superregular because it is a submatrix of C. Since α q−1 2 = 1, we obtain cu,v = 1 1 − bαv−u = 1 1 − bα q−1 2 −u+v = c0,q−1 2 −u+v, 81 J. Lieb, R. Pinto / J. Algebra Comb. Discrete Appl. 7(1) (2020) 73–84 for 0 ≤ u,v ≤ q−3 2 , and, hence, gj,r =   c0,q−1 2 −jn+r−1 c1,q−1 2 −jn+r−1 ... cn−1,q−1 2 −jn+r−1   . Consequently, after an appropriate rearrangement of the columns of G, we obtain a submatrix of the Cauchy matrix C. Therefore, the matrix G is also superregular. Theorem 4.6. [Construction 2] Assume that δ ≥ k and n ≥ k + 2δ −ν and N ≥ 2(b δ k c+1)n+k−1. Let α be a primitive element of a finite field FpN . Set gj,r =   α 2r−1+nj ... α2 r−1+n(j+1)   for r = 1, . . . ,k and j = 0, . . . ,bδkc and gbδ k c+1,r =   α 2nr−1 ... α2 n(r+1)−2   for r = 1, . . . , t. Then, G(z) = ∑µi=0 Gizi with Gi = [gi,1 · · ·gi,k] is the generator matrix of an (n,k,δ) MDS convolutional code over FpN . Proof. With the definitions of the above theorem, G consists of k + δ columns of  α · · · α2 k−1+nbδ k c ... ... α2 n−1 · · · α2 k+n−2+nbδ k c   . Hence, according to Theorem 2.4, it is superregular over FpN if N is greater than∑k+δ−1 i=0 2 k+n−2+nbδ k c−2i = 2n+nb δ k c−k−2δ ∑k+δ−1 i=0 2 2i < 2n+nb δ k c+k−1. For the last inequality, we used the geometric sum. Moreover, Ḡ is equal to  α · · · α2 k−1 ... ... α2 n−1+nbδ k c · · · α2 k+n−2+nbδ k c   , which, according to Theorem 2.4, is superregular over FpN again if N is greater than∑k+δ−1 i=0 2 k+n−2+nbδ k c−2i < 2n+nb δ k c+k−1. Example 4.7. Using Theorem 4.5 it is possible to construct a (4, 2, 2) MDS convolutional code over F25 and with Theorem 4.6 a (4, 2, 2) MDS convolutional code over F 22 9 . 5. Comparison of constructions for MDS convolutional codes In this section, we want to compare the new constructions for MDS convolutional codes in this paper with the already known constructions. The comparison should be in terms of conditions on the parameters n,k and δ and in terms of the necessary field size. Throughout this section, we refer to the new constructions of the preceding section as Construction 1 and Construction 2. The constructions in [9], [16] and [6], which we already mentioned in the introduction, work only for k = 1 but in this case the required field sizes are smaller than the field sizes required for Construction 1 and Construction 2. 82 J. Lieb, R. Pinto / J. Algebra Comb. Discrete Appl. 7(1) (2020) 73–84 For nearly all parameters with k > 1, the construction of [15] leads to the smallest field size of all known constructions. But this construction has the drawback that it only works for |Fq| ≡ 1 mod n. Moreover, Construction 1 obtained in this paper could improve the necessary field size of [15] in some particular cases, e.g. it leads to smaller field sizes for (17, 2, 1) and (17, 2, 4) convolutional codes. However, also this construction has restrictions, i.e. it works only for odd field sizes and if n is larger than a particular lower bound. Maximum distance profile (MDP) convolutional codes are convolutional codes whose so-called column distances increase as rapidly as possible for as long as possible; see [8] or [7] for more explanation. As each (n,k,δ) MDP convolutional code with (n−k) | δ is an MDS convolutional code [7], for comparison, one also has to consider constructions for MDP convolutional codes if (n−k) | δ. In [1] and [11, Theorem 3.2], one could find such constructions that have no other requirements on the parameters than (n−k) | δ. There, the required field sizes are larger than the field size from [15] but again this construction has the drawback that it only works for |Fq| ≡ 1 mod n. Theorem 3.2 of [11] provides a construction for MDP convolutional codes where the required field size is smaller than the field size in [1]. However, it only works for very large characteristic of the field, while the construction in [1] and also Construction 2 work for arbitrary characteristic. If n is sufficiently large, such that the conditions for Construction 2 are fulfilled, it depends on the parameters if it is better than the construction in [1] or not. For example, for an (5, 2, 2) code the construction from [1] is better, and for an (5, 1, 5) code, Construction 2 is better. References [1] P. J. Almeida, D. Napp, R. Pinto, A new class of superregular matrices and MDP convolutional codes, Linear Algebra Appl. 439(7) (2013) 2145–2157. [2] P. J. Almeida, D. Napp, R. Pinto, Superregular matrices and applications to convolutional codes, Linear Algebra Appl. 499 (2016) 1–25. [3] J. Climent, D. Napp, C. Perea, R. Pinto, A construction of MDS 2D convolutional codes of rate 1/n based on superregular matrices, Linear Algebra Appl. 437(3) (2012) 766–780. [4] J. Climent, D. Napp, C. Perea, R. Pinto, Maximum distance seperable 2D convolutional codes, IEEE Trans. Inform. Theory 62(2) (2016) 669–680. [5] G. Forney, Convolutional codes I: Algebraic structure, IEEE Transactions on Information Theory, 16(6) (1970) 720–738. Correction, Ibid., IT-17, (1971) 360. [6] H. Gluesing–Luerssen, B. Langfeld, A class of one–dimensional MDS convolutional codes, J. Algebra Appl. 5(4) (2006) 505–520. [7] H. Gluesing–Luerssen, J. Rosenthal, R. Smarandache, Strongly–MDS convolutional codes, IEEE Trans. Inform. Theory 52(2) (2006) 584–598. [8] R. Hutchinson, J. Rosenthal, R. Smarandache, Convolutional codes with maximum distance profile, Systems & Control Letters 54 (2005) 53–63. [9] J. Justesen, An algebraic construction of rate 1/ν convolutional codes, IEEE Trans. Inform. Theory 21(5) (1975) 577–580. [10] T. Kailath, Linear Systems, Englewood Cliffs, N.J.: Prentice Hall, 1980. [11] J. Lieb, Complete MDP convolutional codes, J. Algebra Appl. 18(6) (2019) 1950105 (13 pages). [12] F. J. MacWilliams, N. J. A. Sloane, The Theory of Error–Correcting Codes, 6th ed. Amsterdam, The Netherlands: North–Holland, 1988. [13] J. Rosenthal, R. Smarandache, Maximum distance separable convolutional codes, Appl. Algebra Engrg. Comm. Comput. 10(1) (1999) 15–32. [14] R. Roth, A. Lempel, On MDS codes via Cauchy matrices, IEEE Trans. Inform. Theory 35(6) (1989) 1314–1319. 83 https://doi.org/10.1016/j.laa.2013.06.013 https://doi.org/10.1016/j.laa.2013.06.013 https://doi.org/10.1016/j.laa.2016.02.034 https://doi.org/10.1016/j.laa.2016.02.034 https://doi.org/10.1016/j.laa.2012.02.032 https://doi.org/10.1016/j.laa.2012.02.032 https://doi.org/10.1109/TIT.2015.2509075 https://doi.org/10.1109/TIT.2015.2509075 https://doi.org/10.1109/TIT.1970.1054541 https://doi.org/10.1109/TIT.1970.1054541 https://doi.org/10.1142/S0219498806001855 https://doi.org/10.1142/S0219498806001855 https://doi.org/10.1109/TIT.2005.862100 https://doi.org/10.1109/TIT.2005.862100 https://doi.org/10.1016/j.sysconle.2004.06.005 https://doi.org/10.1016/j.sysconle.2004.06.005 https://doi.org/10.1109/TIT.1975.1055436 https://doi.org/10.1109/TIT.1975.1055436 https://doi.org/10.1142/S0219498819501056 https://doi.org/10.1007/s002000050120 https://doi.org/10.1007/s002000050120 https://doi.org/10.1109/18.45291 https://doi.org/10.1109/18.45291 J. Lieb, R. Pinto / J. Algebra Comb. Discrete Appl. 7(1) (2020) 73–84 [15] R. Smarandache, H. Gluesing–Luerssen, J. Rosenthal, Constructions for MDS–convolutional codes, IEEE Trans. Inform. Theory 47(5) (2001) 2045–2049. [16] R. Smarandache, J. Rosenthal, A state space approach for constructing MDS rate 1/n convolutional codes, Proceedings of the 1998 IEEE Information Theory Workshop on Information Theory, 116–117. 84 https://doi.org/10.1109/18.930938 https://doi.org/10.1109/18.930938 https://doi.org/10.1109/ITW.1998.706461 https://doi.org/10.1109/ITW.1998.706461 Introduction Preliminaries Conditions to obtain MDS convolutional codes Constructions of MDS convolutional codes Comparison of constructions for MDS convolutional codes References