Low-Complexity Chase Decoding of Reed-Solomon Codes through Basis Reduction

This paper proposes the low-complexity Chase (LCC) decoding using basis reduction (BR) interpolation for Reed-Solomon (RS) codes, namely the LCC-BR algorithm. With received soft information, a number of decoding test-vectors are formulated. The LCC-BR algorithm first constructs a common basis which will be utilized by the following individual basis constructions of all test-vectors. This eliminates the redundant computation in BR interpolation, resulting in a low decoding complexity. Moreover, the LCC-BR algorithm can decode each test-vector in parallel, lowering the decoding latency. This paper further proposes the progressive LCC-BR (PLCC-BR) algorithm that decodes the test-vectors sequentially and terminates once the intended message is found. This progressive decoding is realized without additional memory cost. Simulation results show the complexity and latency advantages of the proposed algorithms over the other benchmark algorithms.