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



18 1 1 18 2 О 43 2 6

19 О 3 19 5 1 44 4 1

20 3 О 20 3 6 45 4 2

21 2 4 21 3 5 46 5 2

22 2 1 22 2 5 47 4 6

23 4 1 23 3 1 48 2 2

24 2 2 24 5 5 t -----

Рис. 3.2. Порождение полей Галуа характеристик 3, 5, 7 и невысоких порядков

при этом, если в (г + 1)-м разряде справа (разряде переполнения) появится О, то полученную в результате сдвига комбинацию оставить без изменения; иначе, если в указанном разряде переполнения появится 1, то отбросить ее, а к полученной комбинации добавить поразрядно по модулю 2 константу Cf из табл. 3.1.

Комментарий. Таким образом, в качестве примитивного элемента а выбирается комбинация (ООО... 010) N-2. Двоичные комбинации для Л, равных 1, 2, содержат строго по одной еди-

нице, которая последовательно смещается влево - в сторону старших разрядов, что соответствует умножению предыдущего элемента W на а. Дальнейший сдвиг влево для получения элемента N=r + 1, т.е. а, приводит к переполнению - появлению {г + 1)-го разряда. Это переполнение устраняется с помощью комбинации-корректора , определяемой заданным полиномом 7г(л:),

Процесс формирования элементов полей GF {1 ) для г = 2 ... 5 представлен на рис. 3.1.

Если характеристика р > 2, то процедура генерации элементов GF(p) отличается тем, что в разряде переполнения может появиться любой элемент из диапазона 0<i<p-" 1. В этом случае к текущей г-разрядной комбинации добавляется по модулю р поправка vCf, где умножение также выпoJШяeтcя по модулю р. Примеры генерации недвоичных полей небольших характеристик и размерностей представлены на рис. 3.2. Например, для GF(3) имеем С2 = (100)= (21); N= (100)-* (21); yV=4-* (210)-- (10) + 2 (21) - (10) -t (12) = (22), mod 3 и т. д. В технике помехоустойчивого кодирования наибольшее применение получили поля характеристики 2. Правила выполнения операций над такими полями приведены в § 3.3.

3,2. ОПЕРАЦИИ НАД КОНЕЧНЫМИ ЦИКЛИЧЕСКИМИ ГРУППАМИ

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



матриц-циркулянтов. Такие матрицы-таблицы (далее, как правило, просто матрицы) строятся по типу таблиц умножения, например, как показано на рис. 3.3.

На пересечении z-й строки и/-го столбца матрицы (рис. 3.3) располагается результат композиции д/ду; так, Д2Лз~4> 3a ~ai и т. п. Здесь использвана мультипликативная запись операции-композиции, называемой далее умножением.

Перечислим некоторые простейшие свойства операции умножения, задаваемой ганкелевой матрицей (рис. 3.3) для элементов множества К = ( fli, Д2» • • • J . Эта операция определена при всех значениях аргументов, т. е. аксиома замкнутости (см. § 3.1) выполняется. Матрица рис. 3.3 симметрична относительно главной диагонали, следовательно, данная операция коммутативна. Далее каждый элемент в любой строке и в любом столбце этой матрицы встречается ровно по одному разу. Поэтому уравнения (3.1) однозначно разрешимы относительно .v и у.

Более того, <К] * > - коммутативная (абелева) группа; однако доказательство ассохщативности операции-композиции в общем случае затруднительно (для рассматриваемой операции это будет сделано далее). В действительности же справедливо следующее более сильное утверждение.

Утверждение. Конечное множество К - [ai, • . , а] с операцией умножения, задаваемой ганкелевой циркулянтной матрицей (рис. 3.3), является конечной циклической группой порядка Ж с порождающими (примитивными) элементами Д2 или а. (Заметим, что последнее утверждение может использоваться в качестве определения цикJШЧecкoй группы.) Циклические группы будем обозначать Сц. Каждую строку (каждый столбец) матрицы рис. 3.3, отмеченную

1, 2, . . , } ,

символом Ду, г t z, . .., ae.j , можно трактовать как подстановку по отношению к самой верхней строке (самому левому столбцу):

а2 = ааг = \ -~--- = 7Г2 (л/ );

агъ а -а /

= з(й/);

\ а aia2 • а -2-1

Аналогично первая строка и первый столбец могут рассматриваться как единичные подстановки:

ai = aai = \----) = tti (д- ),

012 •••



аз . .

as ..

а\ . .

Риа 3-3. Задание операции " • " ганкелевьи циркулянтом

Т. е. 1 = айх - для любых д,- ЕА={а1,Д2.--?й}.

Подстановки тгг и тг являются циклическими (круговыми) - соответственно левой и правой. Все остальные подстановки могут быть представлены как степени циклических подстановок, например:

3 »

ТГ4; .

1 ае

J& -2

• ТГ*

-ТГ2; ТГдг

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

сомножителей: аа = , ааа = и т. п.

Согласно матрице рис. 3.3 для ганкелева циркулянта имеем

al = агйг = Дз» 1 - 2 2 " 2 = 4 i • • •

В общем случае справедливо соотношение

, если / < X ;

Ль если I

Огкуда следует, что

ае.-1

Д2 ; а

а2 а

у -1

при /Ф 1

Аналогично для степеней элемента получим



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