IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 61, NO. 5, MAY 2015 2351
The Bose and Minimum Distance of a
Class of BCH Codes
Cunsheng Ding, Senior Member, IEEE, Xiaoni Du, and Zhengchun Zhou
Abstract—Cyclic codes are an interesting class of linear
codes due to their efficient encoding and decoding algorithms.
Bose-Ray-Chaudhuri-Hocquenghem (BCH) codes form a sub-
class of cyclic codes and are very important in both theory
and practice as they have good error-correcting capability and
are widely used in communication systems, storage devices, and
consumer electronics. However, the dimension and minimum
distance of BCH codes are not known in general. The objective
of this paper is to determine the Bose and minimum distances
of a class of narrow-sense primitive BCH codes.
Index Terms— BCH codes, cyclic codes, linear codes.
I. INTRODUCTION
T
HROUGHOUT this paper, let p be a prime and let
q be a power of p.An[n, k, d] code C over GF(q) is a
k-dimensional subspace of GF(q)
n
with minimum (Hamming)
distance d.
A linear [n, k] code C over GF(q) is called cyclic if
(c
0
, c
1
, ···, c
n−1
) ∈ C implies (c
n−1
, c
0
, c
1
, ···, c
n−2
) ∈ C.
By identifying any vector (c
0
, c
1
, ···, c
n−1
) ∈ GF(q)
n
with
c
0
+ c
1
x + c
2
x
2
+···+c
n−1
x
n−1
∈ GF(q)[x]/(x
n
− 1),
any code C of length n over GF(q) corresponds to a subset of
the quotient ring GF(q)[x]/(x
n
−1). A linear code C is cyclic
if and only if the corresponding subset in GF(q)[x]/(x
n
− 1)
is an ideal of the ring GF(q)[x]/(x
n
− 1).
Note that every ideal of GF(q)[x]/(x
n
− 1) is principal.
Let C =g(x) be a cyclic code, where g(x) is monic and
has the smallest degree among all the generators of C.Then
g(x) is unique and called the generator polynomial, and
h(x) = (x
n
− 1)/g(x) is referred to as the parity-check
polynomial of C.
Let m ≥ 1 be a positive integer and let n = q
m
− 1. Let
α be a generator of GF(q
m
)
∗
.Foranyi with 1 ≤ i ≤ q
m
−2,
Manuscript received May 9, 2014; revised October 19, 2014; accepted
February 6, 2015. Date of publication March 9, 2015; date of current version
April 17, 2015. C. Ding’s work was supported by the Research Grants
Council, University Grants Committee, Hong Kong, under Project 601013.
X. Du’s work was supported by the National Natural Science Foundation
of China under Project 61202395 and Project 61462077 and in part
by the Program for New Century Excellent Talents in University under
Grant NCET-12-0620. Z. Zhou’s work was supported in part by the Natural
Science Foundation of China under Project 61201243 and in part
by the Sichuan Provincial Youth Science and Technology Fund under
Grant 2015JQO004.
C. Ding is with the Department of Computer Science and Engineering,
The Hong Kong University of Science and Technology, Hong Kong (e-mail:
cding@ust.hk).
X. Du is with the College of Mathematics and Statistics, Northwest Normal
University, Lanzhou 730070, China (e-mail: ymldxn@126.com).
Z. Zhou is with the School of Mathematics, Southwest Jiaotong University,
Chengdu, 610031, China (e-mail: zzc@home.swjtu.edu.cn).
Communicated by J. Lahtonen, Associate Editor for Coding Theory.
Digital Object Identifier 10.1109/TIT.2015.2409838
let m
i
(x) denote the minimal polynomial of α
i
over GF(q).
For any 2 ≤ δ<n = q
m
− 1, define
g
(q, m,δ)
(x) = lcm(m
1
(x), m
2
(x), ···, m
δ−1
(x)),
where lcm denotes the least common multiple of these
minimal polynomials. Let C
(q, m,δ)
denote the cyclic code
of length n with generator polynomial g
(q, m,δ)
(x).This
code C
(q, m,δ)
is called the narrow-sense primitive Bose-Ray-
Chaudhuri-Hocquenghem (BCH) code with design distance δ.
It is well known that the codes C
(q, m,δ)
and C
(q, m,δ
)
may be
equal for two different δ and δ
. The largest design distance
of a BCH code is called the Bose distance of the code and is
denoted by d
B
.
The codes C
(q, m,δ)
are treated in every book on coding
theory. However, the following questions about the codes
C
(q, m,δ)
are still open in general.
1) What is the dimension of C
(q, m,δ)
?
2) What is the Bose distance (i.e., the maximum design
distance) of C
(q, m,δ)
?
3) What is the minimum distance d (i.e., the minimum
weight) of C
(q, m,δ)
?
The dimension of C
(q, m,δ)
is known when δ is small, and
is open in general. There are lower bounds on the dimension
of C
(q, m,δ)
, which are very bad in many cases. The minimum
distance d of C
(q, m,δ)
is known only in a few cases. Only
when δ is very small or when C
(q, m,δ)
is the Reed-Solomon
code, both the dimension and minimum distance of C
(q, m,δ)
are known. Hence, we have very limited knowledge of the
narrow-sense primitive BCH codes, not to mention BCH codes
in general. Thus we conclude that BCH codes are neither
well-understood nor well-studied.
In the 1990’s, there were a few papers on narrow-sense
primitive BCH codes [1], [2], [5], [12]. However, in the last
eighteen years, little progress on the study of these codes has
been made. As pointed out by Charpin in [6], it is a well-
known hard problem to determine the minimum distance of
narrow-sense BCH codes.
The objective of this paper is to determine the Bose distance
and the minimum distance of the codes C
(q, m,δ)
with design
distance δ = q
t
+ h,where1≤ t ≤ m − 2and0≤ h ≤
(q
t
− 1)/q
m−t
+1.
II. K
NOWN RESULTS ABOUT THE CODES C
(q, m,δ)
To give a well-rounded treatment of the codes C
(q, m,δ)
,
we summarize known results on the dimension and minimum
distance of the codes in this section.
0018-9448 © 2015 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission.
See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.
资源评论
