6.2. Векторное пространство над конечными полями.

Пусть – конечное поле, элементы которого будем называть скалярами. Тогда

Векторным пространством над полемназывается множество элементов (векторов), замкнутое относительно двух операций: сложения векторов и умножения вектора на скаляр, обозначаемых привычными символами «+» и «•», т.е. если , то.

Операции сложения и умножения удовлетворяют следующим аксиомам:

1. Сложение коммутативно и ассоциативно:

;

2. Существует нулевой (нейтральный) вектор по сложению, не изменяющий любой вектор, сложенный с ним:

;

3. Для любого вектора существует единственный противоположный (обратный) вектор такой, что:

;

4. Умножение на скаляр ассоциативно:

;

5. Умножение любого вектора на единичный скаляр (всегда существующий в ) не меняет его значения:

;

6. Выполняется дистрибутивный закон

.

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

и ,

где сложение и умножение скаляров осуществляется в соответствии с правилами поля . Пространство такого типа может содержать довекторов. В двоичном пространствемаксимальное число векторов не превосходит величиныи согласно правилам поля

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

,

где все – скалярные коэффициенты. Напротив, если ни один из векторовне является линейной комбинацией других, то вектора называютсялинейно независимыми.

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

,

где – компоненты или координатыв базисе, а само выше приведенное соотношение называют представлениемв базисе.

Если в векторном пространстве существует подмножество, являющееся пространством над полемс такими же операциями сложения векторов и умножения на скаляр, тоназываетсяподпространством .

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

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

.

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

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

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

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

. (6.1)

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

. (6.2)

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

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

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

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

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

.

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

.

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

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

, (6.3)

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

, (6.4)

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