Source: http://www.google.com/patents/US8095854?dq=7,346,545
Timestamp: 2015-07-01 23:53:07
Document Index: 690942413

Matched Legal Cases: ['Application No. 2457420', 'Application No. 2456485', 'Application No. 03132883', 'Application No. 03800852', 'Application No. 03132884', 'Application No. 03254308', 'Application No. 03254308', 'Application No. 03254308', 'Application No. 03254308', 'Application No. 03763216', 'Application No. 05789316', 'Application No. 03254214', 'Application No. 10001217', 'Application No. 03763495', 'Application No. 2004', 'Application No. 2003', 'Application No. 2003', 'Application No. 2007', 'Application No. 2003', 'Application No. 2003', 'Application No. 2003', 'Application No. 10', 'Application No. 03800852', 'Application No. 03763495', 'Application No. 05789316']

Patent US8095854 - Method and system for generating low density parity check codes - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign inAdvanced Patent SearchPatentsAn approach for generating a structured Low Density Parity Check (LDPC) codes is provided. Structure of the LDPC codes is provided by restricting a certain part of the parity check matrix to be lower triangular, hence enabling a very simple encoding method that does not require the generator matrix of...http://www.google.com/patents/US8095854?utm_source=gb-gplus-sharePatent US8095854 - Method and system for generating low density parity check codesAdvanced Patent SearchPublication numberUS8095854 B2Publication typeGrantApplication numberUS 11/938,016Publication dateJan 10, 2012Filing dateNov 9, 2007Priority dateJul 26, 2002Also published asUS20040019845, US20080082895Publication number11938016, 938016, US 8095854 B2, US 8095854B2, US-B2-8095854, US8095854 B2, US8095854B2InventorsMustafa Eroz, Feng-Wen Sun, Lin-nan LeeOriginal AssigneeDtvg Licensing, Inc.Export CitationBiBTeX, EndNote, RefManPatent Citations (103), Non-Patent Citations (96), Referenced by (5), Classifications (50), Legal Events (1) External Links: USPTO, USPTO Assignment, EspacenetMethod and system for generating low density parity check codes
US 8095854 B2Abstract
An approach for generating a structured Low Density Parity Check (LDPC) codes is provided. Structure of the LDPC codes is provided by restricting a certain part of the parity check matrix to be lower triangular, hence enabling a very simple encoding method that does not require the generator matrix of the code. The approach can also exploit the unequal error protecting capability of LDPC codes on transmitted bits to provide extra error protection to more vulnerable bits of high order modulation constellations (such as 8-PSK (Phase Shift Keying)).
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.
These and other needs are addressed by the present invention, wherein an approach for generating a structured Low Density Parity Check (LDPC) codes is provided. Structure of the LDPC codes is provided by restricting portion part of the parity check matrix to be lower triangular and/or satisfying other requirements such that the communication between processing nodes of the decoder becomes very simple. Also, the approach can advantageously exploit the unequal error protecting capability of LDPC codes on transmitted bits to provide extra error protection to more vulnerable bits of high order modulation constellations (such as 8-PSK (Phase Shift Keying)). Additionally, the parity check matrix can be algorithmically generated using pre-stored constants and bitwise operations.
a 10 i 0 +a 11 i 1 + . . . +a 1,k−1 i k−1 +b 10 p 0 +p 1=0 Solve p 1 and similarly for p 2 , p 3 , . . . , p n−k−1.
*y j=−ƒ(0,e j) j=0, 1, 2 where ƒ(a,b)=max(a,b)+LUTƒ(a,b) with LUTƒ(a,b)=ln(1+e −|a-b|)
*x j =y j +e j j=0, 1, 2
*p 0 =x 0 +x 1 +x 2 p 4 =y 0 +x 1 +x 2 p 1 =x 0 +x 1 +y 2 p 5 =y 0 +x 1 +y 2 p 2 =x 0 +y 1 +x 2 p 6 =y 0 +y 1 +x 2 p 3 =x 0 +y 1 +y 2 p 7 =y 0 +y 1 +y 2 Next, the bit metric generator 307 determines a priori log likelihood ratios of the coded bits as input to LDPC decoder 305, as follows:
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 It is noted that the function ƒ(.) with more than two variables can be evaluated recursively; e.g. ƒ(a,b,c)=ƒ(ƒ(a,b),c).
Per step 1007, it is determined whether all the parity check equations are satisfied. If these parity check equations are not satisfied, then the decoder 305, as in step 1009, re-derives 8-PSK bit metrics and channel input un. Next, the bit node is updated, as in step 1011. As shown in FIG. 13C, the incoming messages to the bit node n from its dv, adjacent check nodes are denoted by wk 1 →n, wk 2 →n, . . . , wk dv →n The outgoing messages from the bit node n are computed back to d, adjacent check nodes; such messages are denoted by vn→k 1 , vn→k 2 , . . . , vn→k dv and computed as follows:
v n → k i = u n + ∑ j ≠ i w k j → n In step 1013, the decoder 305 outputs the hard decision (in the case that all parity check equations are satisfied):
The second approach to implementing LDPC codes is to physically realize only a subset of the total number of the nodes and use only these limited number of “physical” nodes to process all of the “functional” nodes of the code. Even though the LDPC decoder operations can be made extremely simple and can be performed in parallel, the further challenge in the design is how the communication is established between “randomly” distributed bit nodes and check nodes. The decoder 305, of FIG. 3, according to one embodiment of the present invention, addresses this problem by accessing memory in a structured way, as to realize a seemingly random code. This approach is explained with respect to FIGS. 14A and 14B.
Continuing with the above example, a group of 392 bit nodes and 392 check nodes are selected for processing at a time. For 392 check node processing, q consecutive rows are accessed from the top edge RAM, and 2 consecutive rows from the bottom edge RAM. In this instance, q+2 is the degree of each check node. For bit node processing, if the group of 392 bit nodes has degree 2, their edges are located in 2 consecutive rows of the bottom edge RAM. If the bit nodes have degree d>2, their edges are located in some d rows of the top edge RAM. The address of these d rows can be stored in non-volatile memory, such as Read-Only Memory (ROM). The edges in one of the rows correspond to the first edges of 392 bit nodes, the edges in another row correspond to the second edges of 392 bit nodes, etc. Moreover for each row, the column index of the edge that belongs to the first bit node in the group of 392 can also be stored in ROM. The edges that correspond to the second, third, etc. bit nodes follow the starting column index in a “wrapped around” fashion. For example, if the jth edge in the row belongs to the first bit node, then the (j+1)st edge belongs to the second bit node, (j+2)nd edge belongs to the third bit node, . . . , and (j−1)st edge belongs to the 392th bit node.
The computer system 1500 also includes a communication interface 1517 coupled to bus 1501. The communication interface 1517 provides a two-way data communication coupling to a network link 1519 connected to a local network 1521. For example, the communication interface 1517 may be a digital subscriber line (DSL) card or modem, an integrated services digital network (ISDN) card, a cable modem, or a telephone modem to provide a data communication connection to a corresponding type of telephone line. As another example, communication interface 1517 may be a local area network (LAN) card (e.g. for Ethernet™ or an Asynchronous Transfer Mode (ATM) network) to provide a data communication connection to a compatible LAN. Wireless links can also be implemented. In any such implementation, communication interface 1517 sends and receives electrical, electromagnetic, or optical signals that carry digital data streams representing various types of information. Further, the communication interface 1517 can include peripheral interface devices, such as a Universal Serial Bus (USB) interface, a PCMCIA (Personal Computer Memory Card International Association) interface, etc.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS4709377 *Mar 13, 1985Nov 24, 1987ParadyneViterbi decoder for wireline modemsUS5099484Jun 9, 1989Mar 24, 1992Digital Equipment CorporationMultiple bit error detection and correction system employing a modified Reed-Solomon code incorporating address parity and catastrophic failure detectionUS5371471 *Oct 29, 1993Dec 6, 1994General Electric CompanyLow complexity adaptive equalizer radio receiver employing direct reference state updatesUS5467132 *Nov 29, 1993Nov 14, 1995Deutsche Forschungsansalt Fur Luft-Und Raumfahrt E.V.Method for digital transmission of hierarchical HDTV, EDTV and SDTV television signalsUS5559990Oct 24, 1994Sep 24, 1996Advanced Micro Devices, Inc.Memories with burst mode accessUS5949796 *Jun 19, 1996Sep 7, 1999Kumar; Derek D.In-band on-channel digital broadcasting method and systemUS6031874 *Sep 26, 1997Feb 29, 2000Ericsson Inc.Unequal error protection in coded modulation schemesUS6075408Dec 30, 1998Jun 13, 2000International Business Machines Corp.OQPSK phase and timing detectionUS6097703Dec 19, 1995Aug 1, 2000Salbu Research And Development (Proprietary Limited)Multi-hop packet radio networksUS6115427 *Apr 25, 1997Sep 5, 2000At&T Corp.Method and apparatus for data transmission using multiple transmit antennasUS6216200Mar 14, 1995Apr 10, 2001Mips Technologies, Inc.Address queueUS6292917 *Sep 30, 1998Sep 18, 2001Agere Systems Guardian Corp.Unequal error protection for digital broadcasting using channel classificationUS6405338 *Feb 11, 1998Jun 11, 2002Lucent Technologies Inc.Unequal error protection for perceptual audio codersUS6438180 *Mar 1, 1999Aug 20, 2002Carnegie Mellon UniversitySoft and hard sequence detection in ISI memory channelsUS6510536 *Jun 1, 1999Jan 21, 2003Her Majesty The Queen In Right Of Canada, As Represented By The Minister Of Industry Through The Communications Research CentreReduced-complexity max-log-APP decoders and related turbo decodersUS6518892 *Jul 6, 2001Feb 11, 2003Broadcom CorporationStopping criteria for iterative decodingUS6539367 *May 26, 2000Mar 25, 2003Agere Systems Inc.Methods and apparatus for decoding of general codes on probability dependency graphsUS6553535Aug 20, 1999Apr 22, 2003Massachusetts Institute Of TechnologyPower-efficient communication protocolUS6567465Jun 27, 2001May 20, 2003Pc Tel Inc.DSL modem utilizing low density parity check codesUS6633856Oct 10, 2001Oct 14, 2003Flarion Technologies, Inc.Methods and apparatus for decoding LDPC codesUS6665361Mar 4, 1999Dec 16, 2003Inmarsat, Ltd.Communication method and apparatusUS6715121Oct 12, 2000Mar 30, 2004Thomson-CsfSimple and systematic process for constructing and coding LDPC codesUS6718508May 25, 2001Apr 6, 2004Her Majesty The Queen In Right Of Canada, As Represented By The Minister Of Industry Through The Communication Research CentreHigh-performance error-correcting codes with skew mappingUS6751770 *Oct 10, 2001Jun 15, 2004Sony CorporationDecoder for iterative decoding of binary cyclic codesUS6769091 *Oct 17, 2001Jul 27, 2004Motorola, Inc.Encoding method and apparatus using squished trellis codesUS6785863 *Sep 18, 2002Aug 31, 2004Motorola, Inc.Method and apparatus for generating parity-check bits from a symbol setUS6789227Jul 5, 2001Sep 7, 2004International Business Machines CorporationSystem and method for generating low density parity check codes using bit-fillingUS6829308 *Jan 28, 2003Dec 7, 2004Hughes Electronics CorporationSatellite communication system utilizing low density parity check codesUS6857097 *May 16, 2001Feb 15, 2005Mitsubishi Electric Research Laboratories, Inc.Evaluating and optimizing error-correcting codes using a renormalization group transformationUS6895547 *Jul 11, 2001May 17, 2005International Business Machines CorporationMethod and apparatus for low density parity check encoding of dataUS6901119 *Feb 22, 2001May 31, 2005International Business Machines CorporationMethod and apparatus for implementing soft-input/soft-output iterative detectors/decodersUS6938196 *Apr 4, 2002Aug 30, 2005Flarion Technologies, Inc.Node processors for use in parity check decodersUS6950461Sep 24, 2001Sep 27, 2005Pctel, Inc.Modems utilizing low density parity check codesUS6963622Jul 3, 2003Nov 8, 2005The Directv Group, Inc.Bit labeling for amplitude phase shift constellation used with low density parity check (LDPC) codesUS6965652Dec 7, 2000Nov 15, 2005Marvell International Ltd.Address generator for LDPC encoder and decoder and method thereofUS6985536 *Jan 11, 2002Jan 10, 2006International Business Machines CorporationBlock coding for multilevel data communicationUS7000177 *Dec 7, 2000Feb 14, 2006Marvell International Ltd.Parity check matrix and method of forming thereofUS7017106 *Jul 29, 2004Mar 21, 2006Broadcom CorporationLow density parity check (LDPC) code decoder using min*, min**, max* or max** and their respective inversesUS7072417Dec 7, 2000Jul 4, 2006Marvell International Ltd.LDPC encoder and method thereofUS7116710May 18, 2001Oct 3, 2006California Institute Of TechnologySerial concatenation of interleaved convolutional codes forming turbo-like codesUS7165205Jun 23, 2004Jan 16, 2007Motorola, Inc.Method and apparatus for encoding and decoding dataUS7178082Apr 29, 2004Feb 13, 2007Samsung Electronics Co., Ltd.Apparatus and method for encoding a low density parity check codeUS7184486 *Dec 7, 2000Feb 27, 2007Marvell International Ltd.LDPC encoder and decoder and method thereofUS7191378Jul 3, 2003Mar 13, 2007The Directv Group, Inc.Method and system for providing low density parity check (LDPC) encodingUS7421644Nov 18, 2005Sep 2, 2008Research In Motion LimitedHybrid automatic repeat request system and methodUS7620880Dec 20, 2005Nov 17, 2009Samsung Electronics Co., Ltd.LDPC concatenation rules for IEEE 802.11n system with packets length specified in OFDM symbolsUS20020002695Jun 1, 2001Jan 3, 2002Frank KschischangMethod and system for decodingUS20020021770 *May 3, 2001Feb 21, 2002Beerel Peter A.Reduced-latency soft-in/soft-out moduleUS20020042899Jun 18, 2001Apr 11, 2002Tzannes Marcos C.Systems and methods for LDPC coded modulationUS20020048329 *Sep 12, 2001Apr 25, 2002Tran Hau ThienMethod and apparatus for min star calculations in a map decoderUS20020051499 *Sep 5, 2001May 2, 2002Cameron Kelly B.Quasi error free (QEF) communication using turbo codesUS20020051501Apr 30, 2001May 2, 2002Victor DemjanenkoUse of turbo-like codes for QAM modulation using independent I and Q decoding techniques and applications to xDSL systemsUS20020071504 *Jun 14, 2001Jun 13, 2002Xiaopeng ChenMethod for iterative and non-iterative data detection using reduced-state soft-input/soft-output algorithms for complexity reductionUS20020136318 *Jan 14, 2002Sep 26, 2002Alexei GorokhovTransmission system for transmitting a multilevel signalUS20020141507Jan 31, 2001Oct 3, 2002Motorola, Inc.Method and apparatus for error correctionUS20020150167Feb 19, 2002Oct 17, 2002Victor DemjanenkoMethods and apparatus for configurable or assymetric forward error correctionUS20020153938Jul 23, 2001Oct 24, 2002Siemens Ag.Hybrid power MOSFETUS20020188906Mar 8, 2002Dec 12, 2002Kurtas Erozan M.Method and coding apparatus using low density parity check codes for data storage or data transmissionUS20030014718Jul 5, 2001Jan 16, 2003International Business Machines CorporationSystem and method for generating low density parity check codes using bit-fillingUS20030023917Apr 4, 2002Jan 30, 2003Tom RichardsonNode processors for use in parity check decodersUS20030033570May 9, 2002Feb 13, 2003Khannanov Roman R.Method and apparatus for encoding and decoding low density parity check codes and low density turbo product codesUS20030033575Oct 10, 2001Feb 13, 2003Tom RichardsonMethods and apparatus for decoding LDPC codesUS20030037298 *Jul 11, 2001Feb 20, 2003International Business Machines CorporationMethod and apparatus for low density parity check encoding of dataUS20030058958Dec 21, 2001Mar 27, 2003Digital Fountain, Inc.Multi-stage code generator and decoder for communication systemsUS20030065989Oct 1, 2001Apr 3, 2003Yedida Jonathan S.Evaluating and optimizing error-correcting codes using projective analysisUS20030074626Jan 8, 2002Apr 17, 2003International Business Machines CorporationDecoding low density parity check codesUS20030079171Oct 24, 2001Apr 24, 2003Tim CoeForward error correctionUS20030079172Jul 16, 2002Apr 24, 2003Hiroyuki YamagishiEncoding method and encoderUS20030081691Oct 29, 2001May 1, 2003D.S.P.C. Technologies Ltd.Method and apparatus for decoding lattice codes and multilevel coset codesUS20030091098Oct 25, 2002May 15, 2003Antti ManninenPartially filling block interleaver for a communication systemUS20030104788Aug 30, 2002Jun 5, 2003Sungwook KimDecoding architecture for low density parity check codesUS20030126551Dec 19, 2000Jul 3, 2003Ramesh ManthaHybrid automatic repeat request system and methodUS20030187899Mar 28, 2003Oct 2, 2003Fujitsu LimitedMatrix operation processing deviceUS20030203721Apr 22, 2003Oct 30, 2003Raytheon CompanyAdaptive air interface waveformUS20030207696May 6, 2002Nov 6, 2003Serge WilleneggerMulti-media broadcast and multicast service (MBMS) in a wireless communications systemUS20040034827Feb 19, 2003Feb 19, 2004Ba-Zhong ShenLow density parity check (LDPC) code decoder using min*, min**, max* or max** and their respective inversesUS20040034828Dec 26, 2002Feb 19, 2004Texas Instruments IncorporatedHardware-efficient low density parity check code for digital communicationsUS20040064779Aug 5, 2003Apr 1, 2004Seagate Technology LlcSystem and method for iterative decoding of Reed-Muller codesUS20040093554Sep 30, 2003May 13, 2004Certance LlcChannel processor using reduced complexity LDPC decoderUS20040098659Nov 18, 2002May 20, 2004Bjerke Bjorn A.Rate-compatible LDPC codesUS20040196861Jan 12, 2001Oct 7, 2004Joseph RinchiusoPacket data transmission within a broad-band communication systemUS20040221223Apr 29, 2004Nov 4, 2004Nam-Yul YuApparatus and method for encoding a low density parity check codeUS20050005231Jul 1, 2004Jan 6, 2005Feng-Wen SunMethod and system for generating parallel decodable low density parity check (LDPC) codesUS20050063484Oct 8, 2004Mar 24, 2005Mustafa ErozSatellite communincation system utilizing low density parity check codesUS20050149841Nov 15, 2004Jul 7, 2005Samsung Electronics Co., Ltd.Channel coding/decoding apparatus and method using a parallel concatenated low density parity check codeUS20050154958Mar 31, 2004Jul 14, 2005Bo XiaMethod and apparatus for varying lengths of low density party check codewordsUS20050235195Feb 14, 2005Oct 20, 2005Seung-Hoon ChoiApparatus and method for encoding and decoding a low density parity check code with maximum error correction and error detection capabilityUS20050257124Jul 11, 2005Nov 17, 2005Tom RichardsonNode processors for use in parity check decodersUS20050265387Mar 30, 2005Dec 1, 2005Khojastepour Mohammad AGeneral code design for the relay channel and factor graph decodingUS20050278606Jul 24, 2003Dec 15, 2005Tom RichardsonMethods and apparatus for decoding ldpc codesUS20060156181Oct 27, 2005Jul 13, 2006Samsung Electronics Co., Ltd.Method for puncturing an LDPC channel codeUS20080282127Jul 23, 2008Nov 13, 2008Ramesh ManthaHybrid automatic repeat request system and methodCA2310186A1Jun 2, 2000Dec 2, 2001Jeffrey P. CasturaMethod and system for decodingEP1093231A1Oct 10, 2000Apr 18, 2001Thomson-CsfConstruction method of LDPC codes,and simple systematic coding of LDPC codesJP2002094450A Title not availableWO2002056559A1Dec 14, 2001Jul 18, 2002Koninkl Philips Electronics NvBit interleaved coded modulation (bicm) mappingWO2002099976A2Mar 8, 2002Dec 12, 2002Seagate Technology LlcA method and coding apparatus using low density parity check codes for data storage or data transmissionWO2002103631A1May 31, 2002Dec 27, 2002Flarion Technologies IncMethods and apparatus for decoding ldpc codesWO2003001726A1Jun 14, 2002Jan 3, 2003Alexei GorokhovMimo transmission system in a radio communications networkWO2003065591A2May 30, 2002Aug 7, 2003Seagate Technology LlcA method and decoding apparatus using linear code with parity check matrices composed from circulantsWO2003088504A1Apr 14, 2003Oct 23, 2003Emmanuel BoutillonMethod for coding and/or decoding error correcting codes, and corresponding devices and signalWO2004019268A1Dec 18, 2002Mar 4, 2004Flarion Technologies IncMethods and apparatus for encoding ldpc codesWO2004077733A2Feb 26, 2004Sep 10, 2004Flarion Technologies IncMethod and apparatus for performing low-density parity-check (ldpc) code operations using a multi-level permutation* Cited by examinerNon-Patent CitationsReference1Al-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.2Bond, J.W.; Hui, S.; Schmidt, H.; "Constructing Low-Density Parity-Check Codes with Circulant Matrices"; Information Theory and Networking Workshop; 1999; Metsovo, Greece; Jun. 27-Jul. 1, 1999; p. 52; XP010365561; ISBN:978-0-7803-5954-3.3Bond, 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.4Boutillon, E. et al.; "Decoder-First Code Design"; Proceedings; International Symposium on Turbo Codes and Related Topics; pp. 459-462; Sep. 4-7, 2000.5Boutros, J. et al.; "Generalized Low Density (Tanner) Codes"; 1999 IEEE International Conference on Communications; vol. 1; Jun. 6-10, 1999; pp. 441-445.6Brink, S. et al.; "Iterative Demapping of QPSK Modulation"; Electronics Letters, IEE; Stevenage, Great Britain; vol. 34, No. 15; Jul. 23, 1998; pp. 1495-1460.7Canadian Office action dated Jan. 22, 2010 in Canadian Patent Application No. 2457420 filed Jul. 3, 2003 by Mustafa Eroz et al.; 3 pages.8Canadian Office action dated May 7, 2010 in Canadian Patent Application No. 2456485 filed Jul. 3, 2003 by Mustafa Eroz et al.9Chen et al.; "High Throughput Overlapped Message Passing for Low Density Parity Check Codes"; GLSVLSI '03; Apr. 28-29, 2003.10Chinese 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.11Chinese Office action dated Jul. 22, 2011 in Chinese Patent Application No. 03800852.1 filed Jul. 3, 2003 by Mustafa Eroz et al.12Chinese Office Action dated Sep. 19, 2008 in Chinese Patent Application No. 03132884.9 filed Jul. 24, 2003 by Mustafa Eroz et al.13Douillard, Catherine; Jezequel, Michel; Berrou, Claude; "Iterative Correction of Intersymbol Interference: Turbo-Equalization"; European Transactions on Telecommunications and related Technologies, AEI; Milano, Italy; vol. 6, No. 5; Sep.-Oct. 1995; pp. 507-511.14Duman, T. M. et al.; "Performance Bounds for Turbo-Coded Modulation Systems"; IEEE Transactions on Communications; vol. 47, No. 4; Apr. 1999; pp. 511-521.15Echard, Rich et al.; "The pi-Rotation Low-Density Parity Check Codes"; 2001 IEEE; XP-001099251.16Echard, Rich et al.; "The π-Rotation Low-Density Parity Check Codes"; 2001 IEEE; XP-001099251.17Eleftheriou, 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.18Eleftheriou, E.; "G.gen: LDPC Codes for G.dmt.bis and G.lite.bis"; Jan. 2001; http://stanford.edu/class/ee379b/class-reader/ibm3.pdf.19Eleftheriou, E.; "G.gen: LDPC Codes for G.dmt.bis and G.lite.bis"; Jan. 2001; http://stanford.edu/class/ee379b/class—reader/ibm3.pdf.20Engling, Yeo et al.; "VLSI Architectures for Iterative Decoders in Magnetic Recording Channels"; IEEE Transactions on Magnetics; vol. 37, Issue 2; Mar. 2001; pp. 748-755.21EPO 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.22EPO 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.23EPO 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.24EPO 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.25EPO Summons to attend oral proceedings dated Mar. 11, 2010 in European Patent Application No. 03763216.3 filed Jul. 3, 2003 by Mustafa Eroz et al.26EPO 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.27EPO Summons to attend oral proceedings dated Nov. 17, 2009 in European Patent Application No. 03254214.4 filed Jul. 2, 2003 by Mustafa Eroz et al.; 14 pages.28ESTI; "Digital Video Broadcasting (DVB); Second Generation Framing Structure, Channel Coding and Modulation Systems for Broadcasting, Interactive Services, News Gathering and Other Broadband Satellite Applications"; ETSI Drafts, LIS; Jun. 1, 2004; XP002325753; ISSN: 0000-0002; pp. 21-23.29European Search Report dated May 10, 2010 in European divisional Patent Application No. 10001217.8 filed Jul. 3, 2003 (parent filing date of European Patent Application No. 03763495.3) by Mustafa Eroz et al.30Final Rejection dated Dec. 31, 2008 in U.S. Appl. No. 11/201,796, filed Aug. 10, 2005 by Mustafa Eroz et al.31Final Rejection dated Feb. 25, 2010 in U.S. Appl. No. 10/961,124, filed Oct. 8, 2004 by Mustafa Eroz et al.32Final Rejection dated Feb. 27, 2009 in U.S. Appl. No. 10/353,230, filed Jan. 28, 2003 by Mustafa Eroz et al.33Final Rejection dated Oct. 28, 2008 in U.S. Appl. No. 10/961,124, filed Oct. 8, 2004 by Mustafa Eroz et al.34Flarion; "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.35Flarion; "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.36Futaki, 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.37Gallagher, R.G.; "Low-Density Parity Check Codes"; IRE Transactions of Information Theory; 1962; pp. 21-28; XP-000992693.38Goff; "Signal Constellations for Bit-Interleaved Coded Modulation"; IEEE Transactions on Information Theory; vol. 49, No. 1; Jan. 2003; pp. 307-313.39Hagenauer, 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.40Hagenauer, 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.41Hou, Jilei; Siegel, Paul H.; Milstein, Laurence B.; Pfister, Henry D.; "Design of Low-Density Parity-Check Codes for Bandwidth Efficient Modulation"; Proceedings of the 2001 IEEE Information Theory Workshop; Cairns, Australia; Sep. 2-7, 2001; pp. 24-26.42Howland, C. and Blanksby, A.; "Parallel Decoding Architectures for Low Density Parity Check Codes"; 2001 IEEE International Symposium on Circuits and Systems (ISCAS 2001); vol. 4; pp. IV-742-IV-745.43Japanese Appeal Decision of Rejection dated Sep. 28, 2009 in Japanese Patent Application No. 2004-562643 filed Jul. 3, 2003 by Mustafa Eroz et al.; 9 pages.44Japanese 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.45Japanese 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.46Japanese Office action dated Apr. 19, 2011 in Japanese Patent Application No. 2007-525661 filed Aug. 3, 2005 by Mustafa Eroz et al.47Japanese 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.48Japanese 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.49Japanese 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.50Johnson, S. et al.; "Construction of Low-Density Parity-Check Codes from Kirkman Triple Systems"; Proceedings, IEEE Global Telecommunications Conference 2001; pp. 970-974; Nov. 25-29, 2001.51Johnson, Sarah J.; Weller, Steven R.; "A Family of Irregular LDPC Codes with Low Encoding Complexity"; IEEE Communications Letters; IEEE Service Center; Piscataway, New Jersey, USA; vol. 7, No. 2; Feb. 1, 2003; XP011066488; ISSN:1089-7798.52Korean 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.53Le 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.54Lee, Heung-No; "LDPC Coded Modulation MIMO OFDM Transceiver: Performance Comparison with Map Equalization"; Proceedings, IEEE Vehicular Technology Conference, VTC, 2003-Spring; Jeju, Korea; vol. 2; Apr. 22-25, 2003; pp. 1178-1182; XP010862634; ISBN: 978-0-7803-7757-8.55Li, 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.56Li, Xiaodong; Ritcey, James A.; "Bit-Interleaved Coded Modulation with Iterative Decoding"; 1999 IEEE International Conference on Communications; ICC 1999; pp. 858-863.57Lu, Ben; Yue, Guosen; Wang, Xiaodong; "Performance Analysis and Design Optimization of LDPC-Coded MIMO OFDM Systems"; IEEE Transactions on Signal Processing, IEEE Service Center; New York, New York, USA; vol. 52, No. 2; Feb. 1, 2004; pp. 348-361; XP011105722; ISSN: 1053-587X.58Mackay, 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.59Mansour et al.; "Low-Power VLSI Decoder Architectures for LDPC Codes", Proceedings, IEEE International Symposium on Lower Power Electronics and Design; ISLPED '02; pp. 284-289; Aug. 12-14, 2002.60Meglicki; "Linear Codes"; Apr. 2005; http://beige.ucs.indiana.edu/M743/node119.html.61Narayanaswami, R.; "Coded Modulation with Low Density Parity Check Codes"; Master thesis; Texas A&M University; Jun. 2001; XP2271230.62Non-final Office action dated Apr. 25, 2011 in U.S. Appl. No. 12/967,894, filed Dec. 14, 2010 by Mustafa Eroz et al.63Non-final Office Action dated Apr. 3, 2009 in U.S. Appl. No. 10/961,124, filed Oct. 8, 2004 by Mustafa Eroz et al.64Non-final Office Action dated Aug. 13, 2008 in U.S. Appl. No. 11/201,796, filed Aug. 10, 2005 by Mustafa Eroz et al.65Non-final Office action dated Aug. 16, 2010 in U.S. Appl. No. 12/195,512, filed Aug. 21, 2008 by Mustafa Eroz et al.66Non-final Office Action dated Jun. 11, 2008 in U.S. Appl. No. 10/961,124, filed Oct. 8, 2004 by Mustafa Eroz et al.67Non-final Office action dated May 12, 2011 in U.S. Appl. No. 11/938,110, filed Nov. 9, 2007 by Mustafa Eroz et al.68Non-final Office action dated May 16, 2011 in U.S. Appl. No. 12/498,968, filed Jul. 7, 2009 by Mustafa Eroz et al.69Non-final Office Action dated May 30, 2009 in U.S. Appl. No. 11/201,796, filed Aug. 11, 2005 by Mustafa Eroz et al.70Non-final Office Action dated Nov. 13, 2007 in U.S. Appl. No. 11/635,998, filed Dec. 8, 2006 by Mustafa Eroz et al.71Non-final Office Action dated Nov. 27, 2007 in U.S. Appl. No. 10/961,124, filed Oct. 8, 2004 by Mustafa Eroz et al.72Non-final Office Action dated Sep. 23, 2008 in U.S. Appl. No. 11/186,265, filed Jul. 21, 2005 by Mustafa Eroz et al.73Non-final Office Action dated Sep. 30, 2009 in U.S. Appl. No. 10/961,124, filed Oct. 8, 2004 by Mustafa Eroz et al.74Notice of Allowance dated Aug. 24, 2010 in U.S. Appl. No. 10/961,124, filed Oct. 8, 2004 by Mustafa Eroz et al.75Notice of Allowance dated Feb. 9, 2011 in U.S. Appl. No. 11/710,761, filed Feb. 26, 2007 by Mustafa Eroz et al.76Notice of Allowance dated Jan. 21, 2011 in U.S. Appl. No. 12/195,512, filed Aug. 21, 2008 by Mustafa Eroz et al.77Notice of Allowance dated May 5, 2008 in U.S. Appl. No. 11/635,998, filed Dec. 8, 2006 by Mustafa Eroz et al.78Notice of Allowance dated Oct. 17, 2007 in U.S. Appl. No. 11/059,938, filed Feb. 17, 2005 by Mustafa Eroz et al.79Ping, L. et al.; "Low Density Parity Check Codes with Semi-Random Parity Check Matrix"; Electronics Letters; IEEE Stevenage; vol. 35, No. 1; pp. 38-39; Jan. 7, 1999.80Rejection Decision dated Nov. 11, 2011 in Chinese Patent Application No. 03800852.1 filed Jul. 3, 2003 by Mustafa Eroz et al.81Richardson, 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.82Sci-Worx GMBH; "FEC-52 Next Generation FEC for Digital Video Broadcasting via Satellite"; www.sci-worx.com; 2003.83Selvarathinam, A. et al.; "A Massively Scaleable Decoder Architecture for Low-Density Parity-Check Codes"; Proceedings, IEEE International Symposium on Circuits and Systems; vol. 2; pp. 61-64; May 25-28, 2003.84Sipser et al.; "Expander Codes"; IEEE 1994; pp. 566-576.85Summons to Oral Proceedings dated Oct. 13, 2009 in European Patent Application No. 03763495.3 filed Jul. 3, 2003 by Mustafa Eroz et al.86Supplemental European Search Report dated Apr. 1, 2009 in European patent Application No. 05789316.6 filed Aug. 3, 2005 by Mustafa Eroz et al.87Tullberg, 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.88Vasic, B.; "Combinatorial Constructions of Low-Density Parity Check Codes for Iterative Decoding"; Proceedings, IEEE International Symposium on Information Theory; 2002; p. 312; Jun. 30-Jul. 5, 2002.89Vasic, 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.90Vasic, B.; Kirkman Systems and Their Application in Perpendicular Magnetic Recording; IEEE Transactions on Magnetics; vol. 38, No. 4; pp. 1705-1710; Jul. 2002.91Vasic, Bane; Djordjevic, Ivan B.; "Low-Density Parity Check Codes for Long-Haul Optical Communication Systems"; IEEE Photonics Technology Letters; IEEE Photonics Technology Letters; IEEE Service Center; Piscataway, New Jersey, USA; vol. 14, No. 8; Aug. 1, 2002; XP011067271; ISSN:1041-1135.92Wadayama, Sho; "Low Density Parity Check Code and Decoding Method"; Tokyo, Japan; Jun. 5, 2002; Triceps Corporation; pp. 123-131; ISBN: 4-88657-222-7.93Wadayama, Takashi; "A Coded Modulation Scheme Based on Low Density Parity Check Codes"; IEICE Transaction on Fundamentals; Oct. 2001; vol. E84-A; pp. 2523-2527.94Wesel et al.; "Constellation Labeling for Linear Encoders"; IEEE Transactions on Information Theory; vol. 47, No. 6; Sep. 2001; pp. 2417-2431.95Yi, 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.96Zhang, 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.Referenced byCiting PatentFiling datePublication dateApplicantTitleUS8402341Feb 18, 2010Mar 19, 2013Mustafa ErozMethod and system for providing low density parity check (LDPC) encoding and decodingUS8683292Mar 9, 2013Mar 25, 2014Hughes Network Systems, LlcMethod and system for providing low density parity check (LDPC) coding for scrambled coded multiple access (SCMA)US8782489Mar 6, 2013Jul 15, 2014Hughes Network Systems, LlcMethod and system for providing Low Density Parity Check (LDPC) encoding and decodingUS8887024Feb 10, 2013Nov 11, 2014Hughes Network Systems, LlcApparatus and method for improved modulation and coding schemes for broadband satellite communications systemsUS8972834Aug 28, 2012Mar 3, 2015Hughes Network Systems, LlcSystem and method for communicating with low density parity check codesClassifications U.S. Classification714/774, 714/758International ClassificationH03M13/11, H03M13/00, H04H40/90, H03M13/15, H03M13/25, H04L1/00, H04L27/20, H03M13/29, H04L27/34, H04L27/36Cooperative ClassificationH04L1/00, H04L1/0065, H03M13/1165, H04H40/90, H04L1/0057, H03M13/112, H04L27/2053, H04L27/186, H04L1/006, H04L1/0071, H03M13/152, H03M13/2906, H03M13/1137, H04L1/0061, H03M13/6583, H04L1/005, H04L1/007, H03M13/356, H03M13/255, H03M13/1111European ClassificationH04L1/00B7E, H04L1/00B7B, H04L27/20D2, H04L1/00B7U, H04L27/18P, H04L1/00B7K1, H04L1/00B5E5, H03M13/29B, H04L1/00, H03M13/25L, H04L1/00B7C1, H04L1/00B7V, H03M13/11L1S3, H03M13/65V2, H03M13/11L1D, H03M13/11L3E5, H03M13/35U, H03M13/11L1D3CLegal EventsDateCodeEventDescriptionMay 12, 2009ASAssignmentOwner name: DTVG LICENSING, INC., CALIFORNIAFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:HUGHES ELECTRONICS CORPORATION;REEL/FRAME:022668/0373Effective date: 20090512Owner name: DTVG LICENSING, INC.,CALIFORNIAFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:HUGHES ELECTRONICS CORPORATION;US-ASSIGNMENT DATABASE UPDATED:20100225;REEL/FRAME:22668/373Owner name: DTVG LICENSING, INC.,CALIFORNIAFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:HUGHES ELECTRONICS CORPORATION;US-ASSIGNMENT DATABASE UPDATED:20100225;REEL/FRAME:22668/373Effective date: 20090512Owner name: DTVG LICENSING, INC.,CALIFORNIAFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNOR:HUGHES ELECTRONICS CORPORATION;REEL/FRAME:022668/0373Effective date: 20090512RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services