Issue |
Wuhan Univ. J. Nat. Sci.
Volume 28, Number 1, February 2023
|
|
---|---|---|
Page(s) | 15 - 19 | |
DOI | https://doi.org/10.1051/wujns/2023281015 | |
Published online | 17 March 2023 |
Mathematics
CLC number: O 236.2
On Deep Holes of Projective Reed-Solomon Codes over Finite Fields with Even Characteristic
School of Big Data and Statistics, Sichuan Tourism University, Chengdu 610100, Sichuan, China
Received:
14
July
2022
Projective Reed-Solomon code is an important class of maximal distance separable codes in reliable communication and deep holes play important roles in its decoding. In this paper, we obtain two classes of deep holes of projective Reed-Solomon codes over finite fields with even characteristic. That is, let be finite field with even characteristic,
, and let
be the Lagrange interpolation polynomial of the first
components of the received vector
. Suppose that the
-th component of
is 0, and
,
where
, and
is a polynomial over
with degree no more than
. Then the received vector
is a deep hole of projective Reed-Solomon codes
. In fact, our result partially solved an open problem on deep holes of projective Reed-Solomon codes proposed by Wan in 2020.
Key words: finite field / even characteristic / projective Reed-Solomon code / deep hole
Biography: XU Xiaofan, male, Ph. D., research direction: coding theory. E-mail: xxfsctu@163.com
Fundation item: Supported by Foundation of Sichuan Tourism University (20SCTUTY01) and Initial Scientific Research Fund of Doctors in Sichuan Tourism University
© Wuhan University 2023
This is an Open Access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
0 Introduction
In 1960, Reed and Solomon[1] presented an important error correcting code, that is the so-called Reed-Solomon code. In 1987, Dur[2] defined a double extended Reed-Solomon code, which was later called projective Reed-Solomon code. He further studied the covering radius, decoding problem and the deep holes of projective Reed-Solomon codes in Refs.[3-5].
Now, we first recall the following definition of projective Reed-Solomon codes.
Definition 1[2]Let be a finite field and let
. Then the projective Reed-Solomon codes of length
with dimension
over
can defined as
where is the coefficient of
in
.
Subsequently, we give the definition of deep holes of linear code . To do this, for a received vector
, we first define the error distance
and the covering radius
of linear code
.
Definition 2[5] Let be an
linear code over
. The error distance of a received vector
to code
is defined by
where is the Hamming distance of
and
.
Clearly, if and only if
.
For a given projective Reed-Solomon code we define the Lagrange interpolation polynomial
of the first
components of received vector
by
Obviously, one has for
and further
if and only if
Definition 3 [5]Let be an
linear code over
. Then
is called as the covering radius of .
In fact, there is a well known conjecture on the covering radius of projective Reed-Solomon codes.
Conjecture 1[6] Let be an integer with
Suppose
, then
otherwise,
Now we can propose the definition of deep holes of linear code as follows.
Definition 4 [7] Let be a
linear code over
. If the received vector
such that
, then
is called a deep hole of
.
In 2016, Zhang et al[8] proved that is a deep hole of projective Reed-Solomon codes
by solving the subset problem over finite field
, where
,
, and
is a polynomial over
with degree no more than
. Then, in 2017, Kaipa [9] studied the deep holes of projective Reed-Solomon codes
over
with odd characteristic. In 2018, Xu et al[10] proved that
is a deep hole of
, where
with
and
being a polynomial over
whose degree not exceed
. In 2020, Zhang et al[6] completely determined all the deep holes of projective Reed-Solomon codes
by using the polynomial theory over finite fields and applying the finite geometry method. Meanwhile, they raised the following open problem.
Problem 1[6] For a given projective Reed-Solomon code , how to determine all its deep holes?
More results on deep holes of Reed-Solomon codes, one can see Refs.[11-15].
The main purpose of this paper is to study problem 1 over finite fields with even characteristic. Now, we describe the main theorem of this paper as following.
Theorem 1 Let be finite field with even characteristic,
. Let
be the Lagrange interpolation polynomial of the first
components of the received vector
. Suppose that the
-th component of
is 0, and
or
where , and
is a polynomial over
with degree no more than
. Then the received vector
is a deep hole of
.
Actually, Theorem 1 partially solved Problem 1 raised by Ref.[6]. This paper is organized as follows. In Section 1, we supply some preliminary lemmas that are needed in the proof of Theorem 1. Then in Section 2, we present the proof of Theorem 1.
1 Preliminary Lemmas
In this section, we give some lemmas needed in the proof of Theorem 1. First, a formula of a special determinant over finite fields given as follows.
Lemma 1 Let .Then
Proof Noticed that
Then, one can immediately get Lemma 1 by comparing the coefficients of on both sides of the above equality. This completes the proof of Lemma 1.
Next, we prove the following result on subset sum over finite fields with even characteristic.
Lemma 2 Let be finite field with even characteristic. If
, then the sum of any
different elements in
is nonzero.
Proof The Lemma 2 obviously holds when . Put
Now we give the proof for
, respectively.
Case 1. . Without loss of generality, one can take two distinct elements of
as
. Since
is a finite filed with characteristic 2, hence one can get
Case 2. . Without loss of generality, one can also choose
distinct elements of
as
. Notice that
is a finite filed with characteristic 2, therefore
and also , thus
Case 3. . Without loss of generality, one can pick
distinct elements
. The character of
is 2 can tell us that
The proof of Lemma 2 is complete.
In 1991, Dur[3] had given the following result on covering radius of projective Reed-Solomon codes over finite fields with even characteristic by using the finite geometry method.
Lemma 3[3]Let ,
. Then
Finally, we recall a theorem on the received vector is whether or not a deep hole of maximal distance separable code
.
Lemma 4[16] Let be
maximal distance separable code over finite field
. If the covering radius
of code
is
, then the received vector
is a deep hole of
if and only if any
columns of the
matrix
is linearly independent, where
is the generator matrix of code
.
2 Proof of Theorem 1
In this section, we use the lemmas presented in Section 1 to give the proof of Theorem 1.
Proof Let . By (1) and (2), one can immediately get that
Assume that are any
columns of
where
are arbitrary
integers with
To complete the proof of the Theorem, it suffices to show
To do so, we give the proof as the following eight cases.
Case 1. . The four cases are considered as follows.
Case 1-1. . At this time, one has
Case 1-2. . By
, one can know that
Case 1-3. . One can deduce that
And also , it follows from Lemma 2 that
Then one can derive that
Case 1-4. . By
, one can derive that
Notice that , by Lemma 2, one can get
. It follows that
Case 2.. One only need to deal with the four cases as follows.
Case 2-1. . Notice that for any integer
with
, one has
. It then follows that
Case 2-2. . Since
and
, so
Then by Lemma 1, one can derive that
Now note that and
. Then Lemma 2 can tell us that
This implies
Case 2-3. Since
one then can deduce that
Case 2-4. Owing to
and
one then can get
By Lemma 1, one can deduce that
Notice that and
. Applying Lemma 2, one can obtain
It yields that
Thus, (3) can be immediately obtained from (4)-(11), that is, any columns of
are linearly independent. On the other hand,
is a maximal distance separable code and Lemma 3 also tell us that the covering radius of
is
Therefore, by Lemma 4, one can know that is a deep hole of projective Reed-Solomon codes
. This finish the proof of Theorem 1.
References
- Reed S, Solomon G. Polynomial codes over certain finite fields[J]. Journal of the Society for Industrial and Applied Mathematics, 1960, 8(2): 300-304. [CrossRef] [MathSciNet] [Google Scholar]
- Dur A. The automorphism groups of Reed-Solomon codes[J]. J Combin Theory, Ser A, 1987, 44(1): 69-82. [CrossRef] [MathSciNet] [Google Scholar]
- Dur A. The decoding of extended Reed-Solomon codes[J]. Discrete Math, 1991, 90(1): 21-40. [CrossRef] [MathSciNet] [Google Scholar]
- Dur A. Complete decoding of doubly-extended Reed-Solomon codes of minimum distance 5 and 6[J]. Discrete Appl Math, 1991, 33(1/2/3): 95-107. [CrossRef] [MathSciNet] [Google Scholar]
- Dur A. On the covering radius of Reed-Solomon codes[J]. Discrete Math, 1994, 126(1/2/3): 99-105. [CrossRef] [MathSciNet] [Google Scholar]
- Zhang J, Wan D Q, Kaipa K. Deep holes of projective Reed-Solomon codes[J]. IEEE Trans Inform Theory, 2020, 66(4): 2392-2401. [CrossRef] [MathSciNet] [Google Scholar]
- Cheng Q, Murray E. On deciding deep holes of Reed-Solomon codes[J]. Lecture Notes in Comput Sci, 2007, 4484: 296-305. [CrossRef] [Google Scholar]
- Zhang J, Wan D Q. On deep holes of projective Reed-Solomon codes[C]//2016 IEEE International Symposium Information Theory. Washington D C: IEEE, 2016: 925-929. [Google Scholar]
- Kaipa K. Deep holes and MDS extensions of Reed-Solomon codes[J]. IEEE Trans Inform Theory, 2017, 63(8): 4940-4948. [CrossRef] [MathSciNet] [Google Scholar]
- Xu X F, Hong S F, Xu Y C. On deep holes of primitive projective Reed-Solomon codes[J]. Sci Sin Math, 2018, 48(8): 1087-1094. [CrossRef] [Google Scholar]
- Hong S F, Wu R J. On deep holes of generalized Reed-Solomon codes[J]. AIMS Math, 2016, 1(2): 96-101. [CrossRef] [Google Scholar]
- Keti M, Wan D. Deep holes in Reed-Solomon codes based on Dickson polynomials[J]. Finite Fields Appl, 2016, 40: 110-125. [CrossRef] [MathSciNet] [Google Scholar]
- Li Y J, Wan D Q. On error distance of Reed-Solomon codes[J]. Sci China Ser A, 2008, 51(11): 1982-1988. [CrossRef] [MathSciNet] [Google Scholar]
- Li Y J, Zhu G Z. On the error distance of extended Reed-Solomon codes[J]. Adv Math Commun, 2016, 10(2): 413-427. [CrossRef] [MathSciNet] [Google Scholar]
- Wu R J, Hong S F. On deep holes of standard Reed-Solomon codes[J]. Science China Math, 2012, 55(12): 2447-2455. [NASA ADS] [CrossRef] [MathSciNet] [Google Scholar]
- Zhuang J C, Cheng Q, Li J Y. On determing deep holes of generalized Reed-Solomon codes[J]. IEEE Trans Inform Theory, 2016, 62(1): 199-207. [CrossRef] [MathSciNet] [Google Scholar]
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.