Constructing LDPC Codes from Simple Loop-Free
`Encoding Modules
`
`
`
`Duriush Divsnlar. Sam Dolinar. Jeremy Thorpe, and Christopher Jones
`,
`.
`let Propulsion Laboratory
`- California Institute of 'lechnology
`Pasadena, CA 91109—8099
`e-nlails: DanusltDivanlar®1plnewgov. sum®shannonipl.nasal.gov,
`thorpe®itscultechedu. christopldjpl nasu.gov
`
`
`Absfinct~lnsplred by recently proposod Accumulate-Repent—
`Accumulate (ARA) codes, in this paper we propose a construction
`method for LDPC codes using simple loop-free encoding modules.
`Such codes can be viewed all serial/parallel ounmtenntions of
`simple modules such as accumulators, repetition codea, differ-
`entiators, and punctured single parity check codes. Examples
`are Amumulate-Repeat—Aecumulute (ARA) codes, Accumulate-
`Repeat-Aecumulnte-Aceumulatc (ARAA) codes and Accumulate-
`Repent-Chedr-Accnmulnte codes, and other variations. These
`codes: constitute a subclass of LDPC codes with very fast encoder
`structure. They also have a projected graph or protograph rep-
`mcntatlon that allows for high-speed decoder implementation
`Based on density evolution. we show through some examples that
`low iterative decoding thresholds clone to the channel capacity
`limits can be achieved with low maximum variable node degrees,
`at the block sine goa to infinity. The decoding threshold in many
`exnmples output-[0mm that of the best known unstructured irreg-
`ular LDPC codes constrained to have the same maximum node
`degree. Furthermore, by puncturing the accumulator modules,
`any desired higher rate nodes can be ohtnined with tlirwllolds
`that stay rim to their respective channel capacity thresholds
`uniformly.
`
`Llnrkonu‘crlort
`
`
`Low-denSity 'perityrheck (LDPC) codes‘w'lére proposed by '
`(Salinger [1] in 1962. After introduction of turbo codes by
`Berton er al [2] in 1993, researchers revisited LDPC codes,
`. and extended the work of Gallagcr using the code graphs
`introduced by Thnner [3] in 1981. After 1993 there have been
`many contributions to the design and analysis of LDPC codes;
`see for example [l2], [14]. [15},
`[5]. {16], [17], [20] and
`references there. Recently there has been a flurry of work on
`designing LDPC codes with imposed sub—structure, starting
`with the introduction oi“ mulncedge type codes in [11] and [13].
`Repeat-Accumulate (RA) [6]. Irregular Repeat-Accumulate
`(IRA)
`[7]
`and
`recently Accumulate-RepeerAccumulete
`(ARA) [19] codes were proposed as simple subclasses of
`LDPC codes with fast encoder structures. For high-speed
`decoding, it is advantageous for an LDPC code to be con-
`structed from a protograph [8] or a projected graph [10]. A
`protogrnph is a Tanner graph with a relatively small number
`of nodes. A “copy-end-pennute" operation l8] can be applied
`to the protograph to obtain larger derived graphs of various
`sizes. This operafion consists of first making T copies of the
`protogrupll, and then mounting the endpoints of each edge
`
`among the T variable and T check nodes connected to the set
`of T edgee copied from the same edge in the protogrnph. The
`derived graph is the graph of a node T times as large an the
`code corresponding to the protogrnph. with the some rate and
`the same distribution of variable and check node degrees.
`RA, IRA, and ARA codes, with suitable definitions of ’-
`their inlerieuvcrs. all have simple pmtograph representations
`and thus are untenable to both high~speed encoding and
`decoding. In this paper we define further extensions of RA,
`IRA. and ARA codes, all constructed from simple loop-free '
`encoding modules. These extensions provide greater flexibility p
`to construct codes with lower decoding thresholds and lower
`error floors.
`
`.
`
`II. REPEAT-ACCUMULATE (RA) AND IRREGULAR
`REPEAT-ACCUMULATE (iRA) CODES
`
`.
`
`’
`
`in addition to simplicity. have rea- .
`Classical RA codes.
`sonably good perfonnance, with iterative decoding thresholds
`within 1 dB from capacity for rates less than or equal to 1/3.
`RA codes use fixed repetition for the input bits. As a simple ‘
`example, we consider the rate-U3 Repeal—Accumulate (RA)
`code depicted in Fig. 1(a). For this code the minimum LIL/No
`threshold with iterative decoding is 0.502 dB. This code has
`a protograph representation shown in Fig. 10)), as long as the
`interleaver 77 is chosen to he decomposable into permutations
`along each edge of the protograpll. The iterative decoding
`threshold is unchanged despite this constraint imposed by the
`protogmph. The protograph consists of 4 variable nodes and
`3 check nodes, connected by 9 edges. Three variable nodes are
`connected to the channel and are shown as dark filled circles.
`One variable node is not connected to the channel (i.e., it is
`punctured) and is depicted by a blank circle. The three check
`nodes are depicted by circles with a plus sign inside.
`Jin et a1 [7] generalized the notion of RA codes by allowing
`irregular repetition of the input bits. An Irregular RA (IRA)
`code can be viewed as a serial concatenation of a simple
`low density generator matrix (LDGM) code with different-
`degree variable nodes (irregular repetition) all an outer code,
`and an accumulator as an inner code. The encoder can be
`implemented by repetition codes, exeluuiveOR‘s. and an ac-
`comnletor as shown in Fig. 2.
`
`,
`
`0—7803-8938-7Ili5/SMDO (C) 2005 IEEE
`
`658
`
`Apple Ex. 1061 (IPR2017—00210);
`Apple Ex. 1261 (IPR2017-00219);
`Apple Ex. 1044 (IPR2017-00297),
`Apple Ex. 1061 (IPR2017~00700);
`Apple Ex. 1161 (lPR2017-00701);
`A I E .1261 (IPR2017«OO7’28)
`ASS: In: V. California Institute of Technology
`
`
`
`CALTECH_BCMAPL_00036346
`
`Apple V. Caltech
`IPR201 7'00701
`Apple 1 1 61
`
`Apple v. Caltech
`IPR2017-00701
`Apple 1161
`
`

`

`murmur-ml: no
`go.
`
` Mia-w
`
`‘
`- 71:meo(in do
`
`(a) A rutc-l/J RA rode With-repetition a, and (b) ll! conerponding
`rug, 1'.
`> protogruph.
`
`»
`
`
`
`'
`
`.3 nu. scum utnntnA code“; ‘-
`
`7 m; mature: RA coons . *
`Armada classical RA code with a repetition—zoom code .
`has a high iterative decoding threshold of 3.0i (13. A much
`lower threshold of mo (18 was obtained in [l9] for a rate-
`l/Z code using a modified RA construction as shown in Fig. 3.
`Here the outer code has repetition 3 or 4, the systematic bits
`are transmitted, and the accumulator code is punctured to make
`the overall rate 1/2. With suitable definitions of the interleaver
`71’, the systematic punctured RA code can be represented by
`various pmtographs that yield the same threshold, as illustrated
`in the figure.
`
`”limtoarunn
`
`
`
` to
`
`11W |.'l IS :49
`
`‘ Fig, Li. A systematic punctured RA- code and two possible representations
`by protomhar
`
`it was shown that the threshold can be further improved by
`precoding the repetition code by an accumulator. The design of
`the precodcr in ['19] was guided by an analysis of the extrinsic
`SNR behavior of repetition codes and punctuted accumulator
`codes using Gaussian density evolution.1 The use of a rate-l
`accumulator as a prccoder dramatically improves the extrinsic
`SNR behavior of it repetition 3 outer code in the high extrinsic
`SNR region and hence improves the threshold, as shown by
`comparison of the two outer code extrinsic SNR curves in
`Fig. 4. An RA code with an accumulator precoder is called
`
` Dunn. GNI'InuI
`
`»
`
`‘
`
`,
`
`Extrinsic SNR curves obtained by Gaussian dentily evolution
`'4.
`Fig.
`comparing: outer caries using repetition~3 with or without pretender, and inner
`codes using an accumulator or check plus accumulator.
`
`an Accumulate-RepeatuAccumulate (ARA) code [19].
`An example of a simple rate-U2 ARA code, its pmlograph,
`and the corresponding threshold are shown in Fig 5. The ARA
`encoder in Fig. 5 uses a punctured accumulator as the precodcr.
`A parallel decoder architecture based on decoding one copy
`wow momma Am in
`mew:-
`Monm-
`
`
` ‘N-wuH am on
`
`Fig» 5. A talcum ARA code and its protograph.
`
`IV. ACCUMULA’l‘E-REPE AT<ACCUMULATE (ARA) CODES
`For IRA codes the node degree distribution can he optimlwed
`to achieve low thresholds. However,
`to achieve a very low
`threshold, the maximum repetition for some portion of the
`input bits can be very high, Similar requirements on the
`maximum variable node degree were noted for a general
`irregular LDPC code {4] to achieve a very low threshold. ARA
`codes, on the other hand. can achieve a very low threshold
`(c.g.. within 0.08 All from the capacity limit for rate-.i/Z codes)
`with variable and check nodes of low maximum degree.
`Consider the mte-l/2 systematic punctured RA code with
`repetition 3, and puncturing period 3, shown in Fig. 3. In [19]
`
`of the protogntph (one page) per clock cycle per half-iteration
`is shown in Fig. 6.
`V. ACCLMULATE-REFBA‘I-CHECK‘ACCUMULA’I‘E (ARCA)
`Cones
`The thresholds of ARA codes can be lowered further it" we
`also modify the inner punctured accumulator. We can improve
`the extrinsic SNR behavior of the inner accumulator by using
`simple singie-paritycheek (SPC) codes prior to accumulation,
`as illustrated by comparison of the two inner code extrinsic
`‘All other iterative decoding thresholds in this paper (cxcwt for the analysis
`in Fig. 4) were ohmined using actual density evolution for LDPC codes US].
`
`659
`
`CALTECH__BCMAPL_00036347
`
`

`

`
`
`‘ Projected graph (ordination)
`
`
`
`'checkmkt
`a;
`» . van-Mu undo
`connected to
`chm-Incl
`: C variable node
`mtoonnmcd
`
`to channel
`
`- Fig. 6.. miner Lore decoder ar'cmwéiu}: {oi the main ARA protogrttph
`code in Fig. 5.
`
`SNR curves in Fig. 4. We call such curios Accmnulate-‘Repeao
`Check-Accumolutc'codc (ARCA) codes. These codes are an
`improved version of ARA codes. An example of a simple
`rate-U2 ARCA code,
`its protograph, and the corresponding
`threshold are shown in Fig. 7.
`
`AREA Coda wan repeats. nee 1‘12:
`“amour: use to channel
`
`"'
`
`"M can will? moat Mm I'z
`awcmu: mu In cmml
`
` mmimun
`
`pmmlllflmn
`Unwmvm)
`
`(amount)
`WWW
`
`
`
`1}".st 0.993 ‘19
`
`Pig. 8.‘ 'A rate-i7? systematic punctured RAA code and its protogmph.
`
`Vii. ACCUMULATE-REPESA’I‘~ACCUMULATE-ACCUMULA‘I‘E
`(ARAA) Coons
`While RAA codes can yield a very low error floor, we V
`also desire the somewhat lower decoding thresholds of ARA
`codes. Hence we were motivated to improve the threshold of
`RAA codes by using an accumulator precoder an in ARA
`codes. This combination is called an Accumulate—Repeat-
`Accurnuiate-Aocumulate (ARAA) code. A simple example of ‘
`a rate-m ARAA code, its ptotograph, and the corresponding
`threshold are shown in Fig. 9. A second example is Shown in ,.
`MM Gotta wan meat 2. Rate \/2
`
`syetnmulic (the to Channel
`
`_
`
`‘
`
`v
`
`-
`
`
`“W
`Mahala ow as
`
`Fig. 7. A t‘ate‘lll ARCA code and its protogmph.
`c
`
`VI. RSPF.AT-ACCUMULATEvACCUMULATE (RAA) CODES
`WITH PUNCTURING
`
`
` Home: 2
`
`mandala
`smuluuon
`mutation
`,lnzedulvun
`whom)
`'
`
` mama 0.54 dB
`
`Fig. 9. A rated/2 ARAA code and its protograph.
`
`. Fig. 10.
`
`A rated/3 Repeat-Accumulate-At'cumulate (RAATV’ code
`' without puncturing was proposed in [9]
`to lower the error
`floor. Its iterative decoding threshold is 0.456 dB. A rate-U2
`RAA code obtained by puncturing the systematic bits from
`a rated/3 RAA code has a threshold of 1.234 dB. A lower
`threshold of 0.868 dB for a rate-U2 code can be obtained if
`we puncture the middle uwumulator, and not the systematic
`bits. This type of code is a systematic punctured RAA code,
`shown in Fig. 8 along with its corresponding protograph.
`
`2This code was called a Rupert A: Double Accumulate 021M) coda in [9].
`
`VIII. RA‘l‘B~COMPATlBLE CODE FAMILIES
`
`The codes defined in this paper also allow the construction
`of code families derived from rate-compatible protographs. For
`example, ARA codes with rcpetition 4 (AR4A) are shown in
`Fig. 11 for rates 1/2 and higher. For this example we chose
`repetition 4 rather than 3 to achieve lower error floor. This
`AR4A code family uses an accumulator without puncturing
`as the practical: Also shown in Fig. 11 are rate~compatihlc
`protograph families for ARCA and ARAA codes of rates 1/2
`and higher. The higher code rates are constructed by using
`
`'
`
`'
`
`660
`
`CALTECH_BCMAPL_00036348
`
`

`

`MUM coda Mn ”Male. M16112
`Iylhmtl: DIG. I)Channel
`
`
`nllofl
`.
`"imam-q
`
`
`
`
`
`
` ' mm amas- -. '
`
`”Fig. 10.
`
`' Another rolc-‘llz ARM undue-ind its prowgraph»
`
`repetition codex for‘n portion of the input hits‘and thcn adding
`permuted versions of the repetition to the accumulators. The
`thresholds achieved by these three fmnilies compared to the
`corresponding capacity limits are shown in Fig. 12.
`IX. SIMPLE SERIAL CODES
`
`The lowest threshold achievable by a rate-U2 protogrnph
`with only 3 variable nodes and 2 check nodes is 0.728 dB.
`achieved by the protogmph shown in Fig. 13. This is just a
`serial concatenation of an outer accumulator with a punctured
`inner accumulator, although in this case the input of thc outer
`accumulator is also used as an input to the inner accumulation
`The outer code has minimum distancc 3. To obtain better
`interleaving gain, we need to increase the minimum distance
`of the outer code [18]. The minimum distance of the outer
`accumulator can be increased to 6 by puncturing its output.
`and repeating the input of the outer accumulator by 3 as shown
`in Fig. 14‘
`
`‘
`X. SIMULATION RESULTS
`"
`.
`Perfonnnncé'curves showing bit error rate (BER) and code”
`word error rate (WER) for codes in the AR4A family are
`plotted in Fig.
`l5 for input block size lc = 4096. Another
`curve shows the BER pcrfonnance of Flariou’s lowmrrorv
`Floor ratc~ll2 code of the same size obtained from their web
`site (http://www.ilarion.com). Performance curves for rate—ill
`AR4A and ARAA codes are compared in Fig, 16 for k =
`1024. Preliminary simulations with I: r— 1024 for other rate-U2
`00ch proposed in this paper show comparable performance
`in the waterfall region but higher error floor. All simulations
`were pei'fonned on a field-programmable gate array (FPGA)
`implementation of an LDPC decoder developed at JPL.
`XI. CONCLUSION
`In this paper we designed several new varieties of LDPC
`codes using simplc loop—free encoding modules, allowing fast
`encoding. Puncturing can produce families of good codes
`of various mics. These codes have a projected graph or
`prolograph representation, which allows for high-speed de-
`coder implementation. Iterativc decoding simulations verify
`excellent performancci
`
`’
`
`661
`
`' may cl MM anily
`
`. mmrquiyrmo
`
`n=0 ‘tuu
`
`
`Fmtqfiph n! ARCA Fans»;
`
`5‘
`
`m1. muwmnm
`1-0.1.0‘.‘
`
`
`
`
`’ mmgmpb ai WA Family
`
`2"
`
`lmilh
`
`
`
`omIntoutmvywo
`«=4; 1. no
`
`«panama
`
`mum-um Aluminiu-
`
`Fig. ‘l i. MUM, ARCA, and ARAA protngrnphs of rules 1/2 and higher.
`
`
`
`Fig. 12. . Imratlve decoding thresholds (in dB) for ARCA. Anl’A; and ARAA
`proiogmph fumih'rs, conlpnrcd to the cupnciry limits.
`
`5M” cak. Ml If}.
`
` Immnlala
`
`cannula»
`m};
`u” 1"“ Unknown!)
`
`
`
`fig. 13. Serial concatenation of accumulator with punctured accumulu'tor.‘
`
`CALTECH_BCMAPL_00036349
`
`

`

`Evin! Mn 71 m maul 3. RM) 1’2
`”Wink bill II Channel
`
`
`
`. Concatanitian of nonhuman kupetition, difl‘emntinibr, and punc-
`Fig. 14.
`tunsd accumulator.
`
`‘Z
`
`V;
`
`
`imama-item,. at.5;
`
`
`
`
` ' EDI)“. .
`till
`.
`fig. 15.. Perfb‘mmmc bf AMA bodes of was 1/2 m higher with input
`block me is :- 4096.
`
`-
`
`10‘
`
`
`
`
`
`>
`
`ACKNOWLEDGMENT
`This research was carried out at the. .let Propulsion Labo-
`ratory, Califomitl Institute of Technology, under contract with
`the National Aeronautics and Space: Administration.
`REFERENCES
`(1] R. G. Gnilegcr, Low Density Parity Chuck Codes. Cambridge. MA: MIT
`szx. 1963.
`12] C. Burton and A. Glnviwx. "NW uptimum ei'mi' cumming ending and
`decoding: Turbamdcs." [BEE Mm. Commun, Vol. 44. pp. 1251—1271,
`Octobcr 1996.
`,
`(3] M. R. 'Ilmner. "A mcursiv: appmaclt to low complexity cuties." IEEE
`Trans. inform. Tliwty. vol. 27. pp. 533-547. 1931.
`[4] T. Richardwu, A. Shokmllnhi, and R. Urbauke, ” Design of capacity-
`npwoiwhing inegulnr low- density parity-check codes." 18122 Tums.
`Inform. Theory, vol. 47, pp. 619637, 2001.
`[5] S.-\’. Chung. D. Penney. ’l‘. Richudson, and R. Ethankc, ”0n the design of
`
`inw ntity parity‘ cheat nodes within 0.0045 d8 of the Shannon limit."
`XEEE Communication Letters, vol. 5. pp. 58-60. 2001.
`16} D. Divsniur. .‘1'. fin, and R. McEliccc. " Coding mcmms for Turboiikc
`codes," in Proceedings of the 1998 Allcmm Conference. pp. 201-210,
`1998.
`[7] H..Jin, A. Kliundnkax. and R. McFJicac. ” lmgulnr mpmt-ncuumulutr
`coda." in Pm. 2nd lntmmtianai Symposium on Thrbo Codcs. pp. 1-8.
`2000.
`[8] Jeremy Thurpc. Low Density Pim’ty Check (LDPC) Codes Constructed .
`from hutogi'aphs. JPL INP ngtcss Report 42-154, August 15. 2003.
`[9] D. Divanlar. S. Dolinnr. and F. Pollnra. "Itcmivc ’lluba Dcmdcr Analysis
`based on Density Evolution." IEEE Journal on Scicct Area: in Commu-
`nicaiions, Volume: 19 Issue: 5 . May 2001, Pant“): 891 4,307
`[10] Richardson .
`ct Ri.
`. “ Methods and apparatus fax dccnding LDPC
`codex." United State.» Patent (1.633356. fictnher 14, 2003.
`[1t] '1". Richardson. Mulimdgc ’Iypc LDPC Codcs. prcsmmd at the Work-
`shop honoring Prof. Bub McEiiccc on his 60th binhduy. Calii’oxnin
`Institute. of Technology, Pasadena, California. May 24~75. 2002.
`{12] DJC. Macléay. RM. Nell, "Near Shannon limit pctfuxmnac: of low
`density parity dwelt codes.“ mfififfllllilfli Lctlurs ,Vul. 32, Issue iii, 29
`Aug. 1996. Faucet) 1645.
`'l'. Richardson and R. Urbank:,"i‘lzc Renaissmac 0f Gallagem bow-
`Demity Parity-Check Codes." [EEE Communications Magazine, pagtm
`126-13 l, August! 2003
`[M] M. Luhy. M. Mitzcnmachcr. A. Shokmllnhi, and D. Spiclmnn, "Analysis
`of low deceit)! coats and improved designs using ixtcghlar gram." IEEE
`Tram. lni‘cnn. Theory. vol. 47, pp. 535—598, 2001.
`[is] T. Richardson and R. Urimnke, ”Th: capacity of law-dmity parity
`check sodas undcr mesmgb passing decoding," [EBB nuns. Inform.
`‘l‘hwry. vol. 47. pp. 599-6l8, 2001.
`[16} Y. Kim. 3. Lin. and MJ’C. Fussox‘im‘, "Low‘dcnxlty paxity-cilixzk codes
`based on finite gmomattics: a ml'mcavery and new tesulls." liiEE Trans
`action: on lnfmmation Timmy, Volume: 47 Mae: 7 . Nov. 2001. Page“):
`2711 .2736.
`[17] RR. Knchiacimng, ”Codi-.5 definad on gtaphs." IEEE Communications
`Magazine. Vol. 4!, lawn 8 , Aug. 9.003. Page-3 118 -125.
`* [l8] 3. Benedetto, D. Dlvsainr, (i. Montcm', and E4. Poliara. " Serial concate-
`nation of lntcrlctwcd comm: Pcrformancn analysis. design. and lmalivc
`dccodlng." IEEE 'mms. info. Theory, vol. 44, pp. 909-926. May 1993.
`[l9] A. Abbuxfax. D. Dwsalur. and K Yaoi’Accumuime Repeat Acwmulntc
`Cadas." lSI'l‘ 2004 and Globecam 2004.
`[20] J. Xu and S. Lin, “A Combinatoric Supcmosition Method for Can-
`Mmcting Low Density Pniiiy Cltcclt Cadet," Ploc. 2003 IEEE Int. Symp.
`[Ii/”mm Theory, Yokoiiuzrm, Japan. June 29 ~ July 4. 2003, p. 30.
`
`’
`
`..
`
`US]
`
`gag...
`i?gamma-mm
`
`1m“
`
`
`
`
`n“fiwvmoiMM/‘WNMMIIWG
`1.: uEmmaiii-no.4 u 2..
`j“! M on
`0.0
`on
`1,0
`
`an
`
`an
`
`no
`
`Fig. l6. Pexfonnnnco comparison for example; of ratc~lI2 ARA and ARAA _
`codes with input block size k = 1024.
`
`662"
`
`CALTECH_BCMAPL_00036350
`
`