6.441 Transmission of Information April 25, 2006Lecture 18Lecturer: Madhu Sudan Scribe: Xiaomeng ShiReview of Last LectureGaussian Channel• Noise ∼ N (0, σ2)• Input power constraint P• Capacity achieving input is Gaussian with variance P• Capacity:12log(1 +Pσ2).Colored Gaussian Channels• Blocks of n elements transmitted each time• The additive noise Z ∈ Rnis multivariate gaussian with covariance matrix KZ(noise with memo ry)• Input signal X ∈ Rnhas covariance matrix KX• Input power constraint is nP , ie. trace(KX) ≤ nP .• Capacity (without feedback):Cn=12log|KX+ KZ||KZ|• Unlike memoryless channels, in channels with memory, feedback may increase capacity by as muchas12bit. A colored Gaussian channel with feedback has capacityCF B,n= maxKX:tr(KX)≤nP12log|KX+Z||KZ|≤ Cn+12Network Information TheorySo far, we have only co ns idered single transmitter single receiver communication systems as shown onthe left side of Figure 1. More generally, practical communication systems are more complex and maycontain multiple senders and/or multiple receivers in various configurations. The second plot in Figure 1illustrates such a system. The channel is not dedicated to one communication link, but shared betweenmultiple user s. Network information theory studies problems in such settings. There are many unsolvedproblems in network information theory, but some special networks are better understood than others.One example is the multiple access (MA) channel.The Multiple Access ChannelThe multiple acce ss has many (m) senders and one receiver:An example of MA channels is the ethernet. A MA channel can be charaterized by its input alphabetΩX1, ΩX2, . . . , ΩXm, output a lphabet ΩY, and probability transition function PY |X1,...,Xm. One questionwe would like to ask is, suppose the sources generate information at rate Ri, i ∈ {1, . . . , m}. Is it feasibleto transmit all mes sages correctly? Next we look at some simple examples of multiple access channelsto study what rates are feasible.18-1Sender-Channel-6FeedbackReceiverFigure 1: Single Channel vs. Network...S3V-Enc3-S2W-Enc2-S1X-Enc1-Channel-YDec-Figure 2: Multiple Access ChannelExamples of Multiple Access ChannelsParallel Channel: Y = (X1+ Z1, X2+ Z2)Achievable Rates: R1≤ C1(X1→ X1+ Z1) , R2≤ C2(X2→ X2+ Z2)X1X1+ Z1-C1-X2X2+ Z2-C2-00000000000000000000000000000000000000000000000000000000000000001111111111111111111111111111111111111111111111111111111111111111R1R2Figure 3: Parallel MA ChannelBinary Symmetric: Y = X1+ X2+ Z(mod2), X1, X2∈ { 0, 1}, Z ∼ Bern(p)• Setting X2= 0 achieves R1= 1 − H(p)• Setting X1= 0 achieves R2= 1 − H(P )• Time sharing between these two points gives a straight line R1+ R2= 1 − H(p).Binary Erasure MA Channel: Y = X1+ X2The binary e rasure MA channel (first plot in Figure 5) adds its two inputs.First, note:18-2X2X1Y=X1+X2+Z (mod 2)Z000000000000000000000000000000000000000000000000000000000000000000000000111111111111111111111111111111111111111111111111111111111111111111111111R1R2Figure 4: Bina ry Symmetric MA C hannel• Set X2= 0 ⇒ noiseless channel with rate R1≤ 1.• Set X1= 0 ⇒ R2≤ 1• Time sharing gives a triangular sha ped capacity region as in the symmetric channel Y = X1+X2+ Z(mod 2) case.Can we do better?The answer is yes:• Assume R1= 1, ie., X1is always transmitted reliably.• Decode X2, regarding X1as noise (second plot in Figure 5), X1∼Bern(12).• The MA channel looks like a BEC for X2(last plot in Figure 5), R2=12.X2X1Y=X1+X2X2X1YX2 01Y011/21/2?Figure 5: Binary Erasure MA Channel∴ (1, 0), (1,12), (12, 1), (0, 1) are achievable rate pairs.Time sharing then gives the following achievable rate region:18-300000000000000000000000000000000000000000000000000000000000000001111111111111111111111111111111111111111111111111111111111111111000000001111111100000000111111111/2 11R2R11/2Figure 6: Achievable rate region of Binary Erasur e MA ChannelMultiple Access Gaussian Channel• var(X1) ≤ P1, var(X2) ≤ P2, Z ∼ N (0, σ2)X1X2ZYFigure 7: Multiple Access Gaussian Channel• Set X2= 0 ⇒ 0 ≤ R1≤12ln(1 +P1σ2)• Set X1= 0 ⇒ 0 ≤ R2≤12ln(1 +P2σ2)• Decode one input regarding the other as noise ⇒ R1+ R2≤12ln(1 +P1+P2σ2)The achievable region of a multiple acc ess gaussian channel has the general shape same as Figure 6,except the vertices on the R1, R2axis are loca ted at0,12ln(1 +P2σ2),12ln(1 +P1σ2), 0, and the slantedboundary line is R1+ R2≤12ln(1 +P1+P2σ2).It can also be shown that instead of time-sharing, frequencydivision multiplexing can achieve the following capacity region:R1R2Figure 8: MA Gaussian Channel: Rate pairs achieved by FDMAchievable Rate PairsFor a multiple access channel, what doe s it mean exactly to have a achievable rate pair (R1, R2)?18-4• (R1, R2) is achievable if there exis tEncoding function: X1: {1, . . . , 2R1n} −→ (ΩX1)nX2: {1, . . . , 2R2n} −→ (ΩX2)nDecoding function: Y : (ΩY)n−→ {1, . . . , 2R1n} × {1, . . . , 2R2n}such that decoding err or probability approaches 0 when transmitting the messa ges w1, w2independentlygenerated (uniformly) on codebooks of size 2R1nand 2R2n:w1∈ uniformaly on {1, . . . , 2R1n} w2∈ uniformaly on {1, . . . , 2R2n}• As an illustration:w1∈ { 1, . . . , 2R1n}X1(w1)-Enc1-w2∈ { 1, . . . , 2R2n}X2(w2)-Enc2-Channel-YDec-ˆw1, ˆw2If ( ˆw1, ˆw2) = (w1, w2) with probability → 1, the rate pair (R1, R2) is achievable.What rate pairs are achievable?Theorem the rate pair (˜R1,˜R2) is achievable iff it is in the convex hull of points (R1, R2) such thatthere exist independent distributions PX1, PX2such that0 ≤ R1≤I1= I(X; Y |W )0 ≤ R2≤I2= I(W ; Y |X)R1+ R2≤I3= I(X, W ; Y