Efficient VLSI architectures for algebraic soft-decision decoding of Reed-Solomon codes

Algebraic soft-decision decoding (ASD) algorithms of Reed-Solomon (RS) codes have attracted much interest due to their significant coding gain and polynomial complexity. Practical ASD algorithms include the Koetter-Vardy, low-complexity Chase (LCC) and bit-level generalized minimum distance (BGMD) decodings. This thesis focuses on the design of efficient VLSI architectures for ASD decoders.;One major step of ASD algorithms is the interpolation. Available interpolation algorithms can only add interpolation points or increase interpolation multiplicities. However, backward interpolation, which eliminates interpolation points or reduces multiplicities, is indispensable to enable the re-using of interpolation results. In this thesis, a novel backward interpolation is first proposed for the LCC decoding through constructing equivalent Grobner bases. In the LCC decoding, 2eta test vectors need to be interpolated over. With backward interpolation, the interpolation result for each of the second and later test vectors can be computed by only one backward and one forward interpolation iterations. Compared to the previous design, the proposed backward-forward interpolation scheme can lead to significant memory saving with about the same throughput. To reduce the interpolation latency of the LCC decoding, a unified backward-forward interpolation is proposed to carry out both interpolations in a single iteration. With only 40% area overhead, the proposed unified interpolation architecture can almost double the throughput when large eta is adopted. Moreover, a reduced-complexity multi-interpolator scheme is developed for the low-latency LCC decoding.;The proposed backward interpolation is further extended to the iterative BGMD decoding. By reusing the interpolation results, at least 40% of the interpolation iterations can be saved for a (255, 239) code while the area overhead is small. Further speedup of the BGMD interpolation is limited by the inherent serial nature of the interpolation algorithm. In this thesis, a novel interpolation scheme that can combine multiple interpolation iterations is developed. Efficient architectures are presented to integrate the combined and backward interpolation techniques. A combined-backward interpolator of a (255, 239) code is implemented and can achieve a throughput of 440 Mbps on a Xilinx XC2V4000 FPGA device. Compared to the previous fastest implementation, our implementation can achieve a speedup of 64% with 51% less FPGA resource.;The factorization is another major step of ASD algorithms. In the re-encoded LCC decoding, it is proved that the factorization step can be eliminated. Hence, the LCC decoder can be further simplified.;In the re-encoded ASD decoders, a re-encoder and an erasure decoder need to be added. These two blocks can take a significant proportion of the overall decoder area and may limit the achievable throughput. An efficient re-encoder design is proposed by computing the erasure locator and evaluator through direct multiplications and reformulating other involved computations. When applied to a (255, 239) code, our re-encoder can achieve 82% higher throughput than the previous design with 11% less area. With minor modifications, the proposed design can also be used to implement erasure decoder.;After applying available complexity-reducing techniques, complexity comparisons for three practical ASD decoders were carried out. It is derived that the LCC decoder can achieve similar or higher coding gain with lower complexity for high-rate codes. This thesis also provides discussions on how the hardware complexities of ASD decoders change with codeword length, code rate and other parameters.