2. Теорема Шеннона для канала с шумом.

Есть несколько теорем Шеннона. Одна была рассмотрена выше (теорема Шеннона для канала без шума). Здесь мы докажем еще одну теорему Шеннона и об одной просто упомянем. (Эти теоремы известны как теоремы Шеннона для канала с шумом.).

расскажем еще об одной

Везде в дальнейшем k – число информационных символов. То есть число слов, подлежащих передаче в канал, равно 2^k .

- скорость передачи.

C(p) = 1 – H(p) – пропускная способность канала (доля канала, предназначенного для информации).

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

В теореме Шеннона для канала с шумом будет показано, что существуют коды, когда для любого ε>0 при V(C)< 1- H(p) вероятность ошибки декодирования не более ε.

1. Факты из теории вероятности.

- случайная величина.

- мат. ожидание.

- дисперсия.

Теорема (неравенство Чебышева)

Испытание Бернулли, вероятность успеха p (неудача 1- p). Есть n испытаний. (Удачное испытание – произошла ошибка, неудачное – не произошла. Так как передается n символов, то мы получаем n испытаний во время передачи кодового слова.)

В случае источника Бернулли справедливы равенства: и D(ξ)=np(1-p).

Первое из них очевидно, а ниже приведено краткое доказательство второго.

2. Схема кодирования и декодирования. Вспомогательные утверждения.

Пусть - вектор ошибок. Он подчиняется распределению Бернулли, поэтому матожидание и дисперсия такого вектора и D(ξ)=np(1-p).

Рассмотрим некоторый код C = {x¹…x^M}, где {x¹…x^M}– кодовые слова (вектора Bⁿ).

Применяем декодирование в ближайшее слово (по принципу наибольшего правдоподобия и согласно приведенной выше схеме декодирования). Обозначим через T(C) таблицу декодирования.

П ередача Прием

a x¹ T(C) – таблица

b x²

… …

… x^M

Зададим некоторое ρ>0. Тогда таблица T_ρ(C) состаляется так, чтобы под каждым кодовым словом в столбце находились все слова из S_ρ(xⁱ). Все слова, которые не вошли в столбцы после этого, помещаем в первый столбец.

Замечание.

Подчеркнем еще раз, что кодом называется любое подмножество булева куба Bⁿ мощностью M. Поэтому не любой код будет кодом, исправляющим ошибки. Но к любому коду можно формально применить описанную выше схему декодирования. Все точки кода окружаем шарами радиуса ρ, а полученный вектор декодируем в центр шара. Если же вектор попадает в несколько кодовых шаров, то считаем, что произошла ошибка декодирования. Правило, по которому в этом случае декодер производит декодирование несущественно. Например, применяется какое-нибудь дополнительное правило декодирования: в случайный, в ближайший и т.п.

Вероятность ошибки декодирования.

Обозначим через P(x) – вероятность неправильного декодирования при условии, что передано слово x Bⁿ. Просуммируем по всем кодовым словам из Bⁿ . Сумма ∑P(x) – зависит от комбинаторных свойств кода, вероятности искажения информации в канале p и т.д.

Обозначим через P_c = 1\M ∑P(x) – среднюю ошибку на одно кодовое слово в коде C. Таким образом, число P_c = 1\M ∑P(x) является характеристикой кода C.

Число различных кодов мощности M в Bⁿ: равно .

Пусть L – множество всех таких кодов.

Пусть  (x) – вероятность правильного декодирования.

 _с = 1\M ∑ (x).

Тогда P_c +  _с = 1.

Обозначим через P*(M, n, p) = min Pc, где минимум берется по всем кодам из множества L. То есть P*(M, n, p) – характеристика некоторого существующего кода, являющаяся наилучшей из возможных с точки зрения ошибки декодирования.

Очевидно, что

P *(M, n, p) ≤

Обозначим через  *(M,n,p)= max ρ_с , где максимум берется по всем кодам из множества L. То есть  *(M,n,p) – характеристика некоторого существующего кода, являющаяся наилучшей из возможных с точки зрения ошибки декодирования.

Очевидно, что

 *(M, n, p) ≥

Замечание.

Доказываемая нами теорема Шеннона является теоремой существования. Она не дает алгоритма построения кода с характеристикой P*(M, n, p).

На сегодняшний день наилучший код не найден, все существующие отличны от него в константу раз.

Лемма ( ). Возьмем точку в Bⁿ и шар S_[pn](x), оценим число точек в нем. Справедливо неравенство

|S_[pn](x)| ≤ 2^nH(p)

Доказательство: |S_[pn](x)| = .

Вспомним, что 0 ≤ p < 1\2,. Согласно принципу наибольшего правдоподобия – декодирование в ближайшее кодовое слово – выполняется соотношение

(1 – p)ⁿ ≥ p(1 – p)^n-1 ≥ … ≥ p^k(1-p)^n-k.

Отсюда следует.

,

где - мощность шара радиуса [pn] .

Тогда |S_[pn](x)| ≤ (p^[pn] (1 – p) ^{n – [pn]})^-1 = = 2^nH(p)

Лемма доказана.

Пусть в канал передается вектор xⁱ, а в декодер поступил вектор Y.