Systolic interpolation architectures for soft-decoding Reed-Solomon codes
- 2 March 2004
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
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.Keywords
This publication has 7 references indexed in Scilit:
- Algebraic soft-decision decoding of reed-solomon codesIEEE Transactions on Information Theory, 2003
- A VLSI architecture for interpolation in soft-decision list decoding of Reed-Solomon codesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Algebraic soft-decision decoding of Reed-Solomon codesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- High-speed architectures for Reed-Solomon decodersIEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2001
- Improved decoding of Reed-Solomon and algebraic-geometry codesIEEE Transactions on Information Theory, 1999
- Decoding of Reed Solomon Codes beyond the Error-Correction BoundJournal of Complexity, 1997
- A generalization of the Berlekamp-Massey algorithm for multisequence shift-register synthesis with applications to decoding cyclic codesIEEE Transactions on Information Theory, 1991