CS代写 COMP2610/6261 - Information Theory

COMP2610/6261 – Information Theory
Lecture 20: Joint-Typicality and the Noisy-Channel Coding Theorem
U Logo Use Guidelines Robert C. Williamson
logo is a contemporary n of our heritage.

presents our name, ld and our motto:
earn the nature of things.
authenticity of our brand identity, there are n how our logo is used.
go – horizontal logo
go should be used on a white background. ludes black text with the crest in Deep Gold in
rinting is not available, the black logo can hite background.
e used white reversed out of a black occasionally a neutral dark background.
Research School of Computer Science
Preferred logo
Black version
October 24th, 2018

Channel Capacity: Recap
The largest possible reduction in uncertainty achievable across a channel is its capacity
Channel Capacity
The capacity C of a channel Q is the largest mutual information between its input and output for any choice of input ensemble. That is,
C = maxI(X;Y) pX

Block Codes: Recap
(N,K) Block Code
Given a channel Q with inputs X and outputs Y, an integer N > 0, and
K >0,an(N,K)BlockCodeforQisalistofS=2K codewords C = {x(1), x(2), . . . , x(2K )}
where each x(s) ∈ X N consists of N symbols from X .
RateofablockcodeisK =log2S NN

Reliability: Recap
s Encoder x Q y Decoder in
Probability of (Block) Error
Given a channel Q the probability of (block) error for a code is pB = P(sout ̸= sin) = 􏰄 P(sout ̸= sin|sin)P(sin)
and its maximum probability of (block) error is
pBM =maxP(sout ̸=sin|sin) sin

The Noisy-Channel Coding Theorem: Recap Informal Statement
Recall that a rate R is achievable if there is a block code with this rate and arbitrarily small error probability
We highlighted the following remarkable result:
Noisy-Channel Coding Theorem (Informal)
If Q is a channel with capacity C then the rate R is achievable if and only if R ≤ C, that is, the rate is no greater than the channel capacity.

1 Noisy-Channel Coding Theorem
2 Joint Typicality
3 Proof Sketch of the NCCT
4 Good Codes vs. Practical Codes
5 Linear Codes

The Noisy-Channel Coding Theorem Formal Statement
Recall: a rate is achievable if for any tolerance ε > 0, an (N , K ) code with rate K /N ≥ R exists with max. block error pBM < ε The Noisy-Channel Coding Theorem Formal Statement Recall: a rate is achievable if for any tolerance ε > 0, an (N , K ) code with rate K /N ≥ R exists with max. block error pBM < ε The Noisy-Channel Coding Theorem (Formal) 1 Any rate R < C is achievable for Q The Noisy-Channel Coding Theorem Formal Statement Recall: a rate is achievable if for any tolerance ε > 0, an (N , K ) code with rate K /N ≥ R exists with max. block error pBM < ε The Noisy-Channel Coding Theorem (Formal) 1 Any rate R < C is achievable for Q 2 If probability of bit error pb := pB /K is acceptable, (N , K ) codes exists with rates K ≤R(pb)= C N 1−H2(pb) The Noisy-Channel Coding Theorem Formal Statement Recall: a rate is achievable if for any tolerance ε > 0, an (N , K ) code with rate K /N ≥ R exists with max. block error pBM < ε The Noisy-Channel Coding Theorem (Formal) 1 Any rate R < C is achievable for Q 2 If probability of bit error pb := pB /K is acceptable, (N , K ) codes exists with rates K ≤R(pb)= C N 1−H2(pb) 3 For any p, we cannot achieve a rate greater than R(p) with probability of bit error p. The Noisy-Channel Coding Theorem Formal Statement Recall: a rate is achievable if for any tolerance ε > 0, an (N , K ) code with rate K /N ≥ R exists with max. block error pBM < ε The Noisy-Channel Coding Theorem (Formal) 1 Any rate R < C is achievable for Q 2 If probability of bit error pb := pB /K is acceptable, (N , K ) codes exists with rates K ≤R(pb)= C N 1−H2(pb) 3 For any p, we cannot achieve a rate greater than R(p) with probability of bit error p. The Noisy-Channel Coding Theorem Formal Statement Recall: a rate is achievable if for any tolerance ε > 0, an (N , K ) code with rate K /N ≥ R exists with max. block error pBM < ε The Noisy-Channel Coding Theorem (Formal) 1 Any rate R < C is achievable for Q 2 If probability of bit error pb := pB /K is acceptable, (N , K ) codes exists with rates K ≤R(pb)= C N 1−H2(pb) 3 For any p, we cannot achieve a rate greater than R(p) with probability of bit error p. Notethataspb → 21,R(pb)→+∞,whileaspb →{0,1},R(pb)→C,so we cannot achieve rate greater than C with probability of bit error arbitrarily small Implications of NCCT Suppose we know a channel has capacity 0.6 bits Implications of NCCT Suppose we know a channel has capacity 0.6 bits We cannot achieve a rate of 0.8 with arbitrarily small error Implications of NCCT Suppose we know a channel has capacity 0.6 bits We cannot achieve a rate of 0.8 with arbitrarily small error We can achieve a rate of 0.8 with probability of bit error 5%, since 0.6 = 0.8408 > 0.8 1−H2 (0.05)

1 Noisy-Channel Coding Theorem
2 Joint Typicality
3 Proof Sketch of the NCCT
4 Good Codes vs. Practical Codes
5 Linear Codes

Joint Typicality
Recall that a random variable z from Z N is typical for an ensemble Z
whenever its average symbol information is within β of the entropy H(Z) 􏰇􏰇􏰇􏰇−N1 log2 P(z) − H(Z)􏰇􏰇􏰇􏰇 < β Joint Typicality Recall that a random variable z from Z N is typical for an ensemble Z whenever its average symbol information is within β of the entropy H(Z) 􏰇􏰇􏰇􏰇−N1 log2 P(z) − H(Z)􏰇􏰇􏰇􏰇 < β Joint Typicality A pair of sequences x ∈ ANX and y ∈ ANY , each of length N, are jointly typical (to tolerance β) for distribution P(x,y) if 1 x is typical of P(x) 2 y is typical of P(y) 3 (x, y) is typical of P(x, y) The jointly typical set of all such pairs is denoted JNβ. [z = x above] [z = y above] [z = (x, y) above] àà2: Jointly-typical sequences Joint Typicality TEhxeamjoipnletly-typical set JNβ is the set of all jointly-typical sequence pairs of length Nà Example. Here is a jointly-typical pair of length N = àà for the ensemble P x,y in which P x has pà,p = à.9,à. and P y|x corresponds to a Example (pX = (0.9, 0.1) and BSC with f = 0.2): binary symmetric channel with noise level à.2à x àààààààààààààààààààààààààààààààààààààààààààààààààààààààààààààààààààààààààààààààààààààààààà y àààààààààààààààààààààààààààààààààààààààààààààààààààààààààààààààààààààààààà Notice that x has à 1s, and so is typical of the probability P x at any toleranceβ àandyhas261s,soitistypicalofP y becauseP y= =à.26 à and x and y di!er in 2à bits, which is the typical number of ßips for this channelà Joint typicality theorem. Let x,y be drawn from the ensemble XY N xhas101’s(c.f.p(X =1)=0.1) P x,y = P xn,yn . y has 26 1’s (c.f. p(Y =n=1 ) = (0.8)(0.1) + (0.2)(0.9) = 0.26) Then à the probability that x, y are jointly typical to tolerance β tends x, y differ in 20 bits (c.f. p(X ̸= Y) = 0.2) 􏰜 NH X,Y 2àthenTuhmisbeirsoefsjosinetnlyt-itaylpicnalasdeqduiteinocnest|oJth|eisacblosveetotw2ofactsà to as N → ∞à To be precise, 3à if x′ ∼ XN and y′ ∼ YN, iàeà, x′ and y′ are independent samples |JNβ|≤2N H X,Y +β à àà3 with the same marginal distribution as P x, y , then the probability Joint Typicality University Press 2003. On-screen viewing permitted. Printing not permitted. http://www.cambridge.org/0521642981 k for 30 pounds or $50. See http://www.inference.phy.cam.ac.uk/mackay/itila/ for links. set. The horizontal direction à The Noisy-Channel Coding Theorem There are approximately: AN Figure 10.2. The jointly-typical ' X E 2NH(X) typical x ∈ AN T strings of length N . The N represents A , the set of all input direction represents AY , the set of all output strings of conceivable input–output pairs. Each dot represents a length N . The outer box contains all 2 jointly-typical pair of sequences (x, y). The total number of N T TNHYX A 2 jointly-typical sequences is about NH Y 2 c Proof of the noisy-channel coding theorem Joint Typicality University Press 2003. On-screen viewing permitted. Printing not permitted. http://www.cambridge.org/0521642981 k for 30 pounds or $50. See http://www.inference.phy.cam.ac.uk/mackay/itila/ for links. X E 2NH(X) typical x ∈ AN set. The horizontal direction à The Noisy-Channel Coding Theorem There are approximately: AN Figure 10.2. The jointly-typical represents A , the set of all input NH X NH(Y) NY direction represents AY , the set of XN 2 strintgysopfilecngathlNy. T∈heAvertical all output strings of length N . The outer box contains all conceivable input–output pairs. Each dot represents a 2 jointly-typical pair of sequences (x, y). The total number of N T TNHYX A 2 jointly-typical sequences is about NH Y 2 c Proof of the noisy-channel coding theorem Joint Typicality University Press 2003. On-screen viewing permitted. Printing not permitted. http://www.cambridge.org/0521642981 k for 30 pounds or $50. See http://www.inference.phy.cam.ac.uk/mackay/itila/ for links. X E 2NH(X) typical x ∈ AN set. The horizontal direction à The Noisy-Channel Coding Theorem There are approximately: AN Figure 10.2. The jointly-typical NH X NH(Y) represents A , the set of all input XN 2 strintgysopfilecngathlNy. T∈heAvertical direction represents AY , the set of NH(X,Y) N N 2 all outputyt sptrincgas olf l(enxgt,hyN). ∈ A × A XY The outer box contains all conceivable input–output pairs. Each dot represents a jointly-typical pair of sequences (x, y). The total number of jointly-typical sequences is about 2 N T TNHYX A 2 NH Y 2 c Proof of the noisy-channel coding theorem Joint Typicality University Press 2003. On-screen viewing permitted. Printing not permitted. http://www.cambridge.org/0521642981 k for 30 pounds or $50. See http://www.inference.phy.cam.ac.uk/mackay/itila/ for links. X E 2NH(X) typical x ∈ AN set. The horizontal direction à The Noisy-Channel Coding Theorem There are approximately: AN Figure 10.2. The jointly-typical NH X NH(Y) represents A , the set of all input XN 2 strintgysopfilecngathlNy. T∈heAvertical direction represents AY , the set of NH(X,Y) N N 2 all outputyt sptrincgas olf l(enxgt,hyN). ∈ A × A XY The outer box contains all 2 conceivatbylepinipcuat–oluytpugt piavires.n x 2 Each dot represents a jointly-typical pair of sequences (x, y). The total number of jointly-typical sequences is about N T TNHYX A 2 NH Y 2 c Proof of the noisy-channel coding theorem Joint Typicality University Press 2003. On-screen viewing permitted. Printing not permitted. http://www.cambridge.org/0521642981 k for 30 pounds or $50. See http://www.inference.phy.cam.ac.uk/mackay/itila/ for links. X E 2NH(X) typical x ∈ AN set. The horizontal direction à The Noisy-Channel Coding Theorem There are approximately: AN Figure 10.2. The jointly-typical NH X NH(Y) represents A , the set of all input XN 2 strintgysopfilecngathlNy. T∈heAvertical direction represents AY , the set of NH(X,Y) N N 2 all outputyt sptrincgas olf l(enxgt,hyN). ∈ A × A XY The outer box contains all 2 conceivatbylepinipcuat–oluytpugt piavires.n x 2 Each dot represents a jointly-typical pair of sequences (x, y). The total number of jointly-typical sequences is about N T TNHYX A 2 Thus, by selecting independent typical vectors, we arrive at a jointly typical vector with probability approximately NH Y 2 NH(X,Y) 2 −NI(X;Y) 2NH(X) ·2NH(Y) c Proof of the noisy-channel coding theorem Joint Typicality University Press 2003. On-screen viewing permitted. Printing not permitted. http://www.cambridge.org/0521642981 k for 30 pounds or $50. See http://www.inference.phy.cam.ac.uk/mackay/itila/ for links. X E 2NH(X) typical x ∈ AN set. The horizontal direction à The Noisy-Channel Coding Theorem There are approximately: AN Figure 10.2. The jointly-typical NH X NH(Y) represents A , the set of all input XN 2 strintgysopfilecngathlNy. T∈heAvertical direction represents AY , the set of NH(X,Y) N N 2 all outputyt sptrincgas olf l(enxgt,hyN). ∈ A × A XY The outer box contains all 2 conceivatbylepinipcuat–oluytpugt piavires.n x 2 Each dot represents a jointly-typical pair of sequences (x, y). The total number of jointly-typical sequences is about N T TNHYX A 2 Thus, by selecting independent typical vectors, we arrive at a jointly typical vector NH Y 2 with probability approximately NH(X,Y) 2 −NI(X;Y) 2NH(X) · 2NH(Y) Here we used I (X ; Y ) = H (X ) + H (Y ) − H (X , Y ) NH X Y 2 c Proof of the noisy-channel coding theorem Joint Typicality Theorem Copyright Camb􏱤 Joint Typicality Theorem For all tolerances β > 0
1 Almost every pair is eventually jointly typical P((x,y)∈JNβ)→1asN →∞
Let x,y be drawn from (XY)N with P(x,y) = 164
P(x ,y ). nn
ridge University Press 2003. On-screen viewing permitted. Printing not p You can buy this book for 30 pounds or $50. See http://www.inference.phy.cam.ac.uk/m
T
2
NH Y 2

10.3 Proof of the noisy-channel coding theorem
Imagine that we wish to prove that there is a baby in a class
babies who weighs less than à kgà Individual babies are diðcu
o weighà ShannonÕs method of solving the task is to scoop up

Joint Typicality Theorem
Copyright Camb􏱤
Joint Typicality Theorem
For all tolerances β > 0
1 Almost every pair is eventually jointly typical P((x,y)∈JNβ)→1asN →∞
Let x,y be drawn from (XY)N with P(x,y) = 164
P(x ,y ). nn
ridge University Press 2003. On-screen viewing permitted. Printing not p You can buy this book for 30 pounds or $50. See http://www.inference.phy.cam.ac.uk/m
T
2
NH Y 2

2 The number of jointly typical sequences is roughly 2NH(X,Y):
|JNβ| ≤ 2N(H(X,Y)+β)
10.3 Proof of the noisy-channel coding theorem
Imagine that we wish to prove that there is a baby in a class
babies who weighs less than à kgà Individual babies are diðcu
o weighà ShannonÕs method of solving the task is to scoop up

Joint Typicality Theorem
Copyright Camb􏱤
Joint Typicality Theorem
For all tolerances β > 0
1 Almost every pair is eventually jointly typical P((x,y)∈JNβ)→1asN →∞
Let x,y be drawn from (XY)N with P(x,y) = 164
P(x ,y ). nn
ridge University Press 2003. On-screen viewing permitted. Printing not p You can buy this book for 30 pounds or $50. See http://www.inference.phy.cam.ac.uk/m
T
2
NH Y 2

2 The number of jointly typical sequences is roughly 2NH(X,Y):
|JNβ| ≤ 2N(H(X,Y)+β)
3 For x′ and y′ drawn independently from the
marginals of P(x, y),
P((x′,y′) ∈ JNβ) ≤ 2−N(I(X;Y)−3β)
10.3 Proof of the noisy-channel coding theorem
Imagine that we wish to prove that there is a baby in a class
babies who weighs less than à kgà Individual babies are diðcu
o weighà ShannonÕs method of solving the task is to scoop up

1 Noisy-Channel Coding Theorem
2 Joint Typicality
3 Proof Sketch of the NCCT
4 Good Codes vs. Practical Codes
5 Linear Codes

The Noisy-Channel Coding Theorem
Let Q be a channel with inputs AX and outputs AY . Let C = maxpX I(X;Y) be the capacity of Q and H2(p) = −p log2 p − (1 − p) log2(1 − p).
The Noisy-Channel Coding Theorem
1 Any rate R < C is achievable for Q (i.e., for any tolerance ε > 0, an (N, K ) code with rate K /N ≥ R exists with max. block error pBM < ε) 2 If probability of bit error pb := pB /K is acceptable, there exist (N , K ) codes with rates K ≤R(pb)= C N 1−H2(pb) 3 For any pb, rates greater than R(pb) are not achievable. The Noisy-Channel Coding Th 程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts