Содержание к диссертации
Введение
Глава 1. Система представления числовых данных и особенности их применения в информационных системах 12
1.1. Вопросы организации вычислительных процессов в комплексе систем счисления 12
1.2. Выбор систем счисления 18
Выводы 30
Глава 2. Разработка моделей и алгоритмов преобразования числовых данных из позиционной системы представления в систему остаточных классов 31
2.1. Алгоритм и структура преобразования двоично-десятичных чисел в код остаточных классов первого типа 31
2.2. Алгоритм и структура преобразования двоично-десятичных чисел в код остаточных классов второго вида 36
2.3. Алгоритм и структура устройства преобразования двоичных чисел в систему остаточных классов 37
2.4. Сравнение разработанных методов преобразования двоично-десятичных чисел в код системы остаточных классов 41
Выводы по главе 2
Глава 3. Разработка алгоритмов и моделей преобразования числовых данных системы остаточных классов в систему двоичных кодов 49
3.1. Алгоритм и структура преобразования первого типа в код двоично десятичных чисел из кода остаточных классов 49
3.2. Алгоритм и структура устройства преобразования чисел из системы остаточных классов в двоичный код с табличными слагаемыми 55
Выводы по главе 3 72
Глава 4. Практические приложения полученных результатов 73
4.1. Использование разработанных алгоритмов в сумматорах 59
4.2. Использование СОК для организации передачи и приема данных 67
4.3. Разработка программного продукта, реализующего разработанные алгоритмы : 76
Выводы по главе 4 V 96
Заключение 97
Литература
- Выбор систем счисления
- Алгоритм и структура преобразования двоично-десятичных чисел в код остаточных классов второго вида
- Алгоритм и структура устройства преобразования чисел из системы остаточных классов в двоичный код с табличными слагаемыми
- Использование СОК для организации передачи и приема данных
Введение к работе
Актуальность темы. Интенсивное развитие информационных технологий и широкое внедрение реализующих их автоматизированных систем обработки информации и управления практически во все сферы человеческой деятельности, увеличение объемов и сложности осуществляемых ими преобразований требует обеспечения соответствующего уровня надежности, достоверности и приемлемого времени выполняемых операций. Особую остроту приобретают вопросы, связанные с управлением ответственными объектами и процессами – систем критических приложений (энергетика, транспорт, экология, оборона и т.д.), для которых ошибки в преобразованиях и при передаче данных могут привести к тяжелым и даже к катастрофическим последствиям.
Одним из эффективных направлений развития вычислительных систем обработки данных, функционирующих в недвоичных системах счисления является разработка быстродействующих преобразователей данных из одной принятой системы счисления в другую и наоборот, сочетающих в себе современную элементную базу и развитое математическое обеспечение. Вычислительные системы обработки данных, функционирующих в недвоичных системах счисления кроме устройств преобразования данных должны иметь достаточно большую емкость оперативной и внешней памяти, а также обладать производительностью в сотни миллионов.
К перспективным направлениям решения отмеченной выше задачи следует отнести разработку специализированных вычислительных систем обработки данных (СВСОД), существенно повышающих возможности средств вычислительной техники по обработке и передаче данных, с точки зрения быстродействия и точности.
Однако, наряду со значительными успехами, достигнутыми в теории архитектуры СВСОД, традиционно функционирующих в двоичной системе счисления (СС), важным направлением повышения быстродействия и надежности их работы является использование, наряду с двоичной СС, недвоичных СС. Известно, что главный недостаток двоичной СС – наличие «длинных» межразрядных переносов, что существенно влияет на быстродействие выполнения арифметических операций, что безусловно сказывается на производительности СВСОД. В настоящее время повышение быстродействия СВСОД производится в основном за счет распараллеливания задачи и ее реализации на параллельных ЭВМ. К сожалению на практике имеется класс задач не поддающихся «хорошему» распараллеливанию, но необходимо более высокое быстродействие. Понятно, что традиционными (классическими) способами поставленную задачу не решить в связи имеющими ограничениями на многие параметры. В этом случае необходимы поиски новых путей или усовершенствования известных. С этих позиций представляется целесообразным использование в качестве СС системы счисления в остаточных классов (ССОК). Одно из основных достоинств ССОК – возможность эффективно реализовать процедуру распараллеливания реализации арифметических операций и тем самым существенно повысить быстродействие систем СВСОД.
Проблема использования СОК является не новой. Впервые она была поставлена в пятидесятые годы прошлого века, когда были предприняты попытки по практической реализации данной идеи в рамках проекта «Алмаз», при создании ЭВМ Т-340А и К-340А и суперЭВМ 5Э53. Однако, после двадцати лет исследований все работы были практически приостановлены, по-видимому, ввиду недостаточно развитой элементной базы того времени и отсутствия эффективных алгоритмов прямых и обратных преобразований числовой информации. В настоящее время существующая элементная база позволяет не только реализовать проекты того времени, связанные с ССОК, но и значительно усовершенствовать многие идеи; в частности, применительно к проблемам безопасности и безошибочности вычислений. Поэтому теоретические исследования и практические работы в данной области в последние годы активизировались.
Большой вклад в развитие теоретических и практических вопросов, связанных с СОК, внесли отечественные исследователи и ученые Акушский И.Я., Юдицкий Д.И., Червяков Н.И., Коляда А.А., Коряков И.В., Малашевич Д.Б., зарубежные ученые Свобода А., Валах М., Бияшев Р.Г.
Широкое внедрение СВСОД, функционирующих в ССОК сдерживается и на сегодняшний день, в связи с отсутствием быстродействующих алгоритмов сравнения чисел в ССОК, округления, выхода диапазона чисел за его пределы, а также сложные алгоритмы преобразований чисел из системы остаточных классов в позиционные коды.
С учетом вышеизложенного диссертационная тема работы посвящена решению одной из проблем, а именно разработке быстродействующих алгоритмов и структур устройств преобразования числовой информации из позиционной СС в ССОК, а также из ССОК в позиционную СС.
С этой точки зрения тема диссертационной работы безусловно является актуальной как в теоретическом так и практическом плане.
Объектом исследования - являются способы, методы, алгоритмы и структуры устройств прямых и обратных преобразований числовой информации из одной принятой СС в другую, используемые в настоящее время в СВСОД, функционирующих в ССОК.
Предметом исследования- являются построение таблично-алгоритмического метода и реализация на его основе алгоритмов прямых и обратных преобразований числовой информации из одной принятой СС в другую.
Целью диссертационного исследования является разработка и усовершенствование методов, алгоритмов и структур устройств выполнения прямых и обратных преобразований числовой информации из одной принятой СС в другую. Поставленная цель достигается решением следующих задач:
-
Разработка алгоритма и структуры устройства преобразования числовой информации из ССОК в позиционный код с вычисляемыми слагаемыми;
-
Разработка алгоритма и структуры устройства преобразования числовой информации из ССОК в позиционный код с табличными слагаемыми;
-
Разработка алгоритма и структуры устройства преобразования числовой информации из двоичной системы счисления в СОК;
-
Разработка алгоритма и структуры устройства преобразования числовой информации из двоично-десятичной системы счисления в СОК;
-
Формирование алгоритмов и программных средств, позволяющих выполнять разработанные в работе прямые и обратные преобразования данных из позиционной системы в систему остаточных классов и отличающийся от известных алгоритмов применением таблиц соответствия вычисляемых и табличных слагаемых.
-
Анализ приложений разработанных алгоритмов в системах обработки данных.
Методы исследования основываются на теории чисел, теории вероятностей, дискретной математики, теории алгоритмов, теории графов и теории множеств.
Научная новизна диссертационного исследования заключается в разработке алгоритмов прямых и обратных преобразований числовой информации из одной принятой СС в другую в СОД, функционирующих в ССОК с использованием таблично-алгоритмических способов обработки числовой информации, позволяющих повысить на 1-2 порядка скорость выполняемых преобразований.
К основным результатам, представляющим новизну исследования, можно отнести следующие:
-
Разработаны методы и алгоритмы прямого преобразования данных из позиционной системы представления информации в систему остаточных классов, отличающейся от известных таблично -алгоритмическим способом реализации, что позволяет повысить быстродействие прямых преобразований в средствах ВТ.
-
Построена математическая модель и разработан алгоритм обратного преобразования числовых данных из системы остаточных классов в систему двоичных кодов, отличающейся от известных таблично–алгоритмическим способом реализации, что позволяет повысить быстродействие обратных преобразований в средствах ВТ.
-
Разработаны схемы устройств прямого и обратного преобразования данных в системе остаточных классов и двоичных кодов, позволяющие проектировать преобразователи с большим быстродействием по сравнению с существующими.
-
Сформированы алгоритмические процедуры использования разработанных методов в процессах передачи данных и при выполнении операций суммирования чисел в процессорных устройствах средств ВТ.
Практическая ценность полученных результатов. В работе предложены конкретные практические решения и рекомендации по применению алгоритмов и структур устройств преобразования числовых данных из одной принятой системы счисления в другую. Результаты исследования могут быть использованы при проектировании и изготовлении систем параллельной обработки информации, к которым предъявляются повышенные требования по надежности и достоверности работы. Разработанный оригинальный программный комплекс, использующий предложенные в работе методы и алгоритмы, может быть использован в процессе анализа характеристик методов преобразований данных в ССОК, а также в учебном процессе.
Апробация работы. Основные положения диссертационной работы и вопросы их практического использования докладывались и обсуждались: на ІІ международной научно-практической конференции «Молодежь и наука: реальность и будущее» (Невинномысск, 2009), на ІІІ Всероссийской конференции по актуальным проблемам внедрения и развития сектора IT – технологий «Современные информационные технологии в проектировании, управлении и экономике» (Махачкала, 2008,), на IV Всероссийской конференции по актуальным проблемам внедрения и развития сектора IT- технологий (Махачкала, 2009), на V региональной научно-технической конференции( Махачкала, ДНЦ РАН, 2009) .
Публикации. По результатам диссертационной работы опубликовано 12 работ, в том числе 9 статей, из них две статьи в научных изданиях, рекомендованных ВАК. Без соавторов опубликовано 4 работы.
Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка использованных источников и четырех приложений. Работа изложена на 135 страницах, содержит 17 рисунков, 11 таблиц, список литературы, состоящий из 120 наименований и 4 приложений.
Выбор систем счисления
Выбор двоичной системы счисления основан на том, что она является наиболее оптимальной по комплексному критерию эффективности среди позиционных систем счисления. Несмотря на то, что по одному частному критерию наибольшего быстродействия она занимает одно из последних мест, следует учесть ее преимущество по другим, а также громадный опыт и устойчивые традиции ее использования практически во всех ВУ, что делает постановку вопроса о полной ее замене на современном этапе развития ВТ нецелесообразной. Выбор двоичной системы счисления также обосновывается тем, что ряд операций таких, как сравнение, преобразование чисел и некоторые другие, довольно трудно реализуемы в других системах кодирования, например, в системе остаточных классов.
Выбор двоично-десятичной системы счисления основан на следующих соображениях. Известно, что десятичная система счисления по комплексному критерию эффективности занимает в ряду позиционных систем лишь девятое место. Однако стоит отметить, что по одному из частных критериев - удобству работы человека с машиной и отсутствию необходимости преобразования информации - она несомненно стоит на первом месте.
Необходимость включения в комплекс двоично-десятичной системы счисления обосновывается необходимостью вывода результатов на печать, а также - в некоторых случаях, зависящих от характеристик ПЧД и ПО, производить в ней арифметические операции с целью минимизации времени их реализации по сравнению с другими системами счисления.
Узким местом при выполнении арифметических операций в двоично-десятичной системе кодирования является проблема коррекции результатов, что сильно сказывается на временных затратах при необходимости реализации ОГС.
В связи с этим целесообразно рассмотреть вопросы разработки быстродействующих арифметических устройств (АУ), функционирующих в двоично-десятиной системе счисления и ориентированных на выполнение «-арной операции суммирования числовых данных.
Известно, что существенным недостатком всех позиционных систем счисления является наличие "длинных" переносов, влияющих на время выполнения основной операции - суммирования, что отрицательно сказывается на быстродействии реализации других операций. Также следует отметить, что использование ПСС в ЭВМ приводит к необходимости округления результата вычислений, что связано с накоплением ошибок.
Указанного недостатка лишена система счисления в остаточных классах, р-адическая система, относящиеся к непозиционным системам счисления. Рассмотрим теоретические аспекты применения ССОК, jo-адической системы, кодов Гензеля, дробей Фа-рея и особенности безошибочности вычислений.
Одним из способов избегания ошибок округления и точного выполнения арифметических операций является оперирование целочисленными представлениями всех разновидностей чисел, что имеет место в вычислениях в непозиционных СС (НСС), к которым относят ССОК, /7-адическую СС и коды Гензеля как разновидность бесконечного р-адического представления чисел.
Под безошибочными вычислениями понимается проведение в непозиционной системе счисления (НСС) точных вычислений, выполняемых над целочисленными и дробными операндами, в которых отсутствуют ошибки округления. Теория БОВ (Безошибочные вычисления) имеет дело с задачами, для которых входная информация представлена набо ром целых чисел (или многочленов с целыми коэффициентами), а решение является рациональной функцией от этих чисел (или многочленов). К задачам такого типа относятся обращение матриц в обычном или в обобщенном смысле и построение характеристического многочлена целочисленной матрицы, а также решение линейных систем с целыми коэффициентами.
Необходимость БОВ вытекает из того, что существуют как обширные классы плохо обусловленных задач, так и численно неустойчивые алгоритмы. И в том, и в другом случае при решении соответствующих задач нельзя допускать ошибок округления.
При решении таких задач эффект ошибок округления может быть катастрофическим. К примеру, рассмотрим задачу вычисления определителя матрицы:
Тогда det А=\, в то время как det(A + Е) = 118,94 . Другими словами, если накопление ошибок округления соответствовало введению возмущающей матрицы Е, то вычисленное значение определителя будет равно 118,94, тогда как точное значение есть 1. Поэтому имеются серьезные доводы для использования числовых систем, в которых бы вычисления можно выполнить точно.
В настоящее время значение этих ошибок в традиционных ВУ уменьшается аппарат-но путем удлинения разрядной сетки сумматоров, что влечет за собой увеличение аппаратурных затрат и не приводит к полному устранению указанных ошибок. Это требует поиска алгоритмических способов, связанных с применением новых нетрадиционных методов и систем счисления для представления и обработки чисел.
Этого можно достигнуть, прежде всего, средствами специального кодирования, наиболее широкий интерес из которых представляет система счисления в остаточных классах (ССОК). Ей присущи высокие скорость вычислений и точность их результатов, обусловленные, соответственно, отсутствием межразрядного переноса между цифрами числа и отсутствием операции округления результатов. Многие алгоритмы методов вычислений в непозиционных СС разработаны в рамках теории чисел, однако нерешенной осталась проблема оперативного фиксирования выхода результата за пределы диапазона применяемой ССОК и определения количественной меры возникшего переполнения, позволяющей его разрешения и восстановление истинной величины результата и ведущей к существенному снижению аппаратно-временных затрат, поскольку до сих пор традиционным путем избегания переполнения являлось увеличение числа или величин модулей ССОК с непосредственным увеличением аппаратурных и временных затрат. Преимущества ССОК и ее недостатки рассмотрены в многочисленных работах.
Повышение быстродействия вычислительных устройств наряду с использованием прогрессивных интегральных технологий и скоростных табличных методов вычислений идет в направлении временного и пространственного распараллеливания алгоритмов и структур этих устройств, связанного с увеличением аппаратурных затрат.
Компромиссным решением возникшего между быстродействием и аппаратурными затратами противоречия является применение принципов разрядно-параллельной обработки, при которой аргументами операции выступают не сами числа, а их разрядные срезы, состоящие из одноименных разрядов.
До сих пор разрядно-параллельные вычисления и вычисления в ССОК развивались независимо друг от друга. Представляет практический, в определенной степени научный интерес, объединить достоинства обоих направлений развития структур ЭВМ. Этим объясняется необходимость исследования принципов построения разрядно-параллельных процессоров безошибочной обработки вещественных чисел непозиционных СС, обладающих высокой производительностью, прежде всего за счет автоматической коррекции результатов вычислений.
До настоящего времени открытыми являются и вопросы организации вычислительных процессов в ВУ. использующих КСС. Это связано, во-первых, С необходимостью разбиения сложной задачи на взаимосвязанные фрагменты с точки зрения их реализации в наиболее рациональной СС, а, во-вторых, необходимостью разработки специального программного обеспечения, что требует значительных затрат времени.
Алгоритм и структура преобразования двоично-десятичных чисел в код остаточных классов второго вида
Размерность таблиц соответствия будет определяться следующим образом. Обозначим через 1\ количество различных значений, принимаемых двоичным элементом Ь т множества В,, а через L\ - количество различных значений, принимаемых двоичной тетрадой числа R, Ё2 =10. Тогда количество сочетаний S, определяемых различными значениями Ь т и гт в операции конкатенации, будет равным
Рассмотрим структуру устройства преобразования чисел из двоично-десятичной системы счисления в код системы остаточных классов, позволяющую реализацию данного алгоритма аппаратным путем. На рис.2.2 приведена общая структура устройства преобразования двоично десятичных чисел в код остаточных іслассов, содержащая п независимых блоков, количество которых соответствует набору заданных модулей СОК Р = (Р±, Р2,..., Р{-,...,і ).
На входы всех п преобразующих блоков по соответствующим модулям Р поступает в последовательном коде, начиная со старшей тетрады. Преобразуемое двоично-десятичное числом, представленное в коде с весами 8,4,2,1. После обработки последней (младшей ) тетрады соответствующим блоком на выходе устройства получим код системы остаточных классов по заданным модулям.
А = (а1,а2,...,аі,ап). На рис. 2.3 приведена структура отдельного / -го преобразующего блока для модуля Pt, которая содержит блок памяти (БП), разделенный на ассоциативную часть (АЧ) и информационную часть ИЧ, шины синхронизации ШС1 и ШС2 и группу логических элементов. v у
Структура устройства первого вида, служащая для преобразования двоично десятичных чисел в код системы статочных классов. Работу отдельного і -го преобразующего блока устройства по модулю Рг- можно описать следующим образом. По управляющему импульсу (УИ), поданному на ШС 1, на АЧ БП поступают разряды старшей тетрады исходного преобразуемого числа, т.е. гп. По указанному адресу из ИЧ БП считывается слово, представляющее собой остаток Ь±, полученный в результате деления числового значения старшей тетрады тп на заданный модуль Pt, т.е. rn b0 mod Pt и представленный в двоично-десятичном коде. Полученный код остатка Ъг задерживается на один такт, с помощью элемента задержки. При поступлении второго УИ на ШС 1 на АЧ БП поступает комбинация в виде двух или более тетрад (количество тетрад, необходимых для представления остатка Ьг- в двоично-десятичном коде, зависит от значения модуля Р- ) а2 bv По указанному адресу из ИЧ БП считывается слово, представляющее собой остаток Ь2, полученный в результате деления числового значения второй тетрады в совокупности с числовым значением предыдущего остатка й1на заданный модуль Pt, т.е.:
Данный процесс повторяется до тех пор, пока не будут обработаны все тетрады преобразуемого числа А=(гшГп-і, ...,Тп). После обработки последней (младшей) тетрады rt в со вокупности с тетрадами, предоставляющими значения остатка Ь71_1 .и при наличии УИ на ШС 2, получим искомый результат а{ = Ьп, соответствующий преобразованию исходного числа А в код остаточных классов по заданному модулю Pt гп Ьъ-1mod pi = К = ai Таким образом, предлагаемое устройство преобразования чисел из двоичной СС в СОК по модулю работает согласно следующей схеме: r± b0 mod Pt = Ъг, bQ = О Т2 Ъ± mod Pt - b2, r3 b2mod Pt = b3, rn K-i mod Pi = K bn = (ti = A mod P. Аналогичным образом получаются остатки и по другим модулям системы.
На рис.2.4 приведена структурно функциональная схема устройства для модуля Pt = 3 с прошивкой матрицы блока памяти (БП). Пусть, например, задано число А = 193, представленное в исходном виде в двоично-десятичной системе кодирования Л = (0001 1001 ООП)
Определим остаток данного числа по заданному модулю согласно приведенной структуре преобразующего блока. По информационным входам преобразующего блока при подаче УИ на ШС 1 на АЧ БП поступает старшая тетрада числа A r3 = 0001. По указанному адресу 00 0001 из ИЧ БП считывается слово Ьг = 01, которое задерживается на один такт элементами задержки.
При подаче второго УИ на ШС 1 на входы АЧ БП поступает вторая тетрада числа А, Т2 1001, в совокупности с остатком Ьг, т.е. образуется адрес 01 1001, по которому из ИЧ БП считывается слово Ъ2 =01.
Соответственно при подаче третьего УИ на ШС 1 на входы АЧ БП поступает последняя (младшая) тетрада числа тг , которая в совокупности с остатком Ь7 и образует адрес 010011, по которому из ИЧ БП считывается слово Ь3 =01, которое при подаче УИ по ШС 2 поступает на выходные шины устройства и представляет собой искомый результат преобразования числа А по модулю Pt = 3.
Оценим затраты памяти, необходимые для структурной реализации алгоритма преобразования чисел из двоично-десятичной СС в СОК.
Для определения затрат ПЗУ в словах для і - го преобразующего блока по модулю Р необходимо учитывать разрядность входного слова, которая равна ттц = г +[ log2 Рг], где г - количество двоичных разрядов, необходимых для представления десятичной цифры числа А в двоично-десятичной СС. Тогда затраты памяти ПЗУ в словах V 3 для і - го преобразующего блока можно определить по формуле V 37 = 2Г " logz Р(1. Если задана система модулей Р = {Рг, Р2,...,РЛ), то общие затраты памяти ПЗУ в словах 1 пзу для всех преобразующих блоков по модулям СОК определяются как Vj13,7 = У сУ + F2nc3y + ... + ЦЗУ Подставляя соответствующие значения V 0 , получим
Алгоритм и структура устройства преобразования чисел из системы остаточных классов в двоичный код с табличными слагаемыми
Одной из сфер, где наиболее эффективно проявляются возможности СОК, являются процессоры вычислительных устройств. Это связано, в частности, с тем, что при использовании СОК многие арифметические операции могут быть табулированы, и дальнейшие вычисления выполняться на основе таблиц. Отметим, при работе с табличной информацией каждая операция выполняется приблизительно за три такта работы процессора: нахождение требуемого поля таблицы, выбор значения и пересылка его по требуемому адресу. Наиболее трудоемким из перечисленных трех этапов является нахождение требуемого поля таблицы. Время выполнения этой операции зависит прежде всего от размера таблицы и скорости работы процессора. Размер же таблицы для каждого конкретного основания Р( СОК определяется величиной этого основания.
Пусть имеется п -битовый процессор и используется СОК, основание п = (Р},Р2,...,Рк), причем к делит п. Тогда при условии, что длины всех Р, приблизительно одинаковы, из неравенств получаем /(/J) « —. В частности, если п =128, к =8, то /(/)) « = 16. Отсюда выводим, что каж к 8 дая операция (сложение, умножение, деление и др) по основанию Pt может быть задана таблицей, имеющей размер порядка 216 х216, что может быть приемлемым с точки зрения возможностей со-временных процессоров при достаточно длительном использовании данного основания л. При Сравним предлагаемые алгоритмы с классическими с точки зрения выполнения основной арифметической операции - сложения. Как отмечалось во введении, операция сложения является одной из основных операций вычислительного устройства, на которую опираются другие вычислительные действия [103 - 109], а также с участием автора [111, 113 - 115]. В частности, операции вычитания и умножения в решающей степени опираются на операцию сложения. Например, для формирования алгоритма умножения на основе алгоритма сложения может быть использовано соотношение [103]: х-у = — ((х + у)2 -(х-у)2) В настоящее время наиболее известные алгоритмы сложения двух двоичных чисел следующие [117, 118, 120, 121]. 1. Алгоритма последовательного переноса - RCA-алгоритм (ripple-carry adder). В этом алгоритме, выполняемом по классической схеме сложения двух чисел, числа складываются последовательно побитно, начиная справа налево. Если в результате сложения очередных двух битов возникает дополнительный бит, то он прибавляется к результату, получающемуся при сложении следующих (расположенных слева) битов. Таким образом, процедура сложения аналогична процедуре сложения чисел «вручную с помощью бумаги и карандаша». Алгоритм является наиболее трудоемким из всех рассматриваемых, и имеет порядок 0(п) при сложении двух п- битовых чисел.
2. Алгоритм предсказуемого переноса - CLA-алгоритм (carry look-ahead adder). Это наиболее распространенный в настоящее время тип алгоритмов. Процессоры подавляющего большинства современных компьютеров работают на основе алгоритмов данного типа. Алгоритм имеет иерархическую структуру. Непосредственно сложение заданных чисел происходит по группам на нижнем уровне иерархии. На последующих уровнях обрабатываются результаты предыдущих уровней. Разнообразие алгоритмов данного класса обусловлено выбором размеров групп на каждом уровне иерархии, числа групп иерархии - параметр, тесно связанный с предыдущим, а также формой записи рекуррентных формул, используемых при выполнении расчетов и организации алгоритма. Разбиение на группы позволяет параллельно проводить вычисления в разных группах, что существенно повышает быстродействие алгоритма. Одними из наиболее известных алгоритмов данного класса (учитывающими также особенности их практической реализации) являются алгоритмы Брент-Канга и Когдже-Стоуна [120].
CLA-алгоритм опирается на концепцию генерации и распространения переноса. Сложение двух битов А и В генерирует бит, если при сложении этих битов получается 1 (записывается GG=X) в качестве переноса (без учета возможного единичного бита переноса, полученного от сложения битов более низших разрядов). Из определения следует, что перенос генерируется тогда и только тогда, когда одновременно А—\ и В-\; поэтому событию генерирования бита сопоставим бинарный предикат G{A,В) = А-В, который равен 1 в только в случае, когда генерируется бит. Сложение двух битов А и В распространяет бит, если при сложении этих битов, с учетом возможного дополнительного бита переноса от сложения предыдущих (более младших) разрядов, возможно возникновение бита переноса (значение обозначается PG). Из определения следует, что перенос распространяет бит тогда и только тогда, когда либо А=\ либо В=\ (либо оба равны единице); поэтому событию распространения бита сопоставим бинарный предикат Р(А, В) = А + В который равен 1 только в случае, когда распространяется бит. Как вариант можно взятьР(А,В) = А Ф В), где Ф - сложение по модулю два.
Использование СОК для организации передачи и приема данных
Наконец, по поводу выбора щ. Поскольку по, как следует из 4.1, определяет число возможных параллельных преобразований, оптимальное значение «о должно соответствовать число ядер современного стандартного процессора. Исходя из этого, можно взять п0 = 8.
Оценим стойкость предлагаемого метода закрытия передаваемых данных ограниченного доступа. Для этого произведем оценку числа вариантов, которые необходимо перебрать злоумышленнику, для нахождения истинных значений модулей Р1, Р2,..., Рп путем перебора.
Будем анализировать возможности злоумышленника для наиболее плохой ситуации, когда злоумышленник имеет возможности доступа к внутренним ресурсам компьютера. Именно, пусть злоумышленник может выполнить на компьютере вычисление и, имея доступ к внутренним ресурсам компьютера, может проконтролировать промежуточные значения в памяти компьютера, то есть ему известны остатки rvr2,...,rk от деления числа R на модули Р1,Р2,...,Рк соответственно. Оценим среднее число наборов, которое должен перебрать злоумышленник для того, чтобы найти истинные значения Р:,Р2,...,Рк, зная R и г,,г2,...,гА, при условии, что все сочетания равновероятны.
Будем предполагать также, что длины всех модулей приблизительно одинаковы и лежат в преде-лах от / - d до /.
Общее количество возможных значений каждого модуля равно N = 2 - 2 d. Отсюда следует, вероятность обнаружения истинного набора значений Р1,Р2,...,Рк при одной попытке равна и ju = У]і(1-р) 1р, где М = Nk - общее число всех наборов. Здесь (1-р) 1р есть вероятность то го, что (z -l) по пытки были неудачными, а на г -ой попытке злоумышленнику удалось найти истинный набор Р[,Р2,...,Рк. Из формулы видно, что ц является средним значением для геометрического распределения, и по известной формуле получаем /л = — = (2 -2 d)k. Отметим, что числа к и / Р связаны соотношением &/««, где п — разрядность чисел, которые преобразуются на основе СОК; обычно это значение соответствует разрядности процессора.
Например, для 64-битового процессора можно взять к=8, /=8 и d=2. Тогда имеем: = (28-2б)8=(256-64)8=1846757322198614016«1846757322-109, то есть процессору, имеющему тактовую частоту 5 Ггц/сек, потребуется время, равное t я 369351464 сек. только на перебор вариантов, что составляет более 11,7 лет непрерывной работы процессора. Последнее означает, что злоумышленник практически не имеет никаких реальных возможностей обнаружить истинный набор оснований Рх,Р2,...,Рк.
Приведенная процедура была использована автором формирования системы обмена данными между морскими судами [127].
Современное мореплавание немыслимо без устойчивой системы связи судна с управляющей компанией, клиентами, береговыми службами, с другими судами. При этом характер передаваемой информации может быть самый разнообразный: от открытой общедоступной информации (например, о погодных и иных условиях мореплавания в районе пребывания), частных, приватных сообщений до закрытых переговоров с руководством компании и клиентами. Поэтому обеспечение требуемого уровня закрытости передаваемых сообщений и интерактивных переговоров для любой компании, осуществляющей хозяйственную и иную деятельность в акватории мирового океана и во внутренних водах отдельной страны. Защита наиболее важных переговоров требует использования систем шифрования. Однако, требования, предъявляемые к подобным системам, достаточно строгие и, как следствие, громоздкие в реализации и затратные, что часто делает их малоприемлемыми и затруднительными для использования. В работе предлагается процедура закрытия информации, уровень стойкости которой ниже, чем у существующих методов шифрования, но которая достаточно проста в реализации и вполне приемлема для большинства служебных и приватных сообщений, корабельной переписки.
Основные её достоинства по сравнению с существующими системами шифрования: 1) отсутствие необходимости обмена ключами (или ключом) шифрования; 2) доступность для использования всеми физическими и юридическими субъектами, которые желают обменяться сообщениями именно с данным судном и знают все его идентифицирующие атрибуты; например, название, водоизмещение, владельца, страну, в которой судно зарегистрировано, и др. Список этих параметров в дальнейшем может быть уточнен. Отметим, что для этих целей могут быть использованы показатели, входящие в международный или российский морской регистр судоходства. Непосредственно процедура формирования передаваемого общения и его дешифрация у приемной стороны полностью совпадают с описанными выше. Отметим, что принимающая сторона, зная регистрационные атрибуты судна, передающего сообщение, может автоматически найти его набор простых чисел Р],Р2,...,Р„ и прочесть переданное сообщение. Постороннему лицу для того, чтобы прочесть данное сообщение, не зная регистрационных атрибутов отправителя, потребуются значительные вычислительные «усилия».
Применительно к процессу обмена сообщениями на море предлагаются следующие значения параметров разработанного алгоритма. Рассмотрим возможный способ выбора числа N Общая процедура выбора N аналогична рассмотренной выше. Уточнения требует лишь возможное число субъектов S; в данном случае 0 число судов. Число морских судов в ближайшем будущем, по-видимому, не превзойдет числа S=l0000. Поэтому на основе методов, рассмотренных выше, получаем N 64. По соображениям безопасности (обеспечения требуемого уровня стойкости против прямого перебора вариантов), аналогично общему случаю убеждаемся, что при ./V = 1024, к=4, /=8 и d=1 обеспечивается требуемый уровень стойкости: среднее число попыток найти основание Р при прямом переборе равно /л = (2s -26)4 = 1358954496 . Эксперименты с использованием описанного ниже программного продукта показали, что в среднем за одну секунду программа переводит в СОК 200 ч-300чисел при использовании процессора с тактовой частотой 2.7 Ггц. Предполагая, что эффективная реализация данного алгоритма (например, с использованием непосредственно ассемблера процессора) может увеличить время выполнения не более чем на порядок (то есть в десять раз), выводим, что в среднем за 1 сек. Процессор с тактовой частотой 5Ггц может проверить не более чем 300-10-5-1012/2.7-1012«5556 наборовР за 1 сек. Отсюда выводим, что среднее время перебора вариантов до обнаружения требуемого составит приблизительно 13588954496/556 = 2445816 сек. 28 дня непрерывной работы процессора. Таким образом, предлагаемая система является достаточно стойкой к злоумышленному взлому.
Подводя итог, можно заключить, что предлагаемая процедура позволяет индивидуализировать передаваемые сообщения применительно к каждому субъекту, что обеспечивает достаточный уровень безопасности. Процедура не требует наличия специальных ключей шифрования, а опирается лишь на индивидуальные регистрационные атрибуты (физического или юридического) субъекта, что устраняет проблему доставки ключей и тем самым существенно упрощает в целом процесс организации обмена информацией.
