1.9. ПОСТРОЕНИЕ НОВЫХ КОДОВ ИЗ ЗАДАННЫХ КОДОВ (II)

(I). Добавление общей проверки на четность. Пусть будет двоичным кодом, в котором некоторые кодовые слова имеют нечетный вес. Образуем новый код добавляя 0 в конце каждого кодового слова с четным весом и добавляя 1 в конце каждого слова с нечетным весом. Тогда обладает тем свойством, что каждое кодовое слово имеет четный вес, т. е. этот код удовлетворяет новому уравнению проверки на четность а именно уравнению общей проверки на четность.

Из (1.12) следует, что расстояние между каждой парой кодовых слов теперь четное число. Если минимальное расстояние кода было нечетным, то новое минимальное расстояние равно представляет собой -код. Этот способ

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

Если имеет проверочную матрицу то имеет проверочную матрицу

Пример. Код Добавление общей проверки на четность к коду дает [8, 4, 4] расширенный код Хэмминга с проверочной матрицей

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

где вектор -двоичное представление числа (см. (1.43)). Наконец, если произошли две ошибки, то

и декодер обнаруживает, что произошли две (или более) ошибок. Упражнения. (40). Показать код строго самодуален.

(41) Показать, что расширенный код Хэмминга единствен (в том же самом смысле, что и в упражнении (28)).

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

(42). Если добавить общую проверку на четность (т. е. сделать так, чтобы кодовые слова удовлетворяли уравнению

к троичным кодам с порождающими матрицами

то что случится с их минимальными расстояниями?

(II). Выкалывание кодовых координат. Операция, обратная расширению кода называется выкалыванием и состоит в удалении одной или более координат из каждого кодового слова. Так, например, пусть у нас имеется -код

Выкалывание последней координаты этого кода дает -код

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

(III). Код с выбрасыванием. Простейший способ получения кода с выбрасыванием состоит в следующем. Предположим, что двоичный -код содержит кодовые слова обоих весов, четного и нечетного. Тогда, как следует из упражнения (10), половина кодовых слов имеет четный вес и половина нечетный. Выбросим из кода все кодовые слова нечетного веса, и тогда получим -код. Часто (например, если нечетное).

Пример. Из [7, 4, 3]-кода выбрасыванием всех слов нечетного веса получаем -код.

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

Другими словами состоит из кодовых слов и их дополнений и является где

и d - наибольший вес кодовых слов кода .

Пример. Пополнение кода дает -код, состоящий из всех векторов длины 3.

(V). Удлинение кода путем добавления информационных символов. Обычный способ удлинения кода состоит из последовательного выполнения двух операций: пополнения кода путем добавления вектора 1 и расширения его с помощью общей проверки на четность. В результате этих операций число информационных символов увеличивается на единицу.

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

Код, дуальный к коду Хэмминга. Для иллюстрации все эти шесть операций показаны на рис. 1.11 для кода Хэмминга и на рис. 1.13 для дуального к нему кода.

Рис. 1.11. Применение конструкций к коду Хэмминга

Определение. Двоичным симплексным кодом называется код, дуальный к коду Хэмминга Из § 1.8 мы знаем, что представляет собой -код с порождающей матрицей являющейся проверочной матрицей кода Так, например, для матрица

и кодовые слова

Для кода имеем:

и кодовые слова

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

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

Симплексный код вновь появится в дальнейшем, но под другим именем: код максимальной длины, получаемый на регистре сдвига с обратной связью (см. § 3.4 и гл. 14).

Важным является также код, дуальный к расширенному коду Хэмминга, ибо он представляет собой код Рида — Маллера первого порядка (см. гл. 13). Этот код получается удлинением как описано в (V). Например, такое удлинение кода дает код, изображенный на рис. 1.14.

Рис. 1.12. Изображение кода в виде вершин тетраэдра

Рис. 1.13. Применение конструкций к симплексному коду

Рис. 1.14. (см. скан) Код №10, [8, 4, 4]-код Рида-Маллера первого порядка

Упражнение. (43). Назовем совокупность действительных векторов множеством сигналов. Определим скалярное произведение (все вычисления производятся в поле действительных чисел) и назовем число энергией вектора х. Единичные векторы имеет 1 в компоненте и 0 во всех остальных) образуют множество ортогональ

сигналов, так как Рассмотрим теперь сдвиг множества сигналов Показать, что минимум полной энергии достигается при

Множество сигналов называется симплексом (оно является непрерывным аналогом описанных выше двоичных симплексных кодов). Множество биортогональных сигналов является непрерывным аналогом кодов Рида-Маллера первого порядка