Encoding with integrated error-detection

• US 9,455,745 B2
• Filed: 02/21/2013
• Issued: 09/27/2016
• 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
• Primary Examiner(s): Bonzo, Bryce
• Assistant Examiner(s): NGUYEN, THIEN DANG
• Application Number:
  US13/773,329
• Publication Number:
  US 20140237316A1
• Time in Patent Office: 1,314 Days
• US Class Current: 1/1
• 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 computing device for decoding encoded data, the computing device including:

a logic machine; and

a storage machine storing instructions executable by the logic machine to;

receive, from an encoder, the encoded data including a plurality of n+2-bit code words and an error correction symbol;

determine, at a physical layer of the computing device, that a first n+2-bit code word of the plurality of n+2-bit code words includes an error responsive to determining that the first n+2-bit code word has a Hamming distance of one relative to a valid n+2-bit code word;

responsive to determining that the first n+2-bit code word includes an error, mark, with the physical layer, the first n+2-bit code word as an invalid code word and pass the marked first n+2-bit code word with the plurality of n+2-bit code words to a higher layer of the computing device than the physical layer;

receive, at the higher layer of the computing device, the marked first n+2-bit code word with the plurality of n+2-bit code words and the error correction symbol;

correct, at the higher layer of the computing device, the first n+2-bit code word based on the error correction symbol; and

output a plurality of n-bit data symbols recovered from the plurality of encoded n+2-bit code words.

2. The computing device of claim 1, wherein the instructions are further executable to recover the plurality of n-bit data symbols by matching each of the plurality of encoded n+2-bit code words, including the corrected first n+2-bit code word, to a corresponding n-bit source symbol in a table, the table mapping valid code words to source symbols.

3. The system of claim 1, wherein the first n+2-bit code word and the valid n+2-bit code word include any two code words of the plurality of n+2-bit code words.

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

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

6. The system of claim 1, wherein each of the plurality of n+2-bit code words includes ten bits and each of the corresponding n-bit data symbols includes eight bits, and where the valid n+2-bit code word is one of a plurality of valid n+2-bit code words included in a table mapping each of the plurality of valid n+2-bit code words to a corresponding n-bit source symbol.

7. The system of claim 1, wherein the higher layer of the computing device includes the link layer of the computing device.

8. On a computing device, a method of recovering pre-coded n-bit data symbols from encoded data, where n is a positive integer number of bits, the method comprising:

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

determining, at a physical layer of the computing device, that an n+2-bit code word includes a single bit error responsive to determining that the n+2-bit code word has a Hamming distance of one relative to a valid n+2-bit code word;

marking, at the physical layer of the computing device, the n+2-bit code word that is determined to be an invalid code word;

correcting, at a higher layer of the computing device than the physical layer, the n+2-bit code word based on the error correction symbol; and

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

9. The method of claim 8, wherein the error correction symbol is a checksum symbol.

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

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

12. The method of claim 8, further comprising receiving a table of valid code words.

13. The method of claim 12, 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.

14. On a computing device, a method for decoding encoded data, the method comprising:

receiving, from an encoder, the encoded data including a plurality of n+2-bit code words and an error correction symbol;

determining, at a physical layer of the computing device, that a first n+2-bit code word of the plurality of n+2-bit code words includes an error responsive to determining that the first n+2-bit code word has a Hamming distance of one relative to a valid n+2-bit code word;

responsive to determining that the first n+2-bit code word includes an error, marking, with the physical layer, the first n+2-bit code word as an invalid code word and passing the marked first n+2-bit code word with the plurality of n+2-bit code words to a higher layer of the computing device than the physical layer;

receiving, at the higher layer of the computing device, the marked first n+2-bit code word with the plurality of n+2-bit code words and the error correction symbol;

correcting, at the higher layer of the computing device, the first n+2-bit code word based on the error correction symbol; and

outputting a plurality of n-bit data symbols recovered from the plurality of encoded n+2-bit code words.

15. The method of claim 14, wherein each of the plurality of n+2-bit code words includes ten bits and each of the corresponding n-bit data symbols includes eight bits, and where the valid n+2-bit code word is one of a plurality of valid n+2-bit code words included in a table mapping each of the plurality of valid n+2-bit code words to a corresponding n-bit source symbol.

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

17. The method of claim 14, 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.

18. The method of claim 14, wherein each of the plurality of n+2-bit code words includes at most six consecutive bits of the same value.

19. The method of claim 14, wherein the higher layer of the computing device includes the link layer of the computing device.

20. The method of claim 14, further comprising recovering the plurality of n-bit data symbols by matching each of the plurality of encoded n+2-bit code words, including the corrected first n+2-bit code word, to a corresponding n-bit source symbol in a table, the table mapping valid code words to source symbols.