Hardware-optimized reed-solomon decoder for large data blocks
First Claim
1. An error computation processor for use in a Reed Solomon decoder for computing the error locations and magnitudes of a large data block having a maximum of t errors over a desired Galois field, the processor comprising:
- first computing means for computing an error-locator polynomial and an error-evaluator polynomial; and
second computing means for computing the values of the errors whose location was determined to be in error;
wherein said first and second computing means requires only a first polynomial storage register, a second polynomial storage register, a first element storage register, a second element storage register, one multiplier for performing selected multiplication and division, one adder for performing selected addition and subtraction, an error location stack, an error value stack, and a syndrome register for storing the syndromes of the large data block.
2 Assignments
0 Petitions
Accused Products
Abstract
An error computation processor for use in a Reed Solomon decoder for computing the error locations and magnitudes of a large data block having a maximum of t errors over a desired Galois field. The processor can compute the error-locator polynomial, the error-evaluator polynomial, and the values of the errors whose location was determined to be in error with only two polynomial storage registers, two element storage registers, one multiplier for performing selected multiplication and division, one adder for performing selected addition and subtraction, one error locator stack, one error value stack, and a syndrome register for storing the syndromes of the large data block.
70 Citations
20 Claims
-
1. An error computation processor for use in a Reed Solomon decoder for computing the error locations and magnitudes of a large data block having a maximum of t errors over a desired Galois field, the processor comprising:
-
first computing means for computing an error-locator polynomial and an error-evaluator polynomial; and second computing means for computing the values of the errors whose location was determined to be in error; wherein said first and second computing means requires only a first polynomial storage register, a second polynomial storage register, a first element storage register, a second element storage register, one multiplier for performing selected multiplication and division, one adder for performing selected addition and subtraction, an error location stack, an error value stack, and a syndrome register for storing the syndromes of the large data block. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13)
-
-
14. An error computation processor for use in a Reed Solomon decoder for computing the error locations and magnitudes of a large data block having a maximum of t errors over a desired Galois field, the processor comprising:
-
first computing means for computing an error-locator polynomial and an error-evaluator polynomial; and second computing means for computing the values of the errors whose location was determined to be in error; wherein said first and second computing means includes a first polynomial storage register for storing up to t+1 bytes of the coefficients of the error locator polynomial; a second polynomial storage register for storing up to 2t bytes of the coefficients of the error evaluator polynomial and for storing the coefficients of B(x) during the execution of the Berlekamp-Massey algorithm; a first element storage register for computation of the discrepancy, for storing the normalized value of the discrepancy, for storing intermediate values during the computation of the individual coefficients of the error evaluator polynomial and for storing the results of the evaluation of the error evaluator polynomial; a second element storage register for storing a prior non-zero value of the discrepancy; a multiplier for performing selected multiplication and division; one adder for performing selected addition and subtraction; an error locator stack for storing the roots of the error locator polynomial; an error value stack for storing the magnitude of each error and for storing the derivative of the error locator polynomial during a Chien Search; and a syndrome register for storing the syndromes of the large data block. - View Dependent Claims (15, 16, 17, 18, 19)
-
-
20. A Reed Solomon decoder comprising:
-
syndrome computing means for receiving a large data block having a maximum of t errors and computing the syndromes of said large data block; an error computation processor for computing the error locations and magnitudes of said large data block, the processor including first computing means for computing an error-locator polynomial and an error-evaluator polynomial; and
second computing means for computing the values of the errors whose location was determined to be in error;
wherein said first and second computing means includes a first polynomial storage register for storing up to t+1 bytes of the coefficients of the error locator polynomial;
a second polynomial storage register for storing up to 2t bytes of the coefficients of the error evaluator polynomial;
a first element storage register for computation of the discrepancy;
a second element storage register for storing a prior non-zero value of the discrepancy;
one multiplier for performing selected multiplication and division;
one adder for performing selected addition and subtraction;
an error locator stack for storing the roots of the error locator polynomial;
an error value stack for storing the magnitude of each error; and
a syndrome register for storing the syndromes computed by said syndrome computing means;error correcting means for correcting said errors in said large data block; and a data delay for delaying the transmission of said data block to said error correcting means.
-
Specification