Error-Correcting Codes for Automatic Control

Speaker: Leonard J. Schulman , California Institute of Technology


In many control-theory applications one can classify all possible states of the device by an infinite state graph with polynomially-growing expansion. In order for a controller to control or estimate the state of such a device, it must receive reliable communications from its sensors; if there is channel noise, the encoding task is subject to a stringent real-time constraint. We show a constructive on-line error correcting code that works for this class of applications. Our code is asymptotically optimal subject to the channel capacity constraint, is computationally efficient, and enables on-line estimation and control in the presence of channel noise. Our construction establishes a constructive and asymptotically-optimal analog of Shannon coding theorem for control applications. Joint work with Rafail Ostrovsky and Yuval Rabani.