Reed Solomon decoding of signals having variable input data rates

This application claims the benefit of U.S. Provisional Patent Application Ser. No. 60/803,436, filed May 30, 2006, the entirety of the disclosure of which application is incorporated herein by reference.

The present invention relates generally to data communication and, more particularly, concerns a method and apparatus for decoding signals of variable data rates that have been previously encoded with a Reed Solomon (RS) code.

Reed Solomon Codes are a ubiquitous class of error correcting codes, employed in various types of communication systems, for example, fiber optic systems and HDTV applications. Due to their wide applicability, RS encoders and decoders are employed in several different scenarios, characterized by differing resource constraints, input data rates, and error correction abilities. Optimizing an RS implementation strongly depends on the usage scenario.

An RS code is characterized by the following parameters, m and t, where m is the length of a single data word and t is the maximum number of errors that can be corrected. The total length of the code block is 2 m −1, of which 2t words are parity words and 2 m −1−2t words are a copy of the original message.

RS decoding proceeds in five distinct steps:

Syndrome computation: In this step, the 2t syndrome words are computed from the received code word, r 1 , r 2 , . . . , r n using the following formula:

In accordance with one aspect of the present invention, a class of RS decoder architectures is disclosed that can be used under differing input data rates. A preferred architecture divides the tasks that need to be performed by the RS decoder: Syndrome computation, Error locator polynomial evaluation, Error location, and Error evaluation into an optimal two stage pipeline that balances the execution times of individual pipeline stages, and optimizes resource sharing within the pipeline stage.

In order to cope with changes in input data rate, two key algorithmic components: syndrome computation and error location need to be parallelized. We present a technique to determine the degree of parallelism required of each of these components.

Overall, the division into a two stage pipeline, resource sharing within the pipeline stages, and parallelism of algorithmic components creates a resource efficient, low latency family of RS decoders that can work at different input data rates. The decrease in latency is, in itself an important figure of merit that can result in significantly less buffering, and therefore, itself reduce resource usage.

The foregoing brief description and further objects, features and advantages of the present invention will be understood more completely from the following detailed description of presently preferred embodiments, with reference being had to the accompanying drawings in which:

FIG. 1 is a functional block diagram showing an RS decoder architecture embodying the present invention;

FIGS. 2(A) and 2(B) , sometimes referred to herein collectively as FIG. 2 , are functional block diagrams illustrating a circuit embodying the present invention; and

FIG. 3 is a functional block diagram showing the architecture of the second stage of the RS decode pipeline.

FIG. 1 is a block diagram showing an RS decoder architecture embodying the present invention. The input arrives at the rate of d words per clock cycle. One block of code has a length of 2 m −1 words. Therefore, one complete code block is received in (2 m −1)/d clock cycles. As shown in FIG. 1 , we use a two stage pipeline for our computation. The first pipeline stage performs syndrome computation. The second pipeline stage performs error locator polynomial computation, error location, error evaluation, and error correction.

The following observations are made about this design architecture:

Input data arrives at a rate of d words per clock cycle, or (2 m −1)/d clock cycles per code block. Therefore, designing a circuit that is capable of a higher throughput is not useful, and probably consumes excess resources. The two key compute intensive blocks of the decoder are the syndrome computation and error location. Both these items lie on the critical path and cannot share resources. Therefore, they occupy separate pipeline stages. Computing the error locator polynomial, error evaluation, and error correction are relatively inexpensive in terms of clock cycles and resource utilization. Therefore, these can be combined with any of the compute intensive sections to create a pipeline. Given the regular and simple nature of the computation, the syndrome computation block is best implemented as a separate pipeline stage. Therefore, all other tasks are clubbed into the second pipeline stage. Given the sequential nature of the tasks involved, substantial resource sharing can be achieved by the second pipeline stage. The details of resource sharing are described later on in this section. After the errors are located, they need to be corrected. Therefore, a copy of the input needs to be stored in a buffer/FIFO queue until all errors have been located and evaluated. Since input data arrives continuously, the amount of storage extra required is proportional to the latency of the decoder. For example, if error location and evaluation happens 10,000 cycles after the first data word is clocked in, each data word must be stored for 10,000 clock cycles. Since input arrives continuously, at any time, 10,000 words of data should be stored. Therefore, reducing the latency leads to a reduction in size of the storage buffer. Our two stage pipeline, with the first stage and second stage taking up roughly the same number of cycles (approximately 2 m /d to compute) reduces the total buffer size to 2(2 m /d) (d-words)=2 (m+1) words. Since we require both pipeline stages to take approximately the same time (2 m /d), we require to parallelize the two key tasks: syndrome computation and error location accordingly. Syndrome computation (as described later on this section) is parallelized d-ways, and completes in 2 m /d cycles. Error location is parallelized d+1 ways and completes in 2 m /(d+1) cycles. The extra parallelism of the error location cycle is to enable completion of the other tasks: error polynomial computation, error evaluation and error correction. The above-mentioned observations are a significant aspect of the design of the decoder. Below, the detailed design of each individual block of the decoder is described in a separate section.

Syndrome Computation Block

The first step in RS decoding is syndrome computation, which involves the computation of 2t syndrome words from n received words, as outlined in the previous section. This is done according to the formula:

Now, new data is available every (2 m −1)/d cycles, the syndrome computation block must finish computing in (2 m −1)/d cycles. In order to achieve this, the following transformation is applied to the syndrome computation equation:

Equation A indicates that syndrome computation consists of two atomic steps:

Computing T k Computing α i d T k +T k−1

FIGS. 2(A) and 2(B) , sometimes referred to herein collectively as FIG. 2 , are functional block diagrams illustrating a circuit embodying the present invention. As shown in FIG. 2A , the input is first clocked into a d-word register that feeds a Tk computation block ( FIG. 2B ). The output of the Tk computation block feeds a single word register (R1). The output of the single word register feeds the output register through a multiplexer (MUX). The other port of the MUX is fed by a Multiply-add functional unit fed by the register R1 and the output register. The sequence of computations that takes place, by clock cycle, is as follows (N=(2m−1)/d):

Data r n , r n−1 , . . . , r n−d+1 →d-word register r n−d , r n−d−1 , . . . , r n−2d+1 →d-word register, T N →R1 r n−2d , r n−2d−1 , . . . , r n−3d+1 →d-word register, T N−1 →R1, R1→output register (output register contains TN) r n−3d , r n−3d−1 , . . . , r n−4d+1 →d-word register, T N−2 →R1, T N α i d +T N−1 →output register r n−4d , r n−4d−1 , . . . , r n−5d+1 →d-word register, T N−3 →R1, α i d (T N α i d +T N−1 )+T N−2 →output register . . .

Therefore, the computation completes in N+4 cycles. The hardware requirements for this block are as follows:

m×m multipliers: d×2t m bit adders: d×2t registers: 2t×(d+2) words, m bits each

The critical path is given by.T mult +log 2 (d×T add )

Λ, Ω Evaluation Block

As mentioned above, this block uses the syndrome words to compute the error locator polynomial and the error evaluator polynomial. Several optimized algorithms for performing this task have been presented in the literature, and are surveyed [[0036]1]. Table 1 presents a summary of key results. Note, however, that our implementation does not have to use the resources shown in the table—we just need enough resources to ensure that all tasks assigned to the second pipeline stage complete fast enough to keep the pipeline flowing. However, these resources do serve as an upper bound on what is required.

Error Locator Block

The error locator blocks solves the t th degree polynomial, Λ(z)=0 by substituting for z, every number in GF(2 m ). Therefore, the solution process involves, for every element, α j , jε{1, 2 m }, evaluating Λ(z) according to the following formula:

Λ( z )=1+σ 1 z+σ 2 z 2 + . . . +σ t z t   (3)

The coefficient, j, of a root α j uniquely identifies an error location. A single evaluation of Λ(z) consumes t−1 multiplications and t−1 additions, and can be completed in a single clock cycle, whose period is greater than T mult +log 2 (T add (t−1)). Therefore, 2 m −1 evaluations of Λ(z) take 2 m −1 clock cycles if we assume that we have t−1 multipliers and t−1 adders. Note, however, that this causes the latency of the second pipeline stage, of which error location is part, to exceed 2 m −1 clock cycles. Since the first pipeline stage only uses (2 m −1)/d+4 clock cycles, this delay is clearly unacceptable. In order to ensure that the pipeline stays balanced, we need to perform error location at a rate greater than (2 m −1)/d for a complete code block, in order to ensure that all operations in the second pipeline stage (error location, Λ, Ω computation, Forney error evaluation, error correction) can complete in under (2 m −1)/d+4 clock cycles. Therefore, we simultaneously evaluate d+1 copies of Λ(z), where d is the number of data words latched in per clock cycle.

We now present a means of performing K parallel evaluations of the Λ(z):

We define K initial polynomials as follows:

The hardware realization of this block is presented in “Architecture” section, below.

Error Evaluator Block

The roots, α −k , of the error locator polynomial, Λ, can be used to compute the error magnitudes according to the following formula: e k =α −k Ω(α −k )/Λ′(α −k ). Since the maximum number of located errors is t, the number of error evaluations is bounded by t. Each error evaluation consists of the following steps:

Determining the polynomial Λ′(z) by differentiating Λ(z): Differentiating a polynomial involves re-computing its coefficients according to the following rule: ƒ(z)=α 0 +α 1 z+ . . . +α n−1 x n−1 ƒ′(z)=α 1 +2α 2 z+ . . . +(n−1)α n−1 z n−2 =α 1 +α 3 z 2 +α 5 z 4 + . . . +α n−1 z n−2 . In computing the derivative, we utilize a characteristic of Galois Field addition, i.e., α+α=0. Therefore, computing the derivative merely involves the selection of the coefficients of odd powers of a polynomial. Evaluating Λ′(α −k ): Evaluating the polynomial involves multiplying each coefficient with the appropriate power of α −k and accumulating the result to compute Λ′(α −k ). We can save time by observing that the error locator block computes Λ(α −k )=σ 0 +σ 1 α −k +σ 2 α −2k + . . . +σ i α −tk . Therefore, the desired powers of α −k are available when the error locator is in operation. If the error locator locates a zero, i.e., if, we then store the powers of α −k in a separate FIFO. Since the error locator polynomial has a maximum of t roots, the total storage required for this operation is t×m. Note that the stored powers of α −k can also be used to compute Ω(α −k ) Inverting Λ′(α −k ) to get Λ′(α −k ) −1 : The inverse is computed by referring to a look up table of length 2 m −1. Evaluating Ω(α −k ): This t−1 degree polynomial is computed in the same step that computes Λ. Since the coefficients of the polynomial are available and the powers of α −k are also available, this computation involves t−1 multiplications and t additions. Multiplying Λ′(α −k ) −1 with Ω(α −k ) and α −k to obtain the result: This step can be straightforwardly performed in two clock cycles with a single multiplier.

Architecture, Implementation of the Second Pipeline Stage

This section outlines the architecture and implementation of the error locator polynomial computation, error location, error evaluation, and error correction tasks performed by the RS decoder. Collectively, these tasks form the second stage of the two stage decode pipeline. The plurality of tasks involved argues for a processor style architecture with register files, functional units, and a programmable controller. In what follows, we first describe our architecture, and then describe how this architecture can be used to realize the second pipeline stage. This description takes the form of a register transfer level language.

Architectural Description

FIG. 3 is a functional block diagram showing the architecture of the second stage of the RS decode pipeline. We now describe salient elements of our architecture:

t+1-word register file: Most polynomials required for decoding the RS code have t+1 or fewer coefficients. Therefore, a t+1 word register file is a logical choice for storing polynomials and intermediate results. In addition, operations in the Galois field often involve shifts, a special operation call Chain shift is defined as follows: Chain Shift (R1, R2, R3) shifts the contents of R1 into R2, and the contents of R2 into R3, one word at a time. If R1={r1 — 0, . . . , r1_t}, R2={r2 — 0, . . . , r2_t}, and R3={r3 — 0, . . . , r3_t} before the chain shift operation, the contents of the three registers after the chain shift operation are as follows: R1={0, r1 — 0, . . . , r1_t−1}, R2={r1_t,r2 — 0, . . . , r2_t−1}, R3={r2_t,r3 — 0, . . . , r3_t−1}. If Chain Shift is invoked with two operands, R2 and R3, R1 is assumed to be zero.

1 word register file: A small set of 1-word registers is available for storing single word results.

Stack: A t element stack, with each element consisting of t+1 words is part of the register file.

Dot Product Computing Unit: The error locator and the error evaluator perform, respectively, 2 m and 2×t instances of polynomial evaluation. In each case, the operation involves:

Multiplying α −jk with the desired coefficient Accumulating the result

Since α −jk is always at the beginning of the computation, the polynomial evaluation performed by the RS decoder is simplified into a dot product computation:

∑ i = 1 n ⁢ a i ⁢ b i

Given {a 1 ,a 2 ,a 3 , . . . , a n }{b 1 ,b 2 , . . . , b n }, two vectors, computer. Since the polynomials generated in the RS decoding process have a maximum degree of t, we derive dot-product computing units can handle a total of 2(t+1) inputs. In addition, under some circumstances, we require the dot product computing unit to generate the t+1-word intermediate result: {a i b i ,iε{1,t+1}} Therefore, the dot product outputs a t+q-word intermediate result and a 1 word final result. As mentioned in Section 3.3, d+1 copies of the error locator algorithm are implemented in parallel. Therefore, we require (d+1) dot product computing units. For the following analysis, we assume that d=1; therefore, we have two dot product units. Therefore, these two dot product units can perform the two polynomial evaluations required for error evaluation in parallel. In addition, these dot product units can also be used to evaluate the error locator polynomial, as discussed later on in this section.

Inversion Unit: As mentioned earlier, the error evaluator requires several instances of inverse computation. Therefore an inversion functional unit, realized using a look up table, is available. The inversion unit is capable of computing one inverse per clock cycle.

Multipliers, Adders, comparator: A total of two multipliers and two adders that operate on single word operands are available to handle miscellaneous tasks. A single word comparator is also available.

Mask and Shift Unit: The mask can shift the contents of a t+1-word register to the right or left at a one-word granularity. Therefore, a register entry {a1, a2, at+1} can be transformed into {a2, a3, . . . , at+1, a1} or {at+1, a2, a3, . . . , at}. In addition, the option to mask individual words of the t+1 word register is also available. The manner in which the masking is performed is decided by the output of a mask register. For example, a mask register set to {1,1,1, . . . , 1,0} and a left shift would yield the result {a2, a3, . . . , at, 0}.

Interconnect: The t+1 word register file has six input ports and six output ports. The two outputs of the dot product unit can be routed to different registers. Single word quantities are expanded out to t+1 in the following manner before being written into the t+1 word register file: {x}→{x, x, . . . t+1 times, x}. The 1 word register file is capable of accepting inputs from the single word functional units, as well as single word outputs of t+1 word functional units, e.g., the dot product computation unit

RTL Implementation using our Architecture

We now present the pseudo code for implementing the second stage of the RS decode pipeline using the architecture presented in the previous section. The pseudocode is annotated with comments that describe the numbers of clock cycles consumed by individual tasks, as well as variable names and functions. In all, the program takes 2 m−1 +12t+9 cycles to complete execution, assuming that error location is parallelized by a factor of 2. Recall that, if the syndrome computation is not parallelized, i.e., if d=1, the first pipeline stage executes in 2 m +3 clock cycles (latency), and has a throughput of 2 m −1. For the case of m=8, t=8, the first stage executes in 259 cycles and has a throughput of 255 cycles, and the second stage takes 233 clock cycles. Since both pipeline stages have a throughput that is faster than the data rate: 1 word per clock cycle or 255 cycles per frame, this implementation is capable of decoding RS codes in real time.

A two stage pipelined architecture was disclosed to perform RS decoding in a resource efficient manner. The pipeline features parallelized implementations of the decoders key tasks to match the input rate. Combining several of the decoding tasks into a single pipeline stage, we enable resource sharing between sequential tasks, thereby resulting in a resource efficient implementation. In addition, the small number of pipeline stages and the balance between the two stages results in a low latency implementation, thereby resulting in a very small buffer to store the input data, further reducing the implementation cost.

A preferred pseudocode implementation is presented in the annexed APPENDIX.

Although preferred embodiments of the invention have been disclosed for illustrative purposes, those skilled in the art will appreciate that many additions, modifications, and substitutions are possible without departing from the scope and spirit of the invention.

1. High speed architectures for Reed-Solomon decoders, D. V. Sarwate and N. R. Shanbag, IEEE Trans. VLSI Systems, Vol. 9, No. 5, Oct 2001

Pseudocode Implementation

// The first step is to compute the error location polynomial, and it takes 3*2t+2 cycles

1) Lambda_Reg={1,0,0, . . . , 0};B_reg={0,0,0, . . . , 1}, S_lo={S_t,S_t−1, . . . ,S — 0};S_hi={0,0,S — 2t−1, . . . , S_t+1}; R=0;Count=2t−1;Gamma=1;k=0;−k=0 //λ=1,B=1, λ=1, Lambda_reg, B_reg, Gamma, contain λ, γ, and B respectively.

2) S_temp=Chain_Shift(S_hi_copy,S_lo_copy,S_temp)//S_temp={s0,0, . . . 0}

3) Delta=DP(S_temp,Lambda_Reg);Bz=Left_Shift(Breg);//δ=s r λ 0 +s r−1 λ 1 + . . . +s r−t λ t

4) R=R+1; Temp1=DP(Gamma,Lambda);Temp2=DP(Delta,Bz);Test=(Delta !=0) & k>=0; S_temp=Chain_shift(S_hi,S_lo,S_tmp);If (R=count) break;//temp1=γλ,temp2=δBz, r=r+1

5) Branch on Test 7

6) Lambda=Temp1+Temp2;Breg=Lambda;Gamma=Delta;k=−k−1;−k=1+k; Go to 3

7) k=k+1;−k=−k−1;Go to 3

8) //Computing Omega according to the Equation: ω i =s i λ 0 +s i−1 λ 1 + . . . +s 0 λ i , iε{0,1, . . . , t−1}Ω=ω 0 +ω i z+ . . . +ω t−1 z t−1 , takes 2(t+1)+2=2t+4 cycles

9) r=0;count=t;ChainShift(S_hi,S_lo,S_tmp)

10) Omega1=DP(S_tmp,Lambda_Reg); ChainShift(S_hi,S_lo,S_tmp)

11) ChainShift(Omega1,Omega);Omega1=DP(S_tmp,Lambda_Reg);r=r+1

12) ChainShift(S_hi,S_lo,S_tmp);Test3=cmp(r,t);if (Test3==1) Go to 11;

13) //Evaluate two copies of the error locator polynomial: Λ(α i ), iε{1.2 . . . ,255}, compare each to zero, and store α i etc., corresponding to the roots in the stack, takes 2 m /2+1 cycles

14) Seed1={1,α,α 2 ,α 3 , . . . , α t };Seed2={1,α,α 2 ,α 4 ,α 6 , . . . , α 2t }; Mult={1,α,α 2 ,α 4 ,α 6 , . . . ,α 25 };

15) (Temp1,Result1)=DP(Seed1,Lambda_Reg);(Temp2,Result2)=DP(Seed2,Lambda_Reg)// Temp1={σ 0 ,σ 1 ,α, . . . , σ t α t },Temp2={σ 0 ,σ 1 α 2 , . . . , σ t α 2t }, result1=σ 0 +σ 1 z+ . . . +σ t α t ,

16) (Temp1,Result1)=DP(Temp1,Mult);(Temp2,Result2)=DP(Temp2,Mult);If (Result1==0), {NumErrors1++;Temp1→Stack;} If (Result2==0) {Temp2→Stack;NumErrors2++};Go to 16

17) If (Result1==0){NumErrors1++;Temp1→Stack;} If (Result2=+0) {Temp2→Stack;NumErrors2++}

18) //Now, we compute the error magnitude for all of the locations identified and correct the error, consumes a total of 4t+2 cycles

19) LambdaInv=Inverse(Lambda_Reg);//The inverse of every element of LambdaReg is computed and the result is stored in a t+1 register LambdaInv, LambdaInv={σ 0 −1 ,σ 1 −1 , . . . , σ t −1 }, takes t+1 cycles because we have only 1 inverter

20) count=0;NumErrors=NumErrors1+NumErrors2;Pop Stack→{R11,ErrorLoc,ErrorCoeff};

21) (R12,Temp)←DP(R11,LambdaInv);Message[ErrorLoc]+=R14;If(count==NumErrors) go to 25;

22) R14←DP(R12,Omega);R13←DP(dLambda,R12);

23) R13=Inv(R13);R14=Mult(R14,ErrorCoeff); Pop Stack→{R11,ErrorLoc,ErrorCoeff};Go to 22

24) End