CaltechTHESIS
  A Caltech Library Service

Bit-serial Reed-Solomon decoders in VLSI

Citation

Whiting, Douglas L. (1985) Bit-serial Reed-Solomon decoders in VLSI. Dissertation (Ph.D.), California Institute of Technology. http://resolver.caltech.edu/CaltechETD:etd-03252008-090414

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. Efficient methods for bit-serial multiplicative inversion are also discussed, greatly reducing 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 at a speed independent of the redundancy of the code.

Item Type:Thesis (Dissertation (Ph.D.))
Degree Grantor:California Institute of Technology
Major Option:Computer Science
Thesis Availability:Restricted to Caltech community only
Thesis Committee:
  • Seitz, Charles L. (chair)
Defense Date:22 August 1984
Record Number:CaltechETD:etd-03252008-090414
Persistent URL:http://resolver.caltech.edu/CaltechETD:etd-03252008-090414
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:1117
Collection:CaltechTHESIS
Deposited By: Imported from ETD-db
Deposited On:04 Apr 2008
Last Modified:26 Dec 2012 02:35

Thesis Files

[img] PDF (Whiting_dl_1985.pdf) - Final Version
Restricted to Caltech community only
See Usage Policy.

6Mb

Repository Staff Only: item control page