The WindoWSIL

After my post on the diversity-multiplexing tradeoff, which seemed to create confusion instead of alleviating it, Prof. Heath asked me to clarify the finite-SNR diversity-multiplexing tradeoff proposed by Narasimhan in [1] (pdf). The previous explanation of the Zheng-Tse DMT really simplifies the explanation of the Narasimhan DMT. If you understood the previous post (in the rest of this post I will assume you didn’t), then the finite-SNR result simply defines diversity as the slope of the outage curve at a given SNR. If you have the 3-D plot of outage versus SNR and R, then fix r. Then, for each SNR, the DMT curve is given by (d,r,SNR), where d is the slope of the outage curve at SNR. There is a little bit more to it, so keep reading even if you understood that.

Now, I’m back to assuming you didn’t understand the previous post. This is a safe assumption, as I feel I didn’t explain it very well. We can all agree, I think, that in an ideal world with real-rate constellations, we could express the probability of outage as a function of both SNR and R. Again, R is simply the spectral efficiency of the signaling mode. For instance, if we are sending two streams of 16-QAM, R=8.

So we have this P_out(R,SNR) expression. We’re going to imagine this curve plotted in three dimensions. First, imagine a normal 2-D plot of outage versus SNR for a fixed R. Suppose, for instance, R = 1; that is, we’re sending BPSK using the Alamouti code. Simple, eh? Now, bring in the third dimension of the plot, pointing toward you. Thus, the x-axis is SNR in dB, the y-axis is R, and the z-axis is outage probability.

We can imagine that as R increases, the curve becomes more spread out in the SNR dimension. Intuitively, at any given SNR, a larger rate means a higher probability of outage. It’s important that you can see this before moving on. The 3D figure from the previous post might help.

Again, our three axes are SNR, R, and outage. For a moment, let’s forget about the probability of outage and focus on the relationship between SNR and R. For a fixed number of transmit and receive antennas (Nt and Nr, respectively), MIMO information theory tells us that R is always less than or equal to m*log2(1+p), where p is the per-stream SNR at the receiver, and m=min{Nt,Nr}. The figure below plots this upper bound on R versus 10*log10(SNR) for m=1,2. The red line corresponds to m=2, and the blue line corresponds to m=1. We also plot the lines m*log2(SNR) for m=1,2. At SNR > 15 dB, the m*log(SNR) and m*log(1+SNR) lines virtually overlap for respective m.

Now, remember these are upper bounds on R; in practice, we will not achieve them. However, for a particular signalling strategy, we can plot our R on this plot. For any strategy that does not adapt the rate with SNR, our rate plot will be rather boring. It will be a step function with transition at the SNR below which we cannot reliably communicate at that rate (assuming no channel coding).

Observe that as SNR grows arbitrarily large, the ratio between our fixed rate R0 and the SISO capacity (the blue curve) will become arbitrarily small, regardless of what R0 is. This ratio, at any particular SNR, is the definition of multiplexing gain given in the finite-SNR DMT. Let me repeat this for clarity. For any adaptive signalling strategy, we can plot its rate as a function of SNR. The finite-SNR DMT multiplexing gain at a given SNR is defined as the ratio of our rate to the SISO capacity at that SNR.

We see right away how this is a generalization of the Zheng-Tse DMT. They define multiplexing gain as the limit of the ratio between our R curve and the linear magenta curve as SNR goes to infinity. If we do not adapt with SNR, this ratio becomes arbitrarily small, such that its limit is zero (r = 0). For any finite SNR, however, this ratio is strictly nonzero.

Recall for a second that, in my previous post, I defined the multiplexing gain as the derivative of R with log(SNR). Strictly speaking, this was inaccurate. It is only valid at high SNR and if R is linear with log(SNR). In practical systems, R will be nonlinear in SNR.

Now, back to our figures. We’ve plotted R as a function of SNR, and defined the multiplexing gain as the ratio between our R and the SISO channel capacity. These curves on this 2D plot, however, are surfaces when extended into the outage dimension. This is very important to visualize. Think of the line y = x in two dimensions. Extending this equation to three dimensions results in a plane perpedicular to the y-x plane. We can do the same with our R-SNR plots.

So now, to recap, in our minds we have a 3 dimensional space. The dimensions of this space are x = SNR, y = R, and z = Probability of outage. In this space we have plotted probability of outage for our signalling mode (say, for example, the Alamouti code). Now, we have a surface sticking up out of the x-y plane that represents how we plan to vary R with SNR. The intersection of these two surfaces is a curve. That curve is the probability of outage curve for our signalling mode and adaptation strategy.

Now we define diversity as the negative slope of that curve at any given SNR. Again, this is easily seen as a generalization of Zheng-Tse, since their diversity is the negative slope of that curve as SNR goes to infiinity.

Then, the point on the finite-SNR DMT curve is the triple (d,r,SNR), where again r is the ratio of our R to the SISO capacity at the given SNR.

I hope that made sense, because that’s about it. I’ll now talk about some intuition.

First, since r is the ratio of our R to the SISO capacity, r > 0. The limit r = 0 doesn’t make any sense, but we can approach it arbitrarily closely at any finite SNR. Thus, we can’t really achieve the full diversity gain of the channel at finite SNR.

Further, since our R will be strictly less than capacity, the ratio of R to the SISO capacity will always be less than the ratio of the system capacity to the SISO capacity. Effectively, we won’t achieve the full multiplexing gain of the channel at finite SNR, either.

Finally, we note what this finite-SNR DMT can tell us that the infinite version cannot. By taking the limit of the ratio of R over the SISO capacity as SNR goes to infinity, we’re effectively saying R is a line of slope r. This is why I could fudge it and say r = dR/dlog SNR for the infinite-SNR DMT but not for the finite-SNR DMT. By not taking this limit, the math becomes all but intractable, but we can now make r nonlinear! It can increase (or decrease) however we wish, although it will be upper bounded by the ratio of our capacity to the SISO capacity.

Also notice that, if we don’t adapt with SNR, r is still greater than zero for any finite SNR. For example, again, say R = 1. At SNR=10dB, r will be approximately 1/3, and we’ll say d is some d0. At SNR = 20 dB, r is approximately 1/6, and d will be some d1 > d0 (the slope of any outage curve is monotonic decreasing with SNR). Thus, as SNR increases, on the DMT curve, we move up (d increases) and to the left (r decreases).

So, it seems the major thing Narasimhan’s finite-SNR DMT tells us is how quickly a certain strategy approaches the optimal Zheng-Tse DMT. Two strategies that both achieve the optimal DMT curve will likely have different outage curves, and will thus approach the optimal curve at a different rate. The strategy that approaches it quicker will have a smaller outage probability above some unknown crossing point (which may not even exist; one strategy might always be better than the other in terms of outage).

This motivates our last point. The finite-SNR DMT still doesn’t give crossing points or tell us precisely when to switch from one mode to another. It can give us an estimate of where to switch, however. If two outage curves cross each other, then at some SNR smaller than the crossing-point SNR, the higher curve started decreasing quicker than the lower curve; that is, its diversity became higher than the other’s. Since d is nondecreasing with SNR (for any sensible r), this switch will only happen once.

Take, for instance, Alamouti coding with 16-QAM versus spatial multiplexing with 4-QAM using an ML receiver. Here our model assumes 2 transmit and 2 receive antennas. The probability of vector symbol error (okay, not outage, but the same concept applies) for these two strategies is below.

For the infinite-SNR DMT, r = 0, and the best strategy is always the Alamouti code, which achieves d = 4, while spatial multiplexing with ML receiving achieves d = 2.

For the finite-SNR DMT, r is varying with SNR, though it varies equally for both strategies. Observe that the slope of the error curve of the Alamouti code is flatter at low SNR than the slope of the SM-ML curve. Thus, at low SNR, d(Alamouti) < d(SM-ML).

At around 10 dB, the slope of the Alamouti curve becomes steeper than the slope of the SM-ML curve. Thus, at apprximately 10 dB, d(Alamouti) > d(SM-ML). There is a crossing point in their DMT curves around 10 dB and r approximately 4/3. Note, however, that the error curves don’t cross until approximately 17 dB. Quite a gap. Since, to find the finite-SNR DMT, you must take the derivate of outage term approximations, however, you probably have a decent estimate of the outage terms and can directly calculate crossing points, if that is what you’re interested in.

In summary, the DMT gives us intuition about the outage curves for different signalling strategies. In particular, the DMT curve does not tell us there is a tradeoff in how we use an extra antenna pair given to us, but instead a tradeoff in how we use extra SNR given to us. We can use extra SNR to increase our rate, or decrease our outage probability. This is the fundamental tradeoff.

As many of you know, I’m obsessed with overhead these days. I like to think visually and want to organize my thoughts on a poster, kind of like a white board. Here is what I would like to do: Have a virtual poster or white board where I can draw block diagrams and put latex text with equations and references in different movable blocks. Is there a software package (for the MAC) where this can be done? I guess I could use texpoint and powerpoint but then I can’t use bibtex. Any thoughts? Basically I want different objects I can move.

This is perhaps the first big move towards the 4G mobile wireless system that has been in the talks for the last 5 years or so. Today, ITU-R at the World Radiocommunication Conference (WRC ‘07) has agreed on the spectrum for 4G.

• 450−470 MHz band
• 698−862 MHz band in Region 2 and nine countries of Region 3
• 790−862 MHz band in Regions 1 and 3
• 2.3−2.4 GHz band
• 3.4−3.6 GHz band (no global allocation, but accepted by many countries)

Now the question is what the radio specification will be for 4G (=IMT-Advanced).

http://www.itu.int/newsroom/press_releases/2007/36.html

http://www.itu.int/newsroom/wrc/2007/itur_web_flash/20071019.html

According to a recent University of Chicago study, 49.89% of electrical engineers are ‘very happy’ with their jobs. This was the 11th highest of well over 100 professions. We ranked just below Actor/Director and just above Airline Pilot. Needless to say, we are the happiest engineering profession. Compare our 49.89% “very happy” rating to that of mechanical engineers: 28.2%. How can we be so much happier than them? They’re less happy than waiters, nurses aides, shipping clerks, groundskeepers, and many many other professions. I should note that Computer Programmers also rated very low on this survey.

The data is here.

Last week Google announced Android, an open source platform for mobile software development. Now google has released the software development kit. To top things off the Android Design Challenge is offering a total of $10 million in awards for good mobile software designs. Anybody feel like moving up a few layers and trying this out?

Note 1: You may want to check out my followup post on the diversity-multiplexing tradeoff. I think it’s a bit clearer than this one.

Note 2: You need to click on the figures to view them.

I’d like to share some intuition on the diversity-multiplexing tradeoff (DMT) given to me by Rahul Vaze. This way of looking at it really makes clear what its values and limitations are.

The first step in the intuition is to note the definitions of diversity and multiplexing. Here, multiplexing is not spatial multiplexing. That is, it is not the number of parallel streams being transmitted. This is one place where a lot of people seem to get confused, because strategies such as spatial multiplexing with maximum likelihood detectors can use the maximum available degrees of freedom in the channel while achieving a diversity gain, whereas the DMT shows that maximum “multiplexing” gain will be at the expense of all diversity.

To understand what multiplexing means here, we first define rate R to be the number of spatial streams being transmitted times the number of bits per transmission per stream. Thus, if we are sending streams of M-QAM, bits per transmission. Note that as SNR increases, we can increase M, but we cannot Ns above its maximum level. For this R, and for a given detection strategy, there is a probability of outage curve that resembles the figure below. At high SNR, the log-log curve is a line with slope -d, the diversity order of the strategy.

Now imagine we are at some SNR g1, as shown, with outage probability p1. Suppose the SNR increases to g2. If our constellation size does not increase at all, we are sending at the same rate, and the outage curve remains as shown; we are now operating with outage probability p2. If for every SNR increase, we keep sending the same constellation, and choose to operate at a lower outage probability, at high SNR we will be benefiting from the full diversity gain of the strategy.

We now define multiplexing gain as . Recall our definition of , which does not readily depend on SNR. However, we can choose to make M depend on SNR by using continuous-rate (ideal) adaptive modulation. So M = f(SNR). In the previous example, M = M0, which was independent of SNR, so r = 0. This corresponds to the y-intercept of the DMT curve where the maximum diversity (of the strategy, not necessarily of the channel) is achieved.

It is now natural to ask “what is the fastest achievable rate of change of M with SNR“? Observe that log M is the number of bits per transmission over a SISO link. By Shannon’s formula for the Gaussian channel, . Therefore, . So what happens when we let , i.e., when we allow our constellation to grow linearly with SNR? We see that now . This corresponds to the x-intercept of the DMT curve. But why is diversity zero in this case? The answer to this will give us intuition about all the other points on the DMT curve.

First we observe that, for a fixed transmit/receive strategy, the probability of outage curve is a function of both SNR and R. For simplicity we usually calculate, and plot, the outage curve for fixed R. This is also because, in practice, only integer-rate constellations are used, so an outage plot as a function of R would be discrete in R. However, if we pretend we can send real values of log M (that is, we have constellations of order M, where M is not an integer power of 2), we can plot outage as a continuous function of R. This is still not done, because 3-D plots are difficult to observe on paper, and are generally unnecessary. Instead, on a single 2-D plot, we take cross sections of the curve for fixed values of R.

So in the figure below I’ve drawn some possible outage curves for a fixed strategy as a function of SNR and for different R. Suppose again that we are operating with R = Ns log M0 at SNR g0 with outage p0. This time, however, when g0 increases to g1, we increase M0 to M1 linearly with SNR. Thus, we have kept the gap between our rate R and capacity C constant, and the outage probability will be unchanged.

Adapting the rate with SNR effectively results in a new outage curve that is not a cross section of the general outage curve using a plane parallel to the R = 0 plane, but instead is a cross section using a plane with slope r in the R dimension. I hope the figure below (click for a larger version) explains it better than I can with words.

Now this new outage curve is for a fixed r. For this fixed r, the log-log outage probability curve will be linear with some slope at high SNR, and we call this slope -d(r). This pair (r,d(r)) is one point on the DMT curve. As we vary the R-slope (r) of the cross-section plane in the figure above, we observe different d(r). Obviously, the steepest slope will occur when the plane is perpendicular to the R-plane, or when r = 0. Correspondingly, if this cross-section plane is such that outage is flat, then r is along the line of constant outage (color in the figure above) and d(r) = 0.

Because this tradeoff curve is only relevant asymptotically with SNR (via the diversity gain), it has no application to adaptive signaling strategies. For instance, if at SNR g1 you decide to switch from, say, the Alamouti code to spatial multiplexing, this switch is completely lost in the DMT tradeoff. The tradeoff only tells you how fast you can scale the rate of a fixed strategy relative to how fast capacity is changing at high SNR and still achieve a linear log-log decrease in outage probability.

I was doing a little late-night reading tonight, and it is amazing how poorly some proofs are written by very intelligent people in our field. I’ve even seen poorly written proofs in the midst of a well-written paper. I understand that the primary concern with proofs is correctness, but shouldn’t proofs also be readable? My question is, how essential are nice, clean, understandable proofs in a journal draft? If the goal of our paper is understanding, then clearly they should be just as readable as the text. Maybe that’s why most authors place them in the appendix…so their hideous features don’t destroy the rest of the paper. Of course, some will tell you that if the math in your publication is too understandable, then your peers won’t respect it as much. The point being that, if your proof is straightforward, the result must have come to you easily and is therefore not worthy of publication. You might think I’m joking, but I’ve heard this from many academics over the years.
This really makes me appreciate my first undergraduate class in algebra and number theory. The professor in this class was a bit “picky'’ about the structure of proofs and the logic used to draw conclusions. At the time it made assignments dreadfully tedius, but in the end it made me appreciate a well-written proof. For those of you who didn’t have the opportunity to take undergraduate classes focused on proof-writing, how did you pick up your skills? If you’d like to learn more about proofing skills, check out this link (courtesy of Professor Cusick at Cal State Fresno).

I just heard that the mobile WiMAX standard (IEEE 802.16e) was approved as the sixth international standard for the IMT-2000 third-generation (3G) telecommunication platform, by the International Telecommunication Union (ITU) today. The decision may accelerate the transition from the 2.XG to the 3.XG, but it depends on the operators. Also, the competitor for the mobile WiMAX will be, in my point of view, the legacy WiFi or the IEEE 802.11n standard.

When I came to Austin permanently in July and took a metro bus, I was so surprised about the wireless internet accessibility in a moving bus. At first I thought it was the mobile WiMAX, but it was not. Still I am not sure it is the EDGE (2.5G) or the WiFi (APs along the path), but it is fast enough (for a grad-student) to check my email, and moreover, it is FREE. For me, there’s no demand to use the mobile WiMAX, especially if I pay for it. I can use free WiFi on the campus, in a bus and even in my home (thanks to my reckless neighbor).

I am curious how the operator (such as Sprint, who is implementing the Mobile WiMAX around DC area) take advantage of the official approval today. They may combine it with legacy system to reduce the deployment cost, but the money for the FCC to license the band (5 - 20MHz) will be huge. if they convince some potential users (including me) to pay some money for the service, the money doesn’t matter. But if they don’t, I think they may not win in the 3G game - a step stone to the promising 4G, regardless of the new technological features in itself.

What is your opinion?

I have been watching the developments in nanotechnology as a potential enabler for the new generation of wireless systems. I was initally captivated by the idea of creating a vaccum tube on a wafer using carbon nano tubes. While traditional vaccum tubes are inefficient, they have very high gains which are difficult to realize in solid state electronics. I think analog signal processing is bound to come back…

In any case, I think this paper is a significant stepping stone towards this direction. The paper is here. They even have a demo video (and a nice taste for Irish music).

I am glad to be writing the first post from a 3G device. Wireless is really great. It seems though that 3G is here maybe 7 years late. In any case I look forward to working with some MIMO enabled devices soon. Wsil let’s make this a reality!