Схема кодирования по принципу наибольшего правдоподобия на основе принципа избыточности.

Рассмотрим теперь приведенный выше подход к построению кода более подробно.

Пусть мы имеем ситуацию1.Шар Bⁿ, в нем 2 ⁿ точек. M<2 ⁿ. Стараемся, чтобы каждую из этих точек можно было окружить шаром радиуса t так, чтобы эти шары не пересекались. Заметим, что из того, что p <½, следует:

pⁿ<p^{n- 1}(1 -p) <p^{n- 2}(1 -p)² < … < (1 -p) ⁿ.

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

Дешифруем Yⁱ. В шаре радиуса d с центром в точке xⁱ на расстоянии 1 стоят все векторы, которые получились бы из xⁱ в случае одной ошибки, на расстоянии 2 все векторы с двумя ошибками и т.д.

Возможны 3 случая:

1. Пусть шары с центрами в кодовых точках имеют радиус d и не пересекаются. Yⁱ оказалась в шаре с центром в xⁱ – произошло не более, чем d ошибок, ;

2. Yⁱ не попадает ни в один из шаров, для любого j; (в этом случае алгоритм декодирования должен предусматривать правило сопоставления Yⁱ какому-то из x^j).

3. (попала не в этот шар, а в соседний).

Если выполняется первый случай, то Yⁱ → xⁱ. Если третий, то Yⁱ → x^j, декодирование неверное.

Во втором случае обычно декодируют Yⁱ в x^j, тоже ошибка декодирования.

Пусть мы имеем ситуацию 2. Тогда у нас первого случая не будет вообще, а будут только два остальных.

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

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

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

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

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

P_с = 1\ M ∑ P (x).

Тогда P_c + P_с = 1.

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

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

P *(M, n, p) ≤

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

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

P *(M, n, p) ≥

Замечание.

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