-Constructing LDPC Codes from Simple Loop-Free
`
`Jet Propulsion Laboratory
`_
`- California Instiute of Technology
`Pasadena, CA 91109-8099
`
`Encoding Modules
` ~ Dariush Divsalar, Sam Dolinar, Jeremy Thorpe, and Christopher Jones
`e-mails: Datiush.Pemeercnnasit.gov, sam@shannon,jpl.naya.gov,
`
`thorpe@its.caltech.edu, christop@jp|nasa.gov
`
`
`‘Abstract Inspired by veceritly proposed 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 ag seriaV/paralie) concatenations of
`simple modules such as accumulators, repetition codes, differ-
`entiators, and punctured single parity check codes. Examples
`are Accumulate-Repeat-Accumulate (ARA) codes, Accumulate-
`Repeat-Accumulate-Accumulate (ARAA) codes and Aceumulate-
`Repeat-Check-Accumulate codes, and other variations. These
`codes constitute a subclass of LDFC codes with very fast encoder
`structure. They also have a projected graph or protograph rep-
`resentation that allows for bigh-speed decoder implementation.
`Based on density evolution, we show through some examples that
`low iterative decoding thresholds close to the channel capacity
`linuts can be achieved with low maximum variable node degrees,
`as the block slve goes to infinity, The decoding threshold in many
`examples outperforms 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 codes can be obtained with thresholds
`that stay close to their respective channel capacity thresholds
`uniformly.
`
`o.INTRODUCTIONoo
` Lsw-deusiiyparity-check (LDPC) codeswere proposed by ©
`
`Gallager [1] in 1962, After introduction of turbo codes by
`Berrou et al [2] ia 1993, researchers revisited LDPC codes,
`- and extended the work of Gallager using the code graphs
`introduced by Tanner [3] in 1981. After 1993 there have been
`manycontributions to the design and analysis of LDPC codes;
`see for example [12], [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 of maulti-edge type codes in [11] and [13].
`Repeat-Accumulate (RA) [6], Irregular Repeat-Accumulate
`(RA)
`[7]
`and
`recently Accumulate-Repeat-Accumulate
`{ARA)
`[19] codes were proposed as simple subclasses of
`LDPC codes with fast encoder structures, For high-speed
`decoding, it is advantageous for an LIDPC code to be con-
`structed from a protograph [8] or a projected graph [10]. A
`protograph is a Tanner graph with a relatively small number
`of nodes. A “copy-and-permute” operation [8] can be applied
`to the protograph to obtain larger derived graphs of various
`sizes, This operation consists of first making TJ copies of the
`protograph, and then permuting the endpoints of each edge
`
`amongthe 7" variable and ‘I’ check nodes connecied to the set
`of T edges copied fram the same edge in the protograph. The
`derived graph is the graph of a code T times as large as the
`code corresponding 10 the protograph, with the sume rate and
`the same distribution of variable and check node degrees.
`RA, IRA, and ARA codes, with suitable definitions of.”
`their interleavers, all have simple protograph representations
`and thus are amenable to both high-speed encoding and
`decoding. In this paper we define furcher extensions of RA,
`IRA, and ARA codes, all constructed from simple loop-free
`encoding modules. These extensions provide greater flexibility —
`to construct codes with lower decoding thresholds and lower
`error floors.
`
`Il, REPEAT-ACCUMULATE (RA) AND IRREGULAR
`Repaar-ACCUMULATE (LRA) CODES
`
`—
`
`in addition to simplicity, have rea- .
`Classical RA codes,
`sonably guod performance, 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-1/3 Repeat-Accumulate (RA)
`code depicted in Fig. 1(a), Por this code the minimum Ey/No
`threshold with iterative decoding is 0.502 dB. This code has
`a protograph representation shown in Fig. 1(b), as long as the
`interleaver 7 is chosen to be decomposable into permutations
`wlong each edge of the protugraph. The iterative decoding
`threshold is unchanged despite this constraint imposed by the
`protograph. ‘Ihe 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
`panctured) and is depicted by a blank circle. The three check
`nodes are depicted by circles with a plus sign Inside,
`Jin et al [7] generalized the notion of RA codes by allowing
`imegular repetition of the input bits. An Irregular RA CRA}
`code can be viewed as a serial concatenation of a simple
`low density generator matrix (LDGM) code with different-
`degree variable nodes (irregular repetition) as an outer code,
`and an accumulator as an inner code. The encoder can be
`implemented by repetition codes, exclusive-OR's, and an ac-_
`
`cumulator as showa in Fig. 2.
`
`658
`
`0-7803-8938-7/05/$20.00 (C) 2005 TERE
`
`Apple Ex. 1061 (IPR2G17-00210):
`Apple Ex. 1261 (IPR2017-00219):
`Apple Ex. 1044 (IPR2017-00297),
`Apple Ex. 1061 (IPR2017-00700);
`Apple Ex. 1161 (IPR2017-00701);
`Apple Ex. 1261 (IPR2017-00728)
`Apple Inc. v. California Institute of Technology
`
`CALTECH_BCMAPL_00036346
`
`Apple v. Caltech
`IPR2017-00701
`Apple 1161
`
`Apple v. Caltech
`IPR2017-00701
`Apple 1161
`
`

`

`(a) AcateM/3 RA code With repetition 3, and (b) ity comésparidiig
`Pig. 1...
`+ protograph,
`
`Protographafrata 172 58
`ot:
`
`.
`Threstiold0.602 dl
`
`+.
`
` Simeoeree) Prepents
`
`
`“2 Fig”,
`
`“Structure of an IRA code...
`
`-/) DL Pencrured RA cops.
`Avyate-1/2 classical RA code with a repetition-2 contr vode .
`has a high iterative decoding threshold of 3.01 dB. A much
`jower threshold of 1.116 dB was obtained in [19] for a rate-
`1/2 code using a moditied 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
`m, the systematic punctured RA code can be represented by
`various protographs that yield the same threshold, as illustrated
`io the figure.
`
`“ peatograph
`
`
`
` i)
`
`Themeledd 1.018 do
`
`it was shown that the threshold can be further improved by
`precoding the repetition code by an accunvulator. The design of
`the precoder in [19] was guided by an analysis of the extrinsic
`SNR behavior of repetition codes and punctured accumulator
`codes using Gaussian density evolution.’ ‘The use of a cate-]
`accumulator as a precoder dramatically improves the extrinsic
`SNR behaviorof a 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 ia
`Fig. 4. An RA code with an accumulator precoder is called
`
` SNFEN, ENMout
`
`Exteinsic SNR curves obtained by Gaussian density evolution
`Fig. 4.
`comparing: outer codes using repetition-3 with or without precoder, and inner
`codes using an accumulator or check plus accumulator,
`
`-
`
`.
`
`©
`
` Duwghokd 1546 dB
`
`Fig. S.A tate-1/2 ARA code and its protograph.
`
`an Accunnilate-Repeat-Accumulate (ARA) code (19).
`An example of a simple rate-1/2 ARA code, its protagraph,
`and the correspondingthreshold are shown in Fig. 5. The ARA
`encoder in Fig. 5 uses a punctured accumulator as the precoder,
`A parallel decoder architecture based on decoding one copy
`ABACosa wihcarenB, aale
`Rrotageanh
`ryeeerastinttySheer
`
`
`, Fig. 3. A systematic puactared RAcode and two possible representations
`by protographs.
`
`TV. ACCUMULATE-REPE AT-ACCUMULATE (ARA) CODES
`For IRA codes the node degree distribution can be optimized
`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] 10 achieve a very low threshold, ARA
`codes, on the other haad, can achieve a very low threshold
`(e.g., within 0.08 dB from the capacity limit for rate-1/2 codes)
`with variable and check nodes of low maximum degree.
`Consider the rate-1/2 systematic punctured RA code with
`repetition 3, and puncturing period 3, shownin Fig. 3. Te [19]
`
`ofthe protograph (one page) per clock cycle per half-iteration
`is shown in Fig. 6.
`VY, ACCUMULATE-REPEAI-C HECK-ACCUMULATE (ARCA)
`Cones
`The thresholds of ARA codes can be lowered further if we
`also modify the inner punctured accurnulator, We can improve
`the extrinsic SNR behavior of the inner accumulator by using
`simple single-parity-check (SPC) codes prior to accumulation,
`as illustrated by comparison of the two inner code extrinsic
`‘All other iterative decoding thresholds in this paper {exceptfor the analysis
`in Fig. 4} were obtained using actual density evolution for LDPC codes [15].
`
`659
`
`CALTECH_BCMAPL_00036347
`
`

`

`
`
`_ Projected graph (protagraph)
`
`AANA Coug wit: roppal 2,Plate 2
`syoterauia bis ta Channat
`
`“check nade
`+ @)
`+ @ Veuable node
`oonnoalsd Io
`ohannat
`: © varlable node
`not connected
`te channel
`
`
`
`. Fig; 6. . Patallel LDPC decoder architecture for the rae-i/2 ARA protograph
`eods in Fig. 5,
`
`SNR curves io Fig, 4, We cali such codes Accumulate-Repeat-
`Check-Accumulate code (ARCA) codes. These codes are an
`improved version of ARA codes. An example of s simple
`rate-1/2 ARCA code,
`its protograph, and the corresponding
`threshold are shown in Fig. 7.
`
`ARCA Godo with mapeat 8, ate 72.
`aystamath: bite to Channes
`
`
` a aziamustor-
`
`.
`permcinton
`.
` Repest 3 Tevaevard
`
`
`
`
`
`
`“gut
`
` Tieoshold 0.350 ds
`Fig. 7. A rate-1/2 ARCA code and its protograph.
`«
`
`VI. RRPEAT-ACCUMULATE-ACCUMULATE (RAA) CODES
`WITH PUNCTURING
`
` pammzation
`
`Snbareuvar}
`
`que
`{inkoneayes}
`Protograph
`
`
`
`Trreshetd 0,660 dB
`
`Fig, 8,- A rate-1/2 aystematic punctured RAA code and iis protograph.
`
`—
`
`-
`
`VI1. ACCUMULATE-REFBAT-ACCUMULATE-ACCUMULATE
`(ARAA) Copgs
`While RAA codes can yield a very low error floor, we
`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 as in ARA
`codes. This combination is called an Accurmulate-Repeat-
`Accumulate-Accumulate (ARAA) code. A simple example of ‘-
`a tate-1/2 ARAA code, its protograph, and the corresponding
`threshold are shown in Fig. 9. A second cxample is shownin — -
`AHAS Gode with repeat 2, Hate 1/2
`syetemale bts to Channel
`
`
` Repeat 2
`accumutator
`poounutate:
`Samu
`emurtation
`r
`fuvenoaver
`leriesver)
`
` ‘Theshois 0,664 dB
`
`Fig. 9. A rate-1/2 ARAA code and its protograph.
`
`_ Fig. 10.
`
`A rate-1/3 Repeat-Accumulate-Accumulate (RAA)? code
`~ without puncturing was proposed in [9]
`to lower the error
`floor. Its iterative decoding threshold is 0.456 dB. A rate-1/2
`RAA code obtained by puncturing the systematic bits from
`a rate-1/3 RAA code has a threshold of 1.234 dB. A lower
`threshold of 0.868 dB for a rate-1/2 code can be obtained if
`we puncmre the middle accumulator, and nat 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 Repeat & Double Accumulate (RDA} codes in [9].
`
`VIIL RATE-~COMPATIBLE CODE FAMILIES
`
`The codes defined in this paper also allowthe construction
`of code families derived from rate-compatible protographs. For
`example, ARA codes with repetition 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 funily uses an accumulator without puncturing
`as the precoder. Also shown in Fig. 11 are rate-compatihle ~~
`protograph families for ARCA and ARAA codes of rates 1/2
`and bigher. The higher code rates are constructed by using
`
`660
`
`CALTECH_BCMAPL_00036348
`
`

`

`AMAA Code with repeat2, Raia 1/2
`
` ctee
`
`“Hig! 10.” Another ratei/2 ARAA code and ity protograph.
`
`|,
`Protograpt of ARSA Family
`
`
`a. Corts rela anhyine2)
`TO Sew
`
`
`
`
`Frotogriph af ARCA Family
`
`s
`
`nda fatefantYada
`
`
`
`
`
`repetition codes fora portion of tbe input bitsand then adding
`permuted versions of the repetition to the accumulators. ‘The
`thresholds achieved by these three families compared to the
`corresponding capacity limits are shown in Fig. 12.
`:
`TX. SIMPLE SERIAL CODES
`The lowest threshold achievable by a rate-1/2 protograph
`with only 3 variable nedes and 2 check nodes is 0.728 dB,
`achieved by the protograph 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 the outer
`precede rapa2and Aecuttiator—Anccumuiter
`accumulator is also used as an input to the inner accumulator,
`The outer code has minimum distance 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,
`-
`OX, SIMULATION RESULTS
`Perfotmancecurves showing bit error rate (BER) and code-
`word error rate (WER) for codes in the AR4A family are
`plotted in Fig. 15 for input block size & = 4096. Another
`curve shows the BER performance of Flarion’s low-error-
`floor rate-1/2 code of the same size obtained from their web
`site (http://vww.flarion.com). Pertormance curves for rate-1/2.
`AR4A and ARAA codes are compared in Fig, 16 for k =
`1024. Preliminary simulations with & = 1024 for other rate-1/2
`codes proposed in this paper show coraparable performance
`in the waterfall region but higher error floor. All simulations
`were performed on a field-programmable gate array (FPGA)
`implementation of an LDPC decoder developed at IPL,
`XI. CONCLUSION
`In this paper we designed several new varieties of LDPC
`codes using siraple loop-free encoding modules, allowing fast
`encoding. Puncturing can produce families of good codes
`of various rates, These codes have a projected graph or
`protograph representation, which allows for high-speed de-
`coder implementation. Iterative decoding simulations verity
`excellent performance.
`
`‘Fig. 11. AR4A, ARCA, and ARAA protographs ofrates 1/2 atid higher,
`
`
`
`Fig, 12. Iterative decoding thresholds (in 48) for ARCA, AR4A; and ARAA
`Protugraph furilies, compared to the capacicy limits,
`
`Serta cate, Fale V2
`
` aocurndalor
`
`
`
`
`2omnulation
`might
`seeaMaI itorianve?)
`pestograptt
`
`—
`
`Fig. 13.. Serial concatenation of accuntaiator with punctured accumulator,”
`
`661
`
`CALTECH_BCMAPL_00036349
`
`

`

`‘Beriat code wth repeal 3, Rate 2
`syttowalic ble a Channs)
`
`
`
`
`
`
`Praja
`
`Temi0748
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`.
`
`ACKNOWLEDGMENT
`This research was carried out at the Jet Propulsion Labo-
`ratory, California institute of Technology, under contract with
`the National Acronautics and Space Administration.
`REFERENCES
`{1] RB. G. Gallager, Low Density Parity Check Codes. Cambridge, MA: MIT
`Proas, 1963.
`{21 C. Berrou and A. Glavieux, “Near optimum ercor correcting cudiag, and
`decoding: Turbo-codes,” IEEE Trans, Commun., Vol. 44, pp, 1261-1271,
`October 1096.
`.
`{3] M. R. Tanner, "A recursive approach to Tow complexity codes,” TREB
`Trans. Inform, Theory, vol, 27, pp. 533-547, 1981.
`{4} T. Richardson, A. Shokrollabi, and R. Urbauke, ” Design of vspacity-
`approschiag irregular low- densky parity-check codes," IEEE Trans.
`Inform. Theory, vol. 47, pp. 619-637, 2001.
`{5} S.-Y. Chung, D. Pormey, T. Richardson, and R. Urbanke, “On the design of
`
`Jow-unsity parity- vleck codes within @.0045 dB of the Shannon limit”
`IEEE Consununication Letters, vol. §, pp. 58-60, 2001.
`{6} D. Divsalar, 4. Jin, and R. MeENcce, ” Coding theorems for Turbo-like
`codes,” in Proceedings of the 1998 Allerton Conference, pp. 201-210,
`1998,
`{7] H..Jin, A. Khendekaz, and R. MeBliece, ” Loegular repeat-accumulate
`codes.” in Proc, 2nd Intemational Symposiura on Turbo Codes, pp. 1-8,
`2000.
`{8} Jeremy Thorpe, Low Density Parity Check (LDPC) Codes Constructed -
`fromProcographs, IPL INP Progress Report 42-154, August 15, 2003.
`[9] D. Divsalar, 8. Dotinar, and F. Pollara, “Iterative Turbo Decoder Analysis
`based on Density Evolution,” JEEE Journal on Select Areas in Commu-
`nications, Volume: 19 Issue: 5 , May 2001, Pape(s): 891 -007
`[10] Richardson ,
`et al.
`. ° Methods and apparatus for decoding LDPC
`codes? Vented States Patent 6,633,856, Ociaber 14, 2003.
`{13] T. Richardson, Muisi-Lidge Type LDPC Codes, presented at the Work-
`shop honoring Prof. Bob McEliece on his 60th birthday, California
`Institate of Technology, Pasadena, California, May 24-24, 2002.
`{12] DAC. MacKay, R.M. Neal, "Ngar Shannon Jimit performance of low
`deasity parity check codes," Hlevivonics Letters ,Wol, 32, Issue 18, 29
`Ang. 1996, Page(s) 1643.
`U3) ‘f Richardson aad BR. Urbonke,"The Renaissance of Gailagers Low-
`Density Parity-Check Codes,” [EEE Communications Magazine, pages
`126-131, August 2003
`[14] M. Luby, M. Mitzenmacher, A. Shokrollaai, and D. Spielman, “Analysia
`of low density codes and improved designs using ixceguler graphs.” JEER
`"Trans. Inform. Theory, vol. 47, yp. 585-598, 2001.
`{1S} T. Richardson and R. Urbanke, “The capacity of low-density parity
`check codes under message- passing decoding,” TREE Trans. Inform.
`Theory, vol. 47, pp. 599-618, 2001,
`[!6} ¥. Kou, 5. Lin, end MLP.C. Possorier, “Low-density parity-check codes
`based on tinite geometries: a rediscovery and new resulls," IKKE ‘trans.
`actions on Information Theory, Volume: 47 Issue: 7, Nov. 2001, Page(s):
`QTLL -2736.
`117] BR. Kachischang, "Codes defined on graphs.” IERE Communications
`Magazine, Vol. 41, [issue 8 , Aug. 2003, Pages 128 -125.
`~ [18]
`§&. Benedetto, D. Divsalar, G. Montorsi, and &, Polara, “ Serial concste~
`nation of interlenved codes: Performance analysis, design, and lerative
`decoding.” IEEE Trans. Info. Theory, vol. 44, pp. 909-926, May 1998.
`{19] A. Abbasfar, D. Divsalaz, and K. Yao,"Accumulate Repcat Accumulate
`Codes,” ISTP 2064 and Globecom 2004.
`120] J. Xu and §. Lin, “A Combinaioric Supemosition Method for Cor-
`Ateucting Low Density Parity Check Cores,” Proc, 2003 LEEK Int. Symp.
`dajorm. Theory, Yokohama,Japan, June 29 ~ July 4, 2003, p. 30.
`
`.
`
`+
`
`. Concatenation of secunilator, repetition, differentiator, ard punc-
`Fig. 14.
`tured aecurnulator.
`
`BaiaWordCove
`
`Raton« * EWHo,wo.
`
`“Fig, 15._ Performance of ARGA codes of rates 1/2 and higher with ingot
`block size & = 4096,
`
`&a&
`AB4aneWordCcrorRates
`
`ay NMA
`
`
`=PretogrepnofAlAs with Pwashald {65408
`sameucaspannytncsntn
`FE We 20 AW
`“an Oz M4
`0A
`OF
`40
`IR
`44Feova, 18
`
`ze
`
`Bd ws
`
`99
`
`Fig. 16. Peformance comparison for examples of rate-1/2 ARA and ARAA
`voies with input block size k = 1024,
`
`een
`
`CALTECH_BCMAPL_00036350
`
`