Source: https://patents.google.com/patent/US8095854B2/en
Timestamp: 2019-04-24 02:38:07
Document Index: 341889267

Matched Legal Cases: ['§119', 'Application No. 2457420', 'Application No. 03132883', 'Application No. 03800852', 'Application No. 03254308', 'Application No. 03254308', 'Application No. 03254308', 'Application No. 03254308', 'Application No. 05789316', 'Application No. 2003', 'Application No. 2003', 'Application No. 2007', 'Application No. 2003', 'Application No. 2003', 'Application No. 2003', 'Application No. 10', 'Application No. 03800852']

US8095854B2 - Method and system for generating low density parity check codes - Google Patents
Method and system for generating low density parity check codes Download PDF
US8095854B2
US8095854B2 US11/938,016 US93801607A US8095854B2 US 8095854 B2 US8095854 B2 US 8095854B2 US 93801607 A US93801607 A US 93801607A US 8095854 B2 US8095854 B2 US 8095854B2
US11/938,016
US20080082895A1 (en
2002-07-26 Priority to US39876002P priority Critical
2002-08-15 Priority to US40381202P priority
2002-10-25 Priority to US42150502P priority
2002-10-29 Priority to US42199902P priority
2002-11-04 Priority to US42371002P priority
2003-01-28 Priority to US10/353,230 priority patent/US20040019845A1/en
2007-11-09 Priority to US11/938,016 priority patent/US8095854B2/en
2007-11-09 Application filed by DTVG Licensing Inc filed Critical DTVG Licensing Inc
2008-04-03 Publication of US20080082895A1 publication Critical patent/US20080082895A1/en
2009-05-12 Assigned to DTVG LICENSING, INC. reassignment DTVG LICENSING, INC. ASSIGNMENT OF ASSIGNORS INTEREST (SEE DOCUMENT FOR DETAILS). Assignors: HUGHES ELECTRONICS CORPORATION
2012-01-10 Publication of US8095854B2 publication Critical patent/US8095854B2/en
This application is a divisional application of and claims priority to U.S. patent application (Ser. No. 10/353,230), filed Jan. 28, 2003, entitled “Method and System for Generating Low Density Parity Check Codes,” which claims the benefit of the earlier filing date under 35 U.S.C. §119(e) of, U.S. Provisional Patent Application (Ser. No. 60/398,760), filed Jul. 26, 2002, entitled “Code Design and Implementation Improvements for Low Density Parity Check Codes,” U.S. Provisional Patent Application (Ser. No. 60/403,812), filed Aug. 15, 2002, entitled “Power and Bandwidth Efficient Modulation and Coding Scheme for Direct Broadcast Satellite and Broadcast Satellite Communications,” U.S. Provisional Patent Application (Ser. No. 60/421,505), filed Oct. 25, 2002, entitled “Method and System for Generating Low Density Parity Check Codes,” U.S. Provisional Patent Application (Ser. No. 60/421,999), filed Oct. 29, 2002, entitled “Satellite Communication System Utilizing Low Density Parity Check Codes” and U.S. Provisional Patent Application (Ser. No. 60/423,710), filed Nov. 4, 2002, entitled “Code Design and Implementation Improvements for Low Density Parity Check Codes”; the entireties of which are incorporated herein by reference.
FIG. 4 is a diagram of a sparse parity check matrix, in accordance with an embodiment of the present invention. LDPC codes are long, linear block codes with sparse parity check matrix H(n−k)×n. Typically the block length, n, ranges from thousands to tens of thousands of bits. For example, a parity check matrix for an LDPC code of length n=8 and rate ½ is shown in FIG. 4. The same code can be equivalently represented by the bipartite graph, per FIG. 5.
H (n−k)×n =[A (n−k)×k B (n−k)×(n−k)],
and similarly for p 2 , p 3 , . . . , p n−k−1.
d 1 = - E s N 0 ⁢ { ( r x - s i , x ) 2 + ( r y - s i , y ) 2 } i = 0 , 1 , … ⁢ ⁢ 7.
u 0=ƒ(d 0 +p 0 ,d 1 +p 1 ,d 2 +p 2 ,d 3 +p 3)−ƒ(d 4 +p 4 ,d 5 +p 5 ,d 6 +p 6 ,d 7 ζp 7)−e 0
u 1=ƒ(d 0 +p 0 ,d 1 +p 1 ,d 4 +p 4 ,d 5 +p 5)−ƒ(d 2 +p 2 ,d 3 +p 3 ,d 6 +p 6 ,d 7 ζp 7)−e 1
u 2=ƒ(d 0 +p 0 ,d 2 +p 2 ,d 4 +p 4 ,d 6 +p 6)−ƒ(d 1 +p 1 ,d 3 +p 3 ,d 5 +p 5 ,d 7 ζp 7)−e 2
a n = u n + ∑ j ⁢ ⁢ w k j → n
v n → k i = u n + ∑ j ≠ i ⁢ ⁢ w k j → n
c ^ n = { 0 , a n ≥ 0 1 , a n < 0 Stop ⁢ ⁢ if ⁢ ⁢ H ⁢ c ^ T = 0
US11/938,016 2002-07-26 2007-11-09 Method and system for generating low density parity check codes Active 2026-01-09 US8095854B2 (en)
US39876002P true 2002-07-26 2002-07-26
US40381202P true 2002-08-15 2002-08-15
US42150502P true 2002-10-25 2002-10-25
US42199902P true 2002-10-29 2002-10-29
US42371002P true 2002-11-04 2002-11-04
US10/353,230 US20040019845A1 (en) 2002-07-26 2003-01-28 Method and system for generating low density parity check codes
US11/938,016 US8095854B2 (en) 2002-07-26 2007-11-09 Method and system for generating low density parity check codes
US10/353,230 Division US20040019845A1 (en) 2002-07-26 2003-01-28 Method and system for generating low density parity check codes
US20080082895A1 US20080082895A1 (en) 2008-04-03
US8095854B2 true US8095854B2 (en) 2012-01-10
ID=30773784
US10/353,230 Abandoned US20040019845A1 (en) 2002-07-26 2003-01-28 Method and system for generating low density parity check codes
US11/938,016 Active 2026-01-09 US8095854B2 (en) 2002-07-26 2007-11-09 Method and system for generating low density parity check codes
US (2) US20040019845A1 (en)
KR100918741B1 (en) 2004-07-27 2009-09-24 삼성전자주식회사 Apparatus and method for channel coding in mobile communication system
KR100846869B1 (en) 2004-12-16 2008-07-16 한국전자통신연구원 Apparatus for Decoding LDPC with Low Computational Complexity Algorithms and Method Thereof
KR100800775B1 (en) 2005-07-27 2008-02-01 삼성전자주식회사 A Channel coding method and apparatus in mobile communication system
KR101191196B1 (en) 2006-06-07 2012-10-15 엘지전자 주식회사 Method of encoding and decoding using a parity check matrix
TWI332205B (en) * 2007-03-01 2010-10-21 Lite On It Corp Data modulation/encryption method used in holographic stotage system
WO2010024914A1 (en) * 2008-08-29 2010-03-04 Thomson Licensing System and method for reusing dvb-s2 ldpc codes in dvb-c2
CN103236861B (en) * 2013-05-10 2016-03-16 电子科技大学 Triangular ldpc method of the class code Galois field check matrix
WO2002056559A1 (en) 2001-01-16 2002-07-18 Koninklijke Philips Electronics N.V. Bit interleaved coded modulation (bicm) mapping
US20040064779A1 (en) 2002-09-30 2004-04-01 Seagate Technology Llc System and method for iterative decoding of Reed-Muller codes
WO2004077733A2 (en) 2003-02-26 2004-09-10 Flarion Technologies, Inc. Method and apparatus for performing low-density parity-check (ldpc) code operations using a multi-level permutation
KR100939334B1 (en) * 2007-12-12 2010-01-29 한국전자통신연구원 Apparatus and method of decoding low density parity check code using prototype matrix
TWI425519B (en) * 2009-12-09 2014-02-01 Nat Chip Implementation Ct Nat Applied Res Lab Method for arranging memories of low-complexity low-density parity-check codes decoder and the ldpc codes decoder thereof
WO2011127287A1 (en) * 2010-04-08 2011-10-13 Marvell World Trade Ltd. Non-binary ldpc code decoder
2003-01-28 US US10/353,230 patent/US20040019845A1/en not_active Abandoned
2007-11-09 US US11/938,016 patent/US8095854B2/en active Active
US20020136318A1 (en) * 2001-01-16 2002-09-26 Alexei Gorokhov Transmission system for transmitting a multilevel signal
US20050278606A1 (en) 2001-06-15 2005-12-15 Tom Richardson Methods and apparatus for decoding ldpc codes
Al-Rawi, G. et al.; "Optimizing the Mapping of Low-Density Parity Check Codes on Parallel Decoding Architectures"; Proceedings, IEEE Conference on Information Technology: Coding and Computing; pp. 578-586; Apr. 2-4, 2001.
Bond, J.W.; Hui, S.; Schmidt, H.; "Constructing Low-Density Parity-Check Codes"; EuroComm 2000; Information Systems for Enhanced Public Safety and Security; IEEE/AFCEA; May 17, 2000; Piscataway, New Jersey, USA; IEEE LNKD- DOI:10.1109/EURCOM.2000.874812; Jan. 1, 2000; pp. 260-262; XP010515080; ISBN: 978-0-7803-6323-6.
Boutillon, E. et al.; "Decoder-First Code Design"; Proceedings; International Symposium on Turbo Codes and Related Topics; pp. 459-462; Sep. 4-7, 2000.
Brink, S. et al.; "Iterative Demapping of QPSK Modulation"; Electronics Letters, IEE; Stevenage, Great Britain; vol. 34, No. 15; Jul. 23, 1998; pp. 1495-1460.
Canadian Office action dated Jan. 22, 2010 in Canadian Patent Application No. 2457420 filed Jul. 3, 2003 by Mustafa Eroz et al.; 3 pages.
Chinese Office Action dated Apr. 7, 2006 in Chinese counterpart Application No. 03132883.0 corresponding to U.S. Appl. No. 10/353,230, filed Jan. 28, 2003 by Mustafa Eroz et al.
Chinese Office action dated Jul. 22, 2011 in Chinese Patent Application No. 03800852.1 filed Jul. 3, 2003 by Mustafa Eroz et al.
Duman, T. M. et al.; "Performance Bounds for Turbo-Coded Modulation Systems"; IEEE Transactions on Communications; vol. 47, No. 4; Apr. 1999; pp. 511-521.
Eleftheriou, E. et al.; "Low-Density Parity-Check Codes for Digital Subscriber Lines"; Proceedings; IEEE International Conference on Communications; New York, NY, USA; vol. 1; Apr. 28-May 2, 2002; pp. 1752-1757.
Eleftheriou, E.; "G.gen: LDPC Codes for G.dmt.bis and G.lite.bis"; Jan. 2001; http://stanford.edu/class/ee379b/class-reader/ibm3.pdf.
Eleftheriou, E.; "G.gen: LDPC Codes for G.dmt.bis and G.lite.bis"; Jan. 2001; http://stanford.edu/class/ee379b/class—reader/ibm3.pdf.
EPO Communication dated Apr. 20, 2004 in European counterpart Application No. 03254308.4 corresponding to U.S. Appl. No. 10/353,230, filed Jan. 28, 2003 by Mustafa Eroz et al.
EPO Communication dated May 12, 2005 in European counterpart Application No. 03254308.4 corresponding to U.S. Appl. No. 10/353,230, filed Jan. 28, 2003 by Mustafa Eroz et al.
EPO Communication/Notice of Allowance dated Oct. 26, 2006 in European counterpart Application No. 03254308.4 corresponding to U.S. Appl. No. 10/353,230, filed Jan. 28, 2003 by Mustafa Eroz et al.
EPO Summons to Attend Oral Proceedings dated Apr. 12, 2006 in European counterpart Application No. 03254308.4 corresponding to U.S. Appl. No. 10/353,230, filed Jan. 28, 2003 by Mustafa Eroz et al.
EPO Summons to attend oral proceedings dated Mar. 5, 2010 in European Patent Application No. 05789316.6 filed Aug. 3, 2005 by Mustafa Eroz et al.
Final Rejection dated Feb. 25, 2010 in U.S. Appl. No. 10/961,124, filed Oct. 8, 2004 by Mustafa Eroz et al.
Final Rejection dated Oct. 28, 2008 in U.S. Appl. No. 10/961,124, filed Oct. 8, 2004 by Mustafa Eroz et al.
Flarion; "Flarion Improves Speed for Data Communications and Multimedia Applications with Enhanced Forward Error-Correction Codes"; press releases; Feb. 19, 2002; http://www.flarion.com/news/pr-2002/021902.asp.
Flarion; "Flarion Improves Speed for Data Communications and Multimedia Applications with Enhanced Forward Error-Correction Codes"; press releases; Feb. 19, 2002; http://www.flarion.com/news/pr—2002/021902.asp.
Futaki, Hisashi et al.; "Performance of Low-Density Parity-Check (LDPC) Coded OFDM Systems"; Tokyo University of Science, Faculty of Science and Technology; Japan; 2000 IEEE; pp. 1696-1700.
Gallagher, R.G.; "Low-Density Parity Check Codes"; IRE Transactions of Information Theory; 1962; pp. 21-28; XP-000992693.
Goff; "Signal Constellations for Bit-Interleaved Coded Modulation"; IEEE Transactions on Information Theory; vol. 49, No. 1; Jan. 2003; pp. 307-313.
Hagenauer, J. et al.; "Decoding and Equalization with Analog Non-Linear Networks"; European Transactions on Telecommunications; Eurel publication; Milano, Italy; vol. 10, No. 6; Nov. 1999; pp. 659-680.
Hagenauer, J. et al.; "Iterative Decoding of 6-8 Binary Block and Convolutional Codes"; IEEE Transactions on Information Theory; vol. 42, No. 2; Mar. 1996; pp. 429-445.
Japanese Decision of Rejection dated Jun. 13, 2006 in Japanese counterpart Application No. 2003-176330 corresponding to U.S. Appl. No. 10/353,230, filed Jan. 28, 2003 by Mustafa Eroz et al.
Japanese Decision of Rejection dated Jun. 20, 2006 in Japanese counterpart Application No. 2003-176330 corresponding to U.S. Appl. No. 10/353,230, filed Jan. 28, 2003 by Mustafa Eroz et al.
Japanese Office action dated Apr. 19, 2011 in Japanese Patent Application No. 2007-525661 filed Aug. 3, 2005 by Mustafa Eroz et al.
Japanese Office Action dated Jul. 12, 2005 in Japanese counterpart Application No. 2003-176330 corresponding to U.S. Appl. No. 10/353,230, filed Jan. 28, 2003 by Mustafa Eroz et al.
Japanese Office Action dated Jul. 4, 2005 in Japanese counterpart Application No. 2003-176330 corresponding to U.S. Appl. No. 10/353,230, filed Jan. 28, 2003 by Mustafa Eroz et al.
Japanese Pre-Appeal Examination report dated Dec. 25, 2006 in Japanese counterpart Application No. 2003-176330 corresponding to U.S. Appl. No. 10/353,230, filed Jan. 28, 2003 by Mustafa Eroz et al.
Korean Office Action dated Apr. 29, 2005 in Korean counterpart Application No. 10-2003-39765 corresponding to U.S. Appl. No. 10/353,230, filed Jan. 28, 2003 by Mustafa Eroz et al.
Le Goff, S.Y.; "Channel Capacity of Bit-Interleaved Coded Modulation Schemes Using 8-ary Signal Constellations"; Electronics Letters; Feb. 14, 2002; vol. 28, No. 4.
Li, X. et al.; "Bit-Interleaved Coded Modulation with Iterative Decoding using Soft Feedback"; Electronics Letters, IEE; Stevenage, Great Britain; vol. 34, No. 10; May 14, 1998; pp. 942-943.
Li, Xiaodong; Ritcey, James A.; "Bit-Interleaved Coded Modulation with Iterative Decoding"; 1999 IEEE International Conference on Communications; ICC 1999; pp. 858-863.
Mackay, David J.C.; "Good Error-Correcting Codes Based on Very Sparse Matrices"; IEEE Transaction on Information Theory; vol. 45, No. 2; Mar. 1999; pp. 399-431; XP-002143042.
Meglicki; "Linear Codes"; Apr. 2005; http://beige.ucs.indiana.edu/M743/node119.html.
Narayanaswami, R.; "Coded Modulation with Low Density Parity Check Codes"; Master thesis; Texas A&M University; Jun. 2001; XP2271230.
Non-final Office action dated Apr. 25, 2011 in U.S. Appl. No. 12/967,894, filed Dec. 14, 2010 by Mustafa Eroz et al.
Non-final Office Action dated Apr. 3, 2009 in U.S. Appl. No. 10/961,124, filed Oct. 8, 2004 by Mustafa Eroz et al.
Non-final Office action dated Aug. 16, 2010 in U.S. Appl. No. 12/195,512, filed Aug. 21, 2008 by Mustafa Eroz et al.
Non-final Office Action dated Jun. 11, 2008 in U.S. Appl. No. 10/961,124, filed Oct. 8, 2004 by Mustafa Eroz et al.
Non-final Office action dated May 12, 2011 in U.S. Appl. No. 11/938,110, filed Nov. 9, 2007 by Mustafa Eroz et al.
Non-final Office action dated May 16, 2011 in U.S. Appl. No. 12/498,968, filed Jul. 7, 2009 by Mustafa Eroz et al.
Non-final Office Action dated May 30, 2009 in U.S. Appl. No. 11/201,796, filed Aug. 11, 2005 by Mustafa Eroz et al.
Non-final Office Action dated Nov. 13, 2007 in U.S. Appl. No. 11/635,998, filed Dec. 8, 2006 by Mustafa Eroz et al.
Non-final Office Action dated Nov. 27, 2007 in U.S. Appl. No. 10/961,124, filed Oct. 8, 2004 by Mustafa Eroz et al.
Non-final Office Action dated Sep. 30, 2009 in U.S. Appl. No. 10/961,124, filed Oct. 8, 2004 by Mustafa Eroz et al.
Notice of Allowance dated Aug. 24, 2010 in U.S. Appl. No. 10/961,124, filed Oct. 8, 2004 by Mustafa Eroz et al.
Notice of Allowance dated Feb. 9, 2011 in U.S. Appl. No. 11/710,761, filed Feb. 26, 2007 by Mustafa Eroz et al.
Notice of Allowance dated Jan. 21, 2011 in U.S. Appl. No. 12/195,512, filed Aug. 21, 2008 by Mustafa Eroz et al.
Notice of Allowance dated Oct. 17, 2007 in U.S. Appl. No. 11/059,938, filed Feb. 17, 2005 by Mustafa Eroz et al.
Rejection Decision dated Nov. 11, 2011 in Chinese Patent Application No. 03800852.1 filed Jul. 3, 2003 by Mustafa Eroz et al.
Richardson, T. et al.; "Efficient Encoding of Low-Density Parity Check Codes"; IEEE Transactions on Information Theory; vol. 47, No. 2; pp. 638-656; Feb. 2001.
Sci-Worx GMBH; "FEC-52 Next Generation FEC for Digital Video Broadcasting via Satellite"; www.sci-worx.com; 2003.
Sipser et al.; "Expander Codes"; IEEE 1994; pp. 566-576.
Tullberg, H.M.; Siegel, P.H.; "Bit-Interleaved Coded Modulation for Delay-Constrained Mobile Communication Channels"; Proceedings, IEEE Vehicular Technology Conference; VTC 2000; Tokyo, Japan; IEEE, Inc.; New York, US; vol. 3 of 3; Conf. 51; May 15-18, 2000; pp. 2212-2216; XP000968397.
Vasic, B.; "Structured Iteractively Decodable Codes Based on Steiner Systems and Their Application in Magnetic Recording"; Global Telecommunications Conference; vol. 5; Nov. 2001; pp. 2954-2960.
Wadayama, Sho; "Low Density Parity Check Code and Decoding Method"; Tokyo, Japan; Jun. 5, 2002; Triceps Corporation; pp. 123-131; ISBN: 4-88657-222-7.
Wadayama, Takashi; "A Coded Modulation Scheme Based on Low Density Parity Check Codes"; IEICE Transaction on Fundamentals; Oct. 2001; vol. E84-A; pp. 2523-2527.
Wesel et al.; "Constellation Labeling for Linear Encoders"; IEEE Transactions on Information Theory; vol. 47, No. 6; Sep. 2001; pp. 2417-2431.
Yi, Yu; Hou, Jia; Lee, Moon Ho; "Design of Semi-Algebraic Low-Density Parity-Check (SA-LDPC) Codes for Multilevel Coded Modulation"; Proceedings, IEEE International Conference on Parallel and Distributed Computing, Applications and Technologies; PDCAT 2003; Aug. 27, 2003; pp. 931-934; XP010661473; ISBN: 978-0-7803-7840-7.
Zhang, T. et al.; "Joint Code and Decoder Design for Implementation Oriented (3, k)-Regular LDPC Codes"; Proceedings; 35th Asilomar Conference on Signals, Systems & Computers; pp. 1232-1236; Nov. 4-7, 2001.
US20080082895A1 (en) 2008-04-03
US20040019845A1 (en) 2004-01-29
ES2300716T3 (en) 2008-06-16 Method and system for encoding parity check codes low density (LDPC) short block length.
KR101170629B1 (en) 2012-08-02 Error-correcting multi-stage code generator and decoder for communication systems having single transmitters or multiple transmitters
US7383487B2 (en) 2008-06-03 IPHD (iterative parallel hybrid decoding) of various MLC (multi-level code) signals
US20090183048A1 (en) 2009-07-16 Systems and methods for LDPC coded modulation
CN100449947C (en) 2009-01-07 Method and system for providing long and short block length low density parity check (LDPC) codes
RU2354045C2 (en) 2009-04-27 Device and method for encoding and decoding block codes with low density of parity control with variable coding rate
US9071276B2 (en) 2015-06-30 Data-processing device and data-processing method
DE60313832T2 (en) 2008-01-24 Method and system for generating Low Density Parity Check (LDPC) codes
EP2329602B1 (en) 2015-03-11 Method and apparatus for adapting a bit interleaver to ldpc codes and modulations under awgn channel conditions using binary erasure surrogate channels
US7436902B2 (en) 2008-10-14 Multi-dimensional space Gray code maps for multi-dimensional phase modulation as applied to LDPC (Low Density Parity Check) coded modulation
EP1696574A1 (en) 2006-08-30 AMP (Accelerated Message Passing) decoder adapted for LDPC (Low Density Parity Check) codes
ES2427179T3 (en) 2013-10-29 Encoding parity check codes low density