Low-complexity soft decoding algorithms for Reed-Solomon codes.

摘要

Two approaches to soft decoding of Reed-Solomon Codes (of block length n) are presented. The first procedure is an algebraic, Chase-type, technique which first produces a set of test-vectors that are equivalent on all except h≪n coordinate positions. 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 eta dissimilar indices utilizing a binary-tree structure.; In the factorization step, a candidate message is extracted from each interpolation polynomial. Although an expression for the direct evaluation of each candidate message is provided, carrying-out this calculation for each polynomial is extremely complex. Thus, a novel, reduced-complexity, methodology is also given. Although suboptimal, simulation results affirm the loss in performance incurred by this procedure is decreasing with code length, and negligible for long (n > 100) codes. Significant coding gains are shown to be achievable over traditional hard-decision decoding procedures at a comparable computational complexity. These gains are, furthermore, shown to be similar to recently proposed algebraic techniques that bear a significantly more complex implementation than the proposed algorithm.; The second proposed technique is an iterative methodology that applies the output of subsequent iterations of Belief-Propagation (BP) as input to a legacy decoding algorithm. However, due to the suboptimal performance of BP conducted on the inherently dense Reed-Solomon parity-check matrix, a method is provided to construct reduced-density, binary, parity-check equations. Iterative decoding is then implemented by (1) utilizing a subset of a redundant set of parity-check equations to minimize the number of connections into the least-reliable bits or (2) augmenting the parity-check matrix with phantom-checks that, when added to existing rows, maximally improve the structure of the resulting graph. Simulation results show that performance comparable to the best known Reed-Solomon decoding techniques is achievable with these methodologies. However, unlike these existing procedures, the architecture of the proposed algorithm allows for a practical implementation in hardware.