High-speed syndrome calculation
First Claim
1. A method of dividing a dividend polynomial by a divisor polynomial using a table of pre-computed products of the generating polynomial using a programmable computer that returns a partial product of the most significant symbols and a partial product of the lessor significant symbols from the table of pre-computed products, comprising the steps of iteratively:
- indexing the table of pre-computed multiples of the dividend polynomial for a product of the dividend polynomial;
obtaining the partial product of the most significant symbols from the step of indexing, the partial product containing the most significant symbols of the product of the dividend polynomial;
subtracting the most significant symbols of the partial product from a remainder to form the most significant symbols of a new remainder before obtaining a second partial product of the lessor significant symbols from the step of indexing, the second partial product containing the lessor significant symbols of the product of the dividend polynomial; and
indexing into the table of the pre-computed multiples of the dividend polynomial using the most significant symbols of the new remainder to form a new partial product;
wherein the subtracting step from a previous iteration is performed during a time when a latent memory operation is accessing the table of pre-computed products for the next iteration.
5 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.
-
Citations
3 Claims
-
1. A method of dividing a dividend polynomial by a divisor polynomial using a table of pre-computed products of the generating polynomial using a programmable computer that returns a partial product of the most significant symbols and a partial product of the lessor significant symbols from the table of pre-computed products, comprising the steps of iteratively:
-
indexing the table of pre-computed multiples of the dividend polynomial for a product of the dividend polynomial;
obtaining the partial product of the most significant symbols from the step of indexing, the partial product containing the most significant symbols of the product of the dividend polynomial;
subtracting the most significant symbols of the partial product from a remainder to form the most significant symbols of a new remainder before obtaining a second partial product of the lessor significant symbols from the step of indexing, the second partial product containing the lessor significant symbols of the product of the dividend polynomial; and
indexing into the table of the pre-computed multiples of the dividend polynomial using the most significant symbols of the new remainder to form a new partial product;
wherein the subtracting step from a previous iteration is performed during a time when a latent memory operation is accessing the table of pre-computed products for the next iteration. - View Dependent Claims (2, 3)
-
Specification