Error Correcting Codes for Distributed Control
Mar 09, 2012
from 12:00 PM to 01:00 PM
|Where||ENGR. IV Bldg., Maxwell 57-124|
|Add event to calendar||
Ravi Teja Sukhavasi - Caltech
Coding and information theory, the joint pillars upon which
the telecommunications revolution has thrived, deal with how to reliably
transmit information over unreliable channels. This is done by gathering large
blocks of data and encoding them into larger blocks of data before transmitting,
thereby achieving reliability at the expense of encoding/decoding delay.
Control theory, on the other hand, is concerned with regulating the behavior of
dynamical systems through feedback. At the heart of feedback control is
real-time measurement of signals and application of control inputs. Most
traditional applications were characterized by co-located measurement and
control units, and there was no need to communicate measurement/control signals
over unreliable channels. Hence control theory could largely ignore information
theoretic considerations. But there are increasingly many instances of
networked control systems where measurement and control signals are transmitted
across noisy channels. In such settings, one needs to deal with the real-time
constraints of the control system and the unreliability of the underlying
communication medium in a simultaneous and systematic way.
The work of Schulman and Sahai over the past two decades, and their development of the notions of "tree codes" and "anytime
capacity", provides the theoretical framework for studying such problems. To stabilize an unstable plant driven by bounded noise over a noisy channel one needs real-time encoding and real-time decoding and a reliability which increases exponentially with decoding delay, which is what tree codes guarantee. Even though the central role of tree codes in interactive communication problems is well understood, there has been scant practical progress in this area because explicit constructions of tree codes with efficient encoding and decoding did not exist. We prove the existence of "linear" tree codes with "high probability" and, for the first time, construct explicit codes with efficient encoding and decoding for the erasure channel. The resulting decoder has an expected computational complexity that is constant per time instant and is such that the probability of the computations at each time instant exceeding kC^3 decays exponentially in C. We demonstrate the efficacy of the method through examples and mention several open problems and directions for future work.