High-speed architectures for Reed-Solomon decoders

Dilip V. Sarwate, Naresh R. Shanbhag

Research output: Contribution to journalArticlepeer-review


New high-speed VLSI architectures for decoding Reed-Solomon codes with the Berlekamp-Massey algorithm are presented in this paper. The speed bottleneck in the Berlekamp-Massey algorithm is in the iterative computation of discrepancies followed by the updating of the error-locator polynomial. This bottleneck is eliminated via a series of algorithmic transformations that result in a fully systolic architecture in which a single array of processors computes both the error-locator and the error-evaluator polynomials. In contrast to conventional Berlekamp-Massey architectures in which the critical path passes through two multipliers and 1 + [log 2(t + 1)] adders, the critical path in the proposed architecture passes through only one multiplier and one adder, which is comparable to the critical path in architectures based on the extended Euclidean algorithm. More interestingly, the proposed architecture requires approximately 25% fewer multipliers and a simpler control structure than the architectures based on the popular extended Euclidean algorithm. For block-interleaved Reed-Solomon codes, embedding the interleaver memory into the decoder results in a further reduction of the critical path delay to just one XOR gate and one multiplexer, leading to speed ups of as much as an order of magnitude over conventional architectures.

Original languageEnglish (US)
Pages (from-to)641-655
Number of pages15
JournalIEEE Transactions on Very Large Scale Integration (VLSI) Systems
Issue number5
StatePublished - Oct 2001
Externally publishedYes


  • Berlekamp-Massey algorithm
  • Interleaved codes
  • Pipelined decoders
  • Reed-Solomon codes
  • Systolic architectures

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Electrical and Electronic Engineering


Dive into the research topics of 'High-speed architectures for Reed-Solomon decoders'. Together they form a unique fingerprint.

Cite this