Distance Distribution to Received Words in Reed-Solomon Codes

2018/06/01 by Jiyou Li, Daqing Wan, Li, Jiyou +1
Computer Science · Engineering · #Cellular Automata and Applications #Coding theory and cryptography #Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Number Theory (math.NT) #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.1806.00152

openalex publication_date 2018/06/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let \mathbbF_q be the finite field of q elements. In this paper we obtain bounds on the following counting problem: given a polynomial f(x)∈ \mathbbF_q[x] of degree k+m and a non-negative integer r, count the number of polynomials g(x)∈ \mathbbF_q[x] of degree at most k-1 such that f(x)+g(x) has exactly r roots in \mathbbF_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.

Related

• Improved error bounds for the distance distribution of Reed-Solomon codes
• Points-Polynomials Incidence Theorem with Applications to Coding Theory
• On error distance of received words with fixed degrees to Reed-Solomon code
• Polynomial evaluation over finite fields: new algorithms and complexity\n bounds
• On the List and Bounded Distance Decodibility of the Reed-Solomon Codes