Содержание к диссертации
Введение
1 Основные теоретические сведения 14
1.1 Канонические системы счисления в квадратичных полях. 14
1.2 Квазиканонические системы счисления 18
1.3 Деление с остатком в квадратичных полях 19
1.4 Алгоритмы быстрого умножения больших целых чисел... 21
1.5 Постановка задач 22
1.6 Выводы и результаты первой главы 25
2 Классификация квазиканонических систем счисления в мнимых квадратичных полях 26
2.1 Квазиканонические системы счисления 26
2.2 Классификация двоичных квазиканонических систем счисления в мнимых квадратичных полях 40
2.2.1 Классификация двоичных квазиканонических систем счисления в кольце S(i) 40
2.2.2 Классификация двоичных квазиканонических систем счисления в кольце S iS 44
2.2.3 Классификация двоичных квазиканонических систем счисления в кольце Sli\l7 47
2.3 Троичные квазиканонические системы счисления 52
2.3.1 Классификация троичных квазиканонических систем счисления в кольце S т/3 52
2.3.2 Классификация троичных квазиканонических систем счисления в кольце SliyJ2\ 57
2.3.3 Классификация троичных квазиканонических систем счисления в кольце s(n/l7) 62
2.4 Выводы и результаты второй главы 65
3. Алгоритмы машинной арифметики в квазиканонических системах счисления мнимых квадратичных полей 67
3.1 Алгоритмы реализации арифметических операций в двоичных квазиканонических системах счисления з
3.2 Алгоритмы реализации арифметических операций в троичных квазиканонических системах счисления 74
3.3 Выводы и результаты третьей главы 82
4 Приложения квазиканонических систем счисления 83
4.1 Быстрое безошибочное параллельное вычисление свертки 83
4.2 Размерность границ фундаментальных областей квазиканонических систем счисления
4.2.1 Размерность границ фундаментальных областей двоичных систем счисления в мнимых квадратичных полях 100
4.2.2 Размерность границ фундаментальных областей троичных систем счисления в мнимых квадратичных полях 106
4.3 Выводы и результаты четвертой главы 119
Заключение 120
Список литературы 1
- Деление с остатком в квадратичных полях
- Классификация двоичных квазиканонических систем счисления в мнимых квадратичных полях
- Алгоритмы реализации арифметических операций в троичных квазиканонических системах счисления
- Размерность границ фундаментальных областей двоичных систем счисления в мнимых квадратичных полях
Введение к работе
Актуальность темы
К настоящему времени уже вполне сформировалась точка зрения, что «то, каким образом мы выполняем арифметические действия, тесно связано с тем, каким образом мы представляем числа, с которыми работаем» (Д. Кнут, 2007). В частности, одной из возможностей представления данных в форме, адекватной применяемым математическим методам решения задач информатики, является использование позиционных систем счисления, отличных от традиционной бинарной (двоичной) системы счисления.
Работы в этом направлении ведутся как в области определения параметров систем счисления, позволяющих более эффективно решать традиционные задачи информатики, так и в области экстраполяции существующих теорий и методов решения прикладных задач для данных, представленных элементами алгебр, более общих, чем традиционные алгебры действительных чисел.
В диссертационной работе рассматриваются различные версии двоичной и троичной арифметики для данных, представленных целыми элементами поля комплексных чисел.
Применение троичных систем счисления вместо традиционной двоичной имеет почтенную историю, например, еще в докомпьютерную эпоху при создании механического вычислительного устройства Т. Fauler использовал так называемую троичную уравновешенную систему счисления. Такая же система счисления была задействована в советской электронно-вычислительной машине СЕТУНЬ, созданной Н. П. Брусенцовым. Относительное преимущество троичных систем счисления заключается в том, что они в ряде случаев оказываются экономичнее традиционных двоичных позиционных систем для представления чисел (СВ. Фомин, 1987).
Тем не менее троичная вычислительная техника не получила широкого распространения отчасти из-за отсутствия соответствующей элементной базы -электронных устройств с тремя устойчивыми состояниями (троичных триггеров). В настоящее время, несмотря на возрастание интереса к троичным системам счисления (Yi Jin et al., 2011) препятствия к развитию троичной вычислительной техники определяются в том числе и коммерческими причинами.
Троичная уравновешенная система счисления (с основанием 3 и цифрами о, 1 и -1) не является единственно возможной троичной системой, с помощью которой можно эффективно решать задачи информатики. Заметим, что цифры уравновешенной троичной системы счисления ассоциируются прежде всего не с числами, а с состояниями троичных триггеров, и при реализации арифметических операций в троичных кодах они индуцируют правила действий над этими кодами.
В начале девяностых годов в малодоступных венгерских журналах были опубликованы работы I. Katai и В. Kovacs, посвященные так называемым каноническим системам счисления (в частности троичным) на подмножествах поля
комплексных чисел. Эти работы по ряду причин долгое время оставались вне внимания как математиков, занимающихся проблемами теории чисел, так и специалистов в области информатики. Однако, на рубеже веков возник стойкий интерес к этой тематике, и к настоящему времени библиография работ по этой тематике, как теоретических (W. Penney, I. Katai, В. Kovacs, J. Szabo, W. J. Gilbert, I. Kornyei, H. Brunotte, A. Petho, S. Akiyama и другие), так и прикладных (S. Akiyama, I. Katai, К. Scheicher, J.M. Thuswaldner, W. J. Gilbert и другие), насчитывает более двух тысяч публикаций. В частности, такие системы счисления эффективно применялись для решения следующих прикладных задач:
синтез многомерных генераторов случайных чисел (А.Н. Калугин, 2008);
безошибочное вычисление свертки, умножение больших целых чисел (В.М. Чернов, 2007);
криптографические задачи {В.А. Федосеев, В.М. Чернов, 2006);
синтез новых дискретных ортогональных преобразований (A.M. Белов, 2011; М.С. Каспаръян, 2014).
Несмотря на перечисленные работы, резервы для разработки методов решения прикладных задач с помощью различных новых версий двоичных и троичных (тернарных) систем счисления далеко не исчерпаны. Таким образом, тематика исследования представляется актуальной.
Цель и задачи исследования
Целью диссертационной работы является разработка новых версий двоичной и троичной машинной арифметики в мнимых квадратичных полях.
В связи с обозначенной выше целью работы можно сформулировать задачи исследования, определяющие структуру диссертационной работы и содержание глав.
-
Классификация всех двоичных и троичных квазиканонических систем счисления в мнимых квадратичных полях.
-
Синтез алгоритмов представления целых алгебраических чисел мнимых квадратичных полей в двоичных и троичных квазиканонических системах счисления.
-
Синтез алгоритмов, реализующих арифметические операции для всех двоичных и троичных квазиканонических систем счисления в мнимых квадратичных полях.
-
Определение параметров применимости модифицированного параллельного алгоритма Шенхаге-Штрассена умножения больших целых чисел.
-
Исследование фрактальной структуры границ фундаментальных областей всех двоичных и троичных квазиканонических систем счисления в мнимых квадратичных полях для определения возможности их использования при цифровой обработки сигналов.
Эти задачи направлены на решение проблем, подробно описанных в первой главе диссертации.
Структура диссертации
Деление с остатком в квадратичных полях
В работе В. Ко vacs приводятся рекуррентные алгоритмы вычисления цифр, основанные на другой идее, именно в силу того, что алгоритм деления с остатком реализуем не для всех колец Sly/dy Однако, для колец, в которых существуют основания с нормами 2 и 3, то есть потенциальные двоичные или троичные системы счисления, такие алгоритмы существуют, что позволяет экстраполировать обычный алгоритм деления с остатком на случай этих колец.
В заданном кольце Siyfd) может существовать достаточно много различных комбинаций оснований а и множеств / , где Norm r KNorm a y el, например в кольце целых чисел Эйзенштейна существует 90 таких комбинаций, то есть 90 троичных а-систем. Однако, в силу пункта 2, не для всех из этих а-систем алгоритм деления с остатком по норме приводит к однозначному определению цифр разложения элемента z квазиканонических систем счисления связаны с кривыми, которые не являются множествами, измеримыми по Жордану, это существенно ограничивает возможности получения эффективных оценок качества алгоритмов блочного кодирования изображений с разбиением на блоки -фундаментальные области канонических и квазиканонических систем счисления, а также получение численных оценок, связанных с применением метода Монте-Карло на таких областях.
В связи с обозначенной во введении целью работы и перечисленными в пунктах 1-4 проблемами, сформулируем теоретические задачи исследования, определяющие структуру диссертационной работы и содержание последующих глав: 1) Классификация всех двоичных и троичных квазиканонических систем счисления в мнимых квадратичных полях. 2) Синтез алгоритмов представления целых алгебраических чисел мнимых квадратичных полей в двоичных и троичных квазиканонических системах счисления. 3) Синтез алгоритмов, реализующих арифметические операции для всех двоичных и троичных квазиканонических систем счисления в мнимых квадратичных полях. 4) Определение параметров применимости модифицированного параллельного алгоритма Шенхаге-Штрассена умножения больших целых чисел. 5) Исследование фрактальной структуры границ фундаментальных областей всех двоичных и троичных квазиканонических систем счисления в мнимых квадратичных полях для определения возможности их использования при цифровой обработки сигналов.
1. В этой главе рассмотрены необходимые теоретические сведения из теории канонических систем счисления в квадратичных полях, алгоритмы деления с остатком в квадратичных полях, алгоритмы быстрого умножения больших целых чисел.
2. В данной главе приведены основные проблемы, возникающие при исследовании квазиканонических систем счисления в мнимых квадратичных полях, и на основе этих проблем определены задачи диссертационного исследования.
3. Определение и исследование новых систем счисления можно провести по аналогии с теорией канонических систем счисления. В частности, для таких систем счисления необходимо получить некоторые классификационные теоремы и алгоритмы представления целых алгебраических чисел в этих системах счисления. Это и является основной задачей второй главы. 2 Классификация квазиканонических систем счисления в мнимых квадратичных полях
Поэтому на некотором шаге / получаем, что Norm 1уА = 0, то есть у1 = 0, следовательно, процесс деления с остатком конечен. Лемма 2.4. Если Norm(ym+A Norm(y) Vm = 0,1,... , то Norm (у ) 1.
Лемма 2.5. Если / и ;кт+1 - целые алгебраические числа мнимого кольца SI гл/d I на т шаге процесса деления с остатком (2.2), то для выполнения неравенства Norm(ут+1) Norm(ут) необходимо и достаточно чтобы
В этом случае а-система la, 1 будет являться квазиканонической системой счисления. Стоит отметить, что для остатка г = 0 последнее неравенство записывается в виде Norm іут) 0, что означает, что для остатка rm = О есть лишь одно число, для которого Norm(ут+1) Norm(ут) , которое появляется лишь по окончании процесса деления с остатком (2.2). Лемма 2.6. Если (а, 1\ - а-система в кольце S[\ld\, то множество / содержит один и только один остаток с нулевой нормой, а именно, rQ = 0.
Доказательство. Предположим, что при делении с остатком некоторое число (З делится на основание а. Такое число /? всегда существует. Тогда Р = уа + 0. Предположим, что можно выбрать еще один остаток rx, такой, что \Norm(rA\ \Norm(a)\ и (5 = уха + гх . Тогда у]а + г1 = уа или гх = (у - уАос . Таким образом, NormirA = Normliy - /Аос) = = Norm (у - уА- Norm (а) , а значит, выполнение неравенства NormirA\ Шогт(а)\ возможно только при Normiy-yA = 0 . Тогда NormirA = 0 и, следовательно, rx = 0.
Классификация двоичных квазиканонических систем счисления в мнимых квадратичных полях
Это означает, что а-система -1 + г,0,гИ и все эквивалентные ей системы счисления являются двоичными квазиканоническими системами счисления. Проверка значений у +1 = ±1; ± г в системе счисления 1 + г,0,т показывает, что при последовательном применении алгоритма деления с остатком возможно зацикливание:
Следовательно, в кольце целых алгебраических чисел Sm существуют ровно 8 двоичных квазиканонических систем счисления, а именно, системы счисления с основаниями а = -1 ± і и множествами цифр Алгоритм 2.1. Шаг 1. Пусть р = 0. Шаг 2. Если для у = а + Ь г сумма а + Ь - четная, то г = 0; если Шаг 3. Вычисляем у +1 по формуле у +1 = —. Если у +1 = 0, то алгоритм закончен; если у +1 Ф 0, то увеличиваем значение параметра р на единицу и переходим к шагу 2.
Классификация двоичных квазиканонических систем счисления в кольце Кольцо S (гл/2 целых алгебраических чисел поля Q (гл/2 состоит из элементов z = а + &п/2; а,6 є Z [89]. Пусть а є sit 2 J, Normla) = 2, то есть а является одним из элементов множества ]±г . Согласно лемме 2.6 во множестве / обязательно содержится остаток 0. Норма ненулевого остатка может равняться только единице. Таких остатков ровно два: {±l Таким образом, существует 4 возможные комбинации основания а и множества / , то есть, 4 а-системы. Выясним, какие из них являются квазиканоническими системами счисления. Учитывая леммы 2.7 и 2.8, в кольце SI гл/2) достаточно исследовать лишь одну а-систему, а именно, uV2,o,-l . Каждая из остальных 3 а-систем эквивалентна этой а-системе. Следующая теорема описывает все возможные двоичные квазиканонические системы счисления в кольце S (w 2 .
В кольце целых алгебраических чисел S[iyj2\ существуют ровно 4 двоичные квазиканонические системы счисления, а именно, системы счисления с основаниями а = +гл/2 и множествами цифр
Заметим, что остатки от деления на число а, имеющие норму 1, можно представить в виде (-1) , где к = 1; 2, а основания а-систем запишем как а =ІУІ2-(-І\ , п = 1; 2 . Покажем, что в каждой такой а-системе ап, 0,1-і) представление произвольного целого алгебраического числа у0 единственно. Пусть в процессе деления с остатком (2.2) у = а + Ъ iy2 , г = г + 0 г /2 и а = с гл/2 , s = 0,1, 2, .... Подставляя выражения для и г в формулу (2.1) в качестве (5 и г соответственно, получаем выражение
Таким образом, последовательность остатков в процессе (2.2) деления с остатком по норме определяется однозначно, а значит и представление числа у0 в а-системе ап, 0,1-і) будет единственно. Покажем теперь, что в а-системе n/2,J0,-lj представление произвольного целого алгебраического числа будет конечно.
Согласно лемме 2.5, в процессе деления с остатком (2.2) найдется такое значение I = q, при котором Norm(y +1) 1, следовательно, у +1 = 0 либо / +1 удовлетворяет неравенству Norm (у +1 - 11 2 , то есть, учитывая что Re (у +11 = 11 mod 2 J , получаем, что необходимо проверить конечность представления для чисел у +1 = 1; 1 ± W2 . Для всех этих значений у +1 легко проверить, что через конечное число шагов в а-системе a-s/2,J0,-lj появится частное у = 0 . Поэтому, из равенств (2.2) получаем конечное разложение числа у0 по степеням числа a = iy/2 Вычисляем у +1 по формуле У +1= — Если у +1 = О, то алгоритм закончен; если +1 0, то увеличиваем значение параметра р на единицу и переходим к шагу 2.
Классификация двоичных квазиканонических систем счисления в кольце SІ іуі7 I Кольцо S целых алгебраических чисел поля состоит из а + Ы элементов z = -—; а = Ъ (mod2j, а,6 є Z. Пусть а є sli 7\ 2 Normla) = 2 , то есть а является одним из элементов множества _ _ Согласно лемме 2.6 во множестве / обязательно содержится остаток 0. Норма ненулевого остатка может равняться только единице. Таких остатков ровно два: j±l . Таким образом, существует 8 возможных комбинаций основания а и множества / , то есть, 8 а-систем. Выясним, какие из них являются квазиканоническими системами счисления. Учитывая леммы 2.7 и 2.8, в кольце Sin/7) достаточно исследовать лишь две а системы, а именно, + остальных 6 а-систем эквивалентна одой из этих а-систем. Следующая теорема описывает все возможные двоичные квазиканонические системы счисления в кольце S (iy/7 . Теорема 2.5. В кольце целых алгебраических чисел S w7 существуют ровно 8 двоичных квазиканонических систем счисления, а именно, системы счисления с основаниями а = и множествами цифр {О, і}, {О,-і}.
Алгоритмы реализации арифметических операций в троичных квазиканонических системах счисления
Кроме алгоритма 3.1 существуют и другие алгоритмы сложения чисел в двоичных квазиканонических системах счисления. Рассмотрим, например, следующий алгоритм, который начинает свою работу со старшего разряда и основан на представлении величины РЛа\. В различных кольцах такой алгоритм будет записываться по-разному, однако для его понимания достаточно рассмотреть этот алгоритм лишь в одном кольце, например, S\i\. Алгоритм 3.2.
Алгоритмы реализации операции умножения в некоторых эквивалентных двоичных системах счисления отличаются. В силу особенностей алфавита, а именно, того, что одна из цифр является нулем, таблицы умножения для таких систем счисления сильно упрощаются. Так, в
каждой системе счисления la, 0, г[ нужно получить представление числа
Согласно лемме 2.10, алгоритм умножения чисел в системе счисления а, I легко получается из алгоритма умножения чисел в системе счисления , поэтому достаточно рассмотреть лишь половину из всех возможных систем счисления. Представления для г2 в таких системах счисления также приведены в таблице 3.1.
Поскольку алфавит системы счисления la,І0,г состоит из цифр 0 и г , то умножение чисел Рх и Р2 в этой системе счисления сводится к сложению m чисел, где m - количество цифр единичной нормы в записи числа Р2. Складываемые числа получаются из числа /?х следующим образом.
При умножении числа /?х на цифру г , стоящую в разряде с номером р числа Р2, к записи /?х справа добавляется р нулей. Числа, полученные при умножении на цифры единичной нормы некоторых разрядов, складываются последовательно по два числа в соответствии с алгоритмом сложения.
Инверсию знака, согласно лемме 2.7, достаточно рассмотреть лишь для одной системы счисления из каждого кольца, например s(i).
Пусть представление исходного числа /? в системе счисления выполняется, то используем формулы для 2 г а из таблицы 3.1 для значения, находящегося в хк . При этом, если к + 3 I ( к + 4 Z для
Алгоритмы реализации арифметических операций в троичных квазиканонических системах счисления
Пусть два произвольных числа А и /?2 из кольца SI г-sjd І в троичной квазиканонической системе счисления \а, 0, rv гЛ\ представлены в виде
В случае гх + г2 є 7, выражение rx + г2 совпадает с одним из остатков, и, соответственно, не указывается в этой таблице. Таблица 3.2 - Формулы для сложения и инверсии знака в троичных квазиканонических системах счисления
В результате последовательного преобразования суммы двух чисел Рг+ Р2 с использованием формул для 2 -а3 , 2г2-а3 и 1 +гЛ-а3 из таблицы 3.2 может возникать зацикливание, то есть появление блоков
Выражение для рЛа\ , соответствующее каждому кольцу siisd\ , приведено в таблице 3.2. Из сказанного выше следуют алгоритмы сложения чисел, записанных в системе счисления с основанием а .
Введем следующие обозначения, справедливые для всех алгоритмов. Количество разрядов в записи суммы обозначим /. Значение в разряде с номером j;є 0,1, ..., / -1 обозначим как х. , Шаг 1. Складываем по разрядам два данных числа. При этом в записи суммы может присутствовать цифра не входящая в алфавит системы счисления. Если есть такие js є 0, 1, ..., / -1 , что х. I, то к = min(js) и переходим к шагу 2, иначе алгоритм закончен. Шаг 2. Если к I , то алгоритм закончен. Иначе, если хк I , то переходим к шагу 3, если хк є I, то переходим к шагу 2 при к = к + 1. Шаг 3. Если к + 2 Z , xfc+2 0 и fc+2«2 + к+1а + хк = = г-Р2(а)+ сза3 , где с є JO, гр 2т1? г2, 2т2, гх+г2, ...} , гє/, то необходимо обнулить выражение г рЛа\- ак , используя для Р2 (а) формулы из таблицы 3.2. Если условие хк+2а + xk+ia + хк = Т 2 Vх) + 2] с -а3 не выполняется, то используем формулы для 2гх -а-7 или 2г2 а3 или ( +гЛ-а3 из таблицы 3.2 для а , если необходимо, то меняем /. Переходим к шагу 2. Алгоритм 3.4 начинает свою работу с нулевого разряда, и позволяет осуществить все операции за один проход массива х = (х.) —. Основные действия алгоритма выполняются в третьем шаге. Среди таких действий можно выделить обнуление выражений вида г рЛа\- ак и перенос в старшие разряды. Схемы таких элементов алгоритма для системы
Алгоритмы реализации операции умножения в некоторых эквивалентных троичных системах счисления отличаются. В силу особенностей алфавита, а именно, того, что одна из цифр является нулем, таблицы умножения для таких систем счисления сильно упрощаются. В каждой системе счисления \а, JO, rv гЛ\ нужно получить представление чисел г? , г22 и г±г2 . Согласно лемме 2.8, алгоритм умножения чисел в системе счисления la, I} легко получается из алгоритма умножения чисел в системе счисления \а, / , поэтому достаточно рассмотреть лишь половину из всех возможных систем счисления. Представления для г2 , г22 и гхг2 в таких системах счисления приведены в таблице 3.3, за исключением тривиальных случаев, когда гх2, г22, г±г2 є /.
Размерность границ фундаментальных областей двоичных систем счисления в мнимых квадратичных полях
Метод, приведенный в предыдущем пункте полностью применим к троичным системам счисления, две из трех цифр которых противоположны по знаку.
Для поля QI гл/2) общий вид фундаментальной области системы счисления 1 + п/2, JO, 1, -1 приведен на рисунке 4.7. На рисунке 4.7 также приведены / -приближения при / = 1,2,3 . По аналогии с методом, приведенным в работе [51], выделим элементы, которые будут повторяться для каждого /-приближения. Эти элементы приведены на рисунке 4.8. Из рисунков 4.7 видно, что элемент А для границы / -приближения на следующем / -приближении переходит в один элемент А и два В, элемент С на следующем / -приближении переходит в два А и один В, а В - в С. Таким и количество образом, можно составить матрицу перехода Т элементов первого, второго и третьего типа для / -приближения определяется границы /-приближения первого типа, fy - второго, с{ - третьего. Начальным приближением считается / -приближение для 1 = 1, где ах = 2, Ъх = 2, сх = 2. Тогда минимальное количество отрезков длины С v 2 L, , полностью случае собственные числа являются корнями уравнения -Г +Г +А + 3 = 0. и приблизительно равны « 2,13 V3 , / = \ -0,57+1,04 -г, / л/3 . Длина каждого отрезка равна L; = С 3 2 , где С - константа, характеризующая длину большего ребра прямоугольника при / = о . Таким образом, общая длина границы / -приближения равна равна
Фрактальную размерность d границы фундаментальной области, в этом случае можно вычислить из равенства
Общий вид фундаментальной области системы счисления -1 - г\2, J0,1, ІУІ2 } приведен на рисунке 4.9. На рисунке 4.9 также приведены / -приближения при / = 1, 2, 3 . По аналогии с методом, приведенным в работе [51], выделим элементы, которые будут повторяться для каждого /-приближения. Эти элементы приведены на рисунке 4.10. Из рисунков 4.9 видно, что элемент А для границы / -приближения на следующем / -приближении переходит в один элемент в , элемент в на следующем / -приближении переходит в один с, а С - в один с, три А и один в. Таким образом, можно составить матрицу перехода Т и количество элементов первого, второго и третьего типа для / -приближения определяется следующим образом элементов границы /-приближения первого типа, fy - второго, с{ - третьего. Начальным приближением считается / -приближение для 1 = 1, где ах = 2, Ъх = 2 , сх = 2 . Тогда минимальное количество отрезков длины С л/2 Ц ,
Последний предел будет конечен тогда и только тогда, когда или d = 21og3 \ 1,376841713. Для поля QI гу 11) общий вид фундаментальной области приведен на рисунке 4.11. На рисунке 4.11 также приведены /-приближения при / = 1, 2, 3. По аналогии с методом, приведенным в работе [51], выделим элементы, которые будут повторяться для каждого / -приближения. Эти элементы приведены на рисунке 4.12.
Из рисунков 4.11 видно, что элемент А для границы /-приближения на следующем / -приближении переходит в три элемента В и один элемент С , элемент в на следующем / -приближении переходит в один с, а С - в один элементов границы /-приближения первого типа, fy - второго, с{ - третьего. Начальным приближением считается / -приближение для 1 = 1, где ах = 2, Ъх = 2 , сх = 2 . Тогда минимальное количество отрезков длины С V2 Ц ,
Для остальных систем счисления в поле QI г /11) фундаментальные области будут совпадать с приведенной на рисунке 4.11, с точностью до движений плоскости, следовательно, фрактальные размерности их границ будут такими же. Найдем теперь размерности границ фундаментальных областей троичных квазиканонических систем счисления в QIISI3\ [91]. Для этого рассмотрим 2 случая, а именно:
Решётка целых алгебраических чисел поля Q UV3 Очевидно, что для каждого узла А построенной решётки существует ровно 6 узлов А , т = 1, ..., 6 , удалённых от него на минимальное расстояние. Пусть d - серединные перпендикуляры к отрезкам А А . Обозначим через В точку пересечения d с d , л , кроме т = 6, а 5Й " т " т т+\ " о точку пересечения и d6 . Пусть внутренность полученного правильного шестиугольника В В В В - окрестность точки А . Ясно, что шестиугольные окрестности двух произвольных узлов решётки не пересекаются, и, кроме того, объединение замыканий таких окрестностей всех узлов решётки образует покрытие плоскости.