ENCODING WITH INTEGRATED ERROR-DETECTION

• US 20140237316A1
• Filed: 02/21/2013
• Published: 08/21/2014
• Est. Priority Date: 02/21/2013
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Tantos, Andras
• Granted Patent: US 9,455,745 B2
• Time in Patent Office: Days
• US Class Current: 714/758
• CPC Class Codes: H03M 13/05 using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits H03M13/2906 takes precedence
• CPC Class Codes: H03M 13/31 combining coding for error detection or correction and efficient use of the spectrum without error detection or correction H03M5/14 , H03M5/145
• CPC Class Codes: H03M 5/145 Conversion to or from block codes or representations thereof

Abstract

A method of encoding a data set including one or more n-bit pre-coded symbols in an encoder of a computing system includes determining a plurality of n+2-bit code words, each of the plurality of n+2-bit code words having two or greater Hamming distance from one another. The method further includes mapping each of the plurality of n+2-bit code words to a corresponding source symbol, receiving the one or more n-bit pre-coded symbols at the encoder, matching each n-bit pre-coded symbol to a corresponding n+2-bit code word based on the mapping to produce encoded data. and outputting the encoded data.

Claims

1. A method of encoding a data set including one or more n-bit pre-coded symbols in an encoder of a computing system, the method comprising:

determining a plurality of n+2-bit code words, each of the plurality of n+2-bit code words having two or greater Hamming distance from one another;

mapping each of the plurality of n+2-bit code words to a corresponding source symbol;

receiving the one or more n-bit pre-coded symbols at the encoder;

matching each n-bit pre-coded symbol to a corresponding n+2-bit code word based on the mapping to produce encoded data; and

outputting the encoded data.

2. The method of claim 1, further comprising outputting an error correction symbol, the error correction symbol particular to the encoded data.

3. The method of claim 2, wherein the error correction symbol comprises a checksum for the encoded data.

4. The method of claim 2, wherein the error correction symbol comprises a cyclic redundancy check (CRC) symbol for the encoded data or an XOR sum of bits of the encoded data.

5. The method of claim 1, wherein each of the plurality of code words includes ten bits and each of the corresponding source symbols includes eight bits.

6. The method of claim 1, wherein the plurality of code words includes 256 data codes and 14 control codes.

7. The method of claim 1, wherein each of the plurality of code words includes at most six consecutive bits of the same value.

8. The method of claim 1, further comprising generating a table of valid code words including the plurality of n+2-bit code words and outputting the table of valid code words.

9. An encoding system comprising:

a logic machine; and

a storage machine configured to store instructions executable by the logic machine to;

generate a plurality of code words, each of the plurality of n+2-bit code words having two or greater Hamming distance from one another; and

map each of the plurality of n+2-bit code words to a corresponding source symbol.

10. The system of claim 9, the instructions further executable to transmit an error correction symbol to a computing device, the error correction symbol particular to the encoded data.

11. The system of claim 10, wherein the error correction symbol comprises a checksum for the encoded data.

12. The system of claim 10, wherein the error correction symbol comprises a cyclic redundancy check (CRC) symbol for the encoded data.

13. The system of claim 9, wherein each of the plurality of code words includes ten bits and each of the corresponding source symbols includes eight bits.

14. The system of claim 9, wherein the plurality of code words includes 256 data codes and 14 control codes.

15. A method of recovering pre-coded n-bit data symbols from encoded data, the method comprising:

receiving the encoded data including one or more n+2-bit code words and an error correction symbol;

determine that an n+2-bit code word includes a single bit error responsive to determining that the n+2-bit code word is an invalid code word;

correct the n+2-bit code word based on the error correction symbol; and

recover the n-bit data symbols from the encoded data.

16. The method of claim 15, wherein the error correction symbol is a checksum symbol.

17. The method of claim 15, wherein the error correction symbol is a cyclic redundancy check (CRC) symbol.

18. The method of claim 15, wherein the n-bit data symbols include 8 bits and the n+2-bit code words include 10 bits.

19. The method of claim 15, further comprising receiving a table of valid code words.

20. The method of claim 19, wherein determining that the n+2-bit code word is an invalid code word comprises comparing the n+2-bit code word to the table of valid code words.