LECTURE 18Last time:White Gaussian noise • Bandlimited WGN • Additive White Gaussian Noise (AWGN) • channelCapacity of AWGN channel• Application: DS-CDMA systems • Spreading • Coding theorem • Lecture outlineGaussian channels: parallel • colored noise • inter-symbol interference • general case: multiple inputs and out₭ puts Reading: Sections 10.4-10.5. Parallel Gaussian channelsYj = Xj + Nj where σ2j is the variance for channel j (supersscrip to show that it could be somethhin else than several samples from a singgl channel) the noises on the channels are mutually indepeenden the constraint on energy, however, is over all the channels E ��kj=1(Xj)2� ≤ P Parallel Gaussian channelsHow do we allocate our resources across channels when we want to maximize the total mutual information: We seek the maximum over all fX1,...,Xk(x1, . . . , xk)s.t. E ��jk =1(Xj)2� ≤ P of I �(X1,...,Xk); (Y 1,...,Y k)� Intuitively, we know that channels with good SNR get more input energy, channels with bad SNR get less input energy Parallel Gaussian channelsI �(X1,...,Xk); (Y 1,...,Y k)� = h(Y 1,...,Y k) − h(Y 1,...,Y k X1,...,Xk) = h(Y 1,...,Y k) − h(N1,...,Nk|)k= h(Y 1,...,Y k) − � h(Nj)j=1kk≤ � h(Yj) − � h(Nj) j=1 j=1k� 1 ln � 1+ Pj �≤ j=1 2 σj2 where E[(Xi)2] = Pi hence �kj=1 Pj ≤ P equality is achieved for the Xjs independent and Gaussian (but not necessarily IID) Parallel Gaussian channels Hence (X1,...,Xk) is 0-mean with ⎡ P 10 ... 0 ⎤ ⎢ 0 P 2 ... 0 ⎥ =Λ(X1,...,Xk) ... ... ... ...⎣ 00 ... Pk ⎦ the total energy constraint is a constraint we handle using Lagrange multipliers The function we now consider is 1�kj=1 2ln �1+ σPjj 2 � + λ �kj=1 Pj after differentiating with respect to Pj 11 Pj+σj2+ λ =02 so we want to choose the Pj + Nj to be constant subject to the additional constrain that the Pjs must be non-negative Select a dummy variable ν then �kj=1(ν − σj2)+ = P Parallel Gaussian channels Water-filling graphical interpretationRevisit the issue of spreading in frequencyColored noiseYi = Xi + Ni for n time samples Λ(N1,...,Nn) is not a diagoona matrix: colored stationary GN Energy constraint n 1E[Xi 2] ≤ P Example: we can make I �(X1,...,Xn); (Y 1,...,Y n)� = h(Y 1,...,Y n) − h(Y 1,...,Y n |X1,...,Xn) = h(Y 1,...,Y n) − h(N1,...,Nn) Need to maximize the first entropy Using the fact that a Gaussian maximizes entropy for a given autocorrelation matrix, we obtain that the maximum is 1 ln �(2πe)n� 2 |Λ(X1,...,Xn) +Λ(N1,...,Nn)|note that the constraint on energy is a constrrain on the trace of Λ(X1,...,Xn) Consider |Λ(X1,...,Xn) +Λ(N1,...,Nn)| Colored noiseConsider the decomposition QΛQT = Λ(N1,...,Nn), where QQT = I Indeed, Λ(N1,...,Nn) is a symmetric positive semi-definite matrix |Λ(X1,...,Xn) +Λ(N1,...,Nn)| = |Λ(X1,...,Xn)+ QΛQT | = |Q||QT Λ(X1,...,Xn)Q +Λ||QT | = |QT Λ(X1,...,Xn)Q +Λ| Also, trace �QT Λ(X1,...,Xn)Q� = trace �QQT Λ(X1,...,Xn) � = trace(Λ(X1,...,Xn)) so energy constraint on input becomes a constraint on new matrix QT Λ(X1,...,Xn)Q Colored noiseWe know that because conditioning reduces entropy, h(W, V ) ≤ h(W )+ h(V ) In particular, if W and V are jointly Gaussiian then this means that ln �� ≤ ln �σ2 � + ln �σ2 �|ΛW,V |VW hence |ΛW,V |≤ σ2 × σ2 VW the RHS is the product of the diagonal terms of ΛW,V Hence, we can use information theory to show Hadamard’s inequality, which states that the determinant of any positive definiit matrix is upper bounded by the produuc of its diagonal elements Colored noise Hence, |QT Λ(X1,...,Xn)Q+Λ| is upper bounded by the product �i(αi + λi) where the diagonal elements of QT Λ(X1,...,Xn)Q are the αis their sum is upper bounded by nP To maximize the product, we would want to take the elements to be equal to some constant At least, we want to make them as equal as possible αi =(ν − λi)+ where � αi = nP Λ(X1,...,Xn)= Q diag (αi)QT ISI channels= �TdYj k=0 αkXj−k + Nj we may rewrite this as Yn = AXn + Nn with some correction factor at the beginniin for Xs before time 1 A−1Yn = Xn + A−1Nn consider mutual information between Xn and A−1Yn -same as between Xn and Yn equivalent to a colored Gaussian noise channne spectral domain water-filling �General caseSingle user in multipath Yk = fkSk + Nk wherefk is the complex matrix with entries f [j, i]=⎧⎨ ⎩all paths mgm[j, j − i] for 0 ≤ j − i ≤ Δ0 otherwiseFor the multiple access model, each source has its own time-varying channel K� i=1 the receiver and the sender have perfect knowledge of the channel for all times In the case of a time-varying channel, this would require knowledge of the future behavvio of the channel the mutual information between input and output is I (Yk; Sk)= h (Yk) − h (Nk) kSik + NkYkfi=⎫⎬ ⎭General case We may actually deal with complex random variables, in which case we have 2k degrees of freedom We shall use the random vectors S�2k, Y �2k and N�2k, whose first k components and last k components are, respectively, the real and imaginary parts of the corresponding vectors Sk, Yk and Nk More generally, the channel may change the dimensionality of the problem, for instance because of time variations Y � 2k = f�22kk�S� 2k� + N� 2k Let us consider the 2k� by 2k� matrix f�22kk� Tf�22kk� Let λ1....,λ 2k� be the eigenvalues of f�22kk� Tf�22kk� These eigenvalues are real and non-negative� � General caseUsing water-filling arguments similar to theones for colored noise, we may establishthat maximum mutual information per secﾭ2k�ondis 1 i=1ln 1+ uiλi 2T WN02where ui is given by � WN0�+ ui = γ − 2λi and 2k��ui = TPW i=1 General caseLet us consider the multiple access case We place a constraint, P , on the sum of all the K users’ powers The users may cooperate, and therefore act as an antenna array Such a model is only reasonable if the users are co-located or linked to each other in some fashion There are M =2Kk� input degrees of freeddo and 2k output degrees of freedom [Y [1] ...Y [2k]]= f��M 2k �S�[1] ... S�i[M]�T +[N[1] ...N[2k]] where we have defined �S�[1] ... S�[M]� = �S1[1] ...S1[2k�],S2[1] ...S2[2k�], . . . , SK[1] . . . SK[2k�]�f��2Mk = �f122kk�,f222kk�, . . . , fk 22kk� �General casef��M 2kT f��M 2k has M eigenvalues, all of which are real and non-negative and at most 2k of which are non-zero Let us assume that there are κ positive eigenvalues, which we denote λ�1,..., λ�κ We have decomposed our multiple-accesschannels into κ channels which may be interpprete as parallel independent channelsThe input has M − κ additional degrees of freedom, but those degrees of freedom do not reach the output The maximization along the active κ channeel may now be performed using water-filling techniques Let T be the duration of the transmission� General case We choose � N0W �+ ui = γ − 2λ�i for λ�i = 0, where γ satisfies �� γ − N20λ�Wi �+= TPW i such that λ�i=0�and ui satisfies 2k� ui = TPW i=1 We have reduced several channels, each with its own user, to a single channel with a composite user The sum of all the mutual informations averaage over time is upper bounded by 11 ⎛�γ − N0λWi �+ �⎞ � ln ⎜ 1+ 2�λi⎟ T 2 N0W i such that λ�i=0�⎝ 2 ⎠ 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.