Communication channel with unknown parameters that can change over time
( Произвольно изменяющийся канал AVC ) — это модель канала связи, используемая в теории кодирования , впервые представленная Блэквеллом, Брейманом и Томасианом. Этот конкретный канал имеет неизвестные параметры, которые могут меняться со временем, и эти изменения могут не иметь единообразного характера во время передачи кодового слова .
использование этого канала можно описать с помощью стохастической матрицы
, где
входной алфавит,
выходной алфавит, и
это вероятность для данного набора состояний
, что передаваемый вход
приводит к полученному результату
. Штат
в комплекте
может изменяться произвольно в каждую единицу времени
. Этот канал был разработан как альтернатива Шеннона двоичному симметричному каналу вся природа канала , (BSC), где известна в сетевых каналах чтобы быть более реалистичным для реальных ситуаций .
Емкость детерминированных AVC [ править ]
AVC Емкость может варьироваться в зависимости от определенных параметров.
— достижимая скорость для детерминированного кода AVC , если она больше, чем
, и если для каждого положительного
и
и очень большой
, длина-
существуют блочные коды , которые удовлетворяют следующим уравнениям:
и
, где
является наивысшим значением в
и где
средняя вероятность ошибки для последовательности состояний
. Самая большая ставка
представляет собой емкость AVC, обозначаемую
.
Как видите, единственные полезные ситуации — это когда емкость АВК превышает
, потому что тогда канал сможет передать гарантированный объем данных
без ошибок. Итак, мы начнем с теоремы , которая показывает, когда
положителен в AVC, и обсуждаемые ниже теоремы сузят диапазон
для разных обстоятельств.
Прежде чем сформулировать теорему 1, необходимо обратиться к нескольким определениям:
- AVC симметричен , если
для каждого
, где
,
, и
это функция канала
.
,
, и
все случайные величины входят в наборы
,
, и
соответственно.
равна вероятности того, что случайная величина
равно
.
равна вероятности того, что случайная величина
равно
.
- это комбинированная функция массы вероятности (pmf)
,
, и
.
формально определяется как
.
это энтропия
.
равна средней вероятности того, что
будет определенное значение, основанное на всех значениях
возможно, может быть равно.
это информация взаимная
и
, и равен
.
, где минимум приходится на все случайные величины
такой, что
,
, и
распределяются в виде
.
Теорема 1:
тогда и только тогда, когда AVC не симметричен. Если
, затем
.
Доказательство первой части симметрии: если мы сможем доказать, что
положителен, когда AVC несимметричен, а затем докажите, что
, мы сможем доказать теорему 1. Предположим,
были равны
. Из определения
, это сделало бы
и
независимые случайные величины , для некоторых
, потому что это означало бы, что ни одной случайной величины не энтропия будет зависеть от значения другой случайной величины . Используя уравнение
, (и вспоминая
,) мы можем получить,
![{\displaystyle \displaystyle P_{Y_{r}}(y)=\sum _{x\in X}\sum _{s\in S}P(x)P_{S_{r}}(s)W( y|x,s)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/24fd9bbbdeaa91d6b7dcb4f27eb0597df3ea7ff9)
с
и
являются независимыми случайными величинами ,
для некоторых ![{\displaystyle \textstyle W')}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b17e320a239b97de680873d1e1f5f22cec38fb82)
![{\displaystyle \displaystyle P_{Y_{r}}(y)=\sum _{x\in X}\sum _{s\in S}P(x)P_{S_{r}}(s)W' (д|с)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c0f4d660b58b519f62dbcb628d1d372abca0faab)
потому что только
зависит от
сейчас ![{\displaystyle \textstyle)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4fdd7324087e1751020dedaa17300dd66ae82796)
![{\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]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d75d8cdf6d0c80cbdaa1d124d09471bc017c2da7)
потому что ![{\displaystyle \displaystyle \sum _ {x\in X} P (x) = 1)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3a43ab3e3025c5c4c00e50b02d59627bedc01e82)
![{\displaystyle \displaystyle P_{Y_{r}}(y)=\sum _{s\in S}P_{S_{r}}(s)W'(y|s)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/069a5dfdf80c61d6b200622492943cb3417c8ebd)
Итак, теперь у нас есть распределение вероятностей на
это независимо от
. Итак, теперь определение симметричного AVC можно переписать следующим образом:
с
и
обе функции основаны на
, они были заменены функциями, основанными на
и
только. Как видите, обе стороны теперь равны
мы рассчитали ранее, поэтому AVC действительно симметричен, когда
равно
. Поэтому,
может быть положительным только в том случае, если AVC не симметричен.
Доказательство второй части пропускной способности : полное доказательство см. в статье «Еще раз о пропускной способности произвольно изменяющегося канала: положительность, ограничения», ссылка на которую приведена ниже.
AVC с ограничениями ввода состояния Емкость и
Следующая теорема будет иметь дело с пропускной способностью AVC с ограничениями на вход и/или состояние. Эти ограничения помогают уменьшить очень широкий диапазон возможностей передачи и ошибок в AVC, что позволяет немного легче увидеть, как ведет себя AVC.
Прежде чем мы перейдем к теореме 2, нам необходимо определить несколько определений и лемм :
Для таких АВК существуют:
- - Входное ограничение
на основе уравнения
, где
и
.
- - Государственное ограничение
, на основе уравнения
, где
и
.
- -
![{\displaystyle \displaystyle \Lambda _{0}(P)=\min \sum _{x\in X,s\in S}P(x)l(s)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/acf2ecdfe7ac9bbed36bd939cb08babb6ad5d1bf)
- -
очень похоже на
уравнение, упомянутое ранее,
, но теперь любое состояние
или
в уравнении должно следовать
государственное ограничение.
Предполагать
— заданная функция с неотрицательным знаком на
и
— заданная функция с неотрицательным знаком на
и что минимальные значения для обоих равны
. В литературе, которую я читал по этому вопросу, точные определения обоих
и
(для одной переменной
,) никогда формально не описывается. Полезность входного ограничения
и государственное ограничение
будет основано на этих уравнениях.
Для AVC с ограничениями на вход и/или состояние скорость
теперь ограничено кодовыми словами формата
которые удовлетворяют
, а теперь состояние
ограничено всеми состояниями, которые удовлетворяют
. Наибольшая скорость по-прежнему считается пропускной способностью AVC и теперь обозначается как
.
Лемма 1: Любые коды , в которых
больше, чем
не могут считаться «хорошими» кодами , поскольку такие типы кодов имеют максимальную среднюю вероятность ошибки, большую или равную
, где
это максимальное значение
. Это не очень хорошая максимальная средняя вероятность ошибки, поскольку она довольно велика.
близко к
, а другая часть уравнения будет очень маленькой, поскольку
значение возведено в квадрат, и
установлено больше, чем
. маловероятно Поэтому получение кодового слова без ошибки . Вот почему
условие присутствует в теореме 2.
Теорема 2. При положительном
и сколь угодно малый
,
,
, для любой длины блока
и для любого типа
с условиями
и
, и где
, существует код с кодовыми словами
, каждый типа
, которые удовлетворяют следующим уравнениям:
,
, и где положительный
и
зависеть только от
,
,
, и данный AVC.
Доказательство теоремы 2 : см. статью «Возврат к пропускной способности произвольно меняющегося канала: положительность, ограничения», на которую приведена ссылка ниже для полного доказательства.
Емкость рандомизированных AVC [ править ]
Следующая теорема будет для AVC со рандомизированным кодом . Для таких AVC код представляет собой случайную величину со значениями из семейства блочных кодов длины n , и этим кодам не разрешается зависеть/полагаться на фактическое значение кодового слова . Эти коды имеют одинаковое максимальное и среднее значение вероятности ошибки для любого канала из-за его случайной природы. Эти типы кодов также помогают сделать некоторые свойства AVC более понятными.
Прежде чем мы перейдем к теореме 3, нам нужно сначала определить пару важных терминов:
![{\displaystyle \displaystyle W_{\zeta }(y|x)=\sum _{s\in S}W(y|x,s)P_{S_{r}}(s)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4025fce8ef4192b41659247cba2953ad33103a96)
очень похож на
уравнение, упомянутое ранее,
, но теперь ПМФ
добавляется к уравнению, делая минимум
основал новую форму
, где
заменяет
.
Теорема 3. способность Пропускная рандомизированных равна кодов AVC
.
Доказательство теоремы 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 .