Главная > Разное > Теория кодирования и теория информации
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

10.2. Решающие правила

Пусть на приемном конце канала получен символ Какое следует сделать предположение о посланном символе Это, нечно, зависит от канала, т. е. от переходных вероятностей а также от вероятностей символов источника

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

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

при этом у каждого правила имеются свои преимущества перед другими. Отметим, что решение принимается по каждому символу в отдельности, а не по последовательностям символов.

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

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

где а определяется условиями

Другими словами, если принят символ то никакой символ не может быть более вероятным, чем а. Соответствующие вероятности не являются переходными вероятностями канала. Для того чтобы ввести их, следует воспользоваться формулой Байеса и получить

Если все входные символы равновероятны, то и

Таким образом, условие максимального правдоподобия (10.2.3) выражено через переходные вероятности канала.

В дальнейшем это правило используется даже в тех случаях, когда символы входного алфавита не равновероятны. В общем случае оно не является оптимальным, однако, как и при использовании кода Шеннона — Фано (вместо оптимального кода Хаффмена), для длинных последовательностей отход от оптимальности будет незначительным. При этом правиле по-прежнему можно получить требуемый результат. Это свидетельствует о некоторой устойчивости окончательного результата: на некоторых этапах можно выбирать неоптимальный путь, и теорема тем не менее будет доказана.

Рассматриваемый пример (10.2.2) показывает, что правило максимального правдоподобия не является однозначным. Ясно, что применение правила максимального правдоподобия к каналу (10.2.1) дает Однако для можно выбрать любое из следующих трех правил: Наконец, по правилу максимального правдоподобия,

Таким образом, для данного канала существует три правила (10.2.2) максимального правдоподобия.

Какова вероятность ошибки при использовании в данном канале этого решающего правила? Если записать вероятность

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

Средняя ошибка задается равенством

Используя (10.2.5), ее можно записать в виде

Применяя формулу Байеса (см. разд. 7.3), можно выразить условные вероятности через переходные вероятности канала (напомним, что все вероятности равны

Вычислим эту величину для нашего канала и решающего правила, записанного в последнем столбце выражения (10.2.2). Из матрицы

и равенства (10.2.6) имеем

<< Предыдущий параграф Следующий параграф >>
Оглавление