US(}0742l032B2
`
`.12. Ulllted States Patent
`Jin et al.
`
`am Patent No.:
`(45) Date of Patent:
`
`US 7,421,032 B2
`Sep. 2, 2008
`
`(54) SERLAL CON(.‘.\TENA'l‘ION OF
`[NTERLEAVED CONVOLUTIONAL CODES
`l~‘()l1:VllNG TURBO-I.ll(E (.‘0Dl+1S
`
`(55;
`
`References Cited
`‘
`‘
`_
`_
`‘
`_
`_
`“-5- PM “N1” '30CUM1'«"“5
`
`vs)
`
`(73) Assignee:
`
`( ”‘ ) Notice:
`
`um Jan. u1«uGurd»»=r. m ms» am-ad
`Khandckmt Pasadena. CA (US):
`Robert J. McEliece. Pasadena. CA (US)
`(fallifurnia Institute of Technology.
`«us»
`Subject to afl)’{‘l1lS((i‘lEll.[I1t3Lli. the :‘€l‘lTlctlJfllJ.l:
`patent is L‘.)(lt..‘]1 c or a juste
`no or 3-
`LI.S.(‘. 1540:) by Udays.
`
`222333333 :2
`5.751.739 A
`5,303,115 A it
`5'83l'U93 "
`2-mt:
`5531.374 ,1;
`r1.r)32_2g4 A
`6.044.! It‘: A
`6.094.739 A “
`
`-» $332
`5.-1-3-93 Seshaulrietttl.
`9.1993 Meyer
`$3“? "”‘]‘
`:;.:,:.:. ..
`_1r2(;{_|[_j
`(_-hemakeshl. at a]_
`3.-Ztmtl Bliss
`32000 Wang
`7.-"20i]0 Millerelnl.
`
`714.-"792
`
`3753.1]
`
`714-"792
`
`(21) Appl. No.: 1U542,95l}
`
`(22)
`
`Filed:
`
`(M3. 2006
`
`(65)
`
`Prior Publication Data
`US 2007fOl)25-150 Al
`Feb. 1, 2007
`
`Related U.S.Applieatlm:| Data
`
`(63) Continuation ol'applicat'iot1 No. 09:’86l.l02. filed on
`May I8. 2{l(}l . now Pat. No. 7.] I63‘ l 0. and a CDI1ll.l'lU-
`ation-in-pzirt of applicaliort No. D9f922_.852. filed on
`Aug. 18. 2000. now Pat. No. 7.089.4':"':'.
`
`(60)
`
`bl‘tJ\-‘is-lt1T.]3l application No. 602905.095, filed on May
`13. 2000.
`
`(51)
`
`Int. Cl.
`H041’. 5/I2
`(52) U.S. CI.
`
`{20015.01)
`3751962: 375K265; 3?5r‘343:
`714.055: 7141786: 7143792: 34152: 3413102
`{58) Field ol'Classification Search
`375K259.
`37'5f262. 265. 285. 296, 341. 346, 348; 714E746.
`714E752. 755. 756, 786. 792. 794- 796: 34151.
`34152. 56. 102. 103
`See application file for complete Search history.
`
`{Continued}
`
`on "ER PUB[‘I("A-FIONS
`ppenrlix A. l "filntclure oi‘ Parity Check Malrices of Standardized
`LDPC Codes." Digital Video Bromlca:;t'i.ng (DVB) User guidelines
`for [he second generation system for Bnuadcmting. Intenu.-live Ser-
`vices. News Gathering and other broadband szllellile applications
`{DVD-S3) l;"l'S[ IR [02 37{1V’l.l.l. (Feb. 2005) 'l‘r:chr1ie:1] Report".
`pp. 64.
`
`((.'ot'1til:l1Icd ]
`
`Prfniarg‘ E,\'atJ1f:rer—Dac V. H3
`(74) .<in‘ome:t: Agent. or Fir»:
`
`Fish & Ricltardsou l-'.['.
`
`(57)
`
`ABSTR.-\('T
`
`A serial concatenated coder includes an outer coder and an
`inner coder. The outer Coder irregularly repeats bits in a data
`lalocls’. according to El degree profile and 5I'.'l'-'.il‘l‘Jl:.'rlt.!5'
`the
`repeated bits. Tlu: scrambled and repeated bits are input to an
`inner coder. which has a rate stthslatttittlly close to one.
`
`23 Claims. 5 Drawing Sheets
`
`3 § A
`
`Apple 1101
`
`Variable Node
`Fraction of nodes
`degree I
`
`Check Node
`degree a
`
`Ee E‘
`
`I:
`he
`
`Apple 1101
`
`

`
`US 7,421,032 B2
`Page 2
`
`U.5. PA'I'IiN'I' DOC‘UM IENTS
`
`6.396.423 Bl
`6.437.?l-’-l Bl
`6.SS9.‘)O{\ B2‘
`3t}t}ltl'ttJ25358 Al
`
`SJZUUE Ln.t.tn:ten eta].
`832002 Kim et al.
`232005 Hatrnmons etal.
`95200] Liidson etal.
`
`OTHER PUBLICATIONS
`
`714.-".tSfi
`
`Benedellu El al.. “A Soil-Input Soil-Otllpttt Maximurn A Poslerio-ri
`it/[AP] Module to Decode Parallel and Serial Concatenateil Codes."
`The Telecommunications and Data Aieqtlisition (TDA} Progress
`Report 42-137 for NASA and Califomia Institute ol'TechIlC-logy Jet
`Propulsion laboratory. Jospeh H. Yuan. Ed.. pp. 1-30 (Nov.
`I5.
`1996).
`Benedetto et al.. "Bandwidth eflieient patallel concatenated coding
`schemes." Electronics Letiers 3 [(24): 2067-2069 (Nov. 23. I995).
`Benedetto et nl.. "Design of Seriaily Concalenaled Interleaved
`Codes." [CC 9'.-'. Montreal. Canada. pp. 710-714. t_ Jun. I997).
`Benedetto et at.. "Parallel Concatenated Trellis Coded Modulation.“
`[CC ‘96. IEEE. pp. 974-978. (.lt.I.n. I996).
`Benedetto ct al.. “Serial Concatcnated Trellis Coded Modulation
`with Iterative Decoding.“ Proceedings from the IEEE I99’? Interna-
`tional Symposium on In.l'on11a1ion Theory (ISIT). Ulm. Gertrtany. p.
`8. Jun. 29-1111. -4. I997.
`Benedetto et al.. “Serial Concatenatien of Interleaved Codes: Perfor-
`mance Analysis. Design. and Iterative Decoding." The Telect)ITtrnu—
`nicalions and Data Acquisition tTDA) Progress Report 42-126 for
`NASA and Calil'ornit1 institute of "Technology Jet Propulsion Labo-
`ratory. Jospoh l1.‘t’uen, lld.. pp. 1-26 i_.t'\lIg. IS. 1996).
`Benedetto at .11.. “Serial (foncatentttion of interleaved codes: perfor-
`inancc analysis. design. and itcrtttive decoding.“ Proceedings [mm
`the IEEE 199? International Syrnposittrn on l.nformation 'l'hcory
`IISIT). Lilrn. Germany. p. 106. Jun. 29-Jul. 4. 1997.
`Benedetto el al .. “S0fl—outptll decudi rtg Ellgclrithtrts in iterJ.tl'ivt-.‘ decod-
`ing ofturho codes." The Telet.'ort1n1unications and Data Acquisition
`[TDAl Progress Report 42-124 for NASA and California Institute of
`Teclmology Jet Propulsion Laboratory. Iuspeh [-1. Yuan. Ed.. pp.
`63-8? (Feb. I5. 1996).
`Benedetto. S. et a].. “A Soft-Input Soft-(Jtttput APP Module for
`Iterative Decoding of Cortcalenated Codes.” IEEF. Coirunttniculions
`Letters ltlj: 22-24 (Jan. 1997').
`Berrott et al.. “Near Shannon Limit Ertor-Cotzrecting Coding and
`Decoding: Ttirbo Codes." ICC pp. |lJ64— IGTU t" I993).
`Digital Video Broadcasting t'DVB) User guidelines for the second
`generation system for Broadcasting.
`interactive Services. News
`Gathering and otherhroadhand satellite applications (DVB-S2) ETSI
`TR [U2 3”i'fiVl. I . l. tFeb. 2tlt.'l5}Tecl'tnicz1l Re-porL pp. l—l04(Fet:t I5.
`2fltJ5)_
`
`Divsalar et al,. “Coding Theorems for "1'nrbo-Like‘ Codes.” Proceed-
`ings of the 36"‘ Annual Alterton Conference on Cornnutnication.
`Control. and Computing. Sep. 23-25.
`I998. Allerton llouse.
`Monticello. Illinois. pp. 201-2 It} (1998).
`Divsalnr ct n.|.. “Efl'et.:live [tee distance ufturbn codes." Electronics
`Letters 32(5): 445-446 (Feb. .29. I996).
`Divsalar. D. et al.. "Ilybrid Concatenated Codes and Iterative Decod-
`ing.“ Proceedings from the l.l_-‘.l:IE 199'? International Sympositun on
`Information Theory IISIT]. Ulrrt. Gemiany. p.
`ll] (Jun. 29-Jul. 4.
`I997).
`Divsalar. D. et al.. “Low-rate turbo codes for Deep Space Commu-
`nications.” Pntceedittgs from the [995 [EEE I.ntemn1ion:t.l Sympo-
`sium on Information Theory. Sep.
`|7—22. 1995. Whistler. British
`Colutnbia. Canada. pp. 35.
`Divsalar. D. et al.. "Multiple '1'n.rbo Codes for Deep-Space Commu-
`nications.” The Telecommunications and Data Acquisition (TDAJ
`I’IT:-grass RE]:II:It1 42-121 for NASA and Ca]ii't‘Jmi.'1 institute ofTech-
`nology Jet Propulsion Laltotatory. Jospeh II. Yuen. Ed.. pp. 60-7'?
`{Ma}/15. 1!-J95).
`Divsalnr. D. at al.. "Mttltiple Turbo Codes.” M'IT.COM 95. S11] Diego.
`CA pp. 39-235 (Nov. 5-6. 1995).
`Divsalar. D. et 21].. “On the Design of Turbo Codes.“ The "Telecom-
`nitlnic at ions and Data Acquisition (TDA) Progross Report -12- l 23 for
`NASA and California Institute of Technology Jet Propulsion Labo-
`ratory. Jospeh I-1. Yuen. l3d.. pp. 99-13 I (_’.'-Jov. 15. 1995).
`Divsalar, D. el al.. "Serial Turbo Trellis Coded Modttlation with
`Rate—l Inner Corie." Pr-ziceetlings from the IEEE 2000 Inlerntllional
`Symposium on lnfortnaliun Theory [_lS]T}.
`ltztly. pp.
`l-l-1 [.lu.I't.
`2.000).
`Divsalar. D. et al.. “'l'1Lrbo Codes for PCS Applications." [CC 95.
`Tl-":F.'F.. Sezttilo. WA. pp. 54-59 (Jun. I995}.
`Jirt at al.. "Irregular Repeal—Acc1trnul:tte Codes." 2nd lntcrnatioital
`Symposiuirt on Turbo (‘odes & Related Topics. Sep. -’l-'}'. 2000. Brest.
`Fl':1.t1CG. 25 slides. tpresented on Sep. 4. 2000).
`Jin et at. “Irregular Repeat—Accornutatc Codes." 2"“ International
`Sy111p-osiu.I1't on Turbo Codes 8: Related Topics. Sap.-1-7. 2000. Brest.
`France. pp. l-8 (2tl(ltl}_
`Richardson et al.. "Design of capacity approaching irregular low
`density parity check codes." TE FE Trans. lt:tl'om1. Theory 47 : 6 I 9-637
`(Feb. 2001).
`Richardson. T. and R. Urbanke. “Eflicienl encoding of low-density
`parity check codes.“ IEEF. Trztns. tnfonn. Theory -11': 633-656 (Feb.
`2001].
`Wilberg. et al.. “Codes and Ilemtie Decoding on General Graphs”.
`I995 Intl. Symposium on Information Theory. Sop. 1995. p. 468.
`
`* cited by examiner
`
`

`
`U.S. Patent
`
`Sep. 2, 2008
`
`Sheet 1 of5
`
`Us 7,421,032 B2
`
`FIG.1 (PriorArt)
`
`

`
`U.S. Patent
`
`Sep. 2, 2008
`
`Sheet 2 of 5
`
`US 7,421,032 B2
`
`(.3
`c.)
`<:
`
`:
`
`H‘
`
`£5
`I
`
`C‘!
`
`Q5
`E
`
`E:
`
`5C
`
`:
`—I
`
`_‘C
`
`X
`
`

`
`U.S. Patent
`
`Sep. 2, 2008
`
`Sheet 3 M5
`
`Us 7,421,032 B2
`
`Variable Node
`
`Check Node
`
`Fraction of nodes
`degree i
`
`I
`
`I.
`
`....u
`
`\.
`
`__
`2FHnu3
`
`11!
`
`.IU
`
`
`
`.._..W.........._\_nu:_
`
`__
`
`\.\
`
`X
`
`20H3
`
`.3
`
`I
`
`\
`
`\
`
`\
`
`./I.R.._
`
`_
`
`fll
`
`.1.
`
`lull‘_
`_\\..
`
`4/.00I.0\
`oLo0u.xs1.1..
`.x\I...
`\_\LT__
`..ll..|lI.IvI.lIII\
`
`illDOC
`
`FIG. 3
`
`

`
`U.S. Patent
`
`Sep. 2, 2003
`
`Sheet 4 off»
`
`US 7,421,032 B2
`
`
`
`FIG. 5A
`
`
`
`

`
`U.S. Patent
`
`Sep. 2, 2008
`
`Sheet 5 M5
`
`Us 7,421,032 B2
`
`

`
`US 7,421,032 B2
`
`1
`SERIAL ITONCATENATION OF
`INTERLEAVED CONVOLUTIONAL CODES
`FORMING TURBO—LlKE CODES
`
`(“ROSS-RIEFIIRIINCTIE TD R12] ATIEIJ
`Al-‘PI.,lC.f\.TIONS
`
`This application is a continuation of LI.S. application Ser.
`No. 09186] . 102. filed May 18. 2001. now U.S. Pat. No. 1116.
`? 1 0. which claims the priority ofU.S. provisional application
`Sol’. No. 60;’205.0l)5. filed May I3. 2000, and is a continua-
`tion—in—part of US. application Ser. No. (l9f922.852. tiled
`Aug. 13, 2000, now US. Pat. No. 7,089_.4'r'7.
`
`tu
`
`(.i()Vl£RNMliNT I.IC‘1iNSI-I RICH-ITS
`
`The US. Govemment has a paid—up license in this inven-
`tion and the right in limited circumstances to require the
`patent owner to license others on reasonable terms as pro-
`vided lhr by the terms ot'Gra.nt No. C.‘(.‘R-98()4793 awarded
`by the National Science lioundatiou.
`
`BACKGROUND
`
`Propert ies ol‘a channel a tiect the amount otidata that can be 'n
`handled by tile t:lian.t:tel. The so-called "Sl'ta.ltJJon limit
`defines tl1e theoretical limit of the amount of data that a
`channel can carry.
`Dit't'erent techniques have been used to incrse the data
`rate that can be handled by a charuiel. “Near Shannon I.i.niit
`t<lrror—('.‘.orrectiI1g Coding and Decoding: Turbo Codes." by
`Berrou et al. ICC. pp 1064-1070. (1993). described a new
`“turbo code“ technique that has revolutionized the field of
`error correcting codes. Turbo codes have sutficient random-
`ness to allow reliable eotuniunication over the channel at a
`
`3U
`
`high data rate near capacity. However. they still retain sufli-
`cient stntcture to allow practical encoding and decoding a Igo-
`rithins. Still, the technique for encoding and decoding turbo
`codes can be relatively complex.
`A standard turbo coder 100 is sliown in FIG. I. A block of
`
`k infonuat.ion bits is input directly to a first coder 102. A It bit
`interleaver 106 also receives the It bits and interleaves them
`prior to applying them to a second coder 104. The second
`coder produces an output that has more bits than its inpttt, that
`is, it is a codcrwith ratethat islessthan I .Thecoders I02. 104
`are typically rt:cLl.I'sive convt‘.-Iutional coders.
`Three dillerettt items are sent over the chaimel 150: the
`original 1-: bits. first encoded bits 110. and second encoded hits
`112. At the decoding end. two decoders are used: a first
`const_itt.tenl decoder 160 and a second ctJnt51i1t.te.nt decoder
`162. Each receives both the ori_t_zinal k bits, and one of the
`encoded portions 110. 112. Each decoder sends likelihood
`estimates of the decoded bits to the other decoders. The esti-
`mates are used to decode the uncoded inl'or1nation hits as
`
`t.:orrI.tpted by the noisy chnn.nel_
`
`SUMMARY
`
`A coding system according to an embodiment is config-
`ured to receive a portion of at signal
`to be encoded, For
`example. a data block including a Fixed number of bits. The
`coding system includes an outer coder. which repeats and
`scrambles bits in the data block. The data block is apportioned
`into two or more sttb—blocks. and bits in diflerent sub—bIocks
`are repeated a diITcrt-.'l.1l number oi’ times according to a
`selected degree profile. The outer coder may include a
`
`-15
`
`K)! '41
`
`fit:
`
`{)5
`
`2
`
`repeater with a vat'ial:tlc rate and an interleaver. Alternatively,
`the outer coder may be a low—density generator matrix
`[LDGM) coder.
`The repeated and scrambled bits are input to an inner coder
`that has a rate sttbstaiitially close to one. The inner coder may
`include one or more accumulators that perfonn recursive
`modulo two addition operations on the input bit‘ stream.
`The encoded data output from the inner coder tnay be
`transmitted on a channel and decoded in linear titne at a
`destination using iterative decoding techniques. The decod-
`ing techniques may be ba sed on a Tanner graph representation
`of the code.
`
`BRIEF l)IiSCRlP'l‘l0N OI’ Tllli DRAWINGS
`
`FIG. 1 is a schematic diagram of a prior "turbo code“
`system.
`F IG. 2 is a schematic: diagram ofa coder acctiniiiig to an
`embodiment.
`FIG. 3 is a 'l'at1t'tet‘ graph for an irregular repeat and accu-
`mulate {IRA) coder.
`FIG. -1 is a schematic diagram ot'at1IRA coder according to
`an einbodimeiit.
`
`FIG. 5A illustrates a message li'urn at variable node to a
`check node on the Tanner graph of FIG. 3.
`FIG. 5B illustrates a message from a check node to a
`variable node on the Tanner graph of FIG. 3.
`F [Ci 6 is a schematic diagram ofa coder according to an
`alternate embodiment.
`FIG. 7 is a schematic diagram of a coder according to
`another altentate embodiment.
`
`l)}":"l‘.’\II .-I'll) Dl1S(.‘RIP’l'I()N
`
`FIG. 2 illustrates a coder 200 according to an entbodiment.
`The coder 200 may include an outer coder 202. an interleaver
`204, and inner under 206. The coder may be used to Fortuat
`blocks otdata for transmissiott. introducing redundancy into
`the stream of data to protect the data from loss dtte to trans—
`mission enors. The encoded data may then be decoded at a
`destination in linear time at rates that may approach the cl'laI.ti-
`nel capacity.
`The outer coder 202 1-eceives the ttncoded data. The data
`may be partitioned into blocks oi" fixed size. say it hits. The
`outer coder may be an (n.k) binary linear block coder, where
`11>-It. The coder accepts as input a block u otik data bits and
`produces an output block v of rt data bits. The mathematical
`relationship between u and v is v=T,,u._ where To is an nxl-t
`matrix. and the rate of the coder is kiln.
`The rate of the coder may be irregular. that is. the value of
`To is not constant, and may ditTcr for sub-blocks ofbits in the
`data block. In an enibodimettt.
`the outer coder 202 is a
`repeater that repeats the 1»: bits in a block a ntJtl1l:tct' ol'ti.rnes q
`to produce a block with 11 bits. where n-‘qlt. Since the repeater
`has an irregular output. diflerent bits in the block may be
`repea led a diIl"eret1t number ol'tin‘tes. For example. a I'ractio1'1
`otthe bits in the block may be repeated two times. a fraction
`ofbits may be repeated three times. and the rema inder of bits
`may be repeated tour times. These fractions define a degree
`sequence. or degree profile. of the code.
`The inner coder 206 may be a linear rate-I coder. which
`means that the 11-bit output block it can be written as x='l‘,w.
`where T_,is a nonsingular nxn matrix. The inner coder 2 10 can
`have a rate that is close to l. e.g.. within 50%. more preferably
`10% and perhaps even more preferably within 1% of I.
`In an enibodirnent. the inner coder 206 is an accumulator,
`which produces outputs that are the modulo two (mod-21
`
`

`
`3
`
`4
`
`US 7,421,032 B2
`
`partial sunts ofits inputs. The accurnulalor may he a tmncatcd
`rate—l recursive convolutional coder with the transfer func-
`
`tion It'( 1 4-D]. Such an accumnlat or may be considered a block
`coder whose input block [x.,,
`.
`.
`. _.x,,] and output block
`[y,, .
`.
`. ,y,,] are related by the forntula
`I‘ t ' 31
`
`'4»
`
`J‘: ‘1‘I'-i-‘X2
`
`_L'3 ‘ll’ , ti-'.\'3EEL\'_1
`
`_t-‘,,-—xlE}.x2ELr_\':_I- . ..
`
`Ft-tx
`
`,,.
`
`,x,.). as follows. liach of the inI‘orntation bits is
`.
`.
`.
`(x, .
`associated with one of the inforrnation nodes 302. and each of
`the parity bits is associated with one ofthe parity nodes 306.
`The value of a parity bit is determined uniquely by the con-
`dition that the 1nod—2 sum of the values of the variable nodes
`connected to each of the check nodes 304 is zero. To see this.
`
`set xo =0. Then if the values of the bits on the ra edges coming
`out the pcmiutatiou box are (V, ,
`.
`.
`.
`_. \«',,,]. then we have the
`recursive fonnnla
`
`I
`
`i=I
`.l'_|.' =33‘ IT'S 1'“:
`
`|t.tir
`
`. . _. r. This is in effect the encoding algorithm.
`tor _i —' 1. 2. .
`Two types of IRA codes are represented in FIG. 3. a non-
`systematic version and a systematic version. The nonsystem—
`alic version is an (r.k] code. in which the codeword corre-
`sponding to the ittli:-rmatiott bits (LIL,
`.
`.
`. ..t1k] is fit]. .
`.
`.
`. X’).
`The systematic version is a fk+r. k) code. in which the code-
`word is (11,. .
`.
`.
`. up to. .
`.
`.
`. x,.).
`The rate of the nonsystematic code is
`
`Rm-.-.7 =
`
`(I
`
`2] if}
`
`The rate of the systematic code is
`
`R»-.u =
`
`It‘
`
`(11-Z if}
`
`For example, regular repeat and acctunulate (RA) codes
`can he considered nonsystematic IRA codes with a-'1 and
`exactly one f, equal to 1. say f,_,
`1, and the rest zero. in which
`case Rm.‘ simplifies to R- -Ifq.
`The IRA code may be represented using an alternate nota—
`tion. Let it, be the fraction of edges between the information
`nodes 302 and the check nodes 304 that are adjacent to an
`information node ofdegree 1. and let p, be the traction of such
`edges that are adjacent to a check node ofdegree i+2 (i .e.. one
`lltat is adjacent to i inlorination nodes]. Thcse edge fractions
`may be used to represcrtt the IRA code rather than the corre-
`f-
`sponding node fractions. Define 7L(x)=2,.}t,x ' and p(x)=E,-p,-
`x"" to be the generating. iitnctiotts of these seqtlences. The
`pair 0... p) is called a dt:g;ree distribution. For I.{xl=}J,l‘,-x,-.
`
`I
`_-
`'l
`ti
`. n
`but ef Atrtdry T .tLrt:.tr
`
`where “@" denotes mod—2. or exclusive{)R (XOR). addition.
`An advantage of this system is that only ntotl-2 addition is
`necessary for die accumulator. The acctltttulator may be
`embodied using only XOR gates, which may simplify the
`design.
`The bits output from tl1e outer coder 202 are scrambled
`before they are input to the inner coder 206. This scrambling '
`may be perlomied by the interleave: 204. which performs a
`pscudo—randont pcrnnttation ufan input block \«. yielding an
`output block w having the same length as v.
`The serial concatenation of the interleaved irregular repeat
`code and the accumulate code produces an irregular repeat‘
`and accuntttlatte { IR./\) code. An I RA code is 21 linear code. and
`as such. may he represented as a set of parity checks. The set
`of parity checks may be represented in a bipartite graph.
`called the Tanner graph. of the code. FIG. 3 shows :1 Tanner
`gaph 300 ofan IRA code with parameters (fl. .
`.
`.
`. I]: a].
`wltere £20. 2,1‘,-=1 and “a” is a positive integer. The Tamter
`graph includes two kinds of nodes: variable nodes [open
`circles) and check nodes (liilcd circles). There are k variable
`nodes 302 on the lefi, called infomiation nodes. There are r
`variable nodes 306 on the right. called parity nodes. There are
`r=(k2,.if,.]fa check nodes 304 connected between the inl'onna-
`tion nodes and the parity nodes. Each inlonnation node 302 is
`connected to a number of check nodes 304. The fraction of
`
`3n
`
`'
`
`«to
`
`information nodes connected to exactly i check nodes is 1}.
`Forcxample. in the Tanner graph 300, each ofthe T3 informa-
`tion nodes are connected to two check nodes. corresponding
`to a repeat of q 2. and each of the 1'3 information nodes are
`connected to three check nodes. corresponding to q= 3.
`Each check node 304 is connected to exactly “a“ informa-
`tion nodes 302. In FIG. 3. a=3. These connections can be
`
`made in many ways. as indicated by the arbitrary pemtutation
`of the ra edges joining information nodes 302 and check
`nodes 304 in pemtutation block 310. These connections oor~
`respond to the scrambling performed by the interleaver 204.
`In an altentate entboditnent. the outer coder 202 may be a
`low-density generator matrix {I.DGM) coder that pct'll1rt‘t'ts
`an irregular repeat of the k bits itt the block, as shown in FIG.
`4. As the name implies. an LDGM code has a sparse (low-
`density) generator ntattix. The IRA code produced by the
`coder 400 is a serial concatenation ofthe [.I)(iM code and the
`acctnttttiator code. The irtterleavcr 204 in FIG. 2 may be
`excluded due to the randomness already present in the struc-
`ture of the LDGM code.
`
`11' the permutation perfonrted in permutation block 310 is
`fixed. the Tatlrter graph represents a binary linear block Code
`with k information bits (11,.
`.
`.
`.
`. nk) and r parity bits
`
`45
`
`u- '41
`
`on
`
`05
`
`

`
`5
`
`6
`
`US 7,421,032 B2
`
`The rate of the systematic IRA code given by the degree
`distribution is given by
`
`
`
`
`
`"Belie1‘propag,atiort“ on the Tanner Graph realization may
`be used to decode IRA codes. Roughly speaking. the belief
`propagation decoding technique allows the messages passed
`on an edge to represent posterior densities on the bit associ-
`ated with the variable node. A probability density on a bit is a
`pairofnon-he-gativc real numbers 11(0). p( 1) satisfying p(0)+
`p[ l ]"l. where p-(0) denotes the probability ofthe bit being 0.
`pfl) the probability of it being 1. Such a pair can be repre-
`sented by its log likelihood ratio, tn=Iog(p('0)fp( l )1. The out-
`going message from :1 variable node n to 21 check node v
`represents information about 1].. and a message from a check
`node n to a variable node v represents information about u. as
`shown in FIGS. 5A and SB. respectively.
`The outgoing nit.-ssage front a node n to a node v depends
`on the iucornirtg messages from all neighbors w ofu except v.
`Ifu is a variable message node. this outgoing message is
`
`nu»
`nltu -+ 1'! = E rttttra st] +mgt:.tJ
`
`where rn0(u) is the log—likelihood message associated with
`u. lfu is a check node. the corresponding formula is
`
`LE1!
`
`tutu —e vi
`___
`
`h
`
`nit It‘ —- at
`3
`
`t-7t‘
`-.-. n t:u1l'l
`
`'4:
`
`III
`
`15
`
`3t]
`
`35
`
`45
`
`no
`
`Before decoding, the messages m(w——>u) and n1(u—-aw) are
`initialized to be zero. and m0(u) is initialized to be the log-
`likelihood ratio based on the channel received information. If
`
`65
`
`relies on its input, and y is the output ol‘tltc- channel code bit
`u. then tn,,(u)-'-=log[p(u~0|y]!p(u--1|y)). Alter this initializa-
`tion. the decoding process may run in a hilly parallel and local
`manner. In each iteration, every variablefclieck node receives
`ntessages ii-om its neighbors, and sends back updated mes-
`sages. Decoding is lcrrninatcd after a fixed number of item-
`tions or detecting that all the constraints are satisfied. Upon
`termination. the decoder outputs a decoded sequence based
`on the messages U1(tl]=}:Wm[W"*Ll).
`Thus, on various cltannels, iterative decoding only differs
`in the initial messages rnntut. For example. consider three
`tnemoryless channel models:
`a binary erasure channel
`(BBC 1: a binary symmetric channel (BSC): and an additive
`white Gaussian noise (AGWN] channel.
`In the BIEC. there are two inputs and three outputs. When 0
`is transmitted, the receiver can receive eithcrf) or an erasure IE-.
`An erasure ii output nteans that the receiver does not k1'u:Iw
`ltow to dentodulate the output. Similarly. when 1 is transmit-
`ted. the receiver can receive either 1 or E. Thus. for the BEC.
`
`y e {0, E. 1}. and
`
`Mutant:
`
`it'_t~=tJI
`+oc
`il'_\':-E
`U
`-no ll:_t'=l
`
`In the BSC. there are two possible inputs [(11) and two
`possible outputs (D. 1]. The BBC is characterized by :1 set of
`conditional probabilities relating all possible outputs to pos-
`sible inputs. Thus. for the BSC y e {0, 1},
`
`mnt u I =
`
`1 _
`loglF
`-0-: 1
`l
`l"'” ‘f
`p
`E
`
`if _t-' = U
`
`tr:
`
`1
`
`_
`
`and
`
`In the AWGN, the discrete—time input symbols X take their
`values in a finite alphabet while channel output symbolsY can
`take any values along the real line. There is assumed to be no
`distortion or other eliects other than the addition of white
`Gaussian noise. In an AWGN with a Binary Phase Shitt
`Keying (BPSK) signaling which maps 0 to the symbol with
`amplitude ‘IE and I
`to the symbol with amplitude —.,.I'E§.
`output y E R. then
`
`mull! J§I_v\_i7".=::’Ng
`
`the channel is ntctuoryless. ie, each channel output only
`
`where N‘/2 is the noise power spectral density.
`
`

`
`7
`
`US 7,421,032 B2
`
`The selection ol‘ :1 degree profile for use in a particular
`transmission channel is :3 design parameter, which may be
`affected by various attributes of the channel. The criteria for
`selecting a particular degree pro file may include. for example.
`the type of channel arid the data rate on the channel. For
`exaunple. Table 1 shows degree profiles that have been found
`to produce good results for an AWGN channel l'l'lClClLl.
`
`II
`
`ikl
`3.3
`}.5
`KG
`Mt!
`Ml
`M3
`M3
`114
`M5
`3&2?
`128
`Rmc
`UGA
`o‘
`i_F.hJ"NlI] " {LIB}
`S.L. td]3t
`
`TABLE 1
`
`3
`
`l.I.139l.l2_‘I
`o_"£2I5S5
`
`tI.t'13B82L'|
`
`3
`
`tI.fJ'.'-'8] 94
`n,I2tttttt5
`11.160313
`tI,t]3t§l?8
`
`tI,lIJ8t't2%
`n.-<tt'tT9tI2
`
`0.333364
`1.1840
`1.1931
`III.19F_I
`—tLI.~t-£453
`
`03.3.1223
`1.2415
`1.2t3Ft’i"
`—tI,3jtI
`-I I,495S
`
`-1-
`
`tJ.tJ54-485
`u_tt143t3
`
`tLI.l.‘.t‘)'.-‘S5
`ILZZUEHG
`lJ.Dlt’>4E4
`
`tJ.45[I3t.J'.I
`|1.U]’.-‘S42
`I.I..t333lt<
`1.21515
`l.2?8fl
`_n,3?1
`-0.-$958
`
`Table 1 shows degree profiles yielding codes of rate
`approximately ‘£3 hair the AWGN channel and with a=2_. 3. 4.
`For each sequence. the Gaussian approximation noise thresh-
`old. the actual stu11—product decoding threshold and the cor-
`responding energy per bit {E£,}—noise power (Nmt ratio in dB
`are given. Also listed is the Shannon limit (S.L.).
`As the parameter
`is
`increased the performance
`improves. For example, for a=4. the best r.-ode [band has an
`iterative decoding threshold of I*l,_,fNt.=-0371 dB. which is
`only 0.12 dB above the Shannon limit‘.
`The accumulator component of the coder may be replaced
`by a "double accumulator” 600 as shown in FIG. 6. The
`double accumulator can be viewed as a truncated rate 1 con-
`
`volutional coder with transfer function lf{1+IJ+I)3).
`Alternatively. a pair oiaccumula tors may be the added, as
`shown in FIG. 7. There are three component codes:
`the
`“ottter” code 700. the "middle" code 702. and the '‘inner’’
`code 704. The outer code is an irregular repetition code, and
`the middle and inner codes are both accttmulators.
`
`-it":
`
`45
`
`IRA codes may be implemented in a variety of channels.
`including mernoryless channels. such as the BEC‘. BSC‘. and _-
`AWGN. as well as cltannels having ttoii-bina.n_.' input, non-
`symmetric and Fading channels, andfor channels with
`memory.
`A ntunber of embodj ments have been described. Neverthe-
`
`..i- In
`less. it will be understood that various modifications may be _
`made withottl departing from the spirit and scope of the
`invention. Accordingly. other embodiments are within the
`scope oI'tlJe fol lowing claims.
`
`no
`
`The invention claimed is:
`
`.l. A method comprising:
`receiving a collection of message bits having a first
`sequence in El source data stream;
`generating a sequence ofparity bits. wherein each parity bit
`“x_,-’’ in the sequence is in accordance with the fortuula
`
`i
`
`i=I
`.1’; =.J'. _| +2 1'“,-.|.1.,.
`
`where
`...x _
`J_ 1" is the value ofa parity bit "j—l ," and
`
`tu
`
`1.
`I
`“L "t,i'—I i... M‘
`
`is the value of a sum of “a" randomly chosen irregular repeats
`of the message bits: and
`making the sequence of parity bits available for transmis-
`sion in a transmission data stream.
`
`2. The method of claim 1, wlterein the sequence of parity
`bits is generated is in accordance with “a" being constant.
`3. The method of claim 1, wherein the sequence of parity
`bits is generated is in accordance with "a" varying for di_tl’er—
`ent parity bits.
`4.'1l1e method ofclaim 1, wherein generating the sequence
`of parity bits comprises performing recursive modulo two
`addition operations on the random sequence nl‘bits_
`5. The tttcthod ol'clai.tn l . wherein generating the sequence
`of parity bits comprises:
`generating a random sequence olbits that repeats each of
`the message bits one or tnore times with the repeats of
`the message bits being distributed in a random sequence.
`wherein different fractions of the message bits are each
`repeated a different number of times and the number of
`repeats For each message bit is irregular; and
`XOR summing" in linear sequential fashion a predecessor
`parity bit and “:5” bits oi‘ the r:-J.t'tdon‘t sequence of bits.
`
`6. The method of claim 5. wherein generating the random
`sequence ofbits conlpriscs coding the collection of message
`bits using a low-density generator matrix (LIJGMJ coder.
`7.The1't1et.liod ol‘cla.in1 5. wltereiu generating the random
`sequence ofbits comprises:
`producing a block of data bits. wherein difl'ercnt' message
`bits are each repeated at dilferent number of times in a
`sequence that matches the lirst sequence: and
`randomly permuting the different bits to generate the ran-
`dom sequence.
`8. The method ofclaim 1. funher comprising transmitting
`the sequence oi'parily bits.
`the
`9. The method of claim 8. wherein transniitting,
`sequence of parity bits comprises transmitting the sequence
`of parity hits as part of a no-nsystematic code.
`10. Tlte method oi‘ claim 8, wherein Lransirtiltirtg Lhe
`sequence of parity bits comprises transmitting the sequence
`of parity hits as part of a systematic code.
`11. A device comprising:
`an encoder configured to receive a collection of message
`bits and encode the message bits to generate a collection
`of parity bits in accordance with the following Tantler
`graph:
`
`

`
`US 7,421,032 B2
`
`10
`
`message passing decoder comprising two or more
`checkfvariable nodes operating in parallel to receive
`messages from neighboring checldvariahle nodes and
`send updated messages to the neighboring variable.’
`chcclvt nodes. wherein the message passing decoder is
`configured to decode the received data stream that has
`been encoded in accordance with the following Tanner
`graph:
`
`l[|
`
`Eu
`
`or In
`
`-to
`
`-15
`
`un- '41
`
`'5
`
`E5.‘-
`E3DJ3-
`
`E.F\
`5Z2
`33
`
`19. 'lhc device of claim 18. wherein the message passing
`decoder is con.lig1tmd to decode the received data streain that
`includes the message bits.
`2|). The device of claim 18, wherein the message passing
`decoder is configured to decode the received data stream as if
`a number ofinpuls into nodes v,. was not constant.
`21. The device of claim 18. wherein the message passing
`decoder is configured to decode in linear time at rates Lhat
`approach a capacity ofa channel.
`22. The device of claim 18. wherein the message passing
`decoder oompri sea a heliefpmpagatiolt decoder.
`23. The device of claim 18. wherein the message passing
`decoder is configured to decode lltc received data su-eani
`without the tuessuge hits.
`
`1i
`
`16
`
`if
`
`$
`
`11
`
`2C
`
`.-717-
`53
`:J
`
`".|_’.IC.
`ECQ2
`-::2
`
`E5
`
`12. The device o1"clain1 l 1. wherein the encoder is config-
`ured to generate the collection ofparity bits as ifa number of
`inputs into nodes v, was not constant.
`13. The device o Fclairn 1 I , wltereiit the encoder I.':ot11prises':
`a low—density generator matrix (LDGM) coder configured
`to perform an irregular repeat on message bits having a
`fi.t‘Sl sequence in a source data stream to output a random
`sequence of repeats of the message bits: and
`an accluttulator configured to XOR sum in linear sequel -
`tial fashion a predecessor parity bit and “a" bits of the
`random sequence of repeats of the message bits.
`14. The device ofclaim 12. wherein the accumulator com-
`
`prises a recursive cnnvolutional coder.
`15. The device of claim 14. wltet‘ein the recursive convo-
`lutional coder comprises a truncated rate—l recursive convo-
`lutinnal coder.
`16. The device of claim 14. wherein the recursive convo-
`lution:-il coder has a Lransfer function of [EU +D].
`17. The device of claim 12, liirther comprising a second
`accumulator configured to determine a second sequence of
`parity bits that defines a second condition that constrains the
`random sequence of repeats of the niessage bits.
`18. A device comprising:
`a message passing decoder configured to decode a received
`data stream that includes a collection of parity hits. the
`
`

`
`UNITED STATES PATENT AND TRADEMARK OFFICE
`
`CERTIFICATE OF CORRECTION
`
`PATENT N0.
`APPLICATION NO.
`
`: 72421.03? B2
`: 11x5-42950
`
`Page 1 of 1
`
`DATED
`lNVENTOR(S)
`
`: September 2, 2008
`: Hui Jin, Aarnod Klrandekar and Robert J. McElieoe
`
`It is certified that error appears in the above-identified patent and that said Letters Patent is
`hereby corrected as shown below:
`
`Title Page, item [73] (Assignee), line 1, please delete "'Callifornia'“ and insert
`--Calit‘ornia—-. therefor.
`
`Claim 1 I. Column 9, line 28, delete "V1" and insert --V,——, therefor.
`
`Claim 1 1, Column 9. line 29, delete “U.” and insert --Uk--_. therefor.
`
`Claim 1 I. Column 9, line 29. delete “‘X1“ and insert --X,--. therefor.
`
`Claim 18. Column 10, line 35. delete “V 1'“ and insert --V,--_, therefor.
`
`Claim 18, Colurrm 10, line 36, delete “U1” and insert --Uk--, therefor.
`
`Claim 18, Column 10, line 37, delete “X.” a11d insert -Xr--. therefor.
`
`Signed and Sealed this
`
`Seventeenth Day of February, 2009
`
`.7!i~0«€/F
`
`JD] IN DOLL
`nlc'Iitr_r: U.t'.t'ecfor' Q)“!.’te Ulrfted 5ra.le.\' P£I.l‘t.’h‘f mrd Trridr.-Irmr1l‘ Qflfce
`
`

`
`UNITED STATES PATENT AN