On the evaluation of the capacity of channels with memory

The determination of the capacity of a binary finite state channel with memory is in general a very difficult task. In this paper we present a new systematic method which amounts to computing the entropy of the channel error sequence represented as the output of a stochastic finite state automaton with state cardinality at most twice the one of the original channel. Each state of the original channel yields a maximum of two states in the automaton state transition diagram according to whether the preceeding error symbol was a one or a zero. The error class E is defined as the class of all states terminating on an error while the remaining class E¯ contains states with transitions corresponding to no error. Consequently any path along states in E represents a solid burst of errors and reciprocally all the solid bursts of errors can only result from transitions between states in E and the same property applies to errorless events which can only result from transitions between states in E¯. If the channel has K states, the final result is obtained by computing at most 2K series whose elements are the coefficients of the generating functions of the runs of 0´s after an error terminating in any of the states of E and of the runs of 1´s after an errorless event terminating in any of the states of E¯