Self-Calibrating Time-Interleaved Analog-to-Digital Converters

Vijay Divi and Gregory W. Wornell

One popular method for achieving very high-speed analog-to-digital conversion is to use several slower speed converters in a round-robin fashion.   However, in practice there are gain differences among the constituent converters due to component variation, and the overall sampling is nonuniform due to disparities in converter output path lengths on-chip.  

As a result, the effective converter resolution can easily be several bits per sample less than that of the constituent converters.    A traditional approach to addressing this problem has been to calibrate the converter by feeding it a training signal and using the output to adjust its parameters.   However, this requires taking the converter off-line periodically, which is unacceptable in many applications.   In this work, we show, somewhat counterintuitively, that by using more such imperfect converters so that the input is oversampled relative to its Nyquist rate, it is possible to implement accurate calibration on-line in blind manner, i.e., without requiring knowledge of converter input.   In particular, we design iterative algorithms for learning the converter parameters on-the-fly, which are subsequently used to perform correction in either a feedback mode, whereby the converter parameters are directly adjusted, or in a feedforward mode, whereby the converter output is digitally resampled.   Such blind calibration is an example of a growing trend toward digitally-enhanced analog circuit designs.

Click for larger view

Rateless Coding for Wireless Channels: Efficient ARQ

Uri Erez, Mitchell D. Trott, and Gregory W. Wornell

In wireless networks, there is much variation in the signal-to-noise ratio (SNR) on individual links.  As a result, it is common for communication to be preceded by a training phase, whereby the receiver estimates the channel and conveys this channel state information (CSI) back to the transmitter.   However, in highly dynamic networks typical of mobile applications, there is often a serious mismatch between the actual and last-measured states of the channel during transmission, which ends up overwhelming the automatic repeat-request (ARQ) mechanism in the network and dramatically reducing throughput relative to what capacity analysis would promise.   In this work, we show that a suitable cross-layer architecture can avoid this problem.   In particular, we develop a joint physical-layer/link-layer design in the form of a rateless code.   In this design, no CSI is required at the transmitter.   Rather, a message is encoded into a sequence of incremental redundancy blocks.   The receiver attempts decoding after receiving each such block, and when successful informs the transmitter to terminate transmission.   We show that a construction based on simple linear combinations of submessages can: i) achieve the (a priori unknown) capacity of the channel; and ii) be decoded with extremely low complexity when the generator matrix is appropriately chosen.  The resulting code can be interpreted as a maximally efficient hybrid ARQ scheme.

Click for larger view

Circuit-Aware Codes for Energy-Efficient OFDM Transmission

Everest Huang and Gregory W. Wornell

Orthogonal frequency-division multiplexing (OFDM) is an increasingly attractive transmission format for wireless and wireline communication standards.   However, OFDM waveforms traditionally suffer from high peak-to-average power (PAPR) characteristics, so that when used with typical linear RF amplifiers, power consumption is excessive.   This work explores the joint design of the transmission waveforms and RF amplifiers, i.e., the design of circuit-aware codes, and code-aware circuits.  We show that in low-power applications, by using such an approach it is possible to reduce power consumption by a factor of more than three, which in wireless applications dramatically extends the operating time of mobile devices.   The key ingredients of our system are the combination of novel outphasing RF amplifiers—which are are highly power efficient—and magnitude-only information encoding—which is rate-efficient in the low SNR regime of interest.   In this system, the transmission phase is adjusted via a suitably designed iterative algorithm to minimize PAPR.

Click for larger view

Click for larger view

Efficient Codes for MIMO Communication Channels
Huan Yao and Gregory W. Wornell

As multiple-element antenna arrays become an increasingly important ingredient of high-speed wireless networks, there is a corresponding need for physical-layer system designs that create fat, reliable bit pipes from such channels. Recently, the fundamental tradeoff between throughput and robustness has been quantified in the form of what is referred to as the diversity-multiplexing frontier. While it was understood the sufficiently long and random codes code approach arbitrary points on this frontier, it was not known whether all such points are achievable with practical codes. We show that suitable designed titled-QAM codes, in which a multidimensional constellation is subjected to a unitary transformation, can in fact achieve the full frontier. Moreover, they achieve this frontier even for the shortest code lengths where random codes cannot. A key property of this new family of codes has the property that their minimum determinant difference is independent of the constellation size (and hence transmission rate). Such codes can be used in conjunction with other traditional error-correction codes and appropriately designed iterative decoding, and are considerably more efficient than the popular orthogonal space-time block codes at higher spectral efficiencies.

Efficient Quantization for Sensor Networks,
Stark C. Draper and Gregory W. Wornell

In many peer-to-peer sensor network architectures, the signal measurements acquired at nodes are quantized, and the associated bit representations are propagated through the network to data fusion nodes where inference is performed. From this perspective, the quantizer design problem can be viewed as one of coding for estimation with communication constraints. A naive approach would have each node design its quantization without regard for the network structure. However, a substantially more resource efficient network results from the quantizer taking into account that the intermediate nodes propagating these bit representations are receiving their own measurements as well as bit representations from other nodes. From an information-theoretic perspective, this these intermediate nodes have so-called side information that can be exploited in the code design. We develop powerful greedy coding algorithms based on this principle, and show how they achieve or approach fundamental limits in prototype topologies. From an architectural perspective, the new algorithm represents the design of a network-aware application layer for this problem, which our results establish is substantially more resource-efficient than a traditional layered architecture.

Multimedia Content Authentication,
Emin Martinian and Gregory W. Wornell

In today's world, we find ourselves both impressed by and uncomfortable with the ease with which one can use digital tools to manipulate audio, video, imagery, and other kinds of multimedia content. One might reasonably ask whether it is possible in such a world to make, for example, a photograph that is truly trustworthy in some precise sense. In this work, examine this question, develop a meaningful mathematical model for the problem, and analyze the associated fundamental performance limits of authentications systems that provide a security guarantee. We further develop the structure of systems that approach these limits, and see that the resulting coding strategies can be viewed as rather powerful generalizations of traditional digital signatures. Moreover, we show that such systems can be built from familiar ingredients put together in some rather new ways. More generally, our investigation reveals that such multimedia security problems are inherently highly interdisciplinary, and that practical solutions require jointly exploiting concepts from information theory, coding and communication theory, signal processing and systems theory, and cryptography and complexity theory.

Cooperative Diversity for Wireless Networks,
J. Nicholas Laneman and Gregory, W. Wornell

In a typical wireless network, users exploit their available power and bandwidth resources to communicate their messages to their target destinations as efficiently as possible, and ignore or avoid the messages of other transmitting users. However, we show this selfish strategy is, in fact, not in the collective interest of the group: through cooperation each individual user can experience better performance. In particular, if each user devotes some of its resources to relaying the transmissions it hears from other users as well as to sending its own message, each message is received with higher reliability because it experiences multiple propagation paths. Indeed, with this protocol, the group of cooperating users are forming a "virtual" antenna array, from which there is a substantial spatial diversity benefit. We show that, in fact, very simple relaying schemes yield full spatial diversity: each user's message experiences performance as if it were sent from a physical antenna array of the same size. These lead naturally to novel and efficient distributed space-time codes for networks, which are equally applicable to cellular and ad-hoc architectures. From an architectural perspective, such protocols require only a relatively small violation of the traditional abstraction rules that impose a separation of the physical, link, and network layers.

Smart Buffers for Multimedia Content,
Stark C. Draper, Mitchell D. Trott, and Gregory W. Wornell

Buffers find application in a wide range of contexts, from digital hardware and software systems to broadband packet-switched networks like the Internet. Traditionally, such buffers are designed without regard for the characteristics of the content they will hold. For example, with a simple first-in/first-out (FIFO) buffer, if during some interval of time the number of bits that needs to be stored exceeds the memory resources, some are simply dropped. When those bits represent some multimedia content of interest, the dropped bits correspond to a loss of fidelity. In this work, we examine the design of a smart buffer that takes into account how each bit contributes to the fidelity of the content stored in memory, and develop a buffering algorithm that optimizes end-to-end fidelity. In particular, we develop a greedy algorithm is sample-path optimal: regardless of the pattern of arrivals to and departures from memory, no other algorithm, greedy or not, can achieve better performance. This algorithm ensures that most-significant bits are both stored in memory first and depart memory first, with the resource allocation managed by an easily implemented waterpouring strategy. The smart buffer achieves a given end-to-end fidelity target with considerably less storage and communication resources than traditional designs. From a system or network architecture perspective, the resulting design shows how increasing lower layer awareness of the application layer in relatively simple ways can substantially improve resource efficiency.

Scheduling for Multiple Antenna Wireless Transmission,
Michael J. Lopez and Gregory W. Wornell

It is well known that the use of multiple antennas can enhance the capacity of wireless links delivering messages to geographically dispersed receivers. Moreover, in applications where the channel state information is available at the transmitter, efficient precoding strategies (based on information embedding concepts) exist for multiplexing the different messages to be delivered to different users. In particular, this precoding performs an interference pre-cancellation operation that ensures the different target receivers can ignore interference effects when decoding their messages. However, in typical networks, the collection of messages to be transmitted can be quite large, and a scheduler selects a subset to be multiplexed in any particular transmission interval. When the scheduler and multiplexor operate independently, the scheduler complexity is very low, but the multiplexor can require substantial complexity. We show that by having the scheduler make efficient use of a latency window and take into account the implications of its decisions for multiplexing, the overall system can be much more efficient. In particular, the complexity of multiplexing is significantly reduced while requiring only a small increase in the complexity of scheduling. In addition to highlighting the role of delay as a resource, this work is another compelling illustration of how a modest amount of lower-layer awareness at the networking layers can substantially improve overall resource efficiency from a network architecture perspective.

Information Embedding and Digital Watermarking,
Brian Chen and Gregory W. Wornell

In a variety of emerging applications, there is a need to hide a sequence of bits in some host signal like a photograph or a radio transmission. Applications range from digital rights management and copyright notification and enforcement, to backwards-compatible upgrades to existing communication infrastructure, broadcasting, and covert communication. In such problems, there is an inherent tradeoff between the number of bits embedded, the robustness with which they are embedded, and the distortion the embedding incurs on the host signal. In this research, we show this problem is equivalent to an information theoretic problem of channel coding with side information at the encoder, and use the equivalence to characterize the tradeoff and develop the associated fundamental limits. We further introduce a practical and efficient encoding scheme we refer to as quantization index modulation (QIM), and a distortion-compensation techniques (DC-QIM), for achieving the fundamental limits. The key to the effectiveness of QIM is the way it ensures that the host signal is not a source of interference at the decoder. Indeed, data hiding systems based on DC-QIM are orders of magnitude more efficient than the more familiar data hiding systems based on spread-spectrum methods, in which there is host signal interference. This research underscores the importance of careful problem modeling to effective algorithm design.

The "Dirty Paper" Codec Project:
A Real-Time, Capacity-Approaching Information Embedding System,
Laboratory Partnership with Chinook Communications

The foundations of information embedding were laid more than twenty years ago with early information-theoretic work on the problem of channel coding with side information at the encoder. One of those early papers was Costa's whimsically titled "Writing on Dirty Paper". In recent years, four key advances have made possible the development of practical information embedding systems. First is the recognition that the information embedding problem can be cast as a problem of "writing on dirty paper". Second is the development of practical code constructions in the form of distortion-compensated quantization index modulation (DC-QIM). Third is the development of capacity-approaching turbo codes with very low complexity iterative decoding algorithms. And fourth is the maturation of VLSI technology and the associated development tools. In this project, all four of these advances are exploited together in the design of the world's first real-time, capacity-approaching information embedding system: the "dirty paper" coder/decoder (codec). This system transparently embeds a bitstream at 6 Mb/s into an arbitrary analog NTSC television signal so that it can be reliably transmitted through, for example, any FCC-compliant cable network. Such systems could be used to add roughly 300Mb/s additional downstream capacity to cable infrastructure without requiring plant upgrades or affecting existing services. The system operates within a couple of dB of capacity, and the reference design is complete with analog front end, 400k gate FPGA codec, full DSP-based software equalization, and an embedded linux controller. Other emerging applications of this technology include multi-antenna downlink transmission in wireless systems.