Декодирование по максимуму правдоподобия

Пусть есть код A, содержащий M= 2 ^k слов, причем каждое слово имеет разрядность n:

A =(a ₁, a ₂, …, a_M), a_i =(0, 1, …, n –1).

На длине кода возможны следующие ошибки:

– одиночные, t = 1;

– двукратные, t = 2;

……………………

– n -кратные, t = n.

Суммарное число всевозможных ошибок равно E =2 ⁿ –1.

Задача декодирования состоит в том, чтобы по принятому вектору b_j однозначно определить переданное сообщение a_i, т.е. в качестве a_i следует принять такой вектор, для которого условная вероятность p (a_i / b_j) максимальна. Декодирование, когда максимизируется p (a_i / b_j), получило название декодирования по максимуму апостериорной вероятности. В теории информации

доказывается, что p (a_i / b_j)= С p (b_j / a_i), где С – константа. Следовательно, для максимизации p (a_i / b_j) необходимо максимизировать условную вероятность p (b_j / a_i). Для каждого отдельного канала эта вероятность имеет свое конкретное значение. Для наиболее широко применяемого двоично-симметричного канала зависимость этой вероятности от числа ошибок показана на рис. 6.2.

Из рис. 6.2 следует, что для максимизации p (bj / ai) необходимо выбирать кратность ошибки как можно меньше. Отсюда следует правило декодирования: в качестве переданного слова следует выбирать такое слово, которое отличается от принятого слова в наименьшем числе позиций. Это можно определить так же, как декодирование по минимуму расстояния: принятое слово отождествляется с тем кодовым словом, от которого оно удалено на минимальное расстояние. В теории информации показывается, что такое декодирование является наилучшим декодированием, так как обеспечивает минимальную вероятность ошибки.

На рис. 6.3 представлена структурная схема декодирующего устройства(декодера), реализующего декодирование по минимуму расстояния, где УСр– устройство сравнения, РУ – решающее устройство.

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

Оценим сложность декодера. Пусть код имеет длину n и содержит 2 ^k кодовых слов. Для вычисления расстояния нужно умножить каждое из этих слов на принятое, вычислить скалярное произведение. Одно умножение требует выполнения n арифметических операций сложения двух чисел. Общее количество арифметических операций пропорционально величине n ×2 ^k. Это число растет очень быстро с ростом k, поэтому декодирование по минимуму расстояния целесообразно использовать лишь в кодах с малым числом информационных символов (в низкоскоростных кодах, когда r >> k).

С формальной точки зрения операция корреляции сводится к умножению принятого вектора на кодовую матрицу. Для кодов с основанием q = 2 для подобного умножения требуется n (n –1) операций сложения (вычитания).

При больших n это приводит к большим вычислительным затратам.