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

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

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

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

Обзор

Сформулированная Клодом Шенноном в 1948 году, теорема описывает максимально возможную эффективность методов исправления ошибок в зависимости от уровней помех и искажения данных. Теорема Шеннона имеет широкое применение как в коммуникациях, так и в хранении данных . Эта теорема имеет основополагающее значение для современной области теории информации . Шеннон дал только схему доказательства. Первое строгое доказательство для дискретного случая приведено в (Feinstein 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. Sae-Young Chung; Forney, GD ; Richardson, TJ; Urbank, R. (февраль 2001 г.). «О разработке кодов с низкой плотностью проверок на четность в пределах 0,0045 дБ от предела Шеннона» (PDF) . IEEE Communications Letters . 5 (2): 58–60. doi :10.1109/4234.905935. S2CID  7381972.
2. Описание функции "sup" см. в разделе Supremum.
3. Галлагер, Роберт (1968). Теория информации и надежная связь . Wiley. ISBN 0-471-29048-3.

Ссылки

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

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