Теорема кодирования в шумном канале
Ограничение скорости передачи данных
Теория информации

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

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

Обзор

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

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

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

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

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

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

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

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

→ Сообщение Вт Кодировщик ф н → Э н с о г е г с е д ты е н с е Х н Канал п ( у | х ) → Р е с е я в е г с е д ты е н с е И н Декодер г н → Э с т я м а т е г м е с с а г е Вт ^ {\displaystyle {\xrightarrow[{\text{Сообщение}}]{W}}{\begin{array}{|c| }\hline {\text{Кодер}}\\f_{n}\\\hline \end{array}}{\xrightarrow[{\mathrm {Закодированная \atop последовательность}}]{X^{n}}}{\begin{array}{|c| }\hline {\text{Канал}}\\p(y|x)\\\hline \end{array}}{\xrightarrow[{\mathrm {Получена \atop последовательность}}]{Y^{n}}}{\begin{array}{|c| }\hline {\text{Декодер}}\\g_{n}\\\hline \end{array}}{\xrightarrow[{\mathrm {Расчетное \atop сообщение} }]{\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]
имеет следующее свойство. Для любого и , для достаточно большого , существует код длины и скорости и алгоритм декодирования, такой что максимальная вероятность ошибки блока равна . ϵ > 0 {\displaystyle \epsilon >0} Р < С {\displaystyle R<C} Н {\displaystyle N} Н {\displaystyle N} ≥ Р {\displaystyle \geq R} ≤ ϵ {\displaystyle \leq \epsilon}
2. Если вероятность битовой ошибки приемлема, то достижимы скорости до , где п б {\displaystyle p_{b}} Р ( п б ) {\displaystyle R(p_{b})}
Р ( п б ) = С 1 − ЧАС 2 ( п б ) . {\displaystyle R(p_{b})={\frac {C}{1-H_{2}(p_{b})}}.}
и является бинарным энтропийным функционалом ЧАС 2 ( п б ) {\displaystyle H_{2}(p_{b})}
ЧАС 2 ( п б ) = − [ п б бревно 2 ⁡ п б + ( 1 − п б ) бревно 2 ⁡ ( 1 − п б ) ] {\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} Х 1 н {\displaystyle X_{1}^{n}} н {\displaystyle n} И 1 н {\displaystyle Y_{1}^{n}}

А ε ( н ) = { ( х н , у н ) ∈ Х н × И н {\displaystyle A_{\varepsilon }^{(n)}=\{(x^{n},y^{n})\in {\mathcal {X}}^{n}\times {\mathcal {Y}}^{n}}
2 − н ( ЧАС ( Х ) + ε ) ≤ п ( Х 1 н ) ≤ 2 − н ( ЧАС ( Х ) − ε ) {\displaystyle 2^{-n(H(X)+\varepsilon)}\leq p(X_{1}^{n})\leq 2^{-n(H(X)-\varepsilon)}}
2 − н ( ЧАС ( И ) + ε ) ≤ п ( И 1 н ) ≤ 2 − н ( ЧАС ( И ) − ε ) {\displaystyle 2^{-n(H(Y)+\varepsilon)}\leq p(Y_{1}^{n})\leq 2^{-n(H(Y)-\varepsilon)}}
2 − н ( ЧАС ( Х , И ) + ε ) ≤ п ( Х 1 н , И 1 н ) ≤ 2 − н ( ЧАС ( Х , И ) − ε ) } {\displaystyle {2^{-n(H(X,Y)+\varepsilon)}}\leq p(X_{1}^{n},Y_{1}^{n})\leq 2^{-n(H(X,Y)-\varepsilon)}\}}

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

Шаги

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

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

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

Определять: Э я = { ( Х 1 н ( я ) , И 1 н ) ∈ А ε ( н ) } , я = 1 , 2 , … , 2 н Р {\displaystyle E_{i}=\{(X_{1}^{n}(i),Y_{1}^{n})\in A_{\varepsilon }^{(n)}\},i=1,2,\dots ,2^{nR}}

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

P ( error ) = P ( error | W = 1 ) ≤ P ( E 1 c ) + ∑ i = 2 2 n R P ( E i ) ≤ P ( E 1 c ) + ( 2 n R − 1 ) 2 − n ( I ( X ; Y ) − 3 ε ) ≤ ε + 2 − n ( I ( X ; Y ) − R − 3 ε ) . {\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. n {\displaystyle n} R < I ( X ; Y ) {\displaystyle R<I(X;Y)}

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

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

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

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

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

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

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

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

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

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

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

Тогда пропускная способность канала определяется как

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

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

План доказательства

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

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

Смотрите также

Примечания

  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 .
Retrieved from "https://en.wikipedia.org/w/index.php?title=Noisy-channel_coding_theorem&oldid=1268353029"