Data processing: artificial intelligence – Neural network
Reexamination Certificate
2006-06-16
2009-06-23
Starks, Jr., Wilbert L (Department: 2129)
Data processing: artificial intelligence
Neural network
C341S107000, C360S053000, C370S216000
Reexamination Certificate
active
07552097
ABSTRACT:
Methods and apparatus for decoding codewords using message passing decoding techniques which are particularly well suited for use with low density parity check (LDPC) codes and long codewords are described. The described methods allow decoding graph structures which are largely comprised of multiple identical copies of a much smaller graph. Copies of the smaller graph are subject to a controlled permutation operation to create the larger graph structure. The same controlled permutations are directly implemented to support message passing between the replicated copies of the small graph. Messages corresponding to individual copies of the graph are stored in a memory and accessed in sets, one from each copy of the graph, using a SIMD read or write instruction. The graph permutation operation may be implemented by simply reordering messages, e.g., using a cyclic permutation operation, in each set of messages read out of a message memory so that the messages are passed to processing circuits corresponding to different copies of the small graph.
REFERENCES:
patent: 3542756 (1970-11-01), Gallager et al.
patent: 3665396 (1972-05-01), Forney, Jr.
patent: 4295218 (1981-10-01), Tanner
patent: 4561092 (1985-12-01), Shaver
patent: 4914657 (1990-04-01), Walter et al.
patent: 4972415 (1990-11-01), Walter et al.
patent: 5157671 (1992-10-01), Karplus
patent: 5271042 (1993-12-01), Borth et al.
patent: 5293489 (1994-03-01), Furui et al.
patent: 5313609 (1994-05-01), Baylor et al.
patent: 5396518 (1995-03-01), How
patent: 5457704 (1995-10-01), Hoeher et al.
patent: 5526501 (1996-06-01), Shams
patent: 5615298 (1997-03-01), Chen
patent: 5671221 (1997-09-01), Yang
patent: 5860085 (1999-01-01), Stormon et al.
patent: 5864703 (1999-01-01), Van Hook et al.
patent: 5867538 (1999-02-01), Liu
patent: 5892962 (1999-04-01), Cloutier
patent: 5933650 (1999-08-01), Van Hook et al.
patent: 5968198 (1999-10-01), Hassan
patent: 6002881 (1999-12-01), York et al.
patent: 6073250 (2000-06-01), Luby et al.
patent: 6081909 (2000-06-01), Luby et al.
patent: 6081918 (2000-06-01), Spielman
patent: 6163870 (2000-12-01), Luby et al.
patent: 6195777 (2001-02-01), Luby et al.
patent: 6247158 (2001-06-01), Smallcomb
patent: 6266758 (2001-07-01), Van Hook et al.
patent: 6298438 (2001-10-01), Thayer et al.
patent: 6339834 (2002-01-01), Crozier et al.
patent: 6397240 (2002-05-01), Fernando et al.
patent: 6438180 (2002-08-01), Kavcic et al.
patent: 6473010 (2002-10-01), Vityaev et al.
patent: 6484284 (2002-11-01), Smallcomb
patent: 6526538 (2003-02-01), Hewitt
patent: 6539367 (2003-03-01), Blanksby et al.
patent: 6619430 (2003-09-01), Zhong et al.
patent: 6633856 (2003-10-01), Richardson et al.
patent: 6700867 (2004-03-01), Classon et al.
patent: 6718504 (2004-04-01), Coombs et al.
patent: 6731700 (2004-05-01), Yakhnich et al.
patent: 6751770 (2004-06-01), Morelos-Zaragoza
patent: 6754804 (2004-06-01), Hudepohl et al.
patent: 6757122 (2004-06-01), Kuznetsov et al.
patent: 6771197 (2004-08-01), Yedidia et al.
patent: 6938196 (2005-08-01), Richardson et al.
patent: 6957375 (2005-10-01), Richardson
patent: 6961888 (2005-11-01), Jin et al.
patent: 6973375 (2005-12-01), Brodeur et al.
patent: 7133853 (2006-11-01), Richardson et al.
patent: 7174495 (2007-02-01), Boutillon et al.
patent: 7373581 (2008-05-01), Okamura et al.
patent: 2002/0002695 (2002-01-01), Kschischang et al.
patent: 2003/0065989 (2003-04-01), Yedida et al.
patent: 2004/0034828 (2004-02-01), Hocevar
patent: 1158682 (2001-11-01), None
patent: 299539 (1997-03-01), None
T. Richardson and R. Urbanke, “An Introduction to the Analysis of Iterative Coding Systems”, pp. 1-36.
W. W. Peterson and E.J. Weldon, Jr., “Error-Correcting Codes”, Second Edition, The Massachusetts Institute of Technology, pp. 212-213,261-263, 263, (1986).
NN9210335. Hierarchical Coded Modulation of Data with Fast Decaying Probability Distributions, IBM Tech. Disclosure Bulletin, Oct. 1992, vol. No. 35; ISSUE No. 5; pp. 335-336, whole document.
NN77112415. Digital Encoding of Wide Range Dynamic Analog Signals, IBM Tech. Disclosure Bulletin, Nov. 1, 1997, vol. No. 20; ISSUE No. 6; pp. 2415-2417, whole document.
Sorokine, V. et al. Innovative coding scheme for spread-spectrum communications, The Ninth IEEE International Symposium on Indoor and Mobile Radio Communications, pp. 1491-1495, vol. 3; Sep. 1998, whole document.
Paranchych et al. Performance of a digital symbol synchronizer in cochannel interference and noise, IEEE Transactions on Communications, pp. 1945-1954; Nov. 2000, whole document.
Richardson et al. The capacity of low-density parity-check codes under message-passing Decoding, IEEE Transactions on Information Theory; pp. 599-618, Feb. 2001, (same inventor) whole document.
T. Richardson and R. Urbanke, “The Capacity of Low-Density Parity-Check Codes under Message-Passing Decoding”, pp. 1-44 (Mar. 2001).
T. Richardson, A. Shokrollahi, R. Urbanke, “Design of Capacity-Approaching Irregular Low-Density Parity-Check Codes”, pp. 1-43 (Mar. 2001).
T. Moors and M. Veeraraghavan, “Preliminary specification and explanation of Zing: An end-to-end protocol for transporting bulk data over optical circuits”, pp. 1-55 (May 2001).
Mohammad M. Mansour, Naresh R. Shanbhag, Session 11: Low-power VLSI decoder architectures for LDPC codes, Proceedings of the 2002 international symposium on Low power electronics and design Aug. 2002, pp. 284-289.
Saied Hemati, Amir H. Banihashemi, VLSI circuits: Iterative decoding in analog CMOS, Proceedings of the 13thACM Great Lakes Symposium on VLSI Apr. 2003, pp. 15-20.
Al-Rawi G. et al: “A highly efficient domain-programmable parallel architecture for iterative LDPCC decoding”, Proc. IEEE International Conference on Information Technology: Coding and Computing, Apr. 2, 2001 (Apr. 2, 2001) - Apr. 4, 2001 (Apr. 4, 2001) pp. 569-577, XP002474759.
Boutillon et al., “Decoder-First Code Design,” Proceeding Interantional Symposium on Turbo Codes and Related Topics, Sep. 2001, pp. 459-462, XP008011934.
Engling Y. et al.: “VLSI architectures for iterative decoders in magnetic recording channels”, IEEE Transactions on Magnetics, IEEE Service Center, New York; NY US, vol. 37, No. 2, Mar. 2001 (Mar. 2001), pp. 748-755.
Eric W. Weisstein. “Group-Ring.” From Math World—A Wolfram Web Resource, Dec. 30, 2004, p. 1 of 1.
Eric W. Weisstein et al. “Group Algebra.” From Math World—A Wolfram Web Resource, Dec. 30, 2004, p. 1 of 2.
He Yu-Cheng et al: “Fast decoding of LDPC codes using quantisation”, Electronics Letters, IEE Stevenage, GB, vol. 38, No. 4, Feb. 14, 2002 (Feb. 14, 2002), pp. 189-190, XP006017844.
International Search Report - PCT/US02/017396, International Search Authority - European Patent Office - Aug. 2, 2002.
Levine B. et al: “Implementation of near Shannon limt error-correcting codes using reconfigurable hardware”. IEEE Symp. on Field-Programmable Custom Computing Machines, Napa Valley, CA, USA, Apr. 17, 2000 (Apr. 17, 2000), - Apr. 19, 2000 (Apr. 19, 2000) pp. 217-226, XP010531940, pp. 223-224.
Mansour et al., “On the Architecture-Aware Structure of LDPC Codes from Generalized Ramanujan Graphs and their Decoder Architectures,” 2003 Conference on Information Sciences and Systems, Mar. 2002.
Sorokine et al., “Gallagher Codes for CDMA Applications - Part II: Implementations, Complexity and System Capacity,” IEEE Transactions on Communications, vol. 48, No. 11, Nov. 2000, pp. 1818-1828.
Supplementary European Search Report - EP02739608, International Search Authority - European Patent Office - Munich - Apr. 17, 2008.
Tong Zhang et al: “On finite precision implementation of low density parity check codes decoder”, ISCAS 2001. Proceedings of the 2001 IEEE International Symposium OnProc., IEEE Internat. Symp. on Circuits and Systems, Sydney, Australia, vol. vol. 1 of 5, May 6, 2001 (May 6, 2001) - May 9, 2001 (May 9, 2001) pp. 202-205, XP010541828, pp. 203-204.
Y
Novichkov Vladimir
Richardson Tom
O'Hare James K.
QUALCOMM Incorporated
Starks, Jr. Wilbert L
Straub Michael P.
Umpleby Katherine
LandOfFree
Methods and apparatus for decoding LDPC codes does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods and apparatus for decoding LDPC codes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatus for decoding LDPC codes will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4071014