Понятие о корректирующих кодах.

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

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

Пример 2.2. Для передачи сообщений, число которых равно используется трехэлементиый код . Число комбинаций, которое можио при этом получить, . Комбинации, образуемые трехэлемеитиым кодом, сведены в табл 2.1.

Из таблицы видно, что комбинация № 0 отличается от комбинации № 1 только в одиой позиции.

Следовательно, если при передаче комбинации 000 про изойдет ошибка в третьем элементе, то получим комбинацию -комбинацию № 1, т. е. произойдет ошибка, которую невозможно исправить, обнаружить

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

Поэтому хэммингово расстояние . Иначе, расстояние Хемминга определяют как вес суммы по модулю — условное обозначение суммы) этих кодовых комбинаций. Весом W кодовой комбинации называется число входящих в нее ненулевых элементов.

Перебрав все возможные пары кодовых комбинаций, можно найти минимальное значение d, которое будем обозначать в дальнейшем и называть кодовым расстоянием. Для примера . Рассмотренный в примере код является простым. Любая ошибка (даже одиночная!) при использовании такого кода приведет к тому, что переданная разрешенная кодовая комбинация перейдет в другую разрешенную кодовую комбинацию. Таким образом, простой код не способен обнаруживать и тем более исправлять ошибки и имеет

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

Пример 2.3. Алфавит передаваемых сообщений . Выберем из числа комбинаций, представленных в табл. 2.2, две. Очевидно, что ими должны быть комбинации 000, 111 или 001 и 110 и т. д. Кодовое расстояние Ошибки кратности один или два превращают любую кодовую комбинацию в запрещенную. Следовательно, максимальная кратность обнаруживаемых таким кодом ошибок равна двум

Рассматривая коды с кодовым расстоянием и т. д., можно прийти к выводу, что

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

Вывод о том, какая кодовая комбинация передавалась, делается на основании сравнения принятой запрещенной комбинации со всеми разрешенными. Принятая комбинация отождествляется с той из разрешенных, на которую она больше всего «похожа», т. е. с той, от которой она отличается меньшим числом элементов. Так, если в примере 2.3 при передаче кодовой комбинации 000 получим 001, то вынесем решение, что передавалась комбинация 000.

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

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

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

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