The WindoWSIL

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 $N$ receivers, then a rate vector ${\bf R} = [R_1, R_2, \ldots, R_N]$ is said to be achievable on the broadcast channel if information can be transmitted reliably at rate $R_n$ from the transmitter to the receiver $n$ , $n=1,2,\ldots, N$ , 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 $M_t$ antennas wants to transmit independent information to $N$ receivers, where $n^{th}$ receiver is equipped with $M_n$ antennas $n=1,2,\ldots,N$ . Let ${\bf x}$ be the signal transmitted by the transmitter, then the received signal ${\bf y}_n$ received by receiver $n$ is given by ${\bf y}_n = H_n{\bf x} + {\bf v}_n,$ where $H_n$ is a $M_n\times M_t$ channel matrix and ${\bf v}_n$ is the additive white Gaussian noise (AWGN) with covariance matrix ${\bf N}_n, \ n=1,2,\ldots,N$ .

For MIMO-BC, several transmission strategies have been proposed in literature, for example, superposition coding and dirty paper coding. In superposition coding, if ${\bf x}_n$ is the signal for receiver $n$ then ${\bf x}= \sum_{n=1}^N {\bf x}_n$ 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 $\frac{1}{2}\log(1+SNR)$ 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 ${\bf x}_1$ , then the signal ${\bf x}_2$ for receiver $2$ is generated using ${\bf x}_1$ as the interference signal. Similarly, the signal ${\bf x}_n$ for the receiver $n$ is generated using ${\bf x}_1,\ldots,{\bf x}_{n-1}$ as the interference signals and ${\bf x} = \sum_{n=1}^N{\bf x}_n$ is transmitted from the transmitter. From now on we consider $N=2$ in this article for simplicity. With $N=2$ ,the rates $R_1$ and $R_2$ , simultaneously achievable for receiver $1$ and $2$ , are given by $R_1^{DPC} = \frac{1}{2}\log\frac{\det\left({\bf S}_1+ {\bf S}_2 + {\bf N}_1\right)}{\det\left({\bf S}_2+{\bf N}_1\right)}$ and $R_2^{DPC} = \frac{1}{2}\log\frac{\det\left({\bf S}_2 + {\bf N}_2\right)} {\det\left({\bf N}_2\right)},$ where ${\bf S}_n$ is the covariance matrix of ${\bf x}_n$ . Changing the order of coding, i.e. first generating ${\bf x}_2$ and depending on ${\bf x}_2$ generating ${\bf x}_1$ , $R_1^{DPC} = \frac{1}{2}\log\frac{\det\left({\bf S}_1 + {\bf N}_1\right)}{\det\left({\bf N}_1\right)}$ and $R_2^{DPC} = \frac{1}{2}\log\frac{\det\left({\bf S}_1+ {\bf S}_2 + {\bf N}_2\right)}{\det\left({\bf S}_1+{\bf N}_2\right)}.$ We denote the convex hull of all rate vectors achievable with DPC as $R^{DPC}$ .

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 $n$ be $Y_n$ , where ${\bf y}_n = {\bf H}_n{\bf x}_n + {\bf v}_n, \ n=1,2.$ Since we are assuming ${\bf H}_n$ to be a square matrix, without loss we can multiply the received signal by ${\bf H}_n^{-1}$ without changing the capacity. Note that ${\bf H}_n$ is invertible with probability $1$ . This is formally defined as aligned MIMO BC (AMIMO-BC) with ${\bf y}_n = {\bf x}_n + {\bf v}_n, \ n=1,2.$ Then a transformation of AMIMO-BC is considered, called degraded and aligned MIMO BC (DAMIMO-BC), where ${\bf y}_n = {\bf H}_n{\bf x}_n + {\bf v}^{*}_n, \ n=1,2.$ with $cov ({\bf v}^{*}_1) \le cov({\bf v}^{*}_2)$ , $cov(.)$ denotes the covariance matrix. For any two matrices, ${\bf A}, {\bf B}$ ,by ${\bf A} \le {\bf B}$ we mean ${\bf A} -{\bf B}$ 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.

${\it Remark:}$ 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 $R^{G}$ be the set of all achievable rate vectors $\{R_1^G, R_2^G\}$ with Gaussian superposition coding for DAMIO-BC and let ${\bf B}_1$ and ${\bf B}_2$ be the input covariance matrices achieving $R_1^G$ and $R_2^G$ . To show that any rate vector which does not belong to $R^G$ is not achievable, an enhanced DAMIMO-BC is introduced, which is defined as ${\bf y}_n = {\bf x}_n + {\hat {\bf v}}_n, \ n=1,2.$ where $cov({\hat {\bf v}}_1) \le cov({\bf v}^{*}_1), cov({\hat {\bf v}}_1) + cov({\hat {\bf v}}_2) \le cov({\bf v}^{*}_1) + cov({\bf v}^{*}_2).$ 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 $\alpha_1 \ge 0$ , such that $\alpha_1\left(B_1 + cov({\hat {\bf v}}_1)\right) = cov({\hat {\bf v}}_{2}).$
2. Rate Preservation: The rate vector $(R_1, R_2)$ achievable on enhanced DAMIMO-BC with Gaussian signaling is equal to rate vector $(R_1^G,R_2^G)$ 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 $R^G$ 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 $R^G$ 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 $R^{DPC}$ also lies outside the capacity region. Toward that end, it is shown that for any vector ${\bf R}$ which lies outside the region $R^{DPC}$ there exists an enhanced DAMIMO-BC whose capacity region contains the capacity region of AMIMO-BC, but does not contain ${\bf R}$ . 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 ${\bf R}$ which lies outside the region $R^{DPC}$ also lies outside of the capacity region of AMIMO-BC and we conclude that DPC is the optimal transmission strategy.

Author Archive

High SNR distribution of eigen-values of a Wishart Matrix

AMD Design Contest

Overview of MIMO Broadcast Channel Capacity Results

Automated Theorem Prover

IEEE Information Theory Society limits the size of correspondences

Creative Thinking - Cluade E Shannon

Administrative

Academic Resources

Other Wireless Blogs

Wireless News and Analysis

Categories

Recent Comments