Advances in Mathematics of Communications
Volume xx, No. 0x, 20xx, xxx-xxx

doi:xxx

arXiv:1705.09859v1 [cs.IT] 27 May 2017

ON SHORTENED AND PUNCTURED CYCLIC CODES

Arti Yardi∗
IRIT/INP-ENSEEIHT, University of Toulouse
Toulouse, France

Ruud Pellikaan
Department of Mathematics and Computer Science
Eindhoven University of Technology
P.O. Box 513, 5600 MB Eindhoven, The Netherlands

(Communicated by xxx)
Abstract. The problem of identifying whether the family of cyclic codes is
asymptotically good or not is a long-standing open problem in the field of
coding theory. It is known in the literature that some families of cyclic codes
such as BCH codes and Reed-Solomon codes are asymptotically bad, however
in general the answer to this question is not known. A recent result by Nelson
and Van Zwam shows that, all linear codes can be obtained by a sequence of
puncturing and/or shortening of a collection of asymptotically good codes [1].
In this paper, we prove that any linear code can be obtained by a sequence of
puncturing and/or shortening of some cyclic code. Therefore the result that
all codes can be obtained by shortening and/or puncturing cyclic codes leaves
the possibility open that cyclic codes are asymptotically good.

1. Introduction
A family of codes is called as asymptotically good if it contains an infinite sequence
of codes such that both the rate and the ratio of minimum distance to length of
every code in this sequence is bounded away from zero [2, Ch. 9]. The problem
of identifying asymptotically good families of codes have been well studied in the
literature [3–9]. Justesen codes, AG codes, and Expander codes are some examples
of the known families of asymptotically good codes. While the family of BCH codes
is known to be asymptotically bad [5], some families of quasi-cyclic codes have been
identified as asymptotically good [9]. However, whether the family of cyclic codes is
asymptotically good or not is a long-standing open problem in the literature [10,11].
This problem of identifying whether cyclic codes are asymptotically good or not
was first addressed by Assmus, Mattson, and Turyn [10]. Since then this problem
has been studied by various researchers [5,6,12–14]. Lin and Weldon proved that the
family of BCH codes is asymptotically bad [5]. Berlekamp and Justesen constructed
a family of cyclic codes that performs better than BCH codes, however this family
also turned out to be asymptotically bad [6]. Berman provided a necessary condition
for the sequence of cyclic codes to be asymptotically good [12]. He proved that the
necessary condition for the sequence of cyclic codes to be asymptotically good is
that the number of distinct prime factors of the lengths of cyclic codes should
2010 Mathematics Subject Classification: Primary: 94C99; Secondary: 94B27, 94B60.
Key words and phrases: Coding theory, cyclic codes xxxx.
∗ Corresponding author.
225

c 20xx AIMS

226

Arti Yardi and Ruud Pellikaan

tend to infinity. Martı́nez-Pérez and Willems have also provided similar necessary
conditions for cyclic codes to be asymptotically good and provided some classes
of cyclic codes that were also identified as asymptotically bad [14]. Castagnoli
et al. showed that if there exists an asymptotically good sequence of cyclic codes
(simple-root or repeated-root), then an asymptotically good sequence of simple-root
cyclic codes can also be identified [13].
While the existing literature provides a sequence of asymptotically bad cyclic
codes, the possibility of existence of a good sequence of cyclic codes cannot be denied. A recent result by Nelson and Van Zwam shows that all linear codes can be
obtained by a sequence of puncturing and/or shortening of a collection of asymptotically good codes [1]. This result provides a necessary condition for a given class
of codes to be asymptotically good. One can use this result to give an independent
proof of the fact that graphic and co-graphic codes are not asymptotically good as
shown by Kashyap [15]. In this paper, we prove that the class of cyclic codes satisfy
this necessary condition, i.e., any linear code can be obtained by a sequence of puncturing and/or shortening of some cyclic code. Therefore the result that all codes
can be obtained by shortening and puncturing cyclic codes leaves the possibility
open that cyclic codes are asymptotically good.
The remaining paper is organized as follows. In Section 2, we provide some
notation and preliminaries required in the paper. The main result of the paper is
provided in Section 3, followed by some concluding remarks in Section 4.
2. Notation and preliminaries
The finite field with q elements is denoted by Fq and the polynomial ring with
coefficients from Fq is denoted by Fq [X]. Without loss of generality, we consider any
vector as a row vector and use boldface letters to indicate vectors. The components
of a vector are indicated by lowercase letters. For example, a vector v ∈ Fnq is


given by v = v0 v1 . . . vn−1 , where vi ∈ Fq is the ith component of v, for
i = 0, 1, . . . , n − 1. The polynomial representation of v is given by v(X) = v0 +
v1 X + v2 X 2 + . . . + vn−1 X n−1 . An all-zero vector of length n is denoted by 0n . The
collection of linear block codes of length n and dimension k is denoted by C(n, k)
and a linear block code in this collection in denoted by C. The cyclic code of length
n and generator polynomial g(X) ∈ Fq [X] is denoted by C(n, g). Throughout this
paper, we consider linear block codes that are defined over Fq .
We shall next recall the definition of puncturing and shortening operations on a
linear block code C.
Definition 2.1. Puncturing of a code [16, Ch. 1]: Let C be an [n, k] linear block
code over Fq and let L be the set of any l coordinate locations. Then the puncturing
operation on C at coordinate locations in the set L consists of deleting the entries
of every codeword in C at locations in the set L.
Definition 2.2. Shortening of a code [16, Ch. 1]: Let C and L be as defined in
Definition 2.1. Then the shortening operation on C at coordinate locations in the
set L consists of two steps. In the first step, consider the set W of codewords in
C that have zeros at the locations in the set L. In the second step, puncturing
operation is performed on W at coordinate locations in the set L.
Remark 2.3. It is known that the code obtained after the above mentioned puncturing and shortening operation is a linear block code of length n − l [16, Ch. 1].
Advances in Mathematics of Communications

Volume xx, No. x (20xx), xxx-xxx

On shortened and punctured cyclic codes

227

3. Main result
In this section, we provide the main result of the paper in the following theorem.
Theorem 3.1. Any Fq linear block code can be obtained by a sequence of puncturing
and/or shortening of some cyclic code.
Proof. Let C be any Fq linear block code of length n and dimension k. Let
{v1 , v2 , . . . , vk } be a basis of C. Using this basis, we now construct a cyclic code
such that by a sequence of puncturing and/or shortening of this cyclic code, it is
possible to obtain code C. Corresponding to {v1 , v2 , . . . , vk }, define a vector f as
follows
h
i
f := 1 [v1 0n ] [v2 0n ] [v3 0n ] · · · [vk−1 0n ] vk 1 ,
h
i
(1)
= f0 f1 f2 . . . fm ,
where m = 2n(k − 1) + n + 1 and f0 , f1 , . . . , fm are the components of f such
that f0 = fm = 1. Let f (X) be the polynomial corresponding to f . Let p be the
characteristic of the finite field Fq . Considering the coefficients of f (X), define a
vector g as follows
h
i
g := f0 0p−1 f1 0p−1 · · · 0p−1 fm−1 fm ,
(2)
where 0p−1 is an all-zero vector of length p − 1. Let g(X) be the polynomial
corresponding to g. It is given by,
g(X) :=

(3)

m−1
X

fi X pi + X [(m−1)p+1] .

i=0

′

The derivative g (X) of g(X) is given by,
(4)

g ′ (X) =

m−1
X
i=0

(5)



pfi X pi−1 + (m − 1)p + 1 X (m−1)p

= X (m−1)p ,

where the last equality is obtained since p = 0 in Fq . Since g(0) is not equal to
zero, it follows that the greatest common divisor of g(X) and g ′ (X) is equal to
one. This implies that g(X) does not have multiple zeros [17, Ch. 1, Thm. 1.86].
Furthermore there exists an extension Fqe of Fq such that all zeros of g(X) are
non-zero elements of this finite extension, where e is some positive integer. Hence
g(X) divides X N − 1 where N = q e − 1 and gcd(N, q) = 1. Let n′ be the shortest
′
integer such that g(X) divides X n − 1, gcd(n′ , q) = 1, and 2(n′ − deg(g)) ≥ n′ .
′
Note that if g(X) has multiple zeros, it will never divide X n − 1 for some integer
′
′
n such that gcd(n , q) = 1 [17]. The necessity of the condition 2(n′ − deg(g)) ≥ n′
will be explained later in the proof. From (1) we have fm = 1 and this implies
that g(X) is a monic polynomial. It is known that g(X) that satisfies the above
mentioned conditions generates the cyclic code C(n′ , g) of length n′ [16, Ch. 4]. Let
k ′ = n′ − deg(g) be the dimension of C(n′ , g). The condition 2(n′ − deg(g)) ≥ n′
implies that 2(n′ − deg(g)) = 2k ′ ≥ n′ , i.e., the rate of the code C(n′ , g) is greater
than or equal to 1/2. We next prove that C(n′ , g) is the required cyclic code of the
proof.
Advances in Mathematics of Communications

Volume xx, No. x (20xx), xxx-xxx

228

Arti Yardi and Ruud Pellikaan

Let G be a generator matrix of C(n′ , g). In order to perform a sequence of
puncturing and/or shortening operations on C(n′ , g), we will first write the rows of
G in a convenient form. The first row g0 of G can be given by,
i
h
(6)
g0 := f0 0p−1 f1 0p−1 · · · 0p−1 fm−1 fm 0k′ −1 .
The ith row gi of G can be obtained by considering i right cyclic shifts of g0 [18],
i.e., gi is given by,
i
h
(7)
gi := 0i f0 0p−1 f1 0p−1 · · · 0p−1 fm−1 fm 0k′ −1−i ,

where i = 0, 1, . . . , k ′ − 1. The condition 2k ′ ≥ n′ implies that k ′ ≥ n′ − k ′ = deg(g).
Recall that deg(g) = (m − 1)p + 1 and this implies that k ′ − 1 ≥ (m − 1)p. Thus
the condition 2k ′ ≥ n′ ensures that G has at least (m − 1)p rows. The generator
matrix G can now be written as
(8)


 
g0
f0

  .
.

  .
..

  .

 
 gp   0

 

  .
..

 =  ..
.

 
g
 
 (m−1)p   0

 
.

  ..
..

  .
0
gk′ −1

0p−1

f1

0p−1

f0
..
.
·
..
.
·

·

·

0p−1
..
.
0p−1

·

·

·

fm−1
..
.
fm−2
..
.
f0

·

·

·

·

fm
..
.
0
0
..
.
·

0p−2
..
.
0p−2
..
.
0p−2

·

0
..
.

·

·

·

fm−1

fm
..
.
·

0

·

fm

·
..

·

·

·

f1

.


0
.. 

. 

0 

.. 
,
. 


0 

.. 
. 
fm

where the coordinate location of the coefficient fm−1 in row g0 is same as that of
the coordinate location of the coefficient fm−i−1 in row gip , for i = 1, 2, . . . , m − 1,
which is indicated using the two vertical dashed lines. The code C can now be
obtained by a sequence of puncturing and/or shortening of C(n′ , g) in the following
five steps.


A] Shortening of C(n′ , g) at coordinate locations in the range (j − 1)p + 2, jp , for
j = 1, 2, . . . , m − 1
We first choose j = 1 and shorten C(n′ , g) in the range [2, p]. Let W1 be the
vector space spanned by the rows g0 and gp , gp+1 , . . . , gk′ −1 , i.e., the first row of G
and all the rows after gp of G in (8). The vectors in W1 have zeros in the coordinate
location range [2, p]. We now prove that the set of codewords in C(n′ , g) that have
zeros in this range is exactly the vector space W1 . Consider the matrix formed by
the rows g0 , g1 , . . . , gp of G, i.e., the initial p + 1 rows of G as follows,

 

g0
f0 0
· · · · · 0 f1 0
· · · · · 0
 g1   0 f 0 0 · · · · 0 0 f 1 · · · · · 0 

 


 

..
..
..
(9)  ...  =  ...
,
.
.
.

 

 gp−1   0
·
· · · · 0 f0 0
·
· · · · · 0 
gp
0
·
· · · · · 0 f0 ·
· · · · · 0

where the coordinate location range between the two vertical dashed lines in (9) is
[2, p]. Recall that f0 = 1 (see (1)). From (8) and (9) this implies that a non-zero
codeword in C(n′ , g) that is a linear combination of the rows g1 , g2 , . . . , gp−1 , will
have at least one non-zero coordinate in the range [2, p]. Thus the set of codewords
in C(n′ , g) that have zeros in the range [2, p] is exactly the vector space W1 .
We will now shorten C(n′ , g) in the range [2, p]. In the first step of shortening, we
will get subspace W1 (see Definition 2.2). In the second step, puncturing operation
Advances in Mathematics of Communications

Volume xx, No. x (20xx), xxx-xxx

On shortened and punctured cyclic codes

229

will be performed in the coordinate location range [2, p] of W1 . A generator matrix
G′1 of the code obtained by shortening C(n′ , g) in this range is given by,
(10)


f0
0

 ..
 .
G′1 = 
0

 .
 ..
0

f1
f0

0p−1
0p−1
..
.

· ·
· ·

fm−1
fm−2
..
.

fm
0
..
.

0p−2
0p−2

·

·

· ·

f0

0
..
.

0p−2

·

·

· ·

·

·

·

0
fm−1

·
fm
..
.

·
0

·
·

·
·

f1

·

·

fm
..
.

·

·

·

·
·

0
0
..
.

0 ·

0
..
.

·

·



fm





.





Observe that shortening of C(n′ , g) in the coordinate location range [2, p] eliminated the rows g1 , g2 , . . . , gp−1 of G. Thus the number of rows of G′1 is equal to
′
k ′ − (p − 1).
 Using similararguments it can be proved that shortening of C(n , g) in
the range (j − 1)p + 2, jp will eliminate the rows g(j−1)p+1 , g(j−1)p+2 , . . . , gjp−1 of
G for j = 1, 2, . . . , m − 1. A generator matrix G1 of the code obtained by shortening
in these sets is given by,
(11)







G1 = 





f0
0
..
.
0
.
..
0

f1
f0
..
.
·
.
..
·

f2
f1

·
·

·
·

·

·

·

fm−1
fm−2
..
.
f0

·

·

·

·

fm
0
..
.
0
.
..
·

0p−2
0p−2

0
fm−1

0p−2

f1

·

·
fm
..
.
·

·
·

·
·

·
..

fm

·
·
..
.
·

·

·

·

·

.


0
0 




 =:
0 




fm


h0
 h1 


 . 
 . 
 . 
,

hm−1 


 . 
 .. 
hk1



 

where k1 = k ′ − 1 − (m − 1)(p − 1) and h0 , h1 , . . . , hk1 are defined as the rows
of G1 . Let C1 be the linear block code generated by G1 defined in (11).
B] Shortening of C1 at the last k ′ − 1 − [2np(k − 1)] locations
From (11) we have k1 ≥ m − 1. Substituting the value of m = 2n(k − 1) + n + 1
we get k1 ≥ 2n(k − 1) + n, which implies that k1 > 2n(k − 1). Thus the condition
k1 ≥ m − 1 ensures that G1 has at least 2n(k − 1) rows. In order to perform this
shortening operation, we first write the generator matrix G1 in a convenient form.
We substitute the value of the vector [f0 f1 . . . fm−1 ] = [1 v1 0n v2 0n · · · 0n vk ]
from (1) and form a matrix using the rows h0 and h2n of G1 as follows,

(12)



h0
h2n



=



[1 v1 0n ] v2
[02n 1] v1

· ·
vk
· · vk−1

fm
0

0
·

· ·
· fm

· · · 0
0 · · 0



.

From (12), it can be seen that the coordinate location of the vector vk in h0 and
the location of the vector vk−1 in h2n is the same, which is indicated using the
two vertical dashed lines. In general, the coordinate location of vk−j in h2nj will
be same as that of the location of vk in h0 , for j = 1, 2, . . . , k − 1. Using this the
Advances in Mathematics of Communications

Volume xx, No. x (20xx), xxx-xxx

230

Arti Yardi and Ruud Pellikaan

generator matrix G1 can be written as
(13)



h0


.


..




h2n




..




.

=
 h

 2n(k−1) 


h
 2n(k−1)+1 


.


..


hk1

[1 v1 0n ]

.

..


 [02n 1]


..

.

 0
 2n+1

 02n+1

.

..

02n+1


v2
.
..
v1
..
.
0n
0n
.
..
0n

·

·

·

·

·
·

·
·

·

·

0

fm

vk
.
..
vk−1
..
.
v1
·
.
..
·

·

·

·

·

·

·

·

·

·

fm

0
fm

·
0

·
·

..

·

·

·
·

·
·

·

.
fm
..
.
·
·
.
..
·

·

·
·

..
·

·

·

·

.


0
. 
.. 


0 

.. 
. 
.
0 


0 

. 
.. 
fm

Note that the row h2n(k−1) of G1 corresponds to the row g2np(k−1) of G. From
(7) this implies that the number of columns on the right hand side the vertical
dashed line in (13) is equal to k ′ − 1 − [2np(k − 1)]. Using similar arguments as in
step A], it can be shown that the shortening of C1 in the last k ′ − 1 − [2np(k − 1)]
locations will provide a code with generator matrix G2 given by


(14)

[1 v1 0n ] v2

..
..

.
.

[0
1]
v
G2 = 
2n
1


..
..

.
.
02n+1
0n

· ·

fm

0

0
..
.

0

·

· · vk−1
..
.

·

·

·

fm
..
.

0

· ·

·

·

·

·

·

vk
..
.

v1


0
.. 
. 

· · 0 
.
.. 
. 
· · fm
· ·

Let C2 be the linear block code generated by G2 defined in (14).
C] Puncturing of C2 at the locations other than the initial m columns
Comparing (11) and (14), the number of columns on the left hand side of the
vertical dashed line in (14) is equal to m. Thus the generator matrix G3 of the code
obtained after this puncturing operation is given by,


(15)



[1 v1 0n ] [v2 0n ] · ·
vk

..
..
..

.
.
.

G3 = 
 [02n 1] [v1 0n ] · · vk−1

..
..
..

.
.
.
02n+1
02n
· ·
v1









 =: 







b0
..
.
b2n
..
.
b2n(k−1)






,




where b0 , b1 , . . . , b2n(k−1) are defined as the rows of G3 . Suppose the codeword vj
is given by
(16)


vj = 0lj

wj

0rj



where 0lj and 0rj are all-zero vectors of lengths lj and rj respectively and wj is the
vector obtained by puncturing the initial lj and the last rj entries of vj such that
the first and the last entry of wj are not zero, for j = 1, 2, . . . , k. Let d1 , d2 , . . . , dk
be the lengths of w1 , w2 , . . . , wk respectively, i.e., lj + dj + rj = n. Without loss
of generality we assume that r1 ≤ r2 ≤ . . . ≤ rk . Substituting the value of vj , the
Advances in Mathematics of Communications

Volume xx, No. x (20xx), xxx-xxx

On shortened and punctured cyclic codes

231

generator matrix G3 can be written as
(17)


b0
..
.




 b2n

 b2n+1


..

.
b2n(k−1)





1 0 l1
  ..
  .
 
  0 0 l1
=
  0 0 l1
 
  .
  ..

w1
..
.

0 0 l1

0 r1

0n−1

0d 1
0d 1
..
.

0 r1
0 r1

0n−1
0n−1

0d 1

0 r1

0n−1



0
..
.

0 l2 w 2 0 r 2





· ·



1  0 l1 w 1 0 r 1  · ·
0 1 0l1 w1 0r1 −1 · ·
..
..
.
.
0
0n
· ·

·

vk
..
.

· vk−1
·
·
..
.
·

v1







,





where the number of coefficients between the two vertical dashed lies in (17) is equal
to n. Let C3 be the linear block code generated by G3 .

D] Shortening
of the code C3 at coordinate locations in the range (2j − 1)n + 1 −

r1 , 2jn , for j = 1, 2, . . . , k − 1


We first choose j = 1 and shorten C3 in the range n + 1 − r1 , 2n . Let W2 be
the vector space spanned by the rows b0 and b2n , b2n+1 , . . . , b2n(k−1) , of G3 , i.e.,
the first row of G3 and all the rows after b2n in (17). A generator matrix of W2 is
given by
(18)


b0
b2n
b2n+1
..
.





1 0 l1
0 0 l1
0 0 l1
..
.

w1
0d 1
0d 1
..
.

0 r1
0 r1
0 r1

0n−1
0n−1
0n−1


0
 0 l2
1  0 l1
0 1 0 l1
..
.


w2 0 r 2 
· ·
w1 0 r 1  · ·
w1 0r1 −1 · ·
..
.

·
vk
· vk−1
·
·
..
.




 


 


 

,
=


 


 

b2n(k−1)
0n
· · ·
v1
0 0l1 0d1 0r1 0n−1 0


where the range n + 1 − r1 , 2n is indicated by the two vertical dashed lines. It can
be seen that every vector in W2 has zeros in this range. We next prove that the set
of codewords in C3 that has zeros in this range is exactly the vector space W2 .
Suppose [0l1 w1 ] = [w1 w2 . . . wd ], where d = l1 + d1 . Using this the matrix
formed by the rows b0 , b1 , . . . , b2n of G3 , i.e., the initial 2n + 1 rows of G3 is as
follows,
(19)

 
b0
1
 b1   0

 
 .  .
 ..   ..

 

 
 bd   0

=
 bd+1   0

 
 .  .
 ..   ..

 
b
 0
2n−1
b2n
0

w1
1

·
·

wd
·

0
wd

·
0

·
·

·
·

·
·

·
·

·
·

0
0

0
0

[0l2 w2 0r2 ]
··

·
·

wd
·
..
.
·
·

0
wd

·
0

·
·

0
0

0
0

··
··

·
·

·
·

·
·

·
·

1
0

·
1

··
[0l1 w1 0r1 ]

·
·

..

·
·

·
·

1
·

w1
1

.
·
w1

·
·

·
·

·
·

·
·

·
·

·
·

·
·


vk
· 

.. 
. 


· 
.
· 

.. 
. 

· 
vk−1



where the range n + 1 − r1 , 2n is indicated by the two vertical dashed lines. Since
wd is not equal to zero (see (16)), it can be seen that a non-zero codeword in C3 that
is a linear combination
of the rows b1 , b2 , . . . , bd , will have at least one non-zero

entry in the range d + 2, 2d + 2 ⊆ n + 1 − r1 , 2n . Further, a non-zero codeword in
C3 that is a linear combination of the rows bd+1 , bd+2 , . . . , b2n−1 , will have at least
one non-zero entry in the range n + 1 − r1 , 2n . Therefore the set of codewords in
C3 that have zeros in the range n + 1 − r1 , 2n is exactly the vector space W2 .

Advances in Mathematics of Communications

Volume xx, No. x (20xx), xxx-xxx

232

Arti Yardi and Ruud Pellikaan

 Using stepssimilar to step A], it can be shown that shortening of C3 in the range
n + 1 − r1 , 2n will eliminate the rows b1 , b2 , . . . , b2n−1 of G3 , i.e., when j = 1, the
rows of G3 between
b0 to b2n were eliminated.
We next prove that shortening of


C3 in the range (2j − 1)n + 1 − r1 , 2jn , the rows of G3 between b2n(j−1) to b2jn
will get eliminated, for j = 1, 2, . . . , k − 1. The generator matrix G3 with a focus
on these rows is given by
(20)



b0


.


.
.






b2n




..


.




 b2n(j−2) 


..




.
=


 b
 2n(j−1) 


b
 2n(j−1)+1 


..




.




b
2nj




.


..


b2n(k−1)

1
.
.
.

0

.
.
.

0

.
 ..


0

0

.
 ..

0


 ..
.
0


[0lj wj 0rj ]
..
.
[0lj−1 wj−1 0rj−1 ]
..
.
[0l2 w2 0r2 ]
..
.
[0l1 w1 0r1 ]
[1 0l1 w1 0r1 −1 ]
..
.
··
..
.
··

·

·

·

·
·

·

·

0n−1

0

0n−1

0

0n−1

0

0n−1
0n−1

0
0

0n−1

1

·

·

[0lj+1 wj+1 0rj+1 ]
..
.
[0lj wj 0rj ]
..
.
[0l3 w3 0r3 ]
..
.
[0l2 w2 0r2 ]
[0 0l2 w2 0r2 −1 ]
..
.
[0l1 w1 0r1 ]
..
.
·

·

·

·

·

·

·

·
·

·
·

·

·

·

·


vk

.. 
. 

vk−1 

.. 

. 

· 

.. 
. 
.

· 

· 

.. 
. 

vk−j 


.. 
. 
v1

Observe that the structure of the rows b2n(j−1) , b2n(j−1)+1 , . . . , b2nj of the matrix
in (20) is the same as that of the rows b0 , b1 , . . . , b2n the matrix G3 in (17). Further,
since r1 ≤ r2 ≤ . . . ≤ rk , it can be seen that the vector space spanned by the rows
b
 0 , b2n , . . . , b2n(j−1) and
 the all the rows after row b2n(j−1) have zeros in the range
(2j − 1)n + 1 − r1 , 2jn . Using similar arguments as that of the case when j = 1 it
can be proved that shortening in this range will eliminate the rows of G3 between
b2n(j−1) to b2jn . A generator matrix G4 of the code obtained after the above
mentioned set of shortening operations is given by
(21)




G4 = 


b0
b2n
..
.
b2n(k−1)





 
 
=
 

1 0 l1
0 0 l1
..
.
0

w1
0d 1
..
.

0
1

·

·

·



0l2 w2 0r2−r1
0 l1 w 1
..
.
·



·
·

· ·
vk
· · vk−1
..
.

·

· ·

v1





.


Let C4 be the code corresponding to the generator matrix G4 in (21).
E] Puncturing of C4 at the coordinate locations other than the last n locations
The puncturing operation in this range will delete the columns of G4 that are on
the left hand side of the vertical dashed line in (21). A generator matrix G5 of the
code obtained by this puncturing operation is given by,


vk
 vk−1 


G3 =  .  .
(22)
 .. 
v1

Observe that, G5 is a generator matrix of the required linear block code C of the
theorem and this completes the proof.
Advances in Mathematics of Communications

Volume xx, No. x (20xx), xxx-xxx

On shortened and punctured cyclic codes

233

4. Conclusion
In this paper, we proved that any linear block code can be obtained by a sequence of puncturing and/or shortening of some cyclic code. While the result is in
itself interesting, due to the recent result given by Nelson and Vam Zwam [1], our
result may have applications in studying the long-standing open problem of deciding whether the family of cyclic codes is asymptotically good or not. The result
given by Nelson and Vam Zwam says that, given a family of asymptotically good
codes, any linear block code can be obtained by a sequence of puncturing and/or
shortening of some code in this family. Our result essentially proves that the family
of cyclic codes satisfies this condition.
Acknowledgments
The first author is supported by ANR-11-LABEX-0040-CIMI within the program
ANR-11-IDEX-0002-02 of the Centre International de Mathématiques et Informatique de Toulouse, France. The first author would also like to acknowledge the
support of the Bharti Centre for Communication at IIT Bombay, India.
References
[1] P. Nelson and S. H. M. van Zwam, On the existence of asymptotically good linear codes in
minor-closed classes, in IEEE Transactions on Information Theory, 61 (2015), 1153-1158.
[2] F. MacWilliams and N. Sloane, The Theory of Error Correcting Codes, Amsterdam,
Netherlands:North-Holland Publishing Company, (1977).
[3] J. Justesen, Class of constructive asymptotically good algebraic codes, in IEEE Transactions
on Information Theory, 18 (1972), 652–656.
[4] J. Justesen, New convolutional code constructions and a class of asymptotically good timevarying codes, in IEEE Transactions on Information Theory, 19 (1973), 220–225.
[5] S. Lin and E. J. W. Jr., Long BCH codes are bad, in Information and Control, 11 (1976),
445–451.
[6] E. Berlekamp and J. Justesen, Some long cyclic linear binary codes are not so bad, in IEEE
Transactions on Information Theory, 20 (1974), 351–356.
[7] N. Alon, J. Bruck, J. Naor, M. Naor, and R. M. Roth, Construction of asymptotically good
low-rate error-correcting codes through pseudo-random graphs, in IEEE Transactions on
Information Theory, 38 (1992), 509–516.
[8] L. J. Schulman and D. Zuckerman, Asymptotically good codes correcting insertions, deletions,
and transpositions, in IEEE Transactions on Information Theory, 45 (1999), 2552–2557.
[9] S. Ling and P. Solé, Good self-dual quasi-cyclic codes exist, in IEEE Transactions on Information Theory, 49 (2003), 1052–1053.
[10] E. Assmus Jr, H. Mattson Jr, and R. Turyn, Cyclic codes, in Air Force Cambridge Research
Labs, Bedford, Massachusetts, Scientific report, CRL-65-332 (1965).
[11] P. Charpin, Open problems on cyclic codes, in Handbook of Coding Theory, 1 (1998), 969–
1063.
[12] S. D. Berman, Semisimple cyclic and abelian codes II, in Cybernetics, 3 (1967), 17–23.
[13] G. Castagnoli, J. L. Massey, P. A. Schoeller, and N. von Seemann, On repeated-root cyclic
codes, in IEEE Transactions on Information Theory, 37 (1991), 337–342.
[14] C. Martı́nez-Pérez and W. Willems, Is the class of cyclic codes asymptotically good? in IEEE
Transactions on Information Theory, 52 (2006), 696–700.
[15] N. Kashyap, A decomposition theory for binary linear codes, in IEEE Transactions on Information Theory, 54 (2008), 3035–3058.
[16] W. Huffman and V. Pless, Fundamentals of Error-Correcting Codes, Cambridge, United
Kingdom: Cambridge University Press, (2003).
[17] R. Lidl and H. Niederreiter, Introduction to Finite Fields and Their Applications Cambridge,
United Kingdom: Cambridge University Press, (1986).
[18] S. Lin and D. Costello, Error Control Coding, 2nd ed, Englewood Cliffs, New Jersey, USA:
Prentice-Hall, (2004).
Advances in Mathematics of Communications

Volume xx, No. x (20xx), xxx-xxx

234

Arti Yardi and Ruud Pellikaan

Received for publication xxx.
E-mail address: artidilip.yardi@irit.fr
E-mail address: g.r.pellikaan@tue.nl

Advances in Mathematics of Communications

Volume xx, No. x (20xx), xxx-xxx

