Б6. Декодирование перестановками

Пусть С — множество -выборок из поля образующих код;

Мы рассмотрели получение кодов с минимальным расстоянием удовлетворяющих некоторым линейным соот ношениям:

и

В общем случае мы можем предположить, что код получается с помощью некоторого преобразования дающего кодовые слова длины Через обозначим значение

(в десятичной системе) последовательности двоичных знаков, расположенной в информационных местах кодового слова Тогда можно записать

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

и, следовательно,

Фиксируя некоторую перестановку, дающую порядок компонент векторов пространства будем рассматривать перестановки (см. § 16)

с

Если теперь получено слово с не более чем ошибками, то могут представиться два случая:

1) в информационных местах не содержится ошибок и информация полностью восстанавливается, т. е. можно точно найти кодовое слово:

так как единственное кодовое слово, находящееся на расстоянии от полученного слова ;

2) в информационных местах имеются ошибки, полученная -выборка не совпадает с переданной тогда

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

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

Действуя, как указано в таблице (см. ниже), получаем

— искомое слово.

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

Пример. Применим изложенный метод к коду Хэмминга из § исправляющему простую ошибку. Выпишем кодовые слова в следующем порядке:

Легко проверить, что циклический сдвиг сохраняет закон

образования кода. Если при передаче кодового слова была допущена одна ошибка, а именно, было получено слово то, применяя метод настоящего параграфа, получаем

следовательно,