Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
135
возникает проблема, состоящая в том, что число кодовых слов в коде задается М = eNR и, таким образом, следует ожидать быстрого роста сложности кодера и декодера с ростом N. Эта проблема сложности будет исследована в гл. 6, где будет показано, что этот рост сложности намного слабее, чем можно было бы ожидать, но отнюдь не является малозначительным, В большинстве систем, использующих кодирование, проблема задержки имеет существенно меньшее значение, чем сложность.
5.2. ДЕКОДИРОВАНИЕ БЛОКОВЫХ КОДОВ
Правило декодирования с минимальной вероятностью ошибки является правилом, которое минимизирует вероятность ошибочного декодирования для заданных ансамбля сообщений, множества кодовых слов и канала. Пусть PN (у | хт) — вероятность приема последовательности у при условии, что было передано т-е кодовое слово. Для дискретного канала без памяти она выражается через переходные вероятности канала Р (у \ х) как
^jv(y|xm) = П Р(Уп\хт,п). (5.2.1)
/2—1
Если априорные вероятности сообщений равны Рг (т), то апостериорная вероятность сообщения т при условии, что принята последовательность у, равна
п , , . PN (У ЫРгМ п 0,
РгМу =------------——----------------------------—, (5.2.2)
Рг (У)
где
и
Рг(у)= %Рг (m)PN(y|xm).
т— 1
Если декодер декодирует последовательность у в сообщение т, то вероятность (при заданном у) того, что декодирование является ошибочным, равна 1 — Pr (т|у). Декодер минимизирует вероятность ошибки выбором т, которое максимизирует Pr (т|у). Таким образом, правило декодирования с минимальной вероятностью ошибки определяется следующим образом: следует декодировать принятую последовательность у в т', для которого
Рг (т' | у) ^ Рг (т | у) для всех тфт'. (5.2.3)
Если при заданном у величина Рг (т | у) максимизируется на нескольких различных значениях т, то ясно, что нет разницы, какое из этих значений следует выбрать. Так как знаменатель в (5.2.2) не зависит от т, то правило, эквивалентное правилу декодирования с минимальной вероятностью ошибки, состоит в следующем: следует декодировать у в т', для которого
Рг(т')Р^(у|х/П') > Pr (m)PN (у \хт) для всех тфт'. (5.2.4)
136
Другим правилом декодирования является декодирование по максимуму правдоподобия, которое определяется следующим образом: при заданном у надлежит выбрать т', для которого
pw(ylxm')>-fV(y|xm) для всех тфт'. (5.2.5)
Очевидным преимуществом декодирования по максимуму правдоподобия является то, что оно может быть применено тогда, когда априорные вероятности сообщений не определены или не имеют смысла. Название «максимум правдоподобия» является отчасти дезориентирующим, так как соответствующее ему правило не обязательно приводит к сообщению, которое наиболее вероятно при заданном у. Вместо этого выбирается сообщение, для которого данное у наиболее вероятно при заданном т [сравните (5.2.3) и (5.2.5)]. В частном случае, когда сообщения имеют равные априорные вероятности, можно заметить, что (5.2.4) и (5.2.5) эквивалентны, и в этом случае декодирование по максимуму правдоподобия минимизирует вероятность ошибки.
Другим правилом декодирования, полезным тогда, когда неравные стоимости соответствуют различным типам ошибок, является декодирование с минимальной стоимостью. При этом у декодируется в т, которое минимизирует среднюю стоимость (см. задачу 5.1). Этот класс задач рассматривается в гл. 9 с более фундаментальных позиций.
Наконец, в большинстве практических применений кодирования необходимо при выборе правил декодирования принимать во внимание простоту их реализации; связанные с этим задачи будут обсуждаться в следующей главе.
Итак, до сих пор мы рассматривали правила декодирования, по которым строится гипотеза о сообщении по заданной принятой последовательности канала. Однако, если шум особенно велик, часто при декодировании лучше отказаться от построения этой гипотезы, и в этом случае считается, что возникает обнаруживаемая ошибка. Способность к обнаружению ошибок, в частности, является полезной тогда, когда приемник имеет возможность передавать информацию назад к передатчику, который может вновь передать искаженные блоки.
Правило декодирования теперь можно определить формально, как отображение множества \N последовательностей на выходе канала в множество, состоящее из М сообщений, и выход, соответствующий обнаруженной ошибке. Обозначим множество последовательностей декодируемых в сообщение т через Ym, а дополнение этого множества через Ycm. Когда источник вырабатывает сообщение т, передается кодовое слово хт и возникает ошибка (либо необнаруживаемая, либо обнаруживаемая), если принятая последовательность у принадле-лежит множеству Ycm. Таким образом, вероятность ошибочного декодирования при условии, что было послано сообщение т, равна
