Click for larger view

Self-Synchronizing Codes for Sparse Communication

Aslan Tchamkerten, Venkat Chandar, and Gregory W. Wornell

In traditional communication system architecture, the subsystem that encodes and decodes the bits to be communicated  is designed and implemented separately from the subsystem that establishes a synchronized channel (e.g., by training).   For example, typically a pseudonoise sequence is prepended to a packet of data to enable synchronization prior to decoding.   However, in many emerging applications, such as in the realm of sensor networks, communication is inherently intermittent or bursty.   We develop and analyze a model for such sparse communication scenarios, showing that there is a fundamental tradeoff between the highest rate at which communication is possible and the degree of sparseness.  Such analysis reveals that there is sharp sparseness threshold beyond which reliable communication is fundamentally not possible.  At the same time, away from this limit, we show that even when the channel is only used an exponentially small fraction of time, it is possible to communicate reliably at the traditional capacity of the channel.   However, we further show that such communication is not possible using the traditional architecture.  Rather, synchronization and communication must be implemented jointly, and we develop families of codes with suitable structure.

Click for larger view

Real-Time Neural Decoding for Concurrent Brain-Machine Interfaces

Maryam M. Shanechi, Emery N. Brown, Ziv M. Williams, Gregory W. Wornell

Brain-machine interface (BMI) research has largely focused on the problem of restoring lost motor function in individuals. However, a more compelling aim of such research is the development of a truly ``intelligent'' BMI that can transcend original motor function by considering the higher-level goal of the motor activity and reformulating the motor plan accordingly. This would allow, for example, a task to be performed more quickly than possible by natural movement, or more safely or efficiently than originally conceived. Since a typical motor activity consists of a sequence of planned movements, such a BMI must be capable of analyzing the complete sequence before action. As such its feasibility hinges fundamentally on whether all elements of the motor plan can be decoded concurrently from working memory. In this work, we develop advanced neural decoding algorithms to demonstrate that such concurrent decoding is possible. In particular, we develop and implement a real-time BMI that accurately and simultaneously decodes in advance a sequence of planned movements from neural activity in the premotor cortex. In our experiments, monkeys were trained to add to working memory, in order, two distinct target locations on a screen, then move a cursor to each, in sequence. We find that the two elements of the motor plan, corresponding to the two targets, are encoded concurrently during the working memory period. Interestingly, our results also reveal: that the elements of the plan are encoded by largely disjoint subpopulations of neurons; that surprisingly small subpopulations are sufficient for reliable decoding of the motor plan; and that the subpopulation dedicated to the first target and their responses are largely unchanged when the second target is added to working memory. These results have significant implications for the architecture and design of future generations of BMIs with enhanced motor function capabilities.

Click for larger view

Quasi Light Fields: Computational Abstractions for Coherent 3D Imaging

Anthony Accardi and Gregory W. Wornell

A traditional image represents a view of a scene of interest that is optically consistent with what the human eye would perceive at a particular location and orientation relative to the scene. From this perceptual perspective, the field of photography has aimed to accurately reproduce such views. However, from an information perspective it is ultimately the 3D scene that is of direct interest, not the view itself. In such cases, the view corresponds to an intermediate representation of the scene, from which inferences can be made, including the locations and properties of sources and objects. In the computational photography community, where the focus is on noncoherent imaging at visible wavelengths, this perspectice has led to new view-independent "plenoptic" camera architectures. Such
cameras are designed to capture the so-called light field as the intermediate representation, which constitutes a convenient computational abstraction derived from models based on geometric optics. For coherent imaging, scene reconstruction from field
measurements can be straightforward for scenes that are particularly simple, such as those consisting of a small number of point sources. Indeed, in such scenarios the appropriate phased-array architectures for beamforming and more general array processing
techniques follow immediately from the physics of electromagnetic propagation. For more complicated scenes, however, it is often impractical to directly exploit Maxwell's equations. To address this issue, we develop and fully characterize all radiometrically accurate
extensions of the light field to coherent imaging, which we refer to as quasi light fields by virtue of their close relationship to the quasi distributions that connect quantum and statistical mechanics. We further illustrate the potential of this higher-level computational
abstraction using some simple but revealing examples. Ultimately, this research seeks to relate and unify diverse perspectives from computational photography, classical optics, and array processing.

Click for larger view

Urs Niesen, Devavrat Shah, and Gregory W. Wornell

Users of wireless network services seek access to an ever growing volume of data on their mobile devices. Examples include a variety of video, audio, and image content, as well as a variety of other forms of data. For content that changes much less frequently than it is
requested, network operators increasingly rely on cache-based architectures to ease the burden of such demands on their networks.  In particular, frequently requested content is stored in advance at several nodes in the network.   We examine how such caches are best used in a large wireless network where each node in the network independently requests one or more items of content, each of which is cached at multiple locations. For this scenario, we develop a novel three-layer architecture whose supportable data rates for these requests scales scales optimally with the network size in the strong path-loss regime.  In this architecture, the routing layer at the top treats the wireless network as a tree graph and routes pieces of an item of content from the caches to the destinations. In the middle, the cooperation layer provides the tree abstraction by appropriately distributing and concentrating traffic over the network. Finally, at the bottom, the physical layer implements the distribution and concentration, dealing with the effects of noise and interference. Conveniently, we show that the problem of optimally selecting which caches should serve the content to the user, and which proportions of the content each such cache should provide, can be solved efficiently by a distributed algorithm requiring access only to the routing layer abstraction of the network. Additionally, we establish that the commonly used heuristic of serving content to a user from the nearest cache can lead to particularly poor performance. Collectively, our results provide a variety of useful design principles of wireless network architects.

Click for larger view

Antenna Arrays for Secure Communication

Ashish Khisti and Gregory W. Wornell

It is well understood that multiple-element antenna arrays, when combined with appropriate multi-input multi-output (MIMO) communication techniques, can greatly increase robustness and throughput in wireless communication systems.  As a result, there has been extensive deployment of such technology in recent years.    However, such technology has an equally important role to play in increasing security in wireless communication.   In this work, we investigate a wireless scenario in which there is a sender, an intended receiver, and a computationally-unbounded eavesdropper, each of which has its own antenna array.   For such systems, we develop a computable expression for the secrecy capacity, i.e., the highest rate at which the sender can communicate to the legitimate receiver without leaking information to the eavesdropper, as a function of the numbers of antennas involved and the particular channel realizations.   As part of such analysis, we design ``MIMO wiretap codes'' for approaching such fundamental limits.   Interestingly, such codes can be significantly better than seemingly natural ``masked MIMO'' designs that send information along directions in which there is gain to the intended receiverand synthetic noise along directions in which there is not.     Our analysis also leads to some useful rules of thumb for system design:  1) to optimally thwart an attacker, sender and legitimate receiver should divide their available antenna elements between them in the ratio of 2:1; and 2) to prevent secure communication, the eavesdropper needs 3 times as many antenna elements as sender and intended receiver have combined.

Click for larger view

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.