“Theoretical underpinnings of green radios”

Summary: Broadly, I am interested in minimizing the power consumption in a communication systems. Thus far, my emphasis has been on decoding power --- which is a huge power sink at high data-rates.

The goal: communication and computation. The communication distances are getting smaller: from hundreds of kilometers in the 60's, to a few meters, or even smaller (e.g. 60 GHz communication). At such small distances, the required power for decoding computation can be orders of magnitude larger than the transmit power. How should information and communication theory adapt to this change? A computational abstraction: In a sequence of papers, [ITW'07, ISIT '08, ISIT '09, JSAC '11], we arrive at a “VLSI model of decoding” in order to account for power consumed in the decoding process. The model maps naturally to the fully-parallel architecture of modern-day message-passing decoders, and includes all message-passing algorithms.

A fundamental computational lower bound: In [JSAC'11], we derive fundamental lower bounds on the required number of decoding “iterations,” or clock-cycles, that are needed in order to attain a specified error probability Pe at a given gap from the channel capacity for any code/decoder in the VLSI model of decoding. These bounds show that the total number of decoding iterations must diverge to infinity as Pe -> 0, or as the rate approaches capacity (i.e. the transmit power approaches the Shannon limit). Results are also extended to Gaussian broadcast [ISIT '08].

A fundamental lower bound on total power: Shannon's “waterfall” curves illustrate that the transmit power can remain bounded even as Pe converges to zero. In [JSAC '11], using our bounds on decoding complexity, we explore the behavior of total (transmit + decoding) power as a function of Pe. Unlike the Shannon-waterfall behavior for transmit power, we observe what we call a “waterslide” behavior for total power: it must diverge to infinity as Pe converges to zero. Further, the code must operate at a gap from capacity to limit decoding power. (just as the channel capacity depends on the SNR, these bounds depend on the technology (e.g. 90 nm CMOS) and on the complexity of operations performed by the nodes.)

An “experiment” integrating teaching and research: how low can the decoding power be? To investigate the power consumption of the simplest message-passing (bit-flipping) decoders, I helped design course projects for the course on Digital Integrated Circuits (EE 141) in collaboration with Prof. Jan Rabaey (I was not a TA for the course). The results that we crowd-sourced from the 51 students' projects were interesting: for these simple decoders, the power consumed in the wires can dominate that consumed in the nodes.

Code/decoder design should depend on the desired error-probability: Inspired by the above crowd-sourcing “experiment,” we derive a fundamental result [CISS '11] that shows that the decoder wire-lengths must increase as we demand lower and lower error probabilities. Our simulations of decoding power in [Ganesan, Grover, Rabaey '11 in prep.] verify this empirically: codes that minimize wire-lengths for the desired error probability can be substantially more efficient. The implications are significant: the current wireless standards (that follow the theoretical constructions) rarely propose different codes for different error-probabilities, and thus might waste decoding power.

Coding in interference environments: What is the utility of coding in environments with interference? In [ISTC '10, JSAC '11], under simplifying assumptions, we show a simple fact: coding is required to support a higher density of links (i.e. simultaneous communication links per sq-meter) when interference is treated as noise.

Wireless information and power transfer: For future systems, it is intriguing to consider the transfer information and power on the same channel. For Tesla's coupled inductor setup, we show [ISIT '10b] that there is a tradeoff between power-transfer and the rate of communication.


Relevant references

[ITW '07] Pulkit Grover, Bounds on the Tradeoff between decoding complexity and rate for codes on graphs, Proceedings of the IEEE Information Theory Workshop (ITW) 2007, Lake Tahoe, CA, 2007. [PDF]

[ISIT '08] Pulkit Grover and Anant Sahai, Green Codes: Energy-Efficient Short-Range Communication. Proceedings of the 2008 International Symposium on Information Theory in Toronto, 2008. [PDF] [Slides]

[ISIT '09] Pulkit Grover and Anant Sahai, Time-division multiplexing for Green Broadcasting. (extended version) Proceedings of the IEEE International Symposium on Information Theory (ISIT), 2009. [Short description] [PDF] [Handout] [Slides] [MATLAB code]

[ISIT '10] Pulkit Grover and Anant Sahai, Shannon meets Tesla: Wireless information and power transfer. IEEE International Symposium on Information Theory (ISIT) 2010. [PDF]

[ISTC '10] Pulkit Grover, Kristen Ann Woyach, Hari Palaiyanur and Anant Sahai, An interference-aware perspective on decoding power. 6th International Symposium on turbo codes and iterative information processing (ISTC), to appear. [PDF]

[JSAC '11] Pulkit Grover, Kristen Ann Woyach and Anant Sahai, Towards a communication-theoretic understanding of system-level power consumption, (conditionally) accepted to the IEEE Journal of Selected Areas in Communication (JSAC) Special Issue on Energy-Efficient Wireless Communications. [PDF][MATLAB Code]

[CISS '11] Pulkit Grover and Anant Sahai, Fundamental bounds on the interconnect complexity of decoder implementations, Accepted at Conference on Information Sciences and Systems (CISS) 2011. [PDF]

[Ganesan, Grover, Rabaey '11 in prep.] Karthik Ganesan, Pulkit Grover and Jan Rabaey. “Decoding power consumption can increase significantly with increased wire lengths: Empirical results.”

“Control and communication in cyber-physical systems”

The goal: How do we connect the “cyber” -- the computational/ communicating/ controlling agents -- with the “physical” -- the world around us? My dissertation lays down the foundations of a theory to help answer this question.

The question: Let us consider two control agents that are connected using a noisy communication link. How should they share their workload? I was surprised to find that we do not know the answer! This is because most of the problem formulations and solution techniques in this field are inspired from those in modern communication theory, and caricature the control agents into mere “observers” or “controllers.”

The “observers” cannot act on the system, and therefore they communicate their observations to the “controllers.” The “controllers” cannot observe the state directly, and thus rely on the signals sent by the “observers” to decide on their actions. In a realistic control system, these caricatures of the control agents may be extremely limiting! For instance, it does not even tell us how the control effort can be distributed among different agents.

A theory of implicit communication: The crux of this issue is captured in a deceptively simple problem called the Witsenhausen counterexample, which has been open despite more than 40 years of research effort. In my dissertation, I provide the first provably approximately-optimal solution to the Witsenhausen counterexample by understanding the potential of implicit communication between the controllers. These approximately-optimal solutions were developed in the following sequence of results. In [CDC '08, IJSCC '10, ITW '10], we introduce a vector version of Witsenhausen's counterexample, and obtain approximately-optimal solutions for an asymptotically infinite- length version of the problem. In [ConCom '09, CDC '09, TAC '10 Sub.], we pull the results back to finite-lengths, including the original (scalar) counterexample, using techniques from large-deviation theory.

The work has received attention within Berkeley and outside and across communities of control and commmunication, with the Best Student Paper Award at IEEE Conference on Decision and Control, CDC 2010, the General Chairs' Recognition award for Interactive Papers at IEEE CDC 2009, and a finalist for the Best Student Paper Award at IEEE International Symposium on Information Theory (ISIT) 2010.

Building a communication theory for decentralized control: In my dissertation, I argue that the Witsenhausen counterexample has been a major bottleneck in understanding the interplay of control and communication. Because the counterexample was viewed as essentially unsolvable, it forced problem formulations into corners where the obtained engineering insights could only be very limited. Our approach of using semi-deterministic models to obtain approximately-optimal strategies can be extended to understand toy problems of control under commu- nication constraints which could not have been understood earlier. For instance, what happens when controllers can communicate implicitly as well as explicitly [Allerton '10]? How should one communicate implicitly in a dynamic setting with feedback [Ph.D. thesis]? Various extensions of the counterexample appear in [Allerton '09, ISIT '10, CDC '10].

Relevant references

[CDC '08] Pulkit Grover and Anant Sahai, A vector version of Witsenhausen's counterexample : Towards convergence of control, communication and computation. Proceedings of the IEEE Conference on Decision and Control in Cancun, Mexico, 2008. [PDF] [Handout] [Slides]

[IJSCC '10] Pulkit Grover and Anant Sahai, Vector Witsenhausen Counterexample as Assisted Interference Suppression. Special Issue on "Information Processing and Decision Making in Distributed Control Systems" of the International Journal of Systems, Control and Communications (IJSCC), 2010.

[ITW '10] Pulkit Grover, Aaron B. Wagner and Anant Sahai, Information Embedding Meets Distributed Control. Proceedings of the IEEE Information Theory Workshop 2010, Cairo, Egypt. [PDF] [MATLAB code]

[ConCom '09] Pulkit Grover, Anant Sahai and Se Yong Park, The finite-dimensional Witsenhausen counterexample. (Extended version) Proceedings of the 7th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOpt), Workshop on Control over Communication Channels (ConCom) 2009. [Short description] [PDF] [Handout] [Slides][MATLAB code]

[Allerton '09] Pulkit Grover, Se Yong Park and Anant Sahai, On the Generalized Witsenhausen Counterexample. Allerton Conference on Communication, Control, and Computing, Illinois, 2009. [PDF]

[ISIT '10] Pulkit Grover and Anant Sahai, Distributed signal cancelation inspired by Witsenhausen's counterexample. IEEE International Symposium on Information Theory (ISIT) 2010. [expanded PDF] [Proceedings version]

[TAC '10 Sub.] Pulkit Grover, Anant Sahai and Se Yong Park, The finite-dimensional Witsenhausen counterexample. IEEE Transactions on Automatic Control, Submitted (2010). [PDF] [Talk Handout] [Talk Slides][MATLAB code]