XI → канал → y

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

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

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

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

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

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

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

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

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

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

|S_ρ(x)| ≤ 2^nH(ρ\n) .

Прологарифмируем и поделим на 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ⁿ.

(1)

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

(****)

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

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

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

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

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

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

Приведенное ниже доказательство основано на доказательстве из [10].

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

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

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

Декодирование y производится по принципу наибольшего правдоподобия – в ближайшую кодовую точку. Если это xⁱ, то ошибки нет. Если это не xⁱ, то происходит ошибка.

x^j

Б

y

xⁱ

лиже, чем xⁱ ни одной точки к y нет y декодируется в xⁱ.

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

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

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

.

С другой стороны, из леммы (**) следует, что эта вероятность P{ τ > ρ} ≤ ε\2.

Таким образом

P_c = 1\M ∑P(xⁱ)=

Заметим теперь, что математическое ожидание того, что у попал в шар с центром в xⁱ, равно:

E(f(y|xⁱ)=| S_ρ(x)| / 2ⁿ .

Теперь вспомним неравенство:

P *(M, n, p) ≤

Заметим теперь, что минимальное значение случайной величины не превосходит ее математического ожидания:

Minξ≤ E(ξ).

Из этих соотношений следует цепочка неравенств.

P *(M, n, p) =

= = =

= =

Таким образом

P *(M, n, p) – ε\2≤

Вспомним, что 0 < R < C(ρ), M=2^[nR].

Применяем лемму ( ) и соотношения: [nR] = log M, M = 2^Rn :

1\n log (P*(M, n, P) – ε\2) ≤ 1\n log (|S_ρ|M\2ⁿ )= 1\n log |S_ρ|2^Rn-n ≤ R – C(ρ) – 1 – O(n^-1\2) + 1.

Пусть δ= C(P)-R. Тогда имеем при при больших n неравенство

P*(M, n, P) < ε\2 + 2^-δn.

Устремляем n→∞ и δ→0. Получаем

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

Теорема доказана.