Codebook to reduce error growth arising from channel errors
Techniques for limiting the growth of errors in decoded data words that arise from bit errors incurred during transmission. The growth of 3+ bit errors in the decoded data word is limited at the expense of a higher number of two bit errors, which are correctable using practical error correcting codes.
1. A method comprising:
generating a first codebook by assigning codewords to data words, wherein:
each codeword that is assigned has a Hamming Distance (HD) of one with respect to a data word to which the codeword is assigned;
the data word to which the codeword is assigned has a Hamming Distance less than or equal to two with respect to data words already having codewords assigned; and
utilizing the first codebook to encode data for transmission on a data bus.
2. The method of claim 1 , wherein:
utilizing the first codebook to encode the data words into the codewords after a cyclic redundancy check (CRC) value is computed on the data words; and
the cyclic redundancy check value is transmitted in association with the encoded data on the data bus.
3. The method of claim 1 , further comprising:
forming a first set of the data words satisfying HD(x, y)≤2 for an unassigned codeword; and
sorting the first set of data words such that data words satisfying HD(x, y)=1 have a higher priority for assignment of a codeword;
wherein HD(x) is a data-word-to-decoded-codeword Hamming Distance, HD(y) is a codeword-to-channel-error Hamming Distance, and HD(x,y) is a data-word-to-code-word Hamming Distance.
4. The method of claim 3 , further comprising:
forming a second set of data words satisfying HD(x)≤2 with respect to one another; and
determining an intersection set of the first set of data words and the second set of data words.
5. The method of claim 4 , further comprising:
determining an unassigned codeword from the intersection set that satisfies HD(y)=1 for data words in the intersection set subject to a constraint that a data word to assign to the codeword satisfies HD(x)<=2 with respect to data words that are already assigned to codewords.
6. The method of claim 1 , further comprising:
inverting the first codebook to generate a second codebook to encode the data for transmission on a data bus.
7. The method of claim 1 , further comprising:
determining if an inversion of a most significant bit (MSB) of a transmitted codeword has occurred; and
on condition that the MSB inversion has occurred, retransmitting the transmitted codeword.
8. The method of claim 7 , wherein determining if the MSB inversion occurred comprises comparing a cyclic redundancy check (CRC) for the transmitted data word generated before transmission with a CRC for the transmitted data word generated after decoding.
9. A system comprising:
a first digital component;
a second digital component coupled to the first digital component via a data bus; and
an encoder utilizing a first codebook generated by assigning codewords to data words communicated between the first digital component and the second digital component over the bus, each codeword that is assigned having a Hamming Distance (HD) of one with respect to an assigned data word for the codeword; and
wherein each of the data words has a Hamming Distance less than or equal to two relative to other data words to which codewords are assigned.
10. The system of claim 9 , further comprising:
the encoder disposed between a cyclic redundancy check (CRC) generator and the bus, such that the first codebook is utilized by the encoder to encode the data words into the codewords after a cyclic redundancy check value is computed on the data words by the CRC generator.
11. The system of claim 9 , the first codebook generated by further:
forming a first set of the data words satisfying HD(x, y)≤2 for an unassigned codeword; and
sorting the first set of data words such that data words satisfying HD(x, y)=1 have a higher priority for assignment of a codeword;
wherein HD(x) is a data-word-to-decoded-codeword Hamming Distance, HD(y) is a codeword-to-channel-error Hamming Distance, and HD(x,y) is a data-word-to-code-word Hamming Distance.
12. The system of claim 11 , the first codebook generated by further:
forming a second set of data words satisfying HD(x)≤2 with respect to one another; and
determining an intersection set of the first set of data words and the second set of data words.
13. The system of claim 12 , the first codebook generated by further:
determining an unassigned codeword from the intersection set that satisfies HD(y)=1 for data words in the intersection set subject to a constraint that a data word to assign to the codeword satisfies HD(x)<=2 with respect to data words that are already assigned to codewords.
14. The system of claim 9 , further comprising:
a second codebook utilized by the encoder to encode the data words into the code words, the second codebook generated by inverting the first codebook.
15. The system of claim 9 , the encoder configured to determine if an inversion of a most significant bit (MSB) of a transmitted codeword has occurred; and
on condition that an MSB inversion has occurred, initiate a retransmission of the transmitted codeword over the bus.
16. The system of claim 15 , wherein the encoder determining if the MSB inversion occurred comprises comparing a cyclic redundancy check (CRC) for the transmitted data word generated before transmission with a CRC generated on the data word after decoding.
17. The system of claim 15 , wherein the first digital component and second digital component comprise a memory and a processor.
18. The system of claim 15 , wherein the first digital component and second digital component comprise a first processor and a second processor.
19. The system of claim 15 , wherein the first digital component and second digital component comprise a first memory and a second memory.