Произвольно меняющийся канал

Произвольно изменяющийся канал ( AVC ) — это модель канала связи , используемая в теории кодирования , впервые представленная Блэквеллом, Брейманом и Томасианом. Этот конкретный канал имеет неизвестные параметры, которые могут меняться со временем, и эти изменения могут не иметь единообразного характера во время передачи кодового слова . $\textstyle n$ использование этого канала можно описать с помощью стохастической матрицы $\textstyle W^{n}:X^{n}\times$ $\textstyle S^{n}\rightarrow Y^{n}$ , где $\textstyle X$ входной алфавит, $\textstyle Y$ выходной алфавит, и $\textstyle W^{n}(y|x,s)$ это вероятность для данного набора состояний $\textstyle S$ , что передаваемый вход $\textstyle x=(x_{1},\ldots ,x_{n})$ приводит к полученному результату $\textstyle y=(y_{1},\ldots ,y_{n})$ . Государство $\textstyle s_{i}$ в комплекте $\textstyle S$ может изменяться произвольно в каждую единицу времени $\textstyle i$ . Этот канал был разработан как альтернатива Шеннона двоичному симметричному каналу вся природа канала , (BSC), где известна чтобы быть более реалистичным для реальных ситуаций в сетевых каналах .

и соответствующие доказательства Мощности

Емкость детерминированных AVC [ править ]

AVC Емкость может варьироваться в зависимости от определенных параметров.

$\textstyle R$ — достижимая скорость для детерминированного кода AVC , если она больше, чем $\textstyle 0$ , и если для каждого положительного $\textstyle \varepsilon$ и $\textstyle \delta$ и очень большой $\textstyle n$ , длина- $\textstyle n$ существуют блочные коды , которые удовлетворяют следующим уравнениям: $\textstyle {\frac {1}{n}}\log N>R-\delta$ и $\displaystyle \max _{s\in S^{n}}{\bar {e}}(s)\leq \varepsilon$ , где $\textstyle N$ является наивысшим значением в $\textstyle Y$ и где $\textstyle {\bar {e}}(s)$ средняя вероятность ошибки для последовательности состояний $\textstyle s$ . Самая большая ставка $\textstyle R$ представляет собой емкость AVC, обозначаемую $\textstyle c$ .

Как видите, единственные полезные ситуации — это когда емкость АВК превышает $\textstyle 0$ , потому что тогда канал сможет передать гарантированный объем данных $\textstyle \leq c$ без ошибок. Итак, мы начнем с теоремы , которая показывает, когда $\textstyle c$ положителен в AVC, и обсуждаемые ниже теоремы сузят диапазон $\textstyle c$ для разных обстоятельств.

Прежде чем сформулировать теорему 1, необходимо обратиться к нескольким определениям:

AVC симметричен , если $\displaystyle \sum _{s\in S}W(y|x,s)U(s|x')=\sum _{s\in S}W(y|x',s)U(s|x)$ для каждого $\textstyle (x,x',y,s)$ , где $\textstyle x,x'\in X$ , $\textstyle y\in Y$ , и $\textstyle U(s|x)$ это функция канала $\textstyle U:X\rightarrow S$ .
$\textstyle X_{r}$ , $\textstyle S_{r}$ , и $\textstyle Y_{r}$ это все случайные величины в наборах $\textstyle X$ , $\textstyle S$ , и $\textstyle Y$ соответственно.
$\textstyle P_{X_{r}}(x)$ равна вероятности того, что случайная величина $\textstyle X_{r}$ равно $\textstyle x$ .
$\textstyle P_{S_{r}}(s)$ равна вероятности того, что случайная величина $\textstyle S_{r}$ равно $\textstyle s$ .
$\textstyle P_{X_{r}S_{r}Y_{r}}$ - это комбинированная функция массы вероятности (pmf) $\textstyle P_{X_{r}}(x)$ , $\textstyle P_{S_{r}}(s)$ , и $\textstyle W(y|x,s)$ . $\textstyle P_{X_{r}S_{r}Y_{r}}$ формально определяется как $\textstyle P_{X_{r}S_{r}Y_{r}}(x,s,y)=P_{X_{r}}(x)P_{S_{r}}(s)W(y|x,s)$ .
$\textstyle H(X_{r})$ это энтропия $\textstyle X_{r}$ .
$\textstyle H(X_{r}|Y_{r})$ равна средней вероятности того, что $\textstyle X_{r}$ будет определенное значение, основанное на всех значениях $\textstyle Y_{r}$ возможно, может быть равно.
$\textstyle I(X_{r}\land Y_{r})$ это информация взаимная $\textstyle X_{r}$ и $\textstyle Y_{r}$ , и равен $\textstyle H(X_{r})-H(X_{r}|Y_{r})$ .
$\displaystyle I(P)=\min _{Y_{r}}I(X_{r}\land Y_{r})$ , где минимум приходится на все случайные величины $\textstyle Y_{r}$ такой, что $\textstyle X_{r}$ , $\textstyle S_{r}$ , и $\textstyle Y_{r}$ распределяются в виде $\textstyle P_{X_{r}S_{r}Y_{r}}$ .

Теорема 1: $\textstyle c>0$ тогда и только тогда, когда AVC не симметричен. Если $\textstyle c>0$ , затем $\displaystyle c=\max _{P}I(P)$ .

Доказательство первой части симметрии: если мы сможем доказать, что $\textstyle I(P)$ положителен, когда AVC несимметричен, а затем докажите, что $\textstyle c=\max _{P}I(P)$ , мы сможем доказать теорему 1. Предположим, $\textstyle I(P)$ были равны $\textstyle 0$ . Из определения $\textstyle I(P)$ , это сделало бы $\textstyle X_{r}$ и $\textstyle Y_{r}$ независимые случайные величины , для некоторых $\textstyle S_{r}$ , потому что это означало бы, что ни одной случайной величины не энтропия будет зависеть от значения другой случайной величины . Используя уравнение $\textstyle P_{X_{r}S_{r}Y_{r}}$ , (и вспоминая $\textstyle P_{X_{r}}=P$ ,) мы можем получить,

\displaystyle P_{Y_{r}}(y)=\sum _{x\in X}\sum _{s\in S}P(x)P_{S_{r}}(s)W(y|x,s)

\textstyle \equiv (

с

\textstyle X_{r}

и

\textstyle Y_{r}

являются независимыми случайными величинами ,

\textstyle W(y|x,s)=W'(y|s)

для некоторых

\textstyle W')

\displaystyle P_{Y_{r}}(y)=\sum _{x\in X}\sum _{s\in S}P(x)P_{S_{r}}(s)W'(y|s)

\textstyle \equiv (

потому что только

\textstyle P(x)

зависит от

\textstyle x

сейчас

\textstyle )

\displaystyle P_{Y_{r}}(y)=\sum _{s\in S}P_{S_{r}}(s)W'(y|s)\left[\sum _{x\in X}P(x)\right]

\textstyle \equiv (

потому что

\displaystyle \sum _{x\in X}P(x)=1)

\displaystyle P_{Y_{r}}(y)=\sum _{s\in S}P_{S_{r}}(s)W'(y|s)

Итак, теперь у нас есть распределение вероятностей на $\textstyle Y_{r}$ это независимо от $\textstyle X_{r}$ . Итак, теперь определение симметричного AVC можно переписать следующим образом: $\displaystyle \sum _{s\in S}W'(y|s)P_{S_{r}}(s)=\sum _{s\in S}W'(y|s)P_{S_{r}}(s)$ с $\textstyle U(s|x)$ и $\textstyle W(y|x,s)$ обе функции основаны на $\textstyle x$ , они были заменены функциями, основанными на $\textstyle s$ и $\textstyle y$ только. Как видите, обе стороны теперь равны $\textstyle P_{Y_{r}}(y)$ мы рассчитали ранее, поэтому AVC действительно симметричен, когда $\textstyle I(P)$ равно $\textstyle 0$ . Поэтому, $\textstyle I(P)$ может быть положительным только в том случае, если AVC не симметричен.

Доказательство второй части пропускной способности : полное доказательство см. в статье «Еще раз о пропускной способности произвольно меняющегося канала: положительность, ограничения», ссылка на которую приведена ниже.

AVC с ограничениями ввода и состояния Емкость

Следующая теорема будет иметь дело с пропускной способностью AVC с ограничениями на вход и/или состояние. Эти ограничения помогают уменьшить очень широкий диапазон возможностей передачи и ошибок в AVC, что позволяет немного легче увидеть, как ведет себя AVC.

Прежде чем мы перейдем к теореме 2, нам необходимо определить несколько определений и лемм :

Для таких АВК существуют:

- Входное ограничение

\textstyle \Gamma

на основе уравнения

\displaystyle g(x)={\frac {1}{n}}\sum _{i=1}^{n}g(x_{i})

, где

\textstyle x\in X

и

\textstyle x=(x_{1},\dots ,x_{n})

.

- Государственное ограничение

\textstyle \Lambda

, на основе уравнения

\displaystyle l(s)={\frac {1}{n}}\sum _{i=1}^{n}l(s_{i})

, где

\textstyle s\in X

и

\textstyle s=(s_{1},\dots ,s_{n})

.

-

\displaystyle \Lambda _{0}(P)=\min \sum _{x\in X,s\in S}P(x)l(s)

-

\textstyle I(P,\Lambda )

очень похоже на

\textstyle I(P)

уравнение, упомянутое ранее,

\displaystyle I(P,\Lambda )=\min _{Y_{r}}I(X_{r}\land Y_{r})

, но теперь любое состояние

\textstyle s

или

\textstyle S_{r}

в уравнении должно следовать

\textstyle l(s)\leq \Lambda

государственное ограничение.

Предполагать $\textstyle g(x)$ — заданная функция с неотрицательным знаком на $\textstyle X$ и $\textstyle l(s)$ — заданная функция с неотрицательным знаком на $\textstyle S$ и что минимальные значения для обоих равны $\textstyle 0$ . В литературе, которую я читал по этому вопросу, точные определения обоих $\textstyle g(x)$ и $\textstyle l(s)$ (для одной переменной $\textstyle x_{i}$ ,) никогда формально не описывается. Полезность входного ограничения $\textstyle \Gamma$ и государственное ограничение $\textstyle \Lambda$ будет основано на этих уравнениях.

Для AVC с ограничениями на вход и/или состояние скорость $\textstyle R$ теперь ограничено кодовыми словами формата $\textstyle x_{1},\dots ,x_{N}$ которые удовлетворяют $\textstyle g(x_{i})\leq \Gamma$ , а теперь состояние $\textstyle s$ ограничено всеми состояниями, которые удовлетворяют $\textstyle l(s)\leq \Lambda$ . Наибольшая скорость по-прежнему считается пропускной способностью AVC и теперь обозначается как $\textstyle c(\Gamma ,\Lambda )$ .

Лемма 1: Любые коды , в которых $\textstyle \Lambda$ больше, чем $\textstyle \Lambda _{0}(P)$ не могут считаться «хорошими» кодами , поскольку такие типы кодов имеют максимальную среднюю вероятность ошибки, большую или равную $\textstyle {\frac {N-1}{2N}}-{\frac {1}{n}}{\frac {l_{max}^{2}}{n(\Lambda -\Lambda _{0}(P))^{2}}}$ , где $\textstyle l_{max}$ это максимальное значение $\textstyle l(s)$ . Это не очень хорошая максимальная средняя вероятность ошибки, поскольку она довольно велика. $\textstyle {\frac {N-1}{2N}}$ близко к $\textstyle {\frac {1}{2}}$ , а другая часть уравнения будет очень маленькой, поскольку $\textstyle (\Lambda -\Lambda _{0}(P))$ значение возведено в квадрат, и $\textstyle \Lambda$ установлено больше, чем $\textstyle \Lambda _{0}(P)$ . весьма маловероятно Поэтому получение кодового слова без ошибки . Вот почему $\textstyle \Lambda _{0}(P)$ условие присутствует в теореме 2.

Теорема 2. При положительном $\textstyle \Lambda$ и сколь угодно малый $\textstyle \alpha >0$ , $\textstyle \beta >0$ , $\textstyle \delta >0$ , для любой длины блока $\textstyle n\geq n_{0}$ и для любого типа $\textstyle P$ с условиями $\textstyle \Lambda _{0}(P)\geq \Lambda +\alpha$ и $\displaystyle \min _{x\in X}P(x)\geq \beta$ , и где $\textstyle P_{X_{r}}=P$ , существует код с кодовыми словами $\textstyle x_{1},\dots ,x_{N}$ , каждый типа $\textstyle P$ , которые удовлетворяют следующим уравнениям: $\textstyle {\frac {1}{n}}\log N>I(P,\Lambda )-\delta$ , $\displaystyle \max _{l(s)\leq \Lambda }{\bar {e}}(s)\leq \exp(-n\gamma )$ , и где положительный $\textstyle n_{0}$ и $\textstyle \gamma$ зависеть только от $\textstyle \alpha$ , $\textstyle \beta$ , $\textstyle \delta$ , и данный AVC.

Доказательство теоремы 2 : см. статью «Возврат к пропускной способности произвольно меняющегося канала: положительность, ограничения», на которую приведена ссылка ниже для полного доказательства.

Емкость рандомизированных AVC [ править ]

Следующая теорема будет для AVC со рандомизированным кодом . Для таких AVC код представляет собой случайную величину со значениями из семейства блочных кодов длины n , и этим кодам не разрешается зависеть/полагаться на фактическое значение кодового слова . Эти коды имеют одинаковое максимальное и среднее значение вероятности ошибки для любого канала из-за его случайной природы. Эти типы кодов также помогают сделать некоторые свойства AVC более понятными.

Прежде чем мы перейдем к теореме 3, нам нужно сначала определить пару важных терминов:

$\displaystyle W_{\zeta }(y|x)=\sum _{s\in S}W(y|x,s)P_{S_{r}}(s)$
$\textstyle I(P,\zeta )$ очень похож на $\textstyle I(P)$ уравнение, упомянутое ранее, $\displaystyle I(P,\zeta )=\min _{Y_{r}}I(X_{r}\land Y_{r})$ , но теперь ПМФ $\textstyle P_{S_{r}}(s)$ добавляется к уравнению, делая минимум $\textstyle I(P,\zeta )$ основал новую форму $\textstyle P_{X_{r}S_{r}Y_{r}}$ , где $\textstyle W_{\zeta }(y|x)$ заменяет $\textstyle W(y|x,s)$ .

Теорема 3. способность Пропускная рандомизированных равна кодов AVC $\displaystyle c=max_{P}I(P,\zeta )$ .

Доказательство теоремы 3 : полное доказательство см. в статье «Пропускные способности некоторых классов каналов при случайном кодировании», указанной ниже.

См. также [ править ]

Ссылки [ править ]

Альсведе, Рудольф и Блиновский, Владимир, «Классическая пропускная способность классически-квантовых произвольно изменяющихся каналов», https://ieeexplore.ieee.org/document/4069128
Блэквелл, Дэвид, Брейман, Лео и Томасиан, А.Дж., «Пропускные способности некоторых классов каналов при случайном кодировании», https://www.jstor.org/stable/2237566
Чисар И. и Нараян П., «Произвольно изменяющиеся каналы с ограниченными входными данными и состояниями», http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=2598&isnumber=154.
Чисар И. и Нараян П., «Пропускная способность и правила декодирования для классов произвольно изменяющихся каналов», http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=32153&isnumber=139 .
Чисар И. и Нараян П., «Ещё раз о пропускной способности произвольно меняющегося канала: позитивность, ограничения», http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=2627&isnumber=155 .
Лапидот А. и Нараян П. «Надежная связь в условиях неопределенности канала», http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=720535&isnumber=15554.