Главная Помехоустойчивое кодирование



x S а,- Vi / = 1

или в развернутом виде

причем среда скаляров а-, / = 1, 2,.. ., л, могут бытъи повторяющиеся.

Выражение (1.42) называется линейной формой (линейной комбинацией)

векторов (v n - v * • е К, а скаляры а, n - i • - • > ~ ее коэффициентами. Линейная форма (1.42) является вектором длины «; она называется тривиальной, если все ее коэффициенты равны нулю, т. е. если к - нулевой вектор, и нетривиальной, если хотя бы один ее коэффициент отличен от нуля.

При варьировании коэффициентов а/ линейная форма Л. (1.42) изменяется. Все множество возможных линейных форм из векторов v, • * ♦ назы-

вается линейной оболочкой и обозначается l {v) ~ {v, n~v i * ®*

лри 0L. - vai, (х е GF(), / = 1, 2,. . . , «.

Так как скаляры е gv{q~p)y то {-\==", а линейная оболочка (1.43) заданной системы векторов v замкнута относительно сложения векторов, обратной операции - вычитания векторов и умножения вектора на скаляр.

Конечное множество v векторов называется линейно независимой системой, если линейная форма (1.42) из этих векторов тогда и только тогда равна нулевому вектору О, когда все скаляры {а„, «-р • • » одновременно равны нулю. По-другому: конечная система v векторов v, j, . . . , ij в том и только в том случае линейно независима, когда любая нетривиальная линейная форма из этих векторов не равна нулевому вектору.

Если линейная комбинация (1.42) равна О хотя бы при одном а. ф о, i - - 1, 2,.. ., л, то множество v векторов линейно зависимое.

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

Пусть задана система векторов v, j, .. ., vi, причем v„ ф 0. Такая система тогда и только тогда линейно зависима, когда хотя бы один вектор v- е \ v,

~ i • • * i} является линейной формой исходной системы векторов. Предположим, что некоторая система v векторов независима, а система, расширенная за счет присоединения вектора w, линейно зависимая. Тогда вектор w является линейной формой от векторов из системы v и эта форма едииственна.

Базис, ранг и размерность для конечных множеств векторов. Предположим, что задано некоторое конечное множество (и) векторов w длины п. Вьщелим в нем систему (подмножество) {v, r-i * • » ~ {1 " линейно

независимых векторов, которые для удобства обозначим vi, • • •. а не буквой w с индексами; естественно, векторы тоже имеют длину п. Подобная линейно независимая система v называется базисом для множества { К* }, а сами векторы Vf v ~ базисными, если каждый вектор w является линейной формой, составленной из базисных векторов v,-, / = 1, 2, ..., г. Следовательно, в линейной

форме (1.42) Х = Р*еИ/},аК = (v, .....vi) ~ линейно независимая

система из базисных векторов; в зтом случае коэффициенты ск, в форме (1-42) называются также координатами вектора w относительно базиса v.



Итак, базис для множества И/ } векторов W суть линейно независимая и непустая система F, являющаяся подмножеством {и/}, причем такая, что все векторы W представляются в виде линейных форм от (базисных) векторов этой системы V.

Непустое конечное множество { \] векторов, в котором не все векторы нулевые, всегда обладает хотя бы одним базисом, причем число базисных векторов во всех базисах одинаково.

Мы знаем, что из конечного множества {w\ векторов W, не совпадающего с линейной оболочкой lw} можно скомбинировать все векторы, образующие такую оболочку. В свою очередь каждый вектор W выражается через базисные векторы и, у . .., 11- Очевидно, что с помощью этих же базисных векторов представляются и все векторы из линейной оболочки l (К}. Таким образом, количества базисных векторов, требуюидосся для представления всех векторов из множества (К* } и из линейной оболочки L К*}, одинаковы, но называть их принято по-разному.

Число базисных векторов, входящих в базис для некоторого конечного множества не совпадающего со своей линейной оболочкой, называется рангом (rank) этого множества и обозначается rank { w].

Число базисных векторов, входящих в базис для линейной оболочки L{w}, образованной из векторов множества И}, называется размерностью (dim) линейной оболочки и обозначается dimi ( W]. Ясно, что rank { W ] = dim/. { }.

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

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

Векторное, или линейное, пространство над множеством скаляров - это множество векторов одинаковой длины, компонентами которых являются такие скаляры, что покомпонентные операции над ними допускают сл9жение векторов и умножение вектора на скаляр наподобие операций (1.37) и (1.38).

В наиболее общем случае скаляры являются элементами кольца с единицей, например модульного кольца R\ когда операции сложения и умножения выполняются по модулю р над элементами множества Я = {0, 1,.. ., р - l} , где/? -составное число.

в качестве скаляров можно выбрать также элементы конечного поля GFiq = ~ р ), т. е. элементы множества К = {о, 1, -. . , Эй}, где эе= - 1, с операциями сложения и умножения, выполняемыми по правила... поля GViq) ~ см. § 3.2 и 3.3. Скалярами, в частности, могут быть элементы простого поля GF(/?), т. е. элементы множества Р = О, 1, .. . , р - l} с операциями их сложения и умножения по модулю р, где р - простое число.

в соответствии со сказанным векторные гфостранства определяются над кольцами (с единицей) и над полями. Так как ранее мы определили модульные операции, то здесь можно дать точное определение векторных пространств лишь над модульными кольцами и простыми полями. Для этого достаточно в приведенном выше определении указать тип скаляров и уточнить правила выполнения операций над ними. Читатель без труда сделает это самостоятельно. Далее рассматриваются только векторные пространства над конечными полями GF(q = p), в том числе над простыми полями GF(p). Особое внимание уделяется двоичным



ПОЛЯМ GF(2), наиболее широко используемым при построении современных систем помехоустойчивого кодирования.

Предположим вначале, что векторное тфостранство состоит из всех возможных векторов W длины п. Такое **полное* векторное пространство обозначается

и называется л-мерным (конечномерным) или векторным пространством размерности п. Это объясняется тем, что dim = л, т. е. что число базисных векторов в любом базисе пространства всегда равно п. Более того, любая система из п линейно независимых векторов является базисом л-мерного векторного пространства

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

е„ = (100. . .0); = (010. . . 0); . . - ; 2 = (О - . . 010);

ei- (0.-.01). (1.44)

С другой стороны, в пространстве никакое множество нз т < п векторов не является его базисом, а любое множество из т > п векторов обязательно линейно зависимо.

Конечные поля, как "полные** векторные пространства, и их расширения. Полагая в форме (1.42) п = г, = е,-, где i - 1, 2, а е- - единичные век-

торы, которые определяются равенствами (1.44), и задавая скалярам а.- всевоз-можные значения из простого поля GF(p), можно получить все q = р векторов \ пространства , совпадающих с элементами поля G{q), Таким образом, конечное поле GF( = /?) может трактоваться как "полное" векторное пространство размерности г над полем GF(/?), а система из г единичных векторов является

базисом также и для поля GF(р ).

В свою очередь, поле GFiq - p) можно еще более расширить, например, до поля GFiq)y где q - р, если перейти к векторному пространству JV" размерности п над полем GV{q). Для этого: 1) составляют векторы W - (w, n-v • • wx) длины п из элементов поля GV{p) ~ наборов длины /*, принимаемых уже за скаляры и образованных из элементов {о, \, . . . ,р - l) простого поля GV{p); 2) вводят операции над векторами W, аналогичные операциям (1.37) и (1.38) с той лишь разницей, что компонентные операции должны выполняться по правилам поля GF(p). Следовательно, поле GF ((7") является "полным", т.е. п-мерным, векторным пространством (размерности п) над полем GF( = р), где р - простое число.

Указанный процесс расишрения лоля и векторного пространства, естественно, может быть продолжен. Важно подчеркнуть следующее. Элементами любого конечного поля GF(z), где z - степень простого числа, а / - натуральное число, являются все возможные векторы (комбинации) длины/, образованные из скаляров множества {о, 1, . . . , z - .

Аналогично "полное", /-мерное, векторное пространство над полем GF(r) образовано из всех возможных векторов длины /, составленных иэ элементов поля GF(z) как из скаляров.

Линейные подпространства и "иадпространства". В отличие от конечных полей, которые всегда являются "полными" (в указанном выше смысле) векторными пространствами, существуют и "неполные" векторные пространства, содержащие не все векторы заданной длины.

Выберем некоторое подмножество { С/ ] векторов if длины п в "полном"



0 1 2 3 4 5 6 7 [8] 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94


0.0125