Author Archive

The (North) American model for engineering graduate school

Miscellaneous 2 Comments »

Back in the day I used to frequent some grad school discussion boards on the internet. Yes, I’m a loser (I can feel Bob laughing at me already). It really struck me how different the grad school experience is in the rest of the world. For instance, at Ali’s M.S. university in Canada, he had to defend his M.S. thesis. In Australia, they don’t even have to defend their Ph.D. thesis. Even more astounding, in Europe and Australia (and probably several other places), a PhD generally takes three years after a bachelors. And they have no coursework.

On the other hand, in North America, we are required to earn Master’s degrees before our Ph.D. (or Sc.D.), and must take quite a few courses to do so, the exact amount of which varies from school to school. I believe I heard the average time from bachelors to Ph.D. in the U.S. is around 5.5 years.

How can it take more than two more years for us to get our Ph.D.’s relative to other areas of the world? Do we learn more? Are we less prepared? Are our programs less intense? Certainly at least one of these has to be true to some extent.

When Dan Ryan (from CSIRO in Australia) came to visit the WSIL this summer, he said classes are pointless for grad school; we should be able to learn everything we need to know out of a book. What is our response to this?

I’m afraid I only have questions on this topic.

Finite-SNR Diversity-Multiplexing Tradeoff

Reference 2 Comments »

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.

We Happy Electrical Engineers

Miscellaneous 4 Comments »

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.

The Diversity Multiplexing Tradeoff

Reference 6 Comments »

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 N_sstreams of M-QAM, R = N_s \log(M) 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.

Diversity-Multiplexing Tradeoff

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 r = \frac{dR}{d\log (SNR)}. Recall our definition of R = N_s \log(M), 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, log M \le log(1+SNR). Therefore, \frac{d\log M}{d\log SNR} \le 1. So what happens when we let \frac{d\log M}{d\log SNR} = 1 , i.e., when we allow our constellation to grow linearly with SNR? We see that now r = N_s. 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.

Diversity-Multiplexing Tradeoff

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.
An example of outage as a function of both R and SNR

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.

Interference and Particle/Wave Duality

WSIL News & Views 2 Comments »

Andy Reed, a pretty famous guy in the CS circuit (for fundamental contributions to the Intertubes), has said in an interview for popular media (I can’t find the article at the moment) that we’re missing something.  He says that interference should not exist.  Specifically, visible light (apparently) doesn’t interfere; hold up two same-colored LEDs and you could clearly detect information coming from either source (say, if they were pulsing).  So why should there be RF interference?

That was pretty much the entire article.   I wish I knew more about electromagnetics and quantum physics in order to refute it.  Of course the “only” difference between visible light and RF is the wavelength (or frequency) of propagation.  But quantum physics seems to tell us that particles (of any kind, including photons) are neither waves nor particles in the classical sense.  Some of their behavior is wave-like, some is particle-like.

At RF frequencies, photons are more wave-like.  At visible frequencies, they more particle-like.   I guess Reed seems to think (and may have some reason to that I’m unaware of) that we can exploit the photon’s more particle-like nature at RF.  Of course the article suggests no way of doing so, and Reed probably doesn’t as well.
Anyone know anything about this beyond my 2nd grade knowledge?

Philosophy

Miscellaneous 11 Comments »

I’m determined to coax at least one person in the group into an interesting discussion on this blog. The first problem with doing so is most of us sit so close, we can just turn around and have the discussion in real life. Wrong, I say! In the future we will communicate telepathically via instant message. Should I patent this?

The second problem is that the purpose of this blog has not been well defined, or if it was defined, I was not informed. It serves well as a source of disseminating information to everyone in the group, but it is obviously more than that. If it weren’t, there would be no public posts; there would be no link to it from Robert’s homepage.

I know we are all really busy, but this is important. Because I said so. (Hm, I guess that only works when Robert says it.)

Anyway, on to my question that I expect at least Bob to chime in on, and hopefully everyone else will too. My question is simple: What are we? Are we really engineers? Surely we’re not scientists, but maybe there should be a new category, something like engineering scientists, that would more properly describe us?

Webster defines engineering as “2 a : the application of science and mathematics by which the properties of matter and the sources of energy in nature are made useful to people b : the design and manufacture of complex products” . Webster then defines science as “3 a : knowledge or a system of knowledge covering general truths or the operation of general laws especially as obtained and tested through scientific method”.

Under these definitions I would claim that we’re more scientists than engineers, at least while we’re in WSIL.

The computer geeks are brilliant: they get to choose among calling themselves computer scientists, computer engineers, software engineers, software architects, computer architects, ad infinitum. Just absolutely brilliant. What do we have? “Electrical engineer”, and we barely distinguish from among the incredible diversity of the profession which far exceeds that of computer science.

The point? I think we need more labels for ourselves so we can have fancier business cards. I dream one day mine will read:

Steven W. Peters, Ph.D.
Holder of the Sacred Chalice of Nok
Heir to the House of Wilbur
Communications Scientist
Wireless Architect
Magician of Physical Layer Design

Deserved Bias?

Miscellaneous 4 Comments »

Every once in awhile we invest time in reading a paper or book chapter that says something so profoundly stupid that you have to stop reading for several minutes just to recover. It seems to me that this happens after a fair amount of warning, i.e., the authors have just said some sketchy things you weren’t buying. For instance, I just read the following quote in a book chapter: “Here, the relay channel becomes a 1×2 MIMO channel”. This book is not about MIMO, and obviously these authors know the difference between MIMO and SIMO. But still, they had been saying some things about unrelated topics that I wasn’t convinced about, and now their credibility is shot. If nothing else the example shows that the chapter was hastily thrown together, which, even if the authors know exactly what they’re doing, casts doubt on what they are saying.

My point is that it’s hard (for me) to continue reading work that has obvious flaws in it without being much too skeptical about the rest of the work. How do you guys get past this, or is it something we shouldn’t want to get past?