Wu Y.,Link Media Devices Corporation
IEEE Transactions on Information Theory | Year: 2012
Chase decoding is a prevalent soft-decision decoding method for algebraic codes where an efficient bounded-distance decoder is available. Essentially, it repeatedly applies bounded-distance decoding upon combinatorially flipping certain least reliable bits (or patterns for nonbinary case). In this paper, we devise a one-pass Chase decoding algorithm of Reed-Solomon codes such that the desired error locator polynomial by flipping an error pattern is obtained in one pass (when operated in parallel) through utilizing the preceding results. This is effectively achieved through cumulative interpolation and linear-feedback-shift-register (LFSR) synthesis techniques. Furthermore, through converting the algorithm into the transform domain, exhaustive root search for each error locator polynomial is circumvented. Computationally, the new algorithm exhibits linear complexity $O(n)$, in attempting to determine a candidate codeword associated with each additionally flipped symbol/pattern; it compares favorably to quadratic complexity $O(nd)$ by straightforwardly utilizing hard-decision decoding, where $n$ and $d$ denote the code length and minimum distance, respectively. We also reveal a corrected algorithm for one-pass generalized minimum distance (GMD) decoding for Reed-Solomon codes from Koetter's original work. In addition, we devise a highly efficient one-pass Chase decoding algorithm for binary Bose-Chaudhuri-Hocquenghem (BCH) codes by taking advantage of a key characteristic of the Berlekamp algorithm. Finally, we present a systolic very large-scale integration (VLSI) decoder architecture through slightly compromising the proposed one-pass Chase decoding algorithm. It takes $O(1)$ clock cycles to complete one iteration by flipping one error pattern. Both circuit and memory complexities are dictated by the dimension of flipping patterns; in particular, they are independent of the code length $n$ or the minimum distance $d$ , rendering it highly attractive for various applications. © 2006 IEEE.