Tornado and Luby Transform CodesBackground: Erasure ChannelClassical MDS CodesDigital Fountain ApproachTornado CodesIrregular Bipartite GraphIrregular Graphs: ExampleConstruction of Tornado CodesLinear Time Decoding AlgorithmWhat has to be solved?Conditions on Degree SequencesCapacity Achieving DistributionCapacity Achieving DistributionLinear Programming ApproachPractical ImplementationsIssuesLuby Transform CodesEncoding of LT CodesDecoding LT CodesLT Analysis-1 (ρ(1)=1)LT Analysis-2LT Analysis-3Properties of Soliton DistributionRobust Soliton DistributionRobust Soliton Distribution (contd.)Robust Soliton DistributionConclusionsTornado and Luby Transform CodesAshish Khisti6.454 PresentationOctober 22, 2003Background: Erasure Channelmx2• Capacity of Noiseless Erasure Channel is • No Feedback is necessary to achieve capacity• A random linear code can achieve capacity. Encoding: O(n2) Decoding: O(n3)Applications•Communication Links over the Internet•Storage Media )1(β−mElias[1956] studied the Erasure Channel1x1xkx2?β−1β−1βClassical MDS CodesFeatures• Any set of k co-ordinates is an information set for (n,k,d) MDS Code. • The receiver knows the codeword once it receives any k symbols andknows their positions. • Capacity achieving codes.Drawbacks• Reed Solomon Codes (RS) codes require O(k2) time for decoding. • Block codes : Need prior knowledge of erasure probability. kc212k1c2cn symbolsDigital Fountain Approach• A new protocol for bulk data distribution• Scenario: One Server multiple ReceiversEncoding: Construct encoding symbols on the fly and send them when atleast one receiver is listening.Decoding:Collect desired number of symbols from the server and reconstruct the original fileGoals:Reliable, Efficient, On Demand and TolerantTornado CodesFeatures• Correct 1-R(1- ε) errors over BEC.• Time for encoding and decoding is proportional to• Very fast software implementations.Tradeoffs• The assumption of independent erasures is critical.• High latency.• Low Rate Implementations are less attractive.• Block Codes – Not suitable for heterogeneous receiver population.()ε1lognIrregular Bipartite Graph• Irregular Random Graphs are used for generating check symbols•(x1, x2, … xn) (x1…xn, c1…cnβ)Degree SequencesLeft Degree Sequence: (λ1, λ2,…λn)Right Degree Sequence: (ρ1, ρ2… ρm)Definition: λk(ρk) is the fraction of edges that are incident on a left(right) node of degree k.nx1x211xxc+=2xβncCheck SymbolsInput/MessageSymbolsIrregular Graphs: Exampleπ1 1Given:(λ1, λ2) = (1/2,1/2)(ρ1, ρ2) = (0,1)Number of Edges E = 4li= number of left nodes of degree iri= number of right nodes of degree i223π1122iEriiρ=iEliiλ=3)1,2(),(21=ll)2,0(),(21=rrRandom permutation between edges, induces a uniform distributionover the ensemble.Construction of Tornado Codes(n)(βn)(β2n)(βm+1n)B0B1`BmCBi: Irregular GraphC : Conventional CodeCode C(B0,B1,B2…Bm,C):• Each Biis an irregular bipartite graph with same degree sequences• C is a conventional rate (1- β) code with O(n2) complexity.• m is chosen such thatLength of C:This is a rate (1- β) code with encoding/decoding complexity of O(n).ββββ−=−+∑+=+11102nnnmiminnm≈βLinear Time Decoding Algorithms1s2s31.1. Find a check node cnthat is connected to only one source node sk. If no such cnstop and declare error.(a) set sk= cn(b) find all cn’that are neighbors of skand setcn’=cn’ + sk(c) Remove all edges connected to sk2. Repeat (1) until all source nodes are determined.4.1 0s3101111102.1 s2s35.1 0s310113.11101 s2s31 016.1110What has to be solved?So far…• Identified the structure of encoder as a cascade of irregular bi-partite graphs.• Suggested a candidate decoding algorithm which has linear complexity.Goal:Specify the set of degree sequences (λ1, λ2,…λn) and (ρ1, ρ2… ρm) for which the this simple decoding algorithm succeeds.Main Contribution of the Paper:1. Develop mathematical conditions on the degree sequences under which this decoding scheme succeeds2. Provide explicit degree sequences that achieve the capacity of BEC.Conditions on Degree Sequences∑−=iiixx1)(λλ∑−=iiixx1)(ρρδ: Erasure Probability of the memoriless channelNecessary Condition: If the decoding algorithm succeeds in recovering all message symbols then Approach: Compute the expected value of the fraction of edges with degree one on the right and require that it is > 0]1,0(,1))(1(∈∀−>−xxxδλρDefine:Sufficient Condition: The above condition is also sufficient if we impose λ1= λ2=0. Approach: The proof uses tools from statistical mechanics to show that the variance in degree distribution is small.Capacity Achieving DistributionFix an integer D > 0, Let1...3,2,)1)((1+=−= DiiDHiλ...3,2.1,)!1(1=−=−−iieiiαρα• Average degree of left nodes =• Average degree of right nodes =)log(/1DiEiEiiii≈⎟⎠⎞⎜⎝⎛=⎟⎠⎞⎜⎝⎛−∑∑λλβαραα)log(11Deeiii≈−=⎟⎠⎞⎜⎝⎛−∑Intuition:• Poisson distribution is natural if all the edges from the left uniformly choose the right nodes. • This distribution is preserved when edges are successively removed fromthe graph.• Heavy tail distribution produces some message nodes of high degrees that get decoded first and remove many edges from the graph.Capacity Achieving Distribution• Note that:• For the above choice of ρ(x) and λ(x), it is easy to verify that whenever,• Let D = 1/ε. It follows that ≈β(1- ε) fraction of erasures can be corrected by this rate 1- β code. The maximum degree ≈log(D), implies that the number of operations in decoding is proportional to nlog(1/ ε).]1,0(,1))(1(∈∀−>− xxxδλρDxx )1log()(−−=λ)1()(−=xexαρD/11+<βδLinear Programming Approach•Fix (λ1, λ2,…λn) and δ. The objective is to find (ρ1, ρ2… ρm) for some fixed m.• Let xi= i/N, for i=1,2..N. We have the following constraints:– ρ(1- δ λ( xi)) > 1-xi– ρi ≥ 0 and ρ(1) = 1Minimize• The solution for ρ(x) is feasible if the inequality holds for all x in (0,1]• Once a feasible solution has been found the optimal δ is found by a binary search.• An iterative approach is suggested that uses the dual condition ∑=−+−Niiixx1)1)(1((δλρ]1,0(,))(1(∈∀<− yyyρδλPractical Implementations640K320K160K160KG0G1G2Tornado Z Code • Rate ½ code. Takes 640,000 packets (each 256 byte) as input.• Only three cascades have been