Устройство сравнения чисел, представленных в системе остаточных классов
APPARATUS FOR COMPARING NUMBERS REPRESENTED IN RESIDUE NUMBER SYSTEM

Изобретение относится к вычислительной технике и предназначено для сравнения чисел, представленных в системе остаточных классов.
Известно устройство для сравнения чисел в системе остаточных классов на основе интервально-позиционных характеристик (патент РФ 2557444, опубл. 20.07.2015), содержащее группы входных регистров для хранения сравниваемых модулярных чисел, блоки вычисления интервально-позиционной характеристики, блок поразрядного сравнения модулярных чисел, блоки проверки правильности интервально-позиционных характеристик, блок сравнения интервально-позиционных характеристик, двухвходовой двоичный дешифратор.
Недостатком данного устройства является использование ресурсоемких операций деления с числами с плавающей точкой, что снижает скорость работы и требует округлений.
Наиболее близким к заявленному изобретению является устройство для сравнения чисел, представленных в системе остаточных классов (патент РФ 2503992, опубл. 10.01.2014), содержащее входные регистры, схемы определения знака, схемы сдвига полярности чисел, просмотровые таблицы (память) для хранения констант  и , сумматор и логический элемент «XOR», схему анализа знаков чисел.
Недостатком данного устройства является низкая точность, связанная с представлением чисел в формате с плавающей точкой, а именно с ошибками округления.
Техническим результатом заявляемого изобретения является увеличение скорости и точности вычислений сравнения чисел, представленных в системе остаточных классов.
введены
Данный технический результат достигается тем, что в устройство сравнения чисел, представленных в системе остаточных классов, содержащее  входов остатков первого числа, где  - количество модулей  системы остаточных классов,  входов остатков второго числа,  регистров хранения первого числа,  регистров хранения второго числа, схему определения знака первого числа, схему определения знака второго числа, логический элемент XOR, схему анализа знака, выход сравнения, где входы остатков первого и второго чисел соединены с соответствующими регистрами хранения первого и второго чисел, выходы которых подключены к входам соответствующих схем определения знака первого и второго чисел, выходы которых подключены ко входам логического элемента XOR, а выход схемы анализа знака является выходом сравнения устройства,  блок проверки равенства, блок сумматоров, схема определения знака разности, где выходы регистров хранения первого числа подключены к первым информационным входам блока проверки равенства и блока сумматоров, выходы регистров хранения второго числа подключены к вторым информационным входам блока проверки равенства и через инверторы к вторым информационным входам блока сумматоров, на вход переноса блока сумматоров подается сигнал логической единицы, выходы блока сумматоров подключены ко входам схемы определения знака разности, выход которой подключен к четвертому входу схемы анализа знака, третий вход которой подключен к выходу логического элемента XOR, второй вход подключен к выходу блока проверки равенства, первый и пятый входы подключены к схемам определения знака первого и второго чисел соответственно, при этом блок проверки равенства содержит  логических элементов XOR и логический элемент ИЛИ, где первые входы  логических элементов XOR подключены к первым информационным входам блока проверки равенства, вторые входы  логических элементов XOR подключены ко вторым информационным входам блока проверки равенства, а выходы подключены к входам логического элемента ИЛИ, инвертированный выход которого является выходом блока проверки равенства, схема анализа знаков содержит два мультиплексора, при этом первый вход схемы анализа знаков подключен к младшему биту второго информационного входа первого мультиплексора, второй вход схемы анализа знаков подключен к управляющему входу и старшему и младшему битам первого информационного входа второго мультиплексора, третий вход схемы анализа знаков подключен к управляющему входу первого мультиплексора, четвертый вход схемы анализа знаков подключен к младшему биту и через инвертор к старшему биту первого информационного входа первого мультиплексора, пятый вход схемы анализа знаков подключен к старшему биту второго информационного входа первого мультиплексора, выходы которого подключены ко второму информационному входу второго мультиплексора, выходы которого являются выходом схемы анализа знаков, при этом схемы определения знака первого числа, второго числа и разности содержат  вычислительную ступень, при этом я вычислительная ступень, где , содержит  сумматоров по модулю  и  блоков умножения на веса  по модулю , где  и  - мультипликативная инверсия модуля  по модулю  и модули упорядочены по возрастанию и  является степенью 2, в первой вычислительной ступени первые информационные входы х сумматоров по модулю  через инверторы подключены к первому входу схемы определения знака, вторые информационные входы х сумматоров по модулю  подключены к )-м входам схемы определения знака, на входы переносов х сумматоров по модулю  подается сигнал логической единицы, выходы х сумматоров по модулю  подключены ко входам соответствующих блоков умножения на веса  по модулю , , в x вычислительных ступенях, , первые информационные входы х сумматоров по модулю  через инверторы подключены к выходу первого блока умножения на веса  по модулю -ой вычислительной ступени, вторые информационные входы х сумматоров по модулю  подключены к выходам -ых блоков умножения на веса  по модулю -ой вычислительной ступени, на входы переносов х сумматоров по модулю  подается сигнал логической единицы, выходы х сумматоров по модулю  подключены к входам -ых блоков умножения на веса  по модулю ,  старший бит выхода блока умножения на веса -й вычислительной ступени является выходом схемы определения знака.
Сущность изобретения основана на следующем математическом аппарате. В системе остаточных классов (СОК) любое число  однозначно представляется набором остатков  от деления числа  на взаимно простые модули СОК , где ,  - рабочий диапазон СОК, . Возьмем систему остаточных классов с модулями . Знак в системе остаточных классов чаще всего вводится разбиением диапазона на две части, тогда с учетом динамического диапазона  в СОК можно представить числа , если  четное.
Сравнение чисел в СОК является немодульной операцией, часто требующей выполнения вычислительно сложных операций нахождения позиционных характеристик чисел. Другим способом является сравнение чисел на основе определения знака. Для сравнения двух чисел  и  можно в случае, если ,  определить знаки чисел  и , если числа разного знака, то можно сделать однозначный вывод, какое число больше, иначе необходимо определить знак разности . Если  - отрицательный, то , если положительный, . Необходимость определения знака каждого числа связана с возможностью переполнения динамического диапазона при выполнении арифметических операций.
Функция определения знака числа, представленного в СОК, определяется следующим образом:
Таким образом  можно представить в виде:
<img file="00000044.jpg" he="12" wi="24" img-content="undefined" img-format="jpg" />
(1)
Используя свойство  и формулу (1) определение знака сводится двухэтапному алгоритму: первый этап - деление на , второй этап - деление на , формально математически определяется следующей формулой
Запишем процесс определения в виде алгоритма:
Алгоритм 1.
Определение знака числа
Вход:
- модули СОК
- представление числа  в СОК
- синоптические веса
Выход
:  - положительное число,  - отрицательное число
1. Для  от  до  выполнять:
1.1. Для  от  до  выполнять: \\ деление на
1.1.1.
2. Возвратить
На первом этапе вычисляется  с помощью  деления на модули СОК  соответственно. На втором этапе вычисляется .
Таким образом на основе проверки равенства и трех определений знака можно сравнить два числа, представленных в системе остаточных классов.
Устройство поясняется фигурами 1-4. На фигуре 1 показана общая структурная схема устройства, на фигуре 2 - блок проверки равенства, на фигуре 3 - схема анализа знаков чисел, на фигуре 4 -схема определения знака.
На входы остатков первого числа 1.1-1.n подаются остатки от деления числа  на модули , которые затем поступают для хранения в регистры хранения первого числа 3.1-3.n. На входы остатков второго числа 2.1-2.n подаются остатки от деления числа  на модули , которые затем поступают для хранения в регистры хранения второго числа 4.1-4.n. Далее данные с выходов регистров хранения первого числа 3.1-3.n поступают на соответствующие входы схемы определения знака первого числа 5, которая поясняется фигурой 4, данные с выходов регистров хранения второго числа 4.1-4.n поступают на соответствующие входы схемы определения знака второго числа 6, знаки первого и второго числа с выходов схем определения знака первого 5 и второго 6 чисел поступают на входы логического элемента XOR 10 и первый и пятый входы схемы анализа знака 11. Выход логического элемента XOR 10 поступает на третий вход схемы анализа знака 11.
Схема определения знака поясняется фигурой 4, которая содержит n-1 вычислительных ступеней, при этом -я вычислительная ступень, где , содержит  сумматоров по модулю  17.i.1 - 17.i.n-i и  блоков умножения на веса  по модулю  18.i.1 - 18.i.n-i, где  и  - мультипликативная инверсия модуля  по модулю . В первой вычислительной ступени первые информационные входы х сумматоров по модулю  17.1.1 - 17.1.n-1 через инверторы подключены к первому входу схемы определения знака, вторые информационные входы х сумматоров по модулю  17.1.1 - 17.1.n-1 подключены к соответствующим )-м входам схемы определения знака, на входы переносов х сумматоров по модулю  17.1.1 - 17.1.n-1 подается сигнал логической единицы, выходы х сумматоров по модулю  17.1.1 - 17.1.n-1 подключены ко входам соответствующих блоков умножения на веса  по модулю  18.1.1 - 18.1.n-1, . Во второй вычислительной ступени первые информационные входы х сумматоров по модулю  17.2.1 - 17.2.n-2 через инверторы подключены к выходу первого блока умножения на веса  по модулю  первой ступени, вторые информационные входы х сумматоров по модулю  17.2.1 - 17.2.n-2 подключены к выходам соответствующих -ых блоков умножения на веса  по модулю  первой ступени, на входы переносов х сумматоров по модулю  17.2.1 - 17.2.n-2 второй ступени подается сигнал логической единицы, выходы х сумматоров по модулю  17.2.1 - 17.2.n-2 второй ступени подключены ко входам соответствующих -ых блоков умножения на веса  по модулю  18.2.1 - 18.2.n-2, . И так далее, на  вычислительной ступени первый информационный вход сумматора по модулю  17.n-1.1 через инвертор подключен к выходу первого блока умножения на веса  по модулю  18.n-2.1 -й ступени, второй информационный вход сумматора по модулю  17.n-1.1 подключен к выходу второго блока умножения на веса  по модулю  18.n-2.2 -й ступени , на вход переноса поступает сигнал логической единицы, а выход соединен со входом первого блока умножения на веса  по модулю  18.n-1.1 -й ступени, старший бит выхода которого является выходом схемы определения знака.
При этом блоки 18 умножения на веса  по модулю  могут быть выполнены как в виде памяти, так и в виде вычислительных устройств. Сумматоры 17 по модулю  за счет инвертирования сигнала с одного из входов и сигнала логической единицы на входе переноса фактически выполняют операцию вычитания.
Также данные с выходов регистров хранения первого числа 3.1-3.n поступают на первые информационные входы блока проверки равенства 7, на вторые информационные входы которого поступают данные с выходов регистров хранения второго числа 4.1-4.n. Блок проверки равенства 7 поясняется фигурой 2. Он содержит  логических элементов XOR 13.1-13.n и логический элемент ИЛИ 14. В логических элементах XOR 13.1-13.n происходит сравнение поступающих остатков чисел  и  по модулям , поступающих на первые и вторые информационные входы блока проверки равенства 7. На выходы данных логических элементов XOR 13.1-13.n подается сигнал логической единицы, если на входы подаются отличные значения, и сигнал логического нуля, если на входах одинаковые значения. Логический элемент ИЛИ 14 через инвертор выдает сигнал логической единицы в случае, если числа равны и логического нуля, если хотя бы один из остатков у чисел  и  не совпадает. Выход блока проверки равенства 7 подключен ко второму входу схемы анализа знака 11.
Также данные с выходов регистров хранения первого числа 3.1-3.n поступают на первые информационные входы блока сумматоров 8, на вторые информационные входы которого через инверторы поступают данные с выходов регистров хранения второго числа 4.1-4.n, на вход переноса поступает сигнал логической единицы. Это эквивалентно вычитанию из числа , представленного в СОК, числа . Результаты вычитания по каждому модулю поступают на входы схемы определения знака разности 9, которая поясняется фигурой 4. Выход схемы определения знака разности 9 подключен к четвертому входу схемы анализа знака 11, которая поясняется фигурой 4.
Схема анализа знака 11 содержит первый 15 и второй 16 мультиплексоры. При этом первый вход схемы анализа знаков 11 подключен к младшему биту второго информационного входа первого мультиплексора 15. Второй вход схемы анализа знаков 11 подключен к управляющему входу и старшему и младшему битам первого информационного входа второго мультиплексора 16. Третий вход схемы анализа знаков 11 подключен к управляющему входу первого мультиплексора 15. Четвертый вход схемы анализа знаков 11 подключен к младшему биту и через инвертор к старшему биту первого информационного входа первого мультиплексора 15. Пятый вход схемы анализа знаков 11 подключен к старшему биту второго информационного входа первого мультиплексора 15, выходы которого подключены ко второму информационному входу второго мультиплексора 16, выходы которого являются выходом схемы анализа знаков 11. Если на третий вход схемы анализа знака 11 с выхода логического элемента XOR 10 на управляющий вход первого мультиплексора поступает сигнал логической единицы, это означает, что знаки первого и второго числа, полученные в схемах определения знака первого 5 и второго 6 чисел отличаются. Если знак первого числа, поступающий на первый вход схемы анализа знака 11 равен 0 (положительное), а знак второго числа, , поступающий на пятый вход схемы анализа знака 11 равен 1 (отрицательное), то на выход первого мультиплексора 15 подается сигнал 10 (первое число больше второго), если первое равно 1, а второе 0, то на выход первого мультиплексора подается 01 (второе число больше первого). Если значение с выхода логического элемента XOR 10 равно 0, то на основе знака разности, поступающего со схемы определения знака разности 9 на четвертый вход схемы анализа знака 11, на выход первого мультиплексора 15 подается 01, если знак разности равен 1 (разность первого и второго числа отрицательная), и 10, если знак разности равен 0 (разность первого и второго числа положительны). Если на управляющий вход второго мультиплексора 16 с выхода блока проверки равенства 7 поступает 1, то на выход подается значение 11 (числа равны), иначе подается значение, полученное от первого мультиплексора 15.
На основе примера рассмотрим работу устройства.
Пусть задана система остаточных классов с модулями . Тогда количество входов остатка первого числа 1 и второго числа 2, регистров хранения первого числа 3 и второго числа 4 равно 4, а количество вычислительных ступеней в схемах определения знака первого числа 5, второго числа 6 и разности 9 равно 3. Веса, на которые происходит умножение в блоках 18 умножения на веса  по модулю  схем определения знака равны
,
,
,
.
Если на входы остатков первого 1 и второго 2 чисел поступают числа  и , то через регистры хранения 3 и 4 значения поступают на блок проверки равенства 7, и поскольку числа равны, то на второй вход схемы анализа знака 11 поступает логическая единица, которая поступает на управляющий и первый информационный входы второго мультиплексора 16 и на выход сравнения 12 поступает сигнал 11, который означает, что «первое число равно второму».
Если на входы остатков первого 1 и второго 2 чисел поступают числа  и  то через регистры хранения 3 и 4 значения поступают в схемы определения знака первого 5 и второго 6 чисел.
В схеме 5 определения знака первого числа в первом сумматоре 17.1.1 по модулю  первой вычислительной ступени выполняется операция вычитания из значения 18 со второго входа схемы определения знака 5 значения 16 с первого входа схемы определения знака 5, на выход сумматора 17.1.1 по модулю  поступает значение 2. Во втором сумматоре 17.1.2 по модулю  первой вычислительной ступени выполняется операция вычитания из значения 22 с третьего входа схемы определения знака 5 значения 16 с первого входа схемы определения знака 5, на выход сумматора 17.1.2 по модулю  поступает значение 6. В третьем сумматоре 3.1.3 по модулю  первой вычислительной ступени выполняется операция вычитания из значения 15 четвертого входа схемы определения знака 5 значения 16 с первого входа схемы определения знака 5, на выход сумматора 17.1.3 по модулю  поступает значение 31.
В первом блоке умножения на веса  по модулю  18.1.1 первой ступени происходит умножение по модулю значения 2 с выхода сумматора 17.1.1 по модулю  на сохраненное значение веса , т.е. . Во втором блоке умножения на веса  по модулю  18.1.2 первой ступени происходит умножение по модулю значения 6 с выхода сумматора 17.1.2 по модулю  на сохраненное значение веса , т.е. . Во третьем блоке умножения на веса  по модулю  18.1.3 первой ступени происходит умножение по модулю значения 31 с выхода сумматора 17.1.3 по модулю  на сохраненное значение веса , т.е. .
В первом сумматоре 17.2.1 по модулю  второй вычислительной ступени выполняется операция вычитания из значения 22 второго блока умножения на веса  по модулю  18.1.2 первой ступени значения 18 первого блока умножения на веса  по модулю  18.1.1 первой ступени, на выход первого сумматора 17.2.1 по модулю  поступает значение 4. Во втором сумматоре 17.2.2 по модулю  второй вычислительной ступени выполняется операция вычитания из значения 15 третьего блока умножения на веса  по модулю  18.1.3 первой ступени значения 18 первого блока умножения на веса  по модулю  18.1.1 первой ступени, на выход второго сумматора 17.2.2 по модулю  поступает значение 29.
В первом блоке умножения на веса  по модулю  18.2.1 второй ступени происходит умножение по модулю значения 4 с выхода первого сумматора 17.2.1 по модулю  на сохраненное значение веса , т.е. . Во втором блоке умножения на веса  по модулю  18.2.2 второй ступени происходит умножение по модулю значения 29 с выхода второго сумматора 17.2.2 по модулю  второй ступени на сохраненное значение веса , т.е. .
В первом сумматоре 17.3.1 по модулю  третьей вычислительной ступени выполняется операция вычитания из значения 15 второго блока умножения на веса  по модулю  18.2.2 первой ступени значения 22 первого блока умножения на веса  по модулю  18.2.1 второй ступени, на выход первого сумматора 17.3.1 по модулю  поступает значение 25.
В первом блоке умножения на веса  по модулю  18.4.1 третьей ступени происходит умножение по модулю значения 25 с выхода первого сумматора 17.3.1 по модулю  на сохраненное значение веса , т.е. . В двоичной системе счисления данное число равно 01111 и на выход схемы определения знака 5 первого числа подается старший бит 0.
Таким образом, в СОК с модулями  число  положительное.
Одновременно с этим происходит определение знака  в схеме определения знака второго числа 6.
В первом сумматоре 17.1.1 по модулю  первой вычислительной ступени схемы определения знака второго числа 6 выполняется операция вычитания из значения 0 со второго входа схемы определения знака второго числа 6 значения 0 с первого входа схемы определения знака второго числа 6, на выход сумматора 17.1.1 по модулю  поступает значение 0. Во втором сумматоре 17.1.2 по модулю  первой вычислительной ступени выполняется операция вычитания из значения 0 с третьего входа схемы определения знака второго числа 6 значения 0 с первого входа схемы определения знака второго числа 6, на выход сумматора 17.1.2 по модулю  поступает значение 0. В третьем сумматоре 17.1.3 по модулю  первой вычислительной ступени схемы определения знака второго числа 6 выполняется операция вычитания из значения 16 с четвертого входа схемы определения знака второго числа 6 значения 0 с первого входа схемы определения знака второго числа 6, на выход сумматора 17.1.3 по модулю  поступает значение 16.
В первом блоке умножения на веса  по модулю  18.1.1 первой ступени происходит умножение по модулю значения 0 с выхода сумматора 17.1.1 по модулю  на сохраненное значение веса , т.е. . Во втором блоке умножения на веса  по модулю  18.1.2 первой ступени происходит умножение по модулю значения 0 с выхода сумматора 17.1.2 по модулю  на сохраненное значение веса , т.е. . Во третьем блоке умножения на веса  по модулю  18.1.3 первой ступени происходит умножение по модулю значения 16 с выхода сумматора 17.1.3 по модулю  на сохраненное значение веса , т.е. .
В первом сумматоре 17.2.1 по модулю  второй вычислительной ступени выполняется операция вычитания из значения 0 второго блока умножения на веса  по модулю  18.1.2 первой ступени значения 0 первого блока умножения на веса  по модулю  18.1.1 первой ступени, на выход первого сумматора 17.2.1 по модулю  поступает значение 0. Во втором сумматоре 17.2.2 по модулю  второй вычислительной ступени выполняется операция вычитания из значения 16 третьего блока умножения на веса  по модулю  18.1.3 первой ступени значения 0 первого блока умножения на веса  по модулю  18.1.1 первой ступени, на выход второго сумматора 17.2.2 по модулю  поступает значение 16.
В первом блоке умножения на веса  по модулю  18.2.1 второй ступени происходит умножение по модулю значения 0 с выхода первого сумматора 17.2.1 по модулю  на сохраненное значение веса , т.е. . Во втором блоке умножения на веса  по модулю  18.2.2 второй ступени происходит умножение по модулю значения 16 с выхода второго сумматора 17.2.2 по модулю  второй ступени на сохраненное значение веса , т.е. .
В первом сумматоре 17.3.1 по модулю  третьей вычислительной ступени выполняется операция вычитания из значения 16 второго блока умножения на веса  по модулю  18.2.2 первой ступени значения 0 первого блока умножения на веса  по модулю  18.2.1 второй ступени, на выход первого сумматора 17.3.1 по модулю  поступает значение 16.
В первом блоке умножения на веса  по модулю  18.4.1 третьей ступени происходит умножение по модулю значения 16 с выхода первого сумматора 17.3.1 по модулю  на сохраненное значение веса , т.е. . В двоичной системе счисления данное число равно 10000 и на выход схемы определения знака 6 второго числа подается старший бит 1.
Таким образом, в СОК с модулями  число  отрицательное.
Значения 0 и 1 с выходов схем определения знака первого 5 и второго 6 чисел соответственно поступают на первый и пятый входы схемы анализа знака 11 и входы логического элемента XOR 10 и поскольку они не равны, на выходе логического элемента XOR 10 будет сигнал логической единицы, который поступает на третий вход схемы анализа знака 11, где он подается на управляющий вход первого мультиплексора 15, на выход которого со второго информационного входа поступают значения знаков второго и первого чисел, т.е. 10. Поскольку значение равенства с выхода блока проверки равенства 7 равно 0, то на выход второго мультиплексора 16, который является выходом сравнения 12 устройства будет подан сигнал со второго информационного входа, т.е. 10, что означает «первое число больше второго».
В случае, когда первое и второе число имеют один знак, который поступает на входы логического элемента XOR 10, то выход сравнения 12 зависит от знака, поступающего из схемы определения знака разности 9.
Поскольку все вычисления выполняются над целочисленными значениями малой размерности, увеличивается скорость вычисления и отсутствуют ошибки округления.
Реализация всего устройства возможна с использованием программируемых логических интегральных схем (ПЛИС) и может использоваться как отдельное устройство, так и как сопроцессор для выполнения немодульных операций.