BCH decoding with multiple sigma polynomial calculation algorithms
View Patent ↗Bose-Chaudhuri-Hocquenghem (BCH) decoder architectures which execute a plurality of different algorithms to calculate an error location polynomial. The multiple algorithms may be implemented in a storage controller for increased throughput per gate count. Codewords needing up to a threshold number of corrections may be processed via a first algorithm while those with a greater number of corrections may be processed via the second algorithm. In embodiments, the Peterson-Gorenstein-Zierler (PGZ) algorithm and the Berlekamp-Massey algorithm (BMA) are executed either serially or in parallel to increase throughput of the decoder.
1. A Bose-Chaudhuri-Hocquenghem (BCH) decoder, comprising:
a first engine to calculate, by a first algorithm, an error locator polynomial from a BCH syndrome of a received codeword;
a second engine to calculate, by a second algorithm, the error locator polynomial from the BCH syndrome of the received codeword; and
circuitry to output data based on the error locator polynomial from either the first engine or the second engine.
2. The decoder of the claim 1 , wherein the first engine comprises hardware limited to processing a number of corrections no greater than a threshold, wherein the error locator polynomial is output from either the first engine or the second engine depending on a number of errors detected from the BCH syndrome.
3. The decoder of claim 2 , wherein the threshold is 1,2, or 3 errors.
4. The decoder of claim 1 , wherein the first algorithm is a Peterson-Gorenstein-Zierler (PGZ) algorithm.
5. The decoder of claim 4 , wherein the second algorithm is a Berlekamp-Massey Algorithm (BMA).
6. The decoder of claim 1 , wherein the first and second engines are in parallel, both engines to receive the BCH syndrome from a syndrome calculator at substantially the same time.
7. The decoder of claim 1 , wherein the first and second engines are in series, the first engine to receive the BCH syndrome from a syndrome calculator and the second engine to receive the BCH syndrome only in response to the number of errors exceeding the threshold.
8. The decoder of claim 1 , wherein at least one of the first engine and second engine comprises multiple instantiations of a same engine type to process multiple BCH syndromes in parallel.
9. The decoder of claim 1 , further comprising a first Chien search circuitry coupled to the first engine to receive the output data and a second Chien search circuitry coupled to the second engine to receive the output data.
10. The decoder of claim 9 , wherein the first Chien search circuitry has a substantially wider register width than the second Chien search circuitry.
11. The decoder of claim 1 , wherein the first engine further comprises a first arithmetic logic unit (ALU) and a first state machine to control the first ALU, and wherein the second engine further comprises a second ALU and a second state machine to control the second ALU.
12. An apparatus, comprising:
a storage device interface to receive a codeword from a storage device;
a Bose-Chaudhuri-Hocquenghen (BCH) decoder to locate bit errors in the codeword, wherein the BCH decoders further comprises:
a first engine to calculate, by a first algorithm, an error locator polynomial from a BCH syndrome of the codeword;
a second engine to calculate, by a second algorithm, the error locator polynomial from the BCH syndrome of the codeword; and
a host interface to output data based on the codeword to a host device.
13. The apparatus of claim 12 , further comprising:
a codeword buffer to store the codeword while the bit errors are located;
logic to correct a codeword bit error determined from the error locator polynomial; and
circuitry to output the corrected codeword to the host interface.
14. The apparatus of claim 12 , further comprising the storage device, wherein the storage device comprises a non-volatile semiconductor-based memory.
15. A method for correcting errors in a codeword, the method comprising:
receiving a BCH syndrome of the codeword;
calculating an error locator polynomial by processing the BCH syndrome with at least one of a first algorithm and a second algorithm depending on a number of errors detected from the BCH syndrome exceeding a threshold; and
calculating a bit error location by determining roots of the error locator polynomial.
16. The method of claim 15 , wherein calculating the error locator polynomial further comprises:
processing the BCH syndrome with the first algorithm;
determining if the number of codeword errors exceeds a threshold; and
processing the BCH syndrome with the second algorithm in response to the number of codeword errors exceeding the threshold.
17. The method of claim 15 , wherein the BCH syndrome is processed with the first algorithm in parallel with the second algorithm and wherein the second algorithm is terminated upon determining the number of codeword errors does not exceed the threshold.
18. The method of claim 15 , wherein the BCH syndrome is processed with the first algorithm before it is processed with the second algorithm.
19. The method of claim 15 , further comprising:
performing a Chien search to determine the roots of the error locator polynomial, the Chien search performed with circuitry having a register width dependent upon whether the first or second algorithm is used for calculating the error locator polynomial.
20. The decoding method of claim 15 , wherein the first algorithm is a Peterson-Gorenstein-Zierler (PGZ) algorithm and wherein the second algorithm is a Berlekamp-Massey Algorithm (BMA), and wherein the threshold is 1, 2, or 3 errors.
21. A system, comprising:
a host device having a first antenna;
a storage device interface to receive a codeword from a storage device;
a Bose-Chaudhuri-Hocquenghem (BCH) decoder to locate bit errors in the codeword, wherein the BCH decoders further comprises:
a first engine to calculate, by a first algorithm, an error locator polynomial from a BCH syndrome of the codeword;
a second engine to calculate, by a second algorithm, the error locator polynomial from the BCH syndrome of the codeword; and
a second antenna to output data based on the codeword to the host device.
22. The system as in claim 21 , wherein the host device is a wireless access point coupled to a wired network.
23. The system as in claim 21 , wherein the first algorithm is a Peterson-Gorenstein-Zierler (PGZ) algorithm and wherein the second algorithm is a Berlekamp-Massey Algorithm (BMA).