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



Для составных модулей простые поля не существуют, но для множеств мощности Q ~ р, где р YI г - простое и натуральное числа, существуют поля, называемые конечными и обозначаемые G¥{p ) - подробнее см. § 3,3.

В частности, поле GF(2) состоит из двух злементов 0, 1, над которыми заданы операции:

сложение по модулю 2 -

0+11 + 0=1; .0 + 0-1 + 1=0; умножение по модулю 2 ~

(1.35)

О- О- О 1 = 1 • 0= 0; 1-1=1.

(1.36)

Используя тождества (1,35) и (1.36), прямым перебором можно убедиться, что при а,Ь & GF (2) уравнения

X + а = b (mod 2); уа = b{ mod 2) при а Ф О

имеют решения:

X - Ь+а; у ~ b : а - Ь,

т. е. вычитание по модулю 2 совпадает со сложением по модулю 2, а деление на а Ф О ~ с умножением на 1.

Если /? - не простое число, то множество Р = -I О, 1,.. ., /? ~ 1 j мощности р с модульными операциями сложения и умножения называется модульным кольцом. Оно полем не является, потому что операция, обратная умножению, неоднозначна или даже не существует, как было видно на примере /? - 6. В любом, а не только в модульном, кольце R с двумя бинарными операциями - аддитивной (сложение) и мультипликативной (умножение), лишь для первой из них однозначно может быть определена обратная операция (вычитание). В любом кольце R справедливы соотношения (1.33а) и (1.336), если, кроме того, выполняется равенство (1.33в) для всех его элементов, то такое кольцо называется кольцом с единицей (унитальным кольцом).

Векторы и операции над ними. Назовем скалярами элементы поля GF{p), т. е. элементы из множества Р = О, 1, . . ., р - 1 , где р - простое число, а векторами - наборы длины п из скаляров, например: а ~ (n>n - i - ; b = (b, Ь„ Р . - - , bj), гдед/ e GF(p); Ь,- e GF (/?),/ = 1,2,

Вектор, все n компонент которого равны нулю, обозначается О и называется нулевым: О = (О, О,. . . , 0); здесь в скобках « нулей.

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

сумма векторов -

а + Ь== (йГи + J + 6„ I,. . . + fei); (1.37)

произведение вектора а на скаляр а

(1.38)

в формуле (1.37) использовано сложение по модулю р соответствующих компонент векторов, а в формуле (1,38) - умножение по модулю р каждой компоненты вектора а на скаляр а G GF(/?). Другими словами, покомпонентные операции в правых частях выражений (1,37) и (1.38) являются операциями поля GF (р).



в результате операций (1.37) и (1.38) также будут получены векторы длины «, над которыми вновь можно производать подобные действия; такие операции называются замкнутыми.

Введенные понятия скаляра и вектора допускают два обобщения. Во-первых, скалярами можно считать элементы не простого поля GF(p), а произвольного конечного поля gf{q - ). В этом случае вектор ~ это набор указанных скаляров; вид операций (1.37) и (1.38) не изменяется, но входящие в них покомпонентные операции над скалярами являются операциями поля GF() - подробнее такие операции рассмотрены в § 3.2 и 3.3. Далее под скалярами как элементами поля понимаются элементы поля gfiq ~ р) и, в частности, при г - 1 - поля GF (р).

Во-вторых, в качестве скаляров могут быть приняты элементы некоторого кольца с единицей, например модульного кольца r с элементами из множества р = {0, 1, ~ l} , над которыми выполняются операции по модулю р\

где р - составное число. Определение вектора как набора скаляров не изменяется.

Рассмотрим теперь произведение векторов, которое может быть определено по-разному. Выше при задании пересечения двух двоичных векторов (кодовых комбинаций) использовались их компонентные произведения - см. формулу (1.2). Аналогичная операция может быть введена для произвольных векторов.

Произведением-пересечением а * b двух векторов а, b с компонентами из некоторого поля gf{q) называется вектор, определяемый соотношением (1.2), где компонентное умножение скаляров осуществляется по правилам лоля gfiq).

Важное значение имеет следующее понятие. Пусть заданы векторы д, ь, а их компоненты-скаляры принадлежат полю gf{q); скалярным произведением а - b этих векторов называется скаляр вида

а •ь = anbn+a b +

где операции умножения и сложения скаляров являются операциями поля gv{q). Причем

аьф ьа; (аь) - (Л). (1-39)

Если д • 6 = О, то векторы а нь называются ортогональными.

Предположим, что векторы а и b ~ двоичные, а с ~ их пересечение: с = а * ь. В этом случае

а • b =

0 тогда и только тогда, когда wt(c) ~ четное число;

1 тогда и только тогда, когда wt(c) - нечетное число.

Следовательно, а • а = ов том и только том случае, если wt (а) ~ четное число. Можно также ввести следующий вариант произведения векторов. Вновь считаем, что компоненты-скаляры векторов а иь принадлежат полю gf{q).

Векторным (тензорным, прямым, или кронекеровским) произведением j ®ь векторов а и b соответственно длины тип называется вектор длины тп, получающийся при замене каждого элемента вектора д произведением д-Ь.

Например, для д = (32!) = ПО; ь= (bibi) = (01) получим:

д ® 6 = [(дзб) (агь) (аь) ] - [a-iibibo агфгъ) aibiby)] = = [ 1 • (01) 1 (01) О - (01) ] = (01 01 00);



b & а - {b2a bya) = [2 (fl32i) (*?32i)] = (ООО 110).

Таким образом, операция ® некоммутативна, но, как можно убедаться, ассоциативна.

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

Умножение матрицы а на матрицу в соответственно размеров i хп и пхт осуществляется по правилу скалярного произведения "i-я строка (первой мат рицы) на /-Й столбец (второй матрицы)в результате получается матрица с-лв размера i хт с компонентами

к = п

= S 1.2,/= 1,2,...,w. (1.40)

к - 1

Таким образом, предполагается, что число столбцов матрицы л (первого множителя) равно числу строк матрицы в (второго множителя). Иначе произвел дение ав не определено (не имеет смысла). Произведение (скалярное) матриц обладает следующими свойствами: а) ассоциативностью, т.е. Л (ВС) = (ЛВ)С, если определены произведения ав и вс; б) дистрибутивностью умножения относительно сложшия, 1, е. а {в + с) - ав +ас, если все произведения и суммы имеют смысл. Это произведение некоммутативно, т. е. ав ф в а.

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

Таким образом, векторное произведение матрицы Л = \ац \ pSi3M&p2LlXJ на матрицу в = [бд;/ ] размера kxl дает матрицу размера ( ) X (А"!), у которой элемент с = uijbji стоит на пересечении строки (i - \)к-к и столбца

(/ - l)l + /, где Строки и столбцы нумеруются, начиная с 1, слева направо и сверху вниз.

Например,

[an <i\2]

b2i b22

in bn) (flu Ьц) (Ji2 bii) (fli2 612) (n 21) (n 22) («12 b2l) (an *22)

fell bn

b2i b22

® [oil Л12] =

(bn On) {bn Л12) {bn an) (bn 12)

Фг! On) 021 On) (22 u) (*22 On)

Векторное произведение матриц обладает следующими свойствами: а) ассоциативностью, т. е. (Л ® Я) ® С = Л ® (Я ® О ; б) дистрибутивностью умножения относительно сложения, т. е. Л ® {в + с) - (Л ® Я) + (Л ® О. Это произведение некоммутативно, т. е. а & в ф в С, но справедливо следующее соотношение, связывающее векторное и скалярное произведения, если последнее существует:

(Л ® в){с® d) = (ЛО ® (во).

(1.41)

Линейные формы и линейная зависимость векторов. Составим следующее выражение иэ конечного множества v- [v„, .....векторов и ска-

ляров t О/ } :



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.029