Research article

Some results on deep holes of generalized projective Reed-Solomon codes

  • Received: 24 December 2018 Accepted: 11 February 2019 Published: 19 February 2019
  • MSC : 11C20, 11T71, 94B35, 94B65

  • Let $l\ge 1$ be an integer and $a_1, \ldots, a_l$ be arbitrarily given $l$ distinct elements of the finite field ${\bf F}_q$ of $q$ elements with the odd prime number $p$ as its characteristic. Let $D = {\bf F}_q\backslash\{a_1, \ldots, a_l\}$ and $k$ be an integer such that $2\le k\le q-l-1$. For any $f(x)\in {\bf F}_q[x]$, we let $f(D) = (f(y_1), \ldots, f(y_{q-l}))$ if $D = \{y_1, ..., y_{q-l}\}$ and $c_{k-1}(f(x))$ be the coefficient of $x^{k-1}$ of $f(x)$. In this paper, by using Dür's theorem on the relation between the covering radius and minimum distance of the generalized projective Reed-Solomon code ${\rm GPRS}_q(D, k)$, we show that if $u(x)\in {\bf F}_q[x]$ with $\deg u(x) = k$, then the received word $(u(D), c_{k-1}(u(x)))$ is a deep hole of ${\rm GPRS}_q(D, k)$ if and only if $\sum\limits_{y\in I}y\ne 0$ for any subset $I\subseteq D$ with $\#(I) = k$. We show also that if $j$ is an integer with $1\leq j\leq l$ and $u_j(x): = \lambda_j(x-a_j)^{q-2}+\nu_j x^{k-1}+f_{\leq k-2}^{(j)}(x)$ with $\lambda_j\in {\bf F}_q^*$, $\nu_j\in {\bf F}_q$ and $f_{\leq{k-2}}^{(j)}(x)\in{\bf F}_q[x]$ being a polynomial of degree at most $k-2$, then $(u_j(D), c_{k-1}(u_j(x)))$ is a deep hole of ${\rm GPRS}_q(D, k)$ if and only if $\binom{q-2}{k-1}(-a_j)^{q-1-k}\prod\limits_{y\in I}(a_j-y)+e\ne 0$ for any subset $I\subseteq D$ with $\#(I) = k$, where $e$ is the identity of ${\bf F}_q^*$. Furthermore, $(u({\bf F}_q^*), c_{k-1}(u(x)))$ is not a deep hole of the primitive projective Reed-Solomon code ${\rm PPRS}_q({\bf F}_q^*, k)$ if $\deg u(x) = k$, and $(u({\bf F}_q^*), \delta)$ is a deep hole of ${\rm PPRS}_q({\bf F}_q^*, k)$ if $u(x) = \lambda x^{q-2}+\delta x^{k-1}+f_{\leq{k-2}}(x)$ with $\lambda\in {\bf F}_q^*$ and $\delta\in {\bf F}_q$.

    Citation: Xiaofan Xu, Yongchao Xu. Some results on deep holes of generalized projective Reed-Solomon codes[J]. AIMS Mathematics, 2019, 4(2): 176-192. doi: 10.3934/math.2019.2.176

    Related Papers:

  • Let $l\ge 1$ be an integer and $a_1, \ldots, a_l$ be arbitrarily given $l$ distinct elements of the finite field ${\bf F}_q$ of $q$ elements with the odd prime number $p$ as its characteristic. Let $D = {\bf F}_q\backslash\{a_1, \ldots, a_l\}$ and $k$ be an integer such that $2\le k\le q-l-1$. For any $f(x)\in {\bf F}_q[x]$, we let $f(D) = (f(y_1), \ldots, f(y_{q-l}))$ if $D = \{y_1, ..., y_{q-l}\}$ and $c_{k-1}(f(x))$ be the coefficient of $x^{k-1}$ of $f(x)$. In this paper, by using Dür's theorem on the relation between the covering radius and minimum distance of the generalized projective Reed-Solomon code ${\rm GPRS}_q(D, k)$, we show that if $u(x)\in {\bf F}_q[x]$ with $\deg u(x) = k$, then the received word $(u(D), c_{k-1}(u(x)))$ is a deep hole of ${\rm GPRS}_q(D, k)$ if and only if $\sum\limits_{y\in I}y\ne 0$ for any subset $I\subseteq D$ with $\#(I) = k$. We show also that if $j$ is an integer with $1\leq j\leq l$ and $u_j(x): = \lambda_j(x-a_j)^{q-2}+\nu_j x^{k-1}+f_{\leq k-2}^{(j)}(x)$ with $\lambda_j\in {\bf F}_q^*$, $\nu_j\in {\bf F}_q$ and $f_{\leq{k-2}}^{(j)}(x)\in{\bf F}_q[x]$ being a polynomial of degree at most $k-2$, then $(u_j(D), c_{k-1}(u_j(x)))$ is a deep hole of ${\rm GPRS}_q(D, k)$ if and only if $\binom{q-2}{k-1}(-a_j)^{q-1-k}\prod\limits_{y\in I}(a_j-y)+e\ne 0$ for any subset $I\subseteq D$ with $\#(I) = k$, where $e$ is the identity of ${\bf F}_q^*$. Furthermore, $(u({\bf F}_q^*), c_{k-1}(u(x)))$ is not a deep hole of the primitive projective Reed-Solomon code ${\rm PPRS}_q({\bf F}_q^*, k)$ if $\deg u(x) = k$, and $(u({\bf F}_q^*), \delta)$ is a deep hole of ${\rm PPRS}_q({\bf F}_q^*, k)$ if $u(x) = \lambda x^{q-2}+\delta x^{k-1}+f_{\leq{k-2}}(x)$ with $\lambda\in {\bf F}_q^*$ and $\delta\in {\bf F}_q$.


    加载中


    [1] Y. Li, D. Wan, On error distance of Reed-Solomon codes, Sci. China, Ser. A: Math., 51 (2008), 1982-1988. doi: 10.1007/s11425-008-0066-3
    [2] V. Guruswami, M. Sudan, Improved decoding of Reed-Solomon and algebraic-geometry codes, IEEE Trans. Inform. Theory, 45 (1999), 1757-1767. doi: 10.1109/18.782097
    [3] V. Guruswami, A. Vardy, Maximum-likelihood decoding of Reed-Solomon codes is NP-hard, IEEE Trans. Inform. Theory, 51 (2005), 2249-2256. doi: 10.1109/TIT.2005.850102
    [4] A. Dür, The decoding of extended Reed-Solomon codes, Discrete Math., 90 (1991), 21-40. doi: 10.1016/0012-365X(91)90093-H
    [5] J. Li, D. Wan, On the subset sum problem over finite fields, Finite Fields Th. App., 14 (2008), 911-929. doi: 10.1016/j.ffa.2008.05.003
    [6] R. Wu, S. Hong, On deep holes of standard Reed-Solomon codes, Sci. China Math., 55 (2012), 2447-2455. doi: 10.1007/s11425-012-4499-3
    [7] S. Hong, R. Wu, On deep holes of generalized Reed-Solomon codes, AIMS Math., 1 (2016), 96-101. doi: 10.3934/Math.2016.2.96
    [8] J. Zhuang, D. Lin, C. Lv, Determining deep hole trees of generalized Reed-Solomon codes and an application (in Chinese), Sci. Sin. Math., 47 (2017), 1615-1620. doi: 10.1360/N012017-00014
    [9] J. Zhang, D. Wan, On deep holes of projective Reed-Solomon codes, 2016 IEEE Internal Symposium on Information Theory, (2016), 925-929.
    [10] X. Xu, S. Hong, Y. Xu, On deep holes of primitive projective Reed-Solomon codes (in Chinese), Sci. Sin. Math., 48 (2018), 1087-1094. doi: 10.1360/N012017-00064
    [11] J. Van lint, Introduction to coding theory, 3 Eds., Heidelberg: Springer-Verlag Berlin, 1998.
  • Reader Comments
  • © 2019 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Metrics

Article views(3517) PDF downloads(566) Cited by(2)

Article outline

Other Articles By Authors

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog