| 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.