Содержание к диссертации
Введение
ГЛАВА 1. Вспомогательные сведения из теории алгебраических полей 13
1.1. Рекуррентные функции в конечных полях 13
1.1.1. Некоторые свойства показательных и рекуррентных функций в конечных полях 14
1.1.2. Тригонометрические суммы и суммы характеров с показательными функциями 16
1.2. Канонические системы счисления в квадратичных полях.: 22
1.2.1. Классификация канонических систем счисления 23
1.2.2. Представление данных в канонических системах счисления 28
ГЛАВА 2. Одномерные дискретные преобразования с шумоподобным базисом 34
2.1. М -преобразования 34
2.1.1. Шумоподобные базисы с равномерным распределением значений 35
2.1.2. Шумоподобные базисы с полиномиальным законом распределения значений 39
2.1.3. Специальный случай: редуцированные базисы, порожденные показательной функцией в конечном поле 49
2.2. Статистические свойства значений базисных функций
М -преобразований 54
2.2.1. Проверка равномерности и независимости, следующих друг за другом пар 54
2.2.2. Проверка комбинаций (Покер-тест) 55
ГЛАВА 3. Двумерные преобразования с шумоподобным базисом 63
3.1. Синтез базисов двумерных шумоподобных преобразований 63
3.2. Хаотичность последовательности значений базисных функций 72
3.3. Быстрые алгоритмы М-преобразований 76
ГЛАВА 4. Описание алгоритмического обеспечения и экспериментальных результатов 77
4.1. Алгоритмы и программы определения параметров М -преобразований 77
4.1.1. Алгоритм определения характеристик квадратичных полей, в которых существуют КСС 78
4.1.2. Алгоритм представления целых чисел в канонических системах счисления 84
4.1.3. Алгоритм генерации "фундаментальных" областей для квадратичных полей, в которых существуют КСС 86
4.1.4. Алгоритм нумерации элементов "фундаментальной" области 91
4.1.5. Алгоритм нумерации элементов периодического ограничения "фундаментальной" области 92
4.1.6. Алгоритм синтеза базисных функций двумерных
М -преобразований 95
4.2. Корреляционные свойства поля ошибок 97
Заключение 101
Литература
- Тригонометрические суммы и суммы характеров с показательными функциями
- Шумоподобные базисы с равномерным распределением значений
- Хаотичность последовательности значений базисных функций
- Алгоритм представления целых чисел в канонических системах счисления
Введение к работе
Целью диссертационной работы является разработка и исследование нового класса дискретных ортогональных преобразований, базисные функции которых имеют "шумоподобную" структуру.
Актуальность темы. В составе алгоритмического обеспечения компьютерных систем обработки сигналов и изображений одно из центральных мест занимают алгоритмы дискретных ортогональных преобразований (ДОП). Историю систематического использования методов дискретного спектрального анализа сигналов принято отсчитывать с 1965 г., когда Кули и Тьюки опубликовали свой быстрый алгоритм вычисления дискретного преобразования Фурье (ДПФ), хотя ранее Гуд (1960 г.) и Томас (1963 г.) опубликовали в практически незамеченных современниками работах свои быстрые алгоритмы ДПФ, базирующиеся на несколько ином подходе. За время, прошедшее с первых публикаций, дискретный спектральный анализ стал одним из основных средств решения задач цифровой обработки сигналов, распознавания образов, машинного зрения, компьютерной оптики и т.д.
Разработке различных аспектов теории и применения дискретного спектрального анализа с использованием различных ДОП посвящено большое количество публикаций как у нас в стране, так и за рубежом. Значительный вклад в развитие общей теории ДОП внесли С.С. Агаян, Н.Н. Айзенберг, В.А. Власенко, A.M. Крот, В.Г. Лабунец, A.M. Трахтман, Л.П. Ярославский, Р. Агарвал, Ш. Виноград, Г. Нуссбаумер, Ч. Рейдер и др. Высокоэффективные алгоритмы конкретных преобразований, адаптированные к характеристикам применяемых вычислительных средств разработаны A.M. Григоряном, И.Е. Капориным, Е.Е. Тыртышниковым и др.
В настоящее время теория ДОП развивается, в частности, в следующих направлениях:
• синтез параметрических семейств новых ортогональных базисов со структурой быстрых алгоритмов, инвариантной по отношению к той или иной концепции синтеза таких алгоритмов;
• разработка новых конкретных алгоритмов ДОП, обладающих повышенной точностью и/или быстродействием, адекватных по структуре вычислений последним разработкам в области специализированных процессоров и характеристикам каналов передачи информации.
Именно последний этот аспект теории ДОП - разработка, синтез и исследование ДОП, адекватных особенностям реальных или целенаправленно созданных каналов передачи информации, представляется до сих пор мало исследованным, хотя широкое распространение методов Т дискретного спектрального анализа в разнообразных задачах передачи и обработки информации делает эту проблему весьма актуальной.
Перечисленные задачи определяют структуру работы и содержание отдельных глав.
Краткое содержание диссертации. Диссертационная работа, содержащая 127 стр., состоит из введения, четырех глав, заключения, списка использованной литературы, составляющего 121 наименование и 2 приложений объемом 16 страниц.
В первой главе представлены необходимые сведения из теории алгебраических полей. Рассматриваются некоторые свойства показательных и рекуррентных функций в конечных полях, тригонометрические суммы и суммы характеров с показательными функциями. Эта глава имеет вспомогательный характер, не содержит новых результатов и включена в диссертационную работу для замкнутости изложения и удобства ссылок.
Во второй главе рассматриваются методы синтеза шумоподобных базисов с заданным законом распределения значений базисных функций (равномерным или полиномиальным). Основными результатами второй главы являются две теоремы. Рассматривая основную идею Граллерта [89] -случай базисных функций, принимающих случайным образом два значения, доказывается общая теорема (теорема 2.1) о существовании базисных функций принимающих q различных значений, а также метод эффективного вычисления констант AQ и X гарантирующих ортогональность базисных функций. Также доказывается аналогичная теорема (теорема 2.2) о синтезе базисных функций значения, которых распределены не равномерно, а по полиноминальному закону. Таким образом, получен общий результат, относящийся к синтезу одномерных М -преобразований, а также исследован вопрос о статистических зависимостях комбинаций значений базисных функций, т.е. фактически тестирование последовательностей значений базисных функций как равномерно распределенных последовательностей по отношению к неким тестам.
В третьей главе рассматривается псевдослучайный метод нумерации входных пикселей изображения и спектральных компонент М-преобразований основанных на теории канонических систем счисления в квадратичных полях. Разрабатывается алгоритм псевдослучайной нумерации, и вводится определение двумерного ортогонального преобразования (определение 3.1). Отметим, что свойства базисных функций, полученных этим построением, удовлетворяют определению хаотического отображения метрического пространства. На основе этого доказывается теорема (теорема 3.1), которая характеризует в некоторой степени "независимость" значений базисных функций.
На основе синтезированных одномерных дискретных ортогональных преобразований с шумоподобными базисами синтезируются двумерные преобразования с "хаотическими базисами", согласованные с псевдослучайной разверткой (нумерацией) массива пикселей входного и выходного изображений.
В итоге приводятся экспериментальные результаты, которые, в некотором смысле, показывают эффективность полученного преобразования вследствие некоррелированности поля ошибок восстановленного изображения.
В четвертой главе описывается разработанное программное обеспечение для определения параметров обобщенных одномерных М— преобразований и двумерных хаотических преобразований.
Методы исследований. В диссертационной работе используются методы современной алгебры и теории чисел: теория конечных полей, теория полей алгебраических чисел и канонических систем счисления в алгебраических структурах, а также методы цифровой обработки сигналов и методы арифметического моделирования случайных процессов.
Научная новизна работы» В диссертационной работе получены следующие новые научные результаты:
1. Синтезированы одномерные дискретные ортогональные преобразования, базисные функции которых принимают q различных значений с равными частотами (q - степень простого числа р).
2. Синтезированы одномерные дискретные ортогональные преобразования, базисные функции которых принимают "случайным образом" значения в соответствии с полиномиальным законом распределения.
3. На основе синтезированных одномерных дискретных ортогональных преобразований с шумоподобными базисами синтезированы двумерные преобразования с базисами, согласованные с псевдослучайной разверткой (нумерацией) массива пикселей входного и выходного изображений.
Практическая ценность работы. Практическая значимость работы состоит в том, что разработанные в ней методы непосредственно направлены на решение практических задач и, в частности:
• создание программно-алгоритмических комплексов перспективных систем адаптивной обработки и анализа многомерной цифровой информации;
• пополнение банка данных дискретных ортогональных преобразований.
Апробация работы. Основные результаты диссертационной работы докладывались на следующих научных конференциях:
1. ХІІ-я Всероссийская конференция "Математическое программирование и приложения", (г. Екатеринбург, 2003);
2. Международная научная конференция "Интеллектуализация обработки информации ИОИ-2004", (Крым, г. Алушта, 2004);
3. ХИ-ая Всероссийская школа-коллоквиум по стохастическим методам и VI-ой симпозиум по прикладной и промышленной математике (осенняя открытая сессия), (г. Сочи-Дагомыс, 2005);
4. ХІІ-ая Всероссийская конференция "Математические методы распознавания образов", (г. Москва, 2005).
5. The 4th International Workshop on Security In Information Systems (WOSIS-2006), (Cyprus, 2006).
Публикации. По теме диссертации опубликовано 8 работ. Работы [11-13] выполнены автором единолично, остальные работы [7-Ю], [72] написаны в соавторстве. На защиту выносятся только результаты, полученные лично соискателем. В диссертации ссылки на работы автора помечены звездочкой.
Тригонометрические суммы и суммы характеров с показательными функциями
Метод тригонометрических сумм является одним из основных в аналитической теории чисел. Нам потребуются его простейшие версии, базирующиеся на элементарном свойстве комплексных корней со из единицы i(m=l): JV-1 Z л=0 (йт= і па -=0, при а 0 (mod т); т, при а=0 (mod т).
Таким образом, функция W—E (1-8) может использоваться как индикатор принадлежности целых чисел к заданному множеству. Пример 1.1. Пусть Ат=(0,1,.-.,m-l)cZ, 3cAm, у(п) =Ат, л=0,1,...,Г-1. Тогда при изменении аргумента п в указанных пределах, количество членов последовательности у{р), попавших во множество 3 равно значению (тригонометрической) суммы 2ni(y(n)-b)k j Т-\ т-\ (1.9) т -ЕЕЕехр тп=0ЬеЗк=0
Поэтому задача сводится к вычислению (или оценке) суммы (1.9), которая в свою очередь может быть тем эффективнее вычислена, чем большая арифметическая информация о специфике последовательности у(п) априорно известна.
Аналогом экспоненциальной суммы (1.8), как "индикатора" (1.7) принадлежности элемента поля GF(p) к заданному множеству в случае поля GFI ps ], служит сумма характеров. Определение 1.3. Пусть Oij) есть нетривиальный гомоморфизм аддитивной группы поля GFI/ 5) в группу комплексных корней степени р из единицы. Такой гомоморфизм называется неглавным характером аддитивной группы поля GFI/?"5J. Перечислим основные свойства аддитивных характеров конечного поля. Лемма 1.2. а) Произвольный характер Q=Qb имеет вид: J2niyjbj Оь(Г)=Пехр %j, (1-Ю) где у.- - компоненты представления элемента Y в базисе поля GFI//) над GF(/?), а вектор b=( ,...,bs) однозначно определяется значениями характера на элементах базиса. б) Множество характеров образует мультипликативную группу с нейтральным элементом - главным характером Q=Q0, где вектор 9=(0,...,0) соответствует нулевому элементу 9 поля GFl/?5). в) Мультипликативный сдвиг аргумента Уі- Г ( 9) индуцирует автоморфизм группы характеров. г) Для неглавного характера Q=Qb справедливо равенство 0, при A=Q; S &{АХ)= ps, при A&Q.
Из перечисленных свойств характеров следует, что теория рекуррентных функций порядка s над полем GF(/?), в некотором смысле, "изоморфна" теории показательных функций в поле GFI/?5]. Формальное утверждение, уточняющие этот смысл сформулировано в виде леммы. Лемма 1.3. Для произвольной рекуррентной функции y(n)=aiy(n-l)+...+asy(n-s) (mod р) с ненулевыми начальными значениями Y=(.y(l)v. .,y(s)) существуют такой неглавный характер Q=Qb аддитивной группы поля GFI;/] и такой элемент XeGFJ J, что при всех neZ справедливо равенство exp 2niy(n) =пъ(х"). (1.11) Доказательство. Несмотря на то, что утверждение леммы неявно следует из теоремы главы 8 монографии [26], мы приводим прямое доказательство.
Пусть QNd\ есть квадратичное поле над Q : QUd)=iz=a+by[d; a,beO\, d - свободное от квадратов целое число. Если d>0, то квадратичное поле (или расширение) QNd) называется вещественным, если d<0 - то мнимым. Если норма Norm(z)={a+bJd^{a-b^/d>j=a2 -db2 eZ, элемента z=a+b4deQ\4d\ и его след Тг(г)=[а+Ь^+(а-Ь^=2аег есть целые числа, то элемент z называется (квадратичным) целым элементом поля Q(4d\. Обозначим через SNd) кольцо целых элементов поля QUfd).
В зависимости от вычета числа d (mod 4) кольцо S(v^) имеет различную структуру: sUd)=iz=a+byfd; a,beZ)=zUd) при d=2,3 (mod 4); s(Vrf)= =^ у2 ; a,beZ\ a=b (mod 2) при d=l (mod 4). * г 23
Определение 1.4. Квадратичное целое число a=A+B^Jd называется основанием канонической системы счисления в кольце целых поля Q(yfd), ф если каждый целый элемент z поля QNdj может быть единственным образом представлен в форме конечной суммы z=^ZjaJ, zyGN={0,l,...,|Norm(a)|-l}. (1.21)
Пара {a,N} называется канонической системой счисления (КСС) в кольце SUfd) целых элементов поля QNd).
Шумоподобные базисы с равномерным распределением значений
Рассмотрим задачу построения обобщенного М -преобразования, базисные функции которого принимают к различных значений А\,...,Ак с заданными частотами. Введем некоторые ограничения для этих частот. Пусть р - простое число, (2.8) П =—, -УПС =—; П +.. Лгк =1. Р Р Пусть далее щ,..., - частоты, с которыми значения А\,...,Ак встречаются в полном периоде базисной функции Нт{п).
Теорема 2.2. Существует семейство базисных функций Нт(п), обладающее следующими свойствами: а) функции Нт{п) образуют ортонормированное семейство; Т-\ Нт(п}Нк(п)=0, при тФк\ 1л=0 б) для частот ri,...,r] справедливы равенства (2.9) %=-, при t=\\ р -1 р -\ S rt——, при ЇФ\. (2.10)
Доказательство. Докажем утверждение (а). Пусть ф(«) - есть т последовательность, с периодом T=ps-l, то есть, удовлетворяющая рекуррентному соотношению порядка s в конечном поле GF(p) из р элементов. Пусть A O . -lJcGF ), kx={ax,ax+\,...,a2+ax-]\c.G?(p), и так далее.
Заменим значения (р(и) числамиАх,...,А , по следующему правилу: если значение последовательности ф(л) попадает во множество А,-, то 2я// положим Ho(n)=H(n)=Aj. Покажем, что при (о=е р справедливо равенство: Ч»)=Іі- I I coW"b)«/. (2Л 1} Действительно, внутренняя сумма в (2.11) отлична от нуля и равна р только при ф(«)єАj. Положим далее Нт(п)=Н0(т+п) (2.12) и покажем, что существуют такие числа АХ,...,А , что для функции Hm(ri) выполняются условия ортогональности (2.9).
Так как функции Нт(п) получаются из функции Н$(п) циклическим сдвигом, то левая часть первого уравнения системы (2.9) зависит только от разности (т-к), поэтому достаточно рассмотреть случай m=0, к О (mod Г).
Подставляя в первое уравнение системы (2.9) выражения для Н${п), Н п) из (2.11) и (2.12), получаем Таким образом, задача сводится к нахождению количества значений m-последовательности ф(и), попадающих в интервал А,, когда п пробегает полный период, равный Т. Пусть Nx - количество значений т последовательности ф(л) равных х на полном периоде T=ps-\. По свойству т -последовательностей имеем Nx= р -1, при х=0; ps , при дг О. И, окончательно, с учетом (2.35) и (2.36), получаем частоты, с которыми значения ,..., встречаются на полном периоде последовательности значений базисных функций: Поэтому Gt= axps !-1, при ґ=1; (2.36) а,/?" , при ІФ0.
В частном случае при г=\ линейная рекуррентная последовательность (1.1) есть показательная функция в простом конечном поле GF(/?): ф(и)= р(0)и (mod р). (2.37) Такая последовательность имеет максимальный период при условии, что g является примитивным (первообразным) корнем по модулю р. Рассмотрим метод построения базисных функций преобразования (2.1), принимающих два различных значения, основанный на "повторной редукции" по (mod 2) последовательности значений функции gn (mod р). Более точно, пусть ф(«) наименьший неотрицательный вычет по модулю р функции q (n)=gn. Тогда ф(и)є{0,1,...,/?-і}. Положим hQ(n)=A, ф(и) mod 2=0; «1ъ(п)=В, ф(«) mod 2=1; (2.38) K{n)=k){m+n).
Как и ранее, значения А и В могут быть найдены из условия ортонормированности базисных функций: WV (2.39) /2=0 Так как функции /. получаются друг из друга циклическим сдвигом, то сумма (2.39) зависит только (u-vj. Таким образом, для нахождения значений А и В достаточно рассмотреть случай v=0: AM (huAhZhuMMnHuO- (2.40) При и=0 соотношение (2.40) примет вид: i42-So+52-Si=l, (2.41) где SQ - количество четных значений последовательности ср(«), a S\ -количество нечетных значений последовательности ф"(«). Поскольку каждое значение встречается только один раз на полном периоде последовательности (ф(«)}, равном N=p-1, то количество четных и нечетных значений одинаково: SQ=S\=—(P-1) . Тогда из (2.41) следует А2+В2=—, (2.42) р-\ то есть, первое уравнение системы для определения параметров А и В.
Хаотичность последовательности значений базисных функций
Следуя [79-80], под хаотическим отображением метрического пространства (Х,Э) будем понимать отображение /:Х-»Х, для которого выполняются следующие условия.
1. Для любого открытого множества t/cX, любой точки хеХ и некоторого 8 0 существуют целое число л 0 и yeU такие что д\/ (х),/ (у)\ Ь (существенная зависимость от начальных условий).
2. Для любой пары открытых множеств U,VczX существует такое целое п 0, что (транзитивность отображения).
3. В любой окрестности любой точки пространства X существует, по крайней мере одна периодическая точка (плотность периодических точек).
Рассмотрим пространство Х=(К j , (l \i r) с расстоянием Хэмминга: д(х,у)=д{і х1,.. .,хц),(я,.. .,у =сагс1(т:хх ух). Все точки пространства X, кроме 0=(0,...,0), являются членами последовательности Y/1. Пусть отображение /:Х- Х определено посредством /IY H Y J. Из леммы 1.1 и для т -последовательностей легко следует выполнимость условий 1-3 хаотичности отображения /. Мы докажем утверждения, количественно характеризующие эту хаотичность последовательностей Yj1. Теорема 3.1. Пусть
Duv=card\n:hu(n) hv(n) , 0 w iV-l}. Тогда существует Э=0 = неравенство м I я) 1 , такое, что при u v справедливо DUV QN. (3.10)
Доказательство. Ограничимся подробным доказательством для q=p. Так как функции hm{n) получаются из функции ho(n) циклическим сдвигом, то неравенство (ЗЛО) достаточно доказать для пары функций Ь${п) и hm(n) при m=l,...,N-l. Пусть
Mmjc=card\n\hQ{n)=hm{n)=k\ 0 n N-l}, тогда при кф$ имеем:
Одной из основных, приятных особенностей "классических" дискретных ортогональных преобразований является существование быстрых алгоритмов их вычислений. Покажем, что вычисление М — преобразований сводится к вычислению циклической свертки.
Действительно, рассмотрим преобразование (2.1): N-\ х{т)= х{п)Ит(п). Так как базисные функции преобразования связаны друг с другом циклическим сдвигом аргумента: hm(n)=ho(m+n), то после замены ц=-п аргумента получаем представление преобразования (2.1) в форме циклической свертки N-\ х( п)= х(п)} (т-г =(х И$)(т), m=0,...,N-l. (3.13) rt=l Массив (3.13) может быть найден по обычной спектральной схеме вычисления свертки стандартным применением дискретного преобразования Фурье. ДПФ х(п) "" » Х(тУ- шш иЩ(т у ОДПФ / , w ч 0 K fy)H
Целью настоящей главы является, во-первых, описание программных средств определения параметров М -преобразований и, во-вторых, иллюстрация эффективности применения этих преобразований к задачам диссертационного исследования. Основное внимание уделяется именно описанию программ и алгоритмов определения параметров преобразований.
Результаты, относящиеся к экспериментальным исследованиям статистических характеристик шумов, возникающих в процессе кодирования, передачи и восстановления изображений имеют иллюстративный характер.
Для решения задачи определения параметров двумерных М-преобразований в работе разработаны и программно реализованы следующие алгоритмы. 1. Алгоритм определения характеристик квадратичных полей, в которых существуют КСС. ч 2. Алгоритм представления целых чисел в канонических системах счисления. 3. Алгоритм генерации "фундаментальных" областей для квадратичных полей, в которых существуют КСС. 4. Алгоритм нумерации элементов "фундаментальной" области. 5. Алгоритм нумерации элементов периодического ограничения "фундаментальной" области.
Алгоритм представления целых чисел в канонических системах счисления
Алгоритм declcan переводит целое число в КСС и обратно при помощи формул (1.26)-(1.29) полученных в параграфе 1.2. Числа в КСС представляются в виде двоичной последовательности нулей и единиц. При этом знак числа можно не учитывать из-за специфики системы счисления.
Входными параметрами являются g, A, d и /, где g - число в десятичной системе счисления, которое необходимо преобразовать в КСС, A, d - основание КСС, / - флаг, как характеристика, которая определяет, является ли основание КСС целым или полуцелым.
Выходным параметром является s - массив двоичных чисел, которым представляется число в КСС. Алгоритм dec2can. Шаг 1. if d mod 4=2,3 and f - целое then 5, .+i=2y4r /Norm(a)]-r _i/Norm(a)] else перейти на шаг 2; Шаг 2. if d mod 4=1 and f - полуцелое then +i=5r /Norm(a)]-[ _i/Norm(a)] else перейти на шаг 3; Шаг 3. if d mod 4=-2,-3 and / - целое then 5 +i=2v4r /Norm(a)]-[ _j/Norm(a)] else перейти на шаг 4; Шаг 4. if d mod 4=-1 and / - полуцелое then 5jt+i=5[ /Norm(a)]-[ _1/Norm(a)]; Шаг 5. Вывод результатов. Работу алгоритма завершить.
В качестве примера в таблице 4.4 показаны все битовые строки от 0000 до 1111 и их интерпретация в системе счисления по основанию -1+/, а также представление в этой системе десятичных чисел от-15 до +15.
В этой главе мы опишем алгоритм genjiinreg для генерации "фундаментальных" областей. Нами ранее (параграф 1.2) были рассмотрены свойства канонических систем счисления в квадратичных полях.
Отмечалось, что квадратичное целое число a=A+B Jd называется основанием канонической системы счисления в кольце целых поля Qk/c/j, если каждый целый элемент zeSNd) может быть единственным образом представлен в виде (1.21). Если в сумме (1.21) к - фиксировано, то множество элементов zeSfyfd) изображается на плоскости (Rat(z), Irr(z)) в виде множества точек решетки, которую будем называть "фундаментальной" областью объема р . Рассмотрим рекуррентную последовательность х{п)=а\х{п-\)+...+а у{п-к) (4.1) С учетом (1.21) и (4.1) получаем z(l)= (1) х +х(2)а} +.. .+х(к)ак 1 z(2)=jc(2)a+ (3)a1 +.. .+x(k+l)ak l (4.2) z(n)=x(n)a+x(n+l)a} +...+x(n+k)ak l, где z(ri) - массив координат точек "фундаментальной" области, a основание канонической системы счисления. С учетом (4.2) алгоритм genjiinreg имеет следующий вид.
Входными параметрами являются к и сп, где к - размер "фундаментальной" области, сп - основание КСС. Выходным параметром является zv — массив координат точек "фундаментальной" области. Алгоритм gen_funreg. Шаг 1. n=pow(d,k)-l, 1=п+к-\; //количество точек Шаг 2. for /=1 to k do х[/]=1; //инициализация начальных условий Шаг 3. for i=k+l to I do //вычислениерекуррентной функции (4.1) tmp=x[i-n-l]+x[i-n-2\+x[i-n-3]+x[i-n-4]; x[i\=tmp mod d; Шаг 4. for /=0 to n-\ do //вычисляем координаты no (4.2) p=0; for 7=/+1 to k+i do a=cpow{cn)p,d); xa=x[j] a; z=addcom{z,xa); p=p+l; zv[/+l]=z; //массив точек "фундаментальной" области z=0; Шаг 5. Работу алгоритма завершить.
В качестве примера работы алгоритма genjiinreg в приложение 1 на рисунках П.1.1-П.1.6 приведены результаты "фундаментальных" областей для полей с бинарными и тернарными системами счисления.
