Superregular matrices and applications to convolutional codes P. J. Almeidaa, D. Nappa, R.Pinto∗,a 6 aDepartment of Mathematics, University of Aveiro, Campus Universita´rio de Santiago, 3810–193 Aveiro, 1 Portugal. 0 2 n a J Abstract 2 The main results of this paper are twofold: the first one is a matrix theoretical result. We say 1 that a matriz is superregular if all of its minors that are not trivially zero are nonzero. Given a ] a×b, a ≥ b, superregular matrix over a field, we show that if all of its rows are nonzero then any T linear combination of its columns, with nonzero coefficients, has at least a−b+1 nonzero entries. I Secondly, we make use of this result to construct convolutional codes that attain the maximum . s possible distance for some fixed parameters of the code, namely, the rate and the Forney indices. c [ These results answer some open questions on distances and constructions of convolutional codes posted in the literature [6, 9]. 1 v Key words: convolutional code, Forney indices, optimal code, superregular matrix 0 2000MSC: 94B10, 15B33 6 9 2 0 1. Introduction . 1 0 Several notions of superregular matrices (or totally positive) have appeared in different areas of 6 mathematics andengineeringhavingin commonthe specificationofsome propertiesregardingtheir 1 minors [2, 3,5,11, 14]. Inthe contextof coding theory these matrices have entriesin a finite fieldF : v and are importantbecause they can be used to generate linear codes with gooddistance properties. i A class of these matrices, which we will call full superregular, were first introduced in the context X of block codes. A full superregular matrix is a matrix with all of its minors different from zero and r a thereforeallofitsentriesnonzero. Itiseasytoseethatamatrixisfullsuperregularifandonlyifany F-linear combination of N columns (or rows) has at most N −1 zero entries. For instance, Cauchy and nonsingular Vandermonde matrices are full superregular. It is well-known that a systematic generator matrix G = [I | B]⊤ generates a maximum distance separable (MDS) block code if and only if B is full superregular,[13]. Convolutional codes are more involved than block codes and, for this reason, a more general class of superregular matrices had to be introduced. A lower triangular matrix B was defined to be superregular if all of its minors, with the property that all the entries in their diagonals are coming from the lower triangular part of B, are nonsingular, see [6, Definition 3.3]. In this ∗Correspondingauthor 1This work was supported by Portuguese funds through the CIDMA - Center for Research and Development in Mathematics and Applications, and the Portuguese Foundation for Science and Technology (FCT-Fundaçaõ para a CiênciaeaTecnologia), withinprojectPEst-UID/MAT/04106/2013. Preprint submitted to Elsevier 13 de Janeiro de 2016 paper, we call such matrices LT-superregular. Note that due to such a lower triangular configuration the remaining minors are necessarily zero. Roughly speaking, superregularity asks for all minors that are possibly nonzero, to be nonzero. In [6] it was shown that LT-superregular matrices can be used to construct convolutional codes of rate k/n and degree δ that are strongly MDS provided that (n−k) | δ. This is again due to the fact that the combination of columns of these LT-superregularmatricesensuresthelargestnumberofpossiblenonzeroentriesforanyF-linearcom- bination (for this particular lower triangular structure). In other words, it can be deduced from [6] that a lower triangular matrix B = [b b ...b ]∈ Fn×n, b the columns of B, is LT-superregular 0 1 k−1 i if and only if for any F-linear combination of columns b ,b ,...,b of B, with i < i , then i1 i2 iN j j+1 wt(b)≥wt(b )−N +1=(n−i )−N +1. i1 1 It is important to note that in this case due to this triangular configuration it is hard to come up with an algebraic construction of LT-superregular matrices. There exist however two general constructions of these matrices [1, 6, 7] although they need large field sizes. Unfortunately, LT- superregular matrices allow to construct convolutional codes with optimal distance properties only for certain given parameters of the code. This is because the constant matrix associated to a convolutional code have, in general, blocks of zeros in its lower triangular part. Hence, in order to construct convolutionalcodes with good distance properties for any set of given parameters a more general notion of superregular matrices needs to be introduced. It is the aim of this paper to do so by generalizing the notion of superregularity to matrices with any structure of zeros. To this end we introduce the notion of nontrivial minor (i.e., at least one term in the summation of the Leibniz formula for the determinant is nonzero). Hence, a matrix will be called superregular if all of its nontrivialminorsarenonzero. Thisnotionnaturallyextendsthe previousnotionsofsuperregularity as they have all of its possible nonzero minors different from zero. A key result in this paper is that any F-linear combination of columns of a superregular matrix have the largest possible number of nonzero components (to be made more precise in Section 3). This is a general matrix theoretical result and it stands in its own right. As an application, we will show that this result will ensure that any convolutional code associated to a superregular matrix have the maximum possible distance. In[6,9]itwasprovedthatthedistanceofaconvolutionalcodewithratek/nanddifferentForney indices ν < ··· < ν is upper bounded by n(ν +1)−m +1 where m is the multiplicity of the 1 ℓ 1 1 1 Forney index ν . Whether this bound was optimalor not wasleft as anopen question. In this work 1 we show that it is indeed optimal by presenting a class of convolutional codes that achieve such a bound. In the particular case that the given Forney indices have two consecutive values, say ν and ν+1, then our construction yields a new class of (strongly) MDS convolutional codes. 2. Convolutional codes In this section we recallbasic material from the theory of convolutionalcodes that is relevantto the presented work. In this paper we consider convolutionalcodes constituted by codewords having finite support. Let F be a finite field and F[z] the ring of polynomials with coefficients in F. A (finite support) convolutional code C of rate k/n is an F[z]-submodule of F[z]n, where k is the rank of C (see [12]). The elements of C are called codewords. A full column rank matrix G(z) ∈ F[z]n×k whose columns constitute a basis for C is called an encoder of C. So, C =imF[z]G(z)= v(z)∈F[z]n | v(z)=G(z)u(z) with u(z)∈F[z]k . (cid:8) (cid:9) 2 Convolutional codes of rate k/n are linear devices which map a sequence of k-dimensional in- formation words u ,u ,...,u (expressed as u(z) = ǫ u zi), into a sequence of n-dimensional 0 1 ǫ i=0 i codewords v0,v1,...,vγ (written as v(z) = γi=0vizPi). In this sense it is the same as block codes. The difference is that convolutionalencoPders have a internal “storagevector”or“state vector”. Consequently, convolutionalcodes are often characterized by the code rate and the structure of the storage device. The j-th column degree of G(z)=[g (z)]∈F[z]n×k (also knownas constraintlength of the j-th ij input of the matrix G(z), see [8]) is defined as ν = max degg (z) j ij 1≤i≤n the memory m of the polynomial encoder as the maximum of the columns degrees, that is, m= max ν j 1≤j≤k and the total memory (or overall constrain length) as the sum of the constraint length ν = ν . j 1≤Xj≤k The encoder G(z) can be realizedby a linear sequential circuitconsisting of k shift registers, the j-th of length ν , with the outputs formed as sums of the appropriate shift registers contents. j Two full column rank matrices G (z),G (z) ∈ F[z]n×k are said to be equivalent encoders if 1 2 imF[z]G1(z) = imF[z]G2(z), which happens if and only if there exists a unimodular matrix U(z) ∈ F[z]k×k such that G (z)=G (z)U(z) [8, 12]. 2 1 Among the encoders of the code, the column reduced are the ones with smallest sum of the column degrees. Definition 2.1. Given a matrix G(z) = [g (z)] ∈ F[z]n×k with column degrees ν ,...,ν let Ghc ij 1 k (hc stands for highest coefficient) be the constant matrix whose (i,j)-entryis the coefficient of degree ν if degg =ν or zero otherwise. We say that G(z) is columnreduced if Ghc is full column rank. j ij j It was shown by Forney [4] that two equivalent column reduced encoders have the same column degreesup to a permutation. For this reasonsuchdegreesare calledthe Forney indices ofthe code, see [9]. The number of Forney indices with a certain value ν is called the multiplicity of ν. The degree of a convolutional code is the sum of the Forney indices of the code. Definition 2.2. An important distance measure for a convolutional code C is the distance dist(C) defined as dist(C):= wt(v(D)) | v(D)∈C and v(D)6=~0 , n o where wt(v(D)) is the Hamming weight of a polynomial vector v(D)= v Di ∈F[D]n, i Xi∈N defined as wt(v(D))= wt(v ), i Xi∈N where wt(v ) is the number of nonzero components of v . i i 3 In[12],RosenthalandSmarandacheshowedthatthedistanceofaconvolutionalcodeofratek/n and degree δ must be upper bounded by δ dist(C)≤(n−k) +1 +δ+1. (1) (cid:18)(cid:22)k(cid:23) (cid:19) This bound was called the generalized Singleton bound since it generalizes in a natural way the Singleton bound for block codes (when δ = 0). A convolutional code of rate k/n and degree δ with its distance equal to the generalizedSingletonbound was calleda maximum distance separable (MDS) code[12]. Itwasalsoobservedin[9,12]thatifC is MDS,thenits setofForneyindicesmust haveξ :=k( δ +1)−δ indicesofvalue δ andk−ξ indicesofvalue δ +1(thissetofindicesare k k k calledinthe(cid:4)lit(cid:5)erature“genericsetofcol(cid:4)um(cid:5)nindices”or“compact”). F(cid:4)ew(cid:5)algebraicconstructionsof MDS convolutional codes are known, see [15, 10]. The particular case where (n−k) divides δ was investigated in [6]. Note that in this case all the Forney indices of a MDS convolutional code are equal. Itistheaimofthispapertostudythedistancepropertiesofconvolutionalcodesofgivenrate andany setofForneyindices. Equivalentsboundsofthedistanceofthesecodeswereindependently given in [12] and in [9]. Theorem 2.3. [12] Let C be a convolutional code with rate k/n and different Forney indices ν < 1 ···<ν with corresponding multiplicities m ,...,m . Then the distance of C must satisfy ℓ 1 ℓ dist(C)≤n(ν +1)−m +1. 1 1 Aconvolutionalcode ofrate k/n with differentForney indices ν <···<ν andwith correspon- 1 ℓ ding multiplicities m ,...,m and distance n(ν +1)−m +1 is saidto be anoptimal (n,k,ν ,m ) 1 ℓ 1 1 1 1 convolutional code. Note that a convolutional code of rate k/n and degree δ is MDS if and only if is an optimal (n,k, δ ,k( δ +1)−δ) convolutionalcode. k k (cid:4) (cid:5) (cid:4) (cid:5) It was left as an open question whether there always exist optimal (n,k,ν ,m ) convolutional 1 1 codes for all rates and Forney indices ν ≤···≤ν . In the next section, we consider a special class 1 k of matrices that will allow us to exhibit convolutionalcodes with this property. 3. Superregular Matrices In this section, we recall some pertinent definitions on superregular matrices and introduce a newconstructionofsuperregularmatricesthatwewillusetoobtainMDSconvolutionalcodes. Such matrices have some similarities with the ones introduced in [1]. They have similar entries and, therefore, some properties are the same, even if the structure of these new matrices is different. Let F be a field, A=[µ ] be a square matrix of order m over F and S the symmetric groupof iℓ m order m. The determinant of A is given by |A|= (−1)sgn(σ)µ ···µ . 1σ(1) mσ(m) σX∈Sm Whenever we use the word term, we will be considering one product of the form µ ···µ , 1σ(1) mσ(m) with σ ∈S , and the wordcomponent willbe reservedto refer to eachofthe µ , with 1≤i≤m m iσ(i) in a term. Denote µ ···µ by µ . 1σ(1) mσ(m) σ A trivial term of the determinant is a term µ , with at least one component µ equalto zero. σ iσ(i) If A is a square submatrix of a matrix B with entries in F, and all the terms of the determinant of A are trivial, we say that |A| is a trivial minor of B (if B =A we simply say that |A| is a trivial minor). We say that a matrix B is superregular if all its nontrivial minors are different from zero. In the next theorem we study the weight of vectors belonging to the image of a superregular matrix. 4 Theorem 3.1. Let F be a field and a,b∈N, such that a≥b and B ∈Fa×b. Suppose that u=[u ]∈ i Fb×1 is a column matrix such that u 6=0 for all 1≤i≤b. If B is a superregular matrix and every i row of B has at least one nonzero entry then wt(Bu)≥a−b+1. Proof: Suppose thatwt(Bu)≤a−b,then thereexists asquaresubmatrix ofB oforderb =b,say 1 B , such that B u = 0, and so | B |= 0, i. e., the columns of B are linearly dependent. Since B 1 1 1 1 is superregular, |B | is a trivial minor. By hypothesis u 6=0, for all 1≤i≤b, which implies that 1 i every row of B must have at least two nonzero entries. On the other hand, B may have some of 1 1 its columns identically equal to zero. Using the fact that B is also superregular, we are going to show that there exists, up to per- 1 mutation of rows and columns, a square submatrix B of B of order b , with b < b , such that 2 1 2 2 1 B u = 0, where u is a column matrix with b rows whose entries are elements of u. Therefore, 2 2 | B | is a trivial minor which implies that the columns of B are linearly dependent. Also every 2 2 roweof B will haeve at least two nonzero entries. But then, proceeding in this way, we would ob- 2 tain an infinite sequence B ,B ,B ,... of square matrices of orders b ,b ,b ,..., respectively, with 1 2 3 1 2 3 0 < ··· < b < b < b all having at least two nonzero entries in every row. Of course, this cannot 3 2 1 happen, hence, wt(Bu)≥a−b+1. This is an applicationofthe infinite descentmethod ofFermat. Since u 6= 0, for all 1 ≤ i ≤ b, if some of the columns of B are identically equal to zero, then i 1 the remaining columns are still linearly dependent. Let B be the matrix formed by the columns of B with at least one nonzero entry and let B be a square submatrix of B with the same number of 1 columns. Denote by m the order of B. Clearly m≤b . b 1 Let t be the dimension of the subspace generated by the columns of B. Then B has a t×t b submatrixwhosecolumnsarelinearlyindependent. Therefore,itsdeterminantisnonzeroandttandf >m−t, ν ν ν ν−1 all the other sets of the three sequences are nonempty. Let us assume that D ∩E =∅, for any λ∈{1,2,...,ν}, (7) λ λ and that, for any λ∈{1,...,ν}, if i∈D and j ∈E then µ =0. (8) λ λ ij We will prove (7) and (8) later. Since F =D ∪E ∪F and, from(3) and (7), D , E andF arepairwise disjoint. we have λ−1 λ λ λ λ λ λ f =d +e +f , (9) λ−1 λ λ λ F \D =E ∪F , (10) λ−1 λ λ λ and F \E =D ∪F . (11) λ−1 λ λ λ From (4), (5), (10), (11) and since Z = 0, we obtain that if i ∈ D and j ∈ E then the i-th 0 0 row of M has at most t−(f +e ) = d nonzero entries and the j-th column of M has at most 1 1 1 t−(f +d )=e nonzero entries. 1 1 1 Now, given i ∈ D , for λ ∈ {1,2,...,ν −1}, the i-th row of M has zeros in all entries (i,j) λ with j ∈ E ∪F , by (4) and (10), and in all entries (i,j) with j ∈ E . We show next that λ+1 λ+1 λ µ = 0 for i ∈ D and j ∈ E for any 1 ≤ κ < λ. If κ = λ−1, since by (11) i ∈ F \E , then ij λ κ λ−1 λ 6 by (5) λ = 0. If κ < λ−1, since i ∈ D , then i ∈ F , so by (5) and (11), as j ∈ E , we have ij λ κ+1 κ µ = 0. Thus, since F ,E ,E ,...,E are pairwise disjoint, the i-th row of M has at most ij λ+1 λ+1 λ 1 t−(e +f +e +e +···+e ) nonzeroentries. Using (9) afew times, we conclude that the λ+1 λ+1 λ λ−1 1 number of nonzero entries of the i-th row of M is at most d +···+d +d . 1 λ λ+1 Similarly, if j ∈E , for λ∈{1,2,...,ν−1}, then the j-th column of M has at most λ e +···+e +e 1 λ λ+1 nonzero entries. Finally, the i-th row of M, with i ∈ D , has zeros in all entries (i,j), with j ∈ E , by (8), and ν ν in all entries (i,j) with j ∈ E , with 1 ≤ κ < ν, by (5) and (11). Hence, the i-th row of M has at κ most t−(e +e +···+e ) nonzero entries. Using (9), we conclude that the number of nonzero ν ν−1 1 entries of the i-th row of M is at most d +d +···+d +f . 1 2 ν ν By a similar reasoning, we conclude that the j-th column of M, with i∈D , has at most ν e +e +···+e +f 1 2 ν ν nonzero entries. Permuting the rows of M we obtain a matrix M¯ such that: • the last m−t rows remain unchanged; • the rows of M in D will become the rows m−t−1,...,m−t−d in M¯; 1 1 • for λ=2,...,ν, the rows of M in D will become the rows m−t−1− λ−1d ,...,m−t− λ i=1 i λ d . P i=1 i P Applying to M¯ the following column permutations we obtain a matrix N such that: • the last m−t columns remain unchanged; • the columns of M¯ in E will become the columns m−t−1,...,m−t−e in N; 1 1 • forλ=2,...,ν,thecolumnsofM¯ inE willbecomethecolumnsm−t−1− λ−1e ,...,m− λ i=1 i t− λ e . P i=1 i P Thus, the matrix N satisfies the following properties: 1. its last m−t+d +···+d rows have at most d +···+d +f nonzero entries in the first 1 ν 1 ν ν d +···+d +f columns and zeros afterwards. 1 ν ν 2. its last m−t+d +···+d rows have at most d +···+d nonzero entries in the first 1 ν−1 1 ν d +···+d columns and zeros afterwards. 1 ν 3. its last m−t+e +···+e columns have at most e +···+e nonzero entries in the first 1 ν−1 1 ν e +···+e rows and zeros afterwards. 1 ν Let us define a square submatrix B of N of order b , with b < b , and such that B u˜ = 0 2 2 2 1 2 where u˜ is a column matrix whose entries are elements of u. From the inequality (6), three cases may happen: 7 1. If m−t≥f , let b =d +···+d +f and take B to be a square submatrix of order b , of ν 2 1 ν ν 2 2 the matrix formed by the last m−t+d +···+d rows of N and the first d +···+d +f 1 ν 1 ν ν columns of N. 2. If m−t≥d , let b =d +···+d and take B to be a square submatrix of order b , of the ν 2 1 ν 2 2 matrixformedby the lastm−t+d +···+d rowsofN andthe firstd +···+d columns 1 ν−1 1 ν of N. 3. If m−t≥e , let b =t−(e +···+e ) and take B to be a square submatrix of order b , ν 2 1 ν−1 2 2 ofthematrixformedbythe lastm−(e +···+e )rowsofN andthe firstt−(e +···+e ) 1 ν 1 ν−1 columns of N. In either case, choosing u=[u ,...,u ]T, accordingly, we have B u=0. Notice that b

Superregular matrices and applications to convolutional codes

Similar Superregular matrices and applications to convolutional codes