Bit-Serial Reed Solomon Decoders in VLSI

Abstract

Reed-Solomon codes are known to provide excellent error-correcting capabilities on many types of communication channels. Although efficient decoding algorithms have been known for over fifteen years, currently available decoder systems are large both in size and in power consumption. Such systems typically use a single, very fast, fully parallel finite-field multiplier in a sequential architecture. Thus, more processing time is required as the code redundancy increases. By using many arithmetic units on a single chip, it is possible to exploit the concurrency inherent in the decoding algorithms to attain performance levels previously possible only with large ECL systems.

An investigation into the structure of binary extension fields reveals that the common arithmetic operations used in decoding can be implemented quite efficiently in a bit-serial fashion, using any of several bases over GF(2). Berlekamp's dual-basis multiplier is generalized to the product of two arbitrary field elements, and a necessary and sufficient condition is then derived for the existence of a self-dual basis. The efficient methods presented for bit-serial multiplicative inversion greatly reduce the complexity traditionally associated with this operation.

Using these bit-serial techniques, several architectures for implementing each phase of the known Reed-Solomon decoding algorithms are presented and compared. Simple methods are presented to allow power-sum syndrome decoders to handle codes with a variety of block lengths and redundancies. Each approach comes within a factor of log n (where n is the block length of the code) of the recently derived asymptotic lower bounds for both time and area. Results from a student project to lay out a prototype decoder chip using the Berlekamp-Massey algorithm are also discussed. By utilizing the parallelism inherent in the key equation solution, these architectures can decode received words a t a speed independent of the redundancy of the code.

Files

Additional details