Принципы помехоустойчивого кодирования

1.4.3 Принципы помехоустойчивого кодирования

Покажем, каким образом избыточное кодирование позволяет повысить верность передачи сообщения. Как отмечалось,

для помехоустойчивых блочных равномерных кодов тп>М. Это значит, что для передачи знаков сообщения используют лишь часть возможных последовательностей, составленных из m- ичных символов (часть пространства n-последовательностей). Последовательности, используемые при кодировании, называются разрешенными кодовыми комбинациями, а все другие n- последовательности — запрещенными. На вход канала поступают только разрешенные комбинации. Если при передаче ко-

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

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

Если принята запрещенная кодовая комбинация bj, то, зная параметры канала, можно определить, какая из разрешен-

ных комбинаций bi вероятнее всего передавалась, и произвести декодирование принятой комбинации bj в комбинацию, совпа-

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

47

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

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

ется на M не перекрывающихся подмножеств: В1,B2, ..., Вм. Если принята последовательность, принадлежащая

подмножеству Вi, то считается, что передавалась кодовая комбинация bi. Есте-ственно, что в подмножестве Вi следует включить те запрещен-ные комбинации bj,при приеме которых наиболее вероятной пе-реданной комбинацией является bi.

При декодировании с обнаружением ошибок множество

B разбивается на М+1 подмножеств, из которых В1,В2, ..., ВM со-держат каждое по одной (разрешенной) кодовой комбинации,

а подмножество Вм+1 — все остальные (запрещенные) комбинации. В некоторых системах связи принятая запрещенная комбинация просто отбрасывается и не поступает к получателю. Это обосновано в тех случаях, когда потеря переданного сообщения значительно менее вредна, чем получение ложного сообщения. Чаще при декодировании с обнаружением ошибки ошибочно принятая кодовая комбинация не теряется, а восстанавливается специальными методами. Среди них наиболее распространен метод переспроса.

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

комбинаций можно включить в любое из подмножеств Вi. В за-

48

висимости от свойств канала то или иное правило является предпочтительным.

Существуют и смешанные методы декодирования, когда некоторые ошибки исправляют, а другие только обнаруживают. Здесь множество В также разбито на М+1 подмножеств, но в

подмножество В1 ..., Вм помимо разрешенных комбинаций входят и некоторые близкие к ним запрещенные (исправляемые), а

в BM+1 — только те запрещенные комбинации, которые не могут быть достаточно надежно исправлены.

Говорят, что в канале произошла ошибка кратности q, если в кодовой комбинации q символов приняты ошибочно. Легко видеть, что кратность ошибки есть не что иное, как расстояние Хэмминга между переданной и принятой кодовыми комбинациями, или, иначе, вес вектора ошибки.

Рассматривая все разрешенные кодовые комбинации и определяя кодовые расстояния между каждой парой, можно найти наименьшее из них d = min d(i;j), где минимум берется по всем парам разрешенных комбинаций. Это минимальное кодовое расстояние является важным параметром кода. Очевидно, что для простого кода d=1.

Обнаруживающая способность кода характеризуется следующей теоремой.

Если код имеет d>l и используется декодирование по методу обнаружения ошибок, то все ошибки кратностью q<.d обнаруживаются. Что же касается ошибок кратностью q≥d, то одни из них обнаруживаются, а другие нет.

Для доказательства достаточно вспомнить, что кодовое расстояние между посланной и принятой комбинациями равно q. Следовательно, если q<d, принятая комбинация не может быть разрешенной, так как это противоречило бы определению d. Поэтому она будет принадлежать подмножеству запрещенных комбинаций, т. е. ошибка будет обнаружена. При q≥d принятая комбинация может оказаться разрешенной и ошибка останется

49

необнаруженной, но часто и в этом случае принятая комбинация оказывается запрещенной и ошибка обнаруживается.

Процесс исправления ошибок рассмотрим сначала для симметричного канала без памяти. В таком канале по определению, вероятность правильного приема символа 1—p не зависит от того, какой символ передается, а также от того, как приняты остальные символы. Вероятность того, что вместо переданного

сюда легко вывести, что вероятность получения на выходе «ка-

роятностей независимых событий и из того, что для перехода bi

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

Таким образом, в симметричном канале без памяти

P(bj|bi) зависит только от кодового расстояния между bi и bj. В

случаях, когда р<(т— 1)/т, что практически всегда выполняется, выражение (5.3) монотонно убывает с увеличением d(i; j).

ше, чем меньше ее кодовое расстояние от переданной комбина-

ции bi.

Задачей декодера является принятие решения о том, ка-кая

верное. Однако можно добиваться минимума вероятности ошибочного декодирования. Пусть Р (bi | bj) — условная вероятность того, что передавалась комбинация bi, если принята комбинация

50

€ b j . Эту условную вероятность называют апостериорной веро-

ятностью в отличие от безусловной априорной вероятности Р

(bi) того, что передается bi, когда ничего еще не известно о принятой комбинации. Предположим, что декодер по принятой

€ комбинации b j решил, что передавалась комбинация bk. Веро-

€

ятность того, что это решение верно, очевидно, равна P(bk| b j ).

Чтобы эта вероятность была максимально возможной, декодер

должен из всех разрешенных комбинаций bi(i=1, ..., М) выбрать ту, для которой апостериорная вероятность максимальна. Это правило декодирования по максимуму апостериорной вероятности можно записать сокращенно так:

max P(bi | b j ) .

i

Из теории вероятностей известно, что

(формула Байеса).

Если, как часто бывает на практике, все разрешенные ко-

довые комбинации равновероятны (P(bi ) const 1/M), то максимум апостериорной вероятности совпадает с максимум услов-

ной вероятности P(b j | bi ) , которую называют функцией правдо-

подобия. Правило декодирования по максимуму правдоподобия можно сокращенно записать так:

51

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

множество Вi - следует включить все те комбинации b€j , которые

ближе (в смысле Хэмминга) к bi € , чем в любой другой разрешенной комбинации.

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

Исправляющая способность кода при этом правиле декодирования определяется следующей теоремой.

Если код имеет d>2 и используется декодирование с исправлением ошибок по наименьшему расстоянию, то все ошибки кратностью g<d/2 исправляются. Что же касается ошибок большей кратности, то одни из них исправляются, а другие нет.

Для доказательства покажем, что в условиях теоремы

(при q<.d/2) действительно переданная комбинация bi ближе (в смысле Хэмминга) к принятой комбинации bj, нежели любая другая разрешенная комбинация. Предположим противное, т. е.

что существует разрешенная комбинация bk, для которой d(k; j)<d(i;j). На основании отсюда следует, что d(k;i)≤d(k;j)+d(i;j)<2d(i;j). Но по условию теоремы d(i;j)=q<d/2.

Отсюда d(k;i)<d, что противоречит определению d. Это противоречие и свидетельствует о справедливости теоремы.

Полученные результаты можно выразить следующими

52