High-speed syndrome calculation

• US 6,219,815 B1
• Filed: 02/18/2000
• Issued: 04/17/2001
• Est. Priority Date: 01/20/1998
• Status: Expired due to Term

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: 3Com Corporation (HP Inc.)
• Inventors: DesJardins, Philip A., Mantri, Ravi G.
• Primary Examiner(s): Decady, Albert
• Assistant Examiner(s): Lamarre, Guy J.
• Application Number:
  US09/506,995
• Time in Patent Office: 424 Days
• Field of Search: 714/752, 714/781, 714/784-785, 714/759, 714/761, 714/782, 708/492
• US Class Current: 714/781
• CPC Class Codes: H03M 13/151 using error location or error correction polynomials

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 G_j(X) to yield a number of remainder sub-polynomials R_j(X) used to calculate the syndromes. Calculation of syndromes using evaluation by Horner'"'"'s rule and a generalization thereof is also described.

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.

2. The “

method”

of claim 1 wherein the divisor polynomial comprises a generator polynomial used in a FEC.

3. The “

method”

of claim 1 wherein the dividend polynomial corresponds to transmitted symbols in a transmission system.