Namespaces
Variants
Actions

Difference between revisions of "Channel with multiple directions"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(latex details)
 
(One intermediate revision by one other user not shown)
Line 1: Line 1:
 +
<!--
 +
c0214701.png
 +
$#A+1 = 90 n = 0
 +
$#C+1 = 90 : ~/encyclopedia/old_files/data/C021/C.0201470 Channel with multiple directions,
 +
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}}
 +
 
''multi-terminal channel, multi-user channel''
 
''multi-terminal channel, multi-user channel''
  
A [[Communication channel|communication channel]] for which it is possible to transmit information in several directions simultaneously. The description which follows is for a memoryless discrete-time multi-user channel with finite input and output alphabets. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c0214701.png" /> be <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c0214702.png" /> finite sets, where (the alphabet) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c0214703.png" /> is the set of possible signals which the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c0214704.png" />-th transmitter can send, and let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c0214705.png" /> be <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c0214706.png" /> finite sets, where (the alphabet) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c0214707.png" /> is the set of possible signals which the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c0214708.png" />-th receiver can receive. Suppose further that a [[Stochastic matrix|stochastic matrix]]
+
A [[Communication channel|communication channel]] for which it is possible to transmit information in several directions simultaneously. The description which follows is for a memoryless discrete-time multi-user channel with finite input and output alphabets. Let $  Y _ {1} \dots Y _ {s} $
 +
be $  s $
 +
finite sets, where (the alphabet) $  Y _ {i} $
 +
is the set of possible signals which the $  i $-
 +
th transmitter can send, and let $  \widetilde{Y}  _ {1} \dots \widetilde{Y}  _ {r} $
 +
be $  r $
 +
finite sets, where (the alphabet) $  \widetilde{Y}  _ {j} $
 +
is the set of possible signals which the $  j $-
 +
th receiver can receive. Suppose further that a [[Stochastic matrix|stochastic matrix]]
  
<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/c021470/c0214709.png" /></td> </tr></table>
+
$$
 +
q ( y _ {1} \dots y _ {s} ; \
 +
\widetilde{y}  _ {1} \dots \widetilde{y}  _ {r} ),
 +
$$
  
<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/c021470/c02147010.png" /></td> </tr></table>
+
$$
 +
y _ {i}  \in  Y _ {i} ,\  \widetilde{y}  _ {j}  \in \
 +
\widetilde{Y}  _ {j} ,\  i = 1 \dots s; \  j = 1 \dots r,
 +
$$
  
is given. Two sets of random vectors <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c02147011.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c02147012.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c02147013.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c02147014.png" />, defined on some [[Probability space|probability space]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c02147015.png" />, are said to be connected by a segment of length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c02147016.png" /> of a homogeneous multi-user channel with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c02147017.png" /> inputs and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c02147018.png" /> outputs if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c02147019.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c02147020.png" />, (<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c02147021.png" />; <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c02147022.png" />; <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c02147023.png" />), take values in the sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c02147024.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c02147025.png" />, respectively, and the formula
+
is given. Two sets of random vectors $  ( \eta  ^ {(1)} \dots \eta  ^ {(n)} ) $
 +
and $  ( \widetilde \eta  {}  ^ {(1)} \dots \widetilde \eta  {}  ^ {(n)} ) $,  
 +
where $  \eta  ^ {(k)} = ( \eta _ {1}  ^ {(k)} \dots \eta _ {s}  ^ {(k)} ) $,  
 +
$  \widetilde \eta  {}  ^ {(k)} = ( \widetilde \eta  {} _ {1}  ^ {(k)} \dots \widetilde \eta  {} _ {r}  ^ {(k)} ) $,  
 +
defined on some [[Probability space|probability space]] $  ( \Omega , \mathfrak A , {\mathsf P} ) $,  
 +
are said to be connected by a segment of length $  n $
 +
of a homogeneous multi-user channel with $  s $
 +
inputs and $  r $
 +
outputs if $  \eta _ {1}  ^ {(k)} $
 +
and $  \widetilde \eta  {} _ {j}  ^ {(k)} $,  
 +
( $  i = 1 \dots s $;  
 +
$  j = 1 \dots r $;  
 +
$  k = 1 \dots n $),  
 +
take values in the sets $  Y _ {i} $
 +
and $  \widetilde{Y}  _ {j} $,  
 +
respectively, and the formula
  
<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/c021470/c02147026.png" /></td> </tr></table>
+
$$
 +
{\mathsf P} \{ {
 +
( \widetilde \eta  {}  ^ {(1)} \dots \widetilde \eta  {}  ^ {(n)} )  = \
 +
( \widetilde{y}  {}  ^ {(1)} \dots \widetilde{y}  {}  ^ {(n)} )
 +
} \mid
 +
$$
  
<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/c021470/c02147027.png" /></td> </tr></table>
+
$$
 +
\mid  \
 +
{} {
 +
( \eta  ^ {(1)} \dots \eta  ^ {(n)} ) = ( y  ^ {(1)} \dots y  ^ {(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/c021470/c02147028.png" /></td> </tr></table>
+
$$
 +
= \
 +
\prod _ {k = 1 } ^ { n }  q ( y _ {1}  ^ {(k)} \dots y _ {s}  ^ {(k)}; \widetilde{y}  {} _ {1}  ^ {(k)} \dots \widetilde{y}  {} _ {r}  ^ {(k)} )
 +
$$
  
holds for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c02147029.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c02147030.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c02147031.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c02147032.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c02147033.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c02147034.png" />; <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c02147035.png" />.
+
holds for any $  y  ^ {(k)} = ( y _ {1}  ^ {(k)} \dots y _ {s}  ^ {(k)} ) $
 +
and $  \widetilde{y}  {}  ^ {(k)} = ( \widetilde{y}  {} _ {1}  ^ {(k)} \dots \widetilde{y}  {} _ {r}  ^ {(k)} ) $,  
 +
$  k = 1 \dots n $,  
 +
$  y _ {i}  ^ {(k)} \in Y _ {i} $,  
 +
$  \widetilde{y}  {} _ {j}  ^ {(k)} \in \widetilde{Y}  _ {j} $,  
 +
$  i = 1 \dots s $;  
 +
$  j = 1 \dots r $.
  
The intuitive interpretation is that each input and each output of a multi-user channel is situated in a different terminal (end), i.e. there are <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c02147036.png" /> terminals in total. This means that a transmitter or receiver situated in some terminal cannot use information known to the transmitters or the receivers of other terminals. Multi-user channels possessing this property are often called pure channels, in contrast to mixed multi-user channels, for which there exist terminals containing simultaneously several inputs and outputs of the channel. The complexity of the analysis of mixed multi-user channels is due to the fact that the transmitters of some terminal can, in selecting the next signal to be transmitted, use the information obtained at that moment by all the receivers of the given terminal; the receivers of this terminal can in turn use all the information available in the terminal at the given moment.
+
The intuitive interpretation is that each input and each output of a multi-user channel is situated in a different terminal (end), i.e. there are $  s + r $
 +
terminals in total. This means that a transmitter or receiver situated in some terminal cannot use information known to the transmitters or the receivers of other terminals. Multi-user channels possessing this property are often called pure channels, in contrast to mixed multi-user channels, for which there exist terminals containing simultaneously several inputs and outputs of the channel. The complexity of the analysis of mixed multi-user channels is due to the fact that the transmitters of some terminal can, in selecting the next signal to be transmitted, use the information obtained at that moment by all the receivers of the given terminal; the receivers of this terminal can in turn use all the information available in the terminal at the given moment.
  
The most general problem in information transmission along a pure memoryless multi-user channel, as intuitively described above, is the following. Suppose that there are <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c02147037.png" /> discrete stationary sources of information <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c02147038.png" /> (cf. [[Information, source of|Information, source of]]); <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c02147039.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c02147040.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c02147041.png" /> is the set of all non-empty subsets of the index set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c02147042.png" /> generating the messages <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c02147043.png" />, where the individual components of the message <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c02147044.png" /> take values in some set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c02147045.png" /> of volume <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c02147046.png" />; <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c02147047.png" /> can be required as the message intended for transmission from the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c02147048.png" />-th input of the channel to all outputs with indices <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c02147049.png" />. The message at the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c02147050.png" />-th output, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c02147051.png" />, is a set of random processes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c02147052.png" />, where
+
The most general problem in information transmission along a pure memoryless multi-user channel, as intuitively described above, is the following. Suppose that there are $  s ( 2  ^ {r} - 1) $
 +
discrete stationary sources of information $  U ( i, \Delta ) $(
 +
cf. [[Information, source of|Information, source of]]); $  i = i \dots s $,  
 +
$  \Delta \in D $,  
 +
where $  D $
 +
is the set of all non-empty subsets of the index set $  \{ 1 \dots r \} $
 +
generating the messages  $  \xi ( i, \Delta ) = \{ {\xi _ {k} ( i, \Delta ) } : {k = . . . , - 1, 0, 1 , . . . } \} $,  
 +
where the individual components of the message $  \xi _ {k} ( i, \Delta ) $
 +
take values in some set $  X ( i, \Delta ) $
 +
of volume $  M ( i, \Delta ) $;  
 +
$  \xi ( i, \Delta ) $
 +
can be required as the message intended for transmission from the $  i $-
 +
th input of the channel to all outputs with indices $  j \in \Delta $.  
 +
The message at the $  j $-
 +
th output, $  j = 1 \dots r $,  
 +
is a set of random processes $  \{ {\widetilde \xi  ( i, \Delta ;  j) } : {i = 1 \dots s,  \textrm{ and }  \Delta  \textrm{ such  that  }  j \in \Delta } \} $,  
 +
where
  
<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/c021470/c02147053.png" /></td> </tr></table>
+
$$
 +
\widetilde \xi  ( i, \Delta ; j)  = \
 +
\{ {\widetilde \xi  _ {k} ( i, \Delta ; j) } : {
 +
k = .  .  .  , - 1, 0, 1 , . . . } \}
 +
$$
  
and the components <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c02147054.png" /> take values in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c02147055.png" />. Let segments of messages
+
and the components $  \widetilde \xi  _ {k} ( i, \Delta ;  j) $
 +
take values in $  X ( i, \Delta ) $.  
 +
Let segments of messages
  
<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/c021470/c02147056.png" /></td> </tr></table>
+
$$
 +
\{ {\xi  ^ {L} ( i, \Delta ) =
 +
( \xi _ {1} ( i, \Delta ) \dots \xi _ {L} ( i, \Delta )) } : {
 +
i = 1 \dots s; \Delta \in D } \}
 +
$$
  
of length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c02147057.png" /> be transmitted using a segment of length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c02147058.png" /> of a memoryless multi-user channel using the following block methods of (en)coding and decoding. The (en)coding is determined by a set of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c02147059.png" /> (en)coding mappings <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c02147060.png" /> such that
+
of length $  L $
 +
be transmitted using a segment of length $  N $
 +
of a memoryless multi-user channel using the following block methods of (en)coding and decoding. The (en)coding is determined by a set of $  s $(
 +
en)coding mappings $  f _ {i} $
 +
such that
  
<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/c021470/c02147061.png" /></td> </tr></table>
+
$$
 +
f _ {i} : \
 +
\prod _ {\Delta \in D }
 +
X ( i, \Delta )  \rightarrow  Y _ {i}  ^ {N} ,\ \
 +
i = 1 \dots s,
 +
$$
  
(<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c02147062.png" /> being the direct product of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c02147063.png" /> copies of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c02147064.png" />), and the decoding by a set of decoding mappings:
+
( $  Y _ {i}  ^ {N} $
 +
being the direct product of $  N $
 +
copies of $  Y _ {i} $),  
 +
and the decoding by a set of decoding mappings:
  
<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/c021470/c02147065.png" /></td> </tr></table>
+
$$
 +
g _ {j; i, \Delta }  : \
 +
\widetilde{Y}  {} _ {j}  ^ {N} \rightarrow X ( i, \Delta ),\ \
 +
j = 1 \dots r; i = 1 \dots s,
 +
$$
  
and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c02147066.png" /> is such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c02147067.png" />.
+
and $  \Delta $
 +
is such that $  j \in \Delta $.
  
The set of (en)coding functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c02147068.png" /> establishes a functional dependence between the segments of length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c02147069.png" /> of the messages of all possible sources and the segments of length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c02147070.png" /> of the signals at the inputs of the channel. The set of decoding functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c02147071.png" /> establishes a functional dependence between the segments of length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c02147072.png" /> of the signals at the outputs of the channel and the segments of length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c02147073.png" /> of the messages generated at each output. If the joint distribution of the segments of length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c02147074.png" /> of the messages, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c02147075.png" />, the (en)coding and decoding functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c02147076.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c02147077.png" />, and the transition probabilities of the memoryless multi-user channel are known, then one can calculate the error probability <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c02147078.png" />, defined by the formula <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c02147079.png" />.
+
The set of (en)coding functions $  \{ f _ {i} \} $
 +
establishes a functional dependence between the segments of length $  L $
 +
of the messages of all possible sources and the segments of length $  N $
 +
of the signals at the inputs of the channel. The set of decoding functions $  \{ g _ {j; i, \Delta }  \} $
 +
establishes a functional dependence between the segments of length $  N $
 +
of the signals at the outputs of the channel and the segments of length $  L $
 +
of the messages generated at each output. If the joint distribution of the segments of length $  L $
 +
of the messages, $  \xi  ^ {L} ( i, \Delta ) $,  
 +
the (en)coding and decoding functions $  \{ f _ {i} \} $
 +
and $  \{ g _ {j; i, \Delta }  \} $,  
 +
and the transition probabilities of the memoryless multi-user channel are known, then one can calculate the error probability $  p _ {e} $,  
 +
defined by the formula $  p _ {e} = {\mathsf P} \{ \xi  ^ {L} ( i, \Delta ) \neq \widetilde \xi  {}  ^ {L} ( i, \Delta ;  j)  \textrm{ for  some  }  i = 1 \dots s;  j = 1 \dots r,  \textrm{ and }  \Delta  \textrm{ such  that  }  j \in \Delta \} $.
  
A set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c02147080.png" /> of sets (vectors) of rates <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c02147081.png" /> in the <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c02147082.png" />-dimensional Euclidean space is called the capacity region of the channel considered here if for any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c02147083.png" /> there exist an integer <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c02147084.png" />, (en)codings <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c02147085.png" /> and decodings <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c02147086.png" /> such that
+
A set $  \mathfrak R $
 +
of sets (vectors) of rates $  R = \{ {R ( i, \Delta ) } : {i = 1 \dots s;  \Delta \in D } \} $
 +
in the $  s ( 2  ^ {r} - 1) $-
 +
dimensional Euclidean space is called the capacity region of the channel considered here if for any $  \epsilon > 0 $
 +
there exist an integer $  N $,  
 +
(en)codings $  \{ f _ {i} \} $
 +
and decodings $  \{ g _ {j; i, \Delta }  \} $
 +
such that
  
<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/c021470/c02147087.png" /></td> </tr></table>
+
$$
 +
{
 +
\frac{L  \mathop{\rm log}  M ( i, \Delta ) }{N}
 +
}  \geq  \
 +
R ( i, \Delta ) - \epsilon ,\ \
 +
p _ {e}  \leq  \epsilon .
 +
$$
  
The problem of describing the region <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c02147088.png" /> is one of the main problems in the theory of multi-user channels. In the general case this problem is unsolved. A final solution of it has been obtained only in certain special cases, for example, for multiple-access channels (that is, a multi-user channel with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c02147089.png" />) and for a certain class of broadcast channels (that is, channels with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c021/c021470/c02147090.png" />).
+
The problem of describing the region $  \mathfrak R $
 +
is one of the main problems in the theory of multi-user channels. In the general case this problem is unsolved. A final solution of it has been obtained only in certain special cases, for example, for multiple-access channels (that is, a multi-user channel with $  r = 1 $)  
 +
and for a certain class of broadcast channels (that is, channels with $  s = 1 $).
  
 
====References====
 
====References====
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  C. Shannon,  "Papers on information theory and cybernetics" , Moscow  (1963)  (In Russian; translated from English)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  E.C. van der Meulen,  "Advances in multi-user communication channels" , ''Proc. 1975 IEEE-USSR Joint Workshop Inform. Theory (Moscow, 15–19 Dec. 1975)'' , IEEE  (1976)  pp. 227–247</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  T.M. Cover,  "Broadcast channels"  ''IEEE Trans. Inform. Theory'' , '''18''' :  1  (1972)  pp. 2–14</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  D. Slepian,  J.K. Wolf,  "A coding theorem for multiple access channels with correlated sources"  ''Bell System Techn. J.'' , '''52''' :  7  (1973)  pp. 1037–1076</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  I. Csiszar,  J. Körner,  "Information theory. Coding theorems for discrete memoryless systems" , Akad. Kiado  (1981)</TD></TR></table>
 
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  C. Shannon,  "Papers on information theory and cybernetics" , Moscow  (1963)  (In Russian; translated from English)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  E.C. van der Meulen,  "Advances in multi-user communication channels" , ''Proc. 1975 IEEE-USSR Joint Workshop Inform. Theory (Moscow, 15–19 Dec. 1975)'' , IEEE  (1976)  pp. 227–247</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top">  T.M. Cover,  "Broadcast channels"  ''IEEE Trans. Inform. Theory'' , '''18''' :  1  (1972)  pp. 2–14</TD></TR><TR><TD valign="top">[4]</TD> <TD valign="top">  D. Slepian,  J.K. Wolf,  "A coding theorem for multiple access channels with correlated sources"  ''Bell System Techn. J.'' , '''52''' :  7  (1973)  pp. 1037–1076</TD></TR><TR><TD valign="top">[5]</TD> <TD valign="top">  I. Csiszar,  J. Körner,  "Information theory. Coding theorems for discrete memoryless systems" , Akad. Kiado  (1981)</TD></TR></table>

Latest revision as of 08:33, 14 January 2024


multi-terminal channel, multi-user channel

A communication channel for which it is possible to transmit information in several directions simultaneously. The description which follows is for a memoryless discrete-time multi-user channel with finite input and output alphabets. Let $ Y _ {1} \dots Y _ {s} $ be $ s $ finite sets, where (the alphabet) $ Y _ {i} $ is the set of possible signals which the $ i $- th transmitter can send, and let $ \widetilde{Y} _ {1} \dots \widetilde{Y} _ {r} $ be $ r $ finite sets, where (the alphabet) $ \widetilde{Y} _ {j} $ is the set of possible signals which the $ j $- th receiver can receive. Suppose further that a stochastic matrix

$$ q ( y _ {1} \dots y _ {s} ; \ \widetilde{y} _ {1} \dots \widetilde{y} _ {r} ), $$

$$ y _ {i} \in Y _ {i} ,\ \widetilde{y} _ {j} \in \ \widetilde{Y} _ {j} ,\ i = 1 \dots s; \ j = 1 \dots r, $$

is given. Two sets of random vectors $ ( \eta ^ {(1)} \dots \eta ^ {(n)} ) $ and $ ( \widetilde \eta {} ^ {(1)} \dots \widetilde \eta {} ^ {(n)} ) $, where $ \eta ^ {(k)} = ( \eta _ {1} ^ {(k)} \dots \eta _ {s} ^ {(k)} ) $, $ \widetilde \eta {} ^ {(k)} = ( \widetilde \eta {} _ {1} ^ {(k)} \dots \widetilde \eta {} _ {r} ^ {(k)} ) $, defined on some probability space $ ( \Omega , \mathfrak A , {\mathsf P} ) $, are said to be connected by a segment of length $ n $ of a homogeneous multi-user channel with $ s $ inputs and $ r $ outputs if $ \eta _ {1} ^ {(k)} $ and $ \widetilde \eta {} _ {j} ^ {(k)} $, ( $ i = 1 \dots s $; $ j = 1 \dots r $; $ k = 1 \dots n $), take values in the sets $ Y _ {i} $ and $ \widetilde{Y} _ {j} $, respectively, and the formula

$$ {\mathsf P} \{ { ( \widetilde \eta {} ^ {(1)} \dots \widetilde \eta {} ^ {(n)} ) = \ ( \widetilde{y} {} ^ {(1)} \dots \widetilde{y} {} ^ {(n)} ) } \mid $$

$$ \mid \ {} { ( \eta ^ {(1)} \dots \eta ^ {(n)} ) = ( y ^ {(1)} \dots y ^ {(n)} ) } \} = $$

$$ = \ \prod _ {k = 1 } ^ { n } q ( y _ {1} ^ {(k)} \dots y _ {s} ^ {(k)}; \widetilde{y} {} _ {1} ^ {(k)} \dots \widetilde{y} {} _ {r} ^ {(k)} ) $$

holds for any $ y ^ {(k)} = ( y _ {1} ^ {(k)} \dots y _ {s} ^ {(k)} ) $ and $ \widetilde{y} {} ^ {(k)} = ( \widetilde{y} {} _ {1} ^ {(k)} \dots \widetilde{y} {} _ {r} ^ {(k)} ) $, $ k = 1 \dots n $, $ y _ {i} ^ {(k)} \in Y _ {i} $, $ \widetilde{y} {} _ {j} ^ {(k)} \in \widetilde{Y} _ {j} $, $ i = 1 \dots s $; $ j = 1 \dots r $.

The intuitive interpretation is that each input and each output of a multi-user channel is situated in a different terminal (end), i.e. there are $ s + r $ terminals in total. This means that a transmitter or receiver situated in some terminal cannot use information known to the transmitters or the receivers of other terminals. Multi-user channels possessing this property are often called pure channels, in contrast to mixed multi-user channels, for which there exist terminals containing simultaneously several inputs and outputs of the channel. The complexity of the analysis of mixed multi-user channels is due to the fact that the transmitters of some terminal can, in selecting the next signal to be transmitted, use the information obtained at that moment by all the receivers of the given terminal; the receivers of this terminal can in turn use all the information available in the terminal at the given moment.

The most general problem in information transmission along a pure memoryless multi-user channel, as intuitively described above, is the following. Suppose that there are $ s ( 2 ^ {r} - 1) $ discrete stationary sources of information $ U ( i, \Delta ) $( cf. Information, source of); $ i = i \dots s $, $ \Delta \in D $, where $ D $ is the set of all non-empty subsets of the index set $ \{ 1 \dots r \} $ generating the messages $ \xi ( i, \Delta ) = \{ {\xi _ {k} ( i, \Delta ) } : {k = . . . , - 1, 0, 1 , . . . } \} $, where the individual components of the message $ \xi _ {k} ( i, \Delta ) $ take values in some set $ X ( i, \Delta ) $ of volume $ M ( i, \Delta ) $; $ \xi ( i, \Delta ) $ can be required as the message intended for transmission from the $ i $- th input of the channel to all outputs with indices $ j \in \Delta $. The message at the $ j $- th output, $ j = 1 \dots r $, is a set of random processes $ \{ {\widetilde \xi ( i, \Delta ; j) } : {i = 1 \dots s, \textrm{ and } \Delta \textrm{ such that } j \in \Delta } \} $, where

$$ \widetilde \xi ( i, \Delta ; j) = \ \{ {\widetilde \xi _ {k} ( i, \Delta ; j) } : { k = . . . , - 1, 0, 1 , . . . } \} $$

and the components $ \widetilde \xi _ {k} ( i, \Delta ; j) $ take values in $ X ( i, \Delta ) $. Let segments of messages

$$ \{ {\xi ^ {L} ( i, \Delta ) = ( \xi _ {1} ( i, \Delta ) \dots \xi _ {L} ( i, \Delta )) } : { i = 1 \dots s; \Delta \in D } \} $$

of length $ L $ be transmitted using a segment of length $ N $ of a memoryless multi-user channel using the following block methods of (en)coding and decoding. The (en)coding is determined by a set of $ s $( en)coding mappings $ f _ {i} $ such that

$$ f _ {i} : \ \prod _ {\Delta \in D } X ( i, \Delta ) \rightarrow Y _ {i} ^ {N} ,\ \ i = 1 \dots s, $$

( $ Y _ {i} ^ {N} $ being the direct product of $ N $ copies of $ Y _ {i} $), and the decoding by a set of decoding mappings:

$$ g _ {j; i, \Delta } : \ \widetilde{Y} {} _ {j} ^ {N} \rightarrow X ( i, \Delta ),\ \ j = 1 \dots r; i = 1 \dots s, $$

and $ \Delta $ is such that $ j \in \Delta $.

The set of (en)coding functions $ \{ f _ {i} \} $ establishes a functional dependence between the segments of length $ L $ of the messages of all possible sources and the segments of length $ N $ of the signals at the inputs of the channel. The set of decoding functions $ \{ g _ {j; i, \Delta } \} $ establishes a functional dependence between the segments of length $ N $ of the signals at the outputs of the channel and the segments of length $ L $ of the messages generated at each output. If the joint distribution of the segments of length $ L $ of the messages, $ \xi ^ {L} ( i, \Delta ) $, the (en)coding and decoding functions $ \{ f _ {i} \} $ and $ \{ g _ {j; i, \Delta } \} $, and the transition probabilities of the memoryless multi-user channel are known, then one can calculate the error probability $ p _ {e} $, defined by the formula $ p _ {e} = {\mathsf P} \{ \xi ^ {L} ( i, \Delta ) \neq \widetilde \xi {} ^ {L} ( i, \Delta ; j) \textrm{ for some } i = 1 \dots s; j = 1 \dots r, \textrm{ and } \Delta \textrm{ such that } j \in \Delta \} $.

A set $ \mathfrak R $ of sets (vectors) of rates $ R = \{ {R ( i, \Delta ) } : {i = 1 \dots s; \Delta \in D } \} $ in the $ s ( 2 ^ {r} - 1) $- dimensional Euclidean space is called the capacity region of the channel considered here if for any $ \epsilon > 0 $ there exist an integer $ N $, (en)codings $ \{ f _ {i} \} $ and decodings $ \{ g _ {j; i, \Delta } \} $ such that

$$ { \frac{L \mathop{\rm log} M ( i, \Delta ) }{N} } \geq \ R ( i, \Delta ) - \epsilon ,\ \ p _ {e} \leq \epsilon . $$

The problem of describing the region $ \mathfrak R $ is one of the main problems in the theory of multi-user channels. In the general case this problem is unsolved. A final solution of it has been obtained only in certain special cases, for example, for multiple-access channels (that is, a multi-user channel with $ r = 1 $) and for a certain class of broadcast channels (that is, channels with $ s = 1 $).

References

[1] C. Shannon, "Papers on information theory and cybernetics" , Moscow (1963) (In Russian; translated from English)
[2] E.C. van der Meulen, "Advances in multi-user communication channels" , Proc. 1975 IEEE-USSR Joint Workshop Inform. Theory (Moscow, 15–19 Dec. 1975) , IEEE (1976) pp. 227–247
[3] T.M. Cover, "Broadcast channels" IEEE Trans. Inform. Theory , 18 : 1 (1972) pp. 2–14
[4] D. Slepian, J.K. Wolf, "A coding theorem for multiple access channels with correlated sources" Bell System Techn. J. , 52 : 7 (1973) pp. 1037–1076
[5] I. Csiszar, J. Körner, "Information theory. Coding theorems for discrete memoryless systems" , Akad. Kiado (1981)
How to Cite This Entry:
Channel with multiple directions. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Channel_with_multiple_directions&oldid=13345
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