Today I came across a nice result on the distribution of eigen values of matrix , where the entries of are i.i.d. Gaussian distributed. The result says that the eigen value (in the decreasing order) of has the following distribution, for small .

Its quite useful for analysing many MIMO techniques, such as MRC, MRT.

The reference is a recent IT Paper: http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4544985&isnumber=4544949

### Author Archive

Many of you might know that over the weekend there was a AMD design contest. I was under the impression that such contests are coding heavy and it goes without saying that a potential turnoff for me. Thanks to my roommate, however, my impression changed significantly and I found out that majority of the problems were basically algorithmic puzzles. More importantly it turned out that once you found out the trick involved, the coding required was minimal.

I will give an example shortly. There are offcourse some problems on compiler design and related areas on which we have minimal knowledge. So to form an ideal team for these contests a partner majoring in CE/CS is a must.

Over the weekend me and my roommate (major CE) were able to solve 4 and half problems out of 5. Unfortunately, we were not able to submit our solution to the contest, since my roommate had to fly out of town and due to my “extraordinary” coding skills.

I am writing this post in hope that next year we would see someone from WNCG and especially from WSIL appearing on the LCD TV on the first floor as the winner of such a contest.

Example problem: Let z, l and m be a natural numbers, l less than m. Let p be a prime which appers in the prime factorization of z, e.g. 2 and 3 appear in the prime factorization of 24. The problem is to find out the number of natural numbers between l and m (including l and m) that have p ones in their binary representation.

The broadcast channel is a communication channel with a single transmitter that transmits independent information to multiple receivers. In information theory, capacity of a communication channel is defined as the maximum rate of information that can be transmitted from the transmitter to the receiver reliably. By reliable transmission we mean that the information can be decoded at the receiver with arbitrarily small probability of error. Let us assume that the broadcast channel has receivers, then a rate vector is said to be achievable on the broadcast channel if information can be transmitted reliably at rate from the transmitter to the receiver ,, simultaneously. The capacity of broadcast channel is defined as the convex hull of all achievable rate vectors. Finding the capacity of a general broadcast capacity has been a long standing open problem in information theory. In this article we will discuss the multiple input multiple output broadcast channel (MIMO-BC) whose capacity region has been found recently by Weingarten et. al.

The MIMO-BC model is as follows. A transmitter with antennas wants to transmit independent information to receivers, where receiver is equipped with antennas . Let be the signal transmitted by the transmitter, then the received signal received by receiver is given by where is a channel matrix and is the additive white Gaussian noise (AWGN) with covariance matrix .

For MIMO-BC, several transmission strategies have been proposed in literature, for example, superposition coding and dirty paper coding. In superposition coding, if is the signal for receiver then is transmitted by the transmitter. Dirty paper coding (DPC) is a technique developed by Costa for single input single output (SISO) AWGN channels when there is an interference signal present at the receiver together with AWGN. We assume the interference signal is known non causally at the transmitter. In this setting Costa showed that the capacity is which is exactly equal to the capacity of AWGN channel without any interference. Thus, DPC is shown to completely eliminate the effect of interference. Using DPC for the MIMO BC, if the signal for the first receiver is , then the signal for receiver is generated using as the interference signal. Similarly, the signal for the receiver is generated using as the interference signals and is transmitted from the transmitter. From now on we consider in this article for simplicity. With ,the rates and , simultaneously achievable for receiver and , are given by and where is the covariance matrix of . Changing the order of coding, i.e. first generating and depending on generating , and We denote the convex hull of all rate vectors achievable with DPC as .

As shown above, finding the achievable rate region of MIMO-BC is easy using different transmission strategies but proving that they are capacity achieving, i.e. rate more than the rate achieved by a particular transmission strategy is not achievable with reliable transmission constraint, is quite difficult. Weingarten et.al. solved this problem in their paper and showed that rates achieved with DPC are optimal for MIMO-BC.

Here we present the argument for symmetric MIMO Broadcast channels from Weingarten et. al.’s paper, where the number of antennas at the transmitter and each receiver are equal. We also only consider two receivers here for simplicity, the general case follows similarly. As before let the received signal at receiver be , where Since we are assuming to be a square matrix, without loss we can multiply the received signal by without changing the capacity. Note that is invertible with probability . This is formally defined as aligned MIMO BC (AMIMO-BC) with Then a transformation of AMIMO-BC is considered, called degraded and aligned MIMO BC (DAMIMO-BC), where with , denotes the covariance matrix. For any two matrices, ,by we mean is a negative semidefinite matrix. It is easy to see that DAMIMO-BC is a degraded BC channel, i.e. one receiver receives less noisy signal than the other. For the degraded BC it is known that superposition coding is optimal, however, it is not known whether Gaussian signaling is optimal or not.

For a single input single output degraded BC (SISO-DBC), where the transmitter and each receiver has a single antenna, Bergmans showed that Gaussian signaling is optimal, however, the proof of Bergmans does not extend to the DAMIMO-BC case.

The optimality of Gaussian signalling is shown as follows. Let be the set of all achievable rate vectors with Gaussian superposition coding for DAMIO-BC and let and be the input covariance matrices achieving and . To show that any rate vector which does not belong to is not achievable, an enhanced DAMIMO-BC is introduced, which is defined as where Clearly, any rate vector achievable on DAMIMO-BC is also achievable on the enhanced DAMIMO-BC, thus the capacity region of DAMIMO-BC is contained inside the capacity region of enhanced DAMIMO-BC.

Next, it is shown that for any DAMIMO-BC there exits an enhanced DAMIMO-BC such that the following properties hold

1. Proportionality: There exits , such that

2. Rate Preservation: The rate vector achievable on enhanced DAMIMO-BC with Gaussian signaling is equal to rate vector obtained with Gaussian signaling for DAMIMO-BC.

Then using the proportionality and rate preservation properties, it is shown that any rate vector which does not belong to is not achievable on the enhanced DAMIMO-BC, using Bergmans proof for SISODBC. An important point to note here is that the Bergmans proof works

because of the proportionality property, which is hard to show for DAMIMO-BC. Since the capacity region of DAMIMO-BC is contained inside the capacity region of enhanced DAMIMO-BC, it follows that any rate vector which does not belong to is not achievable and thus Gaussian signaling is optimal.

Coming back to the original AMIMO-BC, to show that DPC is optimal, the authors show that any rate vector which lies outside the region also lies outside the capacity region. Toward that end, it is shown that for any vector which lies outside the region there exists an enhanced DAMIMO-BC whose capacity region contains the capacity region of AMIMO-BC, but does not contain . Recall that we found out the capacity region of enhanced DAMIMO-BC and showed that Gaussian signaling is optimal, thus it follows that any rate vector which lies outside the region also lies outside of the capacity region of AMIMO-BC and we conclude that DPC is the optimal transmission strategy.

Ever wondered what does it take to construct a proof for a theorem, in my mind a lot of hard work, mathematical ability and sometimes stroke of luck. However things are generally not that simple, at times figuring out a proof can drive you nuts, make you crazy, especially if the statement of theorem looks obvious. To relieve us from the misery of figuring out a proof people are developing automated theorem provers and in future we might just have to type in some equations into a software and boom it gives a proof out.

For a preliminary solver, check out this link.

In a recent decision IEEE Information Theory Society has decided to limit the size of correspondence publications in the *IEEE Transactions on Information Theory * to five pages. I really dont see a merit in this decision, this makes correspondences equivalent to conference publications. A better idea would have been to do away with correspondences altogether and increase the acceptance rate in ISIT.

Below is the link for Shannon’s article on creative thinking.

http://inst.eecs.berkeley.edu/%7Eee290s/fa04/creative_thinking_shannon.pdf