векторном пространстве размерности п над полем скаляров GF( ~ ) таким образом, чтобы сумма векторов U-y и u2 и произведение Ua вектора I/ на скаляр а е GF((7) вновь принадлежали этому подмножеству [l/Y Такое подмножество называется линейным подпространством.

Замечание. "Полное" векторное пространство по отношению к своему любому подпространству является как бы надгфостранством. Однако термин "иадпространство" мы резервируем для обозначения иного понятия.

Обозначим размерность подпространства через к. Линейное подпространство \ и) векторного пространства само является векторным пространством размерности Л, так как, по определению, Uy + u2 u) иС/ае{с/}. Итак, по условию {.С/} интуитивно ясно, что к < п. Действительно, мощность подпространства меньше мощности пространства W". Базис для И" содержит

п базисных векторов, всевозможные линейные комбинации из которых дают все векторы W е W. Следовательно, для формирования меньшего числа векторов из подпространства {u} требуется меньше базисных векторов, т. е. А; < п.

Однако определение размерности к произвольного подпространства u] с с ~ весьма сложная задача Практически удобнее осуществить не переход "полное" пространство подпространство, а в некотором смысле противоположный переход: "полное" пространство "иадпространство". По существу такой переход мы уже осуществляли в начале предыдущего параграфа на инженерном языке: сообщение из к информационных символов -> избыточное кодовое слово из п - к + т символов, например, из к информационных и т проверочных символов.

Итак, пусть над полем GFiq = р*), где риг- простое и натуральное числа, задано "полное" А:-мерное векторное пространство Qj состоящее из всевозможных векторов Q = {Qj j, • .., Qy) длины к, Qf G GF(), г = 0, 1, 2,.. . , ~ 1. Таких векторов существует всего штук. Ясно, что эти векторы могут быть сообщениями, образованными из информационных символов Qf Qk-v • •

Построим новые векторы U (кодовые слова) длины л > Л:, компоненты которых являются некоторыми линейными формами типа (1.42)

i = к

"/ iiV / = 1, 2, . - . , л.

(1.45)

в частности, в кодовое слово U сообщение Q может входить в неизменном виде; тогда к к информационным символам Qf добавляются т ~ к дополнительных (проверочных) символов, определяемых как линейные формы (1.45) для/ ~к+1ук + 2...,п - к+т.

Множество {с/] всех векторов - кодовых слов I/, полученных указанным способом, называется линейным "надпространством"; оно состоит из векторов длины п.

Размерность такого "иадпространства" равна Л:, так как любое слово U определяется через к символов Q. Следователшо, несмотря на то, что длина слов U равна л, размерность к линейного "надпространства" меньше п.

Так как сумма двух линейных форм (1.45) Uy + u2 и произведение На, где 0L е GF(), являются линейными формами, то над множеством векторов (с/}

можно ввести операции сложения векторов и умножейия вектора на скаляр а. Поэтому линейное "иадпространство" [ U], получаемое из "полного" А-мерного

векторного пространства за счет перехода Q U, сопровождающегося 30

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

Итак, векторное пространство { f/}, или линейная оболочка, порождено к векторами f/, k-v * 1 длины п; оно является "надпространством" по отношению к "полному" Л-мерному векторному пространству q, состоящему нз всех векторов q = {qfc* qk-v * * длины к. С другой стороны, оно является подпространством по отношению к "полному" векторному пространству размерности л, образованному Иэ всех векторов u длины п.

Для того чтобы терминология была абсолютно корректной (термин "над-пространство" можно было взять без кавычек), следует выравнять длины у векторов q к и. Это достигается формальным приписыванием т нулевых компонент к вектору q = {qff., j, .... q\). Обозначим такие векторы (0), а их множество - {(00)} . Очевидно, справедлива цепочка включений

[«20)1 С {и\

где все векторы имеют длину п.

Как уже отмечалось, множество векторов { f/], а следовательно, надпро-странство по отношению к {(О)] , является линейным блоковым кодом. Компоненты Uj могут быть связаны с информационными символами Qj не формулой (1.45), а произвольной нелинейной зависимостью. В этом случае множество \u\ назьшается нелинейным блоковым кодом. Но и в линейном, нв нелинейном вариантах мощности множеств кодовых слов } и сообщений { } совпадают:

Более подробно с математическим аппаратом, изложенным в этом параграфе, можно ознакомиться по книгам [32, 33, 35]. Необходимые сведения приведены также в работах по теории кодирования [8, 11, 36, 40, 43].

Порождающая матрица как базис линейного блокового кода. Выше мы установили, что множество {U\ векторов длины п>к,т. е. линейный блоковый код, является /:-мерным векторным пространством над некоторым конечным полем. Любой базис такого пространства должен состоять точно из к базисных векторов длины п; обозначим их i,

2» •. • > )t, где gf = gi2, • • > gik)> / = 1, 2, ..., Представим всю совокупность базисных векторов в виде матрицы

Матрица G называется линейного блокового кода, щению е = {Qf, Q 1, . дение

U = QG.

порождающей или генераторной матрицей Кодовое слово соответствующее сооб-• , Qx)-, находится как скалярное произве-

(1.47)

Здесь u- вектор-строка. Кодовое слово в виде вектора-столбца находится как скалярное произведение, вытекающее из соотношений (1.39) и (1.47):

(1.48)

Так как G = {gi, g2, • • •, g/) - базис, то система базисных векторов линейно независима; ее всегда можно привести к следующей стандартной систематической форме:

1 О О 1

4 «

« « «

1 I sk,k+i

• 4

sin s2n

[ek[a], (1.49)

где разделительная вертикальная штриховая линия введена для наглядности и имеет лишь смысл приписывания правой части матрицы к ее левой части; - единичная матрица порядка к, а символом а обозначена правая часть матрицы g. (Указанное приведение основано на алгоритме Гаусса [33].)

Подставляя в соотношение (1.47) матрицу g (1.49), получим кодовое слово и, в которое информационные символы qj, • • • » Gi входят в неизменном виде:

(1.50)

а проверочные символы р,-, / = 1, 2, ..., ш (т =п - к), определяются как линейные формы от информационных символов:

/ = к

2 q

к-/ + 1

s]i -qku q.

Вся совокупность кодовых слов вида (1.50) называется систематическим линейным кодом.

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

а b с z а b

У z x yj

Порождающая матрица-циркулянт всегда может быть представлена в виде: