Algorithms and architectures for soft-decoding Reed-Solomon codes

This thesis describes algorithmic and architectural techniques for reducing the complexity of soft-decoding Reed-Solomon codes. The three soft-decoding algorithms considered are algebraic soft-decoding, generalized minimum distance decoding, and ordered-statistics decoding.; An algorithmic technique to reduce algebraic soft-decoding complexity is proposed using intermediate interpolation results to check for decodability of the received word. The proposed technique combines intermediate interpolation checks with interpolation point re-encoding and co-ordinate transformation. A technique for reducing the number of intermediate interpolation checks is also proposed. At the architectural level, it is shown that efficient computation of discrepancy polynomials reduces interpolation latency by a factor of eight over a direct mapped interpolation architecture.; A high-speed systolic architecture for generalized minimum distance decoding is derived by mapping the iterative erasure decoding algorithm proposed by Koetter onto a systolic array. The proposed architecture is based on the systolic architecture by Sarwate and Shanbhag for implementing the Berlekamp-Massey algorithm.; A low-latency, reduced-memory architecture for ordered-statistics decoding is proposed. Starting with a reduced subset of test-cases, the latency and memory requirements of ordered-statistics decoding are further reduced by substituting the row operations of the original ordered-statistics algorithm with equivalent column operations.; Finally, the applicability of soft-decoding for disk-drive applications is studied. Based on performance improvements and complexity requirements, generalized minimum distance decoding with maximum a priori soft-detection is selected, and the corresponding architecture is developed. The generalized minimum distance decoder is expected to give 0.5 dB gain over a hard-decoder at the target bit error-rate of 10-12 for the disk-drive channel. The architecture is synthesized using the Virtual Silicon standard cell library in a 0.13-mum CMOS process. It has an area of 7.29 mm² and achieves a throughput of 8 Gbps.