Главная Помехоустойчивое кодирование где сложение и умножение показателей - обычные операции над рациональными числами. Заметим, что формула (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 на р Далее для простоты модульные операции обозначаются без кружочка, если их смысл ясен из контекста. Построим таблицы сложения и умножения для малых
Любая система <К\ +> с модульным сложением - циклическая группа и элемент 1 является порождающим (в аддитивной записи: 1, 1 + 1, 1 + 1 + 1,. . . ). Следовательно, операция модульного сложения одрзтма:
Таким образом, таблицы модульного сложения являются ганкелевыми, а вычитания - теплицевыми циркулянтами. Причем для р=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.0273 |