Efficient coding with single-error correction and double-error detection capabilities

Patent metadata

Field	Value
Publication number	US-9787329-B2
Application number	US-201514883657-A
Country	US
Kind code	B2
Filing date	Oct 15, 2015
Priority date	Oct 15, 2015
Publication date	Oct 10, 2017
Grant date	Oct 10, 2017

Abstract

An apparatus for data coding includes an encoder and a decoder. The encoder is configured to receive input data including one or more m-bit data groups that are associated with respective group indices, to generate a code word that includes the input data and an m-bit redundancy that depends on the data groups and on the respective group indices, and to send the code word over a channel. The decoder is connected to the channel and is configured to produce a syndrome that equals zero when the code word is error-free, and when the code word contains a single error caused by the channel, is indicative of an erroneous group in which the single error occurred, and of a location of the single error within the erroneous group, and to recover the input data by correcting the single error at the location in the erroneous group.

First claim

The invention claimed is:

1. An apparatus for data coding, comprising:
an encoder, which is configured to receive input data comprising multiple m-bit data groups that are associated with multiple respective group indices, to generate a code word that comprises the input data and an m-bit redundancy that depends on the multiple m-bit data groups and on the multiple respective group indices, and to send the code word over a communication bus; and
a decoder, which is coupled to the communication bus and is configured to:
produce from the code word a syndrome, by calculating (i) an intermediate data component by bitwise Xoring among the multiple m-bit data groups, (ii) an intermediate index component based at least on the multiple group indices and parity values of the respective m-bit data groups, and (iii) bitwise Xoring between the intermediate data component and the intermediate index component, so as to exploit the dependence of the m-bit redundancy on the multiple m-bit data groups and on the multiple respective group indices;
when the code word contains a single error, produce from the syndrome (i) a group index of an erroneous group, from among the multiple m-bit data groups, in which the single error occurred, and (ii) a location of the single error within the erroneous group; and
recover the input data by correcting the single error at the location in the erroneous group.

2. The apparatus according to claim 1 , wherein at least one of the encoder and decoder is configured to produce an encoded index for each m-bit data group having odd parity, by encoding the respective group index using a second matrix that spans a null-space of a first matrix whose columns enumerate the integer numbers zero to (m−1), and to apply bitwise XORing between the m-bit data group having odd parity and the encoded index.

3. The apparatus according to claim 2 , wherein at least one of the encoder and decoder is configured to encode the group index by multiplying a vector that holds a binary representation of the group index by the second matrix.

4. The apparatus according to claim 2 , wherein at least one of the encoder and decoder is configured to calculate the intermediate index component by calculating an accumulated index by bitwise XORing among the group indices of the m-bit data groups having odd parity, and multiplying the accumulated index by the second matrix.

5. The apparatus according to claim 2 , wherein the decoder is configured to identify the location of the single error within the erroneous group by multiplying the syndrome by the first matrix to obtain a multiplication result, and to generate, using the multiplication result, a respective m-bit error pattern.

6. The apparatus according to claim 5 , wherein the decoder is configured to identify the erroneous group by correcting the syndrome according to the m-bit error pattern.

7. The apparatus according to claim 1 , wherein the encoder is configured to generate the code word by further computing a message parity bit over the m-bit data groups and the m-bit redundancy, and wherein the decoder is configured to detect, using the syndrome and the message parity, an uncorrectable double-error condition when the code word contains two errors.

8. A method for data coding, comprising:
receiving, in an encoder, input data that comprises multiple m-bit data groups, wherein the multiple m-bit data groups are associated with multiple respective group indices;
generating, in the encoder, a code word that comprises the input data and an m-bit redundancy that depends on the multiple m-bit data groups and on the multiple respective group indices, and sending the code word to a decoder over a communication bus;
producing from the code word, in the decoder, a syndrome, by calculating (i) an intermediate data component by bitwise Xoring among the multiple m-bit data groups, (ii) an intermediate index component based at least on the multiple group indices and parity values of the respective m-bit data groups, and (iii) bitwise Xoring between the intermediate data component and the intermediate index component, so as to exploit the dependence of the m-bit redundancy on the multiple m-bit data groups and on the multiple respective group indices;
when the code word contains a single error, produce from the syndrome (i) a group index of an erroneous group, from among the multiple m-bit data groups, in which the single error occurred, and (ii) a location of the single error within the erroneous group; and
recovering the input data, by the decoder, by correcting the single error at the location in the erroneous group.

9. The method according to claim 8 , wherein generating the m-bit redundancy comprises producing an encoded index for each m-bit data group having odd parity, by encoding the respective group index, using a second matrix that spans a null-space of a first matrix whose columns enumerate the integer numbers zero to (m−1), and bitwise XORing between the m-bit data group having odd parity and the encoded index.

10. The method according to claim 9 , wherein encoding the group index comprises multiplying a vector that holds a binary representation of the group index by the second matrix.

11. The method according to claim 9 , wherein calculating the intermediate index component comprises calculating an accumulated index by bitwise XORing among the group indices of the m-bit data groups having odd parity, and multiplying the accumulated index by the second matrix.

12. The method according to claim 9 , and comprising identifying the location of the single error within the erroneous group by multiplying the syndrome by the first matrix to obtain a multiplication result, and generating, using the multiplication result, a respective m-bit error pattern.

13. The method according to claim 12 , and comprising identifying the erroneous group by correcting the syndrome according to the m-bit error pattern.

14. The method according to claim 8 , wherein generating the code word further comprises computing, by the encoder, a message parity bit over the m-bit data groups and the m-bit redundancy, and detecting, by the decoder, using the syndrome and the message parity, an uncorrectable double-error condition when the code word contains two errors.

15. An apparatus for data coding, comprising:
an encoder, which is configured to:
receive multiple input bits to be encoded into a respective N-bit code word that comprises the input bits and a redundancy part;
process the input bits, in m-bit groups, by applying multiple first XOR-trees to each of the m-bit groups to produce respective first group-specific redundancy bits, wherein a number of the first XOR-trees is less than a size of the redundancy part, and further applying an all-ones XOR-tree to each of the m-bit groups to produce respective second group-specific redundancy bits; and
generate the redundancy part using the first group-specific redundancy bits and the second group-specific redundancy bits, and send the code word over a communication bus; and
a decoder, which is coupled to the communication bus and is configured to:
produce from the code word a syndrome that equals zero when the code word is error-free; and
when the code word contains a single error, produce from the syndrome a location of the single error within the code word; and
recover the input bits by correcting the single error at the error location of the code word.

16. The apparatus according to claim 15 , wherein at least one of the encoder and decoder is configured to generate the redundancy part by bitwise XORing among the first group-specific red

Assignees

• Apple Inc

Inventors

• Ish-Shalom Tomer
• Teitel Moti

Classifications

• H03M13/2906 Primary

  using block codes (H03M13/2957 takes precedence) · CPC title

• H03M13/617

  Polynomial operations, e.g. operations related to generator polynomials or parity-check polynomials · CPC title

• H03M13/616

  Matrix operations, especially for generator matrices or check matrices, e.g. column or row permutations · CPC title

• H03M13/098

  using single parity bit · CPC title

• H03M13/19

  Single error correction without using particular properties of the cyclic codes, e.g. Hamming codes, extended or generalised Hamming codes · CPC title