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

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

 

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

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

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

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

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

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

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

Суть приближенного метода сравнения модулярных чисел основана на использовании относительной величины исходного числа к полному диапазону Китайской теоремы об остатках, которая связывает позиционное число A с его представлением в остатках (α₁, α₂, …, α_n), где α_i - наименьшие неотрицательные вычеты числа, относительно модулей системы остаточных классов p₁, p₂, …, p_n следующим выражением

где , p_i - модули СОК, - мультипликативная инверсия P_i относительно p_i, и .

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

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

Пример 1. Пусть дана система оснований p₁=2, p₂=3, p₃=5, p₄=7, объем диапазона P=2·3·5·7=210. Допустим, что в заданной СОК будут представлены только положительные числа. Величины , , , . Сравним два числа A₁=25 и А₂=30, представленные в СОК по основаниям p₁, p₂, p₃, p₄, то есть A₁=(1,1,0,4), A₂=(0,0,0,2). Для этого найдем константы .

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

Так как , то A₂>A₁, есть 30>25.

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

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

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

Число A₂ входит в отрицательный интервал, то есть .

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

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

1. Определить знаки A₁ и A₂.

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

3. Если A₁ и A₂ имеют один и тот же знак, то проверяется .

4. Если A₁ и A₂ имеют разные знаки, то , при A₁<A₂ и при A₁>A₂.

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

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

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

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

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

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

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

Пример 3. Сравнить модулярные числа разных знаков A₁ и -A₂. Система оснований СОК такая же, как и в примере 1: p₁=2, p₂=3, p₃=5, p₄=7.

Пусть число A₁=17=(1,2,2,3), A₂=-19=(1,1,4,5). Тогда дополнительный код A₂=(p₁-1,p₂-1,p₃-4.p₄-5)=(1,2,1,2). Требуется сравнить числа A₁ и A₂.

Проверка знака числа A₁. Для определения знака числа A₁ сравним его с константой . Тогда относительная величина числа A₁ по отношению к величине числа К определяется как

.

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

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

Определим относительные величины и .

,

.

Найдем разность относительных величин, тогда - разность положительная. Следовательно A₁>A₂.

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

Схема модулярного сравнения чисел, основанная на принципах использования относительных величин приведена на рисунке 3 и содержит: входные регистры 1, 9 для хранения чисел, соответствующие A и B которые поступают по шинам 15 и 16; схема определения знаков чисел A и B, соответственно, 2 и 8, схема сдвига полярности 3, 7, соответственно чисел A и B, просмотровые таблицы 5, 7, содержание таблиц для хранения произведения констант и разрядов СОК и соответственно, таблицы 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, который в случае разных знаков формирует сигнал сдвига полярности чисел, соответствующий константе C_i, и подает на вход схем 3 и 7, где происходит сдвиг полярности чисел. Выходы систем схем сдвига полярности 3 и 7, соответственно для чисел А и В, являются адресными входами просмотровых таблиц 5 и 6,

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

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

,

.

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

.

Разность отрицательная, поэтому число 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, согласно которых осуществляется выборка значений констант , в условиях примера эти значения будут равны для 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 поступают на вход сумматора. В результате суммирования получим

.

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

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

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

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

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

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

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

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