Namespaces
Variants
Actions

Difference between revisions of "Channel with a finite number of states"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
 
Line 1: Line 1:
 +
<!--
 +
c0214501.png
 +
$#A+1 = 35 n = 0
 +
$#C+1 = 35 : ~/encyclopedia/old_files/data/C021/C.0201450 Channel with a finite number of states,
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
 +
 +
{{TEX|auto}}
 +
{{TEX|done}}
 +
 
''finite-state channel''
 
''finite-state channel''
  
A [[Communication channel|communication channel]] for which the statistical properties of the output signal at a time <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021450/c0214501.png" /> 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|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, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021450/c0214502.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021450/c0214503.png" />, for the components of the input and output signals. Suppose that functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021450/c0214504.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021450/c0214505.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021450/c0214506.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021450/c0214507.png" />, are given, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021450/c0214508.png" /> is a finite set, called the set of states of the channel, as well as a probability distribution <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021450/c0214509.png" />. Intuitively, the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021450/c02145010.png" /> defines the conditional probability that at a time <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021450/c02145011.png" /> the signal <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021450/c02145012.png" /> appears at the output and the channel goes over to the state <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021450/c02145013.png" /> under the condition that the signal <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021450/c02145014.png" /> was transmitted and that at the previous moment <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021450/c02145015.png" /> the channel was in state <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021450/c02145016.png" />. The distribution <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021450/c02145017.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021450/c02145018.png" /> be recursively defined by the formulas
+
A [[Communication channel|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|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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021450/c02145019.png" /></td> </tr></table>
+
$$
 +
Q _ {n} ( y  ^ {n} , s _ {0} ; \
 +
\widetilde{y}  {}  ^ {n} , s _ {n} ) =
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021450/c02145020.png" /></td> </tr></table>
+
$$
 +
= \
 +
\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 }  ),
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021450/c02145021.png" /></td> </tr></table>
+
$$
 +
Q _ {1} ( y, s _ {0} ; \widetilde{y}  , s _ {1} )
 +
= q ( y, s _ {0} ; \widetilde{y}  , s _ {1} ),
 +
$$
  
where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021450/c02145022.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021450/c02145023.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021450/c02145024.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021450/c02145025.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021450/c02145026.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021450/c02145027.png" />. Let
+
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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021450/c02145028.png" /></td> </tr></table>
+
$$
 +
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
 
Then the transition function
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021450/c02145029.png" /></td> </tr></table>
+
$$
 +
Q _ {n} ( y  ^ {n} , \widetilde{y}  {}  ^ {n} )  = \
 +
{\mathsf P} \{ \widetilde \eta  {}  ^ {n} = \widetilde{y}  {}  ^ {n}  \mid  \eta  ^ {n} =
 +
y  ^ {n} \}
 +
$$
  
of segments of length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021450/c02145030.png" /> of the channel with a finite number of states, for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021450/c02145031.png" />, is, by definition, equal to
+
of segments of length $  n $
 +
of the channel with a finite number of states, for any $  n $,  
 +
is, by definition, equal to
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021450/c02145032.png" /></td> </tr></table>
+
$$
 +
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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021450/c02145033.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021450/c02145034.png" /> are the segments of length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021450/c02145035.png" /> of the input and the output of the channel.
+
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 ,
 
For references see ,
  
 
in the article [[Communication channel|Communication channel]].
 
in the article [[Communication channel|Communication channel]].

Latest revision as of 16:43, 4 June 2020


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.

How to Cite This Entry:
Channel with a finite number of states. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Channel_with_a_finite_number_of_states&oldid=18715
This article was adapted from an original article by R.L. DobrushinV.V. Prelov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article