I have now worked a little over 10 years in the industry, after getting my PhD. In my very first year of work at Qualcomm, I noticed how even when speaking about the same subject, namely CDMA, academia and industry were on totally different planets. When I was in Qualcomm, I co-authored a paper with Dr. Viterbi, titled Two Different Philosophies in CDMA, A Comparison. I still stand by the conclusions we reached, though there was a fairly strong rebuttal from my PhD advisor Prof. Sergio Verdu. His paper is listed in http://www.princeton.edu/~verdu/mud.html and I had located a scanned copy somewhere that I don’t remember now. I will post a link soon. A somewhat related paper by Verdu is http://web.mit.edu/6.933/www/Fall2001/Shannon2.pdf
A very quick summary of the conclusions we reached 10 years ago:
1. Multi-user interference is a major problem in CDMA. Your first line of defence against it is a powerful error-correcting code. You can potentially supplement it with non-linear techniques like successive decoding and successive interference cancellation, but they suffer from parameter estimation errors, so are not [as of 1995] yet anywhere close to being practical. Instead of non-linear techniques, our focus in the paper was on linear techniques common in academia.
2. A second line of defence had been very common in the literature, indeed the exclusive focus of study in the academic literature [true in 1995], namely linear dimensional techniques. Many people superficially claimed these techniques were applicable to commercial Qualcomm CDMA systems then already in the market. They were not. The fundamental system model the academic community used to study their interference suppression techniques differs markedly from Qualcomm CDMA. The systems were philosophically different, and the academic CDMA model was clearly inferior from an engineering point of view.
In spite of Verdu’s rebuttal, these conclusions have held up remarkably well. Today, the error-control code has gotten even more powerful: turbo-codes, which have caused a revolution. The dimensional techniques have been progressively abandoned. It vindicates my conviction that the academic community was barking up the wrong tree, and what they were calling CDMA was not the same CDMA the world has come to know and love and it was clearly inferior as an engineering design. Strong words, right?
A recent overview by Jeff Andrews at UT Austin Interference Cancellation for Cellular Systems: A Contemporary Overview caught my eye, and it referred to that 10 year old controvery (the reference [18] in the quote below is my paper and [19] is my advisor’s rebuttal)
| Quote: |
A controversial paper from QUALCOMM [18] identified at an early stage many of the fundamental problems with academic research on MUD, particularly with the widely researched linear projection techniques of the early to mid-1990s. Although this article made a number of mistakes (as partially documented in [19]), it may have helped spur more intensive research on interference cancellation from the late 1990s to the present. We now summarize the key challenges and historical shortcomings in multi-user receiver implementation, some of which were identified in [18], but will revisit some of these issues later when forecasting a bright future for multi-user reception.
|
Certainly, the “controversial” part is conceded. I was basically committing academic patricide, criticizing the very work that made my advisor famous. But I do stand by the essence of my critique. After all, Jeff Andrews states that my paper “identified many of the fundamental problems with academic research on MUD” - and the rebuttal by my advisor doesn’t really address the central thrust of my paper: namely that there is a fundamental difference in the mathematical system model studied as CDMA by the academia and the one built by Qualcomm and the academic model leads to misleading conclusions. My advisor has been “Dr.CDMA” in academia while what I consider the “real” CDMA (a fair characterization, because Qualcomm-is-CDMA, to this day) has been practiced in the industry. It is not an academic (!) debate: CDMA is now the dominant standard in cellular communications, and barring a challenge-from-below from Wi-Fi/Wi-Max, it should rule the roost for a long time.
We called the academic CDMA D-CDMA (for “dimensional CDMA”, and you can also consider it “delusional CDMA” - just kidding!) and the industry CDMA as R-CDMA (for “random CDMA” or “real CDMA” if you will). D-CDMA system model assigns signature waveforms (dimensions) to users, and deals with their correlations at the receiver using a variety of linear and non-linear algorithms . If the signature waveforms are orthogonal (the ideal situation), then D-CDMA is theoretically equivalent to TDMA. D-CDMA system model simply did not assign any role to error-correcting codes, a significant omission [see below]. Certainly, no paper by my advisor or collaborators until that point mentioned error-correcting codes, and it is fair to say that the D-CDMA model popularized by Dr.CDMA remained by far the most popular model in academia. I contended then, and stand by it now, that this is a significant problem.
In contrast to D-CDMA, R-CDMA is a deceptively simple, even simplistic idea: simply randomize all the users with very long spreading codes, so that every other user looks like Gaussian noise, then use powerful error-correcting codes against that noise + noise-like interference. It can be improved by the well known technique of successive interference cancellation (which my advisor called a proof technique, and suboptimal in practice, in his rebuttal but it is certainly more practical - but not very practical yet! - than many of the algorithms common in the D-CDMA literature).
Qualcomm’s CDMA system, designed based on a very different system model than what was considered in academia, was already in the market when we wrote the paper, so the fact that the academics were still researching their clearly inferior system model that treated demodulation/decoding separately, illustrates how ostrich-like academia often becomes, and why I decided to leave. Papers were published, tenures granted, reputations and careers made, and yet, the basic system model just didn’t make sense, at least to me.
In essence, our critique was not about multi-user demodulation per se but the incorrect system model adopted by the academic community to analyze “CDMA”. The D-CDMA model simply took a very statistical detection theoretic view of the world, while ignoring the fundamental role played by coding techniques. In any practical (or theoretical!) communication receiver, statistical detection (matched filtering and other statistical signal processing like parameter estimation) and decoding work together. Any system model and analysis technique that does not consider the system holistically is prone to reach erroneous or at the very least, misleading conclusions. Yet, the vast D-CDMA academic literature was full of such statistical-detection-based analysis (they call it “demodulation”, to separate it from “decoding”). A telling sign is the emphasis on SNR in the D-CDMA literature, a notion useful in analog parameter estimation, rather than the more appropriate Eb/No, a notion that is only relevant to digital communication. In fact, D-CDMA literature, including almost every paper from my advisor, made the cardinal sin of evaluating digital communications systems based on the uncoded bit error rate. The effect of that is that these systems do not display the characteristic “cliff” whereby the bit error falls steeply when a threshold Eb/No is crossed - that cliff makes analytical methods intractable, so simulation is all but required. All in all, my advisor’s rebuttal essentially missed the central point of my paper, which I believe was reasonably well articulated.
Jeff Andrews provides further confirmation of my critique. To quote from his overview again (emphasis mine)
| Quote: |
For asynchronous systems like the cellular uplink with random user timing offsets, mutually orthogonal codes are not feasible. But again, multi-user receivers that attempt to project the received users into orthogonal dimensions do not stand up to careful scrutiny. In particular, most of these techniques require the construction of a code cross-correlation matrix. But for the long PN codes generally desired for multi-path properties, this matrix must usually be recomputed every symbol, which is impractical. Even more important, it is now well established that strong error correction codes (ECCs) should be used in the uplink (and the downlink, for that matter). The spreading gain of these codes is lost on dimensional multi-user detectors. Furthermore, while the goal of these codes is to lower the required received signal-to-interference-plus-noise ratio (SINR), this complicates channel estimation and other aspects of dimensional MUD. Since linear projection receivers require spreading to be performed by a linear operation, there is direct competition between ECCs and dimensional (linear) MUD [24]. However, as discussed next, interference cancelling multi-user receivers not only do not suffer from this trade-off, but in fact need ECCs to attain their high performance, a result supported by information theory [25–27].
…
Most researchers have come to recognize that in a highly frequency-selective and rapidly changing channel with many users, dimensional separation techniques at the receiver are not viable. Further, it has been realized that effective MUD designs must integrate error correction coding/decoding into the receiver structure, rather than treating coding as a separately concatenated block. For this reason, successive [30–32], parallel [33, 34], and iterative interference cancellation (turbo MUD) [35–38] appear quite attractive.
|
A one-line summary of our paper would be precisely that dimensional-separation techniques at the receiver are not viable. Thank you Jeff, for making that point! I wonder if Prof. Verdu accepts your conclusion, because his rebuttal was still optimistic about those techniques. If he does accept this conclusion, it would be nice to receive an acknowledgement from him, that, yes, his student got that one right.
The reason for the love affair with statistical detection, to the exclusion of decoding, is the ivy-league academic quest for “closed form” mathematical results, at the expense of any kind of real world relevance. If your PhD doesn’t have the requisite number of Lemmas and Theorems, forget it - that seems to be the attitude. Turbo codes left leading coding theorists in the dust, with a radically simple and practical approach, which essentially achieves Shannon capacity (and that was only “proved” through simulations, no theorems, leading to enormous scepticism about the work initially). My advisor, a closet mathematician, always loved the closed form, theorem proof approach himself, and essentially prohibited me from doing any kind of “simulation work” to get a PhD. To be perfectly fair to him, that fit very well (too well!) with my own IIT Brahmin attitude about not getting hands dirty with something as mundane as writing code, an attitude I got out of after I had an epiphany that my entire PhD was useless abstractions piled on top of useless abstractions. That was what led me to abrubtly end my academic career. Looking back after 10 years, that was the single best career decision I made in my life.
When I entered Qualcomm I realized what a valuable tool the computer is to study real world systems, and how limiting the quest for “closed form” can be. In fact, my introduction to the world of software arose from modeling and simulating communication receivers, and I ended up embracing software as a career eventually. I read somewhere that Wolfram quit academia and went into software for what sounded to me (may be I imagined it!) like similar reasons: the Wolfram thesis asserts that the universe is equivalent to a Turing Machine and computer programs are the best tools to study the universe. Wolfram seems to deemphasize the theorem-proof methodology himself - in fact, he asserts in his book that most interesting questions are logically undecidable (i.e unprovable). I agree.
This is not to criticize mathematics; indeed far from it. Simple analytically tractable models (i.e the closed form again!) are illuminating, but they cannot substitute for more realistic models that can so often only be simulated. In particular, the holistic demodulation/decoding system cannot really be handled in any closed form solution I know of. Often, simulation can and does lead to insights into theory and can open theoretical doors that we may not suspect existed.
The reason I am writing this is to set the record straight. I have long ago moved on, and have transferred my affections to software. CDMA is like a long-lost old flame for me - it still excites some passion, but I am happily married to software now 
With the benefit of hindsight, read our paper, and read my advisor’s rebuttal. Then read Andrews’ recent survey. See if the points we made about the flawed system model that is D-CDMA resonate, 10 years later. As for the “mistakes” pointed out by my advisor? Just one sample would suffice. His rebuttal [see section 2.5 in his paper] quotes the “misconception 2.20″ (not specifically attributed to our paper, though the implication is there) that “Multi-user Detection is Successive Cancellation”. We didn’t say that - what we actually said was that if you want real multi-user detection, there is always successive cancellation, a technique well-known and something Dr. Viterbi, my co-author was well-aware of, and had written about long ago in the CDMA (R-CDMA) context. There are still numerous practical difficulties with it, having to do with the fact that various parameters have to be estimated in a noisy changing environment. Guess what? Andrews optimism for MUD is now based on this same technique, dubbed as “misconception” by my advisor. Deja vu all over again …
Here is a pure speculation/suggested PhD thesis: in statistical parameter estimation, there is the Cramer-Rao bound (it is a sort of the analog-equivalent of Shannon capacity, which is a digital construct). It basically says that your accuracy of estimation is limited by the variance of the noise. I have a strong suspicion [I am willing to stand corrected if I see some good results] that the regime of signal to noise you operate in CDMA makes any kind of accurate parameter estimation, which is needed for almost all of these multi-user techniques, including successive cancellation, quite difficult. There is an interplay and tension between bit rate maximization (digital communication) and accurate parameter estimation (analog communication, you assume that the channel is “communicating” those parameters to you!) that I have long wondered about, but done absolutely nothing more than wonder about. Note that if the parameters to be estimated don’t change much with time, you can average over a long interval, so you can do OK. But the real world is not so nice.
Basically after a long detour into inapplicable techniques arising from a faulty system model, academia is finally getting to a point that some of us in the industry reached 10 years ago. Welcome to the real world, guys.
Comments(0) 