3.5. Модулярное представление линейных кодов

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

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

в котором число столбцов типа

Заметим, что матрица

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

Очевидно, что эта матрица симметрична и содержит по одному столбцу каждого возможного типа.

Теперь рассмотрим случай двоичного кода.

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

(Веса кодовых слов появляются в том же самом порядке, в каком кодовые слова расположены в матрице в равенстве 3.7.)

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

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

Строки матрицы С с присоединенным к ним вектором из одних нулей образуют группу, поскольку они составляют пространство строк матрицы М. Рассмотрим совокупность строк, содержащих нули в столбцах. Легко видеть, что они образуют подгруппу. Далее, существуют четыре смежных класса, содержащих одно и то же число элементов, именно: подгруппа, совокупность всех строк, содержащих 0 в столбце и 1 в столбце; совокупность всех строк, содержащих 1 в столбце и 0 в столбце, и, наконец, совокупность всех строк, содержащих единицы в обоих столбцах. Таким образом, одна четвертая часть всех строк, или всего 2 строк, содержат единицы одновременно в столбцах. Аналогичными рассуждениями можно доказать, что каждый столбец содержит единиц. (См. задачу 3.3.)

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

где через обозначена единичная матрица, а через У—матрица, состоящая из одних единиц. Легко проверить, что Следовательно,

откуда

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

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

Пример. Для матрица М может быть выбрана следующим образом:

(Столбцы матрицы упорядочены так же, как упорядочены двоичные числа.)

Тогда

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