автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Двоичные и троичные машинные арифметические операции над цифровыми сигналами в мнимых квадратичных полях

На правах рукописи

Богданов Павел Сергеевич

ДВОИЧНЫЕ И ТРОИЧНЫЕ МАШИННЫЕ АРИФМЕТИЧЕСКИЕ ОПЕРАЦИИ НАД ЦИФРОВЫМИ СИГНАЛАМИ В МНИМЫХ КВАДРАТИЧНЫХ ПОЛЯХ

05.13.17 - Теоретические основы информатики

АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата физико-математических наук

~ 7 ОКТ 2015

САМАРА-2015 005563109

005563109

Работа выполнена в Федеральном государственном автономном образовательном учреждении высшего образования «Самарский государственный аэрокосмический университет имени академика С.П. Королева (национальный исследовательский университет)» на кафедре геоинформатики и информационной безопасности и в Федеральном государственном бюджетном учреждении науки Институте систем обработки изображений Российской академии наук.

Научный руководитель: доктор физико-математических наук

Чернов Владимир Михайлович

Официальные оппоненты:

Каркищенко Александр Николаевич, доктор физико-математических наук, профессор, профессор Южного федерального университета (ЮФУ);

Леухин Анатолий Николаевич, доктор физико-математических наук, профессор, проректор по научной и инновационной деятельности федерального государственного бюджетного образовательного учреждения высшего профессионального образования «Поволжский государственный технологический университет».

Ведущая организация: Федеральное государственное бюджетное учреждение науки Институт математики и механики им. H.H. Красовского Уральского отделения Российской академии наук (ИММ УрО РАН), г. Екатеринбург.

Защита состоится 20 ноября 2015 г. в 10:00 часов на заседании диссертационного совета Д 212.215.07, созданного на базе Федерального государственного автономного образовательного учреждения высшего образования «Самарский государственный аэрокосмический университет имени академика С.П. Королёва (национальный исследовательский университет)», по адресу: 443086, Самара, Московское шоссе, 34.

С диссертацией можно ознакомиться в библиотеке и на сайте Федерального государственного автономного образовательного учреждения высшего образования «Самарский государственный аэрокосмический университет имени академика С.П. Королёва (национальный исследовательский университет)», http://www.ssau.ru/resources/dis protection/bogdanov/.

Автореферат разослан 21 сентября 2015 г.

Учёный секретарь

диссертационного совета Д 212.215.07 доктор технических наук, профессор

И.В. Белоконов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Диссертационная работа посвящена разработке и исследованию новых систем машинной арифметики в приложении к задачам цифровой обработки сигналов.

Актуальность темы

К настоящему времени уже вполне сформировалась точка зрения, что «то, каким образом мы выполняем арифметические действия, тесно связано с тем, каким образом мы представляем числа, с которыми работаем» (Д. Кнут. 2007). В частности, одной из возможностей представления данных в форме, адекватной применяемым математическим методам решения задач информатики, является использование позиционных систем счисления, отличных от традиционной бинарной (двоичной) системы счисления.

Работы в этом направлении ведутся как в области определения параметров систем счисления, позволяющих более эффективно решать традиционные задачи информатики, так и в области экстраполяции существующих теорий и методов решения прикладных задач для данных, представленных элементами алгебр, более общих, чем традиционные алгебры действительных чисел.

В диссертационной работе рассматриваются различные версии двоичной и троичной арифметики для данных, представленных целыми элементами поля комплексных чисел.

Применение троичных систем счисления вместо традиционной двоичной имеет почтенную историю, например, еще в докомпьютерную эпоху при создании механического вычислительного устройства Т. Fauler использовал так называемую троичную уравновешенную систему счисления. Такая же система счисления была задействована в советской электронно-вычислительной машине СЕТУНЬ, созданной Н. П. Брусенцовым. Относительное преимущество троичных систем счисления заключается в том, что они в ряде случаев оказываются экономичнее традиционных двоичных позиционных систем для представления чисел (C.B. Фомин. 1987).

Тем не менее троичная вычислительная техника не получила широкого распространения отчасти из-за отсутствия соответствующей элементной базы -электронных устройств с тремя устойчивыми состояниями (троичных триггеров). В настоящее время, несмотря на возрастание интереса к троичным системам счисления (Yi Jiti et al., 2011) препятствия к развитию троичной вычислительной техники определяются в том числе и коммерческими причинами.

Троичная уравновешенная система счисления (с основанием 3 и цифрами 0 , 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).

Несмотря на перечисленные работы, резервы для разработки методов решения прикладных задач с помощью различных новых версий двоичных и троичных (тернарных) систем счисления далеко не исчерпаны. Таким образом, тематика исследования представляется актуальной.

Цель и задачи исследования

Целью диссертационной работы является разработка новых версий двоичной и троичной машинной арифметики в мнимых квадратичных полях.

В связи с обозначенной выше целью работы можно сформулировать задачи исследования, определяющие структуру диссертационной работы и содержание глав.

1) Классификация всех двоичных и троичных квазиканонических систем счисления в мнимых квадратичных полях.

2) Синтез алгоритмов представления целых алгебраических чисел мнимых квадратичных полей в двоичных и троичных квазиканонических системах счисления.

3) Синтез алгоритмов, реализующих арифметические операции для всех двоичных и троичных квазиканонических систем счисления в мнимых квадратичных полях.

4) Определение параметров применимости модифицированного параллельного алгоритма Шенхаге-Штрассена умножения больших целых чисел.

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

Эти задачи направлены на решение проблем, подробно описанных в первой главе диссертации.

Структура диссертации

Диссертация состоит из четырёх глав, введения, заключения, списка литературы из 91 наименования; изложена на 127 страницах машинописного текста, содержит 16 рисунков, 25 таблиц.

Методы исследований

В диссертационной работе используются методы абстрактной алгебры, теории чисел, цифровой обработки сигналов, фрактальной геометрии.

Научная новизна работы

1. Введен и исследован новый класс систем счисления в мнимых квадратичных полях. В рамках этого исследования определены понятия квазиканонической системы счисления, а-системы и эквивалентности а-систем, доказаны утверждения о конечности и однозначности представления целых алгебраических чисел мнимых квадратичных полей в квазиканонических системах счисления.

2. Впервые получена полная классификация двоичных и троичных квазиканонических систем счисления в мнимых квадратичных полях.

3. Впервые синтезированы алгоритмы представления целых алгебраических чисел мнимых квадратичных полей в двоичных и троичных квазиканонических системах счисления.

4. Впервые доказаны теоремы о конечности алгоритмов арифметических операций для двоичных и троичных квазиканонических систем счисления в мнимых квадратичных полях.

5. Модифицирован метод, который предложил W.J. Gilbert, для вычисления фрактальной размерности границ фундаментальных областей квазиканонических систем счисления в мнимых квадратичных полях.

Теоретическая значимость работы

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

Практическая значимость работы

Приведенные в работе методы и алгоритмы позволяют реализовать машинную арифметику в двоичных и троичных квазиканонических системах счисления мнимых квадратичных полей, что дает возможность использовать такие системы счисления в прикладных задачах: быстрого параллельного умножения больших целых чисел; оценке параметров искажения изображения при его блочном кодировании (снижение влияния эффекта Гиббса); оценке качества двумерных генераторов случайных чисел.

Апробация

Основные результаты диссертации были представлены на 3 научных конференциях: 7-ой международной конференции «Finsler Extensions of Relativity Theory» (FERT, Румыния, Брашов, 2011); 9-ой международной конференции «Интеллектуализация обработки информации» (ИОИ, Черногория, Будва, 2012); 2-ой международной конференции «International Eurasian Conference on Mathematical Sciences and Applications» (IECMSA-2013, Босния и Герцеговина, Сараево).

Публикации

По теме диссертации опубликовано 8 работ. Из них 5 работ опубликовано в изданиях, приведённых в перечне ведущих рецензируемых научных журналов и изданий ВАК Министерства образования и науки РФ.

На защиту выносятся

1. Классификация двоичных и троичных квазиканонических систем счисления в мнимых квадратичных полях.

2. Алгоритмы представления целых алгебраических чисел мнимых квадратичных полей в двоичных и троичных квазиканонических системах счисления.

3. Новые алгоритмы машинной арифметики для двоичных и троичных квазиканонических систем счисления в мнимых квадратичных полях.

4. Определение параметров применимости модифицированного параллельного алгоритма Шенхаге-Штрассена умножения больших целых чисел.

5. Нахождение фрактальной размерности границ фундаментальных областей квазиканонических систем счисления в мнимых квадратичных полях.

ОСНОВНОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ

В первой главе работы приведены необходимые сведения из теории квадратичных полей (ЯМ Чернов, 2007; З.И. Боревич, И.Р. Шафаревич, 1985), введен новый класс систем счисления - квазиканонические системы счисления в

мнимых квадратичных полях.

Определение 1. Пусть ¡1 - целое число, свободное от квадратов, тогда

множество д(Л) = {г = а+ьЛ; ^бей^ег} называется квадратичным полем.

При <1 >0 квадратичное поле называется вещественным, а при <1 <0 - мнимым. Здесь 0 - поле рациональных чисел. В диссертационной работе рассматриваются только мнимые квадратичные поля, поэтому в дальнейшем будем считать а < 0, и записи вида О(-Д) понимать как £?(<ч/Д), где д = > 0.

Определение 2. Пусть для элемента г^а+^е^Й его норма тгт{г) = (а + ьщ{а-ь4а)ег И след Тг{г) = (а + ьЛ) + {а-Ь41)^г есть целые числа, тогда этот элемент называется целым алгебраическим числом поля (¿(-Л).

Определение 3. Пусть любой элемент 2 кольца 5(7?) целых элементов (целых алгебраических чисел) квадратичного поля 0(7?) однозначно представим в форме конечной суммы

2 = Е а!а'. о, е / = {о, 1,...,|№гт(а)| -1},

тогда целое алгебраическое число а = А±-Л называется основанием канонической системы счисления в кольце 5(7?).

Пара {а,1} - называется канонической системой счисления в кольце 5(7?), а / - алфавитом этой системы.

Определение 4. Пусть а - целое алгебраическое число кольца а

множество 1 состоит из целых алгебраических чисел г, кольца таких, что

№гт(г)<Иогт{а), тогда пару {а;/}, назовем а-системой в кольце (П.С.

Богданов, 2015).

Определение 5. Пусть любой целый элемент поля Q(■^Jd) однозначно представим в форме конечной суммы

; = в, 6/, А(г)еЛЮ{0},

где множество / состоит из целых алгебраических чисел кольца х(-У^), величина нормы которых меньше нормы основания а. Тогда целое алгебраическое число а называется основанием квазиканонической системы счисления в кольце целых элементов поля пара {а;/} называется квазикано-

нической системой счисления в кольце 5 (>/?), а / - алфавитом этой системы {П.С. Богданов, В.М. Черное, 2013).

Для представления чисел в некоторой системе счисления может использоваться алгоритм деления с остатком.

Определение 6. Говорят, что в кольце Э имеет место алгоритм деления с остатком по норме, если на отличных от нуля элементах /УеЭ определена функция Могт(р), принимающая целые неотрицательные значения, так, что выполняются следующие условия:

1) если /7*0 делится на а, то Ыогт(р)> №гт(а);

2) для любых элементов р и а * 0 в О существуют такие у и г, что Р = ау + г, Причем либо г = О, либо Могт(г)<Ыогт(а).

Заметим, что существует ровно пять мнимых квадратичных полей, в кольцах целых элементов которых существует алгоритм деления с остатком по норме. Такими полями являются б(/),б((Ч/2),б(1ч/з),0(|Ч/7),0(1чУГТ).

Заметим также, что:

1) В отличие от неотрицательных целых рациональных чисел, среди целых алгебраических чисел может существовать несколько элементов с одинаковой нормой.

2) Алгебраическая норма ЛЪгт(х) = {а+Ы&}[а-ь4с1}= а1 -<1Ьг <¡2 не является нормой в смысле определения, принятого в функциональном анализе, -она не удовлетворяет неравенству треугольника. В связи с этим, аналогичное верному для обычного алгоритма представления числа в двоичной системе счисления, основанного на делении с остатком:

Г« = Гг2+га.

Г, =Г2-2+г1>

Уо = (-((Г,.,-2 + г,)-2+Гм)...)-2 + Г0

неравенству |r„,|<|r,|, неравенствоNorm(y^)<Norm(y,) для алгоритма деления с остатком по норме может выполняться не всегда, что в некоторых случаях пре-

К.-)

пятствует возможности представления элемента г в форме z = £ayarJ при данных значениях а и множества цифр I.

В работе В. Kovacs приводятся рекуррентные алгоритмы вычисления цифр, основанные на другой идее, именно в силу того, что алгоритм деления с остатком реализуем не для всех колец s(4d). Однако, для колец, в которых

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

3) В заданном кольце S (41) может существовать достаточно много

различных комбинаций оснований а и множеств I, где Norm(r)< Norm(a) Vr, е /, например, в кольце целых чисел Эйзенштейна существует 90 таких комбинаций, то есть 90 троичных ot-систем. Однако, в силу пункта 2, не для всех из этих а-систем алгоритм деления с остатком по норме приводит к однозначному определению цифр разложения элемента z в форме z = ]Г а^ . Кроме того, арифме-

j.о К:)

тические операции над элементами z в форме z = X а/х' Д°лжны допускать

J- о

простую аппаратную или программную реализацию.

4) Границы фундаментальных областей, то есть множеств чисел с нулевой целой частью - г= £ а .а', для канонических и квазиканонических систем

счисления связаны с кривыми, которые не являются множествами, измеримыми по Жордану. Это существенно ограничивает возможности получения эффективных оценок качества алгоритмов блочного кодирования изображений с разбиением на блоки - фундаментальные области канонических и квазиканонических систем счисления, а также получение численных оценок, связанных с применением метода Монте-Карло на таких областях.

В связи с обозначенной выше целью работы и перечисленными в пунктах 1-4 проблемами, в главе формулируются конкретные задачи исследования, определяющие структуру диссертационной работы и содержание последующих глав.

Во второй главе работы приведена классификация всех двоичных {U.C. Богданов, В.М. Чернов, 2013) и троичных (П.С. Богданов, В.М. Чернов, 2014) квазиканонических систем счисления в мнимых квадратичных полях, а также рассмотрены алгоритмы представления целых алгебраических чисел мнимых квадратичных полей в таких системах счисления.

В данной главе доказан ряд общих утверждений о введенных квазиканонических системах счисления. Их условно можно разделить на три группы.

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

Вторая группа связана с эквивалентностью а-систем. Это понятие позволяет существенно сократить отмеченный выше перебор при доказательстве классификационных теорем теории квазиканонических систем счисления. Кроме того, для определенных видов эквивалентностей алгоритмы арифметических операций в эквивалентных квазиканонических системах счисления совпадают с точностью до этих эквивалентностей.

Третья часть утверждений представляет собой критерии конечности различных алгоритмов сложения и умножения чисел, а также инверсии знака в квазиканонических системах счисления.

Приведем основные утверждения первой группы.

Лемма 1. Если для пары {а;1} представление произвольного целого алгебраического числа г„ в форме у(1=у1а + г0 единственно, где г0е/, то для того, чтобы пара {а;1} образовывала систему счисления в кольце £(%/?), необходимо и достаточно, чтобы процесс деления с остатком:

Г, = Гм-<* + гп

где /•„,/;.....г, е/ и Ыогт(г,)< Когт(а), был конечен.

Лемма 2. Если ут и ут<[ - целые алгебраические числа мнимого кольца

сгва Могт{утЛ)> К'огт(ут) необходимо и достаточно, чтобы выполнялось неравенство

Из леммы 2 следует, что процесс представления любого целого алгебраического числа кольца 5 в а-системе {а,1} будет конечен, если он конечен

для всех чисел, удовлетворяющих неравенствам (2) для каждого из остатков. В этом случае а-система {а,/} будет являться квазиканонической системой счисления.

Следующая группа утверждений связана с понятием эквивалентности а-систем.

Определение 7. Пусть {а;/} и {а';/'} - две а-системы в кольце 5где \Ыогт{а)\ = \Могт{а')\ , и существует взаимно однозначное отображение причём /(/) = /' , а для любого числа

7а =Г, •<* + /•„, Г, = у2-а + г,.

(1)

^ (V?) на т шаге процесса деления с остатком (I), то для выполнения неравен-

(2)

\Ыогт(у)\ = \Когт(/(г))\. Тогда, если из представления числа у в а-системе {а;/} в виде у = у,а+г, где |Д'огт(г)|<|лгогш(а)|, следует справедливость представления /(у) = /(у))а'+/(г) в а-системе {а';Г}, то а-система {а;1} называется эквивалентной а-системе {аI'}.

Из определения эквивалентности следует, что если а-система {а;/} является квазиканонической системой счисления в кольце 5(7?), то и все эквивалентные ей а-системы тоже будут квазиканоническими системами счисления в кольце 5(7?). Если же а-система {а;/} не является квазиканонической системой счисления в кольце 5(7?), то и все эквивалентные ей а-системы также не являются квазиканоническими системами счисления в кольце 5(7?)-

В следующих утверждениях рассмотрены два вида эквивалентности а-систем и их свойства.

Лемма 3. Пусть п - количество чисел единичной нормы в кольце 5(7?).

Если г - первообразный корень степени п из единицы, то а-системы {а;/} и {а;/-г*} в кольце 5(7?) эквивалентны, где ¿ = 0,1,2,....

Лемма 4. Если а - число комплексно-сопряжённое числу а, а 1 состоит из чисел комплексно-сопряжённых числам из / , то а-системы {а;/} и {а;/} эквивалентны.

Лемма 5. Пусть /:(а,1)-*(а,Г-гк) - эквивалентность а-систем (а,/) и (а,/-г'). Тогда для любых у, Де5(7?) справедливы равенства:

Лг+Р)=/(г)+/(Я /Ы=-/(г).

Лемма 6. Пусть /:(а,/)->(а,7) - эквивалентность а-систем (а,/) и (а,/). Тогда для любых у, Де5(7?) справедливы равенства:

Лг+/») = /(г)+/(/»). /Ы=-/(у), /(г-Р)=Г(г)-№-

Из леммы 5 следует, что алгоритмы сложения и инверсии знака в системах счисления {а,/} и {а,!-г1) имеют одинаковый вид.

Из леммы 6 следует, что алгоритмы сложения, инверсии знака и умножения в системах счисления {а,/} и {а,/} имеют одинаковый вид.

Следующие утверждения позволяют определить конечность различных алгоритмов сложения чисел в квазиканонических системах счисления.

Лемма 7. Пусть числа Д, Д и Д+Д в системе счисления {а,/} имеют

представления Д , Д =$/:,«' и Д + А = > соответственно, тогда

„о /-о '-»

выражение £(/;,.+гу,-г„)в' =|>У • м = тах(М„М„М3)>2, может быть пред-

у.о ;-о

ставлено в виде Р2(а)- £ I Гг^'„а' II. где Р2(а) = а2-Тг(а) а + Д'огт(а), с', ег, с'„ >0, /- е /.

Теорема 1. Пусть в произвольной квазиканонической системе счисления {а,1} для любых двух элементов г. и г. множества / выполняется условие кггл ф к, • , у',*/,, Д, е г, кгк, <-\ и в такой системе счисления существует алгоритм сложения произвольных чисел Д и Д,, в котором учитывается, что г. Р2(а) = 0, тогда такой алгоритм сложения будет конечен, и его результат будет совпадать с результатом представления числа Д +р2 в системе счисления {а, /}.

Теорема 2. Пусть в произвольной квазиканонической системе счисления {а, /} существуют хотя бы два элемента г и г, множества I, для которых выполняется условие к, • г. = к, , у, ф /,, е/, <0, и в такой системе счисления существует алгоритм сложения произвольных чисел Д и Д,, в котором

ЛГ

учитывается, что г Л(а) = 0, причем для всех с = , где 4 берутся из форму-

у.о

лы в лемме 8, эти коэффициенты с, - ограниченны, тогда такой алгоритм сложения будет конечен, и его результат будет совпадать с результатом представления числа Д + Д, в системе счисления {а, /}.

Теоремы 1 и 2 позволяют определить, является ли некоторый алгоритм реализации арифметической операции конечным или нет.

Основной результат второй главы представлен в следующей классификационной теореме.

Теорема 3. В кольцах целых алгебраических чисел мнимых квадратичных полей существует ровно 20 двоичных и 36 троичных квазиканонических систем счисления, а именно:

1. в кольце 5(/) существуют ровно 8 двоичных квазиканонических систем счисления: системы счисления с основаниями а = -1±/ и множествами цифр {0,1},{0,/},{0,-1},{0,-/},

2. в кольце 5(14/2) существуют ровно 4 двоичные квазиканонические системы счисления: системы счисления с основаниями а=±<ч/2 и множествами цифр {0,1}, {0, -1},

3. в кольце 5(¿77) существуют ровно 8 двоичных квазиканониче-

± 1 ± ¡-Л

ских систем счисления: системы счисления с основаниями а =-— и множе-

2

ствами цифр {0.1},{0,-1},

4. в кольце 5(/Тз) существуют ровно 24 троичные квазиканонические системы счисления: системы счисления с основаниями а, = (/7з)ю1'1 и множества-

, . 1 + /7з

МИ цифр {0,1,й)}. {О.а.со1}, {О.йГ.е)5}, {О.ю'.ю4}, {0, аД <у5}, {0, о ,о> }, где со--—

И к = 1,2,3,4,

5. в кольце 5(|Ч/2) существуют ровно 8 троичных квазиканонических систем счисления: системы счисления с основаниями а = ± 1±ьЯ и множеством цифр / = {0,1,-1} , а также системы счисления {-1-/72,{о,и72}] ,

{-1-/72,(0,-1,-/72}}, {-1 + /72,{о. 1,-/72}) И {-1 + /72,{О,-1,/72}},

6. в кольце 5(1'ТГТ) существуют ровно 4 троичные квазиканониче-

±ш7Й

ские системы счисления: системы счисления с основаниями а---— и множеством цифр I = {0,1,-1}.

Из доказательства теоремы 3 легко получаются алгоритмы представления целых алгебраических чисел в таких системах счисления. Все эти алгоритмы также приведены во второй главе диссертационной работы.

В третьей главе диссертации синтезированы алгоритмы реализации арифметических операций для всех двоичных и троичных квазиканонических систем счисления в мнимых квадратичных полях.

Стоит отметить, что арифметические операции, при их реализации на компьютере, работают с кодами (а,(г).«»(.-ь......ассоциированными с представлениями целых алгебраических чисел г = в некоторой системе счис-

у-о

ления {а,/}. В этом случае а, - символы для обозначения состояний соответствующих триггеров, и они по написанию совпадают с а/ лишь для удобства записи и восприятия. Правила преобразования таких кодов полностью определяются операциями над числами г = . Таким образом, как и в случае традиционных позиционных систем счисления алгоритмы, реализующие основные арифметические операции практически полностью определяются правилом «переноса в старший разряд». В таблице 1 приводятся такие правила для всех двоичных квазиканонических систем счисления.

При реализации арифметических операций может возникнуть необходимость в правиле «обратного» переноса - представлении нуля в форме Р2 (а). Это необходимо для того, чтобы такой алгоритм удовлетворял условиям теорем 1 и 2. В противном случае конечность алгоритма гарантировать нельзя.

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

Таблица I - Правила переноса в старшие разряды

Кольцо Система счисления Представление выражений, возникающих при реализации арифметических операций

{/-1.{0,/>> ¡' = /а + / -I = /а4 + /а' + + / 21 = ¡а' +/аг

{'-',{0,-1}) (-1)2 = 1 = (-1}аЧ(-1)в'+(-1)а' + (-1) -2 = (-1)ог'+(-1)а-

Н.М} Ю2=-1=И«2+и«+н | = (-|)а4+(-/)а3+(-/)а:+(-«) 2 г = (-/)сг+(-,-)£Г

{/-1,{0,1}} 1: = 1 -1 = 1-а4 +1а3 +1а~ + 1 2 = 1а'+1-<г

*(,ч/2) {,4/2,(0,1}} 12 = 1 -1 = 1<г+ 1 2 = 1а4 + 1а:

{,4/2,(0,-1}} (-,)' = ! = (_, )вЧ(-1) -2 = (-1)а4+(-1)а:

1; = 1 -1 = 1а2+1а + 1 2 = 1а3+1а

(-1)2 = 1 = (-1)аг+(-1)а + (-1) 2 = (-1)а3+(-1)а

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

Для вычисления произведения больших целых чисел в настоящее время известно большое количество алгоритмов, базирующихся на различных идеях, в частности, в алгоритме Шенхаге-Штрассена нахождение произведения больших целых чисел сводится к вычислению дискретной циклической свертки, которая определяется спектральным методом с помощью дискретного преобразования Фурье. Заметим, что в ряде случаев, например, в криптографии, требуется точное, а не приближённое вычисление, поэтому в методе Шенхаге-Штрассена используется модулярная версия дискретного преобразования Фурье (т.н. теоретико-числовые преобразования), в которой вычисления в поле комплексных чисел заменяются вычислениями по некоторому модулю, выбор которого определяется удобством реализации арифметических операций. К сожалению, количество

таких модулей весьма ограниченно - это простые числа Мерсенна, Ферма, Го-ломба, Люка. Такие числа позволяют вычислять свертку без умножений, но лишь для крайне ограниченного множества длин этой свертки. Использование же составных чисел Мерсенна и Ферма в качестве модулей затруднительно, так как во первых, в кольце классов вычетов по составному модулю есть делители нуля, то есть не все элементы обратимы, и во-вторых, простые сомножители (целые рациональные числа) таких составных чисел уже не являются простыми числами Мерсенна или Ферма. Тем не менее известно (В.М. Чернов, 2007), что в ряде случаев негативного влияния наличия делителей нуля можно избежать, вторая проблема решается использованием в качестве простых сомножителей чисел

специального вида.

В четвертой главе показывается, что использование как двоичных, так и троичных квазиканонических систем счисления, позволяет существенно расширить множество длин сверток, для которых ее вычисление возможно без умножений. Основной идеей в данном случае является использование в качестве модулей чисел специального вида М = (а"±1)-(ал'±1), где сомножители ау±\ и ак ±1, являющиеся целыми алгебраическими числами, взаимно просты. В главе 4 приведен список длин свертки, для которых возможно ее параллельное безошибочное вычисление, с использованием лишь операций сложения и регистровых сдвигов кодов. В таблице 2 приведены данные для лг < 100.

Таблица 2 - Длины сверток, для которых возможно их быстрое безошибочное параллельное вычисление

Поле

е(0

еИ)

оЩ

е(л/гт)

Возможные длины свёрток N для модулей М=(аА'±1)-(ау±1)

1,2,3,4,5,6,7,9,11,13,17,19,23,29,31,37,41,43,47, 53,59,61,67,71,73,79,83,89,97

1,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97

1,2,3,4,5,7,8,11,13,16,17,19,23,29,31,32,37,41,43,47, 53,59,61,64,67,71,73,79,83,89,97

1,2,3,5,6,7,8,10,11,13,16,17,19,22,23,26,29,31,32,34,37,38, 41,43,46,47,53,59,61,62,64,67,71,73,74,79,82,83,86,89,94,97

1,2,3,4,7,8,11,13,16,17,19,23,29,31,32,37,41,43,47,53,59,61,64,67,

71,73,79,83,89,97 ______

Экстраполяция методов получения значений из таблицы 2 на большие значения N представляет хотя и трудоемкую, но простую задачу.

Кроме того, в четвертой главе для всех двоичных и троичных квазиканонических систем счисления в мнимых квадратичных полях вычислена размерность границы фундаментальной области. Для этого был модифицирован метод, предложенный Джильбертом, который он применял для вычисления фрактальной размерности границ фундаментальных областей канонических систем счисления. Результаты вычислений для некоторых квазиканонических систем счисления проиллюстрированы в таблице 3.

Таблица 3 - Размерности границ фундаментальных областей двоичных и троичных квазиканонических систем счисления____

Система счисления

Вид фундаментальной области

Размерность границы

1,376841713

1,26! 9

1,376841713

Основные результаты

1. Введен новый класс систем счисления - квазиканонические системы счисления.

2. Классифицированы все двоичные и троичные квазиканонические системы счисления в мнимых квадратичных полях.

3. Синтезированы алгоритмы представления чисел в таких системах счисления.

4. Синтезированы алгоритмы реализации арифметических операций для всех рассмотренных систем счисления

5. Найдены длины сверток, для которых возможно безошибочное параллельное вычисление с помощью двоичных и троичных квазиканонических систем счисления в мнимых квадратичных полях.

6. Для всех рассмотренных систем счисления найдены размерности границ фундаментальных областей.

Публикации по теме диссертации

Статьи в изданиях, входящих в перечень ВАК:

1. Богданов, П.С. О представлении целых гауссовых чисел в системе счисления Пенни // Компьютерная оптика. - 2010. - Т. 34, № 4. - С. 561-566.

2. Богданов, П.С. Классификация бинарных квазиканонических систем счисления в мнимых квадратичных полях / П.С. Богданов, В.М. Чернов // Компьютерная оптика. - 2013. - Т. 37, № 3. - С. 391-400.

3. Богданов, П.С. Классификация тернарных квазиканонических систем счисления в мнимых квадратичных полях и их приложение / П.С. Богданов,

B.М. Чернов // Компьютерная оптика. - 2014. - Т. 38, № 1. - С. 139-147.

4 Богданов, П.С. О размерности границ некоторых фрактальных множеств на гексагональных решётках / П.С. Богданов, В.М. Чернов // Компьютерная огггика. - 2014. - Т. 38, № 2. - С. 330-334.

5. Богданов, П.С. О сходимости некоторых алгоритмов бинарной и тернарной машинной арифметики для вычислений в мнимых квадратичных полях // Компьютерная оптика. - 2015. - Т. 39, № 2. - С. 249-254.

Материалы и тезисы конЛеоениий. статьи в сборниках:

6. Bogdanov, P.S. Quaternary quasi-canonical number systems for ring of double numbers / P.S. Bogdanov, V.M. Chernov // The VII-th International Conference "Finsler Extensions of Relativity Theory" - Romania, Brasov, 2011.

7. Богданов, П.С. Тернарные системы счисления в гольце целых чисел Эйзенштейна и их приложения / П.С. Богданов, В.М. Чернов // 9-ая Международная конференция "Интеллектуализация обработки информации". Черногория, г. Будва, 2012 г.: Сборник докладов - М.: Торус Пресс, 2012. -

C. 312 — 315. .

8. Bogdanov, P.S. On classification of binary and ternary number systems for imaginary quadratic rings and their applications / P.S. Bogdanov, V.M. Chernov // 2nd International Eurasian Conference on Mathematical Sciences and Applications - Bosnia and Herzegovina, Sarajevo, 2013. P. 440.

Подписано в печать 8.09. 2015. Формат 60 х 84/16. Бумага ксероксная. Печать оперативная. Объем - 1,25 усл. печ. л. Тираж 100 экз. Заказ №105

Отпечатано в типографии издательства «Инсома-пресс» 443080, г. Самара, ул. Санфировой, 1ЮА, оф. 22А, тел. 222-92-40, E-mail: insoma@bk.ru