Error Correcting Codes for Distributed Control

Ravi Teja Sukhavasi - Caltech

Abstract:

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.