6.441-21 Broadcast channels

LECTURE 21 Last time: Multiple access channels • Coding theorem • Capacity region for Gaussian channels • Lecture outline Broadcast channel • Gaussian degraded broadcast channel • Reading: Section 14.6. Broadcast channelSingle source, several receivers The information to the receivers may be the same, or user 2 may have a subset of user 1, or the users have different informatiio Example where the receivers have the same information: radio The rate is then no better than the worst-case channel Broadcast channelExample where user 2 may have a subsetof user 1: video user with better SNR obtains better resoluttio than user with worse SNR different rates over the Internet Does the separation theorem hold? Broadcast channelUsers have different information Example of person speaking two languages to two receivers who speak different languaage (orthogonal signals) Can do better than speaking to one half the time and to the other the rest of the time Communicate in Esperanto using binary code (of course!) By choosing arrangement of Language 1 and Language 2 words, communicate an extra bit (1 is Language 1 and 0 is language 2) to both users Esperanto is shared by both users (commmo information) Can we find a general framework to encompaas all of these different cases? Broadcast channel General model of a stationary memoryless broadcast channel for one input and two outputs: fY1n,Y2n|Yn �y1 n, y2 n|xn� = �in =1 pY1,Y2|X(y1i, y2i|xi) Receiver 1 has rate R1 and receiver 2 has rate R2 The encoding maps the information to the two receivers to a single codeword: n{1,..., 2nR1}×{1,..., 2nR2} �→ X (m1,m2) xn → Broadcast channel The decoding is done independently at each receiver i Yn �→ {1,..., 2nRi} nymi→ �An error occurs whenever �=�mi for i =1 mi or i =2 What is the drawback here? If we assume that for each user the messaage are uniformly distributed and that the two users have independent transmissions, then the above works well There is no requirement that the informatiio for the different users be uncorrelated, so we are not considering IID over {1,..., 2nR1for user 1 and {1,..., 2nR1} for user 2 } � � � � Broadcast channelHow do we take the common information into account? Look at common informatiio with rate R0 (remember the Esperanto) Theencodingmapstheinformationtothe Thedecodingisdoneindependentlyateach �two receivers to a single codeword: {1,..., 2nR0}×{1,..., 2nR1}×{1,..., 2nR2} �→ nX (m1,m2,m0) xn → receiver iYn �→ {1,..., 2nRi}×{1,..., 2nR0}mi mi 0)n (ymi,mAn error occurs whenever→= mi orfor i =1 or i =2i 0 Broadcast channelWhat happens to the separation theorem?By compressing for each user independently, then the messages are uniformly distributed over all possible messages for each user, but possibly this does not hold for the two messages jointly If we compress independently for each user, AEP no longer holds, so in general may not be optimum in terms of minimizing descriptiio of what we want to transmit Equivalently: if there is common informatiion because for instance the users are correllate in the information they need to receiive then we have been wasteful If we do the compression of all the data jointly, then not clear how the decoders work, because they are independent. Broadcast channel A rate triplet (R0,R1,R2) is achievable iff there exists a sequence of ((2nR0, 2nR1, 2nR2),n) codes that have probability of error vanish as n →∞ The capacity region is in general not known Not surprising when we consider the languuag example Exception: degraded broadcast channel, to be seen later For R0 ≤ min{R1,R2} for a broadcast channeel (R0,R1 − R0,R2 − R0) is an achievable triplet of rates with common information Broadcast channelAlthough the broadcast channel capacity region is not known in general, we do know that the region depends only fY1X(y1x)||and on fY2X(y2x)||Type 1 error: user 1 has an error, type 2 error: user 2 has an error, type 3 error: both have errors Over the channel for each user, the probabillit of errors of type 1 and 2 depends on the marginal pdf only The probability of error of type 3 is lower bounded by the probability that at least one user has an error and upper bounded by the sum of the probabilities that both have an error Degraded broadcast channelfY1,Y2X(y1,y2x)= fY1X(y1x)fY2Y1(y2y1)||||||XY1 Y2→→ Consider at first independent transmissions to the two receivers The capacity region is the closure of the (R1,R2) such that R2 ≤ I(U; Y2) R1 ≤ I(X; Y1|U) for some auxiliary U whose cardinality is less than that of any of the input and the outpuut Degraded broadcast channel Method: we generate codewords for user 2 by selecctin IID sequences Un using � fU (ui) and mapping each of the messages m2 in {1,..., 2nR2}onto some un(m2) for each possible un(m2), we generate a codeword for user 1 mapping (m1,m2) onto xn(m1,m2) using � fXU (xiui(m2))||Note: X is transmitted, U is not Decoding: user 1 decodes by looking at jointly typical (Un(m2),Y2 n) pairs user 2 can first look at typical (Un(m2),Y1 n) pairs having thus decoded m2, it can reconstituut Un(m2) and then look at jointly typical (Un(m2),Xn(m1,m2),Y1 n) triplet Degraded broadcast channelThe results for receivers with dependent information can be obtained by using the fact that if (R1,R2) is an achievable rate pair when we have independent informatiion then: For R0 ≤ R2 for a degraded broadcast channeel (R0,R1,R2−R0) is an achievable triplet of rates with common information U is decoded by both and carries the informattio of user 1, that is also received by user 2 Important example: degraded Gaussian broadcaas channel Y1= X + Z1 Y2= X + Z1+ Z2 Consider R0 is R2 � � Degraded broadcast channelEnergy constraint E on input The second user decodes m2 from U Rate R0 is clearly upper bounded by the case where we communicate with only user2 in mind: 12ln 1+ σ2+E σ2 N2 N1 In particular, we can always express R0 as 1 � (1−α)E � ln 1+ 2 αE+σ2+σ2 N2 N1 with the upper bound being achieved for α =0 � � | Degraded broadcast channelFor user 1: consider that we are trying to communicate the independent X, U over a channel with noise N1 From our coding theorem, user 1 first decoode m2 and is thus able to reconstitute U Knowing U, user 1 now tries to recover XU|Subtracting U, there is αE left for XU, which is R1 = 21ln 1+ σE2 N1 � � Degraded broadcast channelNote: the total rate at user 1 is less than if we had no broadcast Hark back to our multiple-access channel:thesum of the rates is upper bounded by ln 1+ σE2 N1 12⎛⎝⎞⎠−12ln⎛⎝1+12ln(1)α−E 2σ+ ⎞⎠ ⎞⎠ αE + σ2 N1 + (1 − α)EEσ21+N1N2⎛⎝E + σ2 αE + σ2+ σ2 N1 N2 N1 σ2 1= ln2αE + σ2+ σ2 N1 N2 N1⎛⎝E + σ2 αE + σ2+ σ2 N1 N2 N11= ln2σ2 σ2+ σ2 N1 N2 N1+ E⎛⎝N2 σα2E + (1 − α)+ Eσσ22 N2 =12ln1+σ2+ EN1N1⎞⎠⎞⎠MIT 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.