Network coding for multicastrelation to compressionand generalization ofSlepian-Wolf1Overview• Review of Slepian-Wolf • Distributed network compression • Error exponents Source-channel separation issues • Code construction for finite field multiple access networks2Distributed data compressionConsider two correlated sources (X, Y ) ∼ p(x, y) that must be separately encoded for a user who wants to reconstruct both What information transmission rates from each source allow decoddin with arbitrarily small probability of error? E.g. H(X1) X1 .. ..X2H(X2|X1)3Distributed source codeA ((2nR1,2nR2),n) distributed source code for joint source (X,Y) consists of encoder maps f1 : Xn →{1,2,...,2nR1}nf2 : Y→{1,2,...,2nR2} and a decoder map n g : {1,2,...,2nR1}×{1,2,...,2nR2}→Xn ×Y-Xn is mapped to f1(Xn) -Yn is mapped to f2(Yn) -(R1,R2) is the rate pair of the code 4Probability of errorPe (n) =Pr{g(f1(Xn),f2(Yn)) =(Xn,Yn)}Slepian-WolfDefinitions:A rate pair (R1,R2)is achievable if there exists a sequence of((2nR1,2nR2),n) distributed source codes with probability of error Pe (n) →0as n →∞ achievable rate region -closure of the set of achievable rates Slepian-Wolf Theorem: 5For the distributed source coding problem for source (X, Y ) drawn i.i.d. ∼ p(x, y), the achievable rate region is R1 ≥ H(X|Y ) R2 ≥ H(Y |X) R1 + R2 ≥ H(X, Y ) Proof of achievabilityMain idea: show that if the rate pair is in the Slepian-Wolf region, we can use a random binning encoding scheme with typical set decoding to obtain a probability of error that tends to zero Coding scheme: • Source X assigns every sourceword x ∈Xn randomly among 2nR1 bins, and source Y independently assigns every y ∈Yn randomly among 2nR2 bins • Each sends the bin index corresponding to the message 6• the receiver decodes correctly if there is exactly one jointly typical sourceword pair corresponding to the received bin indexxes otherwise it declares an error Random binning for single source compressionAn encoder that knows the typical set can compress a source X to H(X)+without loss, by employing separate codes for typical and atypical sequences Random binning is a way to compress a source X to H(X)+ with asymptotically small probability of error without the encoder knowing the typical set, as well as the decoder knows the typical set • the encoder maps each source sequence Xn uniformly at randdo into one of 2nR bins 7• the bin index, which is R bits long, forms the code • the receiver decodes correctly if there is exactly one typical sequence corresponding to the received bin index Error analysisAn error occurs if:a) the transmitted sourceword is not typical, i.e. event(n)E0 = {X ∈/A} b) there exists another typical sourceword in the same bin, i.e.event E1 = {∃x )= f(X), x ∈ A(n)= X : f(x } Use union of events bound: Pe (n) =Pr(E0 ∪ E1) ≤ Pr(E0)+Pr(E1) 8 Error analysis continuedPr(E0) → 0 by the Asymptotic Equipartition Property (AEP) Pr(E1)= Pr{∃x )= f(x),= x : f(x x x ∈ A(n)} ≤ Pr(f(x )= f(x)) x x� = x x� ∈ A(n) = |A(n)| 2−nR x ≤ 2−nR 2n(H(X)+) → 0if R>H(X) 9 For sufficiently large n, Pr(E0),Pr(E1) <⇒ P(n) <2Jointly typical sequencesThe set A(n) of jointly typical sequences is the set of sequences (x,y) ∈Xn ×Yn with probability: 2−n(H(X)+) ≤pX (x) ≤2−n(H(X)−) 2−n(H(Y )+) ≤pY (y) ≤2−n(H(Y )−) 2−n(H(X,Y )+) ≤pX,Y (x,y) ≤2−n(H(X,Y )−) for (X,Y) sequences of length n IID according to pX,Y(x,y)= n i=1 pX,Y (xi,yi) Size of typical set: (n)|≤2n(H(X,Y )+)|A10 Proof: 1= p(x, y) ≥ p(x, y) (n)A≥|A(n)|2−n(H(X,Y )+) Conditionally typical sequencesThe conditionally typical set A(n)(X|y) for a given typical y sequeenc is the set of x sequences that are jointly typical with the given y sequence. Size of conditionally typical set: |A(n)(X|y)|≤2n(H(X|Y )+) Proof: 11For (x, y) ∈A(n)(X, Y ), .p(y)=2−n(H(Y )±) .p(x, y)=2−n(H(X,Y )±) p(x, y) ⇒p(x|y)= p(y) .=2−n(H(X|Y )±2) Hence 1 ≥ p(x|y) x∈A(n)(X|y) ≥|A(n)|2−n(H(X|Y )+2) Proof of achievability – error analysisErrors occur if: a) the transmitted sourcewords are not jointly typical, i.e. event E0 = {(X, Y ) ∈/A(n)} b) there exists another pair of jointly typical sourcewords in the same pair of bins, i.e. one or more of the following events E1 = {∃x =X : f1(x )= f1(X), (x , Y) ∈ A(n)}E2 = )= f2(Y), (X, y ) ∈ A(n)}{∃y = Y : f2(y E12 = {∃(x , y ): x = X, y = Y,f1(x )= f1(X), f2(y )= f2(Y), (x , y ) ∈ A(n)} 12 Use union of events bound: Pe (n) =Pr(E0 ∪ E1 ∪ E2 ∪ E12) ≤ Pr(E0)+Pr(E1)+Pr(E2)+Pr(E12) Error analysis continuedPr(E0)→ 0bythe AEPPr(E1)= Pr{∃x =x :f1(x )=f1(x), (x,y) (x ,y)∈ A(n) } ≤ Pr(f1(x )=f1(x)) (x,y) x� = x (x� , y) ∈ A(n) = |A(n) (X|y)| 2−nR1 (x,y) ≤ 2−nR1 2n(H(X|Y )+2) → 0ifR1 >H(X|Y) 13Similarly, Pr(E2) ≤ 2−nR2 2n(H(Y |X)+2) → 0if R2 >H(Y|X) Pr(E12) ≤ 2−n(R1+R2) 2n(H(X,Y )+) → 0if R1 + R2 >H(X,Y) Error analysis continuedThus, if we are in the Slepian-Wolf rate region, for sufficiently large n, Pr(E0),Pr(E1),Pr(E2),Pr(E12) <⇒ P(n) < 4Since the average probability of error is less than 4, there exist at least one code (f1∗ ,f2∗ ,g ∗) with probability of error < 4. Thus, there exists a sequence of codes with P(n) → 0. 14Model for distributed network compression• arbitrary directed graph with integer capacity links • discrete memoryless source processes with integer bit rates• randomized linear network coding over vectors of bits in F2 • coefficients of overall combination transmitted to receivers• receivers perform minimum entropy or maximum a posteriori probability decoding 15Distributed compression problemConsider • two sources of bit rates r1,r2, whose output values in each unit time period are drawn i.i.d. from the same joint distributtio Q • linear network coding in F2 over vectors of nr1 and nr2 bits from each source respectively Define 16• m1 and m2 the minimum cut capacities between the receiver and each source respectively • m3 the minimum cut capacity between the receiver and both sources • L the maximum source-receiver path length Theorem 1 The error probability at each receiver using minimmu entropy or maximum a posteriori probability decoding is at most i3=1 pei ,where p 1 ≤ exp − n min D(PX1X2 ||Q)e X1,X2 1 + + m1(1 − log L) − H(X1|X2) +22r1+r2 log(n +1) n p 2 ≤ exp − n min D(PX1X2 ||Q)e X1,X2 1 + + m2(1 − log L) − H(X2|X1) +2r1+2r2 log(n +1) n p 3 e ≤ exp − n min D(PX1X2 ||Q) X1,X2 + m3(1 − 1 log L) − H(X1X2) + +22r1+2r2 log(n +1) n 17Distributed compression• Redundancy is removed or added in different parts of the network depending on available capacity • Achieved without knowledge of source entropy rates at interiio network nodes • For the special case of a Slepian-Wolf source network consisstin of a link from each source to the receiver, the network coding error exponents reduce to known error exponents for linear Slepian-Wolf coding [Csi82] 18Proof outline3 =1 pie,where• Error probability ≤i1eis the probability of correctly decoding X2 but not X1,– p2eis the probability of correctly decoding X1 but not X2– p3eis the probability of wrongly decoding X1,X2– p• Proof approach using method of types similar to that in [Csi82] • Types Pxi, joint types Pxy are the empirical distributions of elements in vectors xi 19Proof outline (cont’d)Bound error probabilities by summing over • sets of joint types ⎧ ⎪ ˜˜{P| X1 =X1,X2 = X2} i =1 ⎨ X1X˜1X2X˜2 Pi = {P| X˜1 = X1,X˜2 = X2} i =2 nX1X˜1X2X˜2⎪ ⎩ {P| ˜X˜2 = X2}X1X˜1X2X˜2 X1 = X1, i =3 ˜nriwhere Xi,Xi ∈ F2 20 • sequences of each type TX1X2 =[ xy ] ∈ F2 n(r1+r2) Pxy = PX1X2 TX˜1X˜2|X1X2(xy)= [˜xy˜] ∈ F2 n(r1+r2) P˜x˜= PX˜1X˜2X1X2yxy Proof outline (cont’d)• Define – Pi,i =1,2, the probability that distinct (x,y),(˜x,y), where x x, at the receiver =˜– P3, x,˜x =˜y,the probability that (x,y),(˜y), where x,y =˜are mapped to the same output at the receiver • These probabilities can be calculated for a given network, or bounded in terms of block length n and network parameters 21Proof outline (cont’d)• A link with ≥ 1 nonzero incoming signal carries the zero signal with probability 21 nc ,where c is the link capacity • this is equal to the probability that a pair of distinct input values are mapped to the same output on the link • We can show by induction on the minimum cut capacities mi that Pi ≤ 1 − (1 − 1)L mi 2nmiL ≤ 2n 22Proof outline (cont’d)We substitute in • cardinality bounds |P1| < (n +1)22r1+r2 n|P2| < (n +1)2r1+2r2 n|P3| < (n +1)22r1+2r2 n|TX1X2|≤ exp{nH(X1X2)}|TX˜1X˜2|X1X2(xy)|≤ exp{nH(X˜1X˜2|X1X2)} • probability of source vector of type (x, y) ∈ TX1X2 Qn(xy) = exp{−n(D(PX1X2||Q)+ H(X1X2))} 23Proof outline (cont’d)and the decoding conditions • minimum entropy decoder:H(X˜1X˜2) ≤ H(X1X2)• maximum a posteriori probability decoder: D(P ˜||Q)+ H(X˜1X˜2) ≤ D(PX1X2||Q)+ H(X1X2)X1X˜2to obtain the result 24Conclusions• Distributed randomized network coding can achieve distributed compression of correlated sources • Error exponents generalize results for linear Slepian Wolf codiin • Further work: investigation of non-uniform code distributioons other types of codes, and other decoding schemes 25MIT OpenCourseWarehttp://ocw.mit.edu 6.441 Information Theory Spring 2010 For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms.