초록 ▼

A method evaluates an error-correcting code for a data block of a finite size. An error-correcting code is defined by a parity check matrix, wherein columns represent variable bits and rows represent parity bits. The parity check matrix is represented as a bipartite graph. A single node in the bipar

A method evaluates an error-correcting code for a data block of a finite size. An error-correcting code is defined by a parity check matrix, wherein columns represent variable bits and rows represent parity bits. The parity check matrix is represented as a bipartite graph. A single node in the bipartite graph is iteratively renormalized until the number of nodes in the bipartite graph is less than a predetermine threshold. During the iterative renormalization, a particular variable node is selected as a target node, and a distance between the target node and every other node in the bipartite graph is measured. Then, if there is at least one leaf variable node, renormalize the leaf variable node farthest from the target node, otherwise, renormalize a leaf check node farthest from the target node, and otherwise renormalize a variable node farthest from the target node and having fewest directly connected check nodes. By evaluating many error-correcting codes according to the method, an optimal code according to selected criteria can be obtained.

대표청구항 ▼

1. A method for evaluating an error-correcting code for a data block of a finite size, comprising;defining an error-correcting code by a parity check matrix; representing the parity check matrix as a bipartite graph; iteratively renormalizing a single node in the bipartite graph until a predetermine

1. A method for evaluating an error-correcting code for a data block of a finite size, comprising;defining an error-correcting code by a parity check matrix; representing the parity check matrix as a bipartite graph; iteratively renormalizing a single node in the bipartite graph until a predetermined threshold is reached; and wherein the bipartite graph includes variable nodes representing variable bits of the data block, and check nodes representing parity bits of the data block, and the renormalizing further comprises: selecting a particular variable node as a target node; selecting a particular node to be renormalized; measuring a distance between the target node and every other node in the bipartite graph; if there is at least one leaf variable node, renormalizing a particular leaf variable node farthest from the target node, otherwise if there is at least one leaf check node, renormalizing a particular leaf check node farthest from the target node, otherwise renormalizing a non-leaf variable node farthest from the target node and having fewest directly connected check nodes. 2. The method of claim 1 wherein the predetermined threshold is a minimum number of remaining nodes.3. The method of claim 1 wherein the bipartite graph is cycle-free.4. The method of claim 1 wherein the bipartite graph includes at least one cycle.5. The method of claim 1 wherein a transmission channel is a binary erasure channel, and further comprising:decorating the bipartite graph with numbers pia representing probabilities of messages from variable nodes to check nodes and with numbers qai representing probabilities of messages from check nodes to variable nodes, and the renormalizing of the non-leaf variable node further comprises: enumerating all check-nodes a which are connected to the non-leaf variable node; enumerating all other variable nodes j attached to the check nodes a; and transforming the numbers qaj. 6. The method of claim 5 wherein the transforming of the numbers qaj further comprises:enumerating all check nodes and variable nodes out to a predetermined distance from the target node; constructing a logical argument to determine combinations of erasure causing a particular message from the check node a to the variable node j to be an erasure; translating the logical argument into a transformation for the number qaj. 7. The method of claim 6 further comprising:terminating the renormalizing upon reaching the predetermined threshold by an exact determination. 8. The method of claim 7 wherein the remaining bipartite graph includes N nodes in the exact determination, and further comprising:converting the decorated graph with numbers qai and pia into an erasure graph with an erasure probability xi with each node i of the bipartite graph; generating all 2N possible messages; and decoding each of the 2N messages using a belief propagation decoder, where each message has a probability p=ΠxiΠ(1?xj). 9. The method of claim 5 wherein all the numbers qai are initialized to zero, and all the numbers pia are initialized to an erasure rate of the transmission channel.10. The method of claim 5 further comprising:defining the error-correcting code by a generalized parity check matrix wherein columns represent variable bits and rows define parity bits, and wherein an overbar is placed above columns representing hidden variable bits which are not transmitted; and representing the hidden variable bits by hidden nodes in the bipartite graph. 11. The method of claim 10 wherein the transmission channel is a binary erasure channel and wherein the error-correcting code is defined by a generalized parity check matrix, and further comprising:initializing the numbers pia for hidden nodes i to one. 12. The method of claim 5 wherein the transmission channel is an additive white Gaussian noise channel, and further comprising:representing messages between nodes in the bipartite graph by Gaussian distributions. 13. The method of claim 1, and further comprising:selecting a set of criterion by which to evaluate error-correcting codes; generating a plurality of error-correcting codes; and searching the plurality of error-correcting codes for an optimal error-correcting code according to the set of criterion. 14. The method of claim 13, and further comprising:evaluating an error rate for each error-correcting code at a plurality of nodes; and generating the optimal error-correcting code according to the evaluated error-rate. 15. The method of claim 1 further comprising:evaluating an error rate for the renormalized bipartite graph. 16. A method for evaluating an error-correcting code for a data block of a finite size, comprising:defining an error-correcting code by a parity check matrix; representing the parity check matrix as a bipartite graph, wherein the bipartite graph includes variable nodes representing variable bits of the data block, and check nodes representing parity bits of the data block; iteratively renormalizing a single node in the bipartite graph until a predetermined threshold is reached, wherein the renormalizing further comprises: selecting a particular variable node as a target node; and selecting a particular node to be renormalized; measuring a distance between the target node and every other node in the bipartite graph; if there is at least one leaf variable node, renormalizing a particular leaf variable node farthest from the target node, otherwise if there is at least one leaf check node, renormalizing a particular leaf check node farthest from the target node, otherwise renormalizing a non-leaf variable node farthest from the target node and having fewest directly connected check nodes; wherein a transmission channel is a binary erasure channel, and further comprising: decorating the bipartite graph with numbers pia representing probabilities of messages from variable nodes to check nodes and with numbers qai representing probabilities of messages from check nodes to variable nodes, and the renormalizing of the non-leaf variable node further comprises: enumerating all check-nodes a which are connected to the non-leaf variable node; enumerating all other variable nodes j attached to the check nodes a; wherein the enumerating further comprises: enumerating all check nodes and variable nodes out to a predetermined distance from the target node; constructing a logical argument to determine combinations of erasures causing a particular message from the check node a to the variable node j to be an erasure; translating the logical argument into a transformation for the number qaj; and transforming the numbers qaj.