Error detection and correction using error pattern correcting codes
In general, the disclosure describes techniques for detecting and correcting single or multiple occurrences of data error patterns. This disclosure discusses the generation and application of high-rate error-pattern-correcting codes to correct single instances of targeted error patterns in codewords, and to further correct a significant portion of multiple instances of targeted error patterns, with the least redundancy. In accordance with the techniques, a lowest-degree generator polynomial may be constructed that targets a set of dominant error patterns that make up a very large percentage of all observed occurrences of errors. The lowest-degree generator polynomial produces distinct, non-overlapping syndrome sets for the target error patterns. The lowest-degree generator polynomial may be constructed such that no two error patterns within the list of dominant error patterns map to the same syndrome set, and the single occurrence and starting position of any of the target error patterns can be successfully identified.
1. A method comprising:
receiving a message in an electronic communication system; and
generating a codeword based on the message and a generator polynomial g(x) that contains an irreducible factor that is present in a set of targeted error polynomials that represent one or more targeted error patterns,
wherein the generator polynomial g(x) is of a form g(x)=g′(x)p′(x), where g′(x) is a preliminary generator polynomial selected such that there exist a plurality of distinct syndrome sets for the targeted error patterns, and p′(x) is an external factor that is not a factor of any error polynomial in the set of targeted error polynomials.
2. The method of claim 1 , wherein each of the syndrome sets corresponds with only one of the targeted error patterns of the set of targeted error patterns and one or more possible starting positions for the corresponding targeted error pattern.
3. The method of claim 1 , further comprising:
identifying one of a string of consecutive ones, a string of consecutive zeros and a string of alternating ones and zeros within the generated codeword that exceeds a threshold string length; and
forcing an error pattern within the generated codeword.
4. The method of claim 3 , wherein forcing an error pattern within the generated codeword comprises forcing an error pattern that may be removed at a receiver side.
5. The method of claim 3 , wherein the forced error pattern comprises one of the targeted error patterns.
6. The method of claim 1 , further comprising transmitting the codeword via a communication interface.
7. The method of claim 1 , further comprising storing the codeword on a data storage medium.
8. A device comprising an encoding module that receives a message and generates a codeword based on the message and a generator polynomial g(x) that contains an irreducible factor that is present in a set of targeted error polynomials that represent one or more targeted error patterns, wherein the generator polynomial g(x) is of a form g(x)=g′(x)p′(x), where g′(x) is a preliminary generator polynomial selected such that there exist a plurality of distinct syndrome sets for the targeted error patterns, and p′(x) is an external factor that is not a factor of any error polynomial in the set of targeted error polynomials.
9. The device of claim 8 , further comprising a data storage medium, wherein the encoding module writes the generated codeword to the data storage medium.
10. The device of claim 8 , further comprising a transmitter that transmits the generated codeword to a communication network.
11. The device of claim 8 , wherein each of the syndrome sets corresponds with only one of the targeted error patterns of the set of targeted error patterns and one or more possible starting positions for the corresponding targeted error pattern.
12. The device of claim 8 , wherein the encoding module identifies one of a string of consecutive ones, a string of consecutive zeros, and a string of alternating ones and zeros within the generated codeword that exceeds a threshold string length and forces an error pattern within the generated codeword.
13. The device of claim 12 , wherein forcing an error pattern within the generated codeword comprises forcing an error pattern that may be removed at a receiver side.
14. The device of claim 12 , wherein the forced error pattern comprises one of the targeted error patterns.
15. A non-transitory computer-readable medium comprising instructions that, when executed, cause one or more processors to:
receive a message in an electronic communication system; and
generate a codeword based on the message and a generator polynomial g(x) that contains an irreducible factor that is present in a set of targeted error polynomials that represent one or more targeted error patterns,
wherein the generator polynomial g(x) is of a form g(x)=g′(x)p′(x), where g′(x) is a preliminary generator polynomial selected such that there exist a plurality of distinct syndrome sets for the targeted error patterns, and p′(x) is an external factor that is not a factor of any error polynomial in the set of targeted error polynomials.
16. The non-transitory computer-readable medium of claim 15 , wherein the generator polynomial g(x) is of a form g(x)=g′(x)p′(x), where g′(x) is a preliminary generator polynomial selected such that there exist a plurality of distinct syndrome sets for the targeted error patterns, and p′(x) is an external factor that is not a factor of any error polynomial in the set of targeted error polynomials.
17. The non-transitory computer-readable medium of claim 16 , wherein each of the syndrome sets corresponds with only one of the targeted error patterns of the set of targeted error patterns and one or more possible starting positions for the corresponding targeted error pattern.
18. An apparatus comprising:
means for receiving a message in an electronic communication system; and
means for generating a codeword based on the message and a generator polynomial g(x) that contains an irreducible factor that is present in a set of targeted error polynomials that represent one or more targeted error patterns,
wherein the generator polynomial g(x) is of a form g(x)=g′(x)p′(x), where g′(x) is a preliminary generator polynomial selected such that there exist a plurality of distinct syndrome sets for the targeted error patterns, and p′(x) is an external factor that is not a factor of any error polynomial in the set of targeted error polynomials.
19. The apparatus of claim 18 , wherein each of the syndrome sets corresponds with only one of the targeted error patterns of the set of targeted error patterns and one or more possible starting positions for the corresponding target error pattern.
20. The apparatus of claim 18 , further comprising:
means for identifying one of a string of consecutive ones, a string of consecutive zeros and a string of alternating ones and zeros within the generated codeword that exceeds a threshold string length; and
means for forcing an error pattern within the generated codeword.
21. The apparatus of claim 20 , wherein means for forcing an error pattern within the generated codeword comprises means for forcing an error pattern that may be removed at a receiver side.
22. The apparatus of claim 20 , wherein the forced error pattern comprises one of the targeted error patterns.
23. The apparatus of claim 18 , further comprising means for transmitting the codeword via a communication interface.
24. The apparatus of claim 23 , further comprising means for storing the codeword on a data storage medium.