Systolic interpolation architectures for soft-decoding Reed-Solomon codes

A. Ahmed, N. R. Shanbhag, R. Koetter

Research output: Chapter in Book/Report/Conference proceedingConference contribution


We present a systolic algorithm for performing interpolation, a computationally intensive kernel found in algebraic soft-decoding of Reed-Solomon codes. We reformulate the interpolation algorithm, resulting in a systolic interpolation algorithm, which can compute a reduced number of candidate polynomial coefficients. Using the dependence graph of the algorithm, we realize a low-latency interpolation architecture and a high-throughput interpolation architecture. These architectures are compared against previously: proposed architectures for an RS soft-decoder. We derive expressions for the latency of the systolic implementations and show that, for a reasonable hardware constraint, the low-latency systolic implementation reduces latency by 34% for a [255, 239] RS code. For the same code and hardware constraints, the high-throughput implementation, with a block pipelining depth of 5, increases throughput by 68%. In addition, the critical path of both the low-latency and the high-throughput implementation is smaller than that of previously proposed architectures.

Original languageEnglish (US)
Title of host publication2003 IEEE Workshop on Signal Processing Systems
Subtitle of host publicationDesign and Implementation, SIPS 2003
EditorsWonyong Sung, Myung Hoon Sunwoo
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages6
ISBN (Electronic)0780377958
StatePublished - 2003
Event2003 IEEE Workshop on Signal Processing Systems, SIPS 2003 - Seoul, Korea, Republic of
Duration: Aug 27 2003Aug 29 2003

Publication series

NameIEEE Workshop on Signal Processing Systems, SiPS: Design and Implementation
ISSN (Print)1520-6130


Other2003 IEEE Workshop on Signal Processing Systems, SIPS 2003
Country/TerritoryKorea, Republic of


  • Computer architecture
  • Delay
  • Hardware
  • Interpolation
  • Iterative decoding
  • Kernel
  • Pipeline processing
  • Polynomials
  • Reed-Solomon codes
  • Throughput

ASJC Scopus subject areas

  • Electrical and Electronic Engineering
  • Signal Processing
  • Applied Mathematics
  • Hardware and Architecture


Dive into the research topics of 'Systolic interpolation architectures for soft-decoding Reed-Solomon codes'. Together they form a unique fingerprint.

Cite this