Practical Loss-Resilient Codes
`
`:\:Iichad Luby*
`
`l'vlicha.el MiLzenmachert
`
`Amin Shokrolla.hi+
`
`Daniel Spielman§
`
`Volker Stemann,
`
`Ahstrad
`
`\Ve present a randomized construction of linear-time encodablc and decodablc codes
`LhaL can Lran:;miL over lm;:;y channel:; a.L raLe::; exLremely do:;e Lo ca.pa.cily. The encoding
`and decoding algorithms for these codes have fast and simple software implementations.
`Partial implPmPntations of our algorithms arP fastPr by ordPrs of magnitudP than thP
`be~L ~oft.wa.re implemenLaLiom of a.ny previou~ a.lgoriLluu for Lhi:; problem. \Ve expecl
`these codes will be extremely useful for applications such as real-time audio and video
`Lra.n::;mi:;~ion over Lhe InLernel, where lo:;~y channel:; a.re common anJ fasL decoding i:;
`a requirernent.
`DPspitP thP simplicity of tlw algorithms, thPir dPsign and analysis arP mathPmati(cid:173)
`cally inLrica.Le . The Je::;ign require:; Lhe careful choice of a. random irregular biparliLe
`graph, where the structure of the irregular graph is extremely important. \Ve model the
`progre::;:; of Lhe decoding a.lgoriLluu by a. ~el of JifferenLial eq ua.Lion:;. The :;oluLion Lo
`these equations can then be expressed as polynomials in one variable with coefficients
`dPtPrminPd by t hP graph strmtmP. Ha.<iPd on tlwsP polynomials, >YP dPsign a graph
`~Lruct.ure Lha.L guaranLee~ ~ucce~::;ful decoding wiLh high probabiliLy.
`
`*international Computer ::>cience institute, lJerkeley, C~alifornia. Portions of this research done while
`at Digital Equipment Corporation, Systems Research Center, Palo Alto, CA. ltesearch supported in part
`by National Science Foundation operating grant NCR-941Gl01, and l"nited States-Israel Binational Science
`F'ou ndal.ion gra.nl. No. 92-00226.
`tDigital Equipment Corporation, Systems Re;;earch Center, Palo Alto, CA. A substantial portion of
`this re;;earch done while at the Computer Science Department, UC Berkeley, under the ~ ational Science
`F'ou nd a I. ion gra.nl. No. CCR-950.~448.
`!International Computer Science In;;titute Berkeley, and Institut fiir Informatik der l" niversitiit Bonn,
`Germ <til)'. Rc~ca.rcll ~11pporl.cd by a. H a.bilital.ionssl.ipcndi IJ rTI or lllc Dell t~cllc forsdlu ug~gemci IIsch a.rt. Graul
`Sl1 57/ I I.
`sDepartment of Mathematics, .lvl.I.T. Supported by an NSF mathematical sciences po;;tdoc. A substantial
`portion or tl1is re~ca.rcli done while vi~itiug U.C. Berkeley.
`11Research done while at the International Computer Science Institute.
`
`Hughes, Exh. 1028, p. 1
`
`

`

`1
`
`Introduction
`
`In man.y corrm1m1icalion silualions, data is lost. in transit.. A standard response to this
`problem is to request retransmission of data. that is not received. When some of this
`retransmission is lost, another request is made, and so on. Sur,h u>rnmunir,ation protor,ols
`can lead to delays due to the need for several rounds of communication bet>veen sender and
`receiver.
`An alternat.i vc solu t.ion, ol'lcn called fonuanl er"ror·-cmTtclion in lhe net working lilcr(cid:173)
`ature, is sometimes desirable: Suppose an application sends a. real-time stream of data.
`symbols that is partitioned and transmitted in logical units of blor,ks.1 Furthermore, sup(cid:173)
`pose the network experiences transient and unpredictable losses of a.t most a p fraction of
`symbols out of each block. The folluwing insurance policy can be used to tradeoff the effects
`of such uncontrollable losses on lhe recei vcr fm cont.rolla.bk degradation in qualit..y. Suppose
`originally a. parlicula.r block consists of n data symbols. Inslcad of sending a message of n
`data symbols, send a. message of only (I - p)n data. symbols, by either selecting the most
`important pMts from the original data. stream and omitting the rema.i nder, or by generating
`a slightly lo-wer quality stream at a. ( 1- p) fraction of the original rate. Fill out the block to
`its original length of n >vith pn redundant (check) symbols. This scheme provides optimal
`loss prolcct.ion if the (1- p}n symbols in the message can all be recovered from any set of
`(I- p)n rer,eived symbols from the block. Such a. scheme can be used a.s the ba.sir, building
`blor,k for the more robust and general protection scheme desnibed in [l].
`The problem is to design fast enough encoding and decoding algorithms to make this
`solution feasible. In this paper, >ve present codes that can be encoded and decoded in linear
`lime while providing ncar oplimalloss protection. }foreover, these linear lime algorilhms
`can be implemented lo run very quickly in sol'l 'Narc.
`Our results hold whether each symbol is a single bit or a. pad:et of many bits. We
`a.ssume that the rer,eiver knows the position of each received symbol within the strea.m of
`all encoding symbols. This is appropriate for the Internet, where packets are indexed. \Ve
`adopt as our model of losses the erasure channel, introduced by Elias [fi], in which each
`encoding s.ymbol is losl >vith a Iixed consla.nt probabilit.,'l' pin transit indepcndenl of all lhe
`other symbols. This a.ssu m ption is not a.ppropria,te for the Internet, >vhere losses r,a.n be
`highly wrrelated and bursty. Hmvever, losses on the Internet in general Me not sensitive to
`the actual contents of each packet, and thus if >ve place the encoding into the packets in a
`random order then the independent loss assumption is valid.
`Elias [6] showed that. lhe capacity of the erasure channel is 1 - p and lhal a random
`linear code can be used to t.ransmil over lhe erasure channel at any rate R < 1 - p. This
`means tha,t a. random linear code r,a.n be used to convert a. message of length /ln into a
`transmission of length n from which the message r,a.n be recovered from most portions of
`length greater than Rn. }foreover, every linear code has quadratic time encoding algorithms
`and cubic time decoding algorithms. One cannot hope for better information recovery, but
`
`1 :\n example of l.l1i~ i~ iUI IVTPEG stream, wl1crc a gmup of pid m·c8 <:<UI consl.iLuLc such a. block. and
`where each symbol corresponds t.o the contents of one packet in the block. The latency incurred by the
`application is proportional t.o the time it. takes between when the first and last. packet of the block is sent.,
`plus the one-way travel time through the network.
`
`1
`
`Hughes, Exh. 1028, p. 2
`
`

`

`faster encoding and decoding times <uc dcsira.bk, especially fm real- time a.pplications.
`Reed-Solomon codes can be used to t.ransmil al Lhc capacily of the erasure channel with
`mder n log n enwdi ng time ;:wd quadratic dewdi ng time. These codes have rer,ently been
`customir,ed to u>rn pen sate for Internet pad:et loss in real-time transmission of moderate(cid:173)
`quality video [ 1]. Even this optimized implementation required the use of dedicated worksta(cid:173)
`tions. Transmission of significantly higher quality video requires faster coding algorithms.
`In Lhcory, il is possible lo decode Reed-Solomon codes in time O(n log2 n log log n) (sec,
`[4, Chapter 11.7] and [9, p. 369]). However, for small values of n, quadratic time algorithms
`axe faster than the fast algorithms for the !teed-Solomon based wdes, and for larger values
`of n the O(log:! n log log n) multiplicative overhead in the running time of the fast algorithms
`('vith a moderate sized constant hidden by the big-Oh notation) is large, i.e., in the hundreds
`or largn.
`\Vc oblain vcr_y fasllincar-limc algmit.hms b_y transmitting just bdow channel capacit._y.
`We prod ur,e rate U = 1-p(l +f) wdes along \Vith dewdi ng algorithms that rewver from the
`random loss of a p frar,tion oft he transmitted symbols in time proportional ton ln(I/F), with
`high probability. They can also be encoded in time proportional to n ln( 1/~.:). In Section 7,
`\Ve do this for all E > 0. The fastest previously known encoding and decoding algorithms
`[2] with such a, pcrfonnancc guarantee ha vc run times proportional to n ln( 1/ c)/ c (Sec also
`[:J] for related work.)
`The overall strudu re of our codes are related to wdes introduced in [12] for error(cid:173)
`correction.
`\Ve explain the general construction along ·with the encoding and decoding
`algorithms in Section 2.
`Our encoding and decoding algorilhms arc almost symmetrical. Dolh arc extremely
`simple, computing cxacll_y one XOR operation fm each edge in a, randomly chosen bipar"lilc
`graph. As in many similar a.pplir,ations, the graph is dosen to be sparse, which immediately
`implies that the encoding and decoding algorithms are fast. Unlike many similar applica(cid:173)
`tions, the graph is not regular; instead it is quite irregular with a carefully chosen degree
`sequence. \Ve describe the decoding algorithm as a process on the graph in Section :·L Our
`main tool is a model that. characterizes almosl exactly Lhc pcrfonnancc of Lhc decoding
`algorithm a.s a function of the degree sequence of the gra.ph.
`In Ser,tion 4, we use this
`tool to model the progress of the decoding algorithm by a set of diiferential equations. As
`shuwn in Lemma 1, the solution to these equations can then be expressed as polynomials in
`one variable with coefficients determined by the degree sequence. The positivity of one of
`lhcsc polynomials on the interval (0, 1] with res peel to a paramcln b gua,rant.ccs Lhal, with
`high probability, lhc decoding algmit.hm can recover almost. all lhc message symbols from
`a. loss of up to a 8 fraction of the encoding symbols. The wmplete sucr,ess of the dewding
`algorithm can then be demonstrated by wmbinatorial arguments such as Lemma :3.
`Our analytical tools allow us to almost exactly characterize the performance of the
`decoding algorithm for any given degree sequence. Using these tools, \Ve analyze regular
`graphs in Section 6, and conclude that. they cannot. yidd codes that arc dose lo optimal.
`Henr,e irregular graphs are a ner,essary component of our design.
`Not only do our tools allow us to analyr,e a given degree sequence, but they also help
`us to design good irregular degree sequences. In Section 7 >ve describe, given a parameter
`
`2
`
`Hughes, Exh. 1028, p. 3
`
`

`

`( > 0, a degree sequence fm which lhe decoding is successful >vith high probability fm a loss
`fraclion b that is within ( of 1 - R. Although lhese graphs arc irregular, with some nodes
`of degree l/f, the average degree of each nodes is only ln(l/F). This is the main result of
`the p<tper, i.e., a code with encoding ;:wd decoding times proportional to ln(l/F) that can
`recover from a loss fraction that is >vithin E of optimal.
`In Section 9, we sho>v how linear programming techniques can be used to find good
`degree sequences fm the nodes on the righl given a degree sequence for the lcl'l nodes. \\-'e
`demonstrate thef>e techniques by -finding the right degree sequences that are optimal for a
`series of exam pie left degree seq uencef>.
`
`1.1 Terminology
`
`The bloek length of a. code is the number of symbols in the transmission. In a systemo.tie
`code, the transmitted symbols can be divided into mfsso.ge symbols and dzfr:k symbols. We
`take the symbols to be elements of GF(2), and all arithmetic operations to be over this field;
`i.e., addition is equivalent to taking the exclusive-or of two elements. The message symbols
`can be chosen fredy, and the check symbols arc compuled from lhe message symbols. The
`T-ale of a code is lhe ratio of the number of message symbols to lhe block length. Fm
`example, in a, code of block length n and rate /l, the encoder takef> a.f> input /ln message
`symbols and produces n symbols to be transmitted. In all of our conf>tructions, we a.sf>ume
`that the symbols are bits. It is easy to extend our constructions to >vork ·with symbols that
`arc packets of bils: where we would lale the surn of two bits, jusl take the bit-wise sum of
`l wo packets.
`
`2 The Codes
`
`In this section, we explain the overall construction, as well as the encoding and decoding
`algorithms. We begin by defining a code C(B) >vith n message bits and ;Jn check bits,
`by associating these bits ·with a bipartite graph B. The graph B has n left nodes and
`/in right nodes, cmTesponding to the message bits and lhe check bits, respedivd.y. The
`encoding conf>if>tf> of computing each check bit a.f> the sum of the bits of its neighborf> in H
`(see Figure l(a)l. Thus, the encoding time is propmtiona.l to the number of edges in H.
`The main contribution of our >vork is the design and analysis of the bipartite graph B
`so that the repetition of the following simplistic decoding operation recovers all the missing
`message bits.
`
`If one knows the value of a check bit and all but one of the message
`bits on which it depends,
`Then the value of the missing message bit can be found by computing
`the sum of the check bit and its known message bits.
`
`See Figure l(b) for an example of this operation. The advantage of relying solely on this
`recovery operation is that the total decoding time is (at most) proportional to the mnnber
`of edges in the graph. Our main technical innovation is in the design of sparse random
`
`Hughes, Exh. 1028, p. 4
`
`

`

`x1
`x2
`x2
`
`1c +
`
`x +1
`
`1c
`
`computes the sum
`modulo 2 of its
`neighbors
`1c
`
`ccc
`
`2 3
`
`(cid:96)n
`
`check
`bits
`
`message
`bits
`
`(a)
`
`(b)
`
`x1
`
`xx
`
`2 3
`
`x
`n
`
`Hughes, Exh. 1028, p. 5
`
`

`

`conventional
`code
`
`check
`bits
`
`message
`bits
`
`x1
`
`xx
`
`2 3
`
`x
`n
`
`Hughes, Exh. 1028, p. 6
`
`

`

`snencc, our graphs arc not regulai. Indeed, the analysis in Section 6 shows lhal it is nol
`possible lo approach channel capacily with regular graphs.
`We refer to edges that begin adjacent to a node of degree ion the left (right) a,s ulgfs
`of degree ion the left (right). Ear.h of our degree sequences is sper.ified by a pair of vectors
`( ,\ 1 ~ ••• ~ ,\,,) and (p 1 , ••• , p,) ·where ,\; is the fraction of edges on the left of degree i and Pi
`is the fraction of edges on the right of degree j. Note that our graphs are specified in terms
`of fractions of tdgts~ and not rwdes, of each degree; this form is more con venicnt for much
`of our work. To doosP an appropriatP random bipartitP graph H with r; PdgPs, n nod12s
`on tlw IPft, and /3n nodes on thP right, \VP lwgin with a bipartite graph H' with f. nodes
`on both the left and right hand sides, \Vith each node of B' representing an edge slot. Each
`node on the left hand side of B' is associated ·with a node on the left side of B, so that the
`dist.rilmlion of degrees is given by (>. 1 , ... , ,\111 ), and similarly for the right. \Ve lhcn choose
`a. random matching (i.e., a random permutation) between lhc two sets of E nodes on fl'.
`This ind ucPs a random bipartite gra.ph on H in thP obvious manner with thP desired degrPe
`structure.
`Note that, in the corresponding subgraph of B' remaining after each step, the matching
`remaining on B' still corresponds to a random permutation. Hence, conditioned on the
`degree sequence of lhc remaining subgraph aJlcr each step, the subgraph that remains is
`uniform over all subgraphs with this degree sequence. The evolution of the degree sequence
`is th12refore a. IV!arkov procPss, a fact we makP use of below.
`In the next t\VO sections~ \Ve develop techniques for the analysis of the process for general
`degree sequences. After using these techniques in Section 6 to analyze regular graphs, '.Ve
`describe degree sequences that result in codes that. approach the capacity of the erasure
`channel in Section 7.
`
`4 Differential Equations Description
`
`To analyze the behavior of the process on the subgraph of B described in the previous
`section~ we begin by establishing a set of differential equations that describes its behavior
`in the limiting case, as lhc block kngth goes to infinity. Alt.crnalivdy, one may lhink of these
`equations as describing lhc expected behavior of lhc associaled random variables. Although
`these differPntial equations providP thP k12y insight into the beha:vior of the der.oding process,
`additional wmk is required to justify the rPiationship lwtv·lPen thP limiting and finite r.ases.
`\Ve begin \Vith the initial random graph B, with n left nodes and ;Jn right nodes.
`Consider the two vectors(,\;) and (p;), ·where ,\; and p; are the fractions of edges of degree
`ion lhc ldt., respectively right, with rcspecl lo the t.olalnumber E of edges in the original
`graph. The a.verage node dPgreP on the left at initially satisfips n{1 = Li >.;fi, and similarly
`the average node degrPe on thP right ar initially satisfies a.;:- 1 = Li p,fi.
`\Ve scale the passage of time so that each time unit of length !:it := -k corresponds to
`one step of the decoding process. Let 6 be the fraction of losses in the message. Initially,
`jusl prior to lime 0, each node on Uw leJl is removed with probabilit..Y 1 - b (because
`lhc corresponding message bil is succcssfull.Y recci ved), and thus the initial subgraph of
`H contains tJn nodes on thP left. If the pnxess terminates sucr.essfully, it runs until time
`
`(. -,
`
`Hughes, Exh. 1028, p. 7
`
`

`

`bn/E = b/ar: . \Vc let. L;(l) and r;(l) repre:sent lhe fraction of edges (in lnms of E) of degree
`ion Uw ldt. and righl, respectively, al time l. \\Te denote by fc(l) the fraction of the edge:;
`remaining, that is, e(t) = Li r ; (t) = Li r ;(t).
`lter,all that at ear,h step, a random node of degree one on the right is r,hosen, and the
`corresponding node on the left and all of its adjacent edges are deleted. (If there is no such
`node, the process necessarily stops.) The probability that the edge adjacent to the node of
`degree one on the right. has degree ion Uw len is f;(l)/e(l), and in thi:s case we lose ·i edge:;
`of degree i. This gives rise to the difl'erenr,e equation
`
`' .
`.\
`' .
`iC,(t)
`L ;(t + w.t)- L;(t) = ---( -.
`(c l)
`for the expected change of the number of edges f;(t) of degree i on the left. Noting that
`f; ( t) = L; (t) / E = L; ( t)tlt, \Ve see that in the limit as E ---+ oo the solution of this difference
`equation is de:scribed b_y that. of the di1I"crenlial equalion
`
`df;(t)
`dt
`
`if;(t)
`- - -
`c(t) ·
`
`(1)
`
`\Vhcn we n.'Inove a. node of degree i on lhe lcJl, we remove the one edge of degree one
`from the right, along \Vith the i- l othPr edg12s adjacPnt to this node. Henr,p the PxpectPd
`number of other PdgPs dPIPted is a(t) - L \vhere a( t) = '£ if;(t) / f(f). The right Pnd points
`of these i - 1 other edges on the right hand side are randomly distributed. If one of these
`edges is of degree j on the right, we lose j edges of degree j, and gain j - 1 edges of degree
`j - 1. The probabilily that. an edge has degree jon lhe righl i:s just ·r·j (l)/fc(l). Fori> 1,
`lhen, Uw dilkrcnce equation
`
`( )) i(o.(t)- 1)
`.
`'
`. .
`(
`. .
`R ;(t + tlt) - R ;(t) = ~'i+l (t) - r; t
`c(t)
`
`describes thP expectPd rhange of thP nrmzber of edg12s R t( f) of dPgreP ion the right. The
`corres ponding diifPrential equations for thP r;(t) axP th12refore
`
`,_. ))·i(a.(l)- 1)
`. )
`._ _
`dr.;(l) _
`..
`- - - (r,+l(t- r,(t
`f(t)
`dt
`
`(2)
`
`(\Ve assume that rz:(l) is dclined for all positi ve i, and is 0 for sulliciently large i.) The case
`i = 1 plays a :special role, as we mu:sl take into accounl that al each step an edge of degree
`one on the right is rPmoved. Henr,e, thP diifPrential equation for r 1 ( t) is given as
`
`dr !(t) = (r2(t)- rl(t)) (a(t)- 1) - 1
`dl
`· ·
`· · ·
`e(l)
`
`(3)
`
`Our key interest is in the progression of r 1 ( t) at a function oft. As long as r 1 ( t) > 0, so
`that \Ve have a node of degree one on the right, the process continues; \Vhen r 1 ( t) = 0 the
`process :slop:s. Hence we would like for ·r·1 (l) > 0 until all nodes on the len arc deleted and
`lhe process lnminat.e:s :successfully.
`
`7
`
`Hughes, Exh. 1028, p. 8
`
`

`

`These difl'crcnt.ial equations arc more casil_y solved by defining :c so that. tb: J:c = dt / e( l).
`The value of J: in lenns of lis then J: := exp(-./~dT/e(T)). Dy substituting th'/:c for
`dtje(t), equation (l) beromes df; (:r)jd;r = -if;(:r)j;r, and integrating yields f;(:r) = c;:r1 .
`. \ote that :r = l fort = 0, and C;(t = 0) = t5A.;. Henre, c; = t'i>..; and
`t;(.-r) = 8A.;xi.
`Since f 1:(:c) goes to zero as l goes to b/ at , :c runs over the interval [1, OJ.
`Solving for the r1(:c) is more involved. The main goal is to show that. rd J:) > 0 on (0, 1],
`so that the process does not halt before completion. Details for solving for the r;(:r), and in
`particulax for r 1 (:r), are given in Appendix A; the proposition below presents the solution
`for r 1 ( x). The result is expressed using the generating functions
`/\(J.') = L /\::ci-1
`
`and
`
`i>l
`
`p(J:) = 2:::: (J£:1) -1:
`
`i>l
`lhese generating funclions play <m imporlant role in lhe remainder of our presentation.
`
`Lemma 1 The solulion r 1 (:c) of lht dij]f:r·tntial tqualion (3) is givt'n by
`b/\(J:) [J:- 1 + p(1- bA.(:c))].
`From ( 4), we Jind that this requires lhe condilion
`t5A.(;r)) > l - :r , ;r E (0, l].
`
`p(l -
`
`This condition shall play a central role for the remainder of our work.
`
`(4)
`
`(7i)
`
`5 Using the Differential Equations to Build Codes
`
`Recall that. lhe difl'crcnt.ial equalions describe the limiting behavior of lhe process Oil n' as
`lhe block length goes to inJinily. From this one can dcri ve that if (5) is violated, so that.
`p(l- 8A.(:r)):::; 1- :r somewhere on (0, l] then the process fails for large block lengths with
`high proba.bility.
`Proving the process progresses almost to completion if (5) is satisfied is possible by relat(cid:173)
`ing the difi'crenlial equalions to lhe underlying random process (sec, e.g., [8, 10]). Proving
`lhe process runs to completion can be ha,ndled with a scparale combinatorial argument. In
`some cases, hmvever, this requires small modifications in the graph wnstrur.tion.
`Lemma 2 Ltl n be (l bipadilt gmph dwstn al randon/. Ivilh edge-degrees sptcijied by /\(:c)
`and p( :r). /,et t5 be fi;l:erl so that
`p(1- 8>..(.-r)) > 1- x,
`for .T E (0, 1].
`For all ry > 0, if the message bits ofC(B) arc lost independently with probability 8, then the
`decoding algorithm ltT·mirwtes wilh 'fn.m·e lhan ·rrn Tnessage bits nol recovered with crponen(cid:173)
`lially sTnall probabihly, as lhe block lenglh gmws large.
`
`Hughes, Exh. 1028, p. 9
`
`

`

`The following combinatorial lail arguments is useful in showing lhal lhe process tcnni(cid:173)
`nalcs successfully when there arc no nodes on the len of degree one or two. (Such arguments
`ax12 oft12n r12quir12d in similar situations; s1212, for 12xarnpl12, U"iJ.)
`
`Lemma 3 Let B be a bipartite graph chosen at random with edge-degrees specified by A(x)
`and p(.-r), such that ).(.-r) has ). 1 = A2 = 0. Then there is some ry > 0, such that with
`probabihly 1 - o(1) (over lhe choice of D) 1j al Tnosl an IJ fmclion of lhe nodes on lhe lefl
`in fl l't'lnain, lhtn /he process {er·rninaltS S'liCCessfally.
`
`{Skelch} Lcl S be any scl of nodes on lhe kft. of size al most qn. Lcl a be lhe
`Proof:
`average degree of these nodes. H lhe mnnber of nodes on the righl that arc neighbors of
`Sis gr12at12r than aiSI/2, then on12 of th12se nod12s has only one n12ighbor in 15'1, and so the
`pror,12ss r,an wntinue. Thus, \VI2 only n1212d to show that the initial graph is a. good 12xpandP1"
`on small sets. Since the degree of each node on the left is at least three, standard proofs
`(sec [11]) suffice to show that lhe cxpa.nsion condition holds with high probability for all
`sets conlaining al mosl <m IJ fraclion of the len nodes.
`D
`Using Lemmas 2 and 3, we can show that the wd12s presented in Section 7 \Vork with
`high probability. As our asymptotir, results for asymptototir,ally good gen12ral wdes use
`graphs ·with degree t'vo nodes on the left, >ve extend the construction and use more careful
`arguments to prove that the process completes, as described in Section 7.
`
`6 Analysis of Regular Graphs
`
`\'Ve demonstrate the techniques developed in the previous section in a simple setting: we
`analyze the behavior of the process on random regular graphs. Because random regular
`graphs have so often been used in similar silualions, it is natural to consider if lhe_y give
`rise to codes that arc dose to optimal. They do not. The following lemma proves a weak
`form of this behavior. We have explicitly solved for the largest value of {i \vhid satisfies
`condition (5) for rod12s based on regular graphs for several rate values. In ev12ry case, th12re
`is some small degree value that achieves a maximum value of 8 far from optimal, and the
`maximal achievable value of 8 decreases as the degree increases thereafter.
`
`Lemma 4 Ltl fl bt a bipal'lile r·eg·tdar graph dwstn al randon1., wilh all edge8 having lefl
`'!'hen eonrlition (5) holds only i.f
`degref d and right degref dj(J, ford=::: :3.
`)1<£/;t)-1)
`( .1
`. . . (·
`b<4 1- - -
`-
`d-1
`
`'
`.
`
`and hence as d __,. ·X, the maximum acceptable loss rate goes to 0.
`
`\V12 ha.ve that ).(:r) = :rd-l, and p(:r) = :r(d//Jl-1. Henr,e our wndition (7i) on the
`Proof:
`acceptable loss rate 8 becomes
`
`~·· d-l) (d/,U)-1
`1-(.r
`
`(.
`
`>1-:r
`
`Hughes, Exh. 1028, p. 10
`
`

`

`fm :r E (0, 1].
`\Ve plug in :r
`requirement
`
`1 - d~l. Using the fact lhal (1- d~l )d-l > ! fm d > 3 yields lhe
`8) (d/3)-l
`
`(
`
`1--
`4
`
`1
`> --.
`- d -1
`
`This simplifies to the inequality in the statement of the lemma.
`It is easy to check that as d ---+ oo, the right hand side of the above equation goes to 0,
`which concludes the lemma.
`D
`lienee, for any lixed jJ, there is some d which achieves lhe maximum value of 0 possible
`using regular graphs, and this 15 is far from optimal. l1'or example, in the case \vhere /3 = I /2,
`\Ve have found that the best solution is to let the left nodes have degree three and the right
`nodes have degree six. In this case the code can handle any 6 fraction of losses with high
`probability as long as
`
`(1 - 8:r 2 r ;::: 1 -
`
`;1:
`
`fm :c E (0, 1]. The inequality Jails forb ;::: 0.43. The rale R for lhis code is 1/2, and thus
`Ill is at most 0.86, far from the optimal value of 1.00.
`the ratio 15/(l -
`Simulation runs of the code turn out to match this value of 15 accurately, demonstrating
`that these techniques provide a sharp analysis of the actual behavior of the process.
`
`7 Asymptotically Optimal Codes
`
`In this section, we conslrucl codes that transmit. at. rates arbitrarily dose to lhe capacity of
`the erasure channel. \Ve do this by finding an infinite sequence of solutions to the diiferential
`equations of Section 4 in which {i a.pproaches p.
`As the degree sequences we use have degree two nodes on the left hand side, we cannot
`appeal to Lemma ;) to shuw that they \Vork \Vith high probability. Hence our codes require
`some additional structure.
`Let fl be a. bipartite graph wilh n ldt. nodes and Bn right nodes.
`\\-'e describe our
`choir,e for the left and right degree sequences of H that satisfy condition (5). Let d be a
`positive integer that is used to trade off the average degree ·with how 'Nell the decoding
`process \Vorks, i.e., huw close \Ve can make 8 to j3 = 1 - Rand still have the process finish
`successfully most. of the time.
`The left degree sequence is described by the following truncated heavy tail distribution.
`Let H(d) = z1=1 1/i be the harmonic sum truncated at d, and thus H(d)"' ln(d). Then, for
`all i = 2, ... , rl+ I, the frar,tion of edges of degree ion the left is given by>. ; = 1 /( H (d)(i-1 )).
`The average left degree a-t equals H(d)(d+ 1)/d. Recall that \Ve require the average right
`degree, a.,., to satisfy ar = af//3. The right degree sequence is defined by the Poisson
`dist.ribulion with mean ar: fm all ·i ;::: 1 the fraction of edges of degree i on lhe right. equals
`
`Pi
`
`(i- 1)! ,
`
`10
`
`Hughes, Exh. 1028, p. 11
`
`

`

`where o is chosen lo guarantee that the a.vcragc degree on lhc righl is ar. In other words,
`o sat.isJies ae0 l(e0
`- 1) = ar.
`NotP that we allmv p; > 0 for all i ?' I, and henr,p r;(;r) is not truly a polynomial, but a
`pmvPr seriPs. HowPver, trunr,ating tlw pmvPr seriPs p(:r) at a suffir,iently high t12rm gives a
`finite distribution of the edge de[.:!;rees for ·which the next lemma is still valid.
`\Ve shuw that \Vhen 8 = ;31(1 + 1ld) in (.5)~ the condition is satisfied, i.e., p(1- 8.\(.-r)) >
`1- J: on (0~ 1], where /\(:c) = Li Xi:r£- 1 and p(:r) = Li pp .. i- 1 . Note that. >.(:r) is lhc
`;r) truncated at the dth term, and scaled so that .\(1) = I. l1'urther,
`expansion of -ln(l -
`r;(;r) = e"(~ -1).
`ll'ith the abm1f dwiees for r;(;r) and .\(:r) we have p(l -8.\(:r)) > l- :r on (0, 1]
`Lemma 5
`if l) s r>1r1 + 1 lrl).
`
`Proof: Recall that p( x) = c"'(·"- 1
`we have
`
`), hence p(.-r) increases monotonically in x. As a result,
`
`p(1 - b/\(:c)) > p( 1 + b ln(1 -
`:r) I II (d)) = ( 1 - J'Y"f/ Ff(rl).
`Sinre a ,~ = H(r1)(1 + lid) and a.,.= a!)(J, we obtain cJil H(rl) =(I- C " )(l + 1lr1)15l/3 <
`8(1 + 1ld)l/3 s 1, \Vhich shO\vs that the right hand side of the above inequality is larger
`lhan 1- :r on (0, 1].
`D
`A probkm is lhal Lcnnna. 3 docs not. a.pply to this system because there arc nodes oJ
`degrPe two on the left. Indeed, simulations d12monstrate that a small numbPI' of nodes often
`do I'Pmain. To overwme this problem~ \Ve make a small change in the strudure of the
`graph B. We split the ,3n right nodes of B into t\VO distinct sets, the first set consisting
`of (,3 - ~r)n nodes and the second set consisting of ~rn nodes~ ·where ''f is a small constant
`lo be determined. The graph fl is then Jmmcd b.Y laking lhc union oJ two graphs~ fl1 and
`n'2. nl is formed as described up to lhis point between the n left. nodes and the Jirst scl
`of (,8- i')n right nodes. H2 is formed between the n left nodes and thP second set of '"/n
`right nod12s, where each of then left nodes has degreP three and the 3n edges are wnnectPd
`randomly to the --yn ri[.:!;ht nodes.
`
`Lemma 6 Ltl fl bt lhe bipaf'lile graph just describtd. Then, wilh high pmbabilily, lht
`process terminatu; sw:ees.~f'rdly ·whfn started on a subgraph ~~f' H indueed by tJn ~~f' thf left
`nodes and all ,8n ~~f' the ri,qht nodes, whfre 15 = (J I ( 1 + 1 I d).
`
`[.S'kctch} In the analysis of the process~ \Ve may think of B 2 as being held in reserve
`Proof:
`to handle nodes not already dealt ·with usin[.:!; B 1 • Combining Lemma 5 and Lemma 2, ·we
`can shcnv that, Jm any conslant ·rt > 0, wilh high probabilily al most ·rrn nodes on the lcl'l
`remain aJt.cr the process runs on fl1 . The induced gra.ph in fl'2 between lhcsc remaining qn
`left nodes and the '"/n right nodes is then a random bipartite gra.ph such that all nodes on
`the left ha.ve degrPe three. We rhoose ~/ to be la.rger than 17 by a small constant factor so
`that ·with high probability the process terminates successfully on this subgraph by Lemma :1:
`note that the lemma applies since all nodes on the left have de[.:!;ree three. By choosin[.:!; 17
`suJiicient.ly small, we may make ~: arbilra.rily small, and hence lhc decrease in the value oJ
`b bdow that. slated in Lemma .5 can be made a.rbilrarily small.
`D
`
`11
`
`Hughes, Exh. 1028, p. 12
`
`

`

`Note that. lhc degree oJ each left. node in lhis modilicd construction oJ fl is at. most. three
`bigger than the average degree oJ each left. node in lhc conslruclion oJ fl dc~nibcd at lhc
`b12ginning of this sPdion. \VP ran usP this obsNvation and thP IPmma abovP to imnwdiatPiy
`prove our main tlworem.
`
`Theorem 1 /"or any /{, an!J positivf f, and su.ffir:ifntly large b!od: lfnqth n, then '1.8 a
`loss-resilifnt eodf that, with high probabild!J, is able to nr:over from thf random loss ~~f a
`(1- R)(1- E)-fraction of its bits in time proportional to nln(1/E) .
`
`[.S'A:etch) Set r1 = 1/f to get a onP IPvel wdP with thP propertiPs desuibed in
`Proof:
`Lemma 6. Cascade versions of these codes as described in Section 2 to get the entire code.
`The proof follO\vs since each level of the cascade fails to recover all its message bits, given
`all oJ its check bit~, wilh ~mall probabilit._y.
`D
`
`8 A Linear-Algebraic Interpretation
`
`The (Jn rhed; bits ofthP code C(H) desuibed inSertion 2 Gtn be wmputed by multiplying
`the vector of n message bits by the ,3n x n matrix, M(B), \Vhose ( i, j)-th entry is 1 if there
`is an edge in B between left node i and right node j and is 0 otherwise (the multiplication is
`over the lidd oJ l wo dements). \Ve choo~e our graphs n lo be ~par~e, ~o lhal the resulting
`matrix ;.\1 ( fl) i~ sparse and lhc mulliplication can be performed quickl_y.
`The effkiency oft he decoding algorithm is related to the ease with which one Gtn perform
`Gaussian elimination on submatrices of .:Jf(B). If one knO\vs all the check bits and all but
`8n of the message bits, then it is possible to recover the missing message bits if and only
`if the bn columns oJ Af(BJ indexed by lhc message bits have Jull rank. These bit~ e<m be
`recovered by Gaussian elimination. In Section 7' we prescnl a dist.rilmlion OIL g