Главная Помехоустойчивое кодирование Та бли ца 3.2 Степени для ганкелевых циркулянтов
Многократно применяя правила умножения, задаваемые матрицами (3.5) и рис. 3.4, построим для равного 4, 5, 6, 8, 16, та&1ицы степеней (табл. 3.2), а по ним - таблицы корней (табл. 3.3). Из табл. 3.3 видно, что для ряда значений свободной переменной х не существует корней некоторых степеней. Точнее, не для всех значений х существуют корни тех степеней которые не взаимно просты с порядком х ~q~ 1. Это непосредственно вытекает из следствия упоминавшейся в § 3.1 теоремы Лагранжа о порядке подгруппы конечной группы. Можно заметить, что \fх =х при Т» = 1, где Т и ф умножаются по модулю эе = - 1. Например,Vx~=х дляхЕ GF (q == 2"), ??= ql2. Таблицы степеней и корней иллюстрируют теорему Ферма (см. § 3.1), согласно которой цдяд = эе + ]. Таблица 3.3 Корни для ганкелюых циркулянтов
= 16
fl--l; (3-7a) aa; (3.76) =a, (ЗЛв) где 76 - порядок Сц, Наша задача состоит в нахождении арифметических зависимостей между элементами множества К, удобных при вычислении произведений аЬу частных а : Ь, степеней и корней п-й степени \/а , Так, при Q>4 и использовании матриц умножения типа (3.5) всегда 2-2 - 3 и т. п. Конечно, необходимо помнить, что под "произве- .>? 5, 51 Я >> »> Ч дением , частным , степенью и корнем понимаются не результаты обычных операций над числовым множеством, а результаты специальных операций, лишь для простоты называемых "умножением", "делением" и т. п. и обозначаемых соответствующими традиционными символами, но определяемых матрицами вида (3.5), (3.6) и табл. 3.2, 3.3. Анализ матриц (3.5) показывает, что они побочной диагональю из элементов q - I разделяются на две части, причем справа от этой и„ диагонали осуществляется приведение по модулю q , т. е. вычитание числа q из суммы соответствующих (горизонтального и вертикального) элементов. Аналогично матрицы (3.6) разделяются главной диагональю из единичных элементов, над которой как бы вводится "избыток по модулю (?", т. е. к разности горизонтального и вертикального элементов добавляется число q. Можно показать [см., например, вывод формулы (3.4)], что при любых целых > 2 справедливы следующие соотношения: для операции умножения, задаваемой ганкелевыми циркулянтами типа матриц (3.5), а + b - 1, если а b <,q\ I д + Ь - q, если а b>q; (3.8) для операции деления, задаваемой теплицевыми циркулянтами типа матриц (3.6), с : b 1 + с - если с > + с - by если с<Ь, (3.9) где " + " и "-" - обычные арифметические операции над множеством целых чисел. ., Таким образом, операции умножения и деления, определяемые циркулянтами (3.5) и (3.6) над конечными множествами К, выражаются через обычные арифметические операции сложения и вычитания, которые могут быть реализованы средствами цифровой и аналого-цифровой техники. 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.0177 |