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

Ограничение на скорость передачи данных

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

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

Обзор

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

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

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

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

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

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

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

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

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

${\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)}$^[2]

имеет следующее свойство. Для любого и при достаточно большом существует код длины и скорости и алгоритм декодирования, такие, что максимальная вероятность ошибки блока равна . ${\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 году ^[3] , утверждает, что

${\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)
• Неравенство Фано
• Теория скорости-искажения
• Теорема Шеннона о кодировании исходного кода
• Теорема Шеннона – Хартли
• Турбокод

Примечания

1. Саэ-Янг Чунг; Форни, Джорджия ; Ричардсон, Ти Джей; Урбанк, Р. (февраль 2001 г.). «О разработке кодов с низкой плотностью проверки четности в пределах 0,0045 дБ от предела Шеннона» (PDF) . Коммуникационные письма IEEE . 5 (2): 58–60. дои : 10.1109/4234.905935. S2CID  7381972.
2. Описание функции «sup» см. в Supremum .
3. Галлагер, Роберт (1968). Теория информации и надежная связь . Уайли. ISBN 0-471-29048-3.

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

• Аажанг, Б. (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. doi :10.1002/j.1538-7305.1948.tb01338.x.
• Шеннон, CE (1998) [1948]. Математическая теория связи. Издательство Университета Иллинойса.
• Вулфовиц, Дж. (1957). «Кодирование сообщений, допускающих случайные ошибки». Иллинойс Дж. Математика . 1 (4): 591–606. дои : 10.1215/ijm/1255380682 .