Глава VIII. Простейшие линейные коды

1. Коды с d=2 и коды Хэмминга

Комбинации оптимального линейного кода с имеют значность :

(VIII.1.1)

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

Например, из теоремы VI.3 следует: для образования линейной формы, представляющей проверочный символ кода , необходимо и достаточно, чтобы в матрице порядка любая подматрица порядка имела бы ранг 1 (матрица-строка не должна содержать элементов, равных нулю). Другими словами, комбинации кода отличаются не менее чем в позициях, если

(VIII.1.2)

где для всех .

Любопытным свойством бинарных кодов (VIII.1.1) является то, что они содержат комбинаций веса . Следовательно, проверкой на четность числа единиц в принятой комбинации можно обнаружить любую ошибку нечетной кратности.

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

Линейные коды с принято называть кодами Хэмминга.

Для образования k линейных форм, представляющих проверочные символы кода Хэмминга , 3) необходимо и достаточно, чтобы в подматрице порядка любая строка содержала не менее двух отличных от нуля элементов поля и две ее любые строки были линейно независимы.

Для доказательства этого положения читателю рекомендуется использовать теорему VI1.5 и следствия 1—3 (теоремы VII.5).

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

(VIII.1.3)

Выражение (VIII.1.3) становится очевидным, если учесть следствие 1 (теоремы VII.4) и то, что число -значных комбинаций, имеющих менее двух отличных от нуля символов, равно .

Кодирующее устройство для кодов с , впрочем, как и для других групповых кодов, всегда может быть реализовано на основе линейных форм, представляющих данный код. Минимизация числа элементов такого кодера в принципе может быть проведена методами теории релейных схем. Однако особого внимания заслуживают кодирующие устройства, основанные на линейных многотактных схемах типа фильтров Хаффмена [172— 173].

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

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

Рис.VIII.1.1. Кодирующее устройство для кода (6, 3, 3).

Затем указанная операция сдвига и суммирования производится еще раз. В соответствии с этим в первой ячейке регистра памяти окажется а во второй и третьей соответственно и . Наконец, если осуществить в третий раз указанную операцию, то состояние ячеек регистра памяти окажется соответствующим комбинации кода (6, 3, 3).

Его базисная матрица имеет вид

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

Подмеченная закономерность является частным случаем общего свойства базисных матриц кодов, комбинации которых формируются с помощью устройств вида рис. (VIII.2). Условимся считать , когда ячейка

Рис. VIII.2. Кодирующее устройство для кодов с .

памяти подключена в противном случае.

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

(VIII.1.5)

Умножим столбец (VIII.1.5) на коэффициент после чего просуммируем по модулю два элементы строки. В результате найдем элемент первого столбца контрольной матрицы

(VIII.1.6)

Вычеркнем из (VIII.1.5) первый столбец и справа допишем значение :

(VIII.1.7)

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

(VIII. 1.8)

Вычеркнем в (VIII. 1.7) первый столбец и допишем справа элементы (VIII. 1.8):

(VIII. 1.9)

По аналогии с предыдущим найдем

(VIII. 1.10)

Легко заметить, что имеет место соотношение

(VIII. 1.11)

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

(VIII. 1.12)

и, во-вторых, две любые строки проверочной подматрицы были линейно независимы:

(VIII. 1.13)

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

(VIII. 1.14)

При условие (VIII. 1.12) будет иметь место, если одновременно

(VIII. 1.15)

Аналогичные ограничения на коэффициенты можно определить и для других значений i, что иногда упрощает решение задачи и сокращает объем вычислений. Допустим, что требуется определить значение коэффициентов для случая, когда и . Используя соотношения (VIII. 1.11) и учитывая, что , выпишем проверочную подматрицу кода:

(VIII. 1.16)

Упростим матрицу (VIII. 1.16), полагая и [эти коэффициенты наиболее часто встречаются в (VIII. 1.16)]

(VIII. 1.17)

Непосредственной проверкой можно убедиться, что матрица (VIII. 1.17) удовлетворяет условиям (VIII. 1.12) при (VIII. 1.13). Таким образом, окончательно имеем и . Задача решена.

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

Таблица VIII.1

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

Следует отметить, что одним из интересных и, пожалуй, первым практическим применением кодов с основанием и были так называемые коммерческие коды. Большим вкладом в дело усовершенствования подобного рода кодирования явилось создание группой чешских ученых под руководством доктора Д. Завада коммерческого кода «Unicode»[94], а также разработанного ими табличного метода построения пятизначных кодов и способов коррекции (также табличных) по правилам, не требующим специальных математических знаний.

Эти вопросы детально обсуждаются в работе [49], а также в [156—158].