as) United States
`a2) Patent Application Publication (10) Pub. No.: US 2004/0054960 Al
`(43) Pub. Date: Mar. 18, 2004
`
`Eroz et al.
`
`US 20040054960A1
`
`(54) METHOD AND SYSTEM FOR PROVIDING
`LOW DENSITY PARITY CHECK (LDPC)
`ENCODING
`
`(76)
`
`Inventors: Mustafa Eroz, Germantown, MD (US);
`Feng-Wen Sun, Germantown, MD
`(US); Lin-Nan Lee, Potomac, MD (US)
`
`Correspondence Address:
`Hughes Electronics Corporation
`Patent Docket Administration
`Bldg. 1, Mail Stop A109
`P.O. Box 956
`
`El Segundo, CA 90245-0956 (US)
`
`(21) Appl. No.:
`
`10/613,823
`
`(22) Filed:
`
`Jul. 3, 2003
`
`Related U.S. Application Data
`
`(00) Provisional application No. 60/393,457, filed on Jul.
`3, 2002. Provisional application No. 60/398,760,filed
`on Jul. 26, 2002. Provisional application No. 60/403,
`812, filed on Aug, 15, 2002, Provisional application
`No. 60/421,505, filed on Oct. 25, 2002. Provisional
`application No. 60/421,999, filed on Oct. 29, 2002.
`Provisional application No. 60/423,710, filed on Nov.
`4, 2002. Provisional application No. 60/440,199, filed
`
`on Jan. 15, 2003, Provisional application No. 60/447,
`641, filed on Feb, 14, 2003, Provisional application
`No. 60/456,220, filed on Mar. 20, 2003. Provisional
`application No. 60/469,356, filed on May 9, 2003.
`Provisional application No. 60/482,112,filed on Jun.
`24, 2003. Provisional application No. 60/482,107,
`filed on Jun. 24, 2003.
`
`Publication Classification
`
`(S51) mt. C1? ececcccccseueeeee GO6E 11/00; HO3M 13/00
`(2) US) Cl: scsscwenssmsoecseere ces TABOO
`
`(57)
`
`ABSTRACT
`
`An approach is provided for a method of encoding structure
`Low Density Parity Check (LDPC) codes. Memory storing
`information representing a structured parity check matrix of
`Low Density Parity Check (LDPC) codesis accessed during
`the encoding process. The information is organized in tabu-
`lar form, wherein each row represents occurrences of one
`values within a first column of a group of columns ofthe
`parity check matrix. The rows correspond to groups of
`columns of the parity check matrix, wherein subsequent
`columns within each of the groups are derived according to
`a predetermined operation. An LDPC codedsignal is output
`based on the stored information representing the parity
`check matrix.
`
`1611
`
`i613
`
`1615
`
`STORAGE
`DEVICE
`
`DISPLAY
`
`INPUT
`DEVICE
`
`
`
`
`
`
`CURSOR
`CONTROL
`
`
`
`PROCESSOR
`
`LGE 1004
`
`LGE 1004
`
`1
`
`

`

`Patent Application Publication Mar. 18, 2004 Sheet 1 of 17
`
`RECEIVER
`
`
`TRANSMITTER
`
`US 2004/0054960 Al
`
`105
`
`103
`
`101
`
`100 ~
`
`FIG.1
`
`2
`
`

`

`Patent Application Publication Mar. 18, 2004 Sheet 2 of 17
`
`US 2004/0054960 Al
`
`L0¢
`
`00@HILLINSNVHL
`
`YoOld
`
`
`
`COZ—802
`
`02
`
`YHOLVINGOWaA
`Odd]A4
`
`SOXNOS
`
`
`
`60¢lle
`
`60¢
`
`oda)Hod
`
`
`
`H3GOONSHIGOONA
`
` <$
`
`de‘Ds
`
`3
`
`
`
`

`

`Patent Application Publication Mar. 18,2004 Sheet 3 of 17
`
`US 2004/0054960 Al
`
`LDPC
`
`DECODER
`
`QO
`
`a
`oS
`26
`FS
`ae
`=
`re
`=
`SB[728bs
`= io
`=
`iu
`am oO
`
`303
`
`FIG.3
`
`4
`
`

`

`Patent Application Publication Mar. 18, 2004 Sheet 4 of 17
`
`US 2004/0054960 Al
`
`_-
`
`- =< x
`
`—-
`
`=< x
`
`—
`
`ped
`
`x
`
`— * MM KK OOK
`lSee CO
`I
`:
`AQ
`
`©L
`
`L
`
`nw
`
`<=
`
`OO
`-
`E
`&
`ec - Oro
`
`SE
`&
`&
`
`&
`
`3
`+ 2
`&
`
`«©= correo
`
`ow
`oc Oreoer
`
`_ NN
`oc
`cfc
`
`oO
`
`a uw
`c
`<x
`
`wo ~
`
`co
`Fad
`
`
`
`bitnodes
`
`FIG.4
`
`FIG.5
`
`5
`
`€
`€
`€
`

`

`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Sel We
`
`
`==LowertriangularH,
`RL
`AE+Ere
`
`Se‘1SSS
`
`
`
`
`etee
`i}
`feee
`
`iH DS
`|RAPAATAERMSnat
`
`
`
`LI
`
`Patent Application Publication Mar. 18, 2004 Sheet 5 of 17
`
`US 2004/0054960 Al
`
`
`
`Es/No(dB)
`
`oO
`3
`ih
`2
`
`™_
`2
`Lu
`—
`
`~N
`oS
`Lu
`—_
`
`oo
`3
`Lu
`—_
`
`st
`O
`uu
`™
`
`LO
`oO
`uw
`—
`
`wo
`S
`uu
`el
`
`NM
`2
`Lu
`_
`
`oo
`QO
`ee
`—
`
`aby 1013
`
`FIG.7
`
`6
`
`

`

`Patent Application Publication Mar. 18, 2004 Sheet 6 of 17
`
`US 2004/0054960 Al
`
`100o%Sgo“SobLO
`
`0000OgIgoTht
`
`ceLObot,SZoObl
`
`OOL
`
`oo
`
`dg8“Sis
`
`100ofSzs*S4110
`
`0000058g0OLl
`
`reLkog.Scoth
`
`001
`
`O10
`
`V8“Dls
`
`7
`
`

`

`|
`
`
`
`
`
`qT
`
` rEWAL
`
`
`
`
`
`
`
`
`
`
`
`
`mM
`i=
`
`FIG.9
`
`
`
`Es/No(dB)
`
`8
`
`

`

`Patent Application Publication Mar. 18, 2004 Sheet 8 of 17
`
`US 2004/0054960 Al
`
`AQONLidALvddn
`
`
`
`LI4Sd-8SAlWAG-3Y
`
`TANNVHOONVSOlW.LaWN
`
`LAdNI
`
`
`
`SNOILWNOAMOSHO
`
`éQSlSSiL¥S
`
`ALiWWdTVSaA
`
`l¥OIEALSOdVLAdLNOS00}
`
`
`
`
`
`
`
`NOISIOS0GYVHLAdLNO8001
`
`
`
`
`
`
`
`3QON¥O3HOaLWadnen
`
`
`
`NOLLVZITVLLININHO4H3dLOO}
`
`OlOld
`
`9
`
`
`
`

`

`Patent Application Publication
`
`Mar. 18, 2004 Sheet 9 of 17
`
`US 2004/0054960 Al
`
`
`
`NOISIO3GGHVHLNdLNOLLL
`
`
`
`
`
`
`
`NOILYZMVILIN]NWOsd3d
`
`LOLL
`
`
`
`JON¥O3HOauwaanan
`
`JOONLidSlvddnSOL}
`
`[4OI4FILSOdVLAdLNO
`
`
`
`SNOILVNOSMOSHO
`
`éGAlSSiLy$
`
`AllaV¥dTIV
`
`LOL}
`
`SHA
`
`LlOld
`
`10
`
`10
`
`
`
`
`
`
`
`
`

`

`Patent Application Publication Mar. 18, 2004 Sheet 10 of 17
`
`US 2004/0054960 Al
`
`
`
`Op.T+!1-1,z.13csWgeeeTMHONeeHEMacreMays=UYay
`
`PheTa
`
`del“Sis
`
`ate
`
`Oh“Old
`
`‘N=
`lye—wA
`
`VolDid
`
`uapoulig
`
`11
`
`11
`
`
`
`
`
`

`

`Patent Application Publication Mar. 18, 2004 Sheet 11 of 17
`
`US 2004/0054960 Al
`
`"%3LNdWOO
`
`
`
`OLdNHOO]WHOsHSd
`
`SNINYSL30
`
`Ih-,9|u|
`
`LEEL
`
`elel
`
`TATIWHVdNISLNdWOO
`
`
`
`‘ONIMOTIOSSHL
`
`!
`
`Uo
`
`GLE
`
`SATEVINVA
`
`
`
`GHYVMYO4SLNdWOOLOel
`
`
`
`GYVMYOSSYOLS
`
`
`
`STIEVIEVA€0E}
`
`
`
`QHVMYOVEALAdWOO
`
`
`
`SATEVIEVASOs
`
`GaLNdWOOGNYSSTEVINVA
`
`
`
`SaTaVINWACHYMYOVE
`
`
`
`QNIODLNOSLNdNOO
`
`
`
`GYvVMHYOdGAYOLSSHL
`
`
`
`NOaasvaSaDvssanL0E|
`
`12
`
`
`
`gel“Old
`
`VelOld
`
`12
`
`
`
`

`

`Patent Application Publication Mar. 18,2004 Sheet 12 of 17
`
`US 2004/0054960 Al
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`;
`
`
`
`
`
`
`
`
`
`
`
`
`
`|
`
`
`
`
`
`
`
`|
`
`
`
`so
`
`= 2
`2
`
`oD
`
`
`
`
`
`L
`
`
`
`
`AR L
`
`
`
`
`
`A
`
`858 8 $8 8
`ui
`Lu
`wi
`ww
`ww
`Lu
`Lu
`~
`a}eY 10119
`
`5
`Lu
`
`8
`Li
`
`B
`Lu
`
`FIG.14A
`
`13
`
`13
`
`

`

`Patent Application Publication Mar. 18,2004 Sheet 13 of 17
`
`US 2004/0054960 Al
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`00+3"1
`
`LO-a"}
`
`c0-3'|
`
`€0-4'1
`
`v0-3"1
`
`S0-3't
`
`90-31
`
`20-5'1
`
`80-3'1
`
`60-3'1
`
`ayey 4019
`
`dv‘Sls
`
`14
`
`14
`
`

`

`
`
`
`
`
`
`
`
`
`
` Nt
`
`
`
`
`
` A
`
`
`
`
`AH
`l
`HIEillTIRE.
`
`
`iM
`
`Patent Application Publication
`
`15
`
`

`

`Patent Application Publication Mar. 18,2004 Sheet 15 of 17
`
`US 2004/0054960 Al
`
` =o
`
`Sw=
`
`FIG.15A
`
`16
`
`

`

`Patent Application Publication Mar. 18, 2004 Sheet 16 of 17
`
`US 2004/0054960 Al
`
`©o
`
`a
`uD—
`
`FIG.15B
`
`17
`
`17
`
`

`

`US 2004/0054960 Al
`
`Patent Application Publication Mar. 18, 2004 Sheet 17 of 17
`SDVUOLSaeNIV!7=!6091
`AESSSSSSRSeeaaaeneeseseeeeeeeeeeeeeeeeee4
`£094afte;
`3OV4NSINI!:NOLLVOINAWWOOHS
`2091si
`
`39IAgdAHOWSN
`
`£091
`
`
`
`AV1dS10
`
`LOL
`
`LNdNI
`
`JOIASG
`
`eL9l
`
`YOSHNO
`
`TOHLNOO
`
`519k
`
`9}Old
`
`18
`
`18
`
`
`

`

`US 2004/0054960 Al
`
`Mar. 18, 2004
`
`METHOD AND SYSTEM FOR PROVIDING LOW
`DENSITY PARITY CHECK (LDPC) ENCODING
`
`RELATED APPLICATIONS
`
`(0001] This applicationis related to, and claims the benefit
`of the earlier filing date under 35 U.S.C. $119(e) of, U.S.
`Provisional Patent Application (Serial No. 60/393,457)filed
`Jul. 3, 2002 (Attorney Docket: PD-202095), entitled “Code
`Design and Implementation Improvements for Low Density
`Parity Check Codes,” U.S, Provisional Patent Application
`(Serial No. 60/398,760)
`filed Jul. 26, 2002 (Attorney
`Docket: PD-202101), entitled “Code Design and Implemen-
`tation Improvements for Low Density Parity Check Codes,”
`US. Provisional Patent Application (Serial No. 60/403,812)
`filed Aug. 15, 2002 (Attorney Docket: PD-202105), entitled
`“Power and Bandwidth Efficient Modulation and Coding
`Scheme for Direct Broadcast Satellite and Broadcast Satel-
`lite Communications,” U.S. Provisional Patent Application
`(Serial No. 60/421,505),
`filed Oct. 25, 2002 (Attorney
`Docket: PD-202101), entitled “Method and System for
`Generating Low Density Parity Check Codes,” U.S. Provi-
`sional Patent Application (Serial No. 60/421,999), filed Oct.
`29, 2002 (Attorney Docket: PD-202105), entitled “Satellite
`Communication System Utilizing Low Density Parity
`Check Codes,” U.S. Provisional Patent Application (Serial
`No. 60/423,710), filed Nov. 4, 2002 (Attorney Docket:
`PD-202101), entitled “Code Design and Implementation
`Improvements for Low Density Parity Check Codes,” U.S.
`Provisional Patent Application (Serial No. 60/440,199)filed
`Jan. 15, 2003 (Attorney Docket: PD-203009), entitled
`“Novel Solution to Routing Problem in Low Density Parity
`Check Decoders,” U.S. Provisional Patent Application
`(Serial No. 60/447,6041)
`filed Feb. 14, 2003 (Attorney
`Docket: PD-203016), entitled “Low Density Parity Check
`Code Encoder Design,” U.S. Provisional Patent Application
`(Serial No. 60/456,220)
`filed Mar. 20, 2003 (Attorney
`Docket: PD-203021), entitled “Description LDPC and BCH
`Encoders,” U.S. Provisional Patent Application filed May 9,
`2003 (Attorney Docket: PD-203030), entitled “Description
`LDPC and BCH Encoders,” U.S, Provisional Patent Appli-
`cation filed Jun, 24, 2003 (Attorney Docket: PD-203044),
`entitled “Description LDPC and BCH Encoders,” and U.S.
`Provisional Patent Applicationfiled Jun. 24, 2003 (Attorney
`Docket: PD-203059), entitled “Description LDPC and BCH
`Encoders”; the entireties of which are incorporated herein by
`reference.
`
`FIELD OP THE INVENTION
`
`invention relates to communication
`[0002] The present
`systems, and more particularly to coded systems.
`
`BACKGROUND OF THE INVENTION
`
`(0003] Communication systems employ coding to ensure
`reliable communication across noisy communication chan-
`nels. These communication channels exhibit a fixed capacity
`that can be expressed in terms of bits per symbol at certain
`signal to noise ratio (SNR), defining a theoretical upper limit
`(known as the Shannon limit). As a result, coding design has
`aimed to achieve rates approaching this Shannon limit. One
`such class of codes that approach the Shannon limit is Low
`Density Parity Check (LDPC) codes.
`[0004] Traditionally, LDPC codes have not been widely
`deployed because of a number of drawbacks. One drawback
`
`the LDPC encoding technique is highly complex.
`is that
`Encoding an LDPC code using its generator matrix would
`require storing a very large, non-sparse matrix. Additionally,
`LDPC codes require large blocks to be effective; conse-
`quently, even though parity check matrices of LDPC codes
`are sparse, storing these matrices is problematic.
`
`From an implementation perspective, a number of
`(0005]
`challenges are confronted. For example, storage is an impor-
`tant reason why LDPC codes have not become widespread
`in practice. Also, a key challenge in LDPC code implemen-
`tation has been how to achieve the connection network
`between several processing engines (nodes) in the decoder.
`Further, the computational load in the decoding process,
`specifically the check node operations, poses a problem.
`
`[0006] Therefore, there is a need for an LDPC communi-
`cation system that employs simple encoding and decoding
`processes. There is also a need for using LDPC codes
`efficiently to support bigh data rates, without introducing
`greater complexity. There is also a need to improve perfor-
`mance of LDPC encoders and decoders. There is also a need
`to minimize storage requirements for implementing LDPC
`coding. There is a further need for a scheme that simplifies
`the communication between processing nodes in the LDPC
`decoder,
`
`SUMMARY OFTHE INVENTION
`
`[0007] These and other needs are addressed bythe present
`invention, wherein an approach for encoding 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 satis-
`fying other
`requirements such that
`the communication
`between bit nodes and check nodes of the decoder
`is
`simplified. Memory storing information representing the
`structured parity check matrix is accessed. The information
`is organized in tabular form, wherein each row represents
`occurrences of one values within a first column of a group
`of columnsofthe parity check matrix. The rows correspond
`to groups of columns of the parity check matrix, wherein
`subsequent columns within each of the groups are derived
`according to a predetermined operation (e.g., cyclic shift,
`addition, etc.). An LDPC coded signal based on the stored
`information representing the parity check matrix. According
`to one embodiment of
`the present
`invention, a Bose
`Chaudhuri Hocquenghem (BCH) encoder is utilized by the
`transmitter to encode an input signal using BCH codes,
`wherein the output LDPC coded signal corresponding to the
`input signal represents a code having an outer BCH code and
`an inner LDPC code. Further, a cyclic redundancy check
`(CRC) encoder is supplied to encode the input signal accord-
`ing to a CRC code. The approach advantageously provides
`expedient encoding as well as decoding of LDPC codes.
`
`[0008] According to one aspect of an embodiment of the
`present invention, a method of encoding is disclosed, The
`method includes accessing memory storing information rep-
`resenting a structured parity check matrix of Low Density
`Parity Check (LDPC)codes. The information is organized in
`tabular form, wherein each row represents occurrences of
`one values within a first column ofa group of columns of the
`parity check matrix. The rows correspond to groups of
`columns of the parity check matrix, wherein subsequent
`columns within each of the groups are derived according to
`
`19
`
`19
`
`

`

`US 2004/0054960 Al
`
`Mar. 18, 2004
`
`[0018] FIG. 6 is a diagram of a sub-matrix of a sparse
`parity check matrix, wherein the sub-matrix contains parity
`check values restricted to the lower
`triangular
`region,
`according to an embodiment of the present invention;
`
`[0019] FIG. 7 is a graph showing performance between
`codes utilizing unrestricted parity check matrix (H matrix)
`versus restricted H matrix having a sub-matrix as in FIG. 6;
`[0020] FIGS. 8A and 8Bare, respectively, a diagram of a
`non-Gray 8-PSK modulation scheme, and a Gray 8-PSK
`modulation, each of which can be used in the system of FIG.
`1,
`
`[0021] FIG. 9 is a graph showing performance between
`codes utilizing Gray labeling versus non-Gray labeling;
`
`[0022] FIG. 10 is a flow chart of the operation of the
`LDPC decoder using non-Gray mapping, according to an
`embodiment of the present invention;
`
`[0023] FIG. 11 is a flow chart of the operation of the
`LDPC decoder of FIG, 3 using Gray mapping, according to
`an embodiment ofthe present invention;
`
`FIGS, 12A-12C are diagrams of the interactions
`[0024]
`between the check nodes and the bit nodes in a decoding
`process, according to an embodimentof the present inven-
`tion;
`
`[0025] FIGS. 13A and 13B are flowcharts of processes
`for computing outgoing messages between the check nodes
`and the bit nodes using, respectively, a forward-backward
`approach and a parallel approach, according to various
`embodiments of the present invention;
`
`[0026] FIGS. 14A-14 are graphs showing simulation
`results of LDPCcodes generated in accordance with various
`embodiments of the present invention;
`
`[0027] FIGS. 15A and 15B are diagrams ofthe top edge
`and bottom edge, respectively, of memory organized to
`support structured access asto realize randomness in LDPC
`coding, according to an embodiment of the present inven-
`tion; and
`
`[0028] FIG. 16 is a diagram of a computer system that can
`perform the processes of encoding and decoding of LDPC
`codes,
`in accordance with embodiments of the present
`invention,
`
`DESCRIPTION OF THE PREFERRED
`EMBODIMENT
`
`a predetermined operation. The method also includes out-
`putting an LDPC coded signal based on the stored informa-
`tion representing the parity check matrix.
`
`[0009] According to another aspect of an embodiment of
`the present invention, an encoder for generating Low Den-
`sity Parity Check (LDPC) codes disclosed. The encoder
`includes memory storing information representing a struc-
`tured parity check matrix of the LDPC codes, The informa-
`tion 1s organized in tabular form, wherein each row repre-
`sents occurrences of one values within a first column of a
`group of columns of the parity check matrix. The rows
`correspond to groups of columns of the parity check matrix,
`Wherein subsequent columns within each of the groups are
`derived according to a predetermined operation. The
`encoder also includes meansfor retrieving the stored infor-
`mation representing the parity check matrix to output an
`LDPC coded signal.
`
`[0010] According to another aspect of an embodiment of
`the present invention, a transmitter utilizing Low Density
`Parity Check (LDPC) coding disclosed. The transmitter
`includes memory storing information representing a struc-
`tured parity check matrix of the LDPC codes, the informa-
`tion being organized in tabular form, wherein each row
`represents occurrences of one values within afirst column of
`a group of columns of the parity check matrix. The rows
`correspond to groups of columns of the parity check matrix,
`wherein subsequent columns within each of the groups are
`derived according to a predetermined operation. The trans-
`mitter also includes an LDPC encoder configured to access
`the stored information from the memory to output an LDPC
`coded signal.
`
`[0011] Still other aspects, features, and advantages of the
`present invention are readily apparent from the following
`detailed description, simply by illustrating a number of
`particular embodiments and implementations, including the
`best mode contemplated for carrying out the present inven-
`tion, The present invention is also capable of other and
`different embodiments, and its several details can be modi-
`fied in various obvious respects, all without departing from
`the spirit and scope of the present invention. Accordingly,
`the drawing and description are to be regarded asillustrative
`in nature, and not as restrictive.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`invention is illustrated by way of
`[0012] The present
`example, and not by wayof limitation, in the figures of the
`accompanying drawings and in which like reference numer-
`als refer to similar elements and in which:
`
`(0013] FIG. 1 is a diagram of a communications system
`configured to utilize Low Density Parity Check (LDPC)
`codes, according to an embodimentof the present invention;
`
`[0014] FIGS. 2A and 2B are diagrams of exemplary
`LDPC encoders deployed in the transmitter of FIG. 1;
`
`{0015] FIG.3 is a diagram of an exemplary receiver in the
`system of FIG. 1;
`
`[0029] A system, method, and software for efficiently
`decoding structured Low Density Parity Check (LDPC)
`codes are described. In the following description, for the
`purposes of explanation, numerous specific details are set
`forth in order to provide a thorough understanding of the
`present invention. It is apparent, however, to one skilled in
`the art that the present invention may be practiced without
`these specific details or with an equivalent arrangement. In
`other
`instances, well-known structures and devices are
`shown in block diagram form in order to avoid unnecessarily
`obscuring the present invention.
`(0016] FIG.4is a diagram ofa sparse parity check matrix,
`[0030] FIG. 1 is a diagram of a communications system
`in accordance with an embodimentof the present invention;
`configured to utilize Low Density Parity Check (LDPC)
`codes, according to an embodimentof the present invention.
`Adigital communications system 100 includes a transmitter
`
`(0017] FIG. 5 isa diagram of a bipartite graph of an LDPC
`code of the matrix of FIG. 4;
`
`20
`
`20
`
`

`

`US 2004/0054960 Al
`
`Mar. 18, 2004
`
`101 that generates signal waveforms across a communica-
`tion channel 103 to a receiver 105, In this discrete commu-
`nications system LOO, the transmitter 101 has a message
`source that produces a discrete set of possible messages;
`each of the possible messages has a corresponding signal
`waveform. These signal waveforms are attenuated, or oth-
`erwise altered, by communications channel 103. To combat
`the noise channel 103, LDPC, codes are utilized.
`
`[0031] The LDPC codes that are generated by the trans-
`mitter LOL enable high speed implementation without incur-
`ring any performance loss. These structured LDPC codes
`output from the transmitter 101 avoid assignment of a small
`number of check nodes to the bit nodes already vulnerable
`to channel errors by virtue of the modulation scheme(c.g.,
`8-PSK).
`
`[0032] Such LDPC codes have a parallelizable decoding
`algorithm (unlike turbo codes), which advantageously
`involves simple operations such as addition, comparison and
`table look-up. Moreover, carefully designed LDPC codes do
`not exhibit any sign of error floor.
`
`(0033] According to one embodimentof the present inven-
`tion, the transmitter 101 generates, using a relatively simple
`encoding technique, LDPC codes based on parity check
`matrices (which facilitate efficient memory access during
`decoding) to communicate with the receiver 105. The trans-
`mitter 101 employs LDPC codes that can outperform con-
`catenated turbo+RS (Reed-Solomon) codes, provided the
`block length is sufficiently large.
`
`[0034] FIGS. 2A and 2B are diagrams of exemplary
`LDPCencoders deployed in the transmitter of FIG. 1. As
`seen in FIG. 2A, a transmitter 200 is equipped with an
`LDPC encoder 203 that accepts input from an information
`source 201 and outputs coded stream of higher redundancy
`suitable for error correction processing at the receiver 105.
`The information source 201 generates k signals from a
`discrete alphabet, X. LDPC codes are specified with parity
`check matrices. On the other hand, encoding LDPC codes
`require, in general, specifying the generator matrices. Even
`though it is possible to obtain generator matrices from parity
`check matrices using Gaussian elimination,
`the resulting
`matrix is no longer sparse and storing a large generator
`matrix can be complex.
`
`{0035] Encoder 203 generates signals from alphabet Y to
`a modulator 205 using a simple encoding technique that
`makes use of only the parity check matrix by imposing
`structure onto the parity check matrix. Specifically, a restric-
`tion is placed on the parity check matrix by constraining
`certain portion of the matrix to be triangular. The construc-
`tion of such a parity check matrix is described more fully
`below in FIG. 6. Such a restriction results in negligible
`performance loss, and therefore, constitutes an attractive
`trade-off,
`
`[0036] Modulator 205 maps the encoded messages from
`encoder 203 to signal waveforms that are transmitted to a
`transmit antenna 207, which emits these waveformsover the
`communication channel 103. Accordingly, the encoded mes-
`sages are modulated and distributed to a transmit antenna
`207. The transmissions from the transmit antenna 207 propa-
`gate to a receiver, as discussed below,
`
`[0037] FIG. 2B shows an LDPC encoderutilized with a
`Bose Chaudhuri Hocquenghem (BCH) encoder and a cyclic
`
`21
`
`redundancy check (CRC) encoder, according to one embodi-
`ment of the present invention. Under this scenario, the codes
`generated by the LDPC encoder 203, along with the CRC
`encoder 209 and the BCH encoder 211, have a concatenated
`outer BCHcode and inner low density parity check (LDPC)
`code. Furthermore, error detection is achieved using cyclic
`redundancy check (CRC) codes. The CRC encoder 209, in
`an exemplary embodiment, encodes using an 8-bit CRC
`code with generator polynomial (x°+x°+x°+x7+1)(x7+x+
`1)(x+1).
`
`[0038] The LDPC encoder 203 systematically encodes an
`information block of size kjgnc,Corky, «
`-
`« Mesa;) onto a
`codeword ofsize Dy... CH(igdy,
`.
`-
`- rlyts Por Dasce xe
`Paigkyj) The transmission ofthe codeword starts in the
`given order from 1, and ends with p,, =k" LDPC code
`parameters (Dyg,eskigp.) are given in Table | below,
`TABLE 1
`
`LDPC Code Parameters
`
`(n,
`
`J
`
`LDPC Uncoded
`Block Length
`Kyape
`32400
`43200
`48600
`51840
`54000
`38880
`57600
`58320
`
`LDPCCoded Block
`Length
`Diane
`64800
`64800
`64800
`64800
`64800
`64800
`64800
`64800
`
`Code Rate
`1/2
`2/3
`3/4
`5
`56
`ais
`a9
`9/10
`
`[0039] The task of the LDPC encoder 203 is to determine
`Digpe7Kigpe
`Parity bits (Por Pir + > Pcbaaget) for every
`block of k,g,. information bits, (ig,i,,, .. - si, 1). The
`procedure is as follows. First, the parity bits are initialized;
`PomPi"P2™ += + =Payyeae,=0. The first information bit, ig,
`are accumulated at parity bit addresses specified in the first
`row of Tables 3 through 10. For example, for rate 74 (Table
`3), the following results:
`PoPoBlo
`Pangor™P1 0401 Gilg
`Prcias™PisnasPly
`PsosPsoeDin
`Pirace=Pirerntely
`
` Ponoze™P0028Big
`
`Penss=Peoss‘ein
`PaarPaoantiily
`Poie1™P2r07Pln
`Poan™P sanbig
`
`Pass73=Prss7a‘blp
`Per79=ParzeDip
`Pans7a™Pr0s7oPla
`
`[0040]
`
`(AIL additions are in GF(2)).
`
`[0041] Then, for the next 359 information bits, i,,,m=1,2,
`...,359, these bits are accumulated at parity bit addresses
`{x+m mod 360xq}mod(m4,.-Kjap.), Where x denotes the
`address of the parity bit accumulator corresponding to the
`first bit ip, and q 1s a code rate dependent constant specified
`
`21
`
`

`

`US 2004/0054960 Al
`
`Mar. 18, 2004
`
`
`
`in Table 2, Continuing with the example, q=60forrate “s. By
`way of example, for informationbit 1,, the following opera-
`tions are performed:
`60 Peg
`Pioss1=Pioss1 hy
`Pasio3=Pisiositt
`PsesPssctbl
`Dy seee=PizeePly
`Perss=Parasity
`Parso™Pacectly
`PaesPreah
`Pao0"Psooty
`Pis73a=PisssaPh,
`Passo=Posactily
`10630"PrsesoPi
`Poooge™P20088Ft
`[0042]
`For the 361* information bit i,,,, the addresses of
`the parity bit accumulators are given in the second row of the
`Tables 3 through 10. In a similar manner the addressesofthe
`parity bit accumulators for the following 359 information
`bits i,,,m=361,362, ...,719 are obtained using the formula
`{x+m_ mod360xq}mod(n4,.-Kjap-)s Where x denotes the
`address of the parity bit accumulator corresponding to the
`
`information bit 1,,9, 1-e., the entries in the second row ofthe
`Tables 3-10. In a similar manner, for every group of 360 new
`information bits. a new row from Tables 3 through 10 are
`used to find the addresses of the parity bit accumulators.
`
`[0043] After all of the information bits are exhausted, the
`final parity bits are obtained as follows. First, the following
`operations are performed, starting with 1=1
`
`Pepipiy 1,2, .. +5 ThapeMape1.
`
`Final content ofp;, i=O,1,
`[0044]
`equal to the parity bit p,.
`
`.
`
`©
`
`©
`
`5 DMapewKiapen!
`
`is
`
`TABLE 2
`
`
`
`Code Rate
`q
`23
`60)
`5/6
`30
`12
`90
`a4
`45
`Ais
`36
`a5
`72
`3/9
`20
`a0
`18
`
`
`[0045]
`
`TABLE 3
`
`Address of Parity Bit Accumulators (Rate 2/3)
`0 10491 16043 506 12826 8065 8226 2767 240 18673 9279 10579 20928
`1 17819 8313 6433 6224 5120 5824 12812 17187 9940 13447 13825 18483
`2 17957 6024 8681 18628 12794 5915 14576 10970 12064 20437 4455 7131
`3 19777 6183 9972 14536 8182 17749 11341 5556 4379 17434 13477 18532
`4 4631 19689 1608 659 16707 14335 6143 3058 14618 17894 20684 5306
`5.9778 2552 12096 12369 15198 16890 4851 3109 1700 18725 1997 15882
`6 486 6111 13743 11537 5591 7433 15227 14145 1483 3887 17431 12430
`7 20647 14311 11734 4180 8110 5525 12141 15761 18661 18441 10569 8192
`§ 3791 14759 15264 19918 10132 9062 10010 12786 10675 9682 19246 5454
`9 19525 9485 7777 19999 8378 9209 3163 20232 6690 16518 716 7353
`10 4588 6709 20202 10905 915 4317 11073 13576 16433 368 3508 21171
`11 14072 4033 19959. 12608 631 19494 14160 8249 10223 21504 12395 4322
`12 13800 14161
`13 2948 9647
`1414693 16027
`15 20506 11082
`16 1143 9020
`17 13501 4014
`18 1548 2190
`19 12216 21556
`20 2095 19897
`21 4189 7958
`22 15940 10048
`23 515 12614
`24 8501 8450
`25 17595 16784
`26 5913 8495
`27 16394 10423
`28 7409 6981
`29 6678 15939
`30 20344 12987
`31 2510 14588
`32 17918 6655
`33 6703 19451
`34 496 4217
`35 7290 5766
`3610521 8925
`37 20379 11905
`38 4090 5838
`39 19082 17040
`
`22
`
`22
`
`

`

`US 2004/0054960 Al
`
`Mar. 18, 2004
`
`TABLE 3-continued
`
`Address of Parity Bit Accumulators (Rate 2/3)
`40 20233 12352
`41 19365 19546
`42 6249 19030
`43 11037 19193
`44 19760 11772
`45 19644 7428
`46 16076 3521
`47 11779 21062
`48 13062 9682
`49 8934 $217
`50 11087 3319
`51 18892 4356
`52 7994 3998
`53 5963 4360
`34 7346 11726
`35 5182 5609
`56 2412 17295
`57 9845 20494
`38 6687 1864
`59 20564 3216
`0 18226 17207
`1 9380 8266
`2 7073 3065
`3 18252 13437
`49161 15642
`§ 10714 10153
`6 11585 9078
`7 5359 9418
`8 9024 9515
`9 1206 16354
`10 14994 1102
`11 9375 20796
`12 15964 6027
`13 14789 6452
`14 8002 18591
`15 14742 14089
`16 253 3045
`17 1274 19286
`18 14777 2044
`19 13920 9900
`20 452 7374
`21
`18206 9921
`22 6131 5414
`23 10077 9726
`24 12045 $479
`25 4322 7990
`26 15616 $550
`27 15561 10661
`28 20718 7387
`29 2518 18804
`30 8984 2600
`31 6516 17909
`32 11148 98
`33 20559 3704
`34 7510 1569
`35
`16000 11692
`36 9147 10303
`3716650 191
`38 15577 18685
`39 17167 20917
`40 4256 3391
`41 20092 17219
`42 9218 5056
`43 18429 8472
`44 12093 20753
`45
`16345 12748
`46 16023 11095
`47 5048 17595
`48 18995 4817
`49 16483 3536
`50 1439 16148
`31 3661 3039
`§219010 18121
`53 8968 11793
`
`
`
`
`
`23
`
`23
`
`

`

`US 2004/0054960 Al
`
`Mar. 18, 2004
`
`TABLE 3-continued
`
`
`Address of Parity Bit Accumulators (Rate 2/3)
`54 13427 18003
`553303 3083
`56 531 16668
`57 4771 6722
`58 5695 7960
`59 3589 14630
`
`[0046]
`
`TABLE 4
`
`Address of Parity Bit Accumulators (Rate 5/6)
`0 4362 416 8909 4156 3216 3112 2560 2912 6405 8593 4969 6723
`1 2479 1786 8978 3011 4339 9313 6397 2957 7288 5484 6031 10217
`2 10175 9009 9889 3091 4985 7267 4092 8874 S671 2777 2189 8716
`3 9052 4795 3924 3370 10058 1128 9996 10165 9360 4297 434 5138
`4 2379 7834 4835 2327 9843 804 329 8353 7167 3070 1528 7311
`5 3435 7871 348 3693 1876 6585 10340 7144 3870 2084 4052 27380
`6 3917 3111 3476 1304. 10331 5939 5199 1611 1991 699 8316 9960
`7 G883 3237 1717 10752 7891 9764 4745 3888 10009 4176 4614 1567
`8 10587 2195 1689 2968 5420 2580 2883 6496 111 6023 1024 4449
`9 3786 8593 2074 3321 5057 1450 3840 5444 6572 3004 9892 1512
`10 8548 1848 10372 4585 7313 6536 6379 1766 9462 2456 5606 9975
`11 8204 10593 7935 3636 3882 394 5968 8561 2395 7289 9267 9978
`12.7795 74 1633 9542 6867 7352 6417 7568 10623 725 2531 9115
`13 7131 2482 4260 5003 10105 7419 9203 6691 8798 2092 8263 3755
`14 3600 370 4527 200 9718 6771 1995 8902 3446 768 1103 6520
`15 6304 7621
`16 6498 9209
`17 7293 6786
`18 5950 1708
`19 8521 1793
`20 6174 7854
`21 9773 1190
`22 9517 10268
`23.2181 9349
`24 1949 5560
`25 1556 555
`26 8600 3827
`27 5072 1057
`28 7928 3542
`29 3226 3762
`O 7045 2420
`1 9645 2641
`2 2774 2452
`33331 2031
`4 9400 7503
`5 1850 2338
`6 10456 9774
`7 1692 9276
`§ 10037 4038
`9 3964 338
`10 2640 S087
`11 858 3473
`12 5382 5683
`13.9523 916
`14 4107 13559
`15 4506 3491
`16 8191 4182
`17 10192 6157
`18 5668 3305
`19 3449 1340
`20 4766 2697
`21 4069 6675
`22 1117 1016
`23.5619 3085
`24 8483 8400
`25 8255 394
`26 6338 5042
`27 6174 5119
`
`TABLE4-continued
`
`Address of Parity Bit Accumulators (Rate 5/6)
`28 7203 1989
`29 1781 35174
`0 1464 3359
`1 3376 4214
`2 7238 67
`3 10595 8831
`4 1221 6513
`5 5300 4652
`6 1429 9749
`7 7878 3131
`8 4435 10284
`9 6331 5507
`10 6662 4941
`11 9614 10238
`12 8400 825
`13 9156 3630
`14 7067 8878
`15 9027 3415
`16 1690 3866
`17 2854 8469
`18 6206 630
`19 363 5453
`20 4125 7008
`21 1612 6702
`22 9069 9226
`23 5767 4060
`24 3743 9237
`25 7018 5572
`26 8892 4536
`27 853 6064
`28 8069 5893
`29 2051 2885
`0 10691 3153
`1 3602 4053
`2.328 1717
`32218-9299
`4 1939 7898
`5 617 206
`6 8544 1374
`7 10676 3240
`8 6672 9489
`9 3170 7457
`10 7868 5731
`11 6121 10732
`12 4843 9132
`13 580 9591
`14 6267 9290
`15 3009 2268
`16 195 2419
`17 8016 1557
`18 1516 9195
`19 8062 9064
`20 2095 8968
`21 753 7326
`22 6291 3833
`23 2614 7844
`24 2303 646
`25 2075 611
`26 4687 362
`
`24
`
`24
`
`

`

`US 2004/0054960 Al
`
`Mar. 18, 2004
`
`7
`
`TABLE 4-continued
`
`
`TABLE 5-continued
`
`
`
`Address of Parity Bit Accumulators (Rate 5/6}
`27 8684 9940
`28 4830 2065
`29 7038 1363
`0.1769 7837
`1 3801 1689
`2 10070 2359
`3 3667 9918
`41914 6920
`§ 4344 5669
`6 10245 7821
`7 1648 3944
`8 3310 5488
`9 6346 9666
`10 7088 6122
`11 1291 7827
`12 10592 8945
`13 3609 7120
`14 9168 9112
`15 6203 8052
`16 3330 2895
`17 4264 10563
`18 10556 6496
`19 8807 7645
`20.1999 4530
`21 9202 6818
`22 3403 1734
`23 2106 9023
`24 6881 3883
`25 3895 2171
`26 4062 6424
`27.3755 9536
`38 4683 2131
`29 7347 8027
`
`[0047]
`
`TABLE 5
`
`
`
`Address of Parity Bit Accumulators (Rate 1/2)
`54 9318 14392 27561 26909 10219 2534 8597
`45 7263 4635 7530 28130 3033 23830 3641
`46 24731 23583 26036 17299 5750 702 9169
`47 5811 26154 18653 11551 15447 13685 16264
`48 12610 11347 28768 2792 3174 29371 12997
`59 16789 16018 21449 6165 21202 15850 3186
`60 31016 21449 17618 6213 12166 8334 18212
`61 22836 14213 11327 5896 718 11727 9308
`62 209] 24941 29966 23634 9013 15587 5444
`63 22207 3983 16904 28534 21415 27524 25912
`64 25687 4501 22193 14665 14798 16158 5491
`65 4520 17094 23397 4264 22370 16941 21526
`66 10490 6182 32370 9597 30841 25954 2762
`6722120 22865 29870 15147 13668 14935 19235
`65 6689 18408 18346 9918 25746 5443 20645
`69 29987 12529 13858 4746 30370 10023 24828
`70 1262 28032 29888 13063 24033 21951 7863
`71 6594 29642 31451 14831 9509 9335 31552
`72 1358 6454 16633 20354 24598 624 5265
`73 19529 295 18011 3080 13364 8032 15323
`74 11981 1510 7960 21462 9129 11370 24741
`75 9276 29656 4543 30699 20646 21971 28050
`76 15975 25634 5520 31119 13715 21949 19605
`77 18688 4608 31755 30165 13103 10706 29224
`
`78 21514 23117 12245 26035 31656 25631 30699
`79 9674 24966 31285 29908 17042 24588 31857
`80 21856 27777 29919 27000 14897 11409 7122
`81 29773 23310 263 4877 28622 20545 22092
`82 15605 5651 21864 3967 14419 22757 15896
`83 30145 1759 10139 292773 26086 10556 5098
`84 18815 16575 2936 24457 26738 6030 S05
`
`
`Address of Parity Bit Accumulators (Rate 1/2)
`85 30326 22298 27562 20131 26390 6247 24791
`86 928 29246 21246 12400 15311 32309 18608
`87 20314 602