5. Линейные коды и линейные векторные подпространства

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

Произведением комбинации на элемент поля а называют комбинацию

(VI.5.1)

такую, что каждый ее символ удовлетворяет равенству

(VI.5.2)

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

Говорят, что система -значных комбинаций

(VI.5.3)

линейно зависима, если существует набор элементов данного поля

(VI.5.4)

такой, что

(VI.5.5)

Если же равенство (VI.5.5) не имеет места ни для одного из возможных наборов (VI.5.4), то говорят, что система (VI.5.3) линейно независима.

В курсе высшей алгебры доказываются следующие положения [21]:

1. Если система (VI.5.3) линейно независима, то и любая ее подсистема линейно независима, причем она остается линейно независимой при замене в ней любой комбинации на другую комбинацию:

(VI.5.6)

где , а — произвольные элементы поля .

2. Любая подсистема (VI.5.3), содержащая или более векторов (комбинаций), линейно зависима.

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

(VI.5.7)

Одним из базисов векторов пространства является система единичных векторов. В частности, одним из базисов исходного кода является система единичных векторов (комбинаций) вида

(VI.5.8)

Через базисные комбинации выражается любая комбинация :

(VI.5.9)

В силу того, что число всевозможных различных наборов коэффициентов в (VI.5.9) равно , число всевозможных различных комбинаций множества также равно .

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

Лемма VI.4. Множество комбинаций линейного кода является линейным подпространством пространства .

Для доказательства этого утверждения достаточно показать:

1) если комбинации и принадлежат , то их сумма также принадлежит

2) если комбинация , то и .

Справедливость обоих положений легко доказывается методом, использованным при выводе леммы VI.2.

Следствие 1 (леммы VI.4). Линейное подпространство (код ) имеет размерность , и его базисом служат комбинации, у которых информационными символами являются базисные комбинации исходного кода.

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

(VI.5.10)

где символ комбинации исходного кода — базисные комбинации , информационные символы которых образуют один из возможных базисов исходного кода, например (VI.5.8).

Базис кода наиболее просто находится для случая, когда в качестве выбираются комбинаций, у которых только один информационный символ отличен от нуля:

(VI.5.11)

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

(VI.5.12)

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

По заданной базисной матрице не представляет труда найти линейные формы кода . Для этого достаточно ее строку умножить на а затем просуммировать элементы -го столбца и выписать результат в виде линейной формы

Базисные матрицы кодов табл. VI.1 и VI.4 получаются транспонированием матриц (VI.3.2)-(VI.3.3) соответственно:

(VI.5.13)

(VI.5.14)

Умножая первую строку (VI.5.13) на вторую —на , получим

(VI.5.15)

Суммируя далее элементы каждого столбца, найдем

(VI.5.16)

что совпадает, как и следовало ожидать, с линейными формами (VI.1.6).