LECTURE 20 Last time: Gaussian channels with feedback • Upper bound to benefit of capacity• Lecture outline Multiple access channels • Coding theorem • Capacity region for Gaussian channels • Reading: Section 14.1-14.3. Multiple access channelsSeveral users share the same medium What is the right metric? Joint informatiion User 1 has rate R1 and user 2 has rate R2 How do we relate them to mutual informatiionModel: Yi = X1i + X2i + NiLiao and Ahlswede (independently, 1972)R1 ≤ I(X1; Y |X2) R2 ≤ I(X2; Y |X1)R1+ R2 ≤ I((X1,X2); Y )� Coding theorem mi: message sent by user i mi: decoded message for user i Pe1(Pe2): probability that the decoded code-word for user 1 (2) is different from that sent by user 1 (2) while the decoded code-word for user 2 (1) is the same as the one sent by user 2 (1) (such errors will be denoote as errors of type 1 (2)) Pe1,2: probability that the decoded code-words for both users 1 and 2 are different from those sent by those users (such an error will be denoted as error of type 3) We begin by bounding the probability of errro with an exponential argument and thenwe explore the behavior of that argumentCoding theorem We first consider errors of type 1 -results for errors of type 2 can be derived analogouusl We denote Pe1,m1,m2 the probability that an error of type 1 occurs conditioned on messages m1 and m2 being sent Using the overbar to denote expectation Pe1,m1,m2 = �y �x1 �x2 fX1(x1) fX2(x2) fY |X1,X2(y|x1,x2) P ��(����|��� dx2dx1dy.m1= m1) ∩ m2= m2y, x1,x2Using the union bound, we obtain P ��(������m1= m1) ∩ m2= m2y, x1,x2⎧�|≤ ⎫ρ ⎨� P ��(���|y, x1,x2���⎬ ⎩m=�m1 m1= m) ∩ m2= m2⎭ ∀0 ≤ ρ ≤ 1.�� � Coding theorem Using arguments similar to those for the single user strong coding theorem, we can establish ∀ρ ∈ [0, 1], fX1(x1) and fX2(x2) probabiliit density functions for X1 and X2, respectivvely we have Pe1,m1,m2 ≤ exp �−N �−ρR1+ E1 �ρ, fX1(x1) , fX2(x2)���0 where we have defined, E01 �ρ, fX1(x1) , fX2(x2)� = −N 1 ln fX2(x2)yx2�� 1 �1+ρ ⎫fX1(x) fY X,X2 �yx,x2�1+ρ dx dx2dy⎬ x ||⎭ Coding theoremIt now suffices to determine the behavior of the exponent to determine whether the upper bound to error probability becomes vanishingly small The following lemma parallels the one for the one-user case If I (X1; Y |X2) > 0, then for all 1 ≥ ρ ≥ 0 we have ∂NE01 �ρ, fX1(x1) , fX2(x2)� I (X1; Y |X2) ≥ ∂ρ > 0 (1) E01 �ρ, fX1(x1) , fX2(x2)� ≥ 0 (2) ∂2NE01 �ρ, fX1(x1) , fX2(x2)� ∂ρ2 ≤ 0 (3) ∂E01 �ρ, fX1(x1) , fX2(x2)�⎪ = I (X1; Y |X2) . ∂ρ N ρ=0 (4) Coding theoremLet q1,N , q2,N be a pair of probability densiit functions for the codewords of length N of users 1 and 2 In order for E01 �ρ, q1,N, q2,N�ρR1−in [0, 1],necessary and sufficient thatto bestrictly positive forsome ρit is⎧⎨ ⎩∂E01 �ρ, q1,N, q2,N �− R1∂ρ ⎪ ⎫⎬ ⎭ρ=0> 0.We have that: For all fX1(x1) , fX2(x2) probability density functions for X1, X2, we have I(X1;YX2)|>R1 ≥ 0N ⇒∃ρ ∈ [0, 1] s.t.0 E1 �ρ, fX1(x1) , fX2(x2)� − R1ρ> 0 We can establish analogous results for erroor of type 2 and 3Coding theorem Let us define Emin = min �maxρ �E01 �ρ, q1,N, q2,N � − R1ρ� , maxρ �E2 �ρ, fX1(x1) , fX2(x2)� − R2ρ� ,0 maxρ �E03 �ρ, q1,N, q2,N � − (R1+ R2) ρ�� where E02 and E03 is defined analogously to E01. We may state the following theorem: For allfX1(x1) , fX2(x2) probability density functions for X1, X1, for any messages m1 and m2 of users 1 and 2, we have P em1,m2 ≤ 3e−NEmin and I �X1; Y |X2� >R1 ≥ 0 and N I �X2; Y |X1� >R2 ≥ 0 and N I ��X1,X2� ; Y � N >R1+ R2 ≥ 0 ⇒ Emin > 0 Capacity region Cover-Wyner region for two usersCapacity regionConsider AWGN Multiple-access channel, user i has energy σ2 X1 Pentagon: dominant face corresponds to� σ2+σ2 �1ln 1+ X1 X2 2 σ2 N Interference cancellation at the corners: � σ2 �� σ2 ���12ln 1+ σ2 X+1 σ2 , 12ln 1+ σX22 X2 NN �1 � σ2 �� σ2 �� ln 1+ X1 , 1ln 1+ X2 2 σ22 σ2+σ2 NX1 N without interference cancellation: σ2 σ2�12 ln � 1+ σ2 X+1 σ2 � , 12 ln � 1+ σ2 X+2 σ2 �� X2 NX1 N Recall DS-CDMA example Capacity region� σ2 �� σ2 ���W1 X1 W2 X2FDMA: 2 ln 1+ W1σ2 , 2 ln 1+ W2σ2 NN for equal energies, equal W s desirable TDMA: let α be the fraction of time that user 1 transmits �� σ2 �� σ2 ��αX1 X2 2ln 1+ ασ2 , 1−2 α ln 1+ (1−α)σ2NNfor equal energies, α =0.5 desirable How do we achieve points on the dominant face, that yields maximum sum rate? First way: time share between the corners Other way: rate splitting Capacity regionMake one user (say user 1) into two virtualusers (virtual user 1 and virtual user 3) andsplit energy between these two virtual usersVirtual user 1 rate: � ασ2 �1ln 1+ X1 2 σ2 +(1−α)σ2+σ2 NX1 X2 User 2 rate: � σ2 �1ln 1+ X2 2 σ2 +(1−α)σ2 NX1 Virtual user 3 rate: � (1−α)σ2 �1ln 1+ X1 2 σ2 N Capacity region We have + ln+ ln= ln= ln⎛⎝ασ211+ X1 σ2 +(1 − α)σ2 NX1 ln+ σ2 X2 2⎛⎝⎞⎠σ2 X211+σ2 N ⎞⎠+ (1 − α)σ2 X1 2⎛⎝(1 − α)σ2 X1 σ2 11+2N⎛⎝⎞⎠⎛⎝σ2 X1 σ2 X2 σ2 N 111+ln1++σ2+ σ2 X2 N22⎛⎝⎞⎠σ2+ σ2 X1 X211+σ2 N2⎞⎠⎞⎠��Capacity region If we have σ2 X21= ln then R1 is defined as 1+R2σ2 +(1−α)σ2, NX1 2⎛⎝⎞⎠− R2σ2+ σ2 X1 X2 σ2 N 12ln1+⎛⎝⎞⎠ασ2 X11= ln+ lnOne variable provides all the necessary degrree of freedom 1+σ2 N ⎞⎠ + (1 − α)σ2 X1 + σ2 X2 2⎛⎝(1 − α)σ2 X1 σ2 11+2NCapacity region In general, for µ users, the capacity region is �i∈S Ri ≤ I((Xi)i∈S; Y |(Xi)i�∈S), ∀S ⊂{1,...,µ} We have 2µ − 1 pseudo-users are sufficient to achieve any point on the multiple-access dominant face 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.