Transform Decoding of Reed-Solomon Codes. Volume I. Algorithm and Signal Processing Structure

Abstract : One of the continuing concerns of the Low Cost Electronics project is the application of new technology to the implementation of error-correcting codes for reliable data communication. Our interest stems from the need for low- cost hardware to implement error-correction codes that exhibit significant coding gain on interference-resistant communication channels. Previous studies of coding gain led us to concentrate work on the implementation of the Reed- Solomon class of generalized BCH codes. This class of codes, although well- suited to the correction of both isolated random errors and random error bursts because of its optimum distance properties, continues to be genuinely in need of efficient decoding algorithms implemented by low-cost hardware. This report discusses in detail a transform decoding algorithm and its hardware implications, for the Reed-Solomon codes, that offer major simplifications relative to the conventional BCH decoding algorithm. A fast algorithm for encoding and syndrome computation is described. Modification of the error location process to accommodate erasures is also described. Also discussed are hardware implementation issues with a summary of design features and parameters to be incorporated in a future set of programmable integrated circuits for decoding a large number of Reed-Solomon codes.