Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2005-02-15
2005-02-15
Lamarre, Guy J. (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S804000
Reexamination Certificate
active
06857097
ABSTRACT:
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.
REFERENCES:
patent: 4295218 (1981-10-01), Tanner
patent: 5590248 (1996-12-01), Zarge et al.
patent: 6073250 (2000-06-01), Luby et al.
patent: 1160678 (2001-12-01), None
Mathworld, Graph Loop definition, Mathworld.com.*
Mathworld, Graph Cycle definition, Mathworld.com.*
Mathworld, Bipartite Graph definition, Mathworld.com.*
Schikore et al., “Decimation of 2d scalar data with error control,” Feb. 1995, pp 1-6.*
Etzion et al. “Which codes have cycle-free tanner graphs,” Sep. 1999, IEEE transactions on information theory, vol. 45, No. 6, pp. 2173-2181.*
Nijman et al., “Efficient learning in sparsely coonnected boltzmann machines,” 1996, pp. 1-7.*
Steedly et al. “A modified TLS-Prony method using data decimation,” 1992, pp 1-17.*
Stefan Rüger, Efficient Inference and Learning in Decmatable Boltzmann Machines, Feb. 7, 1997, pp. 1-4 and 8-14.*
http://www.mathworld.com, Graph Loop, 1990, http://mathworld.wolfram.com/GraphLoop.html.*
http://www.mathworld.com, Bipartite Graph, 1985, http://mathworld.wolfram.com/BipartiteGraph.html.*
David MacKay, Relationships between Sparse Graph Codes, Jul. 17-18, 2000, Information-Based Induction Sciences (IBIS 2000 Shizuoka, Japan), pp. 1-4.*
R. Michael Tanner, A recursive approach to low complexity codes, Sep. 1981, IEEE Transactions on Information Theory, vol. IT-27, No. 5, pp. 534-537.*
R. Michael Tanner, Minimum Distance Bounds by Graph Analysis, Jul. 26, 2000, pp. 2-4.*
Stefan M. Rüger, Decimaable Boltzmann Machines for Diagnosis: Efficient Learning and Inference, 1997, pp. 1-6.*
Thomas J. Richardson et al, Design of Capacity-Approaching Irregular Low-Density Parity-Check Codes, Feb. 2001, IEEE Transactios on Information Theory, vol. 47, No. 2, pp. 1-3.*
Sae-Young Chung, Thomas J Richardson, Rudiger L Urbanke, Analysis of Sum-Product Decoding of Low-Density Parity Check Codes Using a Gaussian Approximation, Feb. 2001, IEEE Transactions on Information Theory, vol. 47 No. 2, pp. 657-660.*
Weiberg, N. “Codes and Decoding on General Graphs,” Linkoeping Studies in Science and Technology, No. 440, pp. 1-95, 1996.
Weiss, Y. “Correctness of Local Probability Propagation in Graphical Models with Loops,” Neural Computation, MIT Press, vol. 12, No. 1, pp. 1-41, 2000.
Weiss, Y. “On the Optimality of Solutions of the Max-Product Belief-Propagation Algorithm in Arbitrary Graphs,” IEEE Transactions on Information Theory, vol. 47, No. 2, pp. 736-744, 2001.
Richardson et al., “The Capacity of Low-Density Parity-Check Codes under Message-Passing Decoding,” IEEE Transactions on Information Theory, vol. 47, No. 2, pp. 599-618, 2001.
Bouchaud Jean-Philippe M.
Yedidia Jonathan S.
Brinkman Dirk
Carton Andrew
Lamarre Guy J.
Mitsubishi Electric Research Laboratories Inc.
LandOfFree
Evaluating and optimizing error-correcting codes using a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Evaluating and optimizing error-correcting codes using a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Evaluating and optimizing error-correcting codes using a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3464279