A Caltech Library Service

Bit-Serial Reed-Solomon Decoders in VLSI


Whiting, Douglas Lee (1985) Bit-Serial Reed-Solomon Decoders in VLSI. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/bjd1-9j44.


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.))
Subject Keywords:Computer Science
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Computer Science
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • McEliece, Robert J.
Thesis Committee:
  • Seitz, Charles L. (chair)
  • Kajiya, James Thomas
  • Abu-Mostafa, Yaser S.
  • Berlekamp, Elwyn Ralph
  • McEliece, Robert J.
Defense Date:22 August 1984
Funding AgencyGrant Number
Defense Advanced Research Projects Agency (DARPA)3771
Office of Naval Research (ONR)N00014-79-0597
Record Number:CaltechETD:etd-03252008-090414
Persistent URL:
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:1117
Deposited By: Imported from ETD-db
Deposited On:04 Apr 2008
Last Modified:16 Apr 2021 23:29

Thesis Files

PDF (Whiting_dl_1985.pdf) - Final Version
See Usage Policy.


Repository Staff Only: item control page