Error-Correcting Codes for Automatic Control
Rafail Ostrovsky, Yuval Rabani, Leonard J. Schulman
Abstract:
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 is computationally efficient and enables on-line estimation and control in the presence of channel noise. It establishes a constructive (and optimal-within-constants) analog, for control applications, of the Shannon coding theorem.
comment: Appeared in Proceedings of 46st Annual IEEE Symposium on the Foundations of Computer Science (FOCS-2005).
Fetch PostScript file of the paper Fetch PDF file of the paper