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

Классы МПК:G06F7/02 сравнение цифровых данных
G06F7/72 с помощью арифметического остатка
Автор(ы):, , , ,
Патентообладатель(и):Федеральное государственное автономное образовательное учреждение высшего профессионального образования "Северо-Кавказский федеральный университет" (RU)
Приоритеты:
подача заявки:
2011-09-27
публикация патента:

Изобретение относится к вычислительной технике и может быть использовано в вычислительных системах, функционирующих в системе остаточных классов. Техническим результатом является повышение быстродействия устройства и сокращение аппаратных затрат. Устройство содержит входные регистры, схемы определения знака, схемы сдвига полярности чисел, просмотровые таблицы (память) для хранения констант устройство для сравнения чисел, представленных в системе остаточных   классов, патент № 2503992 и устройство для сравнения чисел, представленных в системе остаточных   классов, патент № 2503992 , сумматор и логический элемент «исключающее или», схему анализа знаков чисел. 3 ил. устройство для сравнения чисел, представленных в системе остаточных   классов, патент № 2503992

устройство для сравнения чисел, представленных в системе остаточных   классов, патент № 2503992 устройство для сравнения чисел, представленных в системе остаточных   классов, патент № 2503992 устройство для сравнения чисел, представленных в системе остаточных   классов, патент № 2503992

Формула изобретения

Устройство для сравнения чисел, представленных в системе остаточных классов, содержащее схему анализа знаков чисел, отличающееся тем, что в него введены схемы определения знаков чисел A и B, схемы сдвига полярности чисел, просмотровые таблицы (память) для хранения констант устройство для сравнения чисел, представленных в системе остаточных   классов, патент № 2503992 и устройство для сравнения чисел, представленных в системе остаточных   классов, патент № 2503992 сумматор и входные регистры, на вход которых поступают числа A и B, представленные в системе остаточных классов, выходы которых соединены с первыми входами схем сдвига полярности и входами схем определения знаков чисел, выходы которых соединены с элементом «исключающее или», выход которой соединен со вторыми входами схем сдвига полярности, выход которых соединен с адресными входами просмотровых таблиц, выходы которых соединены с сумматором, выход которого соединен со схемой анализа сравниваемых чисел, выходы которых являются выходами устройства сравнения чисел, представленные в системе остаточных классов A=B, A>B и A<B.

Описание изобретения к патенту

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

Известны устройства для сравнения n разрядных чисел. (А.С. № 675420, Б.И. № 27, 1979) состоящее из триггеров, логических элементов, узлов хранения, регистров, дешифраторов, запоминающих матриц и счетчика. Однако данное устройство обладает большой сложностью и функционально не может быть использовано для сравнения модулярных чисел.

Наиболее близким по технической сущности к заявленному устройству является устройство для сравнения чисел (А.С. № 541164, БИ № 48, 1977.), содержащее решающие матрицы, блоки анализа полиадических коэффициентов алгебраического сравнения, блоки анализа полиадических коэффициентов сравнений по модулю, блок формирования знака и логические элементы «или».

Недостатками данного устройства является низкое быстродействие и его сложность.

Целью настоящего изобретения является повышения скорости сравнения чисел и сокращение аппаратных затрат.

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

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

Суть приближенного метода сравнения модулярных чисел основана на использовании относительной величины исходного числа к полному диапазону Китайской теоремы об остатках, которая связывает позиционное число A с его представлением в остатках (устройство для сравнения чисел, представленных в системе остаточных   классов, патент № 2503992 1, устройство для сравнения чисел, представленных в системе остаточных   классов, патент № 2503992 2, устройство для сравнения чисел, представленных в системе остаточных   классов, патент № 2503992 , устройство для сравнения чисел, представленных в системе остаточных   классов, патент № 2503992 n), где устройство для сравнения чисел, представленных в системе остаточных   классов, патент № 2503992 i - наименьшие неотрицательные вычеты числа, относительно модулей системы остаточных классов p1 , p2, устройство для сравнения чисел, представленных в системе остаточных   классов, патент № 2503992 , pn следующим выражением

устройство для сравнения чисел, представленных в системе остаточных   классов, патент № 2503992

где устройство для сравнения чисел, представленных в системе остаточных   классов, патент № 2503992 , pi - модули СОК, устройство для сравнения чисел, представленных в системе остаточных   классов, патент № 2503992 - мультипликативная инверсия Pi относительно pi, и устройство для сравнения чисел, представленных в системе остаточных   классов, патент № 2503992 .

Если (1) разделить на константу P, то получим приближенное значение

устройство для сравнения чисел, представленных в системе остаточных   классов, патент № 2503992

где устройство для сравнения чисел, представленных в системе остаточных   классов, патент № 2503992 - константы выбранной системы, а устройство для сравнения чисел, представленных в системе остаточных   классов, патент № 2503992 i - разряды числа, представленного в СОК, при этом значение каждой суммы будет в интервале [0, 1). Конечный результат суммы определяется после суммирования и отбрасывания целой части числа с сохранением дробной части суммы. Дробная часть может быть записана также как Amod1, потому что устройство для сравнения чисел, представленных в системе остаточных   классов, патент № 2503992 . Количество разрядов дробной части числа определяется максимально возможной разностью между соседними числами. При необходимости точного сравнения необходимо вычислить значение (2), которое является эквивалентом преобразования из СОК в позиционную систему счисления. Для решения задач основных процедур принятия решения достаточно знать приблизительно значения чисел A и B по отношению к динамическому диапазону P, которое выполняется достаточно просто, но при этом правильно определяет соотношение A=B, A>B или A<B.

Пример 1. Пусть дана система оснований p1=2, p2=3, p3=5, p4=7, объем диапазона P=2·3·5·7=210. Допустим, что в заданной СОК будут представлены только положительные числа. Величины устройство для сравнения чисел, представленных в системе остаточных   классов, патент № 2503992 , устройство для сравнения чисел, представленных в системе остаточных   классов, патент № 2503992 , устройство для сравнения чисел, представленных в системе остаточных   классов, патент № 2503992 , устройство для сравнения чисел, представленных в системе остаточных   классов, патент № 2503992 . Сравним два числа A1=25 и А2=30, представленные в СОК по основаниям p1, p2 , p3, p4, то есть A1=(1,1,0,4), A2=(0,0,0,2). Для этого найдем константы устройство для сравнения чисел, представленных в системе остаточных   классов, патент № 2503992 .

устройство для сравнения чисел, представленных в системе остаточных   классов, патент № 2503992

устройство для сравнения чисел, представленных в системе остаточных   классов, патент № 2503992

устройство для сравнения чисел, представленных в системе остаточных   классов, патент № 2503992

устройство для сравнения чисел, представленных в системе остаточных   классов, патент № 2503992

По (2) получим

устройство для сравнения чисел, представленных в системе остаточных   классов, патент № 2503992

устройство для сравнения чисел, представленных в системе остаточных   классов, патент № 2503992

Так как устройство для сравнения чисел, представленных в системе остаточных   классов, патент № 2503992 , то A2>A1, есть 30>25.

Рассмотрим случай, когда рабочий диапазон разбит на два интервала устройство для сравнения чисел, представленных в системе остаточных   классов, патент № 2503992 - положительные числа, и устройство для сравнения чисел, представленных в системе остаточных   классов, патент № 2503992 - отрицательные числа. В традиционных ЭВМ определение абсолютных величин двух чисел A1 и A2 производится путем вычисления A1-A2 и определения знака разности. В системе остаточных классов недостаточно определить знак путем устройство для сравнения чисел, представленных в системе остаточных   классов, патент № 2503992 , так как A1-A2 могут выходить за диапазон устройство для сравнения чисел, представленных в системе остаточных   классов, патент № 2503992 и это приведет к неправильному результату.

Пример 2. Вариант неправильного определения сравнения чисел на основе определения знака.

Пусть устройство для сравнения чисел, представленных в системе остаточных   классов, патент № 2503992 , устройство для сравнения чисел, представленных в системе остаточных   классов, патент № 2503992 очевидно, что A1>A2. На основании (2) определим устройство для сравнения чисел, представленных в системе остаточных   классов, патент № 2503992 и устройство для сравнения чисел, представленных в системе остаточных   классов, патент № 2503992 . Основания СОК выберем такими же, как и в первом примере. Тогда A1=(0,1,0,0) и A2=(0,2,0,0) - дополнительный код отрицательного числа. Находим устройство для сравнения чисел, представленных в системе остаточных   классов, патент № 2503992 , устройство для сравнения чисел, представленных в системе остаточных   классов, патент № 2503992 .

Число A2 входит в отрицательный интервал, то есть устройство для сравнения чисел, представленных в системе остаточных   классов, патент № 2503992 .

Следовательно сравнение приведет к неверному результату A1<A2.

Для правильного определения сравнения чисел необходимо проверить знаки A1 и A2 и тогда алгоритм сравнения будет иметь вид:

1. Определить знаки A1 и A2.

2. Если A1 и A 2 без знаков, то положительный знак разности относительных величин означает большее число.

3. Если A 1 и A2 имеют один и тот же знак, то проверяется устройство для сравнения чисел, представленных в системе остаточных   классов, патент № 2503992 .

4. Если A1 и A2 имеют разные знаки, то устройство для сравнения чисел, представленных в системе остаточных   классов, патент № 2503992 , при A1<A2 и устройство для сравнения чисел, представленных в системе остаточных   классов, патент № 2503992 при A1>A2.

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

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

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

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

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

Показанное на рисунке 2 вращение, называется сдвигом полярности и его можно осуществить путем прибавления перед сравнением модулярных чисел константы устройство для сравнения чисел, представленных в системе остаточных   классов, патент № 2503992 при нечетном P или устройство для сравнения чисел, представленных в системе остаточных   классов, патент № 2503992 при четных P к каждому Aустройство для сравнения чисел, представленных в системе остаточных   классов, патент № 2503992 [0, P).

Если устройство для сравнения чисел, представленных в системе остаточных   классов, патент № 2503992 , то сдвиг полярности в пределах СОК оказывается простым остатком, определяемом по формуле устройство для сравнения чисел, представленных в системе остаточных   классов, патент № 2503992 , в которой устройство для сравнения чисел, представленных в системе остаточных   классов, патент № 2503992 ic обозначает остаточные цифры после сдвига полярности.

Пример 3. Сравнить модулярные числа разных знаков A1 и -A2. Система оснований СОК такая же, как и в примере 1: p1=2, p2 =3, p3=5, p4=7.

Пусть число A1=17=(1,2,2,3), A2=-19=(1,1,4,5). Тогда дополнительный код A2=(p1-1,p2 -1,p3-4.p4-5)=(1,2,1,2). Требуется сравнить числа A1 и A2.

Проверка знака числа A1. Для определения знака числа A 1 сравним его с константой устройство для сравнения чисел, представленных в системе остаточных   классов, патент № 2503992 . Тогда относительная величина числа A1 по отношению к величине числа К определяется как

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

Представление константы устройство для сравнения чисел, представленных в системе остаточных   классов, патент № 2503992 . Далее находим устройство для сравнения чисел, представленных в системе остаточных   классов, патент № 2503992 . Отсюда устройство для сравнения чисел, представленных в системе остаточных   классов, патент № 2503992 . Разница положительная, то есть число устройство для сравнения чисел, представленных в системе остаточных   классов, патент № 2503992 , поэтому число A1 входит в первый интервал и является положительным.

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

Определим относительные величины устройство для сравнения чисел, представленных в системе остаточных   классов, патент № 2503992 и устройство для сравнения чисел, представленных в системе остаточных   классов, патент № 2503992 .

устройство для сравнения чисел, представленных в системе остаточных   классов, патент № 2503992 ,

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

Найдем разность относительных величин, тогда устройство для сравнения чисел, представленных в системе остаточных   классов, патент № 2503992 - разность положительная. Следовательно A1>A 2.

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

Схема модулярного сравнения чисел, основанная на принципах использования относительных величин приведена на рисунке 3 и содержит: входные регистры 1, 9 для хранения чисел, соответствующие A и B которые поступают по шинам 15 и 16; схема определения знаков чисел A и B, соответственно, 2 и 8, схема сдвига полярности 3, 7, соответственно чисел A и B, просмотровые таблицы 5, 7, содержание таблиц для хранения произведения констант и разрядов СОК устройство для сравнения чисел, представленных в системе остаточных   классов, патент № 2503992 и устройство для сравнения чисел, представленных в системе остаточных   классов, патент № 2503992 соответственно, таблицы 5-1, 5-3, 5-n для чисел A и 6-1, 6-2, 6-n для чисел B, сумматор 10: логический элемент «исключающее или» 4; схемы анализа знака 11 с выходами: соответственно, A=B 12, A>B 13, A<B 14. Работа устройства для сравнения модулярных чисел осуществляется следующим образом.

На входные регистры 1, 9 по шинам 15, 16, соответственно, поступают исходные числа A и B, представленные в СОК, которые необходимо сравнить. Выходы регистров соединены с 2, 3 и 7, 8, соответственно, для определения знака чисел A и B и сдвига полярности чисел A и B. Выходные сигналы схем определения знаков чисел 2 и 8, соответственно чисел A и B (0 - положительное число, 1 - отрицательное число), поступают на вход логического элемента «исключающего или» 4, который в случае разных знаков формирует сигнал сдвига полярности чисел, соответствующий константе Ci, и подает на вход схем 3 и 7, где происходит сдвиг полярности чисел. Выходы систем схем сдвига полярности 3 и 7, соответственно для чисел А и В, являются адресными входами просмотровых таблиц 5 и 6,

Элементы памяти, просмотровые таблицы (LUT - таблицы) 5-1, 5-2 5-n и 6-1, 6-2, 6-n, соответственно, хранят произведения устройство для сравнения чисел, представленных в системе остаточных   классов, патент № 2503992 и устройство для сравнения чисел, представленных в системе остаточных   классов, патент № 2503992 прием для числа устройство для сравнения чисел, представленных в системе остаточных   классов, патент № 2503992 чисел представляется в дополнительный код, который поступает на вход сумматора 10, в котором происходит суммирование в дополнительном коде. Результат суммирования поступает на блок анализа 11, где определяется: равенство чисел A=B шина 12, A>B шина 13 и A<B шина 14.

Пример 4. Пусть дана система оснований p1=2, p2=3, p3=5, p4 =7. Сравнить модулярные числа A=(1,2,2,3) и B=(1,2,1,2). Исходные числа находятся в регистрах RGA и RGB, которые поступают на входы схем определения знака числа СОЗЧ-А и СОЗЧ-В. В этих схемах происходит сравнение исходных чисел с константой устройство для сравнения чисел, представленных в системе остаточных   классов, патент № 2503992 .

устройство для сравнения чисел, представленных в системе остаточных   классов, патент № 2503992 ,

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

Разность положительная, то есть устройство для сравнения чисел, представленных в системе остаточных   классов, патент № 2503992 , поэтому число А входит в первый интервал, и является положительным.

устройство для сравнения чисел, представленных в системе остаточных   классов, патент № 2503992

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

Разность отрицательная, поэтому число B входит во второй интервал и является отрицательным.

Результат анализа знаков чисел A и B образуется на выходе элемента исключающее «или» который поступает на вход схем сдвига полярности ССП-А и ССП-В. На выходах схем сдвига полярности образуются данные соответственно A=(1,2,2,3)+(1,0,0,0)=(0,2,2,3) и B=(1,2,1,2)+(1,0,0,0)=(0,2,1,2). Выходные данные схем сдвига полярности являются адресными входами просмотровых таблиц LUT-A и LUT-B, согласно которых осуществляется выборка значений констант устройство для сравнения чисел, представленных в системе остаточных   классов, патент № 2503992 , в условиях примера эти значения будут равны для LUT-A (0;0,3333·2;0,6·2;0,5714·3) и для LUT-B (0;0,3333·2;0,6·1;0,5714·2). Выходные сигналы просмотровых таблиц LUT-A и LUT-B поступают на вход сумматора. В результате суммирования получим

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

Разность положительная, так как дополнительный код положительного числа равен самому числу, следовательно A>B. Действительно, число A=17, B=-19.

Результаты сумматора анализируются в схеме сумматора, при этом:

если разность равна 0, то A=B,

если разность положительная, то A>B,

если разность отрицательная, то A<B.

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

Если же использовать рекурсивное сдваивание, тогда логическая глубина определяется выражением [log2n]+3. В известных схемах логическая глубина с учетом определения коэффициентов ОПСС определяется как 2n+5.

Класс G06F7/02 сравнение цифровых данных

устройство сравнения двоичных чисел -  патент 2507564 (20.02.2014)
устройство сравнения двоичных чисел -  патент 2504825 (20.01.2014)
способ пространственно-временной коммутации -  патент 2458383 (10.08.2012)
система и способ сравнения файлов на основе шаблонов функциональности -  патент 2427890 (27.08.2011)
отслеживание и синхронизация частичного изменения элементов -  патент 2421780 (20.06.2011)
устройство сравнения двоичных чисел -  патент 2420789 (10.06.2011)
компаратор двоичных чисел -  патент 2393526 (27.06.2010)
компаратор двоичных чисел -  патент 2389063 (10.05.2010)
селектор двоичных чисел -  патент 2365975 (27.08.2009)
устройство для оценки и сравнения эффективности функционирования однотипных организаций -  патент 2363042 (27.07.2009)

Класс G06F7/72 с помощью арифметического остатка

устройство для преобразования из полиномиальной системы классов вычетов в позиционный код -  патент 2513915 (20.04.2014)
способ организации выполнения операции умножения двух чисел в модулярно-позиционном формате представления с плавающей точкой на универсальных многоядерных процессорах -  патент 2509345 (10.03.2014)
устройство для определения знака модулярного числа -  патент 2503995 (10.01.2014)
способ организации умножения чисел с плавающей запятой, представленных в системе остаточных классов -  патент 2500018 (27.11.2013)
накапливающий сумматор по модулю -  патент 2500017 (27.11.2013)
способ организации умножения чисел с плавающей запятой, представленных в системе остаточных классов -  патент 2485574 (20.06.2013)
полный одноразрядный сумматор по модулю -  патент 2484519 (10.06.2013)
устройство для обнаружения переполнения динамического диапазона, определения ошибки и локализации неисправности вычислительного канала в эвм, функционирующих в системе остаточных классов -  патент 2483346 (27.05.2013)
ячейка однородной вычислительной среды, однородная вычислительная среда и устройство для конвейерных арифметических вычислений по заданному модулю -  патент 2477513 (10.03.2013)
устройство для формирования остатка по произвольному модулю от числа -  патент 2445730 (20.03.2012)
Наверх