Теорема кодирования с шумом

Теория информации
Энтропия Дифференциальная энтропия Условная энтропия Совместная энтропия Взаимная информация Условная взаимная информация Относительная энтропия Скорость энтропии Предельная плотность дискретных точек
Асимптотическое свойство равнораспределения Теория скорости – искажения
Теорема Шеннона о кодировании источника Емкость канала Теорема кодирования с шумом Теорема Шеннона – Хартли.
v т е

В теории информации , то шумная-канальное кодирование теоремы (иногда теорема Шеннона или предел Шеннона ), устанавливаю , что для любой заданной степени шумового загрязнения канала связи , можно общаться дискретные данными (цифровая информация ) почти безошибочные до вычислимая максимальная скорость в канале. Этот результат был представлен Клодом Шенноном в 1948 году и частично основан на более ранних работах и ​​идеях Гарри Найквиста и Ральфа Хартли .

Предел Шеннона или емкость Шеннона каналу связи относится к максимальной скорости данных без ошибок , которые теоретически могут быть переданы по каналу , если ссылка подвержена ошибкам случайной передачи данных, для конкретного уровня шума. Впервые он был описан Шенноном (1948) и вскоре после этого опубликован в книге Клода Элвуда Шеннона и Уоррена Уивера в 1949 году под названием «Математическая теория коммуникации» . ( ISBN  0252725484 ). Это положило начало современной теории информации .

Обзор [ править ]

Заявлено от Клода Шеннона в 1948 году теорема описывает максимально возможную эффективность коррекции ошибок методов в сравнении с уровнем шумовых помех и искажения данных. Теорема Шеннона находит широкое применение как в связи, так и в хранении данных . Эта теорема имеет фундаментальное значение для современной теории информации . Шеннон только набросал доказательство. Первое строгое доказательство для дискретного случая принадлежит Амиэлю Файнштейну ^[1] в 1954 году.

Теорема Шеннона утверждает, что при наличии зашумленного канала с пропускной способностью C и информацией, передаваемой со скоростью R , тогда, если существуют коды, которые позволяют сделать вероятность ошибки в приемнике сколь угодно малой. Это означает , что, теоретически, можно передают информацию практически без ошибок в любом случае ниже предельной скорости, C .${\ Displaystyle R <C}$

Обратное тоже важно. Если , сколь угодно малая вероятность ошибки недостижима. Все коды будут иметь вероятность ошибки больше определенного положительного минимального уровня, и этот уровень увеличивается с увеличением скорости. Таким образом, нельзя гарантировать надежную передачу информации по каналу на скоростях, превышающих пропускную способность канала. Теорема не рассматривает редкую ситуацию, в которой скорость и мощность равны.${\ displaystyle R> C}$

Пропускная способность канала может быть рассчитана на основе физических свойств канала; для канала с ограниченной полосой пропускания с гауссовским шумом, используя теорему Шеннона – Хартли .${\ displaystyle C}$

Простые схемы, такие как «отправить сообщение 3 раза и использовать лучшую схему голосования 2 из 3, если копии отличаются», являются неэффективными методами исправления ошибок, неспособными асимптотически гарантировать, что блок данных может быть передан без ошибок. Усовершенствованные методы, такие как коды Рида – Соломона и, в последнее время, коды и турбокоды с низкой плотностью проверки четности (LDPC) , намного ближе подходят к достижению теоретического предела Шеннона, но за счет высокой вычислительной сложности. Используя эти высокоэффективные коды и вычислительную мощность современных цифровых сигнальных процессоров , теперь можно достичь очень близкого к пределу Шеннона. Фактически было показано, что коды LDPC могут достигать 0,0045 дБ предела Шеннона (для двоичныхКаналы аддитивного белого гауссовского шума (AWGN) с очень большой длиной блока). ^[2]

Математическое утверждение [ править ]

Базовая математическая модель системы связи следующая:

${\displaystyle {\xrightarrow[{\text{Message}}]{W}}{\begin{array}{|c| }\hline {\text{Encoder}}\\f_{n}\\\hline \end{array}}{\xrightarrow[{\mathrm {Encoded \atop sequence} }]{X^{n}}}{\begin{array}{|c| }\hline {\text{Channel}}\\p(y|x)\\\hline \end{array}}{\xrightarrow[{\mathrm {Received \atop sequence} }]{Y^{n}}}{\begin{array}{|c| }\hline {\text{Decoder}}\\g_{n}\\\hline \end{array}}{\xrightarrow[{\mathrm {Estimated \atop message} }]{\hat {W}}}}$

Сообщение Вт передается через канал с шумом с использованием функции кодирования и декодирования. Кодер отображает W в заранее определенной последовательности канальных символов длины п . В своей базовой модели канал искажает каждый из этих символов независимо от других. Выходной сигнал канала - полученная последовательность - подается в декодер, который преобразует последовательность в оценку сообщения. В этом случае вероятность ошибки определяется как:

${\displaystyle P_{e}={\text{Pr}}\left\{{\hat {W}}\neq W\right\}.}$

Теорема (Шеннон, 1948):

1. Для каждого дискретного канала без памяти пропускная способность канала определяется в терминах взаимной информации ,${\displaystyle I(X;Y)}$

${\displaystyle \ C=\sup _{p_{X}}I(X;Y)}$^[3]

обладает следующим свойством. Для любого и , для достаточно большого , существует код длины и скорости и алгоритм декодирования, такой, что максимальная вероятность блочной ошибки равна .${\displaystyle \epsilon >0}$${\displaystyle R<C}$${\displaystyle N}$${\displaystyle N}$${\displaystyle \geq R}$${\displaystyle \leq \epsilon }$

2. Если вероятность битовой ошибки приемлема, достижимы скорости до , где${\displaystyle p_{b}}$${\displaystyle R(p_{b})}$

${\displaystyle R(p_{b})={\frac {C}{1-H_{2}(p_{b})}}.}$

и - бинарная функция энтропии${\displaystyle H_{2}(p_{b})}$

${\displaystyle H_{2}(p_{b})=-\left[p_{b}\log _{2}{p_{b}}+(1-p_{b})\log _{2}({1-p_{b}})\right]}$

3. В любом случае ставки выше недостижимы.${\displaystyle p_{b}}$${\displaystyle R(p_{b})}$

(Маккей (2003), стр. 162; см. Галлагер (1968), гл. 5; Обложка и Томас (1991), стр. 198; Шеннон (1948), тм. 11)

Схема доказательства [ править ]

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

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

Достижимость для дискретных каналов без памяти [ править ]

Это конкретное доказательство достижимости следует стилю доказательств, использующих свойство асимптотической равнораспределенности (AEP). Другой стиль можно найти в текстах по теории информации, использующих показатели ошибок .

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

С помощью связанного с AEP аргумента, учитывая канал, строки длины исходных символов и строки длины выходных данных канала , мы можем определить совместно типичный набор следующим образом:${\displaystyle n}$${\displaystyle X_{1}^{n}}$${\displaystyle n}$${\displaystyle Y_{1}^{n}}$

${\displaystyle A_{\varepsilon }^{(n)}=\{(x^{n},y^{n})\in {\mathcal {X}}^{n}\times {\mathcal {Y}}^{n}}$

${\displaystyle 2^{-n(H(X)+\varepsilon )}\leq p(X_{1}^{n})\leq 2^{-n(H(X)-\varepsilon )}}$

${\displaystyle 2^{-n(H(Y)+\varepsilon )}\leq p(Y_{1}^{n})\leq 2^{-n(H(Y)-\varepsilon )}}$

${\displaystyle {2^{-n(H(X,Y)+\varepsilon )}}\leq p(X_{1}^{n},Y_{1}^{n})\leq 2^{-n(H(X,Y)-\varepsilon )}\}}$

Мы говорим, что две последовательности и являются совместно типичными, если они лежат в совместно типичном множестве, определенном выше.${\displaystyle {X_{1}^{n}}}$${\displaystyle Y_{1}^{n}}$

Шаги

1. В стиле аргумента случайного кодирования мы случайным образом генерируем кодовые слова длины n из распределения вероятностей Q.${\displaystyle 2^{nR}}$
2. Этот код раскрывается отправителю и получателю. Также предполагается, что известна матрица перехода для используемого канала.${\displaystyle p(y|x)}$
3. Сообщение W выбирается в соответствии с равномерным распределением по набору кодовых слов. То есть .${\displaystyle Pr(W=w)=2^{-nR},w=1,2,\dots ,2^{nR}}$
4. Сообщение W отправляется по каналу.
5. Приемник получает последовательность согласно ${\displaystyle P(y^{n}|x^{n}(w))=\prod _{i=1}^{n}p(y_{i}|x_{i}(w))}$
6. Отправляя эти кодовые слова по каналу, мы получаем и декодируем в некоторую исходную последовательность, если существует ровно 1 кодовое слово, которое совместно типично с Y. Если нет совместно типичных кодовых слов или если их более одного, объявляется ошибка. Ошибка также возникает, если декодированное кодовое слово не соответствует исходному кодовому слову. Это называется декодированием типичного набора .${\displaystyle Y_{1}^{n}}$

Вероятность ошибки этой схемы делится на две части:

1. Во-первых, ошибка может возникнуть, если для принятой последовательности Y не найдены совместно типичные X-последовательности.
2. Во-вторых, ошибка может возникнуть, если неправильная последовательность X является типичной совместно с принятой последовательностью Y.

• По случайности построения кода можно предположить, что средняя вероятность ошибки, усредненная по всем кодам, не зависит от отправленного индекса. Таким образом, без ограничения общности можно считать W = 1.
• Из совместного AEP мы знаем, что вероятность того, что не существует совместно типичного X, стремится к 0 при увеличении n. Мы можем ограничить эту вероятность ошибки величиной .${\displaystyle \varepsilon }$
• Также из совместного AEP мы знаем, что вероятность того, что конкретное и результат W = 1 являются типичными вместе, равна .${\displaystyle X_{1}^{n}(i)}$${\displaystyle Y_{1}^{n}}$${\displaystyle \leq 2^{-n(I(X;Y)-3\varepsilon )}}$

Определять: ${\displaystyle E_{i}=\{(X_{1}^{n}(i),Y_{1}^{n})\in A_{\varepsilon }^{(n)}\},i=1,2,\dots ,2^{nR}}$

как случай, когда сообщение i является типичным вместе с последовательностью, полученной при отправке сообщения 1.

${\displaystyle {\begin{aligned}P({\text{error}})&{}=P({\text{error}}|W=1)\leq P(E_{1}^{c})+\sum _{i=2}^{2^{nR}}P(E_{i})\\&{}\leq P(E_{1}^{c})+(2^{nR}-1)2^{-n(I(X;Y)-3\varepsilon )}\\&{}\leq \varepsilon +2^{-n(I(X;Y)-R-3\varepsilon )}.\end{aligned}}}$

Мы можем наблюдать, что по мере приближения к бесконечности, если для канала вероятность ошибки упадет до 0.${\displaystyle n}$${\displaystyle R<I(X;Y)}$

Наконец, учитывая, что средняя кодовая книга показана как «хорошая», мы знаем, что существует кодовая книга, производительность которой лучше, чем в среднем, и, таким образом, удовлетворяет нашу потребность в сколь угодно низкой вероятности ошибки при обмене данными по зашумленному каналу.

Слабое преобразование для дискретных каналов без памяти [ править ]

Предположим, код кодовых слов. Пусть W равномерно проведен по этому множеству как индекс. Позвольте и быть переданными кодовыми словами и принятыми кодовыми словами, соответственно.${\displaystyle 2^{nR}}$${\displaystyle X^{n}}$${\displaystyle Y^{n}}$

1. ${\displaystyle nR=H(W)=H(W|Y^{n})+I(W;Y^{n})}$использование идентичностей, включающих энтропию и взаимную информацию
2. ${\displaystyle \leq H(W|Y^{n})+I(X^{n}(W);Y^{n})}$ поскольку X является функцией W
3. ${\displaystyle \leq 1+P_{e}^{(n)}nR+I(X^{n}(W);Y^{n})}$с помощью неравенства Фано
4. ${\displaystyle \leq 1+P_{e}^{(n)}nR+nC}$ за счет того, что емкость взаимной информации максимальна.

Результат этих шагов таков . Поскольку длина блока стремится к бесконечности, мы получаем, что он отделен от 0, если R больше, чем C - мы можем получить сколь угодно низкие коэффициенты ошибок, только если R меньше C.${\displaystyle P_{e}^{(n)}\geq 1-{\frac {1}{nR}}-{\frac {C}{R}}}$${\displaystyle n}$${\displaystyle P_{e}^{(n)}}$

Сильная конверсия для дискретных каналов без памяти [ править ]

Сильная обратная теорема, доказанная Вулфовицем в 1957 г. ^[4], утверждает, что,

${\displaystyle P_{e}\geq 1-{\frac {4A}{n(R-C)^{2}}}-e^{-{\frac {n(R-C)}{2}}}}$

для некоторой конечной положительной постоянной . В то время как слабое обратное утверждение утверждает, что вероятность ошибки ограничена от нуля при стремлении к бесконечности, сильное обратное утверждение утверждает, что ошибка достигает 1. Таким образом, это резкий порог между совершенно надежной и совершенно ненадежной связью.${\displaystyle A}$${\displaystyle n}$${\displaystyle C}$

Теорема кодирования каналов для нестационарных каналов без памяти [ править ]

Мы предполагаем, что канал не имеет памяти, но его вероятности перехода меняются со временем, как это известно как передатчику, так и приемнику.

Тогда пропускная способность канала определяется выражением

${\displaystyle C=\lim \inf \max _{p^{(X_{1})},p^{(X_{2})},...}{\frac {1}{n}}\sum _{i=1}^{n}I(X_{i};Y_{i}).}$

Максимум достигается при распределениях достижения пропускной способности для каждого соответствующего канала. То есть где - пропускная способность i- го канала.${\displaystyle C=\lim \inf {\frac {1}{n}}\sum _{i=1}^{n}C_{i}}$${\displaystyle C_{i}}$

Схема доказательства [ править ]

Доказательство проводится почти так же, как и доказательство теоремы о канальном кодировании. Достижимость следует из случайного кодирования, при котором каждый символ выбирается случайным образом из распределения достижения пропускной способности для этого конкретного канала. Аргументы типичности используют определение типичных множеств для нестационарных источников, определенных в статье об асимптотическом равнораспределении .

Когда не сходится, в игру вступает техническая сторона lim inf .${\displaystyle {\frac {1}{n}}\sum _{i=1}^{n}C_{i}}$

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

• Свойство асимптотического равнораспределения (AEP)
• Неравенство Фано
• Теория скорости – искажения
• Теорема Шеннона о кодировании источника
• Теорема Шеннона – Хартли.
• Турбо код

Заметки [ править ]

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

• Cover TM , Томас Дж. А., Элементы теории информации , John Wiley & Sons , 1991. ISBN 0-471-06259-6 
• Фано, Р. А. , Передача информации; статистическая теория коммуникаций , MIT Press , 1961. ISBN 0-262-06001-9 
• Файнштейн, Амиэль , «Новая основная теорема теории информации», IEEE Transactions on Information Theory , 4 (4): 2-22, 1954.
• Маккей, Дэвид Дж. К. , Теория информации, логический вывод и алгоритмы обучения , Cambridge University Press , 2003. ISBN 0-521-64298-1 [бесплатно в Интернете] 
• Шеннон, CE , Математическая теория коммуникации . Технический журнал Bell System 27,3: 379–423, 1948.
• Шеннон, CE , Математическая теория коммуникации Урбана, Иллинойс: University of Illinois Press, 1948 (перепечатано в 1998 году).
• Вулфовиц, Дж. , " Кодирование сообщений, подверженных случайным ошибкам ", Illinois J. Math. , 1: 591–606, 1957.

Внешние ссылки [ править ]

• О законе Шеннона и Шеннона
• Теорема Шеннона о кодировании каналов с шумом