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

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

Определение. Если задан ряд положительных целых чисел p1, p2, . pn, называемых в дальнейшем основаниями системы, то под системой счисления в остаточных классах будем понимать такую систему, в которой целое положительное число представляется в виде набора остатков ( вычетов ) по выбранным основаниям

причем образование цифр ai осуществляется следующим образом:

ai = N — , для i = 1, 2, . n, (5)

где [] означает целую часть, то есть цифра i-го разряда ai числа N есть наименьший положительный остаток от деления N на pi.

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

gi º ai + bi,

di º ai bi.

С учетом (5) отсюда следует:

gi = A+B — . (6)

Из представления A и B следует:

где ki и li — целые неотрицательные числа.

=ki + li + ,

A + B = (ki + li)pi + .

Подставляя полученные выражения в (6), получим:

gi º ai + bi. (7)

В случае умножения

di º ai bi.

Аналогично сложению (A + B) получим:

= ki li pi + ai li +bi ki + .

di º ai bi. (8)

Пример. Сложить числа А = 23 и В = 48 в СОК.

Пусть основаниями системы являются p1 = 3, p2 = 5, p3 = 7.

По выбранным основаниям числа А и В в СОК примут вид:

получим А + В = (2, 1, 1).

Легко проверить, что 23 + 48 = 71, а число 71 = (2, 1, 1) в СОК.

Пример. Умножить число А=14 на В=8 в СОК.

В соответствии с (4) получим:

g1 = 4 — = 4 — 3 = 1,

g2 = 12 — = 12 — 2∙5 = 2,

g3 = 1 — = 1 — 0.7 = 1.

Таким образом, А∙В = 122 = (1, 2, 1).

Охарактеризуем в общих чертах достоинства и недостатки введенной СОK.

Достоинства:

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

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

Недостатки:

§ невозможность визуального сопоставления чисел, так как внешняя запись числа не дает представления о его величине;

§ отсутствие простых признаков выхода результата операций за пределы [0,ρ];

§ ограниченность действий системы сферой целых положительных чисел;

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

Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: Для студента самое главное не сдать экзамен, а вовремя вспомнить про него. 10226 — | 7590 — или читать все.

91.146.8.87 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.

Отключите adBlock!
и обновите страницу (F5)

очень нужно

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

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

Читайте также:  Скальпирование процессора i7 7700k

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

Проблема

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

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

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

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

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

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

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

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

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

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

Читайте также:  Excel расчет линии тренда

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

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

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

Пример

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

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

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

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

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

Вывод

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

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

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

Для любой системы взаимно простых чисел p1, … pn, любое число X из диапазона [0; M), где M = p1*p2*…*pn взаимооднозначно представимо в виде вектора (a1, a2, …, an), где ai = X%pi (здесь и далее «%» — операция взятия остатка от целочисленного деления X на pi).
p1, … pn – модули системы
a1, a2, …, an – остатки (вычеты) числа по заданной системе модулей

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

  1. Отсутствие переноса разрядов в сложении и умножении. Пусть нам дано два числа X1 и X2, представленные в виде системы остатков (x11, x12, …, x1n) и (x21, x22, …, x2n) по системе взаимнопростых чисел (p1, p2, …, pn). В этом случае:
    X3 = X1 + X2 = ((x11+x21)%p1, (x12+x22)%p2, …, (x1n+x2n)%pn)
    X4 = X1 * X2 = ((x11*x21)%p1, (x12*x22)%p2, …, (x1n*x2n)%pn)
    То есть что бы сложить или умножить два числа, достаточно сложить или умножить соответствующие элементы вектора, что для микроэлектроники означает, что это можно сделать параллельно и из-за малых размерностей p1, p2, …, pn сделать очень быстро.
  2. Ошибка в одной позиции вектора не влияет на расчеты в других позициях вектора. В отличие от позиционной системы счисления все элементы вектора равнозначны и ошибка в одном из них ведет всего лишь к сокращению динамического диапазона. Этот факт позволяет проектировать устройства с повышенной отказоустойчивостью и коррекцией ошибок.
Читайте также:  Unknown lan id ewa
Обычное умножение Модулярное умножение

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

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

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

Прямое преобразование

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

Пример: Пусть требуется найти представление числа X = 25 по системе модулей (3, 5, 7). X = (25%3, 25%5, 25%7) = (1, 0, 4).

Реализация нахождения вычета в микроэлектронике по заданному модулю строится на следующих свойствах вычетов:
(a+b) % p = (a%p + b%p)%p
(a*b) % p = (a%p * b%p)%p

Любое число X можно записать в виде X%p = (xn-1*2 n-1 + xn-2*2 n-2 + x*2 0 )%p = ((xn-1)%p*2 n-1 %p) + ((xn-2)%p*2 n-2 %p) + … + x%p)%p. Поскольку в данном случае xn-1, … x равны 0 или 1, то фактически нам требуется сложить вычеты вида (2 i %p).

Пример: пусть задано число 25 или в двоичной системе счисления 11001 и требуется найти остаток по модулю 7.
25%7 = (1*2 4 + 1*2 3 + 0*2 2 + 0* 1 + 1*2 0 )%7 = (2 4 %7 + 2 3 %7 + 1%7)%7 = (2 + 1 + 1)%7 = 4

Систему используемых модулей подбирают под конкретную задачу. Например, для представления 32-х битных чисел достаточно следующей системы модулей: (7, 11, 13, 17, 19, 23, 29, 31) – все они взаимнопросты друг с другом, их произведение равно 6685349671 > 4294967296. Каждый из модулей не превышает 5 бит, то есть операции сложения и умножения будут производиться над 5-битными числами.
Особое значение так же имеет система модулей вида: (2 n -1, 2 n , 2 n +1) в связи с тем, что прямое и обратное преобразование для них выполняется простейшим образом. Что бы получить остаток от деления на 2 n достаточно взять последние n цифр двоичного представления числа.

Арифметические операции

Пример: пусть задана система модулей (3, 5, 7), то есть мы можем выполнять операции, результат которых не превышает 3*5*7 = 105. Умножим два числа 8 и 10.
8 = (8%3, 8%5, 8%7) = (2, 3, 1)
10 = (10%3, 10%5, 10%7) = (1, 0, 3)
8*10 = ((2*1)%3, (3*0)%5, (1*3)%7) = (2, 0, 3)
Проверяем
80 = (80%3, 80%5, 80%7) = (2, 0, 3)

Обратное преобразование

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

  1. На базе Китайской теоремы об остатках или системы ортогональных базисов
  2. На базе полиадического кода (другие названия mixed-radix system, система, со смешанным основанием)

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

Способ, основанный на Китайской теореме об остатках, базируется на следующей идее:
X = (x1, x2, … xn) = (x1, 0, …, 0) + (0, x2, …, 0) + … + (0, 0, …., xn) = x1*(1, 0, …, 0) + x2*(0, 1, …, 0) + … + xn*(0, 0, …, 1).
То есть для обратного преобразования требуется найти систему ортогональных базисов B1 = (1, 0, …, 0), B2 = (0, 1, …, 0), …, BN = (0, 0, …, 1). Эти вектора находятся один раз для заданного базиса, а для их поиска требуется решить уравнение вида: (Mi*bi)%pi = 1, где Mi = M/pi, а bi – искомое число. В этом случае позиционное представление Bi = Mi*bi и
X = (x1*(M1*b1) + x2*(M2*b2) + … + xn*(Mn*bn))%M

Пример: пусть задана система модулей (3, 5, 7), найдем значения Mi и bi (0 b1 = 2
(21*b2)%5 = 1 => b2 = 1
(15*b3)%7 = 1 => b3 = 1
Теперь преобразуем какое-нибудь число в системе остаточных классов. Положим
X = (2, 3, 1) = (2*35*2 + 3*21*1 + 1*15*1)%105 = (140 + 63 + 15)%105 = 218%105 = 8

Минус этого метода заключается в том, что для обратного преобразования требуется умножение и сложение больших чисел (M1, …, Mn), а так же операция взятия остатка по модулю большого числа M.

Оцените статью
Добавить комментарий

Adblock
detector