36. Классификация корректирующих кодов. Принципы помехоустойчивого кодирования.

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

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

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

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

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

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

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

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

В теории помехоустойчивого кодирования важным является вопрос об использовании избыточности для корректирования возникающих при передаче ошибок. Здесь удобно рас смотреть блочные коды, в которых всегда имеется возможность выделить отдельные кодовые комбинации. Для равномерных кодов, которые в дальнейшем только и будут изучаться, число возможных комбинаций равно M=2ⁿ, где n — значность кода.

В обычном некорректирующем коде без избыточности, на пример, в коде Бодо, число комбинаций М выбирается равным числу сообщений алфавита источника М₀, и все комбинации используются для передачи информации. Корректирующие коды строятся так, чтобы число комбинаций М превышало число комбинаций источника М₀. Однако в этом случае лишь М₀ комбинаций из общего числа используются для передачи информации. Эти комбинации называются разрешенными, а остальные M – М₀ комбинации носят название запрещенных. На приемном конце в декодирующем устройстве известно, какие комбинации являются разрешенными и какие — запрещенными. Поэтому если переданная разрешенная комбинация в результате ошибки преобразуется в некоторую запрещенную комбинацию, то такая ошибка будет обнаружена, а при определенных условиях — исправлена. Естественно, что ошибки, приводящие к образованию другой разрешенной комбинации, не обнаруживаются.

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

Для любого кода d_y≤n. Минимальное различие между разрешенными комбинациями в данном коде называется кодовым расстоянием d

.

Рис. 7.1. Геометрическое представление разрешенных и запрещенных кодовых комбинаций

Расстояние между комбинациями A_i и A_j условно обозначено на рис. 7.1а, где показаны промежуточные комбинации, отличающиеся друг от друга одним символом В общем случае некоторая пара разрешенных комбинаций A_p1 и A_p2, разделенных кодовым расстоянием d, изображается на прямой рис. 7.1б, где точками указаны запрещенные комбинации. Для того чтобы в результате ошибки комбинация A_p1 преобразовалась в другую разрешенную комбинацию A_p2, должно исказиться d символов. При искажении меньшего числа символов комбинация перейдет в запрещенную комбинацию, и ошибка будет обнаружена. Отсюда следует, что ошибка всегда обнаруживается, если ее кратность, т. е. число искаженных символов в кодовой комбинации:

g≤d-1

Если g < d , то некоторые ошибки также обнаруживаются. Однако полной гарантии обнаружения ошибок здесь нет, так как ошибочная комбинация в этом случае может совпасть с какой-либо разрешенной комбинацией. Минимальное кодовое расстояние, при котором обнаруживаются любые одиночные ошибки, d = 2.

Процедура исправления ошибок в процессе декодирования сводится к определению переданной комбинации по известной принятой. Расстояние между переданной разрешенной комбинацией и принятой запрещенной комбинацией d₀ равно кратности ошибок g. Если ошибки в символах комбинации происходят независимо относительно друг друга, то вероятность искажения некоторых g-символов в n-значной комбинации будет равна:

где P₀ — вероятность искажения одного символа. Так как обычно P₀<<1, то вероятность многократных ошибок уменьшается с увеличением их кратности, при этом более вероятны меньшие расстояния d₀. В этих условиях исправление ошибок может производиться по следующему правилу. Если принята запрещенная комбинация, то считается переданной ближайшая разрешенная комбинация Например, пусть образовалась запрещенная комбинация A₀ (см. рис. 7.1б), тогда принимается решение, что была принята комбинация A₁. Это правило декодирования для указанного распределения ошибок является оптимальным, так как оно обеспечивает исправление максимального количества ошибок. (В общем случае оптимальное правило декодирования зависит от распределения ошибок)