1. Solution in Tutorial 8.
Wehavep(Y =a)=0.5·0.25,p(Y =b)=0.5·0.5,p(Y =c)=0.5·0.75,andp(Y =d)=0.5·0.5. ThusH(Y)=1.9056. Similarly,H(Y |a)=H(Y |b)=H(Y |c)=H(0.5)=1. So,H(Y |X)=1. Thus, I(X; Y ) = 0.9056 bits.
perr =p(y̸=a)·p(x=a)+p(y̸=b)·p(x=b)+p(y̸=c)·p(x=c) = 0.5·0.25+0.5·0.25+0.5·0.5
We know that the capacity is the maximal mutual information. So, from (a), the capacity is at least 0.9056 bits. We know that we can transmit at rate below the capacity with arbitrarily small error probability. Thus, Calvin’s claim is possible.
Copyright By PowCoder代写 加微信 powcoder
We know that the capacity is at most min(log2 |X |, log2 |Y |) = 1.58. We know that we cannot transmit at rate above C while achieving bit error pb. Here, the maximal block error is 0.01, which bounds the
1−H2 (pb )
average probability of error, and hence the bit error. Here 1 − H2(0.1) = 0.9192, and so the maximal rate
is 1.58 = 1.7189 bits per transmission. Thus, Hobbes’ claim is not possible. 0.9192
COMP2610/COMP6261 Tutorial 9 Sample Solutions Tutorial 9: Stream and Noisy Channel Coding
Young Lee and
Tutors: and
Week 11 (16th – 20th Oct), Semester 2, 2017
3. UsingI(X;Y)=H(X)−H(X|Y)itiseasytoshowthat
I(X; Y ) = H2(p0) − qH2(p0)
since the first term is H(X) by definition of H2. The second term is H(X|Y ) because P(X = 0|Y = 1) = 0 andP(X =1|Y =0)=0andP(X =0|Y =?)=p0 andP(X =1|Y =?)=p1 andP(Y =?)=q. Using H(X|Y ) = y H(X|Y = y)P(Y = y) = 0.P(Y = 0) + 0.P(Y = 1) + H2(p0).P(Y =?) gives the above form for H(X|Y ).
When maximised over p0 the above gives
C =maxI(X;Y)=maxH2(p0)−q·H2(p0)=1−q
pX p0 since H2(p0) is maximised to 1 when p0 = 0.5.
The (2, 1) code required is {01, 10}. When 01 is passed through the Z -channel there is a probability of q that the 1 is flipped and so 00 is output. Similarly, if 10 is input then there is a probability q that 00 is output. By mapping 01 to 0; 10 to 1; and 00 to ? we see that this code simulates the erasure channel.
Because we can simulate the erasure channel with two uses of the Z-channel we can always convert any error- correcting code for the erasure channel into an error-correcting code for a two-use Z-channel. Therefore, a code with rate R on the erasure channel will have rate R/2 on the Z-channel.
Since the Noisy-Channel Coding Theorem says any rate up to the capacity C is achievable and we have shown how to convert any rate R code for the erasure channel into a R/2 rate code for the Z-channel the capacity of the Z-channel must be at least C/2. Thus, the capacity of the Z-channel with flip probability q is at least 12 (1 − q).
The reason this is a bound and not an exact derivation of the capacity is that we have implicitly used the uniform distribution (i.e., the one that maximises the erasure mutual information). This may not be the same distribution that maximises the mutual information for the Z-channel.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com