Methods and apparatus for error correction using an R-Q calculator

Abstract

An error correction decoder which includes a syndrome calculator, an error locator polynomial calculator, a standard error locator polynomial calculator, an error transform calculator and an inverse error transform calculator. These error correction decoder calculators provide a pipelined architecture for performing Reed-Solomon error correction calculations quickly. The error locator polynomial calculator includes an R-Q calculator, a λ-μ calculator, an R-Q degree calculator and a trigger circuit. These calculators and the trigger circuit can be implemented each as a plurality of generic cells. The number of generic cells can be changed to construct Reed-Solomon circuits for different Reed-Solomon codes. The R-Q, λ-μ and R-Q degree calculators provide adaptive circuits that use switches and multiplexors, for example, to adapt to perform appropriate calculations based upon the nature of the error correction polynomials applied to the inputs of the calculators. The R-Q, λ-μ and R-Q degree calculators use multipliers, adders, memory elements and/or delay elements to perform the appropriate calculations. The calculations performed are controlled by selecting a path through which data will pass wherein the path is configured to perform the appropriate calculations. The R-Q degree calculator is similar. The trigger circuit provides an adaptive delay using a multiplexor, a bypass path and a delay path. The trigger circuit adjusts the timing of the trigger signal it puts out by selecting either the bypass path or the delay path. By adjusting the delay, the trigger circuit coordinates the triggering of subsequent cells with the timing of calculations performed in preceding cells.

What is claimed is: 
     
       1. An R-Q calculator for processing error correction polynomials, the R-Q calculator comprising: a plurality of R-Q circuits each having an R input, an R output, a Q input and a Q output wherein the plurality of R-Q circuits are coupled together to form a series of R-Q circuits such that the R output of each immediately preceding R-Q circuit is coupled to the R input of each immediately succeeding R-Q circuit and the Q output of each immediately preceding R-Q circuit is coupled to the Q input of each immediately succeeding R-Q circuit and wherein the R input of a first of the R-Q circuits provides an initial R input, the Q input of the first R-Q circuit provides an initial Q input, the R output from a last of the R-Q circuits provides a final R output and the Q output from the last R-Q circuit provides a final Q output;   in each R-Q circuit a switch having an R switch input, a Q switch input, an R' switch output, a Q' switch output and a switch control input wherein the switch is adapted to couple the R switch input to the R' switch output and the Q switch input to the Q' switch output when a first control signal is present at the switch control input, wherein the switch is adapted to couple the R switch input to the Q' switch output and the Q switch input to the R' switch output when a second control signal is present at the switch control input;   in each R-Q circuit an R' delay path adapted to introduce a delay, an R' calculation path adapted to process error correction polynomials and an R' multiplexor wherein the R' delay path is coupled in series with the R' multiplexor between the R' switch output and the R output and wherein the R' calculation path is coupled in series with the R' multiplexor between the R' switch output and the R output such that the R' multiplexor is adapted to couple the R' switch output to the R output through one of the R' delay path and the R' calculation path;   in each R-Q circuit a Q' delay path adapted to introduce a delay, a Q' bypass path and a Q' multiplexor wherein the Q' delay path is coupled in series with the Q' multiplexor between the Q' switch output and the Q output and wherein the Q' bypass path is coupled in series with the Q' multiplexor between the Q' switch output and the Q output such that the Q' multiplexor is adapted to couple the Q' switch output to the Q output through one of the Q' delay path and the Q' bypass path; and   in each R-Q circuit a cross couple path coupled between the Q' delay path and the R' calculation path.   
     
     
       2. The R-Q calculator of claim 1 wherein the R' multiplexor couples the R' calculation path between the R' switch output and the R output when the Q' multiplexor couples the Q' delay path between the Q' switch output and the Q output. 
     
     
       3. The R-Q calculator of claim 2, wherein the delay introduced by the Q' delay path is greater than a delay introduced by the R' calculation path. 
     
     
       4. The R-Q calculator of claim 3, wherein the delay introduced by the Q' delay path is one cycle longer than the delay introduced by the R' calculation path. 
     
     
       5. The R-Q calculator of claim 4, wherein the Q' delay path comprises a memory element. 
     
     
       6. The R-Q calculator of claim 2, wherein the R' multiplexor couples the R' delay path between the R' switch output and the R output when the Q' multiplexor couples the Q' bypass path between the Q' switch output and the Q output. 
     
     
       7. The R-Q calculator of claim 6, wherein the delay introduced by the R' delay path is greater than any delay introduced by the Q' bypass path. 
     
     
       8. The R-Q calculator of claim 7, wherein the delay introduced by the R' delay path is one cycle longer than the any delay introduced by the Q' bypass path. 
     
     
       9. The R-Q calculator of claim 1 wherein the R' multiplexor couples the R' delay path between the R' switch output and the R output when the Q' multiplexor couples the Q' bypass path between the Q' switch output and the Q output. 
     
     
       10. The R-Q calculator of claim 9, wherein the delay introduced by the R' delay path is greater than any delay introduced by the Q' bypass path. 
     
     
       11. The R-Q calculator of claim 10, wherein the delay introduced by the R' delay path is one cycle longer than the any delay introduced by the Q' bypass path. 
     
     
       12. The R-Q calculator of claim 11, wherein the R' delay path comprises a memory element. 
     
     
       13. The R-Q calculator of claim 1, wherein the R' delay path and the Q' delay path each comprise a memory element. 
     
     
       14. The R-Q calculator of claim 1, further comprising: in each R-Q circuit a delay element and an R memory element coupled in series between the R input and the R switch input; and   in each R-Q circuit a second delay element and a Q memory element coupled in series between the Q input and the Q switch input.   
     
     
       15. The R-Q calculator of claim 1, wherein the Q' bypass path and the Q' multiplexor directly couple the Q' switch output to the Q output. 
     
     
       16. The R-Q calculator of claim 1, wherein the error correction polynomials include an R polynomial that is input to the R input of a particular R-Q circuit and a Q polynomial that is input to the Q input of the particular R-Q circuit, wherein the switch in the particular R-Q circuit couples the R switch input to the R' switch output and the Q switch input to the Q' switch output when a degree of the R polynomial is no less than a degree of the Q polynomial, wherein the switch in the particular R-Q circuit couples the R switch input to the Q' switch output and the Q switch input to the R' switch output when the degree of the R polynomial is less than the degree of the Q polynomial and wherein a polynomial output from the R' switch output of the particular R-Q circuit is the R' polynomial for the particular R-Q circuit and a polynomial output from the Q' switch is the Q' polynomial for the particular R-Q circuit. 
     
     
       17. The R-Q calculator of claim 16, wherein the R' multiplexor in the particular R-Q circuit couples the R' switch output to the R output through the R' delay path when the leading coefficient of the Q' polynomial in the particular R-Q circuit is zero and wherein the R' multiplexor in the particular R-Q circuit couples the R' switch output to the R output through the R' calculation path when the leading coefficient of the Q' polynomial in the particular R-Q circuit is not zero. 
     
     
       18. The R-Q calculator of claim 17, wherein the Q' multiplexor in the particular R-Q circuit couples the Q' switch output to the Q output through the Q' delay path when the leading coefficient of the Q' polynomial in the particular R-Q circuit is not zero and wherein the Q' multiplexor in the particular R-Q circuit couples the Q' switch output to the Q output through the Q' bypass path when the leading coefficient of the Q' polynomial in the particular R-Q circuit is zero. 
     
     
       19. The R-Q calculator of claim 16, wherein the Q' multiplexor in the particular R-Q circuit couples the Q' switch output to the Q output through the Q' delay path when the leading coefficient of the Q' polynomial in the particular R-Q circuit is not zero and wherein the Q' multiplexor in the particular R-Q circuit couples the Q' switch output to the Q output through the Q' bypass path when the leading coefficient of the Q' polynomial in the particular R-Q circuit is zero. 
     
     
       20. The R-Q calculator of claim 1, wherein the R' calculation path comprises: a multiplier having a first input, a second input and an output;   a calculation path memory element having an output;   an adder having a first input, a second input and an output wherein the first input of the multiplier is coupled to the R' switch output, the second input of the multiplier is coupled to the output of the calculation path memory element, the output of the multiplier is coupled to the first input of the adder, the cross couple path is coupled to the second input of the adder and the output of the adder is coupled to the R' multiplexor.   
     
     
       21. The R-Q calculator of claim 20, wherein the cross couple path comprises: a cross couple memory element having an output;   a multiplier having a first input, a second input and an output wherein the output of the cross couple memory element is coupled to the first input of the multiplier, the Q' delay path is coupled to the second input of the multiplier and the output of the multiplier is coupled to the second input of the adder.   
     
     
       22. The R-Q calculator of claim 21, wherein the error correction polynomials include an R polynomial that is input to the R input of a particular R-Q circuit and a Q polynomial that is input to the Q input of the particular R-Q circuit, wherein the switch in the particular R-Q circuit couples the R switch input to the R' switch output and the Q switch input to the Q' switch output when a degree of the R polynomial is no less than a degree of the Q polynomial, wherein the switch in the particular R-Q circuit couples the R switch input to the Q' switch output and the Q switch input to the R' switch output when the degree of the R polynomial is less than the degree of the Q polynomial, wherein a polynomial output from the R' switch output of the particular R-Q circuit is the R' polynomial for the particular R-Q circuit and a polynomial output from the Q' switch output of the particular R-Q circuit is the Q' polynomial for the particular R-Q circuit, wherein the calculation path memory element stores the leading coefficient of the Q' polynomial and the cross couple memory element stores the leading coefficient of the R' polynomial. 
     
     
       23. The R-Q calculator of claim 22, wherein in the particular R-Q circuit the R' multiplexor couples the R' switch output to the R output through the R' delay path when the leading coefficient of the Q' polynomial is zero; and   in the particular R-Q circuit the R' multiplexor couples the R' switch output to the R output through the R' calculation path when the leading coefficient of the Q' polynomial is not zero.   
     
     
       24. The R-Q calculator of claim 22, wherein in the particular R-Q circuit the Q' multiplexor couples the Q' switch output to the Q output through the Q' delay path when the leading coefficient of the Q' polynomial is not zero; and   in the particular R-Q circuit the Q' multiplexor couples the Q' switch output to the Q output through the Q' bypass path when the leading coefficient of the Q' polynomial is zero.   
     
     
       25. The R-Q calculator of claim 24, wherein the R' delay path and the Q' delay path each comprise a memory element. 
     
     
       26. The R-Q calculator of claim 1, wherein the cross couple path comprises: a cross couple memory element having an output;   a multiplier having a first input, a second input and an output wherein the output of the cross couple memory element is coupled to the first input of the multiplier, the Q' delay path is coupled to the second input of the multiplier and the output of the multiplier is coupled to the R' calculation path.