Линейные коды. Порождающая матрица линейного кода

 

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

.

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

Двоичным линейным кодом является любое –мерное подпространство пространства векторов длины .

Поскольку подпространство содержит кодовых слов, то есть ни что иное, как число информационных символов, переносимых кодом, а – длина кода. Наряду с обозначением кода как код, встречается и другое, в котором используется еще один его параметр – кодовое расстояние: .

Построим матрицу размерности , строками которой служат вектора :

. (6.1)

Представив информационное сообщение в виде –компонентного вектора , произвольное слово линейного кода с учетом (6.1) может быть записано в виде

. (6.2)

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

Следует особо подчеркнуть, что:

– любой линейный код содержит нулевое кодовое слово ;

– любая сумма слов линейного кода вновь дает кодовое слово, принадлежащее данному коду: если , то .

Теорема 6.3.1. Минимальное расстояние линейного кода равно наименьшему из весов ненулевых слов кода:

.

Доказательство: Согласно определению кодового расстояния и с учетом последних замечаний имеем

.

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

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

, (6.3)

где – единичная матрица, а – матрица размерности . Использование канонической порождающей матрицы (6.3) позволяет построить систематический линейный код, в котором информационные символы занимают первые позиций кодовых слов:

, (6.4)

где – проверочные символы кодового слова.