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

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

МАГОМЕДОВ ШАМИЛЬ ГАСАНГУСЕЙНОВИЧ

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

Специальность 05.13.05 - Элементы и устройства вычислительной техники и систем управления

4849879

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

1 6 ИЮН 2011

Астрахань - 2011

4849879

Работа выполнена в Государственном образовательном учреждении высшего профессионального образования «Дагестанский государственный технический университет»

Научный руководитель:

доктор технических наук, профессор Исмаилов Шейх-Магомед Абдулаевич Официальные оппоненты:

доктор технических наук, профессор Хачумов Вячеслав Михайлович доктор технических наук, профессор Лукьянов Виктор Сергеевич

Ведущая организация: ОАО НИИ «Сапфир»

Защита состоится 2 июля 2011г. в 10 часов 00 минут на заседании диссертационного совета Д 307.001.01 при Астраханском государственном техническом университет по адресу: 414025, г.Астрахань, ул. Татищева 16, гл. корп., ауд. Г.305.

Отзывы на автореферат в двух экземплярах, заверенные гербовой печатью организации, просим направлять по адресу: 414025, г.Астрахань, ул. Татищева 16, ученому секретарю диссертационного совета Д 307.001.01.

С диссертацией можно ознакомиться в библиотеке Астраханского государственного технического университета.

Автореферат разослан «_»_2011 г.

Ученый секретарь Диссертационного совета

Г.А. Попов

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

Актуальность темы. Интенсивное развитие информационных технологий и широкое внедрение реализующих их автоматизированных систем обработки информации и управления практически во все сферы Человеческой деятельности, увеличение объемов и сложности осуществляемых ими преобразований требует обеспечения соответствующего уровня надежности, достоверности и приемлемого времени выполняемых операций. Особую остроту приобретают вопросы, связанные с управлением ответственными объектами и процессами - систем критических приложений (энергетика, транспорт, экология, оборона и т.д.), для которых ошибки в преобразованиях и при передаче данных могут привести к тяжелым и даже к катастрофическим последствиям.

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

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

Однако, наряду со значительными успехами, достигнутыми в теории архитектуры СВСОД, традиционно функционирующих в двоичной системе счисления (СС), важным направлением повышения быстродействия и надежности их работы является использование, наряду с двоичной СС, недвоичных СС. Известно, что главный недостаток двоичной СС - наличие, «длинных» межразрядных переносов, что существенно влияет на быстродействие выполнения арифметических операций, что безусловно сказывается на производительности СВСОД. В настоящее время повышение быстродействия СВСОД производится в основном за счет распараллеливания задачи и ее реализации на параллельных ЭВМ. К сожалению на практике имеется класс задач не поддающихся «хорошему» распараллеливанию, но необходимо более высокое быстродействие. Понятно, что традиционными (классическими) способами поставленную задачу не решить в связи имеющими ограничениями на многие параметры. В этом случае необходимы поиски новых путей или усовершенствования известных. С этих позиций представляется целесообразным использование в качестве СС системы счисления в остаточных, классов (ССОК). Одно из основных достоинств ССОК - возможность эффективно реализовать процедуру распараллеливания реализации арифметических операций и тем самым суще-

ственно повысить быстродействие систем СВСОД.

Проблема использования СОК является не новой. Впервые она была поставлена в пятидесятые годы прошлого века, когда были предприняты попытки по практической реализации данной идеи в рамках проекта «Алмаз», при создании ЭВМ Т-340А и К-340А и суперЭВМ 5Э53. Однако, после двадцати лет исследований все работы были практически приостановлены, по-видимому, ввиду недостаточно развитой элементной базы того времени и отсутствия эффективных алгоритмов прямых и обратных преобразований числовой информации. В настоящее время существующая элементная база позволяет не только реализовать проекты того времени, связанные с ССОК, но и значительно усовершенствовать многие идеи; в частности, применительно к проблемам безопасности и безошибочности вычислений. Поэтому теоретические исследования и Практические работы в данной области в последние годы активизировались.

Большой вклад в развитие теоретических и практических вопросов, связанных с СОК, внесли отечественные исследователи и ученые Акушский И.Я., Юдицкий Д.И., Червяков Н.И., Коляда A.A., Коряков И.В., Малашевич Д.Б., зарубежные ученые Свобода А., Валах М., Бияшев Р.Г.

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

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

С этой точки зрения тема диссертационной работы безусловно является актуальной как в теоретическом так и практическом плане.

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

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

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

1. Разработка алгоритма и структуры устройства преобразования числовой информации из ССОК в позиционный код с вычисляемыми слагаемыми;

2. Разработка алгоритма и структуры устройства преобразования числовой информации из ССОК в позиционный код с табличными слагаемыми;

3. Разработка алгоритма и структуры устройства преобразования число-

вой информации из двоичной системы счисления в СОК;

4. Разработка алгоритма и структуры устройства преобразования числовой информации из двоично-десятичной системы счисления в СОК;

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

6. Анализ приложений разработанных алгоритмов в системах обработки данных.

Методы исследования основываются на теории чисел, теории вероятностей, дискретной математики, теории алгоритмов, теории графов и теории множеств.

Научная новизна диссертационного исследования заключается в разработке алгоритмов прямых и обратных преобразований числовой информации из одной принятой СС в другую в СОД, функционирующих в ССОК с использованием таблично-алгоритмических способов обработки числовой информации, позволяющих повысить на 1-2 порядка скорость выполняемых преобразований.

К основным результатам, представляющим новизну исследования, можно отнести следующие:

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

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

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

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

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

ности и достоверности работы. Разработанный оригинальный программный комплекс, использующий предложенные в работе методы и алгоритмы, может быть использован в процессе анализа характеристик методов преобразований данных в ССОК, а также в учебном процессе.

Апробация работы. Основные положения диссертационной работы и вопросы их практического использования докладывались и обсуждались: на II международной научно-практической конференции «Молодежь и наука: реальность и будущее» (Невинномысск, 2009), на III Всероссийской конференции по актуальным проблемам внедрения и развития сектора IT - технологий «Современные информационные технологии в проектировании, управлении и экономике» (Махачкала, 2008,), на IV Всероссийской конференции по актуальным проблемам внедрения и развития сектора IT- технологий (Махачкала, 2009), на V региональной научно-технической конференции (Махачкала, ДНЦ РАН, 2009).

Публикации. По результатам диссертационной работы опубликовано 12 работ, в том числе 9 статей, из них две статьи в научных изданиях, рекомендованных ВАК. Без соавторов опубликовано 4 работы.

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка использованных источников и четырех приложений. Работа изложена на 117 страницах, содержит 34 рисунка, 5 таблиц, список литературы, состоящий из 106 наименований, и 4 приложений.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

Первая глава посвящена вопросам повышения быстродействия СОД и организации в нйх вычислительных процессов. В связи с этим на сегодняшний день достаточно много внимания уделяется вопросам совершенствования вычислительной техники (ВТ), ее элементной базы и математического обеспечения средств и систем сбора, передачи и обработки информации. В связи с этим в нашей стране и за рубежом ведутся интенсивные разработки по созданию новых перспективных средств ВТ. В настоящее время применительно к той или иной структуре вычислительного устройства (ВУ) используются позиционные системы счисления: либо двоичная, ориентированная на решении научно-технических задач, либо двоично-десятичная - на решение планово-экономических задач.

Известно, что в настоящее время нет ни одной системы счисления, удовлетворяющая разработчиков СОД по многим частным критериям. В связи с чем в работе предлагается рассмотреть вопрос об использовании в СОД нескольких СС (комплекса СС) только с одной целью, а именно, повышение быстродействия СОД, за счет организации вычислительного процесса в ком-

плексе СС.

Введем обозначения: Ух- объем вводимых данных, Уг - объем выводимых данных, в словах К, - объем вычислений в операциях применительно к некоторой СОД. Известно, что если У,+У2«У}, то применяется двоичная система счисления, а в случае У,+Уг »V, - двоично-десятичная СС. Если же рассмотреть процесс решения задачи с Ух + К2« У,, то не ясно, в какой системе счисления производить вычисления. Возможны, также ситуации, когда ^ « Уг « К,, и в этом случае требуется провести анализ для выбора наиболее рациональной системы счисления. Аналогичная задача выбора рациональной СС существует и в случае сравнения возможных вариантов по возможным затратам времени.

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

Выбор элементарной СС применительно к той или иной разработке ВУ обуславливается следующими требованиями:

• простота технической реализации;

• минимум оборудования;

• наибольшая помехоустойчивость кодирования цифр;

• точность представления и вычисления Чисел;

• простота выполнения арифметических операций и операций преобразования;

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

• простота формального аппарата для анализа и синтеза цифровых устройств; ■

• удобства работы с вычислительной машиной.

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

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

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

• возможность использования базовой аппаратуры для выполнения операций преобразования, количество различных видов Б которых определяется комплексом систем счисления и выражается по формуле 5 = М (М - 1), где М -количество элементарных систем счисления в комплексе.

Для иллюстрации последних требований рассмотрим КСС, включающую двоичную, двоично-десятичную С С и систему счисления в остаточных классах. Схематическое изображение указанной КСС приведено на рис.1.

2 <=2-10,

Рисунок 1 - Функциональная полнота операционного базиса комплекса СС

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

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

Следует отметить, что в универсальных ВУ традиционной архитектуры используется несколько СС, но в этом случае их выбор определяется типом решаемых задач; в частности, двоичная - для научно-технических задач, а двоично-десятичная - для планово-экономических задач.

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

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

Большинство известных алгоритмов преобразования из СОК в ПСС основаны на китайской теореме об остатках. Данный этап является одним из наиболее трудоемких и обычно выполняется после завершения всех вычислений. Для повышения быстродействия во многих алгоритмах используется преимущества табличных методов, когда в памяти хранятся модули, веса позиционных представлений, базисы и др. При вычислении базисов СОК наибольшие временные затраты связаны с операциями нахождения обратных весов в формуле т1 -5, з1

(mod pt), где m, - целое положительное число, называемое весом ортогонального базиса, <5- - остаток от деления полученной величины на модуль р,.

Рассмотрим математическую модель предлагаемых преобразований из ПСС в СОК на следующем примере. Пусть задано к- разрядное двоично-десятичное число R = (r1,r2,...,rm,...,rt), т = \,к, где гт = {0,1,...,9} - т- ая двоичная тетрада этого числа, которая вычисляется следующим образом:

4

гт = £ аш • 2'~' и может быть записана в координатном виде

rm =(а1т>а2т>аз*>а4т), a™=0vl- Задан также набор модулей СОК Р = (Р1,Р2,...,Р1...../>„), / = 1

; п. Необходимо представить число R в заданном наборе модулей СОК, т.е. осуществить операцию преобразования вида Л=>(а„а2,...,«,,...,а„), где а, =RmodP,, а,

Для решения этой задачи обычно рассматривают процедуру, опираю-

R

щуюся на операцию деления в модульной арифметике: а , = Л-

Р,, где

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

Введем обозначение: в, = (б,,65,.....Ь[) - последовательность остатков,

образующихся в процессе деления й на Тогда выполнено соотношение Ъ'т = ог„, где «о» означает операцию конкатенации. Процедуру получения остатка а, по модулю с учетом того, что Ь'а = 0, можно представить в следующем виде: начиная с т= 1 до т = к последовательно находятся величины Ь'т: Ь'„ = Ъ'тА о гп тоб^. Тогда а, =Ь'„.

Для получения остатков в; = .....Ь'т,...,Ь[) можно воспользоваться также

таблицей соответствия, формируемой отдельно для каждого модуля Р1. Так как для всех т выполнено ъ'п < Р, и Ь'т получается из г>1_, путем приписывания справа одной из цифр от 0 до 9 с последующим делением полученного числа на Р,, то предварительно, перебрав все возможные числа от 0 до Р,-1, приписывая последовательно к каждому из этих чисел одну из цифр от 0 до 9, а затем поделив на Рп получим искомую таблицу. В дальнейшем при реализации алгоритма вместо деления на Р, можно просто выбирать требуемый результат из таблицы. Очевидно, что размер таблицы равен ^хЮ. Таким образом, вычисление а> сводятся к приписыванию очередной десятичной цифры к предыдущему результату и выбору очередного результат из таблицы. Временные затраты этого преоб-

разования пропорциональны к ■■

1Ш. KP,)

, где 1(х) - разрядность числах

Алгоритм преобразования двоично-десятичного числа в СОК по набору модулей Р = (Р1,Р1,...,Р„) может быть представлен следующим образом (Рис.2).

Алгоритм. Входные переменные: Н = (г1,гг,...,гт,...,гк) двоично-десятичная запись числа Л, Р = (Р„Р2,...,Р„) - набор модулей оснований СОК.

Выходные переменные: А = (щ,а2,...,ап), где от, =ЛшодРг

Выше показано что, алгоритм 1 преобразования из ДДС в СОК состоит в последовательном нахождении остатков Ь'т, причем Ь'к = а,, который определяется к-ой комбинацией последовательных промежуточных величин.

Отличие алгоритма заключается в параллельном нахождении величин 6"' для разложения числа Я. Именно, вычисления выполняются по формулам: гт 10""'тойР, =Ь'к1т+1 одновременно по всем / = 1,и и т = к,\. Тогда для нахождения /? = («,,а2.....а„), где а, = Дтос!^., можно воспользоваться алгоритмом для суммирования чисел в остаточных классах по модулям Р = (№,...,Р„) :

Для определения величин Ь'т можно использовать таблицы соответствия, количество которых определяется максимальной разрядностью позиционного числа Я, так как диапазон Б представления чисел в СОК по модулям Р = (Р„Р2.....Р„) определяется как

я

0 = Блок схема алгоритма, реализую-

Рисунок 2 - Блок-схема алгоритма преобразования из ППС в СОК

щего описанный метод, приведен в работе. Наконец, в работе приведен также алгоритм преобразования из двоичной системы в СОК. Разработка алгоритма преобразования чисел из ДСС в СОК по аналогии с алгоритмом 1 осуществляется следующим образом. Пусть дано преобразуемое т- разрядное двоичное число А-(А)2, а также система модулей СОК Р = (Р,,Р2.....Р„). Необходимо определить: о-, = (л)г mod(/ = 1,л). Разобьём исходное преобразуемое »¡-разрядное двоичное число А на s равных компонентов, причем / - ая компонента содержит г, двоичных разрядов. Тогда множество R = {rl,r2,...,rl), j = определяет структуру разбиения исходного преобразуемого двоичного числа А. Согласно данной структуре разбиения, число А может быть представлено последовательностью 10

упорядоченных множеств следующего вида: (Л)2=(К-})> ' = П"> У = где % - - есть значение разряда в исходном представлении числа (Л)2, ко-

торый соответствует / - ой позиции в гу компоненте структуры разбиения числа (Л)2. Тогда число (Л)2 в зависимости от значения гп ] = можно представить в двоичной (г; = 1), четверичной (гу = 2), восьмеричной (г = 3), шестнадцатерич-ной (гу = 4) и т.д. других системах счисления.

На основании этого можно получить таблицы соответствия, представляющие собой результаты деления исходного числа (А)г на модули /¡, Р2, ... , Р„, с нахождением промежуточных остатков А,, Ьг,...,Ь,, именно последовательно дляу=1,2,..., 5 находим (6, =0): ото<1 =6^,;тогда Ь,= а,.

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

Структурная схема устройства преобразования целых чисел из ПСС в СОК, составленная на основе описанного алгоритма, представлена на рис. 3. Приведена общая структура устройства преобразования двоично-десятичных чисел в код остаточных классов, содержащая и независимых блоков, количество которых соответствует набору заданных модулей СОК Р=(Р],Р2>..;Р1,...,Р„). На входы всех п преобразующих блоков по соответствующим" модулям Р поступает исходное число А в последовательном коде, начиная со старшей тетрады. Преобразуемое двоично-десятичное число А, представленное в коде с весами 8,4,2,1. После обработки последней (младшей ) тетрады соответствующим блоком на выходе устройства получим код системы остаточных классов по заданным модулям.

На рис. 4 приведена структура отдельного / -го преобразующего блока для модуля Р„ которая содержит блок памяти (БП), разделенный на ассоциативную часть (АЧ) и информационную часть ИЧ, шины синхронизации ШС1 и ШС2 и группу логических элементов. Работу отдельного / -го преобразующего блока устройства по модулю Л можно описать следующим образом.

По управляющему импульсу (УИ), поданному на ШС 1, на АЧ БП поступают разряды старшей тетрады исходного преобразуемого числа, то есть гп. По указанному адресу из ИЧ БП считывается слово, представляющее собой остаток ¿1, полученный в результате деления числового значения старшей тетрады гп на заданный модуль Р,, то есть г„= ¿>0 шо<1 Р, , представленный в двоично-десятичном коде. Полученный код остатка ¿>1 задерживается на один такт, с помощью элемента задержки. При поступлении второго УИ на ШС 1 на АЧ БП поступает комбинация в виде двух или более тетрад (количество тетрад, необходимых для представления остатка в двоично-десятичном коде, зависит от значения модуля Р) оцЬ\. По указанному адре су из ИЧ БП считывается слово,

представляющее собой остаток Ь2, полученный в результате деления числового значения второй тетрады в совокупности с числовым значением предыдущего остатка Ь\ на заданный модуль Р, , то есть: r2 b\ mod Л = b2- Данный процесс повторяется до тех пор, пока не будут обработаны все тетрады преобразуемого числа А~(г„,г„.и ...,Г|). После обработки последней (младшей) тетрады г, в совокупности с тетрадами, предоставляющими значения остатка b„. i и при наличии УИ на ШС 2, получим искомый результат а,=Ь„, соответствующий преобразованию исходного числа А в код остаточных классов по заданному модулю Pf. r„b„.\ mod Р/=6„=а/.

rm a„modP„ dj mod P,

Рисунок 3 - Структура устройства, служащая для преобразования двоично-десятичных чисел в код СОК на основе приведенного алгоритма

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

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

Пусть задан набор модулей СОК Р = (Р„Рг.....Р„). Введем понятие базиса

следующим образом: с/, =1, с/, = , 1 = Представление базиса {с!,} в СОК

.и

по модулям Р = (Р1,Р2,...,Рп) имеет вид =(0Д...,«,,«„.„..,,а„), то есть остатки по модулям Р1,Р2,...,Р1_, равны нулю.

результат ътсх^Р,

Рисунок 4 - Структура /-го преобразующего блока по модулю Л

Предполагаемый метод преобразования чисел из СОК в двоичный код заключается в представлении исходного числа Л = (а,,а2,...,ал) в виде суммы

А-^С,, где С, = («,',«2,...,^), 1 = 1 ,п - величины, соответствующие остаткам а,.

/■1

При этом параллельно с суммированием в СОК выполняется суммирование слагаемых С, в двоичном коде с целью получения представления числа А в двоичном коде.

Алгоритм вычисления С,, г = йп, выглядит следующим образом. Пусть для а, известно его позиционное представление (в двоичном коде) а, = С,, где как число С, е [1,2.....]. Пусть также известно представление а, в СОК по модулям рирг,...,рщ и Л' = (а|Если А' совпадает по всем остаткам с исходным числом, то есть а,=щ , то тогда С,=0 для » = 2Г", и исходное число Л в

двоичном коде будет равно Л = С, = .

м

Допустим, что , причем а/=ак для всех Л <_/; тогда С*=0 для к=2,... 1,, С/£0. Слагаемое Су определяется следующим образом. Для определения в разложении (ог„а2' -.ап) числа Л остатка а, по модулю Р} необходимо к А' добавить частичную сумму С, такую, чтобы скорректировать остаток а/ до а} на величину г) = а/ , если а,- а/>О или г7=а/-а7+/',, если а,- а/<0. Используя весовой коэффициент Ь], находим = =(0Д...Дг,с/+1,С/+2,...,С„/)сок ивычисляем

новое значение Л': А' А' +

= (ог„а2...,а; +г,«;ч1 +С/+1.....а'„ + С„У),

где нижний индекс «2» указывает на запись числа в двоичной системе. Здесь

af+r=a.j. Полагаем: о^, ......а'„ :=< +С„/. Тогда А'=(аи а2 , ...,а/,

<Xj+\ ,...,а„ ).

Если в результате операции суммирования А' »А совпадают по всем остаткам а{ и a¡ для / = j+l,n, то С,=0 для ; = j + l,n. Если же имеются не совпадающие остатки а{ и а, для i >j, то х=.. .=C,.i=0. Значение слагаемого С, находится аналогично C¡. После того как слагаемые С,, / = \п определены, находим позиционное представление числа А операцией суммирования в двоич-

и

ной системе счисления: Л = . Описанный выше метод преобразования из

СОК в ПСС может быть формализован в виде следующего алгоритма.

Пусть исходное число в СОК имеет следующее представление: A=(aua2,...,cti,...,an), и пусть = (r¡xx,J&>k,-,X¿ok) обозначает текущий сумматор, функционирующий в СОК, где Л£ок представляет собой остаток по модулю Pt. Обозначим через R^ сумматор, функционирующий в двоичной системе счисления. Введем переменную L, содержимое которой будет указывать

номер i первого по порядку еще не определенного слагаемого С, в разложении

»al

Алгоритм

1. Определить для ai позиционное представление, то есть ai = С\, где Qe {0,1,... ,Р] -1}, а также его представление в СОК/Г= (а/, а2\..., <х„').

2. Загрузить в RC0K и Лппс число C¡, то есть Дсок'-~ (аГ, а2', ... , а„'),

Rncc'-~(Cih ■

3. Присвоить переменной L значение 2.

4. Организовать цикл по проверке на совпадение a¡ и /J¿OK для i- L,п. По окончании цикла перейти к пункту 14.

5. Определить наименьший номер j, для которого a¡ ф R^ok .

6. Вычислить в СОК величину г -а, -.

7. Вычислить С j = bj -dr и при г <0 выполнить r:=r+Pj.

8. Выполнить операцию сложения в двоичной СС: (Лпсс)г~ (Rncch+Cj.

9. Записать представление С,-в СОК: С, = (0Д...Д r,q,q4,,...,C;):

10. Выполнить операцию суммирования в СОК: Rcok- =</?сок+С¡=(аиа2,.. .,aj,aj+l,.. .,а„).

11. Если содержимое Rqok совпадает с исходным числом, то перейти к пункту 14. Иначе перейти к пункту 12.

12. Присвоить переменной L значение /И.

13. Если содержимое L больше п,то перейти к пункту 14; иначе перейти пункту 4.

14. Конец.

Принцип построения и работы структуры устройства преобразования чисел из СОК в двоичный код с вычисляемыми слагаемыми гу, Ь[, с!г Сп поясняется на рис.5. В схеме используются следующие обозначения: Я™" - накапливающий сумматор, функционирующий в СОК по модулю Р;, у = £й;. (Рппс)г -накапливающий двоичный сумматор; Х\, г2,..., ^ - управляющие шины коммутаторов. В работе приведен конкретный пример реализации описанной схемы.

Преобр. число Л тк

Рисунок. 5 - Струю-ура устройства первого вида преобразования чисел из СОК в двоичный код с вычисляемыми слагаемыми.

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

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

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

для каждого конкретного основания Р, ССОК определяется величиной этого основания.

Пусть имеется п -битовый процессор и используется ССОК, основание п = (Р^Р^...^), причем к делит п. Тогда при условии, что длины всех Р, приблизительно одинаковы, размер таблицы 1{Р,)» j. В частности, если и =128, к 128

=8, то 1(Р,)«— = 16. Отсюда выводим, что каждая операция (сложение, умно-8

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

В работе предлагается следующий алгоритм сложения двух чисел. Предположим, что имеется и параллельных сумматоров, и основание СОК ж = {РиР1,...,Рп) выбрано и зафиксировано. В процессе выполнения вычислений необходимо найти сумму чисел А и В. Опишем алгоритм выполнения вычислений.

I. Все числа преобразовываются из позиционной системы счисления в модулярное представление в СОК в базисе модулей в заданном наборе ж модулей СОК, то есть осуществляются операции преобразования вида А=>(а„а2,...,ая), В =>(/?„ А.....Д,) и т.д.

II. Если число процессоров t меньше и, то модули основания упорядочиваются в порядке убывания: я = (Pi,Pi,...,Pn), где Р. > >...>Л.). Запоминаются порядковые индексы (i„i2,...,»,) чисел Pi,P2,...,P„ в исходном наборе л. Если число / г п, то этап II пропускается.

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

1) Для 1 = 1,/ на /-ом процессоре осуществляется операция сложения по модулю Р/ чисел а, и Д. на основе CLA-алгоритма.

2) По мере освобождения каждого процессора выбираются очередные (по порядку расположения модулей Р\,Рг,...,?„) числа ач и ß^ и складываются по

основанию Pj.

IV. После выполнения всех вычислений выполняется обратное преобразование из СОК в ПСС.

Проведена оценка быстродействия предлагаемого алгоритма: сложение

будет выполнено не более чем за 1 + 2 • log2 ^ тактов работы, что при к> 1 существенно меньше, чем при использовании CLA-алгоритма. Отметим, данная оценка является гарантированной, то есть выполняемой при любых входных данных.

В работе проводится сравнение предлагаемого алгоритма с другими наи-

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

В главе предлагается также процедура использования ССОК в процессе обмена данными ограниченного доступа. Традиционная технология обеспечения защиты информации ограниченного доступа обычно предполагает использование методов шифрования. Однако, требования, предъявляемые к подобным системам, достаточно строгие и, как следствие, громоздкие в реализации и затратные в эксплуатации, что часто делает их малоприемлемыми и затруднительными для использования. В работе предлагается процедура закрытия информации, опирающая на использование СОК. Уровень стойкости к злоумыш-' ленным действиям предлагаемой процедуры ниже, чем у существующих методов шифрования, но процедура имеет одно важное достоинство: она достаточно проста в реализации и вполне приемлема для большинства служебных и приватных сообщений, передачи конфиденциальной информации. Безусловно, для ■" данных передачи особо важных и секретных данных должны быть задействованы более стойкие методы й процедуры; в частности, методы шифрования. Другие достоинства предлагаемой процедуры по сравнению с существующими, системами шифрования:

1) отсутствие необходимости обмена ключами (или ключом) шифрования;

2) доступность для использования всеми физическими и юридическими субъектами, которые желают обменяться сообщениями именно с данным физическим или юридическим субъектом и знают или могут получить необходимые;, общедоступные параметры указанного субъекта; например, для юридического субъекта - наименование, юридический адрес, сфера деятельности и другие; для физического субъекта - фамилия, имя, отчество, возраст и другие. Список этих параметров согласовывается предварительно и может включать параметры, которые добавляет сам субъект к списку общесогласованных параметров.

Предлагается следующая процедура их выбора. Пусть Рх,Р2,...,Рп основания СОК.

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

Рассмотрим вначале действия субъекта, передающего информацию.

1. Исходные данные о субъектах, передающем и принимающем информацию, записываются последовательно в виде строки; к этим данным могут быть.

добавлены (по договоренности сторон) конфиденциальные сведения, известные только передающей и принимающей сторонам, а также дописываются дата и интервал времени передачи с точностью до одной минуты. Полученная строка оцифровывается любым способом; например, путем сопоставления каждому знаку его ASCII кода. В результате получаем число D, однозначно соответствующее данной паре субъектов - передающего и принимающего информацию.

2. Полученное число D разбивается на блоки, каждый из которых как число не превосходит числа N. Все блоки для данного числа складываются по

Г л'"

модулю N; в результате получается число М. Если М &

, то М заменяется

на N-M, так что всегда выполнено неравенство

_ 2 .

<.М <N. Очевидно, зна-

N] .2.

чение М зависит от атрибутов как передающего субъекта, так и принимающего.

3. Из базы простых чисел выбирается наибольшее простое число Р,

меньшее числа М. Полагаем Р0=М Я = Р вычисляем Л, =1-4 и

находим Q2 = P0mod(P, [R,]), где [ ] - знак целой части числа. (Коэффициент R, введен для того, чтобы, с одной стороны, число п простых чисел в окончательном наборе Р1,Р2,...,Р„ не оказалось малым, а с другой стороны, соседние простые числа в наборе достаточно сильно различались. Дополнительные пояснения по выбору Л, и /ц, приводятся ниже.) Выбираем из базы простых чисел наибольшее простое число Р2, меньшее Q2 • Процедура формирования простых чисел продолжается аналогичным образом по формулам:

6J+1 = PhX mod • j), где R = 1-4—^———^ и Рц\ - наибольшее целое

число, меньшее Qj+i. Процедура продолжается до тех пор, пока либо достигнем « = «о, либо при некотором у = л + 1 получим ^ =1. Так как Rj< 1, то очевидно PJti < Pj для всех j.

4. Набор чисел Р1,Р2,...,Р„ и есть искомый. Отметим, в полученном наборе простые числа расположены не в порядке возрастания, как описано выше, а в порядке убывания.

. 5. Передаваемое сообщение, аналогично пункту 2, записывается в виде текстовой строки, оцифровывается (получаем число С) и разбивается на блоки

я

Ct,C2,...,Cr, каждый из которых по величине не превосходит значения Р = fj^ •

м

Затем каждое из чисел на основе одного из разработанных в работе алгоритмов

записывается в СОК. Получаем множество наборов Л = {(c,.,,cl2.....с)л,),; = 1,г}, где

(напомним) с(> = С, mod Pt. Сформированный набор Л с приписанным именем передающей стороны и посылается оппоненту по процессу приема-передачи.

Аналогичные действия выполняются принимающей стороной. Проведен анализ возможных значений параметров алгоритма.

Оценена стойкость предлагаемого метода закрытия передаваемых данных ограниченного доступа. Именно, показано, что в случае прямого перебора среднее время нахождения оснований СОК имеет порядок // = (2' — 2'~d)4, где числа к и / связаны соотношением к-1~п,п- разрядность чисел, которые преобразуются на основе СОК; lnl-d - верхняя и нижняя границы для числа битов в записи отдельных простых чисел в основании. В частности, для 64-битового процессора можно взять к=8, /=8 и d=2. Тогда для процессора, имеющему тактовую частоту 5 Ггц/сек, потребуется время, равное 11,7 лет непрерывной работы процессора. Последнее означает, что злоумышленник практически не имеет никаких реальных возможностей обнаружить истинный набор оснований Pi,P2,...,Pk. Приведена процедура была использования описанного алгоритма применительно к процессу обмена данными между морскими судами.

Для проверки возможностей разработанных выше алгоритм автором был разработан программный продукт. Основное его назначение - программная реализация всех приведенных в работе алгоритмов преобразования числовых данных в СОК и из СОК в ППС с целью:

- сравнения возможностей различных вариантов реализации алгоритмов преобразований;

- разработки рекомендаций по выбору наиболее приемлемых параметров алгоритмов.

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

На основе разработанного программного продукта проведено сравнение быстродействий алгоритмов преобразований из ППС и ДЦС в СОК, а также обратных преобразований. Для обеспечения более высокого уровня независимости испытаний было выполнено пять циклов по 100 преобразований в каждом. Вначале каждого цикла требуемые исходные сто наборов модулей оснований Р заранее были сформированы с использованием таблиц простых чисел. Результаты экспериментов приведены в следующей таблице (таблица 1).

Таблица 1

Характер преобразования Время работы алгоритма (сек)

ДЦС=> СОК=>алг.1 ДДС=>СОК=>алг.2 СОК =-ДЦС=>алг.1 СОК =>ДЦС=> алг.2

Номер цикла 1 0,723 0,252 0,967 0,346

2 0,708 0,261 1,004 0,352

3 0,729 0,247 0,993 0,354

4 0,71 0,253 0,997 0,361

5 0,719 0,256 0,994 0,357

Среднее значение 0,718 0,254 0,991 0,354

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

Были также проведены три эксперимента по попытке взломать закрытое на основе СОК сообщение. Параметры алгоритма преобразования взяты в соответствии с приведенными в работе рекомендациями применительно к обмену сообщениями между морскими объектами, то есть длина блока N = 1024 бит, число простых чисел в основании А=4 бита, размер каждого простого числа - не более /=8 бит и не менее 1-й = 6 бит (¿=2). Исходный текст состоял из одного блока длины N. В программный продукт был вставлен модуль, в котором перебирались возможные значения наборов оснований, удовлетворяющие сформулированным ограничениям на к, I и с1. Затем в соответствии с алгоритмом обратного преобразования по СОК находилось исходное число, которое сравнивалось с первоначально выбранным. В случае совпадения программ должна была остановиться, выдав сообщение об удачном вскрытии текста. Начальное значение набора Р выбиралось случайным образом из базы простых чисел в соответствии с заданными ограничениями на к, 1 и <1. Если в процессе перебора достигалась верхняя граница ограничений,, то заново выбиралось начальное значение Р, и процедура перебора повторялась с новым начальным значением. Время непрерывной работы программы по отдельным экспериментам: 22 час., 24,5 час. и 27 час. Результаты: все три эксперимента не привели к вскрытию искомого набора. Таким образом, разработанный алгоритм оказался стойким в рамках тех ограничений, которые были описаны выше.

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

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

В приложении приведены классические схемы сложения чисел в современных процессорах, исходный текст программного продукта, основные экранные формы разработанного программного продукта и акт о внедрении разработанного программного продукта в учебный процесс ГОУ ВПО «ДГТУ».

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

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

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

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

4. Предлагается алгоритм сложения двух чисел в СОК с учетом возможности распараллеливания вычислений, приведена структурная схема аппаратной реализации этого алгоритма. Получена верхняя оценка числа тактов работы алгоритма в зависимости от числа имеющихся процессоров и разрядности используемых чисел. Данная оценка может быть использована для выявления требуемого числа параллельных процессоров (ядер) в зависимости от ограничений на время выполнения операции сложения и связанных с ней других арифметических операций.

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

6. Описана процедура оценки приемлемых значений параметров предлагаемых алгоритмов процесса обмена сообщениями. Указанные параметры конкретизированы применительно к процессу обмена сообщениями между морскими суднами. Оценена стойкость предлагаемого алгоритма закрытия данных, и показано, что для раскрытия данных, закрытых данным алгоритмом, могут потребоваться годы непрерывной работы современного процессора при использовании метода прямого перебора вариантов. В частности для 64-битового процессора это время составляет порядка 9 лет.

7. Сформулированы требования, предъявляемые к программному продукту. Создан программный продукт, реализующий разработанные алгоритмы с учетом сформулированных требований. Проведены тестовые проверки правильности работы программных компонентов.

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

9. СОК и разрядно-параллельных вычислений является одним из перспективных направлений развития средств вычислительной техники.

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

Публикации в ведущих рецензируемых изданиях, рекомендованных ВАК РФ

1. Исмаилов Ш-М.А., Магомедов Ш.Г. Алгоритмы и структуры преобразования числовых данных из позиционной системы счисления в систему остаточных классов// Научно-технические ведомости СПбГТУ. Информатика. Телекоммуникации. Управление. - 2008. -№ 5(65). - С. 159-169. (1,1/0,55).

2. Магомедов Ш.Г. Использование системы остаточных классов для организации передачи и приема данных морскими судами И Вестник Астраханского государственного технического университета. Серия: Морская техника и технология. - 2010. -№2. - С. 44-46. (0,31).

Публикации в других изданиях

3. Магомедов Ш.Г. Разрядно параллельный сумматор и его применение в преобразовании чисел // Современные информационные технологии в проектировании, управлении и экономике: материалы Ш Всероссийской конференции по актуальным проблемам внедрения и развития сектора IT- технологий, 22-25 сент. 2008 г. - Махачкала: ДГТУ, 2008. (0,31).

4. Исмаилов Ш-М.А., Магомедов Ш.Г. Разработка структуры и алгоритма для преобразования двоично-десятичных чисел в код остаточных классов // Современные информационные технологии в проектировании, управлении и экономике: материалы III Всероссийской конференции по актуальным проблемам внедрения и развития сектора IT- технологий, 22-25 сент. 2008 г. - Махачкала: ДГТУ, 2008. (0,55/0,28).

5. Магомедов Ш.Г. Алгоритм преобразования двоично-десятичных чисел в систему остаточных классов // Молодежь и наука: реальность и будущее: материалы II Международной научно-практической конференции.- Невинно-мысск: НИЭУП, 2009. (0,34).

6. Исмаилов Ш-М.А., Магомедов Ш.Г. Разрядно параллельный алгоритм и структура устройства умножения двоичных чисел // Информационные и телекоммуникационные системы: информационные технологии в научных и образовательных процессах: материалы V Региональной научно-технической конференции, 18-20 сект. 2009 г. - Махачкала: ДНЦ РАН, 2009 г. (0,65/0,32).

7. Магомедов Ш.Г., Джамбулатова А.И. Представление в системе счисления в остаточных классах рациональных чисел // Современные информационные технологии в проектировании, управлении и экономике: материалы IV Всероссийской конференции по актуальным проблемам внедрения и развития сектора IT- технологий, 22-25 сент. 2009 г. - Махачкала: ДГТУ, 2009. (0,12/0,06).

8. Магомедов Ш.Г. Алгоритм и структура преобразования чисел из системы остаточных классов в двоичный код с вычисляемыми слагаемыми // Современные информационные технологии в проектировании, управлении и экономике: материалы IV Всероссийской конференции по актуальным проблемам внедрения и развития сектора IT- технологий, 22-25 сент. 2009 г. - Махачкала: ДГТУ, 2009. (0,5).

9. Исмаилов Ш-М.А., Магомедов Ш.Г. Система счисления остаточных классов и ее применение в ЭВМ// Современные информационные технологии в проектировании, управлении и экономике: материалы IV Всероссийской конференции по актуальным проблемам внедрения и развития сектора IT- технологий, 22-25 сент. 2009 г. - Махачкала: ДГТУ, 2009. (0,66/0,33).

Формат 60x84 1/16. Бумага офсет 1. Печать ризографная. Гарнитура Тайме. Усл.п.л. 1,5. Заказ № 084-11 Тир. 100 экз. Отпеч. в тип. ИП Тагиева Р.Х. г. Махачкала, ул. Батырая, 149. 8 928 048 10 45 "ФОРМАТ"

Введение.

Глава 1. Система представления числовых данных и особенности их применения в информационных системах.

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

1.2. Выбор систем счисления.

Выводы.

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

2.1. Алгоритм и структура преобразования двоично-десятичных чисел в код остаточных классов первого типа.

2.2. Алгоритм и структура преобразования двоично-десятичных чисел в код остаточных классов второго вида.

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

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

Выводы по главе 2.

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

3.1. Алгоритм и структура преобразования первого типа в код двоично-десятичных чисел из кода остаточных классов.

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

Выводы по главе 3.

Глава 4. Практические приложения полученных результатов.

4.1. Использование разработанных алгоритмов в сумматорах.

4.2. Использование СОК для организации передачи и приема данных.

4.3. Разработка программного продукта, реализующего разработанные алгоритмы.:.

Выводы по главе 4.^.

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

Практика эксплуатации ЭВМ показывает, что имеющийся в настоящее время парк параллельных вычислителей с производительностью не ниже 100 миллионов операций/с, удовлетворяющий пользователей по быстродействию сегодня, уже в ближайшем будущем может не соответствовать техническим параметрам из-за постоянного роста сложности решаемых задач, требующих на 1-3 порядка более высокой производительности, совершенной памяти и развитого математического обеспечения.

В связи с этим в нашей стране и за рубежом ведутся интенсивные разработки по созданию новых перспективных средств ВТ, практическая реализация которых намечена на 2010-2015 годы [1-3].

Одним из главных направлений развития систем ВТ является разработка высокопроизводительных ЭВМ, сочетающих в комплексе современную элементную базу, развитое математическое обеспечение, достаточно большую емкость оперативной и внешней памяти с производительностью в сотни миллионов операций/с, что отмечается в многочисленных работах, например [4-8].

Это обусловлено тем, что среди различных научно-технических и планово-экономических задач, решаемых на ЭВМ, с каждым годом все больший удельный вес приобретают вычислительные задачи большого объема, многие из которых при этом должны решаться в режиме реального времени [8]. К таким задачам можно отнести аэродинамику, метеорологию, машинную графику, ядерную физику и физику плазмы, обработку изображений, задачи искусственного интеллекта, числового моделирования непрерывных полей, а также задачи финансового моделирования экономики [4, 9].

Характерными особенностями указанного класса задач является большой объем обрабатываемых данных, достигающий порядка 1011 бит информации. Такие задачи требуют выполнения огромного количества арифметических операций (АО), порядка 1014. Даже при использовании самых мощных на сегодняшний день ЭВМ решение задач подобного класса может затягиваться на многие дни, тогда как исследователю часто необходимо иметь в несравненно более короткие сроки. Для других задач, например, связанных с расчетом прогнозов погоды, решение должно быть получено не более чем через час , что принуждает разработчиков искать более эффективные пути построения вычислительных устройств (ВУ) высокой производительности, на несколько порядков выше по сравнению с производительностью существующих ЭВМ. Безусловно, в ВС, ориентированных на решение вычислительных задач большого объема, предъявляются самые высокие требования к производительности, объему оперативной и внешней памяти, точности вычислений, надежности и т.д., указанные в [9-30].

Анализ показывает, что появление ЭВМ с производительностью в миллиарды операций/с. значительно повысит интерес к различным численным алгоритмам, потребность в которых диктуется все усложнившимися запросами фундаментальных и прикладных исследований и в особенности задачами управления в реальном масштабе времени сложными техническими системами. Определяющим требованием при построении таких структур ЭВМ является практическая независимость времени вычислений от числа одновременно обрабатываемых данных. Например, для решения в приемлемое для пользователя время осредненных по Рейнольдсу уравнений Навье-Стокса, встречающихся в задачах аэродинамики, для 10 миллионов точек, необходим быстрый доступ к оперативной памяти с объе

1 "Ч мом 300 миллионов слов, а сама ЭВМ должна обладать быстродействием не менее 10 ме-гафлоп/с.

Наиболее перспективным направлением создания высокопроизводительных ЭВМ считается разработка параллельных вычислителей. Параллельные ЭВМ широко применяются в различных сферах науки и техники, но чаще всего их используют для численного моделирования вычислительных задач большого объема. В таком применении параллельные вычислители способствуют получению новых знаний, позволяя пользователям путем моделирования справляться со сложнейшими проблемами, которые не могут быть решены на вычислительных устройствах (ВУ) с традиционной архитектурой; изучить явления, труднодоступные для экспериментального исследования; подтверждать правильность тех или иных теоретических выводов [31-42]. Именно эти обстоятельства определяют значительный интерес к теории построения параллельных ЭВМ.

Однако, наряду со значительными успехами, достигнутыми в теории архитектуры параллельных вычислителей, традиционно функционирующих в двоичной системе счисления (СС), еще недостаточно исследованы возможности, связанные с оптимизацией способов кодирования потоков числовых данных (ПЧД). Это служит дополнительным резервом роста производительности ЭВМ. Так, представляется целесообразным использование в параллельных ЭВМ не только двоичной системы счисления, главный недостаток которой наличие "длинных" межразрядных переносов, влияющих на быстродействие выполнения арифметических операций, а некоторого комплекса систем счисления, включающего как позиционные, так и непозиционные системы счисления. Это способствует значительному сокращению времени реализации арифметических операций над ПЧД за счет их выполнения в наиболее рациональной системе счисления.

Проблема использования СОК в процессе преобразования данных является не новой. Впервые она была поставлена в пятидесятые годы прошлого века, и были предприняты попытки по практической реализации данной идеи в рамках пробкта «Алмаз», при создании ЭВМ Т-340А и К-340А и суперЭВМ 5Э53. Однако, после двадцати лет исследований все работы были практически приостановлены, по-видимому, ввиду недостаточно развитой элементной базы того времени. В настоящее время существующая элементная база позволяет не только реализовать проекты того времени, связанные с СОК, но и значительно усовершенствовать многие идеи; в частности, применительно к проблемам безопасности и безошибочности вычислений. Поэтому теоретические исследования и практические работы в данной области в последние годы активизировались.

Большой вклад в развитие теоретических и практических вопросов, связанных с СОК, внесли отечественные исследователи и ученые Акушский И.Я., Юдицкий Д.И., Коляда А.А, Исмаилов Ш.-М.А., Червяков Н.И, и др, среди зарубежных можно выделить работы М.А. Soderstand, D.D.Miller, G.A. Jullien, M. A Jenkins, В J. Leon и др.

С другой стороны, представляется целесообразной разработка арифметических узлов ЭВМ, ориентированных на реализацию «-арной операции суммирования, часто встречающейся при выполнении широкого спектра арифметических выражений. Степень значимости указанной операции отмечена в работах, например, И.В.Прангишвили, Я.И.Фета, Б.Н.Малиновского, В.Муртафа [43-48]. Отсутствие в настоящее время таких узлов приводит к необходимости организации попарной обработки ПЧД, что существенно снижает производительность параллельных ЭВМ.

Рассмотренные подходы могут быть использованы совместно для построения высокопроизводительных ЭВМ, функционирующих в комплексе систем счисления и содержащих арифметические узлы, выполняющие операцию параллельного суммирования чисел, с использованием разрядно-параллельных способов обработки ПЧД. Очевидно, что такая организация структуры ЭВМ требует преобразования числовой информации из одной системы счисления в другую, а следовательно, необходима разработка быстродействующих алгоритмов его выполнения [49-54].

Также следует отметить, что проблему повышения производительности необходимо решать в тесной взаимосвязи с задачей обеспечения точности вычислений [31,55-62]. Требования к высокой точности ВУ приобретает особую значимость при решении класса так называемых плохообусловленных задач и алгоритмов, где не допускается накопление ошибок округления [14, 63]. Значение этих ошибок уменьшается аппаратно путем удлинения разрядной сетки сумматоров, что влечет за собой увеличение аппаратурных затрат и не приводит к полному устранению указанных ошибок. Это требует поиска алгоритмических способов, связанных с применением новых нетрадиционных методов и систем счисления для представления и обработки чисел.

Этого можно достигнуть прежде всего средствами специального кодирования, наиболее широкий интерес из которых представляет система счисления в остаточных классах (ССОК). Ей присущи высокие скорость вычислений и точность их результатов, обусловленные, соответственно, отсутствием межразрядного переноса между цифрами числа и отсутствием операции округления результатов [6, 56, 64, 65].

Многие алгоритмы методов вычислений в непозиционных СС разработаны в рамках теории чисел [10, 66-73]. Однако, нерешенной осталась проблема оперативного фиксирования выхода результата за пределы диапазона применяемой ССОК и определения количественной меры возникшего переполнения, позволяющей его разрешения и восстановление истинной величины результата и ведущей к существенному снижению аппаратно-временных затрат, поскольку до сих пор традиционным путем избегания переполнения являлось увеличение числа или величин модулей ССОК с непосредственным увеличением аппаратурных и временных затрат.

Повышение быстродействия вычислительных устройств наряду с использованием прогрессивных интегральных технологий и скоростных табличных методов вычислений идет в направлении временного и пространственного распараллеливания алгоритмов и структур этих устройств, связанного с увеличением аппаратурных затрат [65, 74-82].

Компромиссным решением возникшего между быстродействием и аппаратурными затратами противоречия является применение принципов разрядно-параллельной обработки, при которой аргументами операции выступают не сами числа, а их разрядные срезы, состоящие из одноименных разрядов [83, 84].

До сих пор разрядно-параллельные вычисления и вычисления в ССОК развивались независимо друг от друга. Представляет практический, в определенной степени научный интерес, задача объединить достоинства обоих направлений развития структур ЭВМ. Этим объясняется необходимость исследования принципов построения разрядно-параллельных процессоров безошибочной обработки вещественных чисел непозиционных СС, обладающих высокой производительностью прежде всего за счет автоматической коррекции результатов вычислений, а также достаточно высоким уровнем надежности и защищенности данных [85 - 90].

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

Традиционная, координатная форма представления комплексных чисел посредством выделения в них действительной и мнимой частей, использовавшаяся, например, в цифровой фильтрации с помощью комплекснозначного преобразования Мерсена, не дает ожидаемого повышения эффективности комплексных вычислений. Прорыв в области двоичных комплекснозначных параллельных вычислений в первые был осуществлен в [91, 92], в которых в практику указанных вычислений была введена бескоординатная форма представления комплексных чисел в системе с основанием (-1+1) [93, 94], а также благодаря изящной гауссовой идее изоморфизма между комплексными вычетами по комплексному модулю и его вещественными вычетами. Несмотря на то, что основы разрядно -параллельных вычислений и структур рассмотрены в работах, но практически в них не рассматривались вопросы обработки комплексных чисел, представленных в системе с основанием (-1+1) и в СОК с комплексными основаниями. Не рассматривались также вопросы структурной организации соответствующих арифметических процессоров.

Следует отметить также, что до настоящего времени в литературе не исследованы вопросы организации разрядно-параллельных арифметических устройств (АУ) с точки зрения выбора оптимального комплекса систем счисления, разработки и исследования алгоритмов и структур параллельного суммирования и других арифметических операций на их основе, прямых и обратных преобразований ПЧД, с использованием базового ядра, а также принципы комплексирования процессорных элементов (ПЭ), являющихся основой построения высокопроизводительных ВУ [95-102].

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

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

Объектом исследованияявляются устройства преобразования данных в комплексе систем счисления.

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

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

Поставленная цель достигается решением следующих задач:

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

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

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

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

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

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

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

К основным результатам, представляющим новизну исследования, можно отнести следующие:

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

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

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

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

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

Апробация работы. Основные положения диссертационной работы и вопросы их практического использования докладывались и обсуждались: на II международной научно-практической конференции «Молодежь и наука: реальность и будущее» (Невинномысск, 2009), на III Всероссийской конференции по актуальным проблемам внедрения и развития сектора 1Т - технологий «Современные информационные технологии в проектировании, управлении и экономике» (Махачкала, 2008,), на IV Всероссийской конференции по актуальным проблемам внедрения и развития сектора 1Т- технологий (Махачкала, 2009), на V региональной научно-технической конференции( Махачкала, ДНЦ РАН, 2009) .

Публикации. По результатам диссертационной работы опубликовано 12 работ, в том числе 9 статей, из них две статьи в научных изданиях, рекомендованных. Без соавторов опубликовано 4 работы.

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка использованных источников и четырех приложений. Работа изложена на 117 страницах, содержит 34 рисунка, 5 таблиц, список литературы, состоящий из 136 наименований и 4 приложений.

Выводы по главе 4

1. В главе предлагается конкретный алгоритм сложения двух чисел в СОК и приведена структурная схема аппаратной реализации этого алгоритма. Проводится сравнение данного алгоритма с другими известными алгоритмами сложения двух чисел. Перечисленными достоинства предлагаемого алгоритма, наиболее важным из которых является возможность эффективного распараллеливания процесса суммирования и тем самым повышения быстродействия выполнения операции суммирования в процессорах вычислительных устройств.

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

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

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

5. Сформулированы требования, предъявляемые к программному продукту. Создан программный продукт, реализующий разработанные алгоритмы с учетом сформулированных требований. Проведены тестовые проверки правильности работы программных компонентов.

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

Заключение

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

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

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

4. Предлагается алгоритм сложения двух чисел в СОК с учетом возможности распараллеливания вычислений, приведена структурная схема аппаратной реализации этого алгоритма. Получена верхняя оценка числа тактов работы алгоритма в зависимости от числа имеющихся процессоров и разрядности используемых чисел. Данная оценка может быть использована для выявления требуемого числа параллельных процессоров (ядер) в зависимости от ограничений на время выполнения операции сложения и связанных с ней других арифметических операций.

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

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

7. Сформулированы требования, предъявляемые к программному продукту. Создан программный продукт, реализующий разработанные алгоритмы с учетом сформулированных требований. Проведены тестовые проверки правильности работы программных компонентов.

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

1. Исмаилов Ш-М. А. Теория и применение разрядно-параллельных процессорных эле-ментов обработки числовых данных в комплексе систем счисления. / Диссерт. на со-иск. учен, степени д.т.н. Махачкала, 1996. - 535с.

2. Коляда A.A., Чернявский А.Ф. Модулярные вычислительные структуры: вчера, сегодня, завтра. // Материалы международной научной конференции «Модулярная арифметика». http://www.computer-museum.ru/histussr/sokconfD.htm

3. Гербер К. Дж. Архитектура высокопроизводительных систем. М., Наука, 1985. - 272с.

4. Воеводин В.В, Воеводин Вл.В. Параллельные вычисления. СПбТ: БХВ-Петербург,2002. 608 с.

5. Перспективы использования параллельной архитектуры для создания ЭВМ со сверхвысокой производительностью. Экспресс-информация. Сер. вычислительной техники. -М.: ВИНИТИ, 1985, N 27, с. 1-14.

6. Егоров В.М., Косцов Э.Г. Перспективы создания цифровых высокопроизводительныхвычислительныхустройств.//Автометрия,N 1, 1985.-с. 114-125.

7. Инютин С.А. Модулярные вычисления для задач большой алгоритмической сложности.//Материалы международной научной конференции «Модулярная арифметика». -http://www.computer-museum.ru/histussr/sokconfO.htm

8. Коляда A.A. Модулярные структуры конвейерной экспресс обработки цифровой информации в измерительно-вычислительных системах физического эксперимента. / Диссерт. на соиск. учен, степени д.т.н. Минск, 1991.

9. Самарский А.А Николаев Е.С. Методы решения сеточных уравнений. М., Наука, 1978.- 589 с.

10. Тихонов А.Н., Арсенин В.Я. Методы решения некорректных задач. М., Наука, 1986.288 с.

11. Форсайт Дж., Малькольм. М., Моулер К. Машинные методы математических вычислений.-М.: Мир, 1980.-276 с

12. Шауман A.M. Основы машинной арифметики. JI:, Изд-во ЛГУ, 1979. -312с.

13. Aaron R., Houg Т. L., Capps С. D. Optical computing using residue arithmetic//AIAA Cornput. Aerosp. 6 Conf. (Wakifield. Mass., 7-9 Oct;, 1987). CollectTechn. Pap. Washington, D.C, 1987. P. 207-212.

14. Boehm H and Cartwright R. Exact real arithmetic, formulating real numbers as functions. In David A. Turner, editor, Research Topics in Functional Programming, chapter 3,Addison-Wesley, 1990, pages 43-64.

15. Boehm H. J., Cartwright R., O'Donnel M. J., Riggle M. Exact real arithmetic, a case study in higher order programming. Proc. of the ACM conference on Lisp and functional programming, 1986.August, P.162-173.

16. Chang P. R., Lee С S. G. Residue arithmetic VLSI arra, architecture for manipulator pseudoinverse Jacobian computation. Proc. IEEE Int. Conf. Rob. and Autom. (Philadelphia. Pa, 24-29 Apr. 1988). 1988. Vol. 1. Washington, D. C. P. 297-302.

17. Edalat A., Potts P J. A new representation for exact real numbers. Electronic Notes in Theoretical Computer.Science, 6, 1997.

18. Edalat A., M.H. Escardo. Integration in Real PCF. // In Proceedings of the Eleventh Annual IEEE Symposium on Logic In Computer Science, New Brunswick, New Jersey, USA, 1996, p 382-393.

19. Escardd M.H. PCF extended with real numbers: A domain-theoretic approach to higher-order exact real number computation. Technical Report ECS-LFCS-97-374, Department of Computer Science, University of Edinburgh, December 1997.

20. Froment A. Error Free Computation: A Direct Method to Convert Finite-Segment p-adic

21. Numbers into Rational Numbers // IEEE Trans, on Comput., 1983, Vol. C-32, N 4, P 337343.

22. Gregory R. T. The use of Finite-segment p-adic arithmetic for exact computation. BIT,18,1978,282-300.

23. Heckmann R . The appearance of big integers in exact real arithmetic based on linear fractional transformations. In Proc. Foundations of Software Science and Computation Structures, Lisbon, 1998.

24. Otsokov S.A., Ismailov S-M.A. Application of Methods Error-free Calculations in Hydrology // International Conference on Computational Fluid Dynamics, ICCFD, Moscow, Russia, 2003, P. 206-208.

25. Soderstrand M. A. Escott R. A. VLSI implementation in multiple-valued logic of an FIR digital filter using residue number system arithmetic/ЯЕЕЕ Trans, on Circuits and Syst. 1986. Vol. CAS-33, N 1. P. 5-20.

26. Vuillemin J. E. Exact real computer arithmetic with continued fractions. IEEE Transactions on Computers, 39(8):1087-1105, August 1990.

27. Vimawala A. p-adic Arithmetic Methods for Exact Computation of Rational Numbers. // Scholl of Electrical Engineering and Computer Science, Oregon State University, 2003

28. Воеводин B.B. Вычислительные основы линейной алгебры. М., «Наука», 1977.-303с.

29. Воеводин В.В. Математические модели и методы в параллельных процессах. М.: «Наука», 1986.-296 с.

30. Головкин Б.А. Параллельные вычислительные системы.- М: Наука,. 1980. 520с.

31. Давыдов О.Е, Разработка и исследование шифраторов и цифровых фильтров для абонентской связи в системе остаточных классов. / Диссерт. на соиск. учен, степени канд. техн. наук. Йошкар-Ола, 2000. - 127с.

32. Дадаева И.Г. Исследование помехоустойчивых свойств остаточных кодов в позиционной и непозиционной системах счисления. / Диссерт. на соиск. учен, степени к.т.н. -М, 1978.

33. Инютин С.А. Исследование методов кодирования, декодирования помехозащищен-ных кодов системы остаточных классов / Диссер. на соиск. учен, степени к.т.н. Ал-мата, 1982.

34. Коляда А.А., Коляда Н.А., Чернявский А.Ф. Мультипроцессорная технология модулярных вычислений.//Материалы международной научной конференции «Модулярная арифметика». http://www.computer-museum.ru/histussr/sokconfD.htm

35. Коряков И.В. Защищенная передача сигналов на основе модулярного преобразованиям/Материалы международной научной конференции «Модулярная арифметика». -http://www.computer-museum.ru/histussr/sokconfD.htmч»

36. Коряков И.В. Метод измерения частоты сигнала на основе системы остаточных классово/Материалы международной научной конференции «Модулярная арифметика». -http://www.computer-museum.ru/histussr/sokconf0.htm

37. Музыченко О.Н. Методы синтеза логических схем модульного контроля в унитарных непозиционных двоичных кодах.//Материалы международной научной конференции «Модулярная арифметика». http://www.computer-museum.ru/histussr/sokconfö.htm

38. Финько O.A. Параллельные логические вычисления — прикладная область модулярной арифметики.//Материалы международной научной конференции «Модулярная арифметика». http://www.computer-museum.ru/histussr/sokconfO.htm

39. Однородные микроэлектронные ассоциативные процессоры /Под ред. И.В.Прангишвили.- М.: Сов.радио., 1973, 280 с.

40. Прангишвили И.В., Виленкин С.Я., Медведев И.Л. Параллельные вычислительные системы с общим управлением.- М.: Энергоатомиздат, 1983,-312 с.

41. Фет Я.И., Вертикальная обработка как основа крупноблочной архитектуры. // Техническая кибернетика. М. 1986. N 5. с. 139-158.

42. Фет Я.М. Массовая обработка информации в специализированных однородных процессорах. Новосибирск: Наука, 1976, 240с.

43. Фет Я. И. Параллельные процессоры для управляющих систем. М., Энергоиздат, 1981.- 160 с.

44. Finko O.A. Algorithms and Devices for N-ary Finite Ring Computations.//Материалы международной научной конференции «Модулярная арифметика». -http://www.computer-museum.ru/histussr/sokconfO.htm

45. Полисский Ю. Д. Сравнение чисел в системе остаточных классов./ТМатериалы международной научной конференции «Модулярная арифметика». http://www.computer-museum.ru/histussr/sokconro.htm

46. Преобразователь позиционного кода в код системы остаточных классов: Пат. 1557682. AI, 5 Н 03 М 7/18 / В.А. Краснобаев, O.A. Финько, Н.И.Швецов ( СССР) -№4450764; Заявл. 27.06.1988; Опубл. 15.04.1990. -Бюл. №14-3 с.

47. Преобразователь числа из кода системы счисления в остаточных классов в двоичный код: Пат. 1541783. AI, 5 Н 03 М 7/18 / Ш-М.А. Исмаилов, Э.Х. Хаспулатов ( СССР) -№4404695; Заявл. 04.04.1988; Опубл. 07.02.1990. Бюл. №5 - 3 с.

48. Стасюк А.И. Организация однородных матричных процессоров.//Электр. моделир., N6,1985, с.20-28.

49. Суммирующее устройство по модулю : Пат. 2034328. AI, 6 G 06 F 7/49/ Ш-М.А. Исмаилов, А.А Джанмурзаев, Э.Н. Курбанов (СССР) №930112221; Заявл. 01.03.1993; Опубл. 30.04.1995.-Бгол. №12.-3 с.

50. Суммирующее устройство: A.C. 1062689. СССР, МКИ G 06 F 7/50. / Ш-М.А. Исмаилов, И.А. Айдемиров, О.Г. Кокаев, Т.Э. Темирханов. № 3502589/24-24; Заявл. 20.10.82; Опубл. 23.12.83. - Бюл. № 47.

51. Бережной В.В. Нейросетевая структура для исправления двукратных ошибок в модулярных нейрокомпьютерах.//Материалы международной научной конференции «Модулярная арифметика». http://www.computer-museum.ru/histussr/sokconfD.htm

52. Грегори Р., Кришнамурти Е. Безошибочные вычисления. Методы и приложения. М., Мир, 1988. - 207 с.

53. Дзегеленок И.И., Оцоков Ш.А. Метод ускорения модулярной арифметики с самоисключением ошибок округлеиия.//Материалы международной научной конференции «Модулярная арифметика». http://www.computer-museum.ru/histussr/sokconfD.htm

54. Коляда А. А. Интервально-модулярные коды с исправлением ошибок.// Вестн. Белорус. ун-та. Сер. 1.Физ. Мат. Мех., 1988. № 2, с. 33 -36.

55. Михлин С.Г. Некоторые вопросы теории погрешностей. JL, Издательство Ленинградского университета. 1988. - 333 с.

56. Gregory R. Т. Exact computation with order-N Farey fractions. Computer Science and Statistics: Proceedings of the 15th Symposium on the Interface. J. E. Gentle Editor, North Holland, Amsterdam, 1983.

57. Potts P. J., Edalat A . Exact real computer arithmetic. Imperial College, March, 1997.

58. Каханер Д., Моулер К, Нэш С. Численные методы и программное обеспечение. М., Мир, 2001.-575 с.

59. Акушский И.Я., Амербаев В.М., Пак И.Т. Основы машинной арифметики комплексных чисел. Алма-Ата, Наука, 1970,- 250 с.

60. Акушский Н.Я, Юдицкий Д.И. Машинная арифметика в остаточных классах, М. «Сов. радио », 1968. -439 с.

61. Деревенсков С. О. Разработка и исследование класса аппаратурно-ориентированных алгоритмов решения систем линейных алгебраических уравнений. / Диссерт. на со-иск. учен, степени к.т.н. Волгоград, 1995 - 217с.

62. Исмаилов Ш-М.А., Артамонов Е.И., Кокаев О.Г., Хачумов В.М. Специализированные алгоритмы и устройства обработки массивов данных. Махачкала, Дагестанское книжное издательство,. 1993. - 304 с.

63. Исмаилов Ш-М.А., Хачумов В.М., Оцоков Ш.А. Алгоритм решения систем линейных уравнений по методу «цифра за цифрой» // Вестник Университета. Тех. науки/ ДГТУ. Махачкала, 2000. - с.92-97

64. Казангапов А. Н. Функциональные вычисления в системе остаточных классов. / Диссерт. на соиск. учен, степени к.т.н. Алма-Ата, 1968. - 127 с.

65. Кнут Д. Э. Искусство программирования, том 2. Получисленные алгоритмы, 3-е изд. -М., Издательский дом «Вильяме», 2001. 832 с.

66. Суейдан Л.И.-Исследование и разработка функциональной организации матричных и таблично-матричных устройств для вычисления элементарных функций. Дисс. на со-иск. уч. степ, к.т.н. Л.: 1981.

67. Финько О.А Модулярная арифметика параллельных логических вычислений: Монография / Под. ред. В.Д. Малюгина; М.: ИПУ РАН, 2003. - 224 с.

68. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979. - 536 с.

69. Бадман О.Л.,Миренков Н.Н, и др. Специализированные процессоры для высокопроизводительной обработки данных. Новосибирск, Наука, 1988.

70. Байков В.Д., Смолов В.Б. Специализированные процессоры. Итерационные алгоритмы и структуры. М.: Радио и связь, 1985. - 288 с.

71. Балашов Е.П., Кокаев О.Г., Петров Г.А., Пузанков Д.В., Смагин А.А. Операционные устройства и процессоры с табличным методом обработки информации. УСим, N 5, 1975.-е.16-21.

72. Барашенков В.В., Кокаев О.Г., Тарасов В.Г., Темирханов Т.Э. Способ ускорения арифметических вычислений.// Известия вузов. Приборостроение, 1983, Т.26, N 9, с.26-30.

73. Kokaev O.G., Kislenko V.S., Ameho D. Parallel execution of logical operations in associative processor // IEE Proceedings-E. Computers and Digital Techniques,- London, 1989.

74. Shooman W. Parallel computing with vertical data / AFIPS Confer. Proc. //EJCG-1960.-Vol. 18.-P.111-115.

75. Taheri M., Lullien G., A., Miller U. C. Simbolic ROM arrays for implementing RNS FIR filter// ICASSP 87: Proc. Int. Conf. Acoust. Speech and Signal Process. (Dallas, Tex., 6-9 Apr., 1987). 1987. Vol. 2. New York. P. 771-774. 340.

76. Tayior F. J., Huang С. H. A comparison of DFT algorithms using residue architec-ture//Comput. Elect. Eng, 1981. Vol. 8 , N 3. P. 161 171.

77. Аль Массри М.И. Разрядно-параллельные процессоры обработки веещественных чисел в непозиционных системах счисления. Дисс. на соиск. уч. степ, к.т.н., Л.: ЛЭТИ, 1993.- 208 с.

78. Szabo N. S., Tanaka R. I. Residue Arithmetic and its Applications to Computer Technology. McGraw-Hill, New. York, 1967.

79. Евдокимов В.Ф., Стасюк А.И. Вычислительные системы на основе разрядной интерпретации обрабатываемой информации. // Электр, моделир., N4, 1986. с.33-41.

80. Кисленко B.C. Разрядно-параллельные процессоры арифметической и логической обработки радиолокационной информации. Дисс. на соиск. уч. степ, к.т.н. Д., ЛЭ-ТИ, 1989. - 171 с.

81. Финько O.A. Многоканальные модулярные системы, устойчивые к искажениям криптограмма/Материалы международной научной конференции «Модулярная арифметика». http://www.computer-museum.ru/histussr/sokconfO.htm

82. Gregory R. Т., Matula D., W. Base conversion in residue number systems//BTT.1977. Vol. 17. P. 286-302.

83. Krishnamurthy E. V. On optimal iterative schemes for high speed division. IEEE Transactions on Computers, C-19, 1970, 227-231.

84. Blum L, Cucker F., Shub M., Smale S. Complexity and real computation, New York: Springer-Verlag. (1998).

85. Blum L., Shub M., Smale S. On a theory of computation and complexity over the real numbers. Amer. Math. Soc. Bull. 21:1-46 (1989).

86. Ирхин В.П. Теоретическое обобщение и разработка методов построения непозиционных модулярных спецпроцессоров: Диссерт. на соиск. учен, степени д.т.н. / Воронеж, 1999.

87. Исмаилов Ш-М.А. Структура параллельно-разрядного процессорного элемента обработки потоков числовых данных в комплексе систем счисления: Тез. докл. Всесоюзной научно-техн. сем. "Многопроцессорные вычислительные системы". -Таганрог, 1991.-е. 74-76.

88. Исмаилов Ш-М.А., Оцоков Ш.А. Разрядно-параллельный алгоритм и структура преобразования чисел из позиционной системы счисления в систему остаточных классов. // Вестник. ДНЦ РАН. 2001 .№9.С. 40-43

89. Кокаев О.Г., Развитие и применение ассоциативных вычислений и структур. Дисс. на соиск. уч. степ, д.т.н. Л.:ЛЭТИ, 1989. - 498 с.

90. Коляда A.A. Модульные структуры конвейерной обработки числовой информации. -Минск, Университетское, 1990.-331 с.

91. Коляда A.A. Обобщенные системы остаточных классов. / Диссерт. на соиск. учен, степени канд.физ.-мат.наук. Белор. гос университет. -Минск, 1973. 149 с.

92. Коляда A.A., Пилиповец Ф.С. О нахождении оснований систем остаточных классов // Теория и применение мат. машин. Мн.: Изд-во БГУ, 1972, с. 16-28.

93. Осепянц O.A., Исмаилов Ш-М. А. Методика генерации оптимального основания для представления чисел в системе остаточных классов.//Материалы международной научной конференции «Модулярная арифметика». http://www.computer-museum.ru/histussr/sokconfO.htm

94. Nielsen A. M., Komerup P. MSB-first digit serial arithmetic. Journal of Universal Computer Science, l(7):527-547, 1995.

95. Ong S., Atkins D.E. A Basis for the Quantitative Comparison of Computer Number Systems // IEEE Trans, on comput., 1983, Vol. C-32, N 4, P 359-369.

96. Червяков Н.И., Дьяченко И.В. Принципы построения модулярных сумматоров и умножителей.//Материалы международной научной конференции «Модулярная арифметика». http://www.computer-museum.ru/histussr/sokconfO.htm

97. Краснобаев В.А., Ирхин В.П. Алгоритм реализации операции модульного умножения в системе остаточных классов.//Электр. моделир., N 5, 1993., с.20-27.

98. Червяков Н.И. и др. Методы и алгоритмы округления, масштабирования и деления чисел в модулярной арифметике.//Материалы международной научной конференции «Модулярная арифметика». http://www.computer-museum.ru/histussr/sokconfO.htm

99. Луцкий С.А. Исследование особенностей проектирования и разработки быстродействующих аппаратных средств реализации элементарных функций с высокой точностью. / Дисс. на соиск. уч. степ, к.т.н. Л.: 1982. - 238 с.

100. Ирхин В.П. Табличная реализация операций модулярной ар и ф м етики. //Матер и ал ы международной научной конференции «Модулярная арифметика». -http://www.computer-museum.ru/histussr/sokconfO.htm

101. Смичкус Е.А., Баранов B.JL О преобразовании чисел системы остаточных классов в позиционный код.//УСиМ, N78, 1992.- с.31-36.

102. Устройство для преобразования числа из системы остаточных классов в позиционный код : Пат. 1501280. AI, 4 Н 03 М 7/18 / С.Н. Литвинов (СССР) №4337158; За-явл. 03.12.1987; Опубл. 15.08.1989 - Бюл. №30 - 3 с.

103. Магомедов Ш.Г. Алгоритм преобразования двоично-десятичных чисел в систему остаточных классов// Молодежь и наука: реальность и будущее: материалы II Международной научно-практической конференции.- Невинномысск: НИЭУП, 2009.( 0,34)

104. Katz Randy. Contemporary Logic Design. The Benjamin/Cummings Publishing Company. 1994. - pp.249-256.

105. Vahid Frank. Digital Design. John Wiley and Sons Publishers. 2006. - pp.296-316.

106. Шкурба B.B. Задача трех станков. М., Наука, 1976. - 96с.

107. Конвей Р. В., Максвелл В.Л., Миллер Д.В. Теория расписаний. М., Наука, 1975. -360с.

108. Феллер В. Введение в теорию вероятностей и ее приложения. Т.2. М., Мир, 1984. -с. 181-183.

109. Червяков Н.И., Ряднов С.А., Сахнюк П.А., Шапошников A.B., Модулярные параллельные вычислительные структуры нейропроцессорных систем. -М.: ФИЗМАТ-ЛИТ, 2003.-288 с.

110. Василенко О.Н. Теоретико-числовые алгоритмы в криптографии. М., МЦНМО, 2003.-326с.

111. Магомедов Ш.Г. Использование системы остаточных классов для организации передачи данных морскими судами.//Вестник Астр. гос. тех. ун-та, Серия «Морские технологии», 2010, №128. http://primes.utm.edu/

112. Оцоков Ш.А Алгоритм безошибочного суммирования чисел с фиксированной запятой //Новые информационные технологии: Тез. докл. Всеросс. научн.-техн. конф,-М.:МГ АЛИ,2003, т. 1,- с. 155-158.