Устройство для вычисления ранга модулярного числа Российский патент 2022 года по МПК G06F7/72 

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

Известно устройство для определения ранга числа (авторское свидетельство №1125619, опубл. 23.11.1984), которое содержит блоки умножения на константу, сумматор по наибольшему модулю, две группы элементов ИЛИ, причем входы остатков устройства соединены с входами соответствующих блоков умножения на константу, выходы нечетных и четных блоков умножения на константу соединены соответственно с входами элементов ИЛИ первой и второй групп, выходы которых соединены соответственно с первым и вторым входами сумматора по наибольшему модулю, выход которого является выходом устройства, тактовый вход которого соединен с тактовыми входами блоков умножения на константу.

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

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

Недостатком данного изобретения является использование в вычислениях выражения , вычисление которого является ресурсоемкой задачей в реальных модулярных системах. Также недостатком является некорректность метода, лежащего в основе изобретения, для наборов модулей, отличных от выбранного в качестве примера. Возьмем в качестве СОК набор модулей {3,5,7}, тогда для десятичного числа 17 ранг числа, вычисленный по данному устройству равен 6, в то время как истинное значение ранга равно 2.

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

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

Наиболее близким к заявленному изобретению является устройство определения знака числа, представленного в системе остаточных классов (патент РФ №2747371, опубл. 04.05.2021), содержащее n входов остатка, где n - количество модулей системы остаточных классов, n регистров для хранения разрядов исходного числа, n блоков умножения, где входы остатка подключены к входам соответствующих регистров для хранения разрядов исходного числа, при этом в него введены n-1 вычислительная ступень, при этом i-я вычислительная ступень, где i=1,…,n-1, содержит n-i сумматоров по модулю и n-i блоков умножения на веса по модулю , где j=i+1,…, n и - мультипликативная инверсия модуля по модулю и модули упорядочены по возрастанию и является степенью 2, в первой вычислительной ступени первые информационные входы i-х сумматоров по модулю через инверторы подключены к выходу первого регистра для хранения разрядов исходного числа, вторые информационные входы i-х сумматоров по модулю подключены к выходам (i+1)-х регистров для хранения разрядов исходного числа, на входы переносов i-х сумматоров по модулю подается сигнал логической единицы, выходы i-х сумматоров по модулю подключены ко входам соответствующих блоков умножения на веса по модулю , i=1,…,n-1, в i-x вычислительных ступенях, i=2,…,n-1, первые информационные входы j-х сумматоров по модулю через инверторы подключены к выходу первого блока умножения на веса по модулю (i-1)-ой вычислительной ступени, вторые информационные входы j-х сумматоров по модулю подключены к выходам (j+1)-ых блоков умножения на веса по модулю (i-1)-ой вычислительной ступени, на входы переносов j-х сумматоров по модулю подается сигнал логической единицы, выходы j-х сумматоров по модулю подключены к входам j-ых блоков умножения на веса по модулю , j=1,…,n-i, старший бит выхода блока умножения на веса (n-1)-й вычислительной ступени является выходом знака устройства.

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

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

Технический результат достигается тем, что в устройство определения знака числа, представленного в системе остаточных классов (СОК) содержащее n входов остатка, где n - количество модулей системы остаточных классов, n регистров хранения разрядов исходного числа, n-1 вычислительную ступень прямого хода, при этом i-я вычислительная ступень прямого хода, где i=1,…,n-1, содержит n-i сумматоров по модулю и n-i блоков умножения на по модулю , где j=i+1,…, n и - мультипликативная инверсия модуля по модулю , входы остатка подключены к входам соответствующих регистров хранения разрядов исходного числа, в первой вычислительной ступени прямого хода первые информационные входы i-х сумматоров по модулю через инверторы подключены к выходу первого регистра хранения разрядов исходного числа, вторые информационные входы i-х сумматоров по модулю подключены к выходам (i+1)-х регистров хранения разрядов исходного числа, на входы переносов i-х сумматоров по модулю подается сигнал логической единицы, выходы i-х сумматоров по модулю подключены ко входам соответствующих блоков умножения на по модулю , i=1,…,n-1, в i-x вычислительных ступенях прямого хода, i=2,…,n-1, первые информационные входы j-х сумматоров по модулю через инверторы подключены к выходу первого блока умножения на по модулю (i-1)-ой вычислительной ступени прямого хода, вторые информационные входы j-х сумматоров по модулю подключены к выходам (j+1)-ых блоков умножения на по модулю (i-1)-ой вычислительной ступени прямого хода, на входы переносов j-х сумматоров по модулю подается сигнал логической единицы, выходы j-х сумматоров по модулю подключены к входам j-ых блоков умножения на по модулю , дополнительно введены n выходов прямого хода, n блоков перевода в СОК, n блоков хранения предвычисленных рангов, n выходов исходного числа, выход ранга, а также n-1 вычислительная ступень обратного хода, каждая из которых содержит n умножителей по модулю , n сумматоров по модулю , где j=1,…, n, вычислитель ранга суммы, вычислитель ранга произведения, при этом выход первого регистра хранения разрядов исходного числа является первым выходом прямого хода, выходы первых блоков умножения на по модулю i-x вычислительных ступеней прямого хода, i=1,…,n-1, являются (i+1)-ми выходами прямого хода, i-й выход прямого хода подключен к входу (n+1-i)-го блок перевода в СОК и входу (n+1-i)-го блока хранения предвычисленных рангов, i=1,…,n, i-й выход первого блока перевода в СОК подключен к входу i-го умножителей по модулю первой вычислительной ступени обратного хода и (i+1)-му входу вычислителя ранга произведения первой ступени обратного хода, первый вход которого соединен с выходом первого блока хранения предвычисленных рангов, в i-й вычислительной ступени обратного хода, i=1,…,n-1, j-й выход (i+1)-го блока перевода в СОК, j=1,…,n, соединен с первым входом j-го сумматора по модулю и 2j-м входом вычислителя ранга суммы i-й вычислительной ступени обратного хода, вторые входы j-х сумматора по модулю и (2j+1)-е входы вычислителя ранга суммы i-й вычислительной ступени обратного хода соединены с выходами j-х умножителей по модулю , первый вход вычислителя ранга суммы i-й вычислительной ступени обратного хода соединен с выходом (i+1)-го блока хранения предвычисленных рангов, (2n+2)-й вход вычислителя ранга суммы i-й вычислительной ступени обратного хода соединен с выходом вычислителя ранга произведения i-й вычислительной ступени обратного хода, выходы j-х сумматоров по модулю , j=1,…,n, i-й вычислительной ступени обратного хода, i=1,…,n-2, соединены со входами j-х умножителей по модулю (i+1)-й вычислительной ступени обратного хода и (j+1)-ми входами вычислителя ранга произведения (i+1)-й вычислительной ступени обратного хода, первый вход вычислителя ранга произведения (i+1)-й вычислительной ступени обратного хода соединен с выходом вычислителя ранга суммы i-й вычислительной ступени обратного хода, выходы j-х сумматоров по модулю , j=1,…,n (n-1)-й вычислительной ступени обратного хода являются j-ми выходами исходного числа, выход вычислителя ранга суммы (n-1)-й вычислительной ступени обратного хода является выходом ранга устройства.

Сущность изобретения основана на следующем математическом аппарате. В системе остаточных классов (СОК) любое число X<P однозначно представляется набором остатков от деления числа X на взаимно простые модули СОК , где , - рабочий диапазон СОК, i=1,…,n.

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

)

где - ортогональные базисы СОК, , - мультипликативная инверсия по модулю , а оператором обозначен остаток от деления на , т.е. . При этом ранг числа r показывает, во сколько раз сумма произведений остатков на ортогональные базисы превосходит динамический диапазон СОК.

Для вычисления ранга воспользуемся следующими свойствами:

)

Если и , то

)

Рассмотрим метод, лежащий в основе устройства, на примере.

Пусть задана СОК с модулями , , . Тогда диапазон СОК равен Константы и равны

Значения констант :

=3.

Для чисел от 0 до вычисляют ранги чисел:

Далее вычисление разбивается на два последовательных этапа: прямой и обратные ходы. Запишем прямой ход в виде таблицы 1.

Из таблицы 1 следует, что . Запишем обратный ход в виде таблицы 2. При вычислении ранга используются формулы (2) и (3).

Из крайнего правого столбца видно, что ранг числа 17 равен 2.

Проверим, воспользовавшись формулой для :

Устройство поясняется фигурами 1 и 2, на которых для удобства отображения, устройство для вычисления ранга модулярного числа разбито на две части, прямой ход (фиг.1) и обратный ход (фиг.2).

На фигуре 1 изображена структурная схема блока прямого хода, содержащая n входов остатка 1.1-1.n, где n - количество модулей системы остаточных классов, которые соединены с которые соединены с n регистрами хранения разрядов исходного числа 2.1-2.n. Выход первого регистра хранения разрядов исходного числа 2.1 подключен к первому выходу прямого хода 5.1.

Блок прямого хода содержит n-1 вычислительных ступеней, при этом i-я вычислительная ступень, где i=1,…,n-1, содержит n-i сумматоров по модулю 3.i.1 - 3.i.(n-i) и n-i блоков умножения на по модулю 4.i.1 - 4.i.(n-i), где j=i+1,…, n.

В первой вычислительной ступени первые информационные входы i-х сумматоров по модулю 3.1.1 - 3.1.n-1 через инверторы подключены к выходу первого регистра хранения разрядов исходного числа 2.1, вторые информационные входы i-х сумматоров по модулю 3.1.1 - 3.1.n-1 подключены к выходам соответствующих (i+1)-х регистров хранения разрядов исходного числа 2.2-2.n, на входы переносов i-х сумматоров по модулю 3.1.1 - 3.1.n-1 подается сигнал логической единицы, выходы i-х сумматоров по модулю 3.1.1 - 3.1.n-1 подключены ко входам соответствующих блоков умножения на по модулю 4.1.1 - 4.1.n-1, i=1,…,n-1. Выход первого блока умножения на по модулю 4.1.1 первой вычислительной ступени подключен ко второму выходу прямого хода 5.2.

Во второй вычислительной ступени первые информационные входы i-х сумматоров по модулю 3.2.1 - 3.2.n-2 через инверторы подключены к выходу первого блока умножения на по модулю первой ступени 4.1.1, вторые информационные входы i-х сумматоров по модулю 3.2.1 - 3.2.n-2 подключены к выходам соответствующих (i+1)-ых блоков умножения на по модулю первой ступени 4.1.2-4.1.n, на входы переносов i-х сумматоров по модулю 3.2.1 - 3.2.n-2 второй ступени подается сигнал логической единицы, выходы i-х сумматоров по модулю 3.2.1 - 3.2.n-2 второй ступени подключены ко входам соответствующих i-ых блоков умножения на по модулю 4.2.1 - 4.2.n-2, i=1,…,n-2. Выход первого блока умножения на по модулю 4.2.1 второй вычислительной ступени подключен ко третьему выходу прямого хода 5.3.

И так далее, на вычислительной ступени первый информационный вход сумматора по модулю 3.n-1.1 через инвертор подключен к выходу первого блока умножения на по модулю 4.n-2.1 (n-2)-й ступени, второй информационный вход сумматора по модулю 3.n-1.1 подключен к выходу второго блока умножения на по модулю 4.n-2.2 (n-2)-й ступени, на вход переноса поступает сигнал логической единицы, а выход соединен со входом первого блока умножения на по модулю 4.n-1.1 (n-1)-й ступени, выход первого блока умножения на по модулю 4.n-1.1 (n-1)-й вычислительной ступени подключен к n-му выходу прямого хода 5.n.

На фигуре 2 изображена структурная схема блока обратного хода, которая содержит n выходов прямого хода 5.1-5.n, при этом i-й выход прямого хода 5.i подключен к входу (n+1-i)-го блок перевода в СОК 6.(n+1-i), и входу (n+1-i)-го блока хранения предвычисленных рангов 7.(n+1-i), i=1,…,n Поскольку значения на входах блоков перевода в СОК 6.1-6.n ограничены , то их реализация возможна как табличных способом, там и прямым вычислением. Блоки хранения предвычисленных рангов 7.1-7.n хранят ранги для чисел до

Блок обратного хода содержит n-1 вычислительную ступень, каждая из которых содержит n умножителей по модулю 8, n сумматоров по модулю 10, вычислитель ранга суммы 11, вычислитель ранга произведения 9, и блок хранения предвычисленных рангов 7.

В первой вычислительной ступени блока обратного хода происходит умножение числа, полученного с выхода прямого хода 5.n, представленного в СОК блоком перевода в СОК 6.1, на значение второго модуля СОК . Вход первого умножителя по модулю 8.1.1 соединен с первым выходом первого блока перевода в СОК 6.1, который также соединен со вторым входом вычислителя ранга произведения 9.1, который осуществляет вычисления по формуле (3). Вход второго умножителя по модулю 8.1.2 соединен с вторым выходом первого блока перевода в СОК 6.1, который также соединен со третьим входом вычислителя ранга произведения 9.1. И так далее, вход n-го умножителя по модулю 8.1.n соединен с n-м выходом первого блока перевода в СОК 6.1, который также соединен со (n+1)-м входом вычислителя ранга произведения 9.1. Первый вход вычислителя ранга произведения 9.1 соединен с выходом первого блока хранения предвычисленных рангов 7.1.

Данные с выходов умножителей по модулю 8.1.i поступают на вторые входы соответствующих сумматоров по модулю 10.1.i, на первые входы которых поступают значения с соответствующих выходов второго блока перевода в СОК 6.2. Первый вход вычислителя ранга суммы 11.1 подключен к выходу второго блока хранения предвычисленных рангов 7.2, четные входы вычислителя ранга суммы 11.1 со 2 по 2n подключены к соответствующим выходам второго блока перевода в СОК 6.2, нечетные входы вычислителя ранга суммы 11.1 с 3 по (2n+1) подключены к выходам соответствующих выходов умножителей по модулю 8.1.i, (2n+2)-й вход вычислителя ранга суммы 11.1 подключен к выходу вычислителя ранга произведения 9.1.

Аналогично устроены остальные ступени.

В (n-1)-й вычислительной ступени входы умножителей по модулю 8.n-1.i подключены к выходам соответствующих сумматоров по модулю 10.n-2.i предыдущей ступени. Первый вход вычислителя ранга произведения 9.n-1 подключен к выходу вычислителя ранга суммы 11.n-2 предыдущей ступени, входы со 2 по (n+1)-й подключены к выходам соответствующих сумматоров по модулю 10.n-2.i предыдущей ступени.

Данные с выходов умножителей по модулю 8.n-1.i поступают на вторые входы соответствующих сумматоров по модулю 10.n-1.i, на первые входы которых поступают значения с соответствующих выходов n-го блока перевода в СОК 6.n. Первый вход вычислителя ранга суммы 11.n-1 подключен к выходу n-го блока хранения предвычисленных рангов 7.n, четные входы вычислителя ранга суммы 11.n-1 со 2 по 2n подключены к соответствующим выходам n-го блока перевода в СОК 6.n, нечетные входы вычислителя ранга суммы 11.n-1 с 3 по (2n+1) подключены к выходам соответствующих выходов умножителей по модулю 8.n-1.i, (2n+2)-й вход вычислителя ранга суммы 11.n-1 подключен к выходу вычислителя ранга произведения 9.n-1.

Выходы сумматоров по модулю 10.n-1.i (n-1)-й вычислительной ступени являются выходами исходного числа 12.i, а выход вычислителя ранга суммы 11.n-1 является выходом ранга 13 устройства.

Рассмотрим работу устройства на предыдущем примере. Поскольку СОК содержит 3 модуля, то n=3 и устройство содержит 2 вычислительных ступени прямого хода и 2 вычислительных ступени обратного хода. На входы остатка 1.1-1.3 подаются значения 2, 2, 3 соответственно, которые затем поступают на соответствующие регистры хранения разрядов исходного числа 2.1-2.3.

Значение с первого регистра хранения разрядов исходного числа 2.1 поступает на первый выход прямого хода 5.1 и через инверторы на первые информационные входы сумматоров по модулю 3.1.1 и по модулю 3.1.2 первой вычислительной ступени. На вторые информационные входы сумматоров по модулю 3.1.1 и по модулю 3.1.2 поступают значения с регистров хранения разрядов исходного числа 2.2 и 2.3 соответственно.

В сумматоре по модулю 3.1.1 происходит вычисление . В сумматоре по модулю 3.1.2 происходит вычисление .

Значения с выходов сумматоров по модулю 3.1.1 и по модулю 3.1.2 поступают на входы блоков умножения на по модулю 4.1.1 и на по модулю 4.1.2 первой вычислительной ступени, в которых происходит соответственно умножение и

Значение с выхода блоков умножения на по модулю 4.1.1 поступает на второй выход прямого хода 5.2 и через инвертор на первый информационный вход сумматора по модулю 3.2.1 второй вычислительной ступени, в котором происходит вычисление ( Значение с выхода сумматора по модулю 3.2.1 поступает на вход первого блока умножения на по модулю 4.2.1, в котором происходит вычисление (. Значение с выхода первого блока умножения на по модулю 4.2.1 поступает третий выход прямого хода 5.3.

Таким образом, на выходах прямого хода 5.1-5.3 будут сформированы значения 2, 0, 1.

Значение 1 с выхода прямого хода 5.3 поступает на входы первого блок перевода в СОК 6.1, и входу первого блока хранения предвычисленных рангов 7.1. На первый выход первого блок перевода в СОК 6.1 поступает значение по модулю , т.е. , которое подается на вход первого умножителя по модулю 8.1.1, в котором происходит умножение на , т.е. . На второй выход первого блок перевода в СОК 6.1 поступает значение по модулю , т.е. , которое подается на вход второго умножителя по модулю 8.1.2, в котором происходит умножение на , т.е. . На третий выход первого блок перевода в СОК 6.1 поступает значение по модулю , т.е. , которое подается на вход третьего умножителя по модулю 8.1.3, в котором происходит умножение на , т.е. . Предвычисленное значение 1, хранящееся в памяти, с выхода первого блока хранения предвычисленных рангов 7.1 поступает на первый вход вычислителя ранга произведения 9.1 первой ступени, на входы со 2 по 4 которого поступают значения 1, 1, 1 с первого, второго и третьего выходов первого блок перевода в СОК 6.1. В вычислителе ранга произведения 9.1 происходит вычисление по формуле (3)

Значение 0 с выхода прямого хода 5.2 поступает на входы второго блок перевода в СОК 6.2, и входу второго блока хранения предвычисленных рангов 7.2. На выходах второго блок перевода в СОК 6.2 и второго блока хранения предвычисленных рангов 7.2 будут 0. Выход второго блока хранения предвычисленных рангов 7.2 соединен с первым входом вычислителя ранга суммы 11.1 первой ступени. Первый выход второго блок перевода в СОК 6.2 подключен ко второму входу вычислителя ранга суммы 11.1 и первому входу сумматора по модулю 10.1.1 первой ступени обратного хода, на второй вход которого поступает значение с выхода первого умножителя по модулю 8.1.1, который также подключен к третьему входу вычислителя ранга суммы 11.1. В сумматоре по модулю 10.1.1 происходит вычисление (. Второй выход второго блок перевода в СОК 6.2 подключен ко четвертому входу вычислителя ранга суммы 11.1 и первому входу сумматора по модулю 10.1.2 первой ступени обратного хода, на второй вход которого поступает значение с выхода второго умножителя по модулю 8.1.2, который также подключен к пятому входу вычислителя ранга суммы 11.1. В сумматоре по модулю 10.1.2 происходит вычисление (. Третий выход второго блок перевода в СОК 6.2 подключен ко шестому входу вычислителя ранга суммы 11.1 и первому входу сумматора по модулю 10.1.3 первой ступени обратного хода, на второй вход которого поступает значение с выхода третьего умножителя по модулю 8.1.3, который также подключен к седьмому входу вычислителя ранга суммы 11.1. В сумматоре по модулю 10.1.3 происходит вычисление (. На восьмой вход вычислителя ранга суммы 11.1 поступает значение с выхода вычислителя ранга произведения 9.1. В вычислителе ранга суммы 11.1 происходит вычисление по формуле (2):

Во второй вычислительной ступени обратного хода на входы умножителей по модулю 8.2.1, по модулю 8.2.2, по модулю 8.2.3 второй ступени обратного хода поступают значения 2, 0, 5 с выходов соответствующих сумматоров по модулю 10.1.1, по модулю 10.1.2, по модулю 10.1.3 первой ступени обратного хода. В умножителях 8.2.1-8.2.3 происходит умножение на по соответствующему модулю. На выход первого умножителя по модулю 8.2.1 второй ступени поступает значение (. На выход второго умножителя по модулю 8.2.3 второй ступени поступает значение (. На выход третьего умножителя по модулю 8.2.3 второй ступени поступает значение (.

На первый вход вычислителя ранга произведения 9.2 второй ступени поступает значение 2 с выхода вычислителя ранга суммы 11.1 первой ступени. На входы со второго по четвертый вычислителя ранга произведения 9.2 второй ступени поступают значения 2, 0, 5 с выходов соответствующих сумматоров по модулю 10.1.1, по модулю 10.1.2, по модулю 10.1.3 первой ступени обратного хода. В вычислителе ранга произведения 9.2 второй ступени происходит вычисление по формуле (3)

Значение 2 с выхода прямого хода 5.1 поступает на входы третьего блок перевода в СОК 6.3, и входу третьего блока хранения предвычисленных рангов 7.3. На выходах третьего блок перевода в СОК 6.3 и третьего блока хранения предвычисленных рангов 7.3 будут 2. Выход третьего блока хранения предвычисленных рангов 7.3 соединен с первым входом вычислителя ранга суммы 11.2 второй ступени. Первый выход третьего блок перевода в СОК 6.3 подключен ко второму входу вычислителя ранга суммы 11.2 и первому входу сумматора по модулю 10.2.1 второй ступени обратного хода, на второй вход которого поступает значение с выхода первого умножителя по модулю 8.2.1, который также подключен к третьему входу вычислителя ранга суммы 11.2. В сумматоре по модулю 10.2.1 происходит вычисление (. Второй выход третьего блок перевода в СОК 6.3 подключен ко четвертому входу вычислителя ранга суммы 11.2 и первому входу сумматора по модулю 10.2.2 второй ступени обратного хода, на второй вход которого поступает значение с выхода второго умножителя по модулю 8.2.2, который также подключен к пятому входу вычислителя ранга суммы 11.2. В сумматоре по модулю 10.2.2 происходит вычисление (. Третий выход третьего блок перевода в СОК 6.3 подключен ко шестому входу вычислителя ранга суммы 11.2 и первому входу сумматора по модулю 10.2.3 второй ступени обратного хода, на второй вход которого поступает значение с выхода третьего умножителя по модулю 8.2.3, который также подключен к седьмому входу вычислителя ранга суммы 11.2. В сумматоре по модулю 10.2.3 происходит вычисление (. На восьмой вход вычислителя ранга суммы 11.2 поступает значение с выхода вычислителя ранга произведения 9.2. В вычислителе ранга суммы 11.2 происходит вычисление по формуле (2):

С выходов сумматора по модулю 10.2.1-10.2.3 на выходы исходного числа 12.1-12.3 поступают соответственно 2, 2, 3, что соответствует исходному числу.

С выхода вычислителе ранга суммы 11.2 на выход ранга 13 поступает значение 2, соответствующее ранее вычисленному рангу для числа 17.

Таким образом, устройство позволяет как проверить правильность вычисления за счет проверки выходов исходного числа 12.1-12.n на соответствие входам остатка 1.1-1.n, так и вычислить ранг числа, поступающий на выход ранга 13.

Устройство для вычисления ранга модулярного числа

Таблица 1. Прямой ход нахождения ранга числа

- - - -

Устройство для вычисления ранга модулярного числа

Таблица 2. Обратный нахождения ранга числа

Изобретение относится к вычислительной технике. Технический результат заключается в сокращении размерности операнд при вычислении ранга числа. Технический результат достигается тем, что в устройство определения знака числа, представленного в системе остаточных классов (СОК), содержащее n входов остатка, где n – количество модулей системы остаточных классов, n регистров хранения разрядов исходного числа, n-1 вычислительную ступень прямого хода, при этом i-я вычислительная ступень прямого хода, где i=1,…,n-1, содержит n-i сумматоров по модулю и n-i блоков умножения на по модулю , где j=i+1,…, n и – мультипликативная инверсия модуля по модулю , дополнительно введены n выходов прямого хода, n блоков перевода в СОК, n блоков хранения предвычисленных рангов, n выходов исходного числа, выход ранга, а также n-1 вычислительная ступень обратного хода, каждая из которых содержит n умножителей по модулю , n сумматоров по модулю , где j=1,…, n, вычислитель ранга суммы, вычислитель ранга произведения. 2 ил., 2 табл.

Устройство для вычисления ранга модулярного числа, содержащее n входов остатка, где n – количество модулей системы остаточных классов (СОК), n регистров хранения разрядов исходного числа, n-1 вычислительную ступень прямого хода, при этом i-я вычислительная ступень прямого хода, где i=1,…,n-1, содержит n-i сумматоров по модулю и n-i блоков умножения на по модулю , где j=i+1,…, n и – мультипликативная инверсия модуля по модулю , входы остатка подключены к входам соответствующих регистров хранения разрядов исходного числа, в первой вычислительной ступени прямого хода первые информационные входы i-х сумматоров по модулю через инверторы подключены к выходу первого регистра хранения разрядов исходного числа, вторые информационные входы i-х сумматоров по модулю подключены к выходам (i+1)-х регистров хранения разрядов исходного числа, на входы переносов i-х сумматоров по модулю подается сигнал логической единицы, выходы i-х сумматоров по модулю подключены ко входам соответствующих блоков умножения на по модулю , i=1,…, n-1, в i-x вычислительных ступенях прямого хода, i=2,…, n-1, первые информационные входы j-х сумматоров по модулю через инверторы подключены к выходу первого блока умножения на по модулю (i-1)-ой вычислительной ступени прямого хода, вторые информационные входы j-х сумматоров по модулю подключены к выходам (j+1)-ых блоков умножения на по модулю (i-1)-ой вычислительной ступени прямого хода, на входы переносов j-х сумматоров по модулю подается сигнал логической единицы, выходы j-х сумматоров по модулю подключены к входам j-ых блоков умножения на по модулю , отличающееся тем, что в него введены n выходов прямого хода, n блоков перевода в СОК, n блоков хранения предвычисленных рангов, n выходов исходного числа, выход ранга, а также n-1 вычислительная ступень обратного хода, каждая из которых содержит n умножителей по модулю , n сумматоров по модулю , где j=1,…, n, вычислитель ранга суммы, вычислитель ранга произведения, при этом выход первого регистра хранения разрядов исходного числа является первым выходом прямого хода, выходы первых блоков умножения на по модулю i-x вычислительных ступеней прямого хода, i=1,…, n-1, являются (i+1)-ми выходами прямого хода, i-й выход прямого хода подключен к входу (n+1-i)-го блока перевода в СОК и входу (n+1-i)-го блока хранения предвычисленных рангов, i=1,…, n, i-й выход первого блока перевода в СОК подключен к входу i-го умножителя по модулю первой вычислительной ступени обратного хода и (i+1)-му входу вычислителя ранга произведения первой ступени обратного хода, первый вход которого соединен с выходом первого блока хранения предвычисленных рангов, в i-й вычислительной ступени обратного хода, i=1,…, n-1, j-й выход (i+1)-го блока перевода в СОК, j=1,…, n, соединен с первым входом j-го сумматора по модулю и 2j-м входом вычислителя ранга суммы i-й вычислительной ступени обратного хода, вторые входы j-х сумматоров по модулю и (2j+1)-е входы вычислителя ранга суммы i-й вычислительной ступени обратного хода соединены с выходами j-х умножителей по модулю , первый вход вычислителя ранга суммы i-й вычислительной ступени обратного хода соединен с выходом (i+1)-го блока хранения предвычисленных рангов, (2n+2)-й вход вычислителя ранга суммы i-й вычислительной ступени обратного хода соединен с выходом вычислителя ранга произведения i-й вычислительной ступени обратного хода, выходы j-х сумматоров по модулю , j=1,…, n, i-й вычислительной ступени обратного хода, i=1,…, n-2, соединены со входами j-х умножителей по модулю (i+1)-й вычислительной ступени обратного хода и (j+1)-ми входами вычислителя ранга произведения (i+1)-й вычислительной ступени обратного хода, первый вход вычислителя ранга произведения (i+1)-й вычислительной ступени обратного хода соединен с выходом вычислителя ранга суммы i-й вычислительной ступени обратного хода, выходы j-х сумматоров по модулю , j=1,…, n (n-1)-й вычислительной ступени обратного хода являются j-ми выходами исходного числа, выход вычислителя ранга суммы (n-1)-й вычислительной ступени обратного хода является выходом ранга устройства.