EDP Sciences logo
Submit your paper
Search
Menu
All issues Volume 28 / No 1 (February 2023) Wuhan Univ. J. Nat. Sci., 28 1 (2023) 15-19 Full HTML
Open Access
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

© Wuhan University 2023

Licence Creative CommonsThis 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

(1)

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

(2)

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

(3)

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

(4)

Case 1-2. . By , one can know that

(5)

Case 1-3. . One can deduce that

And also , it follows from Lemma 2 that Then one can derive that

(6)

Case 1-4. . By , one can derive that

Notice that , by Lemma 2, one can get . It follows that

(7)

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

(8)

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

(9)

Case 2-3. Since one then can deduce that

(10)

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

(11)

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

  1. ReedS, SolomonG. Polynomial codes over certain finite fields[J]. Journal of the Society for Industrial and Applied Mathematics, 1960, 8(2): 300-304. [Google Scholar]
  2. DurA. The automorphism groups of Reed-Solomon codes[J]. J Combin Theory, Ser A, 1987, 44(1): 69-82. [CrossRef] [MathSciNet] [Google Scholar]
  3. DurA. The decoding of extended Reed-Solomon codes[J]. Discrete Math, 1991, 90(1): 21-40. [CrossRef] [MathSciNet] [Google Scholar]
  4. DurA. 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. [Google Scholar]
  5. DurA. On the covering radius of Reed-Solomon codes[J]. Discrete Math, 1994, 126(1/2/3): 99-105. [Google Scholar]
  6. ZhangJ, WanD Q, KaipaK. Deep holes of projective Reed-Solomon codes[J]. IEEE Trans Inform Theory, 2020, 66(4): 2392-2401. [CrossRef] [MathSciNet] [Google Scholar]
  7. ChengQ, MurrayE. On deciding deep holes of Reed-Solomon codes[J]. Lecture Notes in Comput Sci, 2007, 4484: 296-305. [Google Scholar]
  8. ZhangJ, WanD 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]
  9. KaipaK. Deep holes and MDS extensions of Reed-Solomon codes[J]. IEEE Trans Inform Theory, 2017, 63(8): 4940-4948. [CrossRef] [MathSciNet] [Google Scholar]
  10. XuX F, HongS F, XuY C. On deep holes of primitive projective Reed-Solomon codes[J]. Sci Sin Math, 2018, 48(8): 1087-1094. [Google Scholar]
  11. HongS F, WuR J. On deep holes of generalized Reed-Solomon codes[J]. AIMS Math, 2016, 1(2): 96-101. [CrossRef] [Google Scholar]
  12. KetiM, WanD. Deep holes in Reed-Solomon codes based on Dickson polynomials[J]. Finite Fields Appl, 2016, 40: 110-125. [CrossRef] [MathSciNet] [Google Scholar]
  13. LiY J, WanD Q. On error distance of Reed-Solomon codes[J]. Sci China Ser A, 2008, 51(11): 1982-1988. [Google Scholar]
  14. LiY J, ZhuG Z. On the error distance of extended Reed-Solomon codes[J]. Adv Math Commun, 2016, 10(2): 413-427. [CrossRef] [MathSciNet] [Google Scholar]
  15. WuR J, HongS F. On deep holes of standard Reed-Solomon codes[J]. Science China Math, 2012, 55(12): 2447-2455. [Google Scholar]
  16. ZhuangJ C, ChengQ, LiJ 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.