Unformatted text preview:

Summary of Raptor CodesTracey HoOctober 29, 20031 IntroductionThis summary gives an overview of Raptor Codes, the latest class of codesproposed for reliable multicast in the Digital Fountain model. This is asummary of a 2003 preprint by Amin Shokrollahi.2 Background2.1 Fountain CodesA fountain code pro duces for given set of k input symbols (x1, . . . , xk) a po-tentially limitless stream of output symbols z1, z2, . . .. The input and outputsymbols can be binary vectors of arbitrary length. Each output symbol is thesum of a randomly and independently chosen subset of the input symbols.Information describing the relations between input and output symbols isobtained at the receivers either in packet headers or by other application-dependent means of synchronization between sender and receivers.A reliable decoding algorithm for a fountain code is one which can re-cover the original k input symbols from any set of m output symbols witherror probability at most inversely polynomial in k. The ratio m/k is calledthe overhead. The encoding cost is the expected number of arithmetic op-erations sufficient for generating each output symbol. The decoding cost isthe expected number of arithmetic operations sufficient to recover the k in-put symbols, divided by k. Desirable properties for a fountain code are anoverhead close to 1, and constant encoding and decoding cost. A universalfountain code is one for which the decoder can recover with high probabilitythe original symbols from any set of output symbols whose size is close tooptimal.12.2 Tornado CodesTornado Codes [1] are not strictly fountain codes since the number of outputsymbols is fixed for a particular code. They are however precursors to the LTCodes and Raptor Codes in that they are derived from sparse irregular ran-dom bipartite graphs, whose associated encoding and decoding algorithmscompute one exclusive-or operation for each edge. The edge degree distri-butions of these graphs are carefully chosen so that with high probability,successful decoding is achieved by a simple belief propagation deco der thatsets the value of a graph node only if the values of all its neighbors areknown.Tornado codes use a cascade of such graphs. For any given rate R andoverhead 1 + ε, an (n, k = Rn) tornado code with O(log(1/ε)) encoding anddecoding cost can be designed, such that a codeword can b e recovered from(1 + ε)k output symbols with probability 1 − O(k−3/4).2.3 LT CodesLT Codes [2] were the first class of universal fountain codes to be invented.Each output symbol is generated by randomly choosing a degree d from somesuitable degree distribution, choosing d distinct input symbols uniformly atrandom, and taking their sum.If the output symbol degrees are chosen according to the Robust Solitondistribution proposed in [2], k input symbols can be recovered from anyk + O(√k log2(k/δ)) output symbols with probability 1 − δ. The averageencoding and decoding cost is O(log(k/δ)).3 Limitation of LT CodesThe following proposition shows that the decoding graph of a reliable de-coder for an LT code has at least O(k log(k)) edges. It follows that if thenumber m of output symbols needed for decoding is close to k, then eachoutput symbol is the sum of O(log(k)) input symbols on average. The persymbol encoding cost is then O(log(k)).Proposition 1 If an LT code with k input symbols as a reliable decodingalgorithm, then there is a constant c such that the decoding graph has atleast ck log(k) edges.Proof outline: Suppose m output symbols suffice to achieve error prob-ability at most 1/kufor some constant u. Let a be the average degree of2an output node in the decoding graph, and b = am/k the average degree ofan input node. The probability of error is lower bounded by the probabilitythat a particular input node v is not a neighbor of any output node, whichcan be expressed as (1 − a/k)n. A series of mathematical manipulationsleads to the inequality b ≥ c log(k).4 Raptor CodesThe key idea of Raptor Coding is to relax the condition that all input sym-bols need to be recovered. If an LT code needs to recover only a constantfraction of its input symbols, then its decoding graph need only have O(k)edges, allowing for linear time encoding. We can still recover all input sym-bols by concatenating a traditional erasure correcting co de with an LT code.n intermediate symbols are obtained by encoding k input symbols with an(n, k) erasure correcting block code capable of recovering all input symbolsfrom a fixed fraction of intermediate symbols. The n intermediate symbolsare then encoded with an LT code that can recover from its output symbolsthe required fraction of intermediate symbols. A Raptor Code is specified byparameters (k, C, Ω(x)), where C is the (n, k) erasure correcting block code,called the pre-code, and Ω(x)) is the generator polynomial of the degree dis-tribution of the LT code, i.e. Ω(x) =Pki=1Ωixi, where Ωiis the probabilitythat the degree of an output node is i.The performance parameters overhead and decoding cost as defined insection 2.1 apply directly to Raptor Codes. However, the definition of theencoding cost of a Raptor Code differs slightly – it is the sum of the en-coding cost of the pre-code divided by k, and the encoding cost of the LTcode. Raptor Codes also require storage for intermediate symbols, so spaceconsumption is another important performance parameter.5 First Examples of Raptor Codes5.1 LT CodesAn LT code with k input symbols and output distribution Ω(x) is itself aRaptor Code with parameters (k, Fk2, Ω(x)), where Fk2is the trivial code ofdimension and block length k. The lack of a pre-code necessitates the useof a sophisticated output distribution Ω(x) with logarithmic encoding anddecoding cost, as discussed in Section 3. The overhead and space howeverare close to 1.35.2 Pre-Code-Only (PCO) Raptor CodesAt the other end of the spectrum are Pre-Code-Only (PCO) Raptor Codes.These codes have a sophisticated pre-code but a trivial output distributionΩ(x) = x, which sets the value of every output symbol to that of a randomlyand uniformly chosen input symbol. This approach in effect builds a fountaincode from any block code.The decoding algorithm collects a predetermined number m of outputsymbols, which determines the values of some number l of intermediatesymbols. The decoding algorithm for the pre-code is then applied to theserecovered intermediate values to obtain the values of the input symbols.The


View Full Document

MIT 6 454 - Summary of Raptor Codes

Documents in this Course
Load more
Download Summary of Raptor Codes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Summary of Raptor Codes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Summary of Raptor Codes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?