Title: Single Letter Expression of Capacity for a Class of Channels with Memory,
Abstract: We study finite alphabet channels with Unit Memory on the previous Channel
Outputs called UMCO channels. We identify necessary and sufficient conditions,
to test whether the capacity achieving channel input distributions with
feedback are time-invariant, and whether feedback capacity is characterized by
single letter, expressions, similar to that of memoryless channels. The method
is based on showing that a certain dynamic programming equation, which in
general, is a nested optimization problem over the sequence of channel input
distributions, reduces to a non-nested optimization problem. Moreover, for UMCO
channels, we give a simple expression for the ML error exponent, and we
identify sufficient conditions to test whether feedback does not increase
capacity. We derive similar results, when transmission cost constraints are
imposed. We apply the results to a special class of the UMCO channels, the
Binary State Symmetric Channel (BSSC) with and without transmission cost
constraints, to show that the optimization problem of feedback capacity is
non-nested, the capacity achieving channel input distribution and the
corresponding channel output transition probability distribution are
time-invariant, and feedback capacity is characterized by a single letter
formulae, precisely as Shannon's single letter characterization of capacity of
memoryless channels. Then we derive closed form expressions for the capacity
achieving channel input distribution and feedback capacity. We use the closed
form expressions to evaluate an error exponent for ML decoding.