Система остаточных классов презентация

Система остаточных классов презентация

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

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

Система остаточных классов допускает расширение или сокращение набора оснований без искажения при этом исходного числа. Например, для представления числа используется три основания — pi, Р2, Рз; тогда число изображается в виде A ( ai, а %, с з); если ввести новые основания — р4 и рз, то изображ: ение числа изменится и будет иметь вид А ( а, а %, сез, 4, б) — Аналогичным образом можно сократить набор оснований. Расширение оснований увеличивает диапазон и разрядность представления чисел, а сокращение — уменьшает. Образование остатков о производится независимо друг от друга. Последнее и определяет данную систему счисления как непозиционную; каждый разряд содержит в себе информацию обо всем числе. При выполнении сложения, вычитания и умножения каждая цифра результата зависит лишь от соответствующих цифр операндов. [3]

Система остаточных классов является фундаментальной для теории и практики машинной арифметики и позволяет ставить и решать новые задачи, недоступные для позиционных систем счисления. [4]

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

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

Использование системы остаточных классов для кодирования числовой информации дает возможность эффективно распараллеливать алгоритмы выполнения элементарных арифметических операций автономных и неавтономных как П — задач, так и не П — задач, что и обеспечивает высокую производительность и надежность. В [4] показано, что в системе остаточных классов были созданы специализированные ЭВМ с уникальной для машин второго поколения производительностью 1 25 миллионов операций в секунду. [7]

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

Кроме того, система остаточных классов является мощным методом повышения надежности. Показано [116], что система остаточных классов с двумя контрольными основаниями позволяет сохранить работоспособность машины при отказах двух элементов. Но и третий, и четвертый отказы не выводят машину из строя. СОК, является исключительно живучей, приближаясь в этом смысле к биологическим системам. К тому же следует отметить, что при переходе на БИС различия в сложности позиционных и непозиционных ЭВМ становятся незначительными. [9]

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

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

Сочетание корректирующих свойств системы остаточных классов и адаптивных свойств искусственных нейронных сетей позволяет реализовать непозиционный нейрокомпьютер с реконфигурируемой в динамике вычислительного процесса структурой. [12]

Для упрощения вычислений в системе остаточных классов желательно, чтобы модули р ( / г Е [1, ]) имели как можно более простое представление. Однако в полной мере экономия в вычислениях может быть достигнута лишь в том случае, когда обработка информации выполняется с помощью специальных вычислительных средств, эффективно представляющих модулярную арифметику. [13]

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

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

Страницы: 1 2 3 4

Нахождение обратных чисел в модульной арифметике (по сложению и умножению)

Модулярная арифметика

Модулярная арифметика часто изучается в школе как "арифметика часов". Если отсчитать 14 часов от 3 часов после полудня, то получится 5 часов утра следующего дня:

Это арифметика по модулю 12.

Читайте также:  3 85 Млрд долл

Обычная запись в модулярной арифметике

читается так: "а сравнимо с b по модулю n". Это соотношение справедливо для целых значений а, b и n ¹ 0, если, и только если

для некоторого целого k.

Отсюда, в частности, следует

Это читается как "n делит (а — b)".Если

то b называют вычетом числа а по модулю n.

Операцию нахождения вычета числа а по модулю n

называют приведением числа а по модулю n или приведением по модулю.

В нашем примере

(3+ 14) mod 12 = 17 mod 12 = 5

число 5 является вычетом числа 17 по модулю 12.

Набор целых чисел от 0 до (n-1) называют полным набором вычетов по модулю п. Это означает, что для любого целого а(а>0) его вычет г по модулю n есть некоторое целое число в интервале от 0 до (n-1), определяемое из соотношения

r = a – k * n,

где k-целое число.

Например, для n =12 полный набор вычетов:

Обычно предпочитают использовать вычеты

но иногда полезны вычеты в диапазоне целых:

Заметим, что

-12(mod 7) º -5(mod 7) º 2(mod 7) º 9(mod 7) и т.д.

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

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

(a + b) mod n = [a(mod n) + b(mod n )] mod n,

(a — b) mod n = [a(mod n) — b(mod n )] mod n,

(a * b) mod n = [a(mod n) * b(mod n )] mod n,

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

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

Вычисление степени числа а по модулю n

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

Система остаточных классов

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

Например, если нужно вычислить

не следует применять примитивный подход с выполнением семи перемножений и одного приведения по модулю громадного числа:

(a * a * a * a * a * a * a * a) mod n

Вместо этого выполняют три малых умножения и три малых приведения по модулю:

((a 2 mod n) 2 mod n) 2 mod n.

Тем же способом вычисляют

a 16 mod n = (((a 2 mod n) 2 mod n) 2 mod n) 2 mod n.

Вычисление

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

x = 25(10) ® 1 1 0 0 1(2), поэтому 25 = 2 4 + 2 3 + 2 0

Тогда

a 25 mod n = (a * a 24 ) mod n = (a * a 8 * a 16 ) mod n = a * ((a 2 ) 2 ) 2 * (((a 2 ) 2 ) 2 ) 2 mod n = ((((a 2 * a) 2 ) 2 ) 2 * a) mod n.

При разумном накоплении промежуточных результатов потребуется только шесть умножений:

(((((((a 2 mod n) * a) mod n) 2 mod n) 2 mod n) 2 mod n) * a) mod n

Этот метод уменьшает трудоемкость вычислений до 1,5xk операций в среднем, где k-длина числа в битах [123].

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

Презентация была опубликована 5 лет назад пользователемМаргарита Стрекопытова

Похожие презентации

Презентация на тему: " Устройство для вычисления скалярного произведения векторов с коррекцией ошибок на базе системы остаточных классов Авторы: Соловьев Р.А. (докладчик) Д.В." — Транскрипт:

1 Устройство для вычисления скалярного произведения векторов с коррекцией ошибок на базе системы остаточных классов Авторы: Соловьев Р.А. (докладчик) Д.В. Тельпухов, Е.С. Балака Институт проблем проектирования в микроэлектронике ИППМ РАН

2 Скалярное произведение векторов (СПВ).

3 Ускорение вычислений СПВ. Схема конвейеризации умножителя

4 Модулярная арифметика. Позиционная система счисления Система счисления, в которой значение каждой цифры в записи числа зависит от его позиции. Система остаточных классов (СОК) Для системы взаимно простых чисел p 1, p 2, … p n, любое число X из диапазона [0; M), M = p 1 *p 2 *…*p n представимо в виде вектора (a 1, a 2, …, a n ), где a i = X mod p i. p 1, … p n – модули системы a 1, a 2, …, a n – остатки числа по заданной системе модулей. Параллелизм вычислений Низкая разрядность вычислений Простая реализация арифметических операций Возможность для коррекции ошибок Сложность сравнения чисел Сложность определения переполнения Необходимость в преобразователях в /из позиционной системы счисления

5 Обнаружение и коррекция ошибок в СОК p3p3 p1p1 p2p2 p u-1 pupu p u+1 p u+2 pnpn … Информационные модули … Контрольные модули Легитимный Диапазон [0;M-1] Нелегитимный Диапазон [M;M*K] M=p 1 p 2 … p u K=p u+1 p u+2 … p n Численный пример Информационные модули: 3, 5, 7 Контрольные модули: 8, 11 Легитимный диапазон: [0;105) 56 = (2,1,0,0,1) (2,3,0,0,1) Набор модулей Значения в СОКЗначение в позиционной записи (5,7,8,11)(3,0,0,1)1288 (3,7,8,11)(2,0,0,1)56 (3,5,8,11)(2,3,0,1)848 (3,5,7,11)(2,3,0,1)518 (3,5,7,8)(2,3,0,0)728

Читайте также:  Как запустить файл ехе на андроид

6 Выбор базисных оснований в СОК Что бы избежать затратной операции округления, можно выбрать динамический диапазон покрывающий все возможные значения результата скалярного произведения. Размерность элемента вектора в битах (k) Количество элементов вектора l Возможный базисMРазмерность максимального результата вычислений (бит) 816 <5, 7, 11, 13, 17, 19> < 2, 3, 5, 7, 11, 13, 17, 19, 23 > <7, 11, 13, 17, 19, 23, 29, 31>

7 Прямой преобразователь в СОК 0 бит Х 1 бит 2 бит … k бит A0A0 A1A1 A2A2 AkAk Пирамида льный сумматор Блок финальной редукции S |Х|p|Х|p

8 Умножение и сложение по модулю в СОК 3 метода умножения по модулю 1)Обычное умножение с последующей коррекцией 2)Индексный метод 3)Метод разности квадратов IF (R P) O = R – P ELSE O = R + Схема индексного умножения Схема сложения по модулю Пример индексного умножения по модулю 5

9 Обратный преобразователь СОК Схема обратного преобразователя для системы из 4 модулей В конвейерных схемах обычно применяют преобразователи на базе полиадического кода из-за однородности их структуры. Основная операция для блоков ROM: Из-за малой размерности a и b, а также в силу того что константы p известны на этапе проектирования, эти блоки на критичных к скорости участках, могут быть заменены на таблицы.

10 Общая схема работы СПВ в СОК

12 Преимущества подхода и нерешенные проблемы 1)Не уступает, а иногда и превосходит по скорости двоичную реализацию 2)Гибкий контроль набора модулей для исправления кратных ошибок 3)Не требует преобразователей в случае работы в модулярном представлении 1)Превосходит по площади двоичные аналоги 2)Более сложная структура 3)Массивный обратный преобразователь, вносящий потенциальные ошибки во время выбора правильного ответа Дальнейшее направление исследований: 1) Проверка эффективности устройства для исправления многократных ошибок 2) Использование улучшенных блоков модулярной арифметики с целью увеличения выигрыша по площади и скорости работы скалярного произведения

Ни для кого не секрет, что математика – наука абстрактная и в своем "чистом" виде никакого отношения к реальному миру не имеет. Многие, конечно попробуют эту мысль оспорить. Однако заставляет задуматься хотя бы тот факт, что разные народы в различные периоды времени даже считали по-разному. Стоит только вспомнить крайне неэффективную систему счисления древних римлян. Греки вместо чисел использовали буквы собственного алфавита, как и славяне. В Вавилоне появилась шестидесятеричная система счисления, которая нашла отражение в подсчете времени (60 минут в часе, 60 секунд в минуте) и углов. И египтяне конечно же отличились, первыми придумав десятичную, хотя и непозиционную, систему счисления. Иными словами – кто как придумал, тот так и считал.

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

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

Проблема

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

Современные вычислительные системы, несмотря на всю свою мощь, все-таки ограничены. И дело даже не в том, что они не могут, например, сделать точный прогноз погоды или расшифровать ДНК. Ограниченность проявляется в самой незначительной, казалось бы, части – диапазоне работы с числами. Просто компьютер способен работать лишь с ограниченным отрезком чисел, который определяется разрядной сеткой процессора. Многие устройства "понимают" числа размером 32 бита (двоичных разряда), другие – 64. Крайне мало 128-ми битных вычислительных элементов, все остальное – вообще единичные случаи. Малая разрядность чисел приводит к невысокой точности вычислений, а многие алгоритмы и вовсе требуют запредельной разрядности. Так например схема шифрования RSA в современном варианте считается достаточно безопасной при длине ключа 2048 бит, что вызывает определенные затруднения при реализации.

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

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

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

Читайте также:  Как научиться пользоваться смартфоном самсунг

Система остаточных классов

Ранее мы пришли к выводу, что позиционность не всегда хорошо. Рассмотрим теперь непозиционный подход к системам счисления. Под непозиционностью понимается отсутствие очевидной связи между разрядами или, иными словами, отсутствие переносов. Одной из самых используемых непозиционных систем счисления является Система остаточных классов (СОК, Residue Number System – RNS). СОК основывается на теории сравнений и была предложена советским математиком Израилем Яковлевичем Акушским в 50-е годы двадцатого века. Теорию вычислений в СОК иногда называют модулярной арифметикой, основной теоремой которой является Китайская теорема об остатках (КТО, Chinese remainder theorem – CRT), одна из формулировок которой приведена ниже [1].

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

Последовательность и есть представление числа в системе остаточных классов. Каждое из чисел называется разрядом числа в СОК. Отметим, что числа являются остатками от деления на числа , откуда . Именно этот факт отражает основные свойства СОК – снижение разрядности. Все дело в том, что для вычисления суммы или произведения двух чисел, представленных в СОК, достаточно сложить и умножить соответственные остатки-разряды:

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

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

Рис. 1. Ускорение операции возведения в степень при использовании СОК.

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

Пример

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

Найдем сумму данных чисел:

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

Умножим полученное число на 2 в СОК. Здесь

что соответствует реальности, так как .

Вывод

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

  • СОК позволяет упростить и уменьшить архитектуру вычислительных электронных устройств, за счет чего повышается не только скорость, но и энергетическая эффективность продуктов.
  • СОК часто используется как средство для синтеза устройств высокой надежности, ее "параллельная" природа позволяет за счет введения избыточных оснований строить высокоэффективные помехоустойчивые коды.
  • Криптографические приложения не ограничиваются одним лишь ускорением работы с длинными числами; СОК является хорошей базой для построения схем разделения секрета, обладающих выгодными относительно аналогов свойствами.
  • В системах цифровой обработки сигналов (ЦОС, DSP) СОК показала себя как выгодный инструмент повышения эффективности цифровых фильтров, о чем свидетельствует огромное количество работа в данной области.
  • Некоторые приложения нашла СОК в системах связи, примером чему является оптимизация технологии CDMA за счет внедрения модулярных преобразований.

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

Ссылка на основную публикацию
Adblock detector