High-speed syndrome calculation
First Claim
1. A method of calculating a syndrome using a dividend polynomial, a generator polynomial, and a pre-computed multiplication table of the products of the generator polynomial stored in the memory of a programmable computer comprising the steps of:
- calculating a remainder polynomial from the division of the dividend polynomial by the generator polynomial using the pre-computed multiplication table, the remainder polynomial being of lower order than the generator polynomial;
calculating the syndrome using the lower-order remainder polynomial and the generator polynomial;
splitting the generator polynomial into a plurality of generator sub-polynomials, the generator sub-polynomial being factors of the generator polynomial; and
dividing by the plurality of generator sub-polynomials to form a plurality of remainder sub-polynomials;
wherein a computation time of the step of calculating the remainder polynomial depends primarily on the order of the dividend polynomial.
6 Assignments
0 Petitions
Accused Products
Abstract
A method and device for calculating syndromes used in forward-error-correction codes. To calculate syndromes more quickly using a computer with memory access latency, the polynomial equation C(X) is divided by a generator polynomial G(X) to form a remainder polynomial R(X). The remainder polynomial R(X) is then used to speed the calculation of the syndromes. A method of dividing a Nth order dividend polynomial by a 2R order divisor polynomial is also described. In addition, to further speed the calculation of syndromes, the generating polynomial is split into a number of sub-polynomials Gj (X) to yield a number of remainder sub-polynomials Rj (X) used to calculate the syndromes. Calculation of syndromes using evaluation by Horner'"'"'s rule and a generalization thereof is also described.
52 Citations
45 Claims
-
1. A method of calculating a syndrome using a dividend polynomial, a generator polynomial, and a pre-computed multiplication table of the products of the generator polynomial stored in the memory of a programmable computer comprising the steps of:
-
calculating a remainder polynomial from the division of the dividend polynomial by the generator polynomial using the pre-computed multiplication table, the remainder polynomial being of lower order than the generator polynomial; calculating the syndrome using the lower-order remainder polynomial and the generator polynomial; splitting the generator polynomial into a plurality of generator sub-polynomials, the generator sub-polynomial being factors of the generator polynomial; and dividing by the plurality of generator sub-polynomials to form a plurality of remainder sub-polynomials; wherein a computation time of the step of calculating the remainder polynomial depends primarily on the order of the dividend polynomial. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21)
-
-
22. A device for calculating a polynomial to form a plurality of syndromes for decoding transmitted data comprising:
-
a polynomial division means for calculating a remainder polynomial from the division of the polynomial with a generator polynomial to calculate a remainder polynomial of lower order than the generator polynomial; and a polynomial calculation means for evaluating said remainder polynomial at the plurality of first order factors of the generator polynomial to form a plurality of syndromes, wherein the polynomial calculation means further comprises; a splitter for splitting the remainder polynomial into a plurality of sub-polynomial equations; a plurality of accumulators in communication with the splitter for evaluating the sub-polynomial equations of the remainder polynomial; an adder in communication with a corresponding one of the plurality of accumulators for adding to the sub-polynomial equations in the plurality of accumulators; a multiplier in communication with a corresponding one of the plurality of accumulators for multiplying the sub-polynomial equations in the plurality of accumulators; control logic to control the adder and multiplier to carry out Horner'"'"'s rule on the sub-polynomials; a final multiplier in communication with a corresponding one of a plurality of accumulators for multiplying accumulator values; and a summer in communication with final multiplier values and yield the result of the polynomial evaluation. - View Dependent Claims (23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44)
-
-
45. A method of calculating a syndrome using a dividend polynomial, a generator polynomial, and a pre-computed multiplication table of the products of the generator polynomial stored in the memory of a programmable computer comprising the steps of:
-
calculating a remainder polynomial from the division of the dividend polynomial by the generator polynomial using the pre-computed multiplication table, the remainder polynomial being of lower order than the generator polynomial; and calculating the syndrome using the lower-order remainder polynomial and the generator polynomial; wherein the step of calculating the remainder polynomial further comprises an iterative procedure comprising the steps of; multiplying the generator polynomial to form a product of the generator polynomial using the multiplication table stored in computer memory; subtracting the product of the generator polynomial from a remainder to form a new remainder; multiplying the generator polynomial to form a new product using the multiplication table stored in computer memory; subtracting the new product from the new remainder to form a newer remainder; and repeating the iterative procedure continues until the product of the generator polynomial can no longer be subtracted from the remainder from the previous iteration; wherein the subtracting step from a previous iteration is performed by the computer processor during a time when the latent memory operation is accessing the multiplication table for the next iteration.
-
Specification