Low-Complexity Soft-Decoding Algorithms for Reed–Solomon Codes—Part I: An Algebraic Soft-In Hard-Out Chase Decoder

<para xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> In this paper, we present an algebraic methodology for implementing low-complexity, Chase-type, decoding of Reed–Solomon (RS) codes of length <emphasis emphasistype="italic"><formula formulatype="inline"><tex Notation="TeX">n</tex> </formula></emphasis>. In such, a set of <emphasis emphasistype="italic"><formula formulatype="inline"><tex Notation="TeX">2^η</tex></formula></emphasis> test-vectors that are equivalent on all except <emphasis emphasistype="italic"><formula formulatype="inline"><tex Notation="TeX">η n</tex></formula></emphasis> coordinate positions is first produced. The similarity of the test-vectors is utilized to reduce the complexity of interpolation, the process of constructing a set of polynomials that obey constraints imposed by each test-vector. By first considering the equivalent indices, a polynomial common to all test-vectors is constructed. The required set of polynomials is then produced by interpolating the final <emphasis emphasistype="italic"><formula formulatype="inline"><tex Notation="TeX">η</tex></formula></emphasis> dissimilar indices utilizing a binary-tree structure. In the second decoding step (<emphasis emphasistype="italic">factorization</emphasis>) a candidate message is extracted from each interpolation polynomial such that one may be chosen as the decoded message. Although an expression for the direct evaluation of each candidate message is provided, carrying out this computation for each polynomial is extremely complex. Thus, a novel, reduced-complexity, methodology is also given. Although suboptimal, simulation results affirm that the loss in performance incurred by this procedure is decreasing with increasing code length <emphasis emphasistype="italic"><formula formulatype="inline"> <tex Notation="TeX">n</tex></formula></emphasis>, and negligible for long <emphasis emphasistype="italic"><formula formulatype="inline"><tex Notation="TeX">$(n > 100)$</tex></formula></emphasis> codes. Significant coding gains are shown to be achievable over traditional hard-in hard-out decoding procedures (e.g., Berlekamp–Massey) at an equivalent (and, in some cases, lower) computational complexity. Furthermore, these gains are shown to be similar to the recently proposed soft-in-hard-out algebraic techniques (e.g., Sudan, Kötter–Vardy) that bear significantly more complex implementations than the proposed algorithm. </para>