A Root-Finding Algorithm for List Decoding of Reed–Muller Codes
Xin-Wen Wu, Margreta Kuijper, Udaya Parampalli · IEEE Transactions on Information Theory · 2005
Let F/sub q/[X/sub 1/,...,X/sub m/] denote the set of polynomials over F/sub q/ in m variables, and F/sub q/[X/sub 1/,...,X/sub m/]/sub /spl les/u/ denote the subset that consists of the polynomials of total degree at most u. Let H(T) be a nontrivial polynomial in T with coefficients in F/sub q/[X/sub 1/,...,X/sub m/]. A crucial step in interpolation-based list decoding of q-ary Reed-Muller (RM) codes is finding the roots of H(T) in F/sub q/[X/sub 1/,...,X/sub m/]/sub /spl les/u/. In this correspondence, we present an efficient root-finding algorithm, which finds all the roots of H(T) in F/sub q/[X/sub 1/,...,X/sub m/]/sub /spl les/u/. The algorithm can be used to speed up the list decoding of RM codes.