BCH or reed-solomon decoder with syndrome modification

• US 8,397,143 B2
• Filed: 11/24/2009
• Issued: 03/12/2013
• Est. Priority Date: 05/22/2009
• Status: Expired due to Fees

• Current Assignee: Intel Corporation
• Original Assignee: LSI Corporation (Broadcom, Inc.)
• Inventors: Neznanov, Ilya V., Gasanov, Elyar E., Panteleev, Pavel A., Aliseychik, Pavel A., Sokolov, Andrey P.
• Primary Examiner(s): Ehne, Charles
• Application Number:
  US12/624,664
• Publication Number:
  US 20100299580A1
• Time in Patent Office: 1,204 Days
• Field of Search: 714/784, 714/785
• US Class Current: 714/785
• CPC Class Codes: H03M 13/151 using error location or error correction polynomials
• CPC Class Codes: H03M 13/6508 Flexibility, adaptability, parametrability and configurability of the implementation

Abstract

An apparatus generally having a first circuit, a second circuit and a third circuit is disclosed. The first circuit may be configured to calculate a plurality of preliminary syndromes from a plurality of received symbols. The second circuit may be configured to calculate a plurality of normal syndromes by modifying the preliminary syndromes using at most two Galois Field multiplications. The third circuit is generally configured to calculate an errata polynomial based on the normal syndromes.

Claims

1. An apparatus comprising:

a first circuit configured to calculate a plurality of preliminary syndromes from a plurality of received symbols;

a second circuit configured to calculate a plurality of normal syndromes by modifying said preliminary syndromes using at most two Galois Field multipliers, and

a third circuit configured to calculate an errata polynomial based on said normal syndromes.

2. The apparatus according to claim 1, wherein said second circuit comprises a plurality of shift registers configured to received said preliminary syndromes in parallel from said first circuit.

3. The apparatus according to claim 1, wherein said second circuit comprises a modification circuit configured to calculate one of said normal syndromes based on one of said preliminary syndromes in a first of a plurality of shift registers.

4. The apparatus according to claim 3, wherein said one normal syndrome is transferred from said modification circuit to said third circuit.

5. The apparatus according to claim 1, wherein said second circuit comprises a plurality of shift registers and a modification circuit connected to shift (i) said preliminary syndromes by one of said shift registers, except one of said preliminary syndromes in a first of said shift registers and (ii) one of said normal syndromes from said modification circuit to a second of said shift registers.

6. The apparatus according to claim 1, wherein said second circuit comprises (i) a register configured to buffer a multiplication factor and (ii) a first Galois Field multiplier configured to calculate said one normal syndrome by multiplying one of said preliminary syndromes by said multiplication factor.

7. The apparatus according to claim 6, wherein said second circuit further comprises a second Galois Field multiplier configured to calculated an updated version of said multiplication factor.

8. The apparatus according to claim 6, wherein said first Galois field multiplier is further configured to alternate between calculating (i) said one normal syndrome and (ii) an updated version of said multiplication factor.

9. The apparatus according to claim 1, further comprising a fourth circuit configured to calculate a plurality of recovered symbols by correcting said received symbols with said errata polynomial.

10. The apparatus according to claim 1, wherein said apparatus forms at least one of (i) a BCH decoder and (ii) a Reed-Solomon decoder.

11. A method for decoding with syndrome modification, comprising the steps of:

(A) calculating a plurality of preliminary syndromes from a plurality of received symbols;

(B) calculating a plurality of normal syndromes by modifying said preliminary syndromes using at most two Galois Field multipliers, and

(C) calculating an errata polynomial based on said normal syndromes using a solver circuit.

12. The method of claim 11, wherein step (B) comprises the sub-step of:

loading said preliminary syndromes in parallel into a plurality of shift registers.

13. The method according to claim 11, wherein step (B) comprises the sub-step of:

calculating one of said normal syndromes in a modification circuit based on one of said preliminary syndromes in a first of a plurality of shift registers.

14. The method according to claim 13, wherein step (B) further comprises the sub-step of:

transferring said one normal syndrome from said modification circuit to said solver circuit.

15. The method according to claim 11, wherein step (B) comprises the sub-step of:

shifting (i) said preliminary syndromes by one of a plurality of shift registers, except one of said preliminary syndromes in a first of said shift resisters, and (ii) one of said normal syndromes from a modification circuit to a second of said shift registers.

16. The method according to claim 15, wherein said shifting is repeated until all of said normal syndromes have been calculated.

17. The method according to claim 11, wherein said at most two Galois field multipliers is a single Galois Field multiplier.

18. The method according to claim 11, wherein step (C) calculates an error locator polynomial in a plurality of iterations starting from a polynomial of degree zero.

19. The method according to claim 11, further comprising the step of:

calculating a plurality of recovered symbols by correcting said received symbols with said errata polynomial.

20. An apparatus comprising:

means for calculating a plurality of preliminary syndromes from a plurality of received symbols;

means for calculating a plurality of normal syndromes by modifying said preliminary syndromes using at most two Galois Field multipliers; and

means for calculating an errata polynomial based on said normal syndromes.