Сравнительный анализ методов перевода чисел из системы остаточных классов в позиционную систему счисления | Статья в журнале «Молодой ученый»

Отправьте статью сегодня! Журнал выйдет 30 ноября, печатный экземпляр отправим 4 декабря.

Опубликовать статью в журнале

Библиографическое описание:

Ляхов П. А., Голошубова Ю. В., Попова Е. А. Сравнительный анализ методов перевода чисел из системы остаточных классов в позиционную систему счисления // Молодой ученый. — 2017. — №22. — С. 1-6. — URL https://moluch.ru/archive/156/44137/ (дата обращения: 19.11.2019).



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

Ключевые слова: система остаточных классов, позиционная система счисления, Китайская теорема об остатках, обратное преобразование

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

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

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

(1)

Операции сложения, вычитания и умножения в СОК определяются формулами

,(2)

.(3)

Можно выделить два основных преимущества СОК [5]

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

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

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

Восстановление числа по остаткам основано на Китайской Теореме об Остатках (КТО) [8]

Теорема 1 (Китайская теорема об остатках) [8]: Пусть – попарно взаимно простые числа, больше 1, пусть Тогда существует единственное неотрицательное решение по модулю P следующей системы сравнений:

(4)

Следовательно:

(5)

где . Элемент означает мультипликативный обратный для , по модулю [9].

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

На рисунке 1 показана схема перевода числа из СОК в ПСС с использованием КТО.

Рис. 1. Схема перевода числа из СОК в ПСС с применением КТО

Матрица

(6)

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

Определим вектор:

(7)

(8)

Теорема 2 (Новая Китайская теорема об остатках 1) [8]: Пусть дано число в СОК . Число в десятичной системе счисления может быть вычислено по следующей формуле:

(9)

где , при любом

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

На рисунке 2 представлена схема перевода числа из СОК в ПСС с использованием НКТО 1.

Рис. 2. Схема перевода числа из СОК в ПСС с применением НКТО1

Рассмотрим алгоритм перевода из СОК в позиционную систему счисления (, X).

a) Если или :

  1. Выполним , если .
  2. Выполним ((, если .
  3. Найдем :
  4. Получим: .

b) Если :

  1. Определим ,
  2. Получим .

c) Если n=1:

Теорема 3 (Новая Китайская теорема об остатках 2) [8]: Рассмотренный алгоритм корректно восстанавливает число по остаткам .

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

На рисунке 3 схематически представлен процесс перевода числа из СОК в ПСС с использованием НКТО 2.

Рис. 3. Схема перевода числа из СОК в ПСС с применением НКТО 2

Пример. Осуществим процедуру перевода числа по модулям (2,3,5,7) из СОК в ПСС. С использованием известной КТО получим:

, , ,, ,

С использованием НКТО1 имеем:

Составим характеристическую матрицу:

С использованием НКТО2:

.

Таблица 1

Сравнительный анализ методов перевода числа из СОК вПСС

Метод

Используемые блоки

Наибольший путь

Сложение

Умножение

Взятие по модулю

Сложение

Умножение

Взятие по модулю

КТО

1

4

1

1

1

1

НКТО1

4

13

1

2

2

1

НКТО2

6

8

3

4

6

2

Из таблицы 1 видно, что для перевода числа из СОК в ПСС, применяя известную КТО, понадобится 1 блок сложения, 4 блока умножения и 1 блок взятия числа по модулю, при этом наибольший путь равен 3 (по 1 блоку на каждую операцию). Если использовать НКТО1, то понадобится 4 блока сложения, 13 блоков умножения и 1 блок взятия числа по модулю, при этом наибольший путь равен 5 (по 2 блока сложения и умножения и 1 блок взятия по модулю). Если применять НКТО2 данная операция займет 6 блоков сложения, 8 блоков умножения и 3 блока взятия по модулю, и тогда наибольший путь будет равен 12 (4 блока сложения, 6 блоков умножения и 2 блока взятия по модулю). Из таблицы видно, что наименьшее количество блоков понадобится, если использовать ранее известную КТО.

Заключение.

Результаты исследования показали, что наиболее рациональным является применение известной КТО, так как ее реализация требует использования наименьшего количества блоков с операциями. КТО требует на 40 % меньше операций в наибольшем пути, по сравнению с НКТО1, и на 75 % меньше операций в наибольшем пути, по сравнению с НКТО2.

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

Литература:

  1. Червяков Н. И., Велигоша А. В., Калмыков И. А., Иванов П. Е. Цифровые фильтры в системе остаточных классов // Радиоэлектроника. — 1995. Т. 38, № 8. — С. 11–20.
  2. Червяков Н. И., Евдокимов А. А., Головко А. Н. Гибридная нейронная сеть для коррекции ошибок «на лету» в системе остаточных классов // Нейрокомпьютеры: разработка, применение. — 2009, № 10. — С. 13–20.
  3. Cardarilli G. C., A. Nannarelli A., Re M. «Residue number system for low-power DSP applications», Proc. 41st Asilomar Conf. Signals, Syst., Comput., 2007. pp. 1412–1416.
  4. Chervyakov N. I., Lyakhov P. A., M. G. Babenko M. G. Digital filtering of images in a residue number system using finite-field wavelets, Automatic Control and Computer Sciences 48 (3), 2014. pp. 180–189.
  5. Peemen M., Setio A. A. A., Mesman B and Corporaal H. Memorycentric accelerator design for convolutional neural networks, 31st International Conference on Computer Design (ICCD2013), 2013, pp. 13–19.
  6. Farabet C., Martini B., Akselrod P., Talay S., LeCun Y and Culurciello E. Hardware accelerated convolutional neural networks for synthetic vision systems, Int’l Symp. on Circuits and Systems (ISCAS2010), 2010, pp. 257–260.
  7. Chervyakov N. I., Molahosseini A. S., Lyakhov P. A., Babenko M. G., Deryabin M. A.: «Residue-to-Binary Conversion for General Moduli Sets Based on Approximate Chinese Remainder Theorem», International Journal of Computer Mathematics, 2016, pp. 1–17.
  8. Parhami B. Computer Arithmetic: Algorithms and Hardware Designs/ B. Parhami, Oxford University Press, Inc., 2000. – 492 p.

[1] Работа выполнена при поддержке гранта Президента Российской Федерации МК-5980.2016.9.

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


Похожие статьи

Применение технологии смешанного обучения в модели...

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

– умножать и делить числа на основание позиционной системы счисления. Метапредметные результаты

Разработка эффективной реализации алгоритмов выполнения...

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

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

...числа, было принято решение хранить десятичное число в системе счисления с

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

Системы счисления | «Молодой

Даже для того, чтобы прочитать число нужно сначала выполнить действия сложения и

Достоинства позиционных систем. – простота выполнения арифметических операций

Поэтому вавилонская система счисления считается позиционной, но непоследовательной.

Создание криптографии с помощью модулярной математики

...шифрования, но общая система шифрования представлена следующим образом на схеме 2

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

a≡b(mod m), если остаток от деления a на m равен b, при условии что a, b и m-целые числа [2...

Проблемы правового регулирования виртуальной валюты в России

В ряде стран официально разрешены операции с криптовалютами, к

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

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

Китайская теорема об остатках в области главных идеалов

Ключевые слова: китайская теорема об остатках, система сравнений, алгоритм Гарнера, кольцо многочленов, кольцо целых

Теорема 1 (китайская теорема об остатках):Рассмотрим область главных идеалов .

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

Китайская теорема об остатках в области главных идеалов

Ключевые слова: китайская теорема об остатках, система сравнений, алгоритм Гарнера, кольцо многочленов, кольцо целых чисел, изоморфизм колец.

Данная теорема помогает свести некоторое сравнение по модулю к системе более простых сравнений, и наоборот...

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

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

Похожие статьи

Применение технологии смешанного обучения в модели...

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

– умножать и делить числа на основание позиционной системы счисления. Метапредметные результаты

Разработка эффективной реализации алгоритмов выполнения...

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

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

...числа, было принято решение хранить десятичное число в системе счисления с

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

Системы счисления | «Молодой

Даже для того, чтобы прочитать число нужно сначала выполнить действия сложения и

Достоинства позиционных систем. – простота выполнения арифметических операций

Поэтому вавилонская система счисления считается позиционной, но непоследовательной.

Создание криптографии с помощью модулярной математики

...шифрования, но общая система шифрования представлена следующим образом на схеме 2

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

a≡b(mod m), если остаток от деления a на m равен b, при условии что a, b и m-целые числа [2...

Проблемы правового регулирования виртуальной валюты в России

В ряде стран официально разрешены операции с криптовалютами, к

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

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

Китайская теорема об остатках в области главных идеалов

Ключевые слова: китайская теорема об остатках, система сравнений, алгоритм Гарнера, кольцо многочленов, кольцо целых

Теорема 1 (китайская теорема об остатках):Рассмотрим область главных идеалов .

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

Китайская теорема об остатках в области главных идеалов

Ключевые слова: китайская теорема об остатках, система сравнений, алгоритм Гарнера, кольцо многочленов, кольцо целых чисел, изоморфизм колец.

Данная теорема помогает свести некоторое сравнение по модулю к системе более простых сравнений, и наоборот...

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

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

Задать вопрос