Произвольно изменяющийся канал - Arbitrarily varying channel - Wikipedia

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

Емкости и связанные доказательства

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

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

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

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

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

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

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

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

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

${\displaystyle \textstyle \equiv (}$поскольку ${\displaystyle \textstyle X_{r}}$ и ${\displaystyle \textstyle Y_{r}}$ находятся независимый случайные переменные, ${\displaystyle \textstyle W(y|x,s)=W'(y|s)}$ для некоторых ${\displaystyle \textstyle W')}$

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

${\displaystyle \textstyle \equiv (}$потому что только ${\displaystyle \textstyle P(x)}$ зависит от ${\displaystyle \textstyle x}$ сейчас же${\displaystyle \textstyle )}$

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

${\displaystyle \textstyle \equiv (}$потому что ${\displaystyle \displaystyle \sum _{x\in X}P(x)=1)}$

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

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

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

Пропускная способность AVC с ограничениями ввода и состояния

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

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

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

- ограничение ввода ${\displaystyle \textstyle \Gamma }$ на основе уравнения ${\displaystyle \displaystyle g(x)={\frac {1}{n}}\sum _{i=1}^{n}g(x_{i})}$, куда ${\displaystyle \textstyle x\in X}$ и ${\displaystyle \textstyle x=(x_{1},\dots ,x_{n})}$.

- Государственное ограничение ${\displaystyle \textstyle \Lambda }$, на основе уравнения ${\displaystyle \displaystyle l(s)={\frac {1}{n}}\sum _{i=1}^{n}l(s_{i})}$, куда ${\displaystyle \textstyle s\in X}$ и ${\displaystyle \textstyle s=(s_{1},\dots ,s_{n})}$.

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

- ${\displaystyle \textstyle I(P,\Lambda )}$ очень похож на ${\displaystyle \textstyle I(P)}$ уравнение, упомянутое ранее, ${\displaystyle \displaystyle I(P,\Lambda )=\min _{Y_{r}}I(X_{r}\land Y_{r})}$, но теперь любое состояние ${\displaystyle \textstyle s}$ или же ${\displaystyle \textstyle S_{r}}$ в уравнении должны следовать ${\displaystyle \textstyle l(s)\leq \Lambda }$ государственное ограничение.

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

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

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

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

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

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

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

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

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

Теорема 3: В емкость за рандомизированный коды АВК ${\displaystyle \displaystyle c=max_{P}I(P,\zeta )}$.

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

Смотрите также

• Бинарный симметричный канал
• Канал двоичного стирания
• Z-канал (теория информации)
• Модель канала
• Теория информации
• Теория кодирования

Рекомендации

• Альсведе, Рудольф и Блиновский, Владимир, "Классическая пропускная способность классически-квантовых каналов с произвольным изменением", http://ieeexplore.ieee.org.gate.lib.buffalo.edu/stamp/stamp.jsp?tp=&arnumber=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