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



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

Справедлива следующая теорема выдающегося французского математика Ж. Лагранжа (J.L.Lagrange, 1736-1813): порядок любого элемента произвольной конечной группы, а не только циклической,

является делителем порядка Группы "ЗЕу [17,32].

Если все элементы циклической группы G могут быть представлены в виде натуральных степеней некоторого элемента PG, то такой элемент называется примитивным.

Ясно, что порождающий элемент а циклической группы всегда примитивен, но а - не единственный примитивный элемент. Примитивным всегда является также элемент а где X - порядок циклической группы. Количество примитивных элементов циклической группы порядка Ф определяется функцией ((г), которая равна количеству всех натуральных чисел, заключенных между 1 и и взаимно простых с ае . Эта функция называется функцией Эшгера и вычисляется в соответствии с выражением

П; - 1

v>(x ) = зе, 1 - - ... 1 - - = П р. {р -I),

I = 1

причем Ф представляется как составное число в виде х -Up , где

Pi - простое, а - натуральное число; / = 1, 2,. . . , х-

С другой стороны, любой элемент G К тогда и только тогда

является примитивным, когда удовлетворяются х условий Ф \,

где 1 = lpj,i = 1, 2,. . . , Х-

Один из центральных вопросов теории конечных циклических

групп, порядок которых составное число, - их разложение в прямую

сумму других циклических групп меньшего порядка [33]. Этот вопрос

будет рассмотрен в гл. 4 в связи с изложением быстрых алгоритмов

дискретных преобразований.

Простейшие примеры групп. В § 1.3 были введены модульные операции, определяемые соотношениями (1.34а) и (1.346). Представим эти операции в следующем виде:

сложение по модулю (mod)p

fl + Ь , если А + Ь <р\ а b - р, если а ЬРр,

умножение по модулю (mod)p

а О b

- <

ab , еслиа <р;

rest [ (ab) : р ], если аЬ>р,

где rest [ (ab) р] ~ остаток от деления произведения ab на р



Далее для простоты модульные операции обозначаются без кружочка, если их смысл ясен из контекста.

Построим таблицы сложения и умножения для малых

- = {0, 1,2

={0, 1,2,3} ,

modp =

2

modp =

mod р =

0 1 •

1 2 •

12 3 •

0 1 2

0 1 0

1 2 0

12 3 0

1 0 1

2 0 1

2 3 0 1

0 1 2

0 1 2

3 0 1 2

0 2 0

0 12 3

0 3 2

Любая система <К\ +> с модульным сложением - циклическая

группа и элемент 1 является порождающим (в аддитивной записи:

1, 1 + 1, 1 + 1 + 1,. . . ).

Следовательно, операция модульного сложения одрзтма:

(о, 1} , /7 = 2

-[О, 1,2, р=3

/: = (о, 1,2,з1,

0 1 2

0 12 3

0 2 1

0 3 2 1

1 0 2

10 3 2

2 1 0

2 10 3

3 2 10

Таким образом, таблицы модульного сложения являются ганкелевыми, а вычитания - теплицевыми циркулянтами. Причем для р=2 операции сложения и вычитания совпадают.

Системы КК; • > являются лишь группоидами (для элемента О нет обратного, а операция деления на О однозначно не определена). Исключим элемент О, обозначив Kq ~ О \ , тогда, если р ~ простое число, то система <Kq; • > - циклическая группа и существует операция деления; причем таблицы операций " " и - циркулянты соот-

ветственно ганкелевы и теплицевы. Если же р система <Ко; • > -

составное число, то лишь коммутативный моноид {е ~ 1). Например,

при р - 4 элемент 2 обратного не имеет, а деление на 2 либо не однозначно О : 2 е (2,о\, 2 : 2G ( 1, з\, либо не определено 1 : 2 G [ф \ , 3:2е (0).

Поле. Рассмотрим алгебры <А; +, • >, т.е. множества с парой бинарных операций (аддитивной и мультипликативной). Первую назовем "сложением", а вторую - "умножением". Если же возможно смешивание знаков "+" и с обычными арифметическими операциями, то смысл символов поясняется отдельно.



Определение. Поле - это множество не менее чем из Двух элементов, над которыми задана пара бинарных операций, называ/мых "сложением" и "умножением" и обладающих тем свойством, чуо для них существуют обратные операции: вычитание и деление (кроме деления на нуль), причем умножение дистрибутивно относительно сложения.

Итак, поле - это алгебра <К; +, •,-, : >. Следовательно, "школьные" алгебры рациональных и вещественных чисел - примеры полей (бесконечных), в то время как целые числа поля не образуют: частное {а : b двух целых чисел а и Ь) не обязательно является целым числом.

Нас интересуют конечные алгебры - поля Э. Галуа (Е. Galois, 1811-1832), содержащие конечное число элементов ={ О, 1, 2, ... , - 1 j . Однако не для любого числа элементов можно подобрать такие операции, что сисгема <А; +, • > является полем. Конечные поля, обозначаемые GF(;7 ) существуют лишь порядка (с числом элементов) , где р - простое число (характеристика поля), г ~ натуральное число (размерность поля). При г = 1 имеем простое поле GF(p) с рассмотренными выше модулярными операциями сложения и умножения. Если же р - составное число, то система </С; +, • >, где сложение и умножение - модулярные операции, полем не является: эта система образует так называемое кольцо, в котором деление даже на ненулевой элемент возможно не всегда.

В любом поле множество К всех элементов образует по операции сложения циклическую (аддитивную) группу; аналогично множество Ко ненулевых элементов образует по операции умножения циклическую (мультипликативную) группу. Поле GF {р) называется расширением поля GF(p).

Генерация элементов поля G¥(p). Конечные поля GF(p) порядка р, где характеристика р - простое число, а размерность г - натуральное число, порождаются с помощью неприводимых полиномов степени г. Особенно удобно использовать примитивные неприводимые полиномы я(х); в этом случае простое поле GF(p) может быть расширено до поля GF(p ) за счет присоединения корня а полинома я(х), т. е. с помощью сравнений по двум модулям р и я(х).

В табл. 3.1 представлены примитивные неприводимые полиномы я (л:) характеристики 2 (до степени г =10) с коэффициентами из простого поля GF(2), а также полиномы характеристик 3, 5, 7 малых степеней; там же указаны комбинации-корректоры (их назначение читатель узнает далее). Из различных вариантов предпочтение было отдано полиномам я(х) с минимальным числом ненулевых коэффициентов, а при равенстве этого числа - полиномам, имеющим ненулевые коэффициенты при меньших степенях переменной х.- Например, для р == 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.012