Теорема кодирования с шумом канала - Noisy-channel coding theorem

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

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

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

Обзор

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

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

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

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

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

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

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

${\ displaystyle {\ xrightarrow [{\ text {Message}}] {W}} {\ begin {array} {| c | } \ hline {\ text {Encoder}} \\ f_ {n} \\\ hline \ end {array}} {\ xrightarrow [{\ mathrm {Закодированная \ наверху последовательность}}] {X ^ {n}}} { \ begin {array} {| c | } \ hline {\ text {Channel}} \\ p (y | x) \\\ hline \ end {array}} {\ xrightarrow [{\ mathrm {Получено \ наверху последовательности}}] {Y ^ {n}} } {\ begin {array} {| c | } \ hline {\ text {Decoder}} \\ g_ {n} \\\ hline \ end {array}} {\ xrightarrow [{\ mathrm {Оценка \ наверху сообщения}}] {\ 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)}$

обладает следующим свойством. Для любого и , для достаточно большого , существует код длины и скорости и алгоритм декодирования, такой, что максимальная вероятность блочной ошибки равна .${\ 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 ^ {- п (Н (Х) + \ varepsilon)} \ leq p (X_ {1} ^ {n}) \ leq 2 ^ {- n (H (X) - \ varepsilon)}}$

${\ Displaystyle 2 ^ {- п (ЧАС (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 ^ {- п (H (X, Y) - \ varepsilon)} \}}$

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

Шаги

1. В стиле аргумента случайного кодирования мы случайным образом генерируем кодовые слова длины n из распределения вероятностей Q.${\ displaystyle 2 ^ {nR}}$
2. Этот код раскрывается отправителю и получателю. Также предполагается, что известна матрица перехода для используемого канала.${\ Displaystyle р (у | х)}$
3. Сообщение W выбирается в соответствии с равномерным распределением по набору кодовых слов. То есть .${\ Displaystyle Pr (W = ш) = 2 ^ {- nR}, ш = 1,2, \ точки, 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} (я)}$${\ displaystyle Y_ {1} ^ {n}}$${\ Displaystyle \ Leq 2 ^ {- п (I (X; Y) -3 \ varepsilon)}}$

Определять: ${\ displaystyle E_ {i} = \ {(X_ {1} ^ {n} (i), Y_ {1} ^ {n}) \ in A _ {\ varepsilon} ^ {(n)} \}, i = 1,2, \ точки, 2 ^ {nR}}$

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

${\ displaystyle {\ begin {align} 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 {выровнено}}}$

Мы можем наблюдать, что по мере приближения к бесконечности, если для канала вероятность ошибки упадет до 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 ЧАС (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}$ за счет того, что емкость взаимной информации максимальна.

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

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

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

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

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

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

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

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

${\ displaystyle C = \ lim \ inf \ max _ {p ^ {(X_ {1})}, p ^ {(X_ {2})}, ...} {\ frac {1} {n}} \ сумма _ {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}}$

Скорость кодирования канала в режиме конечной длины блока

Теория информации с конечной длиной блока исследует максимальную скорость кодирования канала, достижимую при заданной длине блока и вероятности ошибки в режиме конечной длины блока (неасимптотический режим). Максимально достижимая скорость кодирования канала с заданной вероятностью блочной ошибки и длиной блока (для каналов с двоичным аддитивным белым гауссовым шумом (AWGN) с короткими длинами блоков), близко аппроксимируемая Полянским , Бедным и Верду (PPV) в 2010 г., определяется выражением ${\ displaystyle \ left ({\ bar {R}} \ right)}$${\ Displaystyle \ влево (\ эпсилон \ вправо)}$${\ Displaystyle \ влево (п \ вправо)}$

${\ displaystyle {\ bar {R}} \ приблизительно C - {\ sqrt {\ frac {V} {n}}} Q ^ {- 1} \ left (\ epsilon \ right)}$

где - величина, обратная дополнительной кумулятивной функции распределения Гаусса , - пропускная способность канала и является характеристикой канала, называемой дисперсией канала. ${\ displaystyle Q ^ {- 1}}$ ${\ displaystyle C}$${\ displaystyle V}$

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

• Свойство асимптотического равнораспределения (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.

внешние ссылки

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