High-speed architectures for Reed-Solomon decoders.
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 algorighm is in the iterative computation of discrepencies 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+[log2(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.
Introduction
Reed-Solomon codes [1], [3] are employed in numerous communications systems such as those
for deep space, digital subscriber loops, and wireless systems as well as in memory and data
storage systems. Continual demand for ever higher data rates makes it necessary to devise very
high-speed implementations of decoders for Reed-Solomon codes. Recently reported decoder
implementations [5], [19] have quoted data rates of ranging from 144 Mb/s to 1.28 Gb/s. These
high throughputs have been achieved by architectural innovations such as pipelining and parallel
processing. A majority of the implementations [2], [8], [15], [19] employ an architecture based
on the extended Euclidean (eE) algorithm for computing the greatest common divisor of two
polynomials [3]. A key advantage of architectures based upon the eE algorithm is regularity.
In addition, the critical path delay in these architectures is at best Tmult
Tmult , T add , and Tmux are the delays of the nite-eld multiplier, adder, and 2  1 multiplexer
respectively, and this is su-ciently small for most applications. In contrast, relatively few decoder
implementations have employed architectures based on the Berlekamp-Massey (BM) algorithm
DRAFT June 19, 2000
[1], [3], [10], presumably because the architectures were found to be irregular and to have a
longer critical path delay that was also dependent on the error-correcting capability of the code
[5]. In this paper, we show that, in fact, it is possible to reformulate the BM algorithm to
achieve extremely regular decoder architectures. Surprisingly, these new architectures can not
only operate at data rates comparable to architectures based on the eE algorithm, but they also
have lower gate complexity and simpler control structures.
This paper begins with a brief tutorial overview of the encoding and decoding of Reed-Solomon
codes in Section II. Conventional architectures for decoders based on the BM algorithm are
described in Section III. In Section IV, we show that it is possible to algorithmically transform
the BM algorithm so that a homogenous systolic array architecture for the decoder can be
developed. Finally, in Section V, we describe a pipelined architecture for block-interleaved Reed-Solomon
codes that achieves an order of magnitude reduction in the critical path delay over the
architectures presented in Sections III and IV.
II. Reed-Solomon Codes
We provide a brief overview of the encoding and decoding of Reed-Solomon codes.
A. Encoding of Reed-Solomon Codes
data symbols (bytes) that are to be transmitted over
a communication channel (or stored in memory.) These bytes are regarded as elements of the
nite eld (also called Galois eld) GF(2 m ), 1 and encoded into a codeword (c
of n > k bytes. These codeword symbols are transmitted over the communication channel (or
stored in memory.)
For Reed-Solomon codes over GF(2 m is odd, and the code can correct
(n k)=2 byte errors. The encoding process is best described in terms of the data polynomial
being transformed into a codeword polynomial
polynomials C(z) are polynomial
Addition (and subtraction) in GF(2 m ) is the bit-by-bit XOR of the bytes. The 2 m 1 nonzero elements of
can also be regarded as the powers,  of a primitive element  (where
so that the product of eld elements
June 19, 2000 DRAFT
multiples of G(z), the generator polynomial of the code, which is dened as
Y
typically 0 or 1. However, other choices sometimes simplify the decoding process
slightly. Since 2t consecutive powers  of  are roots of G(z), and C(z)
is a multiple of G(z), it follows that
for all codeword polynomials C(z). In fact, an arbitrary polynomial of degree less than n is a
codeword polynomial if and only if it satises (2).
A systematic encoding produces codewords that are comprised of data symbols followed by
parity-check symbols, and is obtained as follows. Let Q(z) and P (z) denote the quotient and
remainder respectively when the polynomial z n k D(z) of degree n 1 is divided by G(z) of
degree
is a multiple of G(z). Furthermore, since the lowest degree
term in z n k D(z) is d 0 z n k while P (z) is of degree at most n k 1, it follows that the codeword
is given by
and consists of the data symbols followed by the parity-check symbols.
B. Decoding of Reed-Solomon Codes
Let C(z) denote the transmitted codeword polynomial and let R(z) denote the received word
polynomial. The input to the decoder is R(z), and it assumes that
where, if e > 0 errors have occurred during transmission, the error polynomial E(z) can be
written as
It is conventional to say that the error values have occurred at the error locations
. Note that the decoder does not know E(z); in fact, it does
DRAFT June 19, 2000
not even know the value of e. The decoder's task is to determine E(z) from its input R(z), and
thus correct the errors by subtracting o E(z) from R(z). If e  t, then such a calculation is
always possible, that is, t or fewer errors can always be corrected.
The decoder begins its task of error correction by computing the syndrome values
If all 2t syndrome values are zero, then R(z) is a codeword, and it is assumed that
that is, no errors have occurred. Otherwise, the decoder knows that e > 0 and uses the syndrome
polynomial S(z), which is dened to be
to calculate the error values and error locations. Dene the error locator polynomial (z) of
degree e and the error evaluator
polynomial
z) of degree at most e 1 to be
e
Y
e
e
Y
These polynomials are related to S(z) through the key equation [1], [3]:
Solving the key equation to determine both (z)
and
z) from S(z) is the hardest part of the
decoding process. The BM algorithm (to be described in Section III) and the eE algorithm
can be used to solve (6). If e  t, these algorithms nd (z)
and
z), but if e > t, then the
algorithms almost always fail to nd (z)
and
z). Fortunately, such failures are usually easily
detected.
Once (z)
and
z) have been found, the decoder can nd the error locations by checking
whether for each j, 0  j  n 1. Usually, the decoder computes the value of
just before the j-th received symbol r j leaves the decoder circuit. This process is called
a Chien search [1], [3]. If is one of the error locations (say X i ). In other
words, r j is in error, and needs to be corrected before it leaves the decoder. The decoder can
June 19, 2000 DRAFT
6 SUBMITTED TO IEEE TRANS. VLSI SYSTEMS
calculate the error value Y i to be subtracted from r j via Forney's error value formula [3]:
z 0 (z)
z= j
denotes the formal derivative of (z). Note that the formal
derivative simplies to  0 since we are considering codes over GF(2 m ). Thus,
z which is just the terms of odd degree in (z). Hence, the value of
z 0 (z) at can be found during the evaluation of (z) at z =  j and does not require
a separate computation. Note also that (7) can be simplied by choosing
C. Reed-Solomon Decoder Structure
In summary, a Reed-Solomon decoder consists of three blocks:
the syndrome computation (SC) block,
the key-equation solver (KES) block, and
the Chien search and error evaluator (CSEE) block.
These blocks usually operate in pipelined mode in which the three blocks are separately and
simultaneously working on three successive received words. The SC block computes the syndromes
via (3) usually as the received word is entering the decoder. The syndromes are passed to
the KES block which solves (6) to determine the error locator and error evaluator polynomials.
These polynomials are then passed to the CSEE block which calculates the error locations and
error values via (7) and corrects the errors as the received word is being read out of the decoder.
The throughput bottleneck in Reed-Solomon decoders is in the KES block which solves (6):
in contrast, the SC and CSEE blocks are relatively straightforward to implement. Hence, in
this paper we focus on developing high-speed architectures for the KES block. As mentioned
earlier, the key equation (6) can be solved via the eE algorithm (see [19] and [17] for imple-
mentations), or via the BM algorithm (see [5] for implementations). In this paper, we develop
high-speed architectures for a reformulated version of the BM algorithm because we believe that
this reformulated algorithm can be used to achieve much higher speeds than can be achieved
by other implementations of the BM and eE algorithms. Furthermore, as we shall show in
Section IV.B.4, these new architectures also have lower gate complexity and a simpler control
structure than architectures based on the eE algorithm.
DRAFT June 19, 2000
III. Existing Berlekamp-Massey (BM) Architectures
In this section, we give a brief description of dierent versions of the Berlekamp-Massey (BM)
algorithm and then discuss a generic architecture, similar to that in the paper by Reed et al.
[13], for implementation of the algorithm.
A. The Berlekamp-Massey Algorithm
The BM algorithm is an iterative procedure for solving (6). In the form originally proposed
by Berlekamp [1], the algorithm begins with polynomials (0;
iteratively
determines polynomials (r; z)
and
satisfying the polynomial congruence,
for thus obtains a solution (2t; z) and
d t; z) to the key equation (6). Two
\scratch" polynomials B(r; z) and H(r; z) with initial values B(0; are
used in the algorithm. For each successive value of r, the algorithm determines (r; z) and B(r; z)
from (r 1; z) and B(r 1; z). Similarly, the algorithm
determines
z) and H(r; z) from
r 1; z) and H(r 1; z). Since S(z) has degree 2t 1, and the other polynomials can have
degrees as large as t, the algorithm needs to store roughly 6t eld elements. If each iteration
is completed in one clock cycle, then 2t clock cycles are needed to nd the error-locator and
error-evaluator polynomials.
In recent years, most researchers have used the formulation of the BM algorithm given by
Blahut [3] in which only (r; z) and B(r; z) are computed iteratively. Following the completion
of the 2t iterations, the error-evaluator
polynomial
y t; z) is computed as the terms of degree
t 1 or less in the polynomial product (2t; z)S(z). An implementation of this version thus
needs to store only 4t eld elements, but the computation of
t; z) requires an additional t
clock cycles. Although this version of the BM algorithm trades space against time, it also
suers from the same problem as the Berlekamp version, viz. during some of the iterations, it is
necessary to divide each coe-cient of (r; z) by a quantity - r . These divisions are most e-ciently
handled by rst computing - 1
r , the inverse of - r , and then multiplying each coe-cient of (r; z)
by - 1
r . Unfortunately, regardless of whether this method is used or whether one constructs
separate divider circuits for each coe-cient of (r; z), these divisions, which occur inside an
iterative loop, are more time-consuming than multiplications. Obviously, if these divisions could
be replaced by multiplications, the resulting circuit implementation would have a smaller critical
June 19, 2000 DRAFT
8 SUBMITTED TO IEEE TRANS. VLSI SYSTEMS
path delay and higher clock speeds would be usable. 2 A less well-known version of the BM
algorithm [4], [13], has precisely this property, and has been recently employed in practice [13],
[5]. We focus on this version of the BM algorithm in this paper.
The inversionless BM (iBM) algorithm is described by the pseudocode shown below. The
iBM algorithm actually nds scalar multiples   (z) and
z) instead of the (z)
and
dened in (4) and (5). However, it is obvious that the Chien search will nd the same error
locations, and it follows from (7) that the same error values are obtained. Hence, we continue
to refer to the polynomials computed by the iBM algorithm as (z)
and
z). As a minor
implementation detail,  in (4) and thus requires no latches for storage, but the iBM
algorithm must store  Note also that b 1 (r) which occurs in Steps iBM.2 and iBM.3 is
a constant: it has value 0 for all r.
The iBM Algorithm
Initialization:
t.
for do
begin
Step iBM.1
Step iBM.2
Step iBM.3 if -(r) 6= 0 and k(r)  0
then
begin
else
2 The astute reader will have noticed that the Forney error value formula (7) also involves a division. Fortunately,
these divisions can be pipelined because they are feed-forward computations. Similarly, the polynomial evaluations
needed in the CSEE block (as well as those in the SC block) are feed-forward computations that can be pipelined.
Unfortunately, the divisions in the KES block occur inside an iterative loop, and hence pipelining the computation
becomes di-cult. Thus, as was noted in Section II, the throughput bottleneck is in the KES block.
DRAFT June 19, 2000
begin
t.
For r < t, Step iBM.1 includes terms s 1   r+1 (r); s 2   r+2 involving
unknown quantities s Fortunately, it is known [3] that deg (r; z)  r so that
therefore the unknown s i do not aect the value of
-(r). Notice also the similarity between Steps iBM.1 and iBM.4. These facts have been used
to simplify the architecture that we describe next.
B. Architectures Based on the iBM algorithm
Due to the similarity of Steps iBM.1 and iBM.4, architectures based on the iBM algorithm
need only two major computational structures as shown in Fig. 1:
The discrepancy computation (DC) block for implementing Step iBM.1, and
The error locator update (ELU) block which implements Steps iBM.2 and iBM.3 in parallel.
The DC block contains latches for storing the syndromes s i , the GF(2 m ) arithmetic units for
computing the discrepancy -(r) and the control unit for the entire architecture. It is connected
to the ELU block which contains latches for storing for (r; z) and B(r; z) as well as GF(2 m )
arithmetic units for updating these polynomials, as shown in Fig. 1. During a clock cycle, the
DC block computes the discrepancy -(r) and passes this value together with
(r) and a control
signal MC(r) to the ELU block which updates the polynomials during the same clock cycle.
operations are completed in one clock cycle, we assume that m-bit
parallel arithmetic units are being employed. Architectures for such Galois eld arithmetic units
can be found in numerous references including [7] and will not be discussed here.
June 19, 2000 DRAFT
block
(in cycles 2t+1 to 3t)
block
Syndromes from the
To the block
To the
l t (r) l t-1 (r) 0011
d
Fig. 1. The iBM architecture.
B.1 DC Block Architecture
The DC block architecture shown in Fig. 2 has 2t latches constituting the DS shift register
that are initialized such that the latches DS contain the syndromes
In each of the rst 2t clock cycles, the t +1 multipliers compute
the products in Step iBM.1. These are added in a binary adder tree of depth dlog 1)e to
produce the discrepancy -(r). Thus, the delay in computing -(r) is T
A typical control unit such as the one illustrated in Fig. 2 has counters for the variables r and
k(r), and storage for
(r). Following the computation of -(r), the control unit computes the
OR of the m bits in -(r) to determine whether -(r) is nonzero. This requires m 1 two-input
gates arranged in a binary tree of depth dlog 2 me. If the counter for k(r) is implemented
in twos-complement representation, then k(r)  0 if and only if the most signicant bit in the
counter is 0. The delay in generating signal MC(r) is thus me  T or + T and .
Finally, once the MC(r) signal is available, the counter for k(r) can be updated. Notice that
a twos-complement arithmetic addition is needed if k(r 1. On the other hand,
negation in twos-complement representation complements all the bits and then adds 1, and hence
the update k(r only the complementation of all the bits in the k(r)
counter. We note that it is possible to use ring counters for r and k(r), in which case k(r) is
DRAFT June 19, 2000
SC block
Syndromes from the
CONTROL
AND
msb
CNTR r
Fig. 2. The discrepancy computation (DC) block.
updated just Tmux seconds after the MC(r) signal has been computed.
Following the 2t clock cycles for the BM algorithm, the DC block computes the error-locator
polynomial
z) in the next t clock cycles. To achieve this, the DS t ; DS latches
are reset to zero during the 2t-th clock cycle, so that, at the beginning of the (2t
cycle, the contents of the DS register (see Fig. 2) are s Also, the
outputs of the ELU block are frozen so that these do not change during the computation of
z). From Step iBM.4, it follows that the \discrepancies" computed during the next t clock
June 19, 2000 DRAFT
cycles are just the coe-cients ! 0
z). The architecture in Fig. 2 is
an enhanced version of the one described in [13]. The latter uses a slightly dierent structure
and dierent initialization of the DS register in the DC block, which requires more storage and
makes it less adaptable to the subsequent computation of the error-locator polynomial.
Note that the total hardware requirements of the DC block are 2t m-bit latches, t
tipliers, t adders, and miscellaneous other circuitry (counters, arithmetic adder or ring counter,
gates, inverters and latches), in the control unit. From Fig. 2, the critical path delay of the
DC block is
me  T or
B.2 ELU Block Architecture
Following the computation of the discrepancy -(r) and the MC(r) signal in the DC block,
the polynomial coe-cient updates of Steps iBM.2 and iBM.3 are performed simultaneously
in the ELU block. The processor element PE0 (hereinafter the PE0 processor) that updates
one coe-cient of (z) and B(z) is illustrated in Fig. 3(a). The complete ELU architecture is
shown in Fig. 3(b), where we see that signals -(r),
(r) and MC(r) are broadcast to all the PE0
processors. In addition, the latches in all the PE0 processors are initialized to zero except for
which has its latches initialized to the element 1 latches
and multipliers, and t adders and multiplexers are needed. The critical path delay of the
ELU block is given by
B.3 iBM Architecture
Ignoring the hardware used in the control section, the total hardware needed to implement the
iBM algorithm is 4t multiplexers. The
total time required to solve the key equation for one codeword is 3t clock cycles. Alternatively,
if
t; z) is computed iteratively, the computations require only 2t clock cycles. However, since
the computations required to
update
are the same as that of (r; z), a near-duplicate of
the ELU block is needed. 3 This increases the hardware requirements to 6t
t; z) < t, the array has only t PE0 processors.
DRAFT June 19, 2000
d (r)
d (r)
l
d (r)
d (r)
l
(a)
d (r)010101010101010101
PE0001100110011l l l l 0t-1
(b)
Fig. 3. The ELU block diagram:(a) the PE0 processor, and (b) the ELU architecture. The latches in
are initialized to 1 2 GF those in other PE0s are initialized to 0.
In either case, the critical path delay of the
iBM architecture can be obtained from Figs. 1, 2, and 3 as
which is the delay of the direct path that begins in the DC block starting from the DS i latches,
through a multiplier, an adder tree of height dlog (generating the signal -(r)), feeding
into the ELU block multiplier and adder before being latched. We have assumed that the
indirect path taken by -(r) through the control unit (generating signal MC(r)) feeding into the
ELU block multiplexer is faster than the direct path, i.e., Tmult > dlog 2 me  T or + T and . This
is a reasonable assumption in most technologies. Note that more than half of T iBM is due to
the delay in the DC block, and that this contribution increases logarithmically with the error
correction capability. Thus, reducing the delay in the DC block is the key to achieving higher
speeds.
In the next section, we describe algorithmic reformulations of the iBM algorithm that lead to
June 19, 2000 DRAFT
14 SUBMITTED TO IEEE TRANS. VLSI SYSTEMS
a systolic architecture for the DC block and reduce its critical path delay to TELU .
IV. Proposed Reed-Solomon Decoder Architectures
The critical path in iBM architectures of the type described in Section III passes through two
multipliers as well as the adder tree structure in the DC block. The multiplier units contribute
signicantly to the critical path delay and hence reduce the throughput achievable with the iBM
architecture. In this section, we propose new decoder architectures that have a smaller critical
path delay. These architectures are derived via algorithmic reformulation of the iBM algorithm.
This reformulated iBM (riBM) algorithm computes the next discrepancy -(r + 1) at the same
time that it is computing the current polynomial coe-cient updates, that is, the
and the b i (r 1)'s. This is possible because the reformulated discrepancy computation does not
use the  explicitly. Furthermore, the discrepancy is computed in a block which has
the same structure as the ELU block, so that both blocks have the same critical path delay
A. Reformulation of the iBM Algorithm
A.1 Simultaneous Computation of Discrepancies and Updates
Viewing Steps iBM.2 and iBM.3 in terms of polynomials, we see that Step iBM.2 computes
while Step iBM.3 sets B(r+1; z) either to (r; z) or to zB(r; z). Next, note that the discrepancy
-(r) computed in Step iBM.1 is actually - r (r), the coe-cient of z r in the polynomial product
Much faster implementations are possible if the decoder computes all the coe-cients of (r; z)
(and of (r; even though only - r (r) is needed to compute (r and to
decide whether B(r is to be set to (r; z) or to z  B(r; z).
Suppose that at the beginning of a clock cycle, the decoder has available to it all the coe-cients
of (r; z) and (r; z) (and, of course, of (r; z) and B(r; z) as well.) Thus,
available at the beginning of the clock cycle, and the decoder can compute (r
DRAFT June 19, 2000
Furthermore, it follows from (10) and (11) that
set to either (r; or to z  (r;
z  B(r; z)  S(z). In short, (r are computed in exactly the same manner
as are (r Furthermore, all four polynomial updates can be computed
simultaneously, and all the polynomial coe-cients as well as - r+1 (r + 1) are thus available at the
beginning of the next clock cycle.
A.2 A New Error-Evaluator Polynomial
The riBM algorithm simultaneously updates four polynomials (r; z), B(r; z), (r; z), and
S(z). The 2t iterations
thus produce the error-locator polynomial (2t; z) and also the polynomial (2t; z). Note that
since
c t; z)  (2t; z)  S(z) mod z 2t it follows from (11) that the low-order coe-cients of
(2t; z) are
just
s t; z), that is, the 2t iterations compute both the error-locator polynomial
(2t; z) and the error-evaluator
polynomial
y t; z) { the additional t iterations of Step iBM.4
are not needed. The high-order coe-cients of (2t; z) can also be used for error evaluation. Let
(2t; z)
where
(h) (z) of degree at most e 1 contains the high-order
terms. Since X 1
i is a root of (2t; z), it follows from (11) that (2t; X 1
0: Thus, (7) can be re-written as
z 0 (z)
z=X 1
We next show that this variation of the error evaluation formula has certain architectural advan-
tages. Note that the choice m preferable if (12) is to be used.
A.3 Further Reformulation
Since the updating of all four polynomials is identical, the discrepancies can be calculated
using an ELU block like the one described in Section III. Unfortunately, for
the discrepancy - r (r) is computed in processor PE0 r . Thus, multiplexers are needed to route the
June 19, 2000 DRAFT
appropriate latch contents to the control unit and to the ELU block that computes (r
Additional reformulation of the iBM algorithm, as described next, eliminates
these multiplexers. We use the fact that for any i < aect the value
of any later discrepancy - r+j (r j). Consequently, we need not store - i (r) and  i (r) for i < r.
Thus, for
and the polynomials
with initial values ^
It follows that these polynomial coe-cients are
updated as
set either to - i+1+r or to  i+r
(r). Note that
the discrepancy - r
is always in a xed (zero-th) position with this form of update. As a
nal comment, note this form of update ultimately produces ^
thus (12) can be used for error evaluation in the CSEE block.
The riBM algorithm is described by the following pseudocode. Note that b 1
for all values of r, and these quantities do not need to be stored or updated.
The riBM Algorithm
Initialization:
t.
for do
begin
Step riBM.1
Step riBM.2 if ^
then
begin
DRAFT June 19, 2000
else
begin
Next, we consider architectures that implement the riBM algorithm.
B. High-speed Reed-Solomon Decoder Architectures
As in the iBM architecture described in Section III, the riBM architecture consists of a
reformulated discrepancy computation (rDC) block connected to an ELU block.
B.1 The rDC Architecture
The rDC block uses the processor PE1 shown in Fig. 4(a) and the rDC architecture shown
in Fig. 4(b). Notice that processor PE1 is very similar to processor PE0 of Fig. 3(a). How-
ever, the contents of the upper latch \
ow through" PE1 while the contents of the lower latch
\recirculate". In contrast, the lower latch contents \
ow through" in processor PE0 while the
contents of the upper latch \recirculate". Obviously, the hardware complexity and the critical
path delays of processors PE0 and PE1 are identical. Thus, assuming as before that
Tmult > dlog 2 me  T or +T and , we get that T Note that the delay is independent
of the error-correction capability t of the code.
The hardware requirements of the proposed architecture in Fig. 4 are 2t PE1 processors, that
is, 4t latches, 4t multipliers, 2t adders, and 2t multiplexers, in addition to the control unit which
is the same as that in Fig. 2.
June 19, 2000 DRAFT
d (r)
d (r) d (r) d (r)
d (r)
d (r)
d
d
(a)
s
d (r)
sw
sw
s
(b)
Fig. 4. The rDC block diagram:(a) the PE1 processor, and (b) the rDC architecture.
B.2 The riBM Architecture
The overall riBM architecture is shown in Fig. 5. It uses the rDC block of Fig. 4 and the
ELU block in Fig. 3. Note that the outputs of the ELU block do not feed back into the rDC
block. Both blocks have the same critical path delay of T add and since
they operate in parallel, our proposed riBM architecture achieves the same critical path delay:
which is less than half the delay T add of the enhanced iBM
architecture.
As noted in the previous subsection, at the end of the 2t-th iteration, the PE1 i s,
contain the coe-cients
of
(2t; z) which can be used for error evaluation. Thus, 2t clock cycles
are used to determine both (z)
and
(h) (z) as needed in (12). Ignoring the control unit, the
hardware requirement of this architecture is 3t
DRAFT June 19, 2000
d (r)
l l l l 0t-1
ELU- block
CONTROL
rDC-block
Fig. 5. The systolic riBM architecture.
multiplexers. This compares very favorably with the
multiplexers needed to implement the
enhanced iBM architecture of Section III in which both the error-locator and the error-evaluator
polynomial are computed in 2t clock cycles. Using only t 1 additional multipliers and t additional
multiplexers, we have reduced the critical path delay by more than 50%. Furthermore, the riBM
architecture consists of two systolic arrays and is thus very regular.
B.3 The RiBM Architecture
We now show that it is possible to eliminate the ELU block entirely, and to implement the
BM algorithm in an enhanced rDC block in which the array of 2t PE1 processors has been
lengthened into an array of 3t processors as shown in Fig. 6. In this completely systolic
architecture, a single array computes both (z)
and
(z). Since the t processors
eliminated from the ELU block re-appear as the t additional PE1 processors, the RiBM
architecture has the same hardware complexity and critical path delay as the riBM architecture.
June 19, 2000 DRAFT
However, its extremely regular structure is esthetically pleasing, and also oers some advantage
in VLSI circuit layouts.h
t-1t
d
s
CONTROL
l (r)
s
Fig. 6. The homogenous systolic RiBM architecture.
An array of PE0 processors in the riBM architecture (see Fig. 5) carries out the same polynomial
computation as an array of PE1 processors in the RiBM architecture (see Fig 6), but in
the latter array, the polynomial coe-cients shift left with each clock pulse. Thus, in the RiBM
architecture, suppose that the initial loading of PE1 0 , PE1 1 , . , PE1 2t 1 is as in Fig. 4, while
are loaded with zeroes, and the latches in PE1 3t are loaded
as the iterations proceed, the polynomials ^
are
updated in the processors in the left-hand end of the array (eectively, (r; z) and (r; z) get
updated and shifted leftwards). After 2t clock cycles, the coe-cients
of
(h) (z) are in processors
Next, note that PE1 3t contains (0; z) and B(0; z), and as the iterations
proceed, (r; z) and B(r; z) shift leftwards through the processors in the right-hand end of the
array, with  i (r) and b i (r) being stored in processor PE1 3t r+i . After 2t clock cycles, processor
PE1 t+i contains  i (2t) and b i (2t) for t. Thus, the same array is carrying out two
separate computations. These computations do not interfere with one another. Polynomials
DRAFT June 19, 2000
are stored in processors numbered 3t r or higher. On the other hand,
since deg (r;
is known to be an upper bound on deg (r; z). It is known [3] that l(r) is
a nondecreasing function of r, and that it has maximum value errors have
occurred. Hence, 2t 1 r thus, as (r; z) and B(r; z)
shift leftwards, they do not over-write the coe-cients of ^
We denote the contents of the array in the RiBM architecture as polynomials ~
~
z) with initial values ~
z 3t . Then, the RiBM architecture implements
the following pseudocode. Note that ~ - 3t+1 values of r, and this quantity
does not need to be stored or updated.
The RiBM Algorithm
Initialization:
~
for do
begin
then
begin
~
else
begin
~
June 19, 2000 DRAFT
22 SUBMITTED TO IEEE TRANS. VLSI SYSTEMS
B.4 Comparison of Architectures

Table

I summarizes the complexity of the various architectures described so far. It can be seen
that, in comparison to the conventional iBM architecture (Berlekamp's version), the proposed
riBM and RiBM systolic architectures require t 1 more multipliers and t more multiplexers.
All three architectures require the same numbers of latches and adders, and all three architectures
require 2t cycles to solve the key equation for a t-error-correcting code. The riBM and RiBM
architectures require considerably more gates than the conventional iBM architecture (Blahut's
version), but also require only 2t clock cycles as compared to the 3t clock cycles required by
the latter. Furthermore, since the critical path delay in the riBM and RiBM architectures
is less than half the critical path delay in either of the iBM architectures, we conclude that
the new architectures signicantly reduce the total time required to solve the key equation (and
thus achieve higher throughput) with only a modest increase in gate count. More important,
the regularity and scalability of the riBM and RiBM architectures creates the potential for
automatically generating regular layouts (via a core generator) with predictable delays for various
values of t and m.
Comparison of the riBM and RiBM architectures with eE architectures is complicated by the
fact that most recent implementations use folded architectures in which each processor element
in the systolic array has only a few arithmetic units, and these units carry out all the needed
computations via time-division-multiplexing. For example, the hypersystolic eE architecture in
[2] has 2t elements each containing only one multiplier and adder. Since each
iteration of the Euclidean algorithm requires 4 multiplications, the processors of [2] need several
multiplexers to route the various operands to the arithmetic units, and additional latches to store
one addend until the other addend has been computed by the multiplier, etc. As a result, the
architecture described in [2] requires not only many more latches and multiplexers, but also many
more clock cycles than the riBM and RiBM architectures. Furthermore, the critical path delay
is slightly larger because of the multiplexers in the various paths. On the other hand, nite-eld
multipliers themselves consist of large numbers of gates (possibly as many as 2m 2 , but fewer
if logic minimization techniques are used), and thus a complete comparison of gate counts for
the two architectures requires very specic details about the multipliers. Nonetheless, a rough
DRAFT June 19, 2000


I
Comparison of Hardware Complexity and Path Delays
Architecture Adders Multipliers Latches Muxes Clock Critical
cycles path delay
iBM
iBM
Euclidean
Euclidean [2](folded) 2t
comparison is that the riBM and RiBM architectures require three times as many gates as the
hypersystolic eE architecture, but solve the key equation in one-sixth the time.
It is, of course, possible to implement the eE algorithm with more complex processor elements,
as described by Shao et al. [14]. Here, the 4 multiplications in each processor are computed using
4 separate multipliers. The architecture described in [14] uses only 2t+1 processors as compared
to the 3t processors needed in the riBM and RiBM architectures, but each
processor in [14] has 4 multipliers, 4 multiplexers, and 2 adders. As a result, the riBM and
RiBM architectures compare very favorably to the eE architecture of [14] { the new architectures
achieve the same (actually slightly higher) throughput with much smaller complexity.
One nal point to be made with respect to the comparison between the riBM and RiBM
architectures and the eE architectures is that the controllers for the systolic arrays in the former
are actually much simpler. In the eE architecture of [14], each processor also has a \control
section" that uses an arithmetic adder, comparator, and two multiplexers. 2dlog 2 te bits of
arithmetic data are passed from processor to processor in the array, and these are used to
generate multiplexer control signals in each processor. Similarly, the eE architecture of [2] has a
separate control circuit for each processor. The delays in these control circuits are not accounted
for in the critical path delays for the eE architectures that we have listed in Table I. In contrast,
all the multiplexers in the riBM and RiBM architectures receive the same signal and the
computations in these architectures is purely systolic in the sense that all processors carry out
exactly the same computation in each cycle, with all the multiplexers set the same way in all the
June 19, 2000 DRAFT
processors { there are no cell-specic control signals.
Preliminary Layout Results
Preliminary layout results from a core generator are shown in Fig. 7 for the KES block for
a 4-error-correcting Reed-Solomon code over GF(2 8 ). The processing element PE1 is shown
in Fig. 7(a) where the upper 8 latches store the element ~
- r while the lower 8 latches store the
element ~
r . A complete RiBM architecture is shown in Fig. 7(b) where the 13 PE1 processing
elements are arrayed diagonally and the error locator and error evaluator polynomials output
latches can be seen to be arrayed vertically. The critical path delay of the RiBM architecture
as reported by the synthesis tool in SYNOPSYS was 2:13 ns in TSMC's 0:25m 3:3V CMOS
technology.
(a) (b)
Fig. 7. The RiBM architecture synthesized in a 3:3V , 0:25m CMOS technology:(a) the PE1 processing
element, and (b) the RiBM architecture.
In the next section, we develop a pipelined architecture that further reduces the critical path
delay by as much as an order of magnitude by using a block-interleaved code.
DRAFT June 19, 2000
V. Pipelined Reed-Solomon Decoders
The iterations in the original BM algorithm were pipelined using the look-ahead transformation
[12] by Liu et al. [9], and the same method can be applied to the riBM and RiBM algorithms.
However, such pipelining requires complex overhead and control hardware. On the other hand,
pipeline interleaving (also described in [12]) of a decoder for a block-interleaved Reed-Solomon
code is a simple and e-cient technique that can reduce the critical path delay in the decoder by
an order of magnitude. We describe our results for only the RiBM architecture of Section IV
but the same techniques can also be applied to the riBM architecture as well as to the decoder
architectures described in Section III.
A. Block-Interleaved Reed-Solomon Codes
A.1 Block Interleaving
Error-correcting codes for use on channels in which errors occur in bursts are often interleaved
so that symbols from the same codeword are not transmitted consecutively. A burst of errors thus
causes single errors in multiple codewords rather than multiple errors in a single codeword. The
latter occurrence is undesirable since it can easily overwhelm the error-correcting capabilities of
the code and cause a decoder failure or decoder error. Two types of interleavers, block interleavers
and convolutional interleavers, are commonly used (see, e.g. [16], [18].) We restrict our attention
to block-interleaved codes.
Block-interleaving an (n; k) code to depth M results in an (nM; kM) interleaved code whose
codewords have the property that (c (n 1)M+i ; c (n
is a codeword in the (n; Equivalently, a codeword of the (nM; kM) code
is a multichannel data stream in which each of the M channels carries a codeword of the (n;
code.
A.2 Interleaving via Memory Arrays
The usual description (see, e.g., [16], [18]) of an encoder for the block-interleaved (nM; kM)
code involves partitioning kM data symbols (d blocks of k consecutive
symbols, and encoding each block into a codeword of the (n;
codewords are stored row-wise into an M  n memory array. The memory is then read out
column-wise to form the block-interleaved codeword. Notice that the block-interleaved code-
June 19, 2000 DRAFT
26 SUBMITTED TO IEEE TRANS. VLSI SYSTEMS
word is systematic in the sense that the parity-check symbols follow the data symbols, but the
Reed-Solomon encoding process described in Section II-A results in a block-interleaved codeword
in which the data symbols are not transmitted over the channel in the order in which they entered
the encoder. 4 At the receiver, the interleaving process is reversed by storing the nM received
symbols column-wise into an M  n memory array. The memory is then read out row-wise to
received words of length n that can be decoded by a decoder for the (n; code. The
information symbols appear in the correct order in the de-interleaved stream, and the decoder
output is passed on to the destination.
A.3 Embedded Interleavers
An alternative form of block interleaving embeds the interleaver into the encoder, thereby
transforming it into an encoder for the (nM; kM) code. For interleaved Reed-Solomon codes,
the mathematical description of the encoding process is that the generator polynomial of the
interleaved code is G(z M ), where G(z) denotes the generator polynomial of the (n;
dened in (1), and the codeword is formed as described in Section II-A { i.e., with D(z) now
denoting the data polynomial d kM 1 z of degree kM
1, the polynomial z (n k)M D(z) is divided by G(z M ) to obtain the remainder P (z) of degree
(n k)M 1. The transmitted codeword is z (n k)M D(z) P (z). In essence, the data stream
treated as if it were a multichannel data stream and the stream in
each channel is encoded with the (n; code. The output of the encoder is a codeword in the
block-interleaved Reed-Solomon code (no separate interleaver is needed) and it has the property
that the data symbols are transmitted over the channel in the order in which they entered the
encoder.
The astute reader will have observed already that the encoder for the (nM; kM) code is just
a delay-scaled encoder for the (n; code. The delay-scaling transformation of an architecture
replaces every delay (latch) in the architecture with M delays, and re-times the architecture to
account for the additional delays. The encoder treats its input as a multichannel data stream
and produces a multichannel output data stream, that is, a block-interleaved Reed-Solomon
In fact, the data symbol ordering is that which is produced by interleaving the data stream in blocks of k
symbols to depth M .
DRAFT June 19, 2000
codeword. Note also that while the interleaver array has been eliminated, the delay-scaled
encoder uses M times as much memory as the conventional encoder.
Block-interleaved Reed-Solomon codewords produced by delay-scaled encoders contain the
data symbols in the correct order. Thus, a delay-scaled decoder can be used to decode the
received word of nM symbols, and the output of the decoder also will have the data symbols
in the correct order. Note that a separate de-interleaver array is not needed at the receiver.
However, the delay-scaled decoder uses M times as much memory as the conventional decoder.
For example, delay-scaling the PE1 processors in the RiBM architecture of Fig. 6 results in the
delay-scaled processor DPE1 shown in Fig. 8. Note that for 0  i  2t 1, the top and bottom
sets of M latches in DPE1 i are initialized with the syndrome set S 0;M 1
where s i;j is the i th syndrome of the j th codeword. For 2t  i  3t 1, the latches in DPE1 i
are initialized to 0 while the latches in DPE1 3t are initialized to 1 2 GF(2 m ). After 2tM clock
cycles, processors DPE1 0 { DPE1 t 1 contain the interleaved error-evaluator polynomials while
processors DPE1 t { DPE1 2t contain the interleaved error-locator polynomials.
MD
MD
Fig. 8. Delay-scaled DPE1 processor. Initial conditions in the latches are indicated in ovals. The
delay-scaled RiBM architecture is obtained by replacing the PE1 processors in Fig. 6 with DPE1
processor and delay-scaling the control unit as well.
We remark that delay-scaled decoders can also be used to decode block-interleaved Reed-Solomon
codewords produced by memory array interleavers. However, the data symbols at the
June 19, 2000 DRAFT
28 SUBMITTED TO IEEE TRANS. VLSI SYSTEMS
output of the decoder will still be interleaved and an M  k memory array is needed for de-interleaving
the data symbols into their correct order. This array is smaller than the M  n
array needed to de-interleave the M codewords prior to decoding with a conventional decoder,
but the conventional decoder also uses less memory than the delay-scaled decoder.
Delay-scaling the encoder and decoder eliminates separate interleavers and de-interleaver and
is thus a natural choice for generating and decoding block-interleaved Reed-Solomon codewords.
However, a delay-scaled decoder has the same critical path delay as the original decoder, and
hence cannot achieve higher throughput than the original decoder. On the other hand, the extra
delays can be used to pipeline the computations in the critical path, and this leads to signicant
increases in the achievable throughput. We discuss this concept next.
B. Pipelined Delay-Scaled Decoders
The critical path delay in the RiBM architecture is mostly due to the nite-eld multipliers in
the processors. For the delay-scaled processors DPE1 shown in Fig. 8, these multipliers can be
pipelined and the critical path delay reduced signicantly. We assume that M  m and describe
a pipelined nite-eld multiplier with m stages.
B.1 A Pipelined Multiplier Architecture
While pipelining a multiplier, especially if it is a feedforward structure, is trivial, it is not so in
this case. This is because for RS decoders the pipelining should be done in such a manner that
the initial conditions in the pipelining latches are consistent with the syndrome values generated
by the SC block. The design of nite-eld multipliers depends on the choice of basis for the
representation. Here, we consider only the standard polynomial basis in which the m-bit byte
represents the Galois eld element
The pipelined multiplier architecture is based on writing the product of two GF
X and Y as
Let pp i denote the sum of the rst i terms in the sum above. The multiplier processing element
shown in Fig. 9(a) computes pp i+1 by adding either X i (if y
DRAFT June 19, 2000
Simultaneously, MPE i multiplies X i by . Since  is a constant, this multiplication requires
only XOR gates, and can be computed with a delay of only T On the other hand,
the delay in computing pp i+1 is T . Thus, the critical path delay is an order of
magnitude smaller than T tremendous speed gains can be achieved if
the pipelined multiplier architecture is used in decoding a block-interleaved Reed-Solomon code.
Practical considerations such as the delays due to pipelining latches, clock skew and jitter will
prevent the fullest realization of the speed gains due to pipelining. Nevertheless, the pipelined
multiplier structure in combination with the systolic architecture will provide signicant gains
over existing approaches.
DD
pp
pp
pp
pp
a
(m-1)D (m-2)D D
(b)
Fig. 9. The pipelined multiplier block diagram:(a) the multiplier processing element (MPE), and (b)
the multiplier architecture. Initial conditions of the latches at the y input are indicated in ovals.
The pipelined multiplier thus consists of m MPE processors connected as shown in Fig. 9(b)
with inputs pp and the y i 's. The initial conditions of the latches at the y input are zero,
and therefore the initial conditions of the lower latches in the MPEs do not aect the circuit
operation. The product XY appears in the upper latch of MPEm 1 after m clock cycles and
each succeeding clock cycle thereafter computes a new product. Notice also that during the rst
June 19, 2000 DRAFT
clock cycles, the initial contents of the upper latches of the MPEs appear in succession at the
output of MPEm 1 . This property is crucial to the proper operation of our proposed pipelined
decoder.
B.2 The Pipelined Control Unit
If the pipelined multiplier architecture described above (and shown in Fig. is used in the
DPE1 processors of Fig. 8, the critical path delay of DPE1 is reduced from Tmult + T add to
just . Thus, the control unit delay in computing MC(r), which is inconsequential in
the RiBM architecture (as well as in the iBM and riBM architectures, and the delay-scaled
versions of all these), determines the largest delay in a pipelined RiBM architecture.
Fortunately, the computation of MC(r) can also be pipelined in (say) stages.
This can be done by noting that d delays from DPE1 0 in the M-delay scaled RiBM architecture
(see Fig. 8) can be retimed to the outputs of the control unit and then subsequently employed
to pipeline it. Note, however, that the d latches in DPE1 0 that are being retimed are initialized
to S 0;d 1
i at the begininng of every decoding cycle. Hence, the retimed latches in the control
unit will need to be initialized to values that are a function of syndromes S 0;d 1
i . This is not a
problem because these syndromes will be produced by the SC block in the beginning of each
decoding cycle.
B.3 Pipelined Processors
If pipelined multiplier units as described above are used in a delay-scaled DPE1 processor,
and the control unit is pipelined as described above, then we get the pipelined PPE1 i processor
shown in Fig. 10 (and the pipelined RiBM (pRiBM) architecture also described in Fig. 10). The
initial values stored in the latches are the same as were described earlier for the DPE1 processors.
Note that some of the latches that store the coe-cients of ~
are part of the latches in the
pipelined multiplier. However, the initial values in the latches in the lower multiplier in Fig. 10
are 0. Thus, during the rst m clock cycles
ow through into the
leftmost latches without any change.
From the above description, it should be obvious that the pRiBM architecture based on the
PPE1 processor of Fig. 10 has a critical path delay of
DRAFT June 19, 2000
mD
mD
d (Mr+j)(M-d)D
d
(M-m)D
Fig. 10. Pipelined PPE1 processor. Initial conditions in the latches are indicated in ovals. The pipelined
RiBM architecture is obtained by replacing the PE1 processors in Fig. 6 with PPE1 processor and
employing the pipelined delay-scaled controller.
Thus, the pRiBM architecture can be clocked at speeds that can be as much as an order of magnitude
higher than those achievable with the unpipelined architectures presented in Sections III
and IV.
C. Decoders for Non-interleaved Codes
The pRiBM architecture can decode a block-interleaved code at signicantly faster rates than
the RiBM architecture can decode a non-interleaved code. In fact, the dierence is large enough
that a designer who is asked to devise a decoder for non-interleaved codes should give serious
thought to the following design strategy.
Read in M successive received words into an block-interleaver memory array.
Read out a block-interleaved received word into a decoder with the pRiBM architecture.
Decode the block-interleaved word and read out the the data symbols into a block-deinterleaver
memory array.
Read out the de-interleaved data symbols from the deinterleaver array.
Obviously, similar decoder design strategies can be used in other situations as well. For example,
to decode a convolutionally interleaved code, one can rst de-interleave the received words,
and then re-interleave them into block-interleaved format for decoding. Similarly, if a block-
interleaved code has very large interleaving depth M , the pRiBM architecture may be too large
to implement on a single chip. In such a case, one can de-interleave rst and then re-interleave to
a suitable depth. In fact, the \de-interleave and re-interleave" strategy can be used to construct
June 19, 2000 DRAFT
a universal decoder around a single decoder chip with xed interleaving depth.
VI. Concluding Remarks
We have shown that the application of algorithmic transformations to the Berlekamp-Massey
algorithm result in the riBM and RiBM architectures whose critical path delay is less than
half that of conventional architectures such as the iBM architecture. The riBM and RiBM
architectures use systolic arrays of identical processor elements. For block-interleaved codes,
the de-interleaver can be embedded in the decoder architecture via delay-scaling. Furthermore,
pipelining the multiplications in the delay-scaled architecture result in an order of magnitude
reduction in the critical path delay. In fact, the high speeds at which the pRiBM architecture
can operate makes it feasible to use it to decode non-interleaved codes by the simple stratagem
of internally interleaving the received words, decoding the resulting interleaved word using the
pRiBM architecture, and then de-interleaving the output.
Future work is being directed towards integrated circuit implementations of the proposed
architectures and their incorporation into broadband communications systems such as those for
very high-speed digital subscriber loops and wireless systems.
VII.

Acknowledgments

The authors would like to thank the reviewers for their constructive criticisms which has
resulted in signicant improvements in the manuscript.



--R

Algebraic Coding Theory

Theory and Practice of Error-Control Codes












Applied Coding and Information Theory for Engineers

Control Systems for Digital Communication and Storage

--TR
systems for digital communication and storage
Applied coding and information theory for engineers

--CTR
Kazunori Shimizu , Nozomu Togawa , Takeshi Ikenaga , Satoshi Goto, Reconfigurable adaptive FEC system with interleaving, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China
Tong Zhang , Keshab K. Parhi, On the high-speed VLSI implementation of errors-and-erasures correcting reed-solomon decoders, Proceedings of the 12th ACM Great Lakes symposium on VLSI, April 18-19, 2002, New York, New York, USA
Y. W. Chang , T. K. Truong , J. H. Jeng, VLSI architecture of modified Euclidean algorithm for Reed-Solomon code, Information Sciences: an International Journal, v.155 n.1-2, p.139-150, 1 October
Zhiyuan Yan , Dilip V. Sarwate, Universal Reed-Solomon decoders based on the Berlekamp-Massey algorithm, Proceedings of the 14th ACM Great Lakes symposium on VLSI, April 26-28, 2004, Boston, MA, USA
Jung H. Lee , Jaesung Lee , Myung H. Sunwoo, Design of application-specific instructions and hardware accelerator for reed-solomon codecs, EURASIP Journal on Applied Signal Processing, v.2003 n.1, p.1346-1354, January
Zhiyuan Yan , Dilip V. Sarwate, New Systolic Architectures for Inversion and Division in GF(2^m), IEEE Transactions on Computers, v.52 n.11, p.1514-1519, November
systolic architectures;interleaved codes;berlekamp-massey algorithm;pipelined decoders;reed-solomon codes