Prueba

On the High-Speed VLSI Implementation of Errors-and-Erasures Correcting Reed-Solomon Decoders
Tong Zhang and Keshab K. Parhi
Department of Electrical and Computer Engineering
University of Minnesota, Minneapolis, MN 55455, USA
{tzhang,parhi}@ece. umn.edu

ABSTRACT
Recently a novel algorithm transformation was proposed to reduce the critical path and simplify the architecture design ofBerlekamp-Massey algorithm implementation for errors alone Reed-Solomon decoding. In this paper, we apply the same methodology to transform the Berlekamp-Massey al gorithm for errors-and-erasures RS decoding. We present a regular hardware architecture to implement the reformulated Berlekamp-Massey algorithm, which can achieve high throughput. Moreover, an operation scheduling scheme is proposed tofurther reduce the hardware complexity without loss of throughput
1. INTRODUCTION
Reed-Solomon (RS) codes are widely used for forward er ror correcting (FEC) in numerous communication systems because of their good error correction capability for burst errors [9]. A conventional errorsalone RS decoding proce dure can be modified to correct both errors and erasures [1][4] (an erasure occurs whenthe position of a corrupted symbol is known). Erasure information can be supplied by the demodulator in a communication system, i.e., the de modulator marks the received symbols that are very likely to contain errors. RS decoder with the capability of correct ing errors as well as erasures will improve performance i various systems [9] [10] [3].
To accommodate the continuously increasing demandsfor higher speed communication systems, RS decoders should be able to decode data at much higher throughput than the current standard states. Except applying the more advanced physical-level, e.g., sub-micron, technology to improve the throughput, the effective algorithm/architecture-level transformations and modifications are also playing important roles to achieve higher throughput. In RSdecoders the throughput bottleneck is in solving the Berlekamp's key equation, where two algorithms are typically employed [1]: extended Euclidean (eE) algorithm and Berlekamp-Massey (BM) algorithm. Recently a novel algorithm transformation
To appear in the 12th Great Lakes Symposium on VLSI, 2002

was proposd in [7] to reformulate the BM algorithm fo errors-alone RS decoders so that thekey-equation-solving block has a very regular semi-systolic architecture with the critical path of only Tmult+Tadd, where Tmutt and Tadd are the delays of the finite field multiplier and adder, respec tively. This amount of critical path is much smaller than that of the previous RS decoder implementations using BM algorithm and comparable to the best known result of imple mentations based on eE algorithm.The basic methodology behind such algorithm transformation is to remove the data dependency inside of one iteration at the cost of increased computation complexity so that the critical path can be re duced. In this paper, we show that this methodology can be readily applied to the errors-and-erasures RS decoder imple mentations to achieve regular semi-systolic architecture and critical path ofTmuit +Tadd. Moreover, exploiting the char acteristics of errors-and-erasures RS decoding, we propose an operation scheduling scheme for the developed decoder architecture to reduce the hardware complexity without loss of throughput.
This paper is organized as follows. We introduce the fundamentals of RS decoding in Section 2. An inverse-free BM algorithm for errors-and-erasures RS decoding isdescribed in Section 3. In Section 4, we apply the methodology proposed in [7] to transform the BM algorithm for errors-and-erasures RS decoding, based on which we present a semi systolic high-speed hardware architecture. We note that in order to facilitate the reader's reference to [7], we use the same notations as much as possible in the algorithm and hardware architecture descriptions
2. RS...