5.2. ДЕКОДИРОВАНИЕ БЛОКОВЫХ КОДОВ

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

Если априорные вероятности сообщений равны то апостериорная вероятность сообщения при условии, что принята последовательность у, равна

где

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

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

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

Очевидным преимуществом декодирования по максимуму правдоподобия является то, что оно может быть применено тогда, когда априорные вероятности сообщений не определены или не имеют смысла. Название «максимум правдоподобия» является отчасти дезориентирующим, так как соответствующее ему правило не обязательно приводит к сообщению, которое наиболее вероятно при заданном у. Вместо этого выбирается сообщение, для которого данное у наиболее вероятно при заданном [сравните (5.2.3) и (5.2.5)]. В частном случае, когда сообщения имеют равные априорные вероятности, можно заметить, что (5.2.4) и (5.2.5) эквивалентны, и в этом случае декодирование по максимуму правдоподобия минимизирует вероятность ошибки.

Другим правилом декодирования, полезным тогда, когда неравные стоимости соответствуют различным типам ошибок, является декодирование с минимальной стоимостью. При этом у декодируется в которое минимизирует среднюю стоимость (см. задачу 5.1). Этот класс задач рассматривается в гл. 9 с более фундаментальных позиций.

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

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

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

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

равна

Для примера рассмотрим код, представленный на рис. 5.2.1. В нем есть два кодовых слова Правило декодирования (которое, как можно заметить, является правилом максимального правдоподобия для состоит в том, чтобы декодировать каждую из последовательностей (0,0,0), (0,0,1), (0,1,0) и (1,0,0) в сообщение 1 и другие последовательности в сообщение 2. Следовательно, совпадает с и является множеством последовательностей (0,1,1), (1,0,1) (1,1,0) и (1,1,1). Для ДСК, изображенного на рис например, и подобное вычисление для других у из дает

Соотношения (5.2.5) и (5.2.7) "по виду довольно безобидные.

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

Рис. 5.2.1. Код и правило декодирования для