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

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

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

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

Из сказанного видно, что при избыточном кодировании возможны два основных метода декодирования — с обнаружением ошибок и с их исправлением. Сущность метода декодирования с исправлением ошибок заключается в том, что все множество B принимаемых последовательностей длины n разбивается на M не перекрывающихся подмножеств: В₁,B₂, ..., В_м. Если принята последовательность, принадлежащая подмножеству В_i, то считается, что передавалась кодовая комбинация b_i. Естественно, что в подмножестве В_i следует включить те запрещенные комбинации b_j,при приеме которых наиболее вероятной переданной комбинацией является b_i.

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

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

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

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

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

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

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

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

Процесс исправления ошибок рассмотрим сначала для симметричного канала без памяти. В таком канале по определению, вероятность правильного приема символа 1—p не зависит от того, какой символ передается, а также от того, как приняты остальные символы. Вероятность того, что вместо переданного символа b_i- будет принят символ равнар/(т—1). Отсюда легко вывести, что вероятность получения на выходе «канала комбинации , если на вход подана комбинацияb_i

(1.41)

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

Таким образом, в симметричном канале без памяти P(bj|bi) зависит только от кодового расстояния между b_i и bj. В случаях, когда р<(т— 1)/т, что практически всегда выполняется, выражение (5.3) монотонно убывает с увеличением d(i; j). Следовательно, вероятность принять комбинацию тем больше, чем меньше ее кодовое расстояние от переданной комбинацииb_i.

Задачей декодера является принятие решения о том, какая кодовая комбинация передавалась, если принята комбинация . Разумеется, решение, принимаемое декодером, не всегда верное. Однако можно добиваться минимума вероятности ошибочного декодирования. Пусть Р (b_i | bj) — условная вероятность того, что передавалась комбинация b_i, если принята комбинация . Эту условную вероятность называютапостериорной вероятностью в отличие от безусловной априорной вероятности Р (b_i) того, что передается b_i, когда ничего еще не известно о принятой комбина­ции. Предположим, что декодер по принятой комбинации решил, что передавалась комбинацияb_k. Вероятность того, что это решение верно, очевидно, равна P(b_k|). Чтобы эта вероятность была максимально возможной, декодер должен из всех разрешенных комбинаций b_i(i=1, ..., М) выбрать ту, для которой апостериорная вероятность максимальна. Это правило декодирования по максимуму апостериорной вероятности можно записать сокращенно так:

.

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

, (1.42)

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

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

, (1.43)

а эта вероятность, как видно, в симметричном канале без памяти определяется только кодовым расстоянием между b_i и b_j. Следо­вательно, в таком канале запрещенную комбинацию b_j следует декодировать, как ту разрешенную комбинацию b_i, которая на­ходится на наименьшем расстоянии от b_j. Иначе говоря, в подмножество В_i - следует включить все те комбинации , которые ближе (в смысле Хэмминга) к, чем в любой другой разрешенной комбинации.

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

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

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

Для доказательства покажем, что в условиях теоремы (при q<.d/2) действительно переданная комбинация b_i ближе (в смысле Хэмминга) к принятой комбинации bj, нежели любая другая разрешенная комбинация. Предположим противное, т. е. что существует разрешенная комбинация b_k, для которой 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. Это противо­речие и свидетельствует о справедливости теоремы.

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

(1.44)

где q₀ — кратность гарантированно обнаруживаемых ошибок в режиме, когда ошибки только обнаруживаются; q_и — кратность гарантированно исправляемых ошибок.