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

Изобретение относится к области вычислительной техники. Техническим результатом является увеличение скорости и точности вычислений определения знака чисел, представленных в системе остаточных классов. Раскрыто устройство определения знака числа, представленного в системе остаточных классов, содержащее входов остатка, где – количество модулей системы остаточных классов, регистров для хранения разрядов исходного числа, блоков умножения, где входы остатка подключены к входам соответствующих регистров для хранения разрядов исходного числа, при этом в него введены вычислительных ступеней, при этом -я вычислительная ступень, где , содержит сумматоров по модулю и блоков умножения на веса по модулю , где и – мультипликативная инверсия модуля по модулю и модули упорядочены по возрастанию и является степенью 2, в первой вычислительной ступени первые информационные входы -х сумматоров по модулю через инверторы подключены к выходу первого регистра для хранения разрядов исходного числа, вторые информационные входы -х сумматоров по модулю подключены к выходам -х регистров для хранения разрядов исходного числа, на входы переносов -х сумматоров по модулю подается сигнал логической единицы, выходы -х сумматоров по модулю подключены ко входам соответствующих блоков умножения на веса по модулю , , в -x вычислительных ступенях, , первые информационные входы -х сумматоров по модулю через инверторы подключены к выходу первого блока умножения на веса по модулю -й вычислительной ступени, вторые информационные входы -х сумматоров по модулю подключены к выходам -х блоков умножения на веса по модулю -й вычислительной ступени, на входы переносов -х сумматоров по модулю подается сигнал логической единицы, выходы -х сумматоров по модулю подключены к входам -х блоков умножения на веса по модулю , старший бит выхода блока умножения на веса -й вычислительной ступени является выходом знака устройства. 1 ил.

 

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

Известно устройство для определения знаков чисел в системе остаточных классов (патент РФ 2557446, опубл. 20.07.2015), содержащее группу входных регистров для хранения числа, представленного в коде симметричной системы остаточных классов, энергонезависимые регистры для хранения интервально-позиционной характеристики константы - наибольшего положительного числа в симметричной системе остаточных классов, блок вычисления интервально-позиционной характеристики, блок проверки правильности интервально-позиционной характеристики, блок сравнения интервально-позиционных характеристик, двухвходовой двоичный дешифратор.

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

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

Недостатком данного устройства является низкая точность, связанная с представлением чисел в формате с плавающей точкой, а именно с ошибками округления.

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

Данный технический результат достигается тем, что в устройство определения знака числа, представленного в системе остаточных классов, содержащее входов остатка, где - количество модулей системы остаточных классов, регистров для хранения разрядов исходного числа, блоков умножения, где входы остатка подключены к входам соответствующих регистров для хранения разрядов исходного числа, введены вычислительная ступень, при этом я вычислительная ступень, где , содержит сумматоров по модулю и блоков умножения на веса по модулю , где и - мультипликативная инверсия модуля по модулю и модули упорядочены по возрастанию и является степенью 2, в первой вычислительной ступени первые информационные входы х сумматоров по модулю через инверторы подключены к выходу первого регистра для хранения разрядов исходного числа, вторые информационные входы х сумматоров по модулю подключены к выходам )-х регистров для хранения разрядов исходного числа, на входы переносов х сумматоров по модулю подается сигнал логической единицы, выходы х сумматоров по модулю подключены ко входам соответствующих блоков умножения на веса по модулю , , в x вычислительных ступенях, , первые информационные входы х сумматоров по модулю через инверторы подключены к выходу первого блока умножения на веса по модулю -ой вычислительной ступени, вторые информационные входы х сумматоров по модулю подключены к выходам -ых блоков умножения на веса по модулю -ой вычислительной ступени, на входы переносов х сумматоров по модулю подается сигнал логической единицы, выходы х сумматоров по модулю подключены к входам -ых блоков умножения на веса по модулю , старший бит выхода блока умножения на веса -й вычислительной ступени является выходом знака устройства.

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

Функция определения знака числа, представленного в СОК, определяется следующим образом:

Таким образом можно представить в виде:

Используя свойство и формулу (1) определение знака сводится двухэтапному алгоритму: первый этап - деление на , второй этап - деление на , формально математически определяется следующей формулой

Запишем процесс определения в виде алгоритма:

Алгоритм 1. Определение знака числа

Вход: - модули СОК

- представление числа в СОК

- синоптические веса

Выход: - положительное число, - отрицательное число

1. Для от до выполнять:

1.1. Для от до выполнять: \\ деление на

1.1.1.

2. Возвратить

На первом этапе вычисляется с помощью деления на модули СОК соответственно. На втором этапе вычисляется .

Устройство поясняется фигурой 1, которая содержит входов остатка 1.1-1.n, которые соединены с регистрами для хранения разрядов исходного числа 2.1-2.n. Устройство содержит n-1 вычислительных ступеней, при этом -я вычислительная ступень, где , содержит сумматоров по модулю 3.i.1 - 3.i.n-i и блоков умножения на веса по модулю 4.i.1 - 4.i.n-i, где и - мультипликативная инверсия модуля по модулю . В первой вычислительной ступени первые информационные входы х сумматоров по модулю 3.1.1 - 3.1.n-1 через инверторы подключены к выходу первого регистра для хранения разрядов исходного числа 2.1, вторые информационные входы х сумматоров по модулю 3.1.1 - 3.1.n-1 подключены к выходам соответствующих )-х регистров для хранения разрядов исходного числа 2.2-2.n, на входы переносов х сумматоров по модулю 3.1.1 - 3.1.n-1 подается сигнал логической единицы, выходы х сумматоров по модулю 3.1.1 - 3.1.n-1 подключены ко входам соответствующих блоков умножения на веса по модулю 4.1.1 - 4.1.n-1, . Во второй вычислительной ступени первые информационные входы х сумматоров по модулю 3.2.1 - 3.2.n-2 через инверторы подключены к выходу первого блока умножения на веса по модулю первой ступени, вторые информационные входы х сумматоров по модулю 3.2.1 - 3.2.n-2 подключены к выходам соответствующих -ых блоков умножения на веса по модулю первой ступени, на входы переносов х сумматоров по модулю 3.2.1 - 3.2.n-2 второй ступени подается сигнал логической единицы, выходы х сумматоров по модулю 3.2.1 - 3.2.n-2 второй ступени подключены ко входам соответствующих -ых блоков умножения на веса по модулю 4.2.1 - 4.2.n-2, . И так далее, на вычислительной ступени первый информационный вход сумматора по модулю 3.n-1.1 через инвертор подключен к выходу первого блока умножения на веса по модулю 4.n-2.1 -й ступени, второй информационный вход сумматора по модулю 3.n-1.1 подключен к выходу второго блока умножения на веса по модулю 4.n-2.2 -й ступени , на вход переноса поступает сигнал логической единицы, а выход соединен со входом первого блока умножения на веса по модулю 4.n-1.1 -й ступени, старший бит выхода которого является выходом знака 5.

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

На основе примера рассмотрим работу устройства.

Пусть задана система остаточных классов с модулями . Тогда количество входов остатка 1 и регистров для хранения разрядов исходного числа 2 равно 4, а количество вычислительных ступеней равно 3. Для них веса, на которые происходит умножение в блоках 4 умножения на веса по модулю равны

, ,

,

.

Пусть на входы 1.1-1.4 поступает число , тогда в регистрах для хранения разрядов исходного числа 2.1-2.4 будут храниться соответственно числа 16, 18, 22, 15.

В первом сумматоре 3.1.1 по модулю первой вычислительной ступени выполняется операция вычитания из значения 18 второго регистра для хранения разрядов исходного числа 2.2 значения 16 первого регистра для хранения разрядов исходного числа 2.1, на выход сумматора 3.1.1 по модулю поступает значение 2. Во втором сумматоре 3.1.2 по модулю первой вычислительной ступени выполняется операция вычитания из значения 22 третьего регистра для хранения разрядов исходного числа 2.3 значения 16 первого регистра для хранения разрядов исходного числа 2.1, на выход сумматора 3.1.2 по модулю поступает значение 6. В третьем сумматоре 3.1.3 по модулю первой вычислительной ступени выполняется операция вычитания из значения 15 четвертого регистра для хранения разрядов исходного числа 2.4 значения 16 первого регистра для хранения разрядов исходного числа 2.1, на выход сумматора 3.1.3 по модулю поступает значение 31.

В первом блоке умножения на веса по модулю 4.1.1 первой ступени происходит умножение по модулю значения 2 с выхода сумматора 3.1.1 по модулю на сохраненное значение веса , т.е. . Во втором блоке умножения на веса по модулю 4.1.2 первой ступени происходит умножение по модулю значения 6 с выхода сумматора 3.1.2 по модулю на сохраненное значение веса , т.е. . Во третьем блоке умножения на веса по модулю 4.1.3 первой ступени происходит умножение по модулю значения 31 с выхода сумматора 3.1.3 по модулю на сохраненное значение веса , т.е. .

В первом сумматоре 3.2.1 по модулю второй вычислительной ступени выполняется операция вычитания из значения 22 второго блока умножения на веса по модулю 4.1.2 первой ступени значения 18 первого блока умножения на веса по модулю первой ступени, на выход первого сумматора 3.2.1 по модулю поступает значение 4. Во втором сумматоре 3.2.2 по модулю второй вычислительной ступени выполняется операция вычитания из значения 15 третьего блока умножения на веса по модулю 4.1.3 первой ступени значения 18 первого блока умножения на веса по модулю первой ступени, на выход второго сумматора 3.2.2 по модулю поступает значение 29.

В первом блоке умножения на веса по модулю 4.2.1 второй ступени происходит умножение по модулю значения 4 с выхода первого сумматора 3.2.1 по модулю на сохраненное значение веса , т.е. . Во втором блоке умножения на веса по модулю 4.2.2 второй ступени происходит умножение по модулю значения 29 с выхода второго сумматора 3.2.2 по модулю второй ступени на сохраненное значение веса , т.е. .

В первом сумматоре 3.3.1 по модулю третьей вычислительной ступени выполняется операция вычитания из значения 15 второго блока умножения на веса по модулю 4.2.2 первой ступени значения 22 первого блока умножения на веса по модулю второй ступени, на выход первого сумматора 3.3.1 по модулю поступает значение 25.

В первом блоке умножения на веса по модулю 4.4.1 третьей ступени происходит умножение по модулю значения 25 с выхода первого сумматора 3.3.1 по модулю на сохраненное значение веса , т.е. . В двоичной системе счисления данное число равно 01111 и на выход знака 5 подается старший бит 0.

Таким образом, в СОК с модулями число положительное.

Рассмотрим другой пример: тогда в регистрах для хранения разрядов исходного числа 2.1-2.4 будут храниться соответственно числа 0, 0, 0, 16.

В первом сумматоре 3.1.1 по модулю первой вычислительной ступени выполняется операция вычитания из значения 0 второго регистра для хранения разрядов исходного числа 2.2 значения 0 первого регистра для хранения разрядов исходного числа 2.1, на выход сумматора 3.1.1 по модулю поступает значение 0. Во втором сумматоре 3.1.2 по модулю первой вычислительной ступени выполняется операция вычитания из значения 0 третьего регистра для хранения разрядов исходного числа 2.3 значения 0 первого регистра для хранения разрядов исходного числа 2.1, на выход сумматора 3.1.2 по модулю поступает значение 0. В третьем сумматоре 3.1.3 по модулю первой вычислительной ступени выполняется операция вычитания из значения 16 четвертого регистра для хранения разрядов исходного числа 2.4 значения 0 первого регистра для хранения разрядов исходного числа 2.1, на выход сумматора 3.1.3 по модулю поступает значение 16.

В первом блоке умножения на веса по модулю 4.1.1 первой ступени происходит умножение по модулю значения 0 с выхода сумматора 3.1.1 по модулю на сохраненное значение веса , т.е. . Во втором блоке умножения на веса по модулю 4.1.2 первой ступени происходит умножение по модулю значения 0 с выхода сумматора 3.1.2 по модулю на сохраненное значение веса , т.е. . Во третьем блоке умножения на веса по модулю 4.1.3 первой ступени происходит умножение по модулю значения 16 с выхода сумматора 3.1.3 по модулю на сохраненное значение веса , т.е. .

В первом сумматоре 3.2.1 по модулю второй вычислительной ступени выполняется операция вычитания из значения 0 второго блока умножения на веса по модулю 4.1.2 первой ступени значения 0 первого блока умножения на веса по модулю первой ступени, на выход первого сумматора 3.2.1 по модулю поступает значение 0. Во втором сумматоре 3.2.2 по модулю второй вычислительной ступени выполняется операция вычитания из значения 16 третьего блока умножения на веса по модулю 4.1.3 первой ступени значения 0 первого блока умножения на веса по модулю первой ступени, на выход второго сумматора 3.2.2 по модулю поступает значение 16.

В первом блоке умножения на веса по модулю 4.2.1 второй ступени происходит умножение по модулю значения 0 с выхода первого сумматора 3.2.1 по модулю на сохраненное значение веса , т.е. . Во втором блоке умножения на веса по модулю 4.2.2 второй ступени происходит умножение по модулю значения 16 с выхода второго сумматора 3.2.2 по модулю второй ступени на сохраненное значение веса , т.е. .

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

В первом блоке умножения на веса по модулю 4.4.1 третьей ступени происходит умножение по модулю значения 16 с выхода первого сумматора 3.3.1 по модулю на сохраненное значение веса , т.е. . В двоичной системе счисления данное число равно 10000 и на выход знака 5 подается старший бит 1.

Таким образом, в СОК с модулями число отрицательное.

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

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

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