Главная | Обратная связь | Поможем написать вашу работу!

Вероятностное доказательство второй теоремы Шеннона.

Это необязательное дополнение к лекциям для тех, кто уже знаком с самыми азами теории вероятностей. Базируется на лекциях [8].

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

Пусть - случайная величина. - мат. ожидание. - дисперсия.

Теорема 13.3. (Неравенство Чебышева) Справедливо неравенство:

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

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

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

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

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

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

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

xⁱ → канал → Y

Считаем, что Y = x _i + e, где e – вектор ошибок.

Пусть τ – случайная величина, равная | e | (количество ошибок).

Т.к. так как относительно этой величины мы имеем распределение Бернулли, то E (τ) = np, D (τ) = np (1 – p).

Вводится некоторый параметр b = , который носит чисто технический характер. Грубо говоря, если на одно слово приходится np ошибок, то мы будем окружать кодовые слова шарами радиуса ρ =[np+b], где b>0 – некоторая «маленькая» добавка

Лемма 13.2. Справедливо соотношение

P { τ > ρ } ≤ ε \2

для любого заранее заданного ε.

Доказательство. Применим неравенство Чебышева:

P {| τ – E (τ)| > ε } ≤ D (τ)/ ε ².

Положим ρ = [ E (τ) + b], тогда

P {| τ – np | > b} ≤ D (τ) / b ².

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

P {| τ – np | > b } ≤ ε/ 2.

Тогда P (τ > ρ) = P {| τ – np | > b }. Это проиллюстрировано ниже:

- τ np τ

τ > nP + b

τ – nP > b

Отсюда следует P { τ > ρ }≤ P {| τ – np | > b}≤ D (τ) / b ²=ε/2.

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

Лемма 13.3. Пусть ρ = [ E (τ) + b ] и b = , тогда

1\ n log | S_ρ (x)| ≤ H(P) + O(n -^1\2) при n → ∞.

Доказательство. Из леммы 13.1 и леммы 13.2 получаем неравенство:

| S_ρ (x)| ≤ 2 ^nH ^{(ρ \} ⁿ ⁾.

Прологарифмируем и поделим на n, разложим логарифм в ряд (это корректно) и оставим главные члены:

1\ n log | S_ρ (x)| ≤ H(ρ \ n) = - ρ \ n log ρ \ n – (1 – ρ \ n) log (1 – ρ \ n) = - [ nP + b ]\ n log [ nP + b ]\ n – (1 – [ nP + b ]\ n ] log (1 – [ nP + b ]\ n) ≈ - P log P – (1 – P) log (1 – P) + O(b \ n) = H(p)+ O(n ^-1\2).

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

Введем некоторую функцию, определенную на парах векторов из Bⁿ.

(13.5)

Лемма 13.4. Справедливо соотношение:

(13.6)

Доказательство. Здесь P (xⁱ) – вероятность неправильного декодирования переданного слова xⁱ Bⁿ. P (y‌‌| xⁱ) - вероятность того, что при передаче слова xⁱ на декодер попало слово y. Пусть Q(y‌‌| xⁱ)- вероятность того, слово y декодировано в слово xⁱ. Тогда

Заметим, что слово y может быть декодировано в слово x^j, только если оно попало в шар соответствующего радиуса с центром в x^j. Из этого следует, что

Если xⁱ декодируется правильно, то y попало в шар нужного радиуса с центром в xⁱ, и тогда =0. В этом случае в неравенстве (13.6) слева 0, а справа неотрицательная величина. Если xⁱ декодируется неправильно, то y попало в шар нужного радиуса с центром в x^j, j≠i, и тогда, если =0, то

Если же =1 (а это может быть, если шары пересекаются), то

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

Доказательство теоремы.

Теорема 13.4 (вторая теорема Шеннона). Для любого R: 0 < R < C (ρ), такого что M=2^[^nR], выполняется соотношение:

P *(M, n, P) → 0, n → ∞.

Доказательство. Пусть передаем x ⁱ, принято некое y, оцениваем ошибку декодирования.

Мы рассматриваем в качестве кодов все возможные подмножества Bⁿ. Т.е. кодовые точки располагаются случайным образом. Точки упали как угодно, на них строим шары радиуса ρ.

Декодируем так: если точка у попала в шар радиуса t вокруг кодовой точки, то декодируем ее в данную кодовую точку, если в этом шаре нет других точек; если есть другие кодовые точки или у не попало ни в один из шаров вокруг кодовой точки, то у декодируем по эвристическим правилам. При этом возможна ошибка декодирования.

Вспомним введенную выше функцию f(x,y). Из леммы 13.4 следует, что вероятность того, что у находится от x ⁱ на расстоянии, большем ρ, задается формулой: