I. ПРОИЗВЕДЕНИЕ КОДОВ И ИХ ОБОБЩЕНИЕ

18.2. ПРЯМОЕ ПРОИЗВЕДЕНИЕ КОДОВ

Пусть и 98 обозначают соответственно -линейные коды над полем GF(q). Для простоты предположим, что первые символов кода и первые символов кода являются информационными.

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

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

Рис. 18.1. Кодовые слова кода являющегося прямым произведением

Описанная конструкция называется также кронекеровским произведением кодов и является простейшей разновидностью произведения кодов. Столбцы построенной матрицы — слова кода а строки — слова кода

Пример. (1). Прямое произведение двоичного -кода с самим собой является -кодом, состоящим из 16 матриц, изображенных на рис. 18.2.

Рис. 18.2. Прямое произведение двоичного -кода с самим собой

Упражнения. (1). Проверить, что представляет собой линейный код над GF(q) с параметрами

(2). Кодовые слова могут быть также образованы сначала заполнением верхних строк, а затем заполнением всех столбцов. Показать, что это дает тот же самый код.

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

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

Упражнение. (3). Пусть порождающие матрицы кодов и соответственно. Показать, что кронекеровское произведение этих матриц (определенное в § 14.4) является порождающей матрицей кода

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

кода в виде многочлена

Если мы предположим, что то представляют собой циклические сдвиги строк и столбцов и также принадлежат коду Другими словами, код является идеалом групповой алгебры абелевой группы, порожденной элементами х и у такими, что

Предположим, что взаимно просты. Тогда согласно китайской теореме об остатках (§ 10.9) для каждой пары где существует единственное целое число в диапазоне такое, что

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

Например, если то принимает следующие значения:

Кодовое слово принимает вид

Теорема 1. Если циклические коды и то код — также циклический.

Доказательство. Как было показано выше, кодовое слово может быть представлено как где Кроме того, если то и поэтому

Следовательно, код представляет собой идеал групповой алгебры циклической группы, порожденной z.

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

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

а порождающий многочлен равен Они представляют собой кодовые слова соответственно.

Упражнения. (4). Предположим, что порождающие идемпотенты кодов Показать, что порождающий идемпотент кода получается из заменой на

(5). Предположим, что Показать, что если и — ненули кодов соответственно, то ненулей кода имеют вид где

(6). Выбрать в качестве кодов и -коды соответственно. Найти параметры, весовой спектр, порождающий идемпотент и порождающий многочлен кода

(7). При выборе отличном от код может быть также превращен в циклический. В каких случаях разные выборы приводят к разным циклическим кодам? [Указание. Показать, что для кода, рассмотренного в упражнении (6), приводят к разным результатам.]

Иногда знание того факта, что код является прямым произведением, позволяет найти его весовой спектр.

(8). (Трудное.) Пусть представляют собой

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

где определяется следующим рекуррентным соотношением: