Some results on ordinary words of standard Reed-Solomon codes

1.   Introduction

Let ${\mathbb F}_q$ be the finite field of $q$ elements with characteristic $p$. Let $D = \{x_1, \cdots, x_n\}$ be a subset of ${\mathbb F}_q$, which is called the evaluation set. The generalized Reed-Solomon code $RS_q(D, k)$ of length $n$ and dimension $k$ over ${\mathbb F}_q$ is defined as follows:

If $D = {\mathbb F}_q^*$, then it is called standard Reed-Solomon code, i.e.,

where $\alpha$ is a primitive element of ${\mathbb F}_q$. We refer the above definition as the polynomial code version of the standard Reed-Solomon code. If $D = {\mathbb F}_q$, then it is called the extended Reed-Solomon code. For any $[n, k]_q$ linear code $C$, the minimum distance $d(C)$ is defined by

where $d(\cdot, \cdot)$ denotes the Hamming distance of two words which is the number of different entries of them and $w(\cdot)$ denotes the Hamming weight of a word which is the number of its non-zero entries. Since the Reed-Solomon code is a linear code, we have

The error distance to code $C$ of a received word ${\bf u}\in {\mathbb F}_q^n$ is defined by

Clearly, $d({\bf u}, C) = 0$ if and only if ${\bf u}\in C$. The most important algorithmic problem in coding theory is the maximum likelihood decoding (MLD): Given a received word ${\bf u}\in{\mathbb F}_q^n$, find a codeword ${\bf v}\in C$ such that $d({\bf u}, {\bf v}) = d({\bf u}, C)$, then we decode ${\bf u}$ to ${\bf v}$ ^[4]. Therefore, it is very crucial to decide $d({\bf u}, C)$ for the word ${\bf u}$. When decoding the generalized Reed-Solomon code $RS_q(D, k)$, for a received word ${\bf u} = (u_1, \cdots, u_n)\in {\mathbb F}_q^n$, we define the Lagrange interpolation polynomial $u(x)$ of ${\bf u}$ by

i.e., $u(x)$ is the unique polynomial of degree $\deg(u(x))\le n-1$ such that $u(x_i) = u_i$ for $1\leq i\leq n$. For ${\bf u}\in{\mathbb F}_q^n$, we define the degree of $u(x)$ to be the degree of ${\bf u}$, i.e., $\deg({\bf u}): = \deg(u(x))$. It is clear that ${\bf u}\in RS_q(D, k)$ if and only if $d({\bf u}, RS_q(D, k)) = 0$ if and only if $\deg({\bf u})\leq {k-1}$. Equivalently, ${\bf u}\not\in RS_q(D, k)$ if and only if $d({\bf u}, RS_q(D, k))\ge 1$ if and only if $k\le \deg({\bf u})\le n-1$. Evidently, we have the following simple bounds due to Li and Wan ^[3].

Theorem 1.1. ^[3] Let ${\bf u}$ be a received word such that ${\bf u}\not\in RS_q(D, k)$. Then

Let ${\bf u}\in {\mathbb F}_q^n$. If $d({\bf u}, RS_q(D, k)) = n-k$, then the received word ${\bf u}$ is called a deep hole of $RS_q(D, k)$. In 2007, Cheng and Murray ^[1] conjectured that a word ${\bf u}$ is a deep hole of $RS_q({\mathbb F}^*_q, k)$ if and only if $u(x) = ax^k+f_{\leq{k-1}}(x)$, where $u(x)$ is the Lagrange interpolation polynomial of the received word ${\bf u}$ and $a\in{\mathbb F}_q^*$. In 2012, Wu and Hong ^[9] disproved this conjecture by presenting a new class of deep holes for standard Reed-Solomon codes $RS_q({\mathbb F}_q^*, k)$. In fact, let $q\geq 4$ and $2\leq k\leq q-2$. They showed that the received word ${\bf u}$ is a deep hole if its Lagrange interpolation polynomial equals $ax^{q-2} +f_{\leq{k-1}}(x)$. Later on, the main result of ^[9] is extended to the generalized Reed-Solomon code in ^[2]. Recently, some progress on deep holes of generalized projective Reed-Solomon codes are made in ^[10] and ^[11].

On the other hand, the received word ${\bf u}$ is called an ordinary word of $RS_q(D, k)$ if $d({\bf u}, RS_q(D, k)) = n-\deg(u(x))$. If $\deg({\bf u}) = k$, then the upper bound is equal to the lower bound which implies that ${\bf u}$ is a deep hole and also an ordinary word. This immediately gives $(q-1)q^k$ ordinary words. We call these trivial ordinary words. It is an interesting problem to determine all the ordinary words. In 2008, Li and Wan ^[3] proposed an open problem to determine all the ordinary words of the standard Reed-Solomon code. In ^[4], by using Weil's estimate on character sums, the following result is obtained.

Theorem 1.2. ^[4] Let ${\bf u}\in {\mathbb F}_q^q$ be such that $k+1\leq \deg({\bf u})\leq q-1$. Assume that $q > \max((\deg ({\bf u}))^2, (\deg({\bf u})-k-1)^{2+{ilon}_{\varepsilon}})$ and $k > (\frac{4}{{ilon}_{\varepsilon}}+1)(\deg({\bf u})-k)+\frac{4}{{ilon}_{\varepsilon}}+2$ for some constant ${ilon}_{\varepsilon} > 0$. Then ${\bf u}$ is an ordinary word of extended Reed-Solomon code $RS_q({\mathbb F}_q, k)$.

Furthermore, using Weil's character sum estimate and Li-Wan sieve for distinct coordinates counting, Zhu and Wan ^[12] showed the following result.

Theorem 1.3. ^[12] Let ${\bf u}\in {\mathbb F}_q^q$ be such that $k+1\leq \deg({\bf u})\leq q-1$. If there are positive constants $c_1$ and $c_2$ such that $\deg({\bf u})-k < c_1q^{1/2}, (\deg({\bf u})-k + 1) \log_2 q < k < c_2q$, then ${\bf u}$ is an ordinary word of extended Reed-Solomon code $RS_q({\mathbb F}_q, k)$.

In ^[5], Li and Zhu proved the following result.

Theorem 1.4. ^[5] Let $3\leq k + 2 \leq q-1$, and ${\bf u}\in {\mathbb F}_q^q$ be represented by polynomial $u(x) = x^{k+2}-bx^{k+1} + cx^k + v(x)$ with $\deg v(x)\leq k-1$. If $k+2 = q-1$ and $b^2 = c$, then ${\bf u}$ is an ordinary word of extended Reed-Solomon code $RS_q({\mathbb F}_q, k)$.

In this paper, we make use of a well-known result, i.e. the so-called König-Rados theorem, to find all the ordinary words of degree $q-2$ of standard Reed-Solomon code $RS_q({\mathbb F}_q^*, k)$. The main result of this paper can be stated as follows.

Theorem 1.5.Let $q\geq 4, 2\leq{k}\leq{q-2}$ and ${\bf u}\in{\mathbb F}_q^{q-1}$ be a received word with $u(x)$ being its Lagrange interpolation polynomial and $\deg u(x) = {q-2}$. Then ${\bf u}$ is an ordinary word of $RS_q ({\mathbb F}_q^*, k)$ if and only if $u(x)$ is of the following form

with $a, \lambda\in{\mathbb F}_q^*$ and $f_{\leq k-1}(x)\in {\mathbb F}_q[x]$ being of degree at most $k-1$.

If one picks $k = q-2$, then the ordinary words given by Theorem 1.5 are just the trivial ones. From Theorem 1.5, the following interesting result follows immediately.

Proposition 1.6. Let $q\geq 4, 2\leq{k}\leq{q-2}$. Then the number of ordinary words of degree $q-2$ of the standard Reed-Solomon code $RS_q ({\mathbb F}_q^*, k)$ is equal to $(q-1)^2q^k$.

This paper is organized as follows. First, in Section 2, we show several preliminary lemmas that are needed in the proof of Theorem 1.5. Consequently, we show Theorem 1.5 in Section 3. Finally, we present two examples to illustrate the validity of our main result.

2.   Auxiliary lemmas

In this section, our main goal is to prove several lemmas that are needed in the proof of Theorem 1.5. In what follows, we let

and

where $\alpha$ is a primitive element of ${\mathbb F}_q$. We begin with the following lemma.

Lemma 2.1. Let ${\bf u}, {\bf v}\in {\mathbb F}_q^{q-1}$ be two words. If ${\bf u} = \lambda {\bf v}+f_{\leq k-1}({\mathbb F}_q^*)$, where $\lambda\in {\mathbb F}_q^*$ and $f_{\leq k-1}(x)\in {\mathbb F}_q[x]$ is a polynomial of degree at most $k-1$. Then each of the following is true:

(ⅰ). We have $d({\bf u}, RS_q({\mathbb F}_q^*, k)) = d({\bf v}, RS_q({\mathbb F}_q^*, k))$.

(ⅱ). The word ${\bf u}$ is an ordinary word of $RS_q({\mathbb F}_q^*, k)$ if and only if the word ${\bf v}$ is an ordinary word of $RS_q({\mathbb F}_q^*, k)$.

Proof. (ⅰ). Since $RS_q({\mathbb F}_q^*, k)$ is a linear code, we obtain that

as desired.

(ⅱ). Since ${\bf u} = \lambda {\bf v}+f_{\leq k-1}({\mathbb F}_q^*)$, one has $\deg {\bf u} = \deg {\bf v}$. Hence ${\bf u}$ is an ordinary word of $RS_q({\mathbb F}_q^*, k)$ if and only if

if and only if

But part (ⅰ) tells us that $d({\bf u}, RS_q({\mathbb F}_q^*, k)) = d({\bf v}, RS_q({\mathbb F}_q^*, k))$. So (2.1) holds if and only if

So ${\bf u}$ is ordinary holds if and only if (2.2) is true. In other words, ${\bf u}$ is ordinary if and only if ${\bf v}$ is ordinary.

This completes the proof of Lemma 2.1.

Consequently, we give another useful fact.

Lemma 2.2. Let ${\bf u}\in {\mathbb F}_q^{q-1}$ be a received word and $u(x)$ be its Lagrange interpolation polynomial. Then one has

Proof. By (1.1), we have

as required.

The proof of Lemma 2.2 is complete.

The following result gives a formula on the number of nonzero solutions of polynomial equation over finite fields and is due to König and Rados (see, for instance, ^[6,7,8]). It is a key and important ingredient in the proof of our main result.

Lemma 2.3. (König-Rados) (^[6,7,8]) Let $f(x) = a_0+a_1x+\cdots+a_{q-2}x^{q-2}\in{\mathbb F}_q[x].$ Then the number of nonzero solution of equation $f(x) = 0$ in ${\mathbb F}_q$ is equal to $q-1-{\rm rank}(A)$, where $A$ is the left $(q-1)\times (q-1)$ circulant matrix defined by

3.   Proof of Theorem 1.5

In this section, we use the lemmas presented in the previous section to give the proof of Theorem 1.5.

Proof of Theorem 1.5. First of all, we show the sufficiency part. Let

where $a$ and $\lambda\in{\mathbb F}_q^*$, $f_{\leq k-1}(x)\in {\mathbb F}_q[x]$ is a polynomial of degree at most $k-1$. Define

Then $u(x) = \lambda u_k(x)+f_{\leq k-1}(x).$ Now we pick a primitive element $\alpha$ of ${\mathbb F}_q$ and let

By Lemma 2.1, one gets that

Therefore, in order to show that

is an ordinary word, it suffices to prove that ${\bf u}_k$ is an ordinary word. Equivalently, we need only to show that

since $\deg u_k(x) = q-2$. This will be done in what follows.

By Lemma 2.2, we have

For any $v(x)\in P_{k-1}$, one has $\deg {v(x)}\leq {k-1}$. But $\deg u_k(x) = q-2 \geq {k}.$ Hence

It then follows that for any ${v(x)\in P_{k-1}}$, one has

On the other hand, we take

Then $v_0(x)\in P_{k-1}$. Furthermore, by (3.1) we have

Since

and $a\in {\mathbb F}_q^*$ implying that

it then follows that

This infers that

from which one can derive that

So (3.4) together with (3.5) and (3.6) implies that

Hence (3.2) follows immediately from (3.3) and (3.7). So ${\bf u}$ is an ordinary word of $RS_q ({\mathbb F}_q^*, k)$. This finishes the proof of the sufficiency part.

Now we turn our attention to the proof of the necessity part. Let ${\bf u}$ be an ordinary word of $RS_q({\mathbb F}_q^*, k)$ and $\deg u(x) = q-2$. Then by the definition of ordinary word, we have

Hence by Lemma 2.2, one has

Notice that for any ${v(x)\in P_{k-1}}$, one has

So there is a polynomial $v_0(x)\in P_{k-1}$ such that

Write

and

Let $u_{q-2} = \lambda$. Since deg$u(x) = q-2$, one has $\lambda\in{\mathbb F}_q^*$. Then

with $c_i = \lambda^{-1}u_i$ for all integers $i$ with $k\leq i\leq{q-2}$ and $c_i = \lambda^{-1}(u_i-v_i)$ for all integers $i$ with $0\leq i\leq{k-1}$. One then deduces that

On the other hand, Lemma 2.3 yields that

where $B$ is the left circulant matrix defined by

So from (3.8) and (3.9), we derive that ${\rm rank}(B) = 1$. Since $c_{q-2} = \lambda^{-1}\lambda = 1,$ one has

Assume that $c_{q-3} = 0$. Then $B$ holds a nonzero minor of order 2, and so one gets that rank$(B)\ge 2$, which is impossible. Hence we must have $c_{q-3}\ne 0$. In the following, we let $c_{q-3} = a$. Then $a\in{\mathbb F}_q^*$. For each integer $i$ with $1\le i\le q-1$, let ${\bf r}_i$ denote the $i$-th row of the matrix $B$. Then rank$({\bf r}_i) = 1$ for each integer $i$ with $1\le i\le q-1$. Since rank($B$) = 1, there exists an element $a\in {\mathbb F}^*_q$ such that ${\bf r}_1 = a{\bf r}_2$. Then we deduce that $c_{q-2} = ac_0$ and $c_k = ac_{k+1}$ for $0\le k\le q-3$. Since $c_{q-2} = 1$, one has $a = c_{q-3}, c_0 = a^{-1} = a^{q-2}$ and $c_k = a^{-1}c_{k-1}$ for $1\le k\le q-2$. It then follows that $c_k = a^{q-2-k}$ for $0\le k\le q-2$. This implies that

Therefore

where

So the necessity part is proved.

This concludes the proof of Theorem 1.5

4.   Examples and final remarks

In this last section, we supply two examples to demonstrate the validity of Theorem 1.5.

Example 4.1. Let $q = 7, n = q-1 = 6, k = 3$. Putting $\alpha = 3$ gives us the standard Reed-Solomon code

Using the MATLAB 2011a programming, we search for the ordinary word and find out all the ordinary words of degree $q-2 = 5$ of standard Reed-Solomon code $RS_7 ({\mathbb F}_7^*, 3)$ that are listed in Table 1. By (1.2), we can get the Lagrange interpolation polynomial $u(x)$ of the ordinary word $u$ of degree 5 of $RS_7 ({\mathbb F}_7^*, 3)$ listed also in Table 1. This coincides with Theorem 1.5.

Suppose that ${\bf u}$ is an ordinary word of degree $5$ of $RS_7 ({\mathbb F}_7^*, 3)$. Then

On the other hand, one has

So it is sufficient to find a codeword $v$ in $RS_7({\mathbb F}_7^*, 3)$ such that $d({\bf u}, {\bf v}) = 1$. For the received ordinary word ${\bf u} = \lambda(3, 1, 0, 6, 0, 4)+{\bf f}$ of degree 5, by (1.2) we compute and get that $u(x) = \lambda\sum\limits_{i = 3}^{5}x^i+f(x)$. Furthermore, one can search and find the word ${\bf v} = \lambda(4, 1, 0, 6, 0, 4)+{\bf f}\in RS_7({\mathbb F}_7^*, 3)$ such that $d({\bf u}, {\bf v}) = 1$. For the other ordinary words ${\bf u}$ of degree 5, one can also find the corresponding codewords ${\bf v}$ such that $d({\bf u}, {\bf v}) = 1$. We can easily compute the Lagrange interpolation polynomial $v(x)$ of ${\bf v}$ also listed in Table 1.

Example 4.2. Let $q = 11, n = q-1 = 10, k = 5$. Putting $\alpha = 2$ gives us the standard Reed-Solomon code

Using the MATLAB 2011a programming, we search for the ordinary word and find out all the ordinary words of degree $q-2 = 9$ of standard Reed-Solomon code $RS_{11} ({\mathbb F}_{11}^*, 5)$ that are listed in Table 2. By (1.2), one can easily calculate the Lagrange interpolation polynomial $u(x)$ of the ordinary word ${\bf u}$ of degree 9 of $RS_{11} ({\mathbb F}_{11}^*, 5)$ listed also in Table 2. This coincides with Theorem 1.5.

Suppose that ${\bf u}$ is an ordinary word of degree $9$ of $RS_{11} ({\mathbb F}_{11}^*, 5)$. Then

On the other hand, one has

So it is sufficient to find a codeword ${\bf v}$ in $RS_{11}({\mathbb F}_{11}^*, 5)$ such that $d({\bf u}, {\bf v}) = 1$. For the received ordinary word ${\bf u} = \lambda(5, 2, 0, 5, 0, 10, 0, 4, 0, 7)+{\bf f}$ of degree 9, by (1.2) we compute and get that $u(x) = \lambda\sum\limits_{i = 5}^{9}x^i+f(x)$. Furthermore, one can search and find the codeword ${\bf v} = \lambda(6, 2, 0, 5, 0, 10, 0, 4, 0, 7)+{\bf f}\in RS_{11}({\mathbb F}_{11}^*, 5)$ such that $d({\bf u}, {\bf v}) = 1$. For the other ordinary words $u$ of degree 9, one can also find the corresponding codewords $v$ such that $d({\bf u}, {\bf v}) = 1$. It is easy to compute the Lagrange interpolation polynomial $v(x)$ of ${\bf v}$ that is listed in Table 2.

Remark 4.3. In this paper, we determine all the ordinary words of maximal degree $q-2$ of the standard Reed-Solomon code $RS_q({\mathbb F}_q^*, k)$. In the close future, we will explore the ordinary words of degree no more than $q-3$ of the standard Reed-Solomon code $RS_q ({\mathbb F}_q^*, k)$.

Acknowledgments

The authors would like to thank the anonymous referees for their careful readings of the manuscript and helpful comments and suggestions that improved the presentation of the paper. This work was supported partially by National Science Foundation of China Grant # 11771304, by the Fundamental Research Funds for the Central Universities and by Foundation of Sichuan Tourism University under Grant # 19SCTUZZ01.

Conflict of interest

We declare that we have no conflict of interest.