Error detection method and apparatus

• US 20090113267A1
• Filed: 09/30/2008
• Published: 04/30/2009
• Est. Priority Date: 10/31/2007
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Harrison, Keith, Munro, William
• Granted Patent: US 8,205,134 B2
• Time in Patent Office: Days
• US Class Current: 714/746
• CPC Class Codes: H03M 13/1108 Hard decision decoding, e.g. bit flipping, modified or weighted bit flipping
• CPC Class Codes: H03M 13/1111 Soft-decision decoding, e.g. by means of message passing or belief propagation algorithms
• CPC Class Codes: H03M 13/37 Decoding methods or techniques, not specific to the particular type of coding provided for in groups H03M13/03 - H03M13/35
• CPC Class Codes: H04L 9/0662 with particular pseudorandom sequence generator
• CPC Class Codes: H04L 9/0858 Details about key distillation or coding, e.g. reconciliation, error correction, privacy amplification, polarisation coding or phase coding

Abstract

To identify errored bits in a binary data set, an ordered plurality of modulo-2 summations of respective selections of the data-set bits are compared with a target syndrome. The selections of data-set bits are defined by the connection of sum nodes to variable nodes in a logical network of nodes and edges where each variable node is associated with a respective data-set bit and each sum node corresponds to a respective modulo-2 summation. Any sum node for which the corresponding summation of selected data-set bits is found to be inconsistent with the target syndrome is identified as errored. Predetermined patterns of errored sum nodes are then looked for to identify one or more associated errored data-set bits. The identified errored data-set bits can then be flipped to correct them

Claims

1. A method of detecting errored bits in a binary data set comprising:

comparing an ordered plurality of modulo-2 summations of respective selections of the data-set bits with a target syndrome, said selections being defined by the connection of sum nodes to variable nodes in a logical network of nodes and edges where each variable node is associated with a respective data-set bit and each sum node corresponds to a respective said modulo-2 summation;

identifying as errored any sum node for which the corresponding summation of selected data-set bits is found by the comparing to be inconsistent with the target syndrome; and

identifying a predetermined pattern of errored sum nodes in the logical network thereby to identify one or more associated errored data-set bits.

2. A method of correcting errored bits in a binary data set comprising:

identifying errored bits in the binary data set according to the method of claim 1; and

flipping the value of each identified errored bit of the binary data set.

3. A method of correcting errors in a received data set, the method comprising:

applying iterative belief propagation to adjust bit-value probabilities of the received data set; and

applying the method of claim 2 to the binary data set formed by the probable bit values of the received data set after application of said iterative belief propagation.

4. A method according to claim 3, further comprising determining whether the received data set is still errored following application of the method of claim 2, and in this case continuing iterative belief propagation from where it reached immediately prior to application of the method of claim 2.

5. A method according to claim 4, wherein determining whether the received data set is still errored is effected by at least one of:

determining whether all identified errored sum nodes are part of an identified pattern of errored sum nodes; and

forming a checksum and comparing it with a reference.

6. A method according to claim 1, wherein identifying a predetermined pattern of errored sum nodes in the network is effected by carrying out an ordered search for the presence, in all or a particular portion of the logical network, of each one of a set of different predetermined patterns of the errored sum nodes.

7. A method according to claim 1, wherein the nodes and edges of said logical network together define at least a continuum of cells covering a finite toroid, each cell being delimited by an equal number of variable and sum nodes alternately arranged and interconnected into a loop by edges.

8. A method according to claim 7, wherein:

each cell has six nodes four of which are each shared with three adjacent cells and are each linked by edges to four other nodes two of which are of the same cell, the other two nodes of each cell being linked only to nodes of the cell concerned, said continuum being representable as made up of rectangular cells; and

identifying a predetermined pattern of errored sum nodes in the logical network is effected by carrying out a search in the continuum for at least one of the following patterns of errored sum nodes;

two errored sum nodes linked via a single intermediate variable node that has no other links, the associated errored data-set bit being the data-set bit associated with said intermediate variable node;

two errored sum nodes linked by a trio of nodes comprising two variable nodes straddling an un-errored sum node, each variable node being linked only to the un-errored sum node and a respective one of the errored sum nodes, the associated errored data-set bits being the data-set bits associated with the variable nodes of said trio of nodes;

four errored sum nodes linked via a single intermediate variable node, the associated errored data-set bit being the data-set bit associated with said intermediate variable node;

six errored sum nodes comprising;

a first pair linked by a trio of nodes comprising two variable nodes straddling an intermediate un-errored sum node, each variable node being linked to the intermediate sum node and to a respective one of the errored sum nodes of the first pair,

a second pair linked via a single intermediate variable node that has no other links, each errored sum node of the second pair also being linked to a respective one of the variable nodes of said trio of nodes linking the first pair of errored sum nodes; and

a third pair linked via a single intermediate variable node that has no other links, each errored sum node of the third pair also being linked to a respective one of the variable nodes of said trio of nodes linking the first pair of errored sum nodes;

the associated errored data-set bits being the data-set bits associated with the two variable nodes of said trio of nodes linking the first pair of errored sum nodes.

9. A method according to claim 7, wherein the nodes and edges of said logical network further define a plurality of spider structures each comprising a node of one type, variable or sum, linked by edges to randomly-selected nodes of the other type, sum or variable, that also participate in defining said continuum of cells.

10. A method according to claim 9, wherein for each spider structure, the randomly-selected nodes that also participate in defining said continuum of cells are sum nodes, and wherein identifying a said predetermined pattern of errored sum nodes in the logical network is effected by carrying out a search for spider structures where all the sum nodes are errored, the associated errored data-set bit being the data-set bit associated with the variable node of that spider structure.

11. Error-detecting apparatus for detecting errored bits in a binary data set, the error-detecting apparatus comprising:

a comparison arrangement for comparing an ordered plurality of modulo-2 summations of respective selections of the data-set bits with a target syndrome, said selections being defined by the connection of sum nodes to variable nodes in a logical network of nodes and edges where each variable node is associated with a respective data-set bit and each sum node corresponds to a respective said modulo-2 summation;

an errored-sum-node identifying arrangement for identifying as errored any sum node for which the corresponding summation of selected data-set bits is found by the comparison arrangement to be inconsistent with the target syndrome; and

a pattern-identifying arrangement for identifying a predetermined pattern of errored sum nodes in the logical network thereby to identify one or more associated errored data-set bits.

12. Apparatus for correcting errored bits in a binary data set, the error-correcting apparatus comprising:

error-detecting apparatus according to the method of claim 11; and

an arrangement for flipping the value of each identified errored bit of the binary data set.

13. Error-correcting apparatus for correcting errors in a received data set, the error-correcting apparatus comprising:

a processing arrangement for applying iterative belief propagation to adjust bit-value probabilities of the received data set; and

error-correcting apparatus according to claim 12 arranged to correct errored bits in the binary data set formed by the probable bit values of the received data set after application of said iterative belief propagation.

14. Error-correcting apparatus according to claim 13, further comprising an arrangement for determining whether the received data set is still errored following operation of the error-correcting apparatus of claim 12, and where this is determined to be the case, for causing the processing arrangement to continuing iterative belief propagation from where it reached immediately prior to operation of the error-correcting apparatus of claim 12.

15. Error-correcting apparatus according to claim 14, wherein determining whether the received data set is still errored is effected by at least one of:

determining whether all identified errored sum nodes are part of an identified pattern of errored sum nodes; and

forming a checksum and comparing it with a reference.

16. Error-detecting apparatus according to claim 11, wherein the pattern-identifying arrangement is arranged to identify a predetermined pattern of errored sum nodes in the network by carrying out an ordered search for the presence, in all or a particular portion of the logical network, of each one of a set of different predetermined patterns of the errored sum nodes.

17. Error-detecting apparatus according to claim 11, wherein the nodes and edges of said logical network together define at least a continuum of cells covering a finite toroid, each cell being delimited by an equal number of variable and sum nodes alternately arranged and interconnected into a loop by edges.

18. Error-detecting apparatus according to claim 17, wherein:

each cell has six nodes four of which are each shared with three adjacent cells and are each linked by edges to four other nodes two of which are of the same cell, the other two nodes of each cell being linked only to nodes of the cell concerned, said continuum being representable as made up of rectangular cells; and

the pattern-identifying arrangement is arranged to identify a predetermined pattern of errored sum nodes in the logical network by carrying out a search in the continuum for at least one of the following patterns of errored sum nodes;

two errored sum nodes linked via a single intermediate variable node that has no other links, the associated errored data-set bit being the data-set bit associated with said intermediate variable node;

two errored sum nodes linked by a trio of nodes comprising two variable nodes straddling an un-errored sum node, each variable node being linked only to the un-errored sum node and a respective one of the errored sum nodes, the associated errored data-set bits being the data-set bits associated with the variable nodes of said trio of nodes;

four errored sum nodes linked via a single intermediate variable node, the associated errored data-set bit being the data-set bit associated with said intermediate variable node;

six errored sum nodes comprising;

a first pair linked by a trio of nodes comprising two variable nodes straddling an intermediate un-errored sum node, each variable node being linked to the intermediate sum node and to a respective one of the errored sum nodes of the first pair,

a second pair linked via a single intermediate variable node that has no other links, each errored sum node of the second pair also being linked to a respective one of the variable nodes of said trio of nodes linking the first pair of errored sum nodes; and

a third pair linked via a single intermediate variable node that has no other links, each errored sum node of the third pair also being linked to a respective one of the variable nodes of said trio of nodes linking the first pair of errored sum nodes;

the associated errored data-set bits being the data-set bits associated with the two variable nodes of said trio of nodes linking the first pair of errored sum nodes.

19. Error-detecting apparatus according to claim 17, wherein the nodes and edges of said logical network further define a plurality of spider structures each comprising a node of one type, variable or sum, linked by edges to randomly-selected nodes of the other type, sum or variable, that also participate in defining said continuum of cells.

20. Error-detecting apparatus according to claim 19, wherein for each spider structure, the randomly-selected nodes that also participate in defining said continuum of cells are sum nodes, and wherein the pattern-identifying arrangement is arranged to identify a said predetermined pattern of errored sum nodes in the logical network by carrying out a search for spider structures where all the sum nodes are errored, the associated errored data-set bit being the data-set bit associated with the variable node of that spider structure.