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 ReedSolomon 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 ReedSolomon 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 ReedSolomon 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 ReedSolomon codes . In fact, our result partially solved an open problem on deep holes of projective ReedSolomon codes proposed by Wan in 2020.
Key words: finite field / even characteristic / projective ReedSolomon code / deep hole
Biography: XU Xiaofan, male, Ph. D., research direction: coding theory. Email: 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 socalled ReedSolomon code. In 1987, Dur^{[2] }defined a double extended ReedSolomon code, which was later called projective ReedSolomon code. He further studied the covering radius, decoding problem and the deep holes of projective ReedSolomon codes in Refs.[35].
Now, we first recall the following definition of projective ReedSolomon codes.
Definition 1^{[2]}Let be a finite field and let . Then the projective ReedSolomon 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 ReedSolomon 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 ReedSolomon 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 ReedSolomon 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 ReedSolomon 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 ReedSolomon 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 ReedSolomon code , how to determine all its deep holes?
More results on deep holes of ReedSolomon codes, one can see Refs.[1115].
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 ReedSolomon 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 11. . At this time, one has
Case 12. . By , one can know that
Case 13. . One can deduce that
And also , it follows from Lemma 2 that Then one can derive that
Case 14. . 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 21. . Notice that for any integer with , one has . It then follows that
Case 22. . 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 23. Since one then can deduce that
Case 24. 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 ReedSolomon 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): 300304. [CrossRef] [MathSciNet] [Google Scholar]
 Dur A. The automorphism groups of ReedSolomon codes[J]. J Combin Theory, Ser A, 1987, 44(1): 6982. [CrossRef] [MathSciNet] [Google Scholar]
 Dur A. The decoding of extended ReedSolomon codes[J]. Discrete Math, 1991, 90(1): 2140. [CrossRef] [MathSciNet] [Google Scholar]
 Dur A. Complete decoding of doublyextended ReedSolomon codes of minimum distance 5 and 6[J]. Discrete Appl Math, 1991, 33(1/2/3): 95107. [CrossRef] [MathSciNet] [Google Scholar]
 Dur A. On the covering radius of ReedSolomon codes[J]. Discrete Math, 1994, 126(1/2/3): 99105. [CrossRef] [MathSciNet] [Google Scholar]
 Zhang J, Wan D Q, Kaipa K. Deep holes of projective ReedSolomon codes[J]. IEEE Trans Inform Theory, 2020, 66(4): 23922401. [CrossRef] [MathSciNet] [Google Scholar]
 Cheng Q, Murray E. On deciding deep holes of ReedSolomon codes[J]. Lecture Notes in Comput Sci, 2007, 4484: 296305. [CrossRef] [Google Scholar]
 Zhang J, Wan D Q. On deep holes of projective ReedSolomon codes[C]//2016 IEEE International Symposium Information Theory. Washington D C: IEEE, 2016: 925929. [Google Scholar]
 Kaipa K. Deep holes and MDS extensions of ReedSolomon codes[J]. IEEE Trans Inform Theory, 2017, 63(8): 49404948. [CrossRef] [MathSciNet] [Google Scholar]
 Xu X F, Hong S F, Xu Y C. On deep holes of primitive projective ReedSolomon codes[J]. Sci Sin Math, 2018, 48(8): 10871094. [CrossRef] [Google Scholar]
 Hong S F, Wu R J. On deep holes of generalized ReedSolomon codes[J]. AIMS Math, 2016, 1(2): 96101. [CrossRef] [Google Scholar]
 Keti M, Wan D. Deep holes in ReedSolomon codes based on Dickson polynomials[J]. Finite Fields Appl, 2016, 40: 110125. [CrossRef] [MathSciNet] [Google Scholar]
 Li Y J, Wan D Q. On error distance of ReedSolomon codes[J]. Sci China Ser A, 2008, 51(11): 19821988. [CrossRef] [MathSciNet] [Google Scholar]
 Li Y J, Zhu G Z. On the error distance of extended ReedSolomon codes[J]. Adv Math Commun, 2016, 10(2): 413427. [CrossRef] [MathSciNet] [Google Scholar]
 Wu R J, Hong S F. On deep holes of standard ReedSolomon codes[J]. Science China Math, 2012, 55(12): 24472455. [NASA ADS] [CrossRef] [MathSciNet] [Google Scholar]
 Zhuang J C, Cheng Q, Li J Y. On determing deep holes of generalized ReedSolomon codes[J]. IEEE Trans Inform Theory, 2016, 62(1): 199207. [CrossRef] [MathSciNet] [Google Scholar]
Current usage metrics show cumulative count of Article Views (fulltext 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 4896 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.