Single-bit first error correction
Embodiments include device, storage media, and methods for decoding a codeword of encoded data. In embodiments, a processor may be coupled with a decoder and configured to multiply the codeword and a parity-check matrix of the encoded data to produce a syndrome. If the syndrome is non-zero then the processor may identify a bit error in the codeword based at least in part on a comparison of the syndrome to one or more columns of the parity-check matrix. Other embodiments may be described and claimed.
1. An apparatus comprising:
a memory to store a codeword of an encoded data; and
a controller coupled with the memory to:
compute a syndrome of the encoded data when reading the encoded data from the memory;
determine whether the encoded data contains at least one bit of error based at least in part on the syndrome;
first attempt to correct the at least one bit of error with a single-bit correction process; and
second attempt to correct the at least one bit of error with a multi-bit correction process if the first attempt fails to correct the entire at least one bit of error due to the encoded data having multi-bit errors;
wherein compute a syndrome includes multiply a multi-column parity-check matrix and the codeword of the encoded data read from the memory to produce the syndrome of the encoded data;
wherein determine includes determine whether the syndrome is non-zero; and
wherein the first attempt includes identify a single bit error in the codeword of the encoded data based at least in part on a comparison of the non-zero syndrome to one or more columns of the parity-check matrix.
2. The apparatus of claim 1 , wherein the controller is to further identify a location of the bit error based at least in part on the comparison.
3. The apparatus of claim 1 , wherein the comparison comprises a binary tree comparison.
4. The apparatus of claim 1 , wherein the parity-check matrix is a binary matrix.
5. The apparatus of claim 1 , wherein the parity-check matrix comprises one or more elements based at least in part on a primitive polynomial of the codeword.
6. The apparatus of claim 5 , wherein an element in the one or more elements comprise an m×m matrix wherein m is an integer based at least in part on a number of possible values in the codeword.
7. The apparatus of claim 1 , wherein the codeword is a Bose-Ray-Chaudhuri (BCH) codeword or a Reed-Solomon (RS) codeword.
8. The apparatus of claim 1 , wherein the apparatus is a computing device further comprising
a number of processor cores coupled with the controller;
a solid state drive coupled with the controller, the solid state drive comprising the memory; and
a battery coupled with the controller.
9. The apparatus of claim 8 , wherein the apparatus is a personal digital assistant (PDA), a smartphone, a computing tablet, an e-reader, an ultrabook, a laptop computer, a desktop computer, a server, a set-top box, or a game console.
10. One or more non-transitory computer readable media comprising instructions to cause an apparatus, in response to execution of the instructions by the apparatus, to:
receive a codeword of an encoded data;
compute a syndrome of the encoded data using the codeword;
determine whether the encoded data contains at least one bit of error based at least in part on the syndrome;
first attempt to correct the at least one bit of error with a single-bit correction process; and
second attempt to correct the at least one bit of error with a multi-bit correction process if the first attempt fails to correct the entire at least one bit of error due to the encoded data having multi-bit errors;
wherein compute a syndrome includes multiply a multi-column parity-check matrix and the codeword to identify the syndrome of the encoded data;
wherein determine includes determine whether the syndrome is non-zero; and
wherein first attempt includes identify a single bit error in the codeword based at least in part on a comparison of the non-zero syndrome to one or more columns of the parity-check matrix.
11. The one or more computer readable media of claim 10 , wherein the instructions are to further e-cause the apparatus, in response to execution of the instructions by the apparatus, to identify a location of the bit error in the codeword based at least in part on the comparison.
12. The one or more computer readable media of claim 10 , wherein the comparison comprises a binary tree comparison.
13. The one or more computer readable media of claim 10 , wherein the parity-check matrix comprises one or more elements based at least in part on a primitive polynomial of the codeword.