Zero-Error Feedback Capacity for Bounded Stabilization and Finite-State Additive Noise Channels
Amir Hossein Saberi, Farhad Farokhi, Girish N. Nair
Abstract
This article studies the zero-error feedback capacity of <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">causal</i> discrete channels with memory. First, by extending the classical zero-error feedback capacity concept, a new notion of <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">uniform zero-error feedback capacity</i> <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$C_{0f} $ </tex-math></inline-formula> for such channels is introduced. Using this notion a tight condition for bounded stabilization of unstable noisy linear systems via causal channels is obtained, assuming no channel state information at either end of the channel. Furthermore, the zero-error feedback capacity of a class of additive noise channels is investigated. It is known that for a discrete channel with correlated additive noise, the ordinary capacity with or without feedback is equal <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\log q-\mathcal {H}_{ch} $ </tex-math></inline-formula> , where <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathcal {H}_{ch} $ </tex-math></inline-formula> is the entropy rate of the noise process and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$q $ </tex-math></inline-formula> is the input alphabet size. In this paper, for a class of finite-state additive noise channels (FSANCs), it is shown that the zero-error feedback capacity is either zero or <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$C_{0f} =\log q -h_{ch} $ </tex-math></inline-formula> , where <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$h_{ch} $ </tex-math></inline-formula> is the <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">topological entropy</i> of the noise process. A condition is given to determine when the zero-error capacity with or without feedback is zero. This, in conjunction with the stabilization result, leads to a “Small-Entropy Theorem”, stating that stabilization over FSANCs can be achieved if the sum of the topological entropies of the linear system and the channel is smaller than <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\log q$ </tex-math></inline-formula> .