Distance Distribution to Received Words in Reed-Solomon Codes

Abstract

Let ${\mathbb{F}}_q$ be the finite field of $q$ elements. In this paper we obtain bounds on the following counting problem: given a polynomial $f(x)\in {\mathbb{F}}_q[x]$ of degree $k+m$ and a non-negative integer $r$, count the number of polynomials $g(x)\in {\mathbb{F}}_q[x]$ of degree at most $k-1$ such that $f(x)+g(x)$ has exactly $r$ roots in ${\mathbb{F}}_q$. Previously, explicit formulas were known only for the cases $m=0,1,2$. As an application, we obtain an asymptotic formula on the list size of the standard Reed-Solomon code $[q,k,q-k+1{]}_q$.

15 pages

References in corpus (1)

• Maximum-likelihood decoding of Reed-Solomon Codes is NP-hard