Design of P1“O\’Etl.)l}’ Good LoW—Densit_V Parity Clieelt Codes
`
`Tom Rit'ha1'dson_, Amin Sholtrollahi and Riidiger Urbanlie
`Hell l.ahs,
`l.uc.ent 'l‘echno|ogies
`l\-'I1n‘ray Hill: NJ 07974
`
`April 5,_ l 999
`
`Abstract
`
`We design sequences of low—densiLy parity (Jl1V:‘.C.l-L codes that provablu\»' perforni at rates ex-
`tremely close to tl1e Sliannon capacity. The. codes are built from highly irrogiilar bipartite graphs
`with carefiilly chosen degree patterns on both sides. Our theoretical analysis of the codes is based
`on
`Additionally, based on the assuniption that the u11tle1'lyi11g c.on1n1unic.ation chainiel is
`sjy'n1n1et1‘ic, we prove that the ]JI‘OlJEl.l)llll'_'y' densities at tl1e message nodes of the. graph sat.isfjv'
`a certain syiriirietry. This enables us‘ Lo derive a succinct desc.ription ol the density evolution
`for the case of a belief propagation decoder. F111‘tl1er1noro, we prove a stability condition which
`implies an upper bound on the fraction of errors that a belief‘ propagation decoder can correct
`when applied Lo 21. code induced froni a bipartite grapli with a given degree distribution.
`0111‘ codes are fo11nd by optiinizing the degree st1‘11ct111‘e of the underlying graphs. WE‘. develop
`several strategies to perform this optimization. We also present some simulation results for the
`codes found which sliow that tl1e perfoianaiice of the codes is very close to the asymptotic
`theoretical hounds.
`
`IJ'1.dt:;r Tt!J"Jns
`codes
`
`Low density parity (Jl1t‘.C.l-L eodesu beliel propagation, turbo codes,
`
`irregular
`
`1
`
`I11trod11cti011
`
`In this pa.per we present .iri‘egu.i.'m" |ovv'—density parity check codes (l;l)l’C.Cs] which exhibit pertor—
`
`mance extretnely close to the best possible as tl(_‘.l.L‘1‘II1l11(_‘(l by the Sliannon capacity l01'I[L11ld.. For
`
`the additive white Gaussian noise channel (_AW’G.\'C‘T) the best code of rate one-half presented in
`
`this paper has a threshold Within (].(]6dB from capacity, and simulation results show that our best
`
`l,|)l’(:"~(:'l of length "[05 achieves a bit error probability’ of "I043 less than OX1 3dH aWa_§»' from r,a.pa.citjr,
`
`l1andil_y' beating the best [t111‘lJo] codes liILOW11 so la1'.
`
`LDPCCs possess .'se.ve1'al other distiiiet a.1lvaI1ta,ges over L111'bo—codes. First, the C.0II1pl(_‘Xlt 5: ol‘ heliell
`
`propagation) decoding; is somewhat less than that of t1:1rbo—c.odes and, being fully parallelizable, can
`
`potentially be performed at sigiiificaiitly greater speeds. Second, as indicated in a previous paper
`
`[1], VE!|‘_\_’ low complexity decoders that closely approximate heliet propagation in performance may
`
`Apple 1219
`Apple 1219
`
`

`
`be (and liave l)(,‘.L‘I1) designed for tliese codes. Third, lm\«'—dc11siL_y parity cliecl«: decoding is \«'e1'iliable
`
`in the sense that decoding to a correct codeword is a detectable event. One practical objection to
`
`low—density pa.rity—cl1eck codes has been tha.t their encoding complexity is high. One way to get
`
`a.round this problem is by slightly modif_\;'ing the construction of codes from bipartite graphs to a,
`
`cascade of such graplis, sec [2, 3]. A Llilleicrit solution for practical purposes, which does not require
`
`cascades, will be presented elsewhere
`
`Let us recall some ba.sic notation. As is well known, low—density parity—cl1eck codes are well repre-
`
`sented by bipartite graphs in which one set of nodes, the r:r,I.rir.'b."£ node.-a, corresponds to elements
`
`of the codeword a.n d the other set of nodes, the rt'h.ert'k n.or."es-.4 corresponds to the set of pa.rity—c.l1eck
`
`constraints satislied by codewoids of the code. Rt-.gula'r'low—density pa1'iL_y—cl1ccl: codes are those for
`
`which all nodes of the san1e type have the san1e degree. Thus, a (3,6)—regular loW—density parity-
`
`cheek code ha.s a graphical representation in which a.ll variable nodes have degree 3 and all check
`
`nodes have degree 6. The bipartite graph determining such a code is shown in l<"ig.
`
`'1.
`
`U I
`
`Figure 1: A (3,(*i)—regular code of lengtli 10. There are l(] variable nodes and 5 check nodes. For
`each checl; node c.,- the sum (over GF('2)) of all adjacent variable nodes is equal to zero.
`
`For an irrc:gulc1.rlow—clensi1:y parity—cl1eck code the degrees of each set of nodes are chosen accorcl—
`
`ing to some distribution. Thus, an irregular loW—density parity—checl< code might have a graphical
`
`Hughes, Exh. 1029, p. 2
`
`

`
`represe1Lt.ation in which ltall t.he varia.ble nodes have deg1‘ee 5 and half hawe degree 3, while hall
`
`the constraint nodes have degree ti and half have degree 8. For a given length and a. given de-
`
`gree sequence (finite distribution) We define an en..sembl'e of codes by choosing the edges, i.e., the
`
`connections between Variable and check nodes, randoml_\;'. More precisely, we enumerate the edges
`
`emanating lirorn the variable. nodes in some a1'lJit1‘a1'_v order and proeee.d in t.he sarne way with the
`
`edges emanating from the check nodes. Assunie that the number of edges is E. Then a. code ( a par-
`
`ticular instance of this ensemble) can be identified with a permutation on E letters. Note that all
`
`elements in this ensemble are equiprobable.
`
`In practice the edges are not chosen entirely randomly
`
`since. e.e1'tain poterttially t1ILl0rtt1IL‘d.t.(_! events in t.he graph eonst.1'11ct.ir_m can be easily avoided.
`
`In a 1'ee.e1'Lt. paper‘
`
`[1] we presertted an itS_VII1_'[)t()l.lf.‘. analysis of LDPCCS under Inessage passing
`
`decoding. Assume we have the following setup:
`
`1. VVe. are given an o1'de1'ed family olbinary—inp11t discrete memo1'_vless Lthannels pa1'amet.erized
`
`by at real pa.raInete1' 6 such that if (51 < 52 then the Lthannel with pa.1‘aInete1' 62 is a pl1ysie.all_v
`
`degraded version of the channel with parameter 6 .. Further, each channel in this family fulfills
`
`the channel s_3«'rr1rnetrjy' condition
`
`Pt:/lit? = 1J=1J(—;ul:Ir= —1)-
`
`(1)
`
`2. A sequence of code ensembles (.’,.[/\,p) is specified, where 73.
`13
`.r_
`.2
`.r_
`.
`.
`/\(_;r) :: Z‘-‘i_1 )t.;.*r:”
`(_p(_;r) :: Z:::;1,r,a.;.~'r:” 1)
`is the.
`\«'a.1'1a.lJle
`
`1
`
`is the length of the code and
`
`(_elLec.l«:) node degree. sequence.
`
`More p1'ec.isel_y,
`/\€;
`('05)
`is the lraetion of edges emanating from varia.ble [c.heel:) nodes of
`,1 H
`J
`‘
`degree 1'. Note that the ra.te of the code is given in terms of }\{__:c] a.nd p(:c) as l — _0
`.
`,
`
`A 1I1e..ssa.ge passing decoder is seleet.ed. By delinition, 1nessa.ge.s only c.onta.in er:£r'13n.sr'(: inlor—
`
`mation, ie, the messa.ge emitted along a.n edge C does not depend on the incoming message
`
`along the same edge.
`
`l“urther, the decoder fulfills the following s_t;'InI11etry conditions.
`
`l“lip—
`
`ping the sign of all
`
`incoming messages at a. variable node results in a flip of the sign of all
`
`outgoing 1r1e..ssa.ge.s. The .syrri111<_!t1'y condition at a. eheel<. node is slightly more irivolved. Let
`
`C‘ be a11 edge emanating from a check node If. Then flipping the sign of i incoming messages
`
`arriving a.t node 6, excluding the messa.ge along edge 6, results in a. change of the sign of the
`
`outgoing message by [—l )i.
`
`In all these cases. only the sign is cliangerl, but the reliability
`
`remains uI1elLa.1Lge.d.
`
`Hughes, Exh. 1029, p. 3
`
`

`
`Under the above a.ssumptions there exists a threshold 6* with the following properties: For any
`
`( > U and (5 < 6* there exists an *n.((._b) such that almost every code] in C.n‘(/\,_p),_ -n, > ‘ir[(,(5)._
`
`has probability of error smaller than 6 assuming that transmission takes place over a c.hannel with
`
`parameter 6. Conversely, if the transmission takes plac.e over a channel with parameter 6 > 6*,
`
`then a.lmost any code in C.,L(/\_,,o] has probability of error uniformly bounded away from 7'.ero.2
`
`lfurther, for the important case of belief propagation decoders a procedure was introduced tha.t
`
`enables the ellicient cornputation of 6“ to any desired degree of acct11'ac_x_=.
`
`In [1] threshold values
`
`and si111ulation results were given for a Variety of noise models, but the c.lass of low-density parity-
`
`check codes c.onsidered was largely restricted to regular c.odes.
`
`In the present paper we present
`
`results indicating the remarkable performanc.e that can be achieved by properly chosen -.ir-reg-u,lm*
`
`codes.
`
`The idea underlying this paper is quite straightlorward. Assume we are interested in transmission
`
`over a partic.ular memoryless c.hannel using a particular message passing dec.oder. Since for every
`
`given pair of degree sequences ['/\._p) we can determine the resulting threshold value c‘i*_, it is natural
`
`to search for those pairs which maximize this threshold.3 This was done, with great success,
`
`in
`
`the case of erasure channels [5, 6, T]. In the case of most other channels of interest the situation is
`
`much more co111plicated and new methods must be brought to bear on the optimization problem.
`
`Fig. 2 compares the performance of the (3, 6')—regular LDPCC (which is the best regular such code)
`
`with the performance of the best irregular l,l)l’(:'l(:'l we found in our search and the performance of
`
`the standard parallel turbo code introduced by Berrou, Galvierix, and Thitimajsliima.
`
`All three
`
`codes haxre rate one—hall‘ and their per‘lo1'rna.nce under belief propaga.tion decoding over the A‘/VGNC
`
`is shown for a c.ode word length 105. Also shown is the Shannon limit and the threshold value of
`
`our best
`
`l,l)l’(:'l(:'l
`
`[_U" : 0.9718‘).
`
`l"‘rom this figure it is clear how much benefit can be derived from
`
`optimizing the degree sequences.
`
`l"‘or 71 : 'l06 and a bit error probability of "I045, our best l.l)l’C(L
`
`is only U.13dB away l'ro1n capacity. This handily beats the per‘lo1'rna.nce of tu1'bo—codes. Eve.r1 more
`
`impressive, the threshold, which indicates the performance for infinite lengths, is a mere [).[)(*5dB
`
`away from capacity.
`
`lMore precisely,
`to 1.
`
`t.he fraction of codes for which the above statement. is true converges exponentially (in :1") fast
`
`3‘»Ve Conjecture that this is actually true for every Code in C,,,[:)\, ,0).
`3\Ve rriay also optirni'.t(* degree .-aequcnees under various <:orIsl.ra.inl.~:. For cxaanple, the la.rg(*r l.he clegrecs used the
`larger the code size needs to he in order to approa.elI
`l.he predicted aayrriptollc. Therefore,
`it
`is highly desira.l)l(* to
`look for the best degree sequences with some a priori bound on the size of the degrees.
`
`Hughes, Exh. 1029, p. 4
`
`

`
`(3, 6)-regular LDPCC
`
`Threshold
`
`Turbo Code
`
`irregular LDPCC
`
`Threshold
`
`Shannon Limit
`
`10-2
`
`10-3
`
`10-4
`
`10-5
`
`10-6
`
`0.0
`
`0.2
`
`0.4
`
`0.6
`
`0.8
`
`1.0
`
`1.2
`
`1.0
`
`0.977
`
`0.955
`
`0.933
`
`0.912
`
`0.891
`
`0.871
`
`0.159
`
`0.153
`
`0.147
`
`0.142
`
`0.136
`
`0.131
`
`0.125
`
`Eb/N0 [dB]
`
`0.851 (cid:109)
`
`0.12 Pb
`
`Hughes, Exh. 1029, p. 5
`
`

`
`-1” > ‘I — i’J,(r‘.i]/h.['p"‘)._ where h,(-] is the binary entrop_v function and p’‘‘ : , then the block
`
`error p1'obabilit__v is bounded a.wa.__v lrorn 0.
`
`Proof. Note that the capacity of the BSC is equal to l —
`
`Since p* > 1/2 for any finite ((2.,
`
`we ha.ve h.(p“] < l and, hence,
`
`‘I — h,(r‘i]/h.['p"‘) < l — h.['r5_). Callager stated the above Theorem
`
`originally for (' Fi:)—1'egnlar codes. A closer look, however, shows that the p1'ool'rernains valid for
`
`the case of irregular codes if the original expression p* =
`—‘
`','
`Lt
`.
`.
`Details of the proof can be found in [9, p.
`
`* =
`
`I-l-[ I —2.5)’*'
`2
`
`is replaced by the expression
`.
`—
`‘
`.59]. We note that a slightly sharper
`
`bound can be given if we replace r.7.',. with the a.verage degree of the [' l — r]—fra.ction of highest degree
`
`nodes. However. since the irnprovernent is usually only slight and since the exact size of the gap is
`
`not signilicant in practice. we leave the details to the reader.
`
`D
`
`The outline of this paper is as follows.
`
`In Section 2 we describe and study density evolution.
`
`Under the assu111ption that the input distribution arises from a syminetric channel, we show that
`
`the message distributions satisfy a certain e0ri.si.ste-mt:-_u condition which is invariant under densitv
`
`evolution. Many siniplilications arise in this case which allord us considerable inlorrnation on the
`
`nature of density evolution.
`
`In pa.1'ticular, we show that density evolution always converges to a
`
`fixed point. ‘We also address the stability of the fixed point that corresponds to the correct solution.
`
`in Section 3 we give tables of some very good degree sequences. Although we focus mostl_v on the
`
`AW'(:lN(:,' and ra.tes one—hall._ we also give a few examples for diljrierent channels and rates.
`
`in Section
`
`3 we also p1‘ese11t some simulation results that show that the promised pe1'l'o1‘1nanc.e can be close.ly
`
`achieved for reasonably long codes. Finally, in Section =1 we describe our nun1eric.al optimization
`
`techniques which were used to generate the tables in Section 3.
`
`2 Density Evolution: Colisistency, Stability, and Fixed Points
`
`Density evolution, as described in [l], is general enough to enable the c.o1nputation of message den-
`
`sities rega.rdless of the initial densit_v.
`
`in the case of most interest, the message distribution a.rises
`
`from the observation of the input bit after passing it through a known s_vm metric channel. Since
`
`the channel is linown, the log—l_ilu_slil1oo(l [or the input bit given the ol)st_2r'vatio1i is deterrnined and
`
`this log-likelihood constitutes the received message. Message distributions [ under the ubiquitous
`
`all-one word assumption) which arise this way satisfy certain coiisisteiicy conditions that are pre-
`
`served under density evolution.
`
`In the following, we will examine these conditions. They will
`
`lead
`
`Hughes, Exh. 1029, p. 6
`
`

`
`to sirnplilications of de11sit_y cvol11tio1L.
`
`F111‘tl1e1'111r_w1‘-3, in this c.ase_, one can p1'ove a monotoniL:it_y
`
`property of density evolution which implies tha.t density evolution converges to a. fixed point. Fi-
`
`nall_\;',
`
`in this section, We study the asymptotics of correct decoding to arrive at at stabilit_\;' condition
`
`for the fixed point corresponding to zero probability of error.
`
`Let us lirst b1'i<_~.ll_v recall the lorm and de1'ivation of density cvol11tio1L for beliel p1'opagatio1L.
`
`In
`
`g«_~.ncral, cacli Iriessage 1‘ep1‘es<:nts an estimate ol a p'dI‘l.l('.11lit1‘ transmitted bit. Let 1: denote the vallie
`
`of this bit and recall that 3: is an element of :1}. At a. variable node, we will represent messages
`
`as log—li kelihood ratios,
`
`J 1
`:1: : "I
`log ML) 7
`pwW=-U
`
`where y represents all the observations coiiveyed to the variable node at tha.t time.
`
`In the sequel
`
`We will often refer to messa.ge distributions without Further qualilica.tions. Unless stated otherwise,
`
`this will always ruler‘ to rnessage distributions at \«'a1'iable Iiodcs under the a]_l—one word assumption
`
`where the messages a.re represented a.s log—lil;elihood ratios. At a. check node it is more convenient
`
`to represent the message as a. tuple (3, 1‘) where 3 E lxVg 2: {:1} indicates the hard decision and
`
`Where r E El is equal to
`
`haMw=Hw—pw=—Hwl-
`
`Here l~'14"2 denotes the two—element group with elements {:1} and group opera.tion equal to real
`
`multiplication. Since we wish to ad mit the possil.)ilit_\;' of perfect knowledge ota bit (erasu re channel],
`
`we must admit the possibility that Inessage distributions rnay l1a\-'0 point masses at the endpoints.
`
`E.g., in the log-likelihood representation this mea.ns that we may have ‘point masses at infinity’ in
`
`our message distributions. Thus, in gene1"a.l, message distributions are probability distributions on
`
`the two— point com pactification of R, which we denote |.)_\;' E. To sirwiplity the presenta.tion we shall
`
`ger1e1'a]l_y assume that distributions are absolutely continuous with 1‘espert
`
`to Leliesgtle Ineasiire
`
`and can tl1<_!1'elo1'e be rep1'ese1Lt.ed by their de.nsit.ie.s.5
`
`Assume now that the received message a.nd the incoming messages at a variable 11ode are given in
`
`log-likelihood form. The outgoing message along a11 edge if is then simply the sum of the received
`
`message plus all
`
`incoming messages, excluding the message incoming along edge 6. Therefore,
`
`5A couple of exceptions will be made for certain discrete measures. ln particular, We shall require the distribution
`.-330, the ‘delta, function at i11fi11it_v.’
`\Ve shall also require the distributioli Au the ‘delta, function at zerof Corresponding
`lU ELII
`[‘I'dH|.I IT‘.
`
`..‘]
`
`Hughes, Exh. 1029, p. 7
`
`

`
`assuming independence (tree assuinption), the dc-ns-ity of the outgoing iiiessztge is the convolution
`
`of the densities of the messages participating in this sum.
`
`An equivalent statement is true at the check nodes. Assume that the incoming messages to a.
`
`check node are all in the l'o1‘1n .5-*,_
`
`The otitgoing II1t_sssa.gt_s [agaili in [3, I‘) 1~ep1‘esentattion) along
`
`an edge (3 is then siinpiy the sum of all incoming messages, exciudiiig; the iiiessage incoming along
`
`edge e (here “addition” is perforined cornponentwise, i.e., (5.,-rt) —|— (S2._'T’3) : (5.
`
`=i= 52.1‘. + ‘r-3),
`
`where the first component is in lr"l/2 : {:1} and “addition” corresponds to real multiplication,
`
`and the second eoniponent is an elernent of R with 1't_sg111a.1‘ addition.) Thus, as in the. previous
`
`case, the density of the otitgoing Inessage, over W-"2 X Kl’, ezui be written as the. eonvolution of the
`
`corresponding densities of the incoming; iiiessages. Here, R+ refers to [(1, 00] the c.o1iipac.tific.zttion of
`
`IRJ’. To complete the description we need only specify the change of Variables necessa.ry to convert
`
`at density from one 1'ep1‘esentation to the other and to incorporate the. de.gree. sequences.
`
`Suppose that we lLd.\’L‘ a. gI‘a.p11 with left and right edge dt_~.g1ee distribtitions given by A[;i=] =
`
`i:l
`Edi‘
`
`i:l
`,\y;g’’ ', and ,0(;2:') : Ed“ pl;-33'3", respectively. We follow [3] and use the following; convention:
`—1
`
`for at polynoinial qfrc] : Z1. q,;:c"i
`
`with read coefficients q,; we denote by q(_f] the distribution
`
`:31-r,r.i-‘f'75‘l"A‘1l._ where here and in the sequel tit» denotes convolution.
`
`[n the following, we a.ssurne tha.t the channel satisfies the symmetry condition [_'I ].
`
`liiurther, we
`
`assuine that the atH—o11e codeword was transinitted. Let PU be the distribution of the 1'e.eeived
`
`1og—1ike1ihoods and Pg denote the distribution of 1og—1ike1ihoods sent from the V€t1‘iE1b1€
`
`nodes to the
`
`check nodes in the 6th iteration. Let Rg denote the distribution of 1og—1ike1ihoods sent from the
`
`checlc nodes to the variable nodes in the fith iteration. We may initialize with R0 : A0.
`
`The distribution of messages passed [rorn at message node to a. check node in the 5th ite1'a.tion is
`
`given by the convolution Pg :: PD (59 z\('R,g,1).
`
`To obtain the distribution of niessages from check nodes back to message nodes, We 111ust perforin
`
`E1 cliaiige of measure. To this end we define the operator 7 which takes the space of distributions
`
`on RJ“ into itself. For densities on RJ“ we define -7' as
`
`V y 2 0:
`
`:: f[lneothy/2) eschly).
`
`The operator 1: represents a, change of va.ria,|J|es y —-
`ln coth -yr/22, i.e., f(y] dy : *_:['f)['-*_y) dy, since
`fil; ln cotli-y/22 : —csch['-y). (We can extend the definition of 1: to distributions on RJ“ by taking
`
`on
`
`Hughes, Exh. 1029, p. 8
`
`

`
`limits.) This shows part (a._) of the following le1'1'1II1ZL, while part ('b_) follows easily from the fact that
`
`ln coth Pin6013211 W2) : 31.
`
`Lennna 1.
`
`'/‘he: fr)Ho7ivin.gfnr?t3 h.0."ni:
`
`ta) ,{;;]°“1«*{.f){;r1) dy : .ii;i° fly) (1.7;
`
`(13) *1-'(1«"(f.)_){:y]= f(*y).
`
`For any distribution
`
`on R let f’ denote 'l[_m,0]
`
`and let f+ denote 'l£0=x]]
`
`where 'l_,~1 denotes
`
`the L?l1i{i1'E.’bf.?|.I'_‘.1'_lSLl|J
`
`l11I1c.tio1L of 51 so tllatt
`
`= fl’ + j"".5
`
`Giveri a dist1'ib11Lio11 f o\:c1' R oflog—lil«:elihoods Z, we catrl 1‘(_‘p1‘(_‘S(_‘.I1|. it as it distriblitiori over 14-’; X R4’
`
`by represeiiting I as the pair (5, 7-]. ‘We therefore define F, the clizuige of variable operator, by
`
`T'('f]('-Sm) = 1[1}('-9h'('f+_)(r) + l{_1;}('—sh'("Rf”_)(r)-
`
`where Rf’ denotes the reflection off about U, i.e., 'Rf’{:c] : f’('—a:_).
`
`Now, let g be a. distribution over 141-"'2 >< RJK Let _q+ and ‘gr’ he defined by g+('7'_] : 'l{,}('.€s)g('.ei,7‘_] and
`
`_q‘(T) : 'l;l,1}[.-;)_r;[.-a, T‘). ’I"hen the inverse of 1‘
`
`is given by
`
`1”'mJUJ:~Hq+)U)+7%fly‘MfL
`
`Using this notation, we obtain the following.
`
`Theorem 2 (Density Evolution). Lei’. PU dt-‘n.r,u'.(-.
`
`[lat-.
`
`iiraitiiaf 'r'n.e.:-sagt-‘ ali3.:-£r'ibu£i(:'r'L, undt-.'r' the as-
`
`sumption that the all—0n.c~ Code-word was tmnsmfitcdfl, of (.5. l0w—dc-n.s-ity pm-eTty chc-ck code specified by
`
`edge (iifiQ‘T‘E*E d*a',s't7’ib~a:.ta'::un..-a Z1. /\4L-;r‘i‘1 and Z1. pt-;I:‘i‘1. If Iii-5 rfenrate.-a the riemaity of the n1.e.-;3rr,qe3 pr.'5.-am’
`
`from [.h(-.
`
`(:h(-ml.‘ ‘H0(Il(-‘é~‘ {.0 the ‘n’l’t(-‘é~‘-5'Llg('. nodt-..5'
`
`(LI. roimd [5 of the belt}-.f-prc:pagr.L£i'0i'i.,
`
`irritfa RU :: AU, HL(-‘."l-
`
`we r’i.Lm(-.
`
`2.1 Consistency
`
`m=r*mHe@MRemy
`
`In the following, we call a distribution
`
`on R c0n.an:'.a?tent if it mtisfies f[:}:'] : f(—;I:)e“‘ for all
`
`:1: E ]l_R+. Mo1'e lo1'mztll_y, at piobability 111<3as111'L~ U is coiisisteiit il' the l'ollowi11g hold. First, I} tan
`
`5111 the ge11e1'a,l case. Where a point 1113.55 at U is allowed, the 111a,:3:3 at U should be split equally between f‘ and f'''.
`
`CO
`
`Hughes, Exh. 1029, p. 9
`
`

`
`be written as 1/‘ + 11+ where I/_ is supported on [—oc,0] and 12+ is supported on [0,
`
`Letting
`
`‘R1/— LlL‘.I10L(_‘ as bo1‘1_m~. Lhc 1'cllec.tio1L of 1/‘ abotit 0, we rc.q11irc. Lllat ‘R1/— be absoltitcly conLinuous
`
`with respect to 12+ and that the R.ad0n—Nil~:odyn derivative [10, p. 180] of “RIF with respect 12+ be
`
`given by e"'. If 12 has a density f then consistency of 1/ is equivalent to coiisisteiicy of f as defined
`
`above. Note that Am and A.) are consistent mea.suI'es.
`
`‘We will first establish consistency of the initial message distI'i|)ution of density evolution under
`
`geri-'c1‘al conditions.
`
`Proposition 1.
`
`,Si11.p;1Jr).se
`
`14‘/m.t
`
`rt 1?/1.r1.7mr~?[1‘1rts
`
`.s;1;n1.71'1.r~?tr_7; p7‘o;:1r»?1‘1Ty My |
`
`:1: : 'l_] : p('—y |
`
`:1: : —'l ),
`
`L1-‘rad I-19.1". PU be (1%.
`
`i1'1.1?l-irll 1'1'1.(<.s.srLge
`
`rl17.s£r‘1Cb1L£17ca1'1.
`
`1311 Zrag-l17Lvc<Zif1.(1r_1d n:1£13r_1 fr_1'r'm u1'1d::<'r' Hat:
`
`all-r_rr'1c«:
`
`tirord
`
`assrmzption. Then P0 is consistent.
`
`Proof. Let 12 denote the measure corresponding to P0, i.e., for any measurable subset A, 1/('A_) ::
`
`Pg(;1:_) drc. Note that P0 is equal to the distribution of the random variable
`
`:3
`
`lg‘)
`
`p(*y|»”6 = 1)
`::l 2;
`0‘ p(y|-‘F = ~1)
`
`('3)
`
`under the assumption that the all-one codeword was transmitted. For any measurable set A we
`
`Iiave .!2('.4_] :
`
`(A) p('y|.'17 : '1) dy. Invoking channel symrnetry and equation
`
`We Iiave
`
`1/(—A')
`
`-»:--lr_—A)
`
`so (A)
`
`ptylw = 1) C111
`Pl_—;i1'|1' = 1') dy
`p(-_y|:1: : -1) (ll).
`e""“p(:y|$ = 1) dy-
`
`]
`]
`/ 7
`]
`
`-z‘i{-4)
`
`(A)
`
`Thus, we obtain that 1/ is a consistent nleasure, i.e., setting A = [2, 2 + dz) we obta.in
`
`1/[-5 — d;, —z')
`
`=e
`
`1x(/:, 2 + dz)
`
`D
`
`Example 1 (Erasure Channel). For the erasure cllannel the initia.l message distribution is 630+
`
`['1 — F)A;x.. Then
`
`: EAC. + (l — t-?)£*~.,x and P6 : §A0,w'|1ich shows that the initial distribution
`
`is L'DI1SlSl.(,‘.I1l .
`
`10
`
`Hughes, Exh. 1029, p. 10
`
`

`
`Exarnple 2 (BSC). For the BSC the lllltlitl Iiiessage. distribution is PU[:z=) :: r§it._10g1-.s -|- (1 —
`
`6]Ah_’gfi. W’e11£we 130+ = (1 — c5]A]_
`1-4
`6
`ug b
`
`iv
`and P0‘ = 6Ah__U 1_o , so consistency is apparent.
`
`Example 3 (AWGNC). Here the initial message distribution is I’0(;r) ::
`
`“Z ‘\
`
`c0nsistenc_V condition is then
`
`[I—%:I2a2
`0.2
`,' _ T -49% _
`_.
`Pg(.1—)—
`Rfie
`8
`—
`
`—
`
`0.2
`,1
`Rflre
`
`
`I_'—:c——3gj£c£
`8
`
`.1" _
`e —P0{__
`
`_ ,'
`:L—)e
`
`.1"
`
`.
`
`Example 4 (Laplace Channel). As a final e:-iainple,
`
`the initial
`
`inessage distribution for the
`
`I.-aplace channel is given by
`
`PD(:z:') :
`
`LA
`
`where
`
`Again, it is easy to check that the consistency condition is 1°11 lfilled.
`
`VV-'3 say that two ('.lL‘¢tILI1L‘.lS are c:qiLi7:rrzlc~:J'z.£ if tl1e._y l1zwe the same initial message dist1'ib11Li0n.
`
`It is
`
`often coiivenient to pick one representative for each equivalence class. How this can be done is
`
`s h OW n i n
`
`Lemma 2. Let Pgf-y] be 2L consistent distribution. Then the syrnnietric Cllitllflel p('-|-] with p(7y|:c :
`
`1) = Pg(y) (and hence by syiiiiiietry p(7y|:c : —l_) = Pg(—y_)_) has initial message distribution Pg(y).
`
`Proof.
`
`, MM$=H
`lot?»
`'Mmx=—U
`
`: I0
`
`INN
`pWW:L):,
`————:|
`g——————
`‘rt/yh¢=lU 0g1%(—y)
`
`Pally]
`0% —PU(y)C_y
`
`: y.
`
`D
`
`0111‘ I1L‘.}it goal is to show LlLa,t L:011sisLe11c._y is p1'<_s.se.1'w_ed under density (_‘.\«'0l11ti0IL. This leatds to LiL‘.1‘t€tlIL
`
`si1np]ifica.tions of its representzttion.
`
`Lemma 3.
`
`disl-'r'i7b'u-l-i0ra-
`
`mrc~:r R 23.5:
`
`:c:r_:'r'Lsis'l.u:<'r'¢£
`
`and only *7[‘}?,j")('_L,I) = t.a11lL(y/2)'}'(f+)(y).
`
`ll
`
`Hughes, Exh. 1029, p. 11
`
`

`
`Pmri We li ave
`
`and
`
`*.=("R.f’_)(:u_) = .f”{'— In cothiii/9.)_) C-°=<‘-li(y}
`
`“_r[f+_)(y_] = f+(111 cothiy/2)) c.sch(;y__].
`
`N()tc Lhal [r0111
`
`: f(:i:_)<)""‘ it follows Lilitl
`
`-‘i‘(’R.f‘J(yi = 97~'P(—l"C"'“l‘(;U/2llf+(l|1C0tl1l1U/2_)_)Cficlilivl = T-anhm/9.)-i‘(.f”_)(:r,i_).
`
`and the lemma follows directly.
`
`Thus, We 111a§J extend the definition of CO11SiSte11C.fv' to densities over irVg >< RF“.
`
`Lemma 4. Consistency is invaricmt under coiwoliition in R and coiwoliition in T-“V2 >< R4’.
`
`Proof. Let f and g be C(,)I1SiSl(,!I1[ d(,‘,I1Sili(,‘,S 0\»'e1'
`
`Then
`
`fail fit!-' - y)y('y) dy
`
`’X'.I
`
`— ’X'.I
`
`foo v’”"”J'[y - :ir_)<:*"y('-ii) dy
`e‘‘f(:y / »T_.i9( /3!) dz;
`.fi--Mr - ii).r;i[i;) ‘lil-
`
`: GI
`
`To Show that CO11SiSte11C._\;’ is i11V€l.I'iE1I1t under convcihzitioii over I-‘V2 >< RJ“ is SO111€Wh€Lt more elaborate.
`
`Let
`
`and g‘ be coiisisteiit densities 0Vei'
`
`l"l"’2 X R“ and let us F£Xp|‘F£SS them as
`
`flfifll : 'lii}(5lf"(?‘]+'li_i}l.-*)f_("’)
`ll
`
`V
`
`1i1}(é?J£i+l"i + 1{—1}(é=')£i—(”'i~.
`
`Cr:
`
`-..
`
`Q .—.
`
`(Where
`
`: 'l1u.}[_.-;)‘f[_.-L, 7""), etc.) and let us Slmll.’-ll'l_'y' express
`
`iii» g. "I‘l1i=en the convolution of
`
`d.ILd g is S1J(_‘.L'ill.L‘Ll_ by
`
`if -:3.>.r;}“ + (f :3: gr : U” + f") -:32 (.r/‘ +9")
`51
`(I -39 9)” ~ if 2?: 9)‘ W — I”) -:1 (sf — sf).
`
`.\'ow,_ the cr_w11sisLi_211c.y conditioii for at (liSL1'ii)11liL)IL
`
`o\»'c:1'
`
`ii?’-3 >< El‘ C.‘d.IL be (_‘_3ip1‘(_‘.'~_‘..'~_‘.t_‘.d as
`
`{..f+ - f’)[_i/) = 9'y(.f+ + .f’){_i;)-
`
`'l"hu.~3._ it is easily V(3,I'i1Cie(l tlia.t
`
`0}.)
`
`Ir] is coiisisteiit.
`
`12
`
`Hughes, Exh. 1029, p. 12
`
`

`
`In Vl(_‘.W of Lhe above it is L‘.OI1\-'(_‘.I1l(_‘.I1|. to inLrod11ce tlw “l0ld"’ 0pe1'aL01‘ .7: which Latkes distriblitiolis
`
`on R to distrihutioiis on R+. ‘Ne define it by
`
`.Ff(:r) : .f+m + 7?.f‘(:r) : .f+(':r) + .f‘(—:r)—
`
`Altr)gL\tl1e1', we obtain the l'0l_l0wing.
`
`Theorem 3 (Density Evolution and Consistency).
`
`l.et 1”.) denote the ?'n.i'tiri.t rii.e.-;.m_r;e c."i3tr‘i'-
`
`hu{i7oi'z. of L1.
`
`lr_rw—dc:'r1é='i£y pa-'r'i7t-y crhecrk creidt:
`
`.,s=pec:i3]i7ed- by edge degree: diT.s{.r‘ibu£i7oits Z1-/\1;:z:i"
`
`L1-ml
`
`Zip,;3:’*' and assume that Pg
`
`eons-is-tent.
`
`If R; denotes the dern32'ty of the messages passed
`
`from the check nodes to the nzessage: nodes at round E of the behfef—pr0pa.gation then we have
`
`R-.2 = £7" 0 "r)r*(("r 0 5F)(Pu 61' z\(R-e_1)_)).
`
`and P5 is consistent for all 6 2 0.
`
`Example 5 (Erasure Channel). Let. f l)L‘. a Llelisity dieL1'ih11Lio11 ol'Ll1e [‘o1'II1 (A0 + (1 — (JA-:30-
`
`Then JF(f_) : f, and 1:'{f_) = {l — e_)Ag + €3.30. Furtlier, ,\('f] : ,\{e_)Ag —|— (1 — A(e_)_)£«.,xn,. Hence,
`
`starting with the initial message distribution EA.) -|- ("I — e_]L~.m corresponding to an erasure channel
`
`with G|'P].SlJ re pI'oha.hi|ity F, the iteraition is given by Ijf : ff-9_(1'A.0 + ("'1 — p{_«_]L~.w, where
`
`Pr = .0(l * EH1 ”PI:’—I ))-
`
`Thie is the same formula as derived in [5, 6].
`
`Let fat] be a. c:011siste11t distribution. We define the error p1"oba.bi]ity operator zLs7
`
`P1'm[f') ::
`
`.0
`— 1.1,
`
`dxz:
`
`.
`
`A11 easy but helpful c:011seq11e11ce of the eoilsisteilcy conditioil is noted in the following
`
`Corollary 1. Let
`
`he a coiisisteiit distribution.
`
`ll" P1'm[j") : 0 [lien f : £x.,,O.
`
`Hence, requiring that the pr0|.)a,|.)i|ity of error converges to zero is equivalent to requiring that the
`
`message den.<,it_\;' converges to a delta, function at infinity.
`
`llf f l1a,s a point. 1113.55 at U the11 EXa.Cl-l_V half of that 111a,ss is i11cluclecl
`
`i11 Prm-1-(f).
`
`13
`
`Hughes, Exh. 1029, p. 13
`
`

`
`2.2 Fixed Points of Density Evolution
`
`In the case of the erasure channel and a belief propagation decoder the state of the system at
`
`any iteration is described by the remaining number of erasures. Denote the remaining number of
`
`erasures by :2: and let h.[':2:] be the remaining number of erasures after a further iteration. "l‘hen the
`
`threshold is given by the rnatximum number 1:0 such that
`
`V0 < :9 < 9:0 :
`
`h.(:c) <
`
`[-"1__]
`
`A similar statement is true for the DSC together with Gallagofs decoding algorithm A. In this case
`
`:1: signifies the remaining number ol'o1'1'o1's.
`
`An alternative description of the threshold can be given in terms of fixed points. The threshold is
`
`given by the maximum number 3:.) such that for no :2: E (0, ;.r:.j.)
`
`h(';r:) : :1:
`
`.
`
`Assume now we are given a general discrete memoryless channel which fulfills the channel symmetry
`
`conditions and we employ a belief propagation decoder. The state of the s_ystem is now described
`
`by the message density.
`
`l.et
`
`denote such a density and let h.(f] denote the corresponding density
`
`after a fu1'th<:1' iteration. Cl<:ar'ly,_ l.l1(_‘.I‘L‘ is no characterization of the threshold which corrcsporids
`
`to [ :1] since there is, a priori, no given linear ordering of densities. The alternative formulation in
`
`(5') involving fixed points looks more promising. Unfortunately, the nonexistence of fixed-points
`
`for iterated function systems in more than one dimension is in genera.l not enough to guara.ntee
`
`co11\re1'gc1Lcc:. So it is quite surprising that for rncssagc distributions of bcl_i<:l' pr‘opa.gatio1L docodo1's
`
`llxcrl points stifllciently C.lLd.1‘dL(‘.l.L‘1‘lZ,(_‘. the L'()11\’L‘1‘g'(_‘,I1C.L‘ of the soqrioiiccs, as we will show in this section.
`
`Let Pg(;2:') denote the distribution of the messages at the .€—th
`
`iteration assuming that the all—one
`
`word was transmitted. Assume that we were to decide on the transmitted bit according to the sign
`
`of the message.
`
`in this case the conditiona.l error probability, conditioned on the tra.nsmission of
`
`the al_l—on<: coclcwornl. is equal to P1‘m(P[). But. l)L‘C'<i1.1S(_‘. of the syrn1I1otr'y conditions. this is equal
`
`to the unconditional error probability. Since the sign of the message is equal to the MAP estimate,
`
`this error probability is clearly a non—increasing function of .6.
`
`This monotonicity property will play a. key role in the sequel.
`
`It
`
`is not hard to see that there is
`
`actually a Whole family of such monotonicity conditions.
`
`"I4
`
`Hughes, Exh. 1029, p. 14
`
`

`
`Theorem 4. Let Pg be (M. mc~:s-.sa-gt dt.s£I'ibu£tr_rr'¢ at (1%: 51'-Us cie:c:c:ctiJ'z.g .5-tap (ind let g be a :c:r_rr'Lsist.c<'r'¢£
`
`distribution on R. Then
`
`is G n-m'z.—tn.:c:re:a5in.g f'uJ'z.c*{io1'z. of (5.
`
`P I-erri
`
`J’? ('3'
`
`Pmof. The message of which
`
`’{_«
`
`is the distribution represents a conditional pI'oha.hi|ity of a. par—
`
`|.i('.1_1l&t1‘ bit \«'a111e. Ass11111<_~. Lhat an i1Ldep<_~.11Ll<:1L1. obse1'vaLio11 of Lhe satiric bit \«'&{111L‘. is €L\«'£{il€Ll)l(_‘
`
`to Lhe
`
`decoder and 2LSS11111€
`
`that this independent observation is obtained by passing the bit tlirougli a
`
`cha.1111el p('-|-] wliicli fulfills the synirrietry condition and has p(y|3: : l_) : g(y_). By Lemma 2 and
`
`under the a.ssumption that the a||—one codeword was transmitted, the conditional (JistI'ihution of
`
`Lho bit Vdllle log—lil«:elilLood, L‘0I1f.iiLi0IL(_‘f.i on all lILl01‘I[L€Ll.l(_‘:I1
`
`i11L:o1‘poraitt:Ll in Pg and the ilidependelit.
`
`observa.ti011, has distribution B; 65;: g. Since the new distribution corresponds aga.i11 to a. MAP esti-
`
`mate conditioned on i11f01‘II12L13i011 which is 11o11—decre2Lsi11g in E, the stated monotoriicity condition
`
`Fol lows.
`
`It is convenient to use the following ""basis" for all these monotonicity conditions. Let
`/3‘
`
`t.
`
`1
`
`g__._,[:z't) := _l +e?A_3 + _l .
`
`3
`
`3
`
`(6)
`
`C|ea.r|y,g:[:1:'] is a consistent (Jistribution. For any consistent distribution f let ‘I-‘sf be defined as
`
`IF’?! :: Pllerrijl
`
`VVritte11 in an aLlte1‘I1a.tiVe way we llave
`
`l
`
`2: 1 + 02
`
`(13: f(;r)(_’l + e\»c) +
`
`(J3: f(.'i7)(a_\31‘ : lit‘: (1 _ '/3°C“ — (:5'~’\a: )f(.;L,) (M) I
`
`(7)
`
`Corollary 2. Let Pg be the ma:-8.5-age distributioit at the €-th
`
`deeorling step. Then ‘PER:
`
`a non-
`
`in.r:7’£r.'s'in_qfimetion of f for mrery 0 § 2 g oo.
`
`Lemma 5 (Basis Le1111na.). Let f and g be consistent dis-tmTbti—ti0n—s such that ‘F-fig = ‘P3 f, V: 2 U.
`
`"Ii/WI}.
`
`: 9'.
`
`Proof. ‘Write the COI1ClltlO11S ’Pz(f(a:) — g{__ 13]] = 0, V2 2 (1, in the equivalent form
`
`V: > 0:
`
`/OC[f[;}:']—‘q[:1:']'](il—ez’”’)d;r : O.
`
`15
`
`Hughes, Exh. 1029, p. 15
`
`

`
`Di[lb1‘c:11LiaLi11g both sides with 1‘(JSpL‘CL