We consider matrix-product codes $${[C_1\cdots C_s] \cdot A}$$ , where $${C_1, \ldots , C_s}$$ are nested linear codes and matrix A has full rank. We compute their minimum distance and provide a decoding algorithm when A is a non-singular by columns matrix. The decoding algorithm decodes up to half of the minimum distance.
Discover the world's research
- 20+ million members
- 135+ million publications
- 700k+ research projects
Join for free
Construction and decoding of matrix-product
codes from nested codes∗
Fernando Hernando† Kristine Lally‡Diego Ruano§
Abstract
We consider matrix-product codes [C1 · · · Cs ]· A , where C1 ,...,C s
are nested linear codes and matrix Ahas full rank. We compute their
minimum distance and provide a decoding algorithm when Ais a non-
singular by columns matrix. The decoding algorithm decodes up to half
of the minimum distance.
1 Introduction
We consider the matrix-product construction, [C1 · · · Cs ]·A , introduced by
Blackmore and Norton in [2] which may also be seen as a generalization of
the Plotkin (u| u +v )-construction. In [2] a lower bound for the minimum dis-
tance when the matrix Ahas a certain property, called non-singular by columns,
is obtained. Moreover, this bound is sharp if the non-singular by columns ma-
trix is triangular. The same construction and a similar lower bound for the
minimum distance are also given by ¨
Ozbudak and Stichtenoth in [9], but for an
arbitrary matrix A . In the particular case of non-singular by columns matrices
the bounds coincide. The construction in [9] is a generalization of the one in
[8]. See also [1] and [7] for other generalizations.
In this paper we prove that the lower bound given in [9] is sharp when
the codes C1 , . . . , Cs are nested. This key property also enables an efficient
decoding procedure for a class of matrix-product codes. In section 3 we provide
a decoding algorithm for matrix-product codes where the codes C1 , . . . , Cs are
nested and the matrix Ais non-singular by columns. This decoding algorithm
decodes up to half of the minimum distance.
In section 4 we consider the matrix-product construction when C1 , . . . , Cs
are cyclic codes. The resulting codes are quasi-cyclic codes. The quasi-cyclic
class of codes is the natural generalization of the cyclic class, and acquired a
special interest after it was shown that some codes in this class meet a modified
∗The work of F. Hernando is supported in part by the Claude Shannon Institute, Science
Foundation Ireland Grant 06/MI/006 (Ireland) and by MEC MTM2007-64704 and Junta de
CyL VA025A07 (Spain). The work of D. Ruano is supported in part by DTU, H.C. Oersted
post doc. grant (Denmark) and by MEC MTM2007-64704 and Junta de CyL VA065A07
(Spain)
†Department of Mathematics, University College Cork, Cork, Ireland. F.Hernando@ucc.ie
‡Department of Mathematics and Statistics, RMIT University, Melbourne, Australia.
kristine.lally@rmit.edu.au
§Department of Mathematics, Technical University of Denmark, Matematiktorvet, Build-
ing 303, DK-2800, Kgs. Lyngby, Denmark. D.Ruano@mat.dtu.dk
1
Gilbert-Varshamov bound [3]. Applying our previous results to this case, we
provide the minimum distance and a decoding algorithm for a class of quasi-
cyclic codes.
2 Matrix-Product Codes
We follow the Blackmore and Norton approach in [2] to introduce matrix-
product codes. With this setting, one can define large codes from small ones.
Definition 2.1. Let C1 , . . . , Cs ⊂ Fm
qbe linear codes of length mand a matrix
A= ( ai,j ) ∈ M( Fq , s × l ), with s≤ l . The matrix-product code C =
[C1 · · · Cs ]·A is the set of all matrix-products [c1 · · · cs ]·A where ci ∈ Ci is an
m×1 column vector ci = (c1,i , . . . , cm,i )T for i = 1, . . . , s. Therefore, a typical
codeword cis
c=
c1,1 a1,1 + · · · + c1,s as,1 · · · c1,1 a1,l + · · · + c1,s as,l
.
.
... . .
.
.
cm,1 a1,1 + · · · + cm,s as,1 · · · cm,1 a1,l + · · · + cm,s as,l
.(1)
The matrix-product construction is also presented by ¨
Ozbudak and Stichtenoth
in [9]. Clearly the i -th column of any codeword is an element of the form
Ps
j=1 a j,i c j ∈F m
q, therefore reading the entries of the m× l -matrix above in
column-major order, the codewords can be viewed as vectors of length ml,
c=
s
X
j=1
aj,1 cj ,...,
s
X
j=1
aj,lcj
∈Fml
q.(2)
Henceforth we will use either notation (1) or (2) as required without further
comment.
From the above construction it follows that a generator matrix of Cis of the
form:
G=
a1,1 G1a1,2 G1 · · · a1,s G1 · · · a1,l G1
a2,1 G2a2,2 G2 · · · a2,s G2 · · · a2,l G2
.
.
..
.
.· · · .
.
.· · · .
.
.
as,1 Gsas,2 Gs · · · as,sGs · · · as,l Gs
,
where Gi is a generator matrix of Ci ,i = 1, . . . , s . Moreover, if Ci is a [m, ki, di ]
code then one has that [C1 · · · Cs ]·A is a linear code over Fq with length lm and
dimension k = k1 + · · · +ks if the matrix Ahas full rank and k < k1 + · · · +k s
otherwise. In the following we assume Ahas full rank.
Let us denote by Ri = (ai,1 , . . . , ai,l ) the element of F l
qconsisting of the i-th
row of A , for i = 1, . . . , s . We denote by Di the minimum distance of the code
CR i generated by h R1 , . . . , Ri i in Fl
q. In [9] the following lower bound for the
minimum distance of the matrix-product code C is obtained,
d( C)≥ min{ d1 D1 , d2 D2 , . . . , ds Ds } , (3)
where di is the minimum distance of Ci .
2
Considering the lower bound (3), since D1 ≥ · · · ≥ Ds , it is clear that, to
obtain a matrix-product code with good parameters, it is advisable to choose
Cj with minimum distance greater than or equal to that of Cj−1 . To this aim
it is therefore also advisable to choose Cj with dimension less than or equal to
that of Cj−1 . In particular it is wise to choose C1 with large dimension and
Cs with large minimum distance. For this reason, henceforth we will assume
that C1 , . . . , Cs are nested codes, C1 ⊃ C2 ⊃ · · · ⊃ Cs , and this condition is not
particularly restrictive. It follows that d1 ≤ · · · ≤ ds . Introducing this property
allows us to obtain several results: the following theorem for computing the
minimum distance and a decoding algorithm in the next section.
Theorem 2.2. Let C be the matrix-product code [ C1 · · · Cs ]· A where C1 ⊃ C2 ⊃
· · · ⊃ Cs are linear codes and matrix A ∈ M( Fq , s ×l) has full rank. Then, the
minimum distance of Cis
d( C ) = min{ d1 D1 , d2 D2 , . . . , ds Ds } , (4)
where di = d(Ci ) , Di = d ( C R i ) and CR i is as described above.
Proof. From [9] we have d (C )≥ min{d1 D1 , d2 D2 , . . . , ds Ds } (this result is also
valid for C1 , . . . , Cs non-nested). We include a rewriting of the proof here for
completeness. Any codeword of C is of the form c = [c1 · · · cs ]·A . Let us suppose
that cr 6 = 0 and ci = 0 for all i > r. It follows that [cj,1 · · · c j,s ]·A ∈ CR r for
j= 1 , . . . , m, where cj,i is the j -th component of the word ci . Since cr 6= 0 it
has at least dr non-zero components. Suppose ci v ,r 6 = 0, for v= 1, . . . , dr . For
each v = 1, . . . , dr , the product [ci v ,1 · · · ci v ,s ]·A is a non-zero codeword in C R r,
since A has full rank. Therefore the weight of [ci v ,1 · · · ci v ,s ]·A is greater than
or equal to Dr and the weight of cis greater than or equal to dr Dr .
In order to see that the above bound is sharp, we construct a codeword with
weight dr Dr , for each r = 1, . . . ,s . Choose c1 , . . . , cr such that c1 = · · · = cr ,
(this is possible since the codes are nested), with wt ( c1 ) = dr , and cr+1 = . . . =
cs = 0. Let f= P r
i=1 f i R i , with f i ∈F q , be a word in C R rof weight D r . If
c0
i=f i c i then
s
X
j=1
aj,1 c 0
j,...,
s
X
j=1
aj,l c0
j
=c1
r
X
j=1
aj,1 fj ,...,
r
X
j=1
aj,lfj
=c1f,
is a codeword in Cwith weight drDr , and the result holds.
Example 2.3. Consider the ternary linear codes C1 , C2, C3 with generator
matrices
G1 =
111
021
001
, G 2 = 111
021 , G3 = 111 ,
respectively. The parameters of these codes are [3, 3, 1], [3, 2, 2] and [3, 1,3],
respectively, and the codes are nested, C1 ⊃ C2 ⊃ C3 . Here d1 = 1, d2 = 2 and
d3 = 3.
3
We consider the matrix-product code C = [C1C2C3 ]·A where
A=
111
021
001
.(5)
The minimum distances of the codes C R i , i = 1, 2, 3 obtained from the matrix
Aare D1 = 3, D2 = 2 and D3 = 1.
On construction we find that Cis a [9,6] code. Applying Theorem 2.2 we
find that the minimum distance of Cis min{d1D1 , d2 D2 , d3 D3 } = 3. We note
that 3 is the largest possible minimum distance for a [9, 6] linear code over F3 .
Remark 2.4. If the codes C1 , . . . , Cs are not nested then the lower bound (3)
for the minimum distance is not necessarily sharp, that is, Theorem 2.2 does
not hold, as the following example shows.
Example 2.5. Consider the ternary cyclic codes C1 , C2, C3, C4 with generator
polynomials f1 = (x + 2)(x+ 1), f2 = (x2 + 1)(x+ 2), f3 = (x2 + 1) and
f4 = ( x2 + 1)( x + 1) respectively. Notice that since f1 - f2 , the codes are not
nested. The parameters of these codes are [4, 2, 2], [4, 1, 4], [4, 2, 2] and [4, 1, 4]
respectively. So here d1 = 2, d2 = 4, d3 = 2 and d4 = 4.
Consider C = [C1C2C3 C4 ]·A , where
A=
1111
0111
0011
0001
.(6)
The minimum distances of the codes CR i , i = 1,..., 4 obtained from the matrix
Aare D1 = 4, D2 = 1, D3 = 1 and D4 = 1.
On construction we find that Cis a [16, 6, 4] code. However, the lower bound
for the minimum distance is only min{d1D1 , d2 D2 , d3 D3 , d4 D4 } = 2.
In [2], the following condition for the matrix Ais introduced.
Definition 2.6. [2] Let A be a s× l matrix and At be the matrix consisting of
the first t rows of A . For 1 ≤j1 < · · · < jt ≤l , we denote by A ( j1 , . . . , jt ) the
t× tmatrix consisting of the columns j1 , . . . , jt of At .
A matrix A is non-singular by columns if A ( j1 , . . . , jt ) is non-singular
for each 1 ≤t≤s and 1 ≤j1 < · · · < jt ≤l . In particular, a non-singular by
columns matrix Ahas full rank.
By [2] a non-singular by columns matrix Adefines MDS codes CR i , for
i= 1 , . . . , s. Also in [2] the following lower bound for the minimum distance of
a matrix-product code with Anon-singular by columns is obtained,
d( C)≥ min{ ld1 , ( l− 1)d2 ,..., ( l− s + 1)ds } . (7)
This bound is the particular case of (3) when Di =l− i + 1. Moreover, it
was shown in [2] that if Ais non-singular by columns and triangular, (i.e. it is
a column permutation of an upper triangular matrix), then the bound (7) for
the minimum distance is sharp. Here we can deduce, by applying Theorem 2.2,
that if Ais non-singular by columns and the codes C1 , . . . , Cs are nested, then
this bound (7) is also sharp. It is known from [2] that, for s≥ 2 there exists an
s× lnon-singular by columns matrix over Fq if and only if s≤ l≤ q .
4
3 Decoding Algorithm
In this section, we present a decoding algorithm for a class of matrix-product
codes: namely, we consider s nested linear codes C1 , . . . , Cs ⊂ Fm
qand a non-
singular by columns matrix A ∈ M (Fq , s × l ), where s≤ l (see definition 2.6).
We provide a decoding algorithm for the matrix-product code C = [C1 · · · Cs ] ·
A⊂Fml
q, assuming that we have a decoding algorithm DC i for C i which decodes
up to ti = b ( di − 1)/2c errors, for i = 1, . . . , s . We assume that each DCi answers
"failure" if there is no codeword in Ci within distance b (di − 1)/ 2c of the received
word.
A codeword in Chas the form c = (P s
j=1 a j,1 c j ,..., P s
j=1 a j,l c j ), where c j ∈
Cj , for all j. Since we consider C1 , . . . , Cs to be nested codes, C1 ⊃ · · · ⊃ Cs ,
each block P s
j=1 a j,i c j of c is a codeword in C 1 . A first approach to decoding
might be to decode each block of a received word by decoder DC1 . However,
with this approach, we may not achieve the error correcting capability of the
code. A more sophisticated approach takes place here where we use the decoders
DCi , for i = 1 , . . . , s, in a such a way that we can always decode up to the full
error correcting capability of the code, that is, our decoding algorithm for C
decodes up to half of the minimum distance
d( C ) = min{ ld1 , ( l− 1)d2 ,..., ( l− s + 1)ds } . (8)
We first describe the main steps in our decoding algorithm. The algorithm
is outlined as a whole in procedural form in Algorithm 1.
Consider the codeword c = (P s
j=1 a j,1c j ,..., P s
j=1 a j,l c j ), for some c j ∈
Cj , for all j. Suppose that cis sent and that we receive p =c + e , where
e= (e1 , e2, . . . , el )∈ Fml
qis an error vector. Let {i 1 , . . . , i s }⊂{ 1, . . . , l} be
an ordered subset of indices. We now also suppose that esatisfies the extra
property that
wt( ei j )≤ tj for all j ∈ {1 , . . . , s} . (9)
We denote by pi = P s
j=1 a j,i c j +e i ∈F m
qthe i-th block of p, for i = 1 , . . . , l.
Since C1 ⊃ · · · ⊃ Cs , each block P s
j=1 a j,i c j of c is a codeword of C 1 .
Therefore, we decode the i1 -th block pi 1 of p using DC1 . Since wt (ei 1 )≤ t1 we
obtain ei 1 and P s
j=1 a j,i 1c j .
We do not know c1 , but we can eliminate it in every other block in the
following way: we consider a new vector p2) ∈ Fml
qwith components
p2)
i=p i −a 1,i
a1,i1
(pi 1 − e i 1 ) =
s
X
j=2
a2)
j,ic j +e i ,for i 6 = i 1 ,
where a2)
j,i =a j,i − a 1,i
a1,i1 a j,i 1 , and p 2)
i1 =p i 1−e i 1. Since A is a non-singular
by columns matrix, the elements of the first row of Aare non-zero, and so the
denominator a1,i1 is non-zero.
Since C2 ⊃ · · · ⊃ Cs , we notice that the i -th block of p2) is a codeword of
C2 plus the error block ei , for i ∈ {1 , . . . , s }\{ i1 }. We now decode the i2 -th
block p2)
i2 =P s
j=2 a 2)
j,i2 c j +e i 2 of p 2) using DC 2 . Since w (e i 2)≤t 2 we obtain
ei 2 and P s
j=2 a 2)
j,i2 c j .
5
As before, we do not know c2 , but we can eliminate it in every other block
as follows: we consider a new vector p3) ∈ Fml
qwith components
p3)
i=p2)
i−a 2)
2,i
a2)
2,i2
(p 2)
i2 −e i 2 ) =
s
X
j=3
a3)
j,ic j +e i ,for i 6 = i 1 , i 2 ,
where a3)
j,i =a 2)
j,i − a 2)
2,i
a2)
2,i 2
a2)
j,i2 ,p 3)
i1 =p 2)
i1 and p 3)
i2 =p2)
i2 −e i 2.
Notice that the i-th block of p3) is a codeword of C3 plus the error block ei ,
for i ∈ { 1 , . . . , s}\{ i1 , i2 }.
Then we iterate this process, defining pk) for k = 3, . . . , s , and decoding
the ik -th block using DCk . In this way, we obtain the error blocks ei , and
the corresponding codeword blocks P s
j=1 a j,i c j , for i∈ {i 1 , . . . , i s }. The vector
(P s
j=1 a j,i 1c j ,..., P s
j=1 a j,i sc j ) formed from these sdecoded blocks is equal to
the product [c1 · · · cs ]·A ( i1 , . . . , is ), where A ( i1 , . . . , is ) is the s× s -submatrix of
Aconsisting of the columns i1 , . . . , is . Since this matrix is full rank, we can now
easily compute c1 , . . . , cs by inverting A (i1 , . . . , is ) or solving the corresponding
linear system. Finally we recover the remaining l− s codeword blocks "for free"
(i.e. no decoding procedure is involved for these blocks) by simply recomputing
the entire codeword c = [c1 · · · cs ]·A = (P s
j=1 a j,1 c j ,..., P s
j=1 a j,l c j ), since we
know the cj 's and the matrix A.
For each elimination step in the above procedure, it is necessary that ak)
k,ik 6=
0, for each k = 2, . . . , s , to avoid zero division. We now prove that this follows
from the non-singular by columns property of A . Let A 1) =A . The matrix
Ak) = ( ak)
i,j )∈ M(F q , s ×l) , k = 2, . . . , s, is obtained recursively from A k −1) by
performing the following l− (k− 1) elementary column operations:
columni(Ak) ) = columni (Ak−1) )− a k−1)
k−1,i
ak−1)
k−1,ik−1
columni k−1 (Ak−1) ),
for each i / ∈ {i1 , . . . , ik−1 }. These operations introduce l − (k − 1) additional zero
elements in the k− 1-th row of Ak) at each iteration. Hence the minor of Ak)
given by the first k rows and the i1 , . . . , ik columns, is a triangular matrix (in this
case, a column permutation of a lower triangular matrix) whose determinant is
ak)
1,i1 · · · a k )
k,ik . Since A is non-singular by columns, this minor is non-singular. It
follows that the determinant is non-zero, and therefore ak)
k,ik 6= 0.
The procedure described above will successfully decode the received word, if
wt( e) ≤ b( d( C)− 1) /2c , and for a given choice of indices { i1 , . . . , is }⊂{ 1, . . . , l } ,
each error block satisfies wt (ei j )≤tj =b ( dj − 1)/2c , for all j = 1, . . . , s . The
procedure may fail if wt (ei j ) > tj for some j.
If a decoder DCj answers "failure" , that is, it cannot decode pj)
ij , since there
is no codeword in Cj within distance tj to the received block pj)
ij , then we
consider another ordered subset of indices, and start the procedure again.
Similarly if wt (ei j ) > tj and the decoder DCj incorrectly decodes the block
pj)
ij , then we can detect this at the end by checking whether the entire decoded
word is a codeword in Cor not (overall failure) and by checking that we have not
corrected more than b (d(C )− 1)/2c errors in total (incorrect overall decoding).
6
In either case we again consider another ordered subset of indices, and restart
the procedure.
We now prove that for every error vector e with wt ( e ) ≤ b (d(C )− 1)/2c
there exists a "good" set of indices {i1 , . . . , is } ⊂ { 1, . . . , l} satisfying condition
(9). We can therefore repeat the procedure described above, with various or-
dered subsets of indices, until a "good" set of indices is chosen and decoding is
successful. It follows that our algorithm decodes all error patterns of weight up
to half the minimum distance of the code.
Theorem 3.1. Let C be the matrix-product code [C1 · · · Cs ]·A , where C1 ⊃ · · · ⊃
Cs and Ais a non-singular by columns matrix. Let e = ( e1 , e2, . . . , el )∈F ml
q
be an error vector with wt(e ) ≤ b ( d( C)− 1) /2c . Then there exists an ordered
subset { i1 , . . . , is } ⊂ {1 , . . . , l} satisfying wt( ei j )≤ tj = b( dj − 1)/2c , for all
j∈ {1 , . . . , s} .
Proof. We claim that there exists i1 such that wt (e i 1 )≤ t1 . Suppose that there
is no i1 ∈ { 1, . . . , l} with wt (ei 1 )≤ t1 , that is, wt (ei )>b ( d1 − 1)/2c , for all
i= 1 , . . . , l. This implies that wt( ei )≥ d1 / 2, for all i. Using (8) we obtain,
wt( e)≥ ld 1
2>ld 1 − 1
2≥ ld 1 − 1
2 ≥ d (C)− 1
2
which contradicts our assumption.
Let us assume that the property holds for a subset {i1 , . . . , ij−1 } ⊂ { 1, . . . , l}
of size j− 1 < s . We now prove it holds for a subset of size j . Suppose
that there is no ij with wt (ei j )≤tj , that is, wt (ei )>b (dj − 1)/2c , for all
i∈ {1 , . . . , l }\{ i1 , . . . , ij−1 } . This implies that wt( ei )≥ dj /2, for all i ∈
{1 , . . . , l }\{ i1 , . . . , ij−1 }. Using (8) we obtain,
wt( e) ≥
j−1
X
k=1
wt( ei k ) + ( l−j+ 1) d j
2>
j−1
X
k=1
wt( ei k ) + ( l−j+ 1) dj −1
2≥
≥ (l− j+ 1) dj − 1
2 ≥ d (C)− 1
2
which contradicts our assumption and the result holds.
Summarizing, we can now formulate our decoding algorithm for C = [C1 · · · Cs ] ·
A⊂Fml
q, where C 1 ⊃ · · · ⊃ C s and A is a non-singular by columns matrix, in
procedural form in Algorithm 1.
Remark 3.2. We note that the algorithm becomes more computationally in-
tensive as the number of blocks sthat we may need to decode at each iteration,
and the total number of blocks l, increase. So, it is worthwhile to say that for
s= l= 2 (respectively 3) the algorithm only needs, at most, 2 (respectively 6)
iterations to find the right ordered subset of indices. In this case we need to
decode at most 4 (respectively 18) blocks of length mto achieve a successful
decoding of the full-length received word of length ml.
An advantage of using nested codes in our construction, from the point of
view of implementation in an electronic circuit, is that much of the circuitry
7
Algorithm 1 Decoding algorithm for C = [C1 · · · Cs ]· A
Input: Received word p= c+ e with c∈C and wt ( e) ≤ b(d (C ) − 1)/ 2 c .
C1 ⊃ · · · ⊃ Cs nested codes and A a non-singular by columns matrix.
Decoder DCi for code Ci ,i = 1, . . . , s.
Output: The codeword c .
1: p0 =p;A0 =A ;
2: for {i1 , . . . , is } ⊂ {1, . . . , l } do
3: p= p0 ;A =A0 ;
4: for j = 1, . . . , s do
5: pi j =DCj ( p i j );
6: if p i j = "failure" then
7: Break the loop and consider another i1 , . . . , is in line 1;
8: end if
9: for k= j + 1, . . . , s do
10: pi k =pi k −a j,ik
aj,ij
pi j ;
11: columni k(A ) = columni k (A )−a j,ik
aj,ij
columni j(A);
12: end for
13: end for
14: Obtain (c1 , . . . , cs ) from p i 1 , . . . , pi s ;
15: p= [C1 · · · Cs ]·A ; (see (1) and (2))
16: if p ∈C and wt ( p− p0 ) ≤ b( d( C) − 1)/ 2 c then
17: RETURN: p;
18: end if
19: end for
used for implementing decoder DC1 can also be used to implement decoders
DC2 , . . . , DCs of the subset subcodes C2 , . . . , Cs , respectively.
Generalized Reed-Muller codes are iterative matrix-product codes defined
using a non-singular by columns matrix (see [2]). Therefore, Algorithm 1 can
be used to decode this family of codes. Furthermore, Algorithm 1 can be con-
sidered as a generalization of the decoding algorithm for Reed-Muller codes in
[6, Chapter 13].
4 A class of Quasi-Cyclic codes from nested cyclic
codes
Finally we consider the matrix-product code, C = [C1 · · · Cs ]·A , where the
component codes C1 , . . . , Cs are cyclic codes of the same length. In this case, a
generator matrix of C can be constructed as an s× l array of truncated circulant
submatrices, and defines a quasi-cyclic code with sgenerators and index l, [4, 5].
Determining the minimum distance of an arbitrary quasi-cyclic code is not
easy, and a good general decoding algorithm has not yet been developed for
this class of codes. Here we note that when the cyclic codes C1 , . . . , Cs are
nested, and A is a non-singular by columns matrix, then Theorem 2.2 provides
the minimum distance, and Algorithm 1 provides a decoding algorithm for a
restricted class of quasi-cyclic codes, obtained by matrix-product construction.
8
We now provide an example of how Algorithm 1 proceeds in this case.
Example 4.1. Consider the following linear codes over F3 ,
•C1 the [13 , 10 , 3] cyclic code generated by f1 = x3 + x2 + x + 2.
•C2 the [13 ,7 , 5] cyclic code generated by f2 = ( x3 +x2 + x + 2)( x3 + 2 x2 +
2x + 2).
•C3 the [13 , 3 , 9] cyclic code generated by f3 = ( x + 2)( x3 + x + 2)( x3 +
x2 + x+ 2)( x3 + 2x2 + 2 x+ 2).
Let C = [C1C2 C3 ]·A , where Ais the non-singular by columns matrix
A=
111
021
001
.
We use decoder DCi for Ci , which decodes up to half the minimum distance,
i.e., DC1 , DC2 , DC3 decode up to t1 = 1, t2 = 2 and t3 = 4 errors, respectively.
One may easily check that D1 = 3, D2 = 2 and D3 = 1. Therefore, d (C ) =
min{d1D1 , d2 D2 , d3 D3 } = 9 by Theorem 2.2, thus we may correct up to t = 4
errors in a codeword of C.
We consider polynomial notation for codewords of Ci , for all i, that is the
codewords of length 13 in Ci are polynomials in Fq [x ] /(x 13 − 1) and words in
Care elements in (Fq [ x] /( x13 −1))3 . Let p =c +e be the received word, with
codeword c = (0, 0, 0) and the error vector of weight t = 4
e= (e1 , e2, e3 ) = (1 + x, 2x2 , 2x 11 ) .
•Consider, i1 = 1, i2 = 2, i3 = 3.
We decode the first block p1 = 1 + x of p , using DC1 . There is only one
word, 1 + x +x4 , in C1 within distance one to p1 , so DC1 decodes p1 to
p2)
1= 1 + x+ x 4 . Notice that it is incorrectly decoded, but we cannot
detect it at this moment. Proceeding, we compute
p2)
2=p 2 −p 2)
1= 2 + 2x+ 2x 2 + 2x 4 ,
p2)
3=p 3 −p 2)
1= 2 + 2x+ 2x 4 + 2x 11 .
The new matrix of coefficient is
A2) =
100
021
001
.
Then, we decode p 2)
2using DC 2 . There is only one word, 2 + 2x + 2x 2 +
x4 +x11 , in C2 within distance two to p2)
2. Thus, DC 2 decodes p 2)
2to
p3)
2= 2 + 2x+ 2x 2 +x 4 +x 11 . We compute
p3)
3=p 2)
3−2p 3)
2= 1 + x+ 2x 2 .
9
Finally, we decode p 3)
3using DC 3 . Since there is only one word, 0, in C 3
within distance four to p 3)
3,DC 3 decodes p 3)
3to p 4)
3= 0.
Notice that the distance of the decoded word (p2)
1, p 3)
2, p 4)
3) to p is 6 > t =
4, thus we have corrected more errors than the error correction capability
of the code which implies that we should consider another set of indices.
•Second attempt, consider i1 = 2, i2 = 1, i3 = 3.
We decode the second block p2 = 1 + x of p , using DC1 . There is only
one word, 0, in C1 within distance one to p1 . Thus, DC1 decodes p2 to
p2)
2= 0. Proceeding, we compute
p2)
1=p 1 −p 2)
2=p 1 = 1 + x,
p2)
3=p 3 −p 2)
2=p 3 = 2x 11.
The new matrix of coefficient is
A2) =
010
122
001
.
Then, we decode p2)
1using DC 2 . There is only one word, 0, in C 2 within
distance two to p2)
1. Thus, DC 2 decodes p 2)
1to p 3)
1= 0. We compute
p3)
3=p 2)
3−p 3)
1=p 3 = 2x 11.
We decode p 3)
3using DC 3 . Since there is only one word, 0, in C 3 within
distance four to p 3)
3,DC 3 decodes p 3)
3to p 4)
3= 0. And since the weight of
p− p3) is equal to 4, we have decoded the received word successfully.
Acknowledgements
The authors would like to thank M. Greferath for his course at Claude Shannon
Institute and P. Beelen and T. Høholdt for helpful comments on this paper.
References
[1] van Asch, B.; "Matrix-product codes over finite chain rings"; Appl. Algebra
Engrg. Comm. Comput. 19 (2008), no. 1, 39–49
[2] Blackmore, T.; Norton, G.H.; "Matrix-product codes over Fq "; Appl. Algebra
Engrg. Comm. Comput. 12 (2001), no. 6, 477–500.
[3] Kasami, T.; "A Gilbert-Varshamov bound for quasi-cyclic codes of rate 1/2",
IEEE Trans. Inform. Theory, 20, pp. 679, 1974.
10
[4] Lally, K.; Fitzpatrick, P.; "Algebraic Structure of quasicyclic codes"; Dis-
crete Appl. Math., 111, no. 1-2, pp. 157–175, 2001.
[5] Ling, S.; Sol´e. P.; "On the algebraic structure of quasi-cyclic codes I: finite
fields", IEEE Trans. Inform. Theory, vol. IT-47, 2751–2759, Nov. 2001.
[6] Macwilliams, F.J.; Sloane N.J.A.; The Theory of Error-Correcting Codes,
ser. North-Holland mathematical library. North-Holland, 1977, vol. 16.
[7] Mart´ınez-Moro, E.; "A generalization of Niederreiter-Xing's propagation
rule and its commutativity with duality"; IEEE Trans. Inform. Theory 50
(2004), no. 4, 701–702.
[8] Niederreiter, H.; Xing, C.; "A propagation rule for linear codes"; Appl.
Algebra Engrg. Comm. Comput. 10 (2000), no. 6, 425–432.
[9] ¨
Ozbudak, F.; Stichtenoth, H.; "Note on Niederreiter-Xing's propagation rule
for linear codes"; Appl. Algebra Engrg. Comm. Comput. 13 (2002), no. 1, 53–
56.
11
... In 2001, Blackmore and Norton [3] proposed a new class of codes called matrixproduct codes. From then on, some scholars considered several kinds of such codes and obtained many meaningful results related to their minimum distances, duals and decoding algorithms, see [5,6,9,10,17,18,33,35]. In recent years, seeking for the matrix-product codes satisfying Euclidean or Hermitian dual-containing is a new manner to construct good quantum codes. ...
... Let us recall some basics on matrix-product codes. Definition 1 [3,17] ...
- Meng Cao
- Jianlian Cui
In 2001, Blackmore and Norton introduced an important tool called matrix-product codes, which turn out to be very useful to construct new quantum codes of large lengths. To obtain new and good quantum codes, we first give a general approach to construct matrix-product codes being Hermitian dual-containing and then provide the constructions of such codes in the case s∣(q2-1)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$s{\mid }(q^{2}-1)$$\end{document}, where s is the number of the constituent codes in a matrix-product code. For s∣(q+1)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$s{\mid } (q+1)$$\end{document}, we construct such codes with lengths more flexible than the known ones in the literature. For s∣(q2-1)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$s{\mid } (q^{2}-1)$$\end{document} and s∤(q+1)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$s{\not \mid } (q+1)$$\end{document}, such codes are constructed in an unusual manner; some of the constituent codes therein are not required to be Hermitian dual-containing. Accordingly, by Hermitian construction, we present two procedures for acquiring quantum codes. Finally, we list some good quantum codes, many of which improve those available in the literature or add new parameters.
... For general matrix product codes over finite fields, a lower bound for the minimum distance was obtained in [40]. Decoding methods for some matrix product codes were also discussed in [26,27,29]. Other related works may be found in [28,36,37]. ...
... Theorem 2.1 (Cf. [40], [27,Theorem 1]). The matrix-product code [C 1 , . . . ...
https://doi.org/10.1016/j.disc.2019.111768
... If we give the decoder information which symbols are erased (unreliable) and not erased (reliable), then we are performing error-and-erasure decoding. It follows from Theorem 2 that an error-anderasure decoder that decodes every received word that satisfies (2), and rejects all other received words, can be described by a map ...
... gives us the (u + v + w | 2u + v | u) construction. B (2) has minimum distance 2 and can thus only detect one error, while B (1) has minimum distance 3, which means that it can correct one error. ...
Generalized concatenated codes were introduced in the 1970s by Zinoviev. There are many types of codes in the literature that are known by other names that can be viewed as generalized concatenated codes. Examples include matrix-product codes, multilevel codes and generalized cascade codes. Decoding algorithms for generalized concatenated codes were developed during the 1970s and 1980s. However, their use does not appear to be as widespread as it should, especially for codes that are known by other names but can be viewed as generalized concatenated codes. In this paper we review the decoding algorithms for concatenated codes, generalized concatenated codes and matrix-product codes, and clarify the connection between matrix-product codes and generalized concatenated codes. We present a small improvement to the decoding algorithm for concatenated codes. We also extend the decoding algorithms from errors-only decoders to error-and-erasure decoders. Furthermore, we improve the upper bound on the computational complexity of the decoding algorithm in the case of matrix-product codes where the generator matrix for the inner code is non-singular by columns.
... Ever since the introduction, researchers have been trying to pave new tracks in this area. Particularly relevant to us here are constructions of matrixproduct codes over various commutative rings (see, for instance, [6][7][8][9][10][11]). Let C i be an [n, k i ]-linear code over R, for i � 1, . . . ...
-
![Boulagouaz M Hammed]()
- Abdulaziz Deajim
A well-known lower bound (over finite fields and some special finite commutative rings) on the Hamming distance of a matrix-product code (MPC) is shown to remain valid over any commutative ring R. A sufficient condition is given, as well, for such a bound to be sharp. It is also shown that an MPC is free when its input codes are all free, in which case a generator matrix is given. If R is finite, a sufficient condition is provided for the dual of an MPC to be an MPC, a generator matrix for such a dual is given, and characterizations of LCD, self-dual, and self-orthogonal MPCs are presented. Finally, the results of this paper are used along with previous results of the authors to construct novel MPCs arising from σ,δ-codes. Some properties of such constructions are also studied.
... Matrix-product codes over finite fields can be viewed as a generalization of the Plotkin's (u|u +v)-construction and the ternary (u +v +w|2u +v|u)-construction, see Refs. [16][17][18][19][20]. It is worth mentioning that Mankean and Jitman gave a necessary condition that matrix-product construction are Euclidean and Hermitian self-orthogonal linear codes [21,22]. ...
- Hao Song
- Ruihu Li
- Yang Liu
- Guanmin Guo
In this paper, we provide methods for constructing Hermitian dual-containing (HDC) matrix-product codes over \(\mathbb {F}_{q^2}\) from some non-singular matrices and a special sequence of HDC codes and determine parameters of obtained matrix-product codes when the input matrix and sequence of HDC codes satisfy some conditions. Then, using some nested HDC BCH codes with lengths \(n=\frac{q^4-1}{a} (a=1 ~\)or\(~ a=q\pm 1)\), we construct some HDC matrix-product codes with lengths \(N=\) 2n or 3n and derive nonbinary quantum codes with length N from these matrix-product codes via Hermitian construction. Four classes of quantum codes over \(\mathbb {F}_{q}\) (\(3\le q\le 5\)) are presented, whose parameters are better than those in the literature. Besides, some of our new quantum codes can exceed the quantum Gilbert-Varshamov (GV) bound.
-
![Hualu Liu]()
- Xiusheng Liu
In this paper, we firstly present a new criterion of linear complementary pairs (abbreviated to LCP) of codes over finite fields. Our result for the linear complementary pairs of codes extends the criterion of linear complementary dual (LCD) codes given by Massey. Then, two methods to construct LCP of codes from matrix product codes are provided, and concrete examples are presented to construct good parameters of LCP of codes.
-
![M. B. Ould Medeni]()
- Abdulaziz Deajim
Self-orthogonal codes and self-dual codes, on the one hand, and matrix-product codes, on the other, form important and sought-after classes of linear codes. Combining the two constructions would be advantageous. Adding to this combination the relaxation of the underlying algebraic structures to be commutative rings instead of fields would be even more advantageous. The current article paves a path in this direction. The authors study the problem of self-orthogonality and self-duality of matrix-product codes over a commutative ring with identity. Some methods as well as special matrices are introduced for the construction of such codes. A characterization of such codes in some cases is also given. Some concrete examples as well as applications to torsion codes are presented.
- Meng Cao
Matrix-product codes over finite fields are an important class of long linear codes by combining several commensurate shorter linear codes with a defining matrix over finite fields. The construction of matrix-product codes with certain self-orthogonality over finite fields is an effective way to obtain good $q$-ary quantum codes of large length. Specifically, it follows from CSS construction (resp. Hermitian construction) that a matrix-product code over $\mathbb{F}_{q}$ (resp. $\mathbb{F}_{q^{2}}$) which is Euclidean dual-containing (resp. Hermitian dual-containing) can produce a $q$-ary quantum code. In order to obtain such matrix-product codes, a common way is to construct quasi-orthogonal matrices (resp. quasi-unitary matrices) as the defining matrices of matrix-product codes over $\mathbb{F}_{q}$ (resp. $\mathbb{F}_{q^{2}}$). The usage of NSC quasi-orthogonal matrices or NSC quasi-unitary matrices in this process enables the minimum distance lower bound of the corresponding quantum codes to reach its optimum. This article has two purposes: the first is to summarize some results of this topic obtained by the author of this article and his cooperators in \cite{Cao2020Constructioncaowang,Cao2020New,Cao2020Constructionof}; the second is to add some new results on quasi-orthogonal matrices (resp. quasi-unitary matrices), Euclidean dual-containing (resp. Hermitian dual-containing) matrix-product codes and $q$-ary quantum codes derived from these newly constructed matrix-product codes.
Given a commutative ring R with identity, a matrix A∈Ms×l(R), and linear codes C1,⋯,Cs over R of the same length, this article considers the hull of the matrix-product code [C1⋯Cs]A. Consequently, it introduces various sufficient conditions (as well as some necessary conditions in certain cases) under which [C1⋯Cs]A is a complementary dual (LCD) code. As an application, LCD matrix-product codes arising from torsion codes over finite chain rings are considered. Moreover, we show the existence of asymptotically good sequences of LCD matrix-product codes over such rings.
Linear complementary dual (LCD) codes are linear codes satisfying C∩C⊥={0}. Researchers have proved to construct linear codes over finite fields Fq, q>3, is equivalent to construct LCD codes. This means that the investigation of binary and ternary LCD codes is the only remaining open problem. In this work, we propose new constructions of binary and ternary LCD codes by using matrix-product codes and prove that binary and ternary LCD codes from matrix-product codes are asymptotically good. Then we construct some new and good binary and ternary LCD codes using matrix-product matrices.
A new algebraic approach to quasi-cyclic codes is introduced. The key idea is to regard a quasi-cyclic code over a field as a linear code over an auxiliary ring. By the use of the Chinese remainder theorem (CRT), or of the discrete Fourier transform (DFT), that ring can be decomposed into a direct product of fields. That ring decomposition in turn yields a code construction from codes of lower lengths which turns out to be in some cases the celebrated squaring and cubing constructions and in other cases the (u+υ|u-υ) and Vandermonde constructions. All binary extended quadratic residue codes of length a multiple of three are shown to be attainable by the cubing construction. Quinting and septing constructions are introduced. Other results made possible by the ring decomposition are a characterization of self-dual quasi-cyclic codes, and a trace representation that generalizes that of cyclic codes
- Tim Blackmore
- Graham H. Norton
Codes C 1 ,…,C M of length n over ?q and an M × N matrix A over ?q define a matrix-product code C = [C 1 …C M ] ·A consisting of all matrix products [c 1 … c M ] ·A. This generalizes the (u|u+v)-, (u+v+w|2u+v|u)-, (a+x|b+x|a+b+x)-, (u+v|u-v)- etc. constructions. We study matrix-product codes using Linear Algebra. This provides a basis for a unified analysis of |C|, d(C), the minimum Hamming distance of C, and C ⊥. It also reveals an interesting connection with MDS codes. We determine |C| when A is non-singular. To underbound d(C), we need A to be `non-singular by columns (NSC)'. We investigate NSC matrices. We show that Generalized Reed-Muller codes are iterative NSC matrix-product codes, generalizing the construction of Reed-Muller codes, as are the ternary `Main Sequence codes'. We obtain a simpler proof of the minimum Hamming distance of such families of codes. If A is square and NSC, C ⊥ can be described using C 1⊥, …,C M ⊥ and a transformation of A. This yields d(C ⊥). Finally we show that an NSC matrix-product code is a generalized concatenated code.
- Kristine Lally
-
![Patrick Fitzpatrick]()
We use Gröbner bases of modules as a tool in the construction and classification of quasicyclic codes. Whereas previous studies have been mainly concerned with the 1-generator case, our results elucidate the structure of arbitrary quasicyclic codes and their duals. As an application we provide a complete characterisation of self-dual quasicyclic codes of index 2.
- Ferruh Özbudak
- Henning Stichtenoth
. We present a simple construction of long linear codes from shorter ones. Our approach is related to the product code construction; it generalizes and simplifies substantially the recent "Propagation Rule" by Niederreiter and Xing. Many optimal codes can be produced by our method.
- Harald Niederreiter
-
![Chaoping Xing]()
. We establish a general theorem which, given an arbitrary linear code, generates a family of linear codes of larger lengths and higher dimensions. The proof is based on a representation of the given linear code as a (generalized) algebraic-geometry code. Examples yielding many optimal linear codes document the power of this theorem.
- Bram van Asch
T. Blackmore and G. H. Norton [Appl. Algebra Eng. Commun. Comput. 12, 477–500 (2001; Zbl 1004.94034)] introduced the notion of matrix-product codes over finite fields. The present paper provides a generalization to finite chain rings. For codes a distance function is defined using a homogeneous weight function in the ring. It is proved that the minimum distance of a matrix-product codes is determined by the minimum distances of the separate codes. At the end of the paper we focus on Galois rings and define a special family of matrix-product codes.
-
![Edgar Martínez-Moro]()
Niederreiter and Xing (2000) recently proposed a propagation rule for linear codes.Özbudak and Stichtenoth showed that the Niederreiter-Xing construction is a particular construction of a matrix-product code. Cheng, Cheng, and Sun analyzed the case when Niederreiter-Xing rule commutes with duality. The aim of this correspondence is to generalize the propagation rule to a wider class of codes and analyze the case when it commutes with duality.
- Tadao Kasami
It is shown that there exist arbitrarily long quasi-cyclic (2k,k) binary codes that meet a bound slightly weaker than the Gilbert-Varshamov bound. This is a refinement of the result of Chen, Peterson, and Weldon [1].
The Theory of Error-Correcting Codes, ser. North-Holland Mathematical Library
- F J Macwilliams
- N J A Sloane
- F.J. Macwilliams
Macwilliams, F.J.; Sloane N.J.A.; The Theory of Error-Correcting Codes, ser. North-Holland mathematical library. North-Holland, 1977, vol. 16.
Source: https://www.researchgate.net/publication/220537695_Construction_and_decoding_of_matrix-product_codes_from_nested_codes
Posted by: alfredoalfredoanhorne0268725.blogspot.com
