Distance Distribution to Received Words in Reed-Solomon Codes

Abstract: Let

m a t h b b 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) i n m a t h b b F_{q} [x]

of degree

k + m

and a non-negative integer

r

, count the number of polynomials

g (x) i n m a t h b b F_{q} [x]

of degree at most

k - 1

such that

f (x) + g (x)

has exactly

r

roots in

m a t h b b 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}

.

This page was built for publication: Distance Distribution to Received Words in Reed-Solomon Codes