-Constructing LDPC Codes from Simple Loop-Free
`
`Encoding Modules
`
`
`
`~ Dariush Divsalar, Sam Dolinar, Jeremy Thorpe, and Christopher Jones
`_
`Jet Propulsion Laboratory
`- California Instiute of Technology
`Pasadena, CA 91109-8099
`emails: Dariush.beenasa.gov, sam@shannon,jp]nasa.gov,
`
`
`
`thorpe@its.caltech.edu, christop@jpl.nasa.gov
`
`
`AbstractInspired by veceritly proposed Accumulate-Repeat-
`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 Accumulate.
`Repeat-Check-Accumulate codes, and other variations. These
`codes constitute a subclass of LDPC codes with very fast encoder
`stracture. 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 clone to the channel capacity
`limits can be achieved with low maximum variable node degrees,
`as the block alve goes to infinity, The decoding threshold in many
`exaniples 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.
`
`ohINTRODUCTIONcao
` Lsw-deusiiypaity-check (LDPC) codeswere proposed by ©
`
`Gallager (1] in 1962, After introduction of turbo codes by
`Berrou et al [2] in 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 multi-edge type codes in [11] and [13].
`Repeat-Accumulate (RA) [6], Irregular Repeat-Accumulate
`(IRA)
`[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 T 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 coresponding to the protograph, with the same 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,
`TRA, 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
`REPEAT-ACCUMULATE (LRA) CODES
`
`—
`
`in addition to simplicity, have rea- .
`Classical RA codes,
`sonably good 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)
`eode depicted in Fig. 1(a). Por this code the minimum E,/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 decompusuble into permutations
`wlong cach edge of the protugruph. The iterative decoding
`threshold is unchanged despite this constraint imposed by the
`protograph. 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.c., it is
`punctured) and is depicted by a blank cinle. 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 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) 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.
`
`
`
`CALTECH_BCMAPL_00036346
`Apple v. Caltech
`IPR2017-00700
`Apple 1061
`
`0-7803-8938-7/05/$20,00 (C) 2005 TERR
`
`658
`
`Apple Ex. 1061 (IPR2017-00210);
`Apple Ex. 1261 (IPR2017-00219):
`Apple Ex. 1044 (IPR2017-00297),
`Apple Ex. 1061 (IPR2017-00700);
`Apple Ex. 1161 (IPR2017-00701);
`Apple Ex. 1261 (IP R2017-00728)
`AppleInc. v. California Institute of Technology
`
`Apple v. Caltech
`IPR2017-00700
`Apple 1061
`
`

`

`Protogeaphafrata 172 A
`ot:
`
`.
`Tihrestiold0.02 di
`
`+.
`
` Simeoeree) Prepents
`
`
`(a) A coteM/3 RA code With repetition 3, and (b) ile comésparidiig
`Pig. 1...
`+ protograph,
`
`“2 Big3,
`
`“Strucof an IRA code... -
`
`./) DOL Puncture’ RA copss
`Avrate-1/2 classical RA code with a repetition-2 omter vode .
`has a high iterative decoding threshold of 3.01 dB. A much
`lower threshold of 1.116 dB was obtained in [19] for a rate~
`1/2 cade 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 af the interleaver
`m, the systematic punctured RA code can be represented by
`various protographs that yield the same threshold, as illustrated
`in the figure,
`
`“ pratograph
`
` i)
`
`Themeledd 1018 do
`
`, Fig. 3. A systematic puactared RAcode and two possible representations
`by protographs.
`
`
`
`it was shown that the threshold can be further improved by
`precoding the repetition code by an accunwulator. 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 accurmuiator or check plus accumulator,
`
`an Accunnilate-Repeat-Accumulate (ARA) code (19].
`An example of a simple rate-1/2 ARA code, its protagraph,
`and the correspondiug threshold 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
`ABUCoswihcaret8, aale
`‘Rrotageaph
`sryeeerastinttySree
`
`
` Duwgoed 1546 dB
`
`Fig. 3. A tate-1/2 ARA cade and its protograph.
`
`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. Ie [19]
`
`ofthe protograph (one page) per clock cycle per half-iteration
`is shown in Fig. 6.
`VY, ACCUMULATE-REPEAI-C HECK-ACCUMULATE (ARCA)
`Copes
`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)
`
`FANS Coug with roppal 2,Plate 12
`syoteraw biis ta Channat
`
`“check nade
`+ @)
`+ @ Veuable node
`oonnoalsd [6
`channel
`: © vartabie node
`not connected
`to channal
`
`
`
`. Fig; 6. . Pacallel 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
`tate-1/2 ARCA code,
`its protograph, and the corresponding
`threshold are shown in Fig. 7.
`
`ARCA Gode with mapeat 3, ate 72.
`ayatamath: bite to Channes
`
`
` oe asiamestor-
`
`.
`permcinton
`.
` Repest 3 Tevaevard
`
`
`
`
`
`
`“gue
`
`Tieoshold 0.350 ds
`Fig. 7. A rate-1/2 ARCA code and its protograph.
`©
`
`VI. RRPEAT-ACCUMULATE-ACCUMULATE (RAA) CODES
`WITH PUNCTURING
`
` pammzation
`
`Snbatewvar}
`
`ue
`{inkoneayes}
`Protograph
`
`
`
`Trreshatd 0,660 dB
`
`Fig, 8, A rate-1/2 systematic punctured RAA code and iis protograph.
`
`—
`
`-
`
`VI). ACCUMULATE-REPBAT-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 — -
`AAS Gode with repeat 2, Hate 1/2
`syetemale bts to Channal
`
`
` Repeat 2
`accumutato?
`soounutate
`Samu
`emt
`r
`ftuvenoaver
`teriesver)
`
` ‘Thenshois 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 fanily uses an accumulator without puncturing
`as the precoder. Also shown in Fig. 11 are rate-compatihle ~~
`protograph families for ARCA and ARAA codes ofrates 1/2
`and bigher. The higher code rates are constructed by using
`
`660
`
`CALTECH_BCMAPL_00036348
`
`

`

`AMAA Code with repeat2, Raia 1/2
`
` maids o:802a8 +
`
`“Higs 10." Another ratei/2 ARAA code and its protograph.
`
`|,
`Protogeapt of ARSA Family
`
`
`a. Horta tals anhyin2)
`TO Same
`
`
`
`
`Frotogriph af ARCA Family
`
`s
`
`anda fatetantYada
`
`
`
`
`
`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
`prceder rapa2nd Accuttiator—Ancumuiter
`accumulatoris 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,
`UX, 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:/syww.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 io 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. Sterative decoding simulations verity
`excellent performance.
`
`‘Fig. 1.
`
`-AR4A, ARCA, and ARAA protographs ofrates 1/2 atid higher,
`
`
`
`Fig, 12. Iterative decoding thresholds (in 48) for ARCA, AR4A; and ARAA
`Protugraph families, compared to the capacicy limits,
`
`Battal cate, Fale V2
`
` docurndalor
`
`
`
`
`2ornulation
`mmagt
`seeaMeaT terianve!)
`pestograpt
`
`—
`
`Fig. 13.. Serial concatenation of accuntalator with punctured accumulator,
`
`661
`
`CALTECH_BCMAPL_00036349
`
`

`

`‘Beriat code wth repeal 3, Rate 2
`syttowalic ble a Channs!
`
`
`
`
`
`
`Praja
`
`Timnbid0748
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`.
`
`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) RG. 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,” JEEE Trans, Commun., Vol. 44, pp. 1261-1271,
`October 1996.
`.
`{3] M. R. Tonner, "A recursive approach to Tow complexity codes,” TRER
`Trans. inform, Theory, vol, 27, pp. 533-547, 1981.
`td] T. Richardson, A. Shokrollabi, and R. Urbauke, ” Dosign of uspacity-
`approschiag irregular low- densly parity-check codes," TEBE Trans.
`Inform. Theory, vol. 47, pp. 619-637, 2001.
`{5} S.-Y. Chung, D. Porney, T. Richardson, and R. Urbanke, “On the design of
`
`Jow-unsity parity- veck 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. Khendekar, and R. MeBlicce, ” 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, Page(s): 891 -007
`[iQ] Richardson ,
`et al.
`. ° Methods and apparatus for decoding LDPC
`codes, Vented States Patent 6,633,856, October 14, 2003.
`{13] T. Richardson, Muiti-Lidge Type LDPC Codes, presented at the Work-
`shop honoring Prof. Bob McEliece on his 60th birthday, California
`Institate of Technology, Pasadena, Califormia, May 24-24, 2002.
`{12] DAC. MacKay, R.M. Neal, "Nzar Shannon Simit performance of low
`deasity parity check codes," Hlevivonies Letters ,Wol, 32, Issue 18, 29
`Aug. 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 ixcegular graphs.” JEER
`‘Trans. Inform. Theory, vol. 47, yp. 585-598, 2001.
`{1S} T. Richardson and R. Urbanke, “The capacity af low-density parity
`check codes ander message- passing decoding,” TREE Trans. Inform.
`Theory, vol. 47, pp. 599-618, 2001,
`[!6} ¥. Kou, 5. Lin, and 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, [ssue 8, Aug. 2003, Pages 128 -125.
`~ [18]
`§&. Benedetto, D. Divsalar, G. Montorsi, and &, Polara, “ Serial concste-
`nation of interlenved codes: Performance analysis, design, and lterative
`decoding.” IEEE Trans, Info. Theory, val. 44, pp. 909-926, May 1998.
`{19] A. Abbasfar, D. Divsalar, anc K. Yao,"Accumulate Repcat Accumulate
`Codes,” ISYP 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.
`dajorn. Theory, Yokohama, Japan, June 29 ~ July 4, 2003, p. 30.
`
`.
`
`-
`
`. Concatenation of secumlator, repetition, differentiator, ard punc-
`Fig. 14.
`tured accumulator.
`
`BandWoCove
`
`Raton- EWHo,wo.
`
`“Fig. 15._ Performiace of ARGA codes of rates 1/2 and higher with ingot
`block size & = 4096,
`
`&a&
`AB4anetWordCcrorRates
`
`ay Nua
`
`
`=PretogrepnofAltA, with Pwashald {65408
`mamecgspannayneese
`FE We 20 2 ze
`“an Oz M4
`04 Of
`40
`12
`44Foo, 18
`
`Bd
`
`2s
`
`99
`
`Fig. 16. Peformance comparison for examples of rate-1/2 ARA and ARAA
`voiles with input block size k = 1024,
`
`een
`
`CALTECH_BCMAPL_00036350
`
`