Generalized rational interpolation over commutative rings and remainder decoding

Abstract

We propose a new decoding procedure for Bose-Chaudhuri-Hocquenghem (BCH) and Reed-Solomon (RS) codes over Zm where m is a product of prime powers. Our method generalizes the remainder decoding technique for RS codes originally introduced by Welch and Berlekamp and retains its key feature of not requiring the prior evaluation of syndromes. It thus represents a significant departure from other algorithms that have been proposed for decoding linear block codes over integer residue rings. Our decoding procedure involves a Welch-Berlekamp (WB)-type algorithm for solving a generalized rational interpolation problem over a commutative ring R with identity. The solution to this problem includes as a special case, the solution to the WB key equation over R which is central to our decoding procedure. A remainder decoding approach for decoding cyclic codes over Zm up to the Hartmann-Tzeng bound is also presented.