Channel with a finite number of states

finite-state channel

A communication channel for which the statistical properties of the output signal at a time $ t $ are determined by the input signal at this moment and the state of the channel at the previous moment, and where the set of possible states of the channel is finite. A channel with a finite number of states can also be defined by a finite probabilistic automaton (cf. Automaton, probabilistic). Below a rigorous definition is given of a discrete-time homogeneous channel with a finite number of states and with finite spaces of values, $ Y $ and $ \widetilde{Y} $, for the components of the input and output signals. Suppose that functions $ q ( y, s ^ \prime ; \widetilde{y} , s ^ {\prime\prime} ) $, $ y \in Y $, $ \widetilde{y} \in \widetilde{Y} $, $ s ^ \prime , s ^ {\prime\prime} \in S $, are given, where $ S $ is a finite set, called the set of states of the channel, as well as a probability distribution $ \{ {p _ {s _ {0} } } : {s _ {0} \in S } \} $. Intuitively, the function $ q ( y, s ^ \prime ; \widetilde{y} , s ^ {\prime\prime} ) $ defines the conditional probability that at a time $ k \tau $ the signal $ \widetilde{y} $ appears at the output and the channel goes over to the state $ s ^ {\prime\prime} $ under the condition that the signal $ y $ was transmitted and that at the previous moment $ ( k - 1) \tau $ the channel was in state $ s ^ \prime $. The distribution $ \{ {p _ {s _ {0} } } : {s _ {0} \in S } \} $ can be regarded as the probability distribution of the initial state of the channel (that is, the state of the channel at the initial moment). Let the functions $ Q _ {n} ( y ^ {n} , s _ {0} ; \widetilde{y} {} ^ {n} , s _ {n} ) $ be recursively defined by the formulas

$$ Q _ {n} ( y ^ {n} , s _ {0} ; \ \widetilde{y} {} ^ {n} , s _ {n} ) = $$

$$ = \ \sum _ {s _ {n - 1 } \in S } q ( y _ {n} ,\ s _ {n - 1 } ; \widetilde{y} _ {n} , s _ {n} ) Q _ {n - 1 } ( y ^ {n - 1 } , s _ {0} ; \widetilde{y} {} ^ {n - 1 } , s _ {n - 1 } ), $$

$$ Q _ {1} ( y, s _ {0} ; \widetilde{y} , s _ {1} ) = q ( y, s _ {0} ; \widetilde{y} , s _ {1} ), $$

where $ y ^ {n} = ( y _ {1} \dots y _ {n} ) $, $ y _ {i} \in Y $, $ \widetilde{y} _ {i} \in \widetilde{Y} $, $ i = 1 \dots n $, $ s _ {k} \in S $, $ k = 0 \dots n $. Let

$$ Q _ {n} ( y ^ {n} , s _ {0} ; \widetilde{y} {} ^ {n} ) = \ \sum _ {s _ {n} \in S } Q _ {n} ( y ^ {n} , s _ {0} ; \widetilde{y} {} ^ {n} , s _ {n} ). $$

Then the transition function

$$ Q _ {n} ( y ^ {n} , \widetilde{y} {} ^ {n} ) = \ {\mathsf P} \{ \widetilde \eta {} ^ {n} = \widetilde{y} {} ^ {n} \mid \eta ^ {n} = y ^ {n} \} $$

of segments of length $ n $ of the channel with a finite number of states, for any $ n $, is, by definition, equal to

$$ Q _ {n} ( y ^ {n} , \widetilde{y} {} ^ {n} ) = \ \sum _ {s _ {0} \in S } p _ {s _ {0} } Q _ {n} ( y ^ {n} , s _ {0} ; \widetilde{y} {} ^ {n} ), $$

where $ \eta ^ {n} = ( \eta _ {1} \dots \eta _ {n} ) $ and $ \widetilde \eta {} ^ {n} = ( \widetilde \eta _ {1} \dots \widetilde \eta _ {n} ) $ are the segments of length $ n $ of the input and the output of the channel.

For references see ,

in the article Communication channel.