Error detection/correction and fault detection/recovery – Pulse or data error handling – Digital data error correction
Reexamination Certificate
2006-01-24
2006-01-24
Decady, Albert (Department: 2133)
Error detection/correction and fault detection/recovery
Pulse or data error handling
Digital data error correction
C714S784000
Reexamination Certificate
active
06990626
ABSTRACT:
A method and apparatus are disclosed for MAP decoding of signals encoded using error correction codes to make maximum probability decisions about each transmitted bit. A MAP decoding algorithm is disclosed that exploits properties of Reed-Muller error correction codes that use q-ary block codes to provide a decoding algorithm having a complexity that is proportional to n logqn for Reed-Muller codes. The disclosed MAP decoding algorithm employs two matrices D and {overscore (D)} to represent the code set and has an overall complexity that is exponential for a general code set. For Reed-Muller codes, the disclosed MAP decoding algorithm employs matrices Biand {overscore (Bi)} that are sparse matrices (i.e., contain many zero entries), thereby reducing the number of required operations and yielding a complexity that is proportional to n logqn. In addition, the disclosed MAP decoding algorithm permits faster decoding by permitting a parallel implementation having a critical path length that is proportional to 2 logqn for Reed-Muller codes.
REFERENCES:
patent: 5926488 (1999-07-01), Khayrallah
patent: 6145114 (2000-11-01), Crozier et al.
patent: 2002/0122510 (2002-09-01), Yakhnich et al.
patent: 2003/0026224 (2003-02-01), Kim et al.
patent: 2003/0074626 (2003-04-01), Coker et al.
patent: 2004/0071357 (2004-04-01), Cook
J. Massey, “Deep-Space Communications and Coding: A Marriage Made in Heaven”, Sep. 22-23, 1992. , url =“citeseer.ist.psu.edu/massey92deepspace.html”.
D. J. C. MacKay, “Good Error-Correcting Codes Based on Very Sparse Matrices”, Information Theory, IEEE Transactions, vol. 45, Issue 2, Mar. 1999, pp. 399-431.
Ben Cooke, “Reed-Muller Error Correcting Codes”, MIT Undergraduate Journal of Mathematics, vol. 1, 1999, url =“http://www.-math.mit.edu/phase2/UJM/vol1/COOKE7FF.PDF”.
A. Ashikhmin, et al., “Quasioptimal Biorthogonal-Code Decoding Algorithms,” Radioelectronica, vol. 31, No. 11, pp. 30-34, 1988 (in Russian), English translation: Radio Electronics and Communication System, v.31, 11, pp. 26-30, 1988.
A. Ashikhmin, et al., “A List Algorithm for Locating the Maximal Element in a Walsh Spectrum,” Radioelectronica, vol. 32, No. 3, pp. 15-22, 1990 (In Russian), English translation: Radio Electronics and Communication Systems, v.32, 11, pp. 37-41, 1990.
A. Ashikhmin, et al., “Fast Decoding of First Order Reed-Muller and Related Codes,” Designs, Codes and Cryptography, vol. 7, pp. 187-215, 1996.
L. R. Bahl, et al., “Optimal Decoding of Linear Codes for Minimizing Symbol Error Rate,” IEEE Trans. Inf. Theory, vol. IT-20, pp. 284-287, Mar. 1974.
Y. Be'ery et al., “Optimal Soft Decision Block Decoders Based on Fast Hadamard Transform,” IEEE Trans. on Inf. Theory, vol. IT-32, pp. 355-364, 1986.
P. Delsarte, J.-M.Goethals and F.J.MacWilliams, “On generalized Reed-Muller codes and their relatives,” Info.and Control, vol.16, pp. 403-442, 1974.
R. R. Green, “A Serial Orthogonal Decoder,” JPL Space Programs Summary, vol. 37-39-IV, pp. 247-253, 1966.
I. J. Good, “The Interaction Algorithm and PracticalFourier Analysis,” J.Royal Stat. Soc., (London)1958. vol. B-20. pp. 361-372.
I.Grushko, “Majority-Logic Decoding of Generalized Reed-Muller Codes,” Problemy Peredachi Informatsii, vol. 26, pp. 189-196, 1990.
T. Kasami, et al., “New Generalizations of the Reed-Muller codes, Part 1: Primitive codes,” IEEE Trans. on Inf. Theory, vol. IT-14, pp. 189-199, 1968.
T. Kasami, et al., “On the optimum bit orders with respect to the state complexity of trellis diagrams for binary linear codes,” IEEE Trans. Inf. Theory, vol. IT-39, pp. 242-245, Jan. 1993.
T. Kasami, et al., “On Complexity of Trellis Structure of Linear Block Codes,” IEEE Trans. Inf. Theory, vol. IT-39, pp. 1057-1064, Jan. 1993.
S.Litsyn, et al., “Fast Decoding of First Order Reed-Muller Codes in the Gaussian Channel,” Problems of Control and Information Theory, vol. 14, No. 3, pp. 189-201, 1985.
D. E. Muller, “Application of Boolean Algebra to Switching Circuit Design and to Error Detection,” IEEE Trans. Computers, vol. 3, pp. 6-12, 1954.
I. S. Reed, “A Class of Multiple-Error-Correcting Codes and the Decoding Scheme,” IEEE Trans. Inf. Theory, vol. IT-4, pp. 38-49, 1954.
De'cady Albert
Lucent Technologies - Inc.
Trimmings John P.
LandOfFree
Method and apparatus for MAP decoding of first-order reed... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for MAP decoding of first-order reed..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for MAP decoding of first-order reed... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3533031