Теорема о кодировании зашумленного канала

«Теорема Шеннона» перенаправляется сюда. Имя Шеннона также связано с теоремой выборки .

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

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

Обзор

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

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

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

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

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

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

График, показывающий долю пропускной способности канала ( ось Y ), которая может быть использована для полезной нагрузки, в зависимости от уровня шума канала (вероятность переворота битов; ось X ).

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

${\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 передается по зашумленному каналу с использованием функций кодирования и декодирования Кодер n отображает W в заранее определенную последовательность символов канала длины . В своей самой базовой модели канал искажает каждый из этих символов независимо от других. Выход канала – полученная последовательность – подается в декодер , который отображает последовательность в оценку сообщения. В этом случае вероятность ошибки определяется как:

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

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

1. Для каждого дискретного канала без памяти пропускная способность канала определяется через взаимную информацию. $I(X;Y)$ как

$\ C=\sup _{p_{X}}I(X;Y)$

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

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

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

и $H_{2}(p_{b})$ это двоичная функция энтропии

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

3. Для любого $p_{b}$, ставки превышают $R(p_{b})$ не достижимы.

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

Схема доказательства

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

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

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

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

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

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

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

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

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

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

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

Шаги

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

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

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

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

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

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

${\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}}$

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

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

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

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

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

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

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

Сильная обратная теорема, доказанная Вулфовицем в 1957 году: заявляет, что,

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

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

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

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

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

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

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

Схема доказательства

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

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

См. также

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

Ссылки

• Аажанг, Б. (2004). «Теорема Шеннона о кодировании канала с шумом» (PDF) . Соединения .
• Обложка, ТМ ; Томас, Дж. А. (1991). Элементы теории информации . Уайли. ISBN  0-471-06259-6 .
• Фано, РМ (1961). Передача информации; статистическая теория коммуникаций . МТИ Пресс. ISBN  0-262-06001-9 .
• Файнштейн, Амиэль (сентябрь 1954 г.). «Новая основная теорема теории информации». Труды профессиональной группы IRE по теории информации . 4 (4): 2–22. Бибкод : 1955PhDT........12F . дои : 10.1109/TIT.1954.1057459 . hdl : 1721.1/4798 .
• Лундхейм, Ларс (2002). «О Шенноне и формуле Шеннона» (PDF) . Телектроник . 98 (1): 20–29.

• Маккей, Дэвид Дж. К. (2003). Теория информации, вывод и алгоритмы обучения . Издательство Кембриджского университета. ISBN  0-521-64298-1 . [бесплатно онлайн]
• Шеннон, CE (1948). «Математическая теория связи». Технический журнал Bell System . 27 (3): 379–423. дои : 10.1002/j.1538-7305.1948.tb01338.x .
• Шеннон, CE (1998) [1948]. Математическая теория связи . Издательство Университета Иллинойса.
• Вулфовиц, Дж. (1957). «Кодирование сообщений, допускающее случайные ошибки» . Иллинойс Дж. Математика . 1 (4): 591–606. дои : 10.1215/ijm/1255380682 .