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

Авторы патента:

Червяков Николай Иванович (RU)

Лавриненко Ирина Николаевна (RU)

Ляхов Павел Алексеевич (RU)

Бабенко Михаил Григорьевич (RU)

Лавриненко Антон Викторович (RU)

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

Владельцы патента RU 2559772:

Федеральное государственное автономное образовательное учреждение высшего профессионального образования "Северо-Кавказский федеральный университет" (RU)

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

Изобретение относится к вычислительным модулярным системам и предназначено для выполнения основного деления чисел, представленных в системе остаточных классов (СОК).

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

Известно изобретение «Нейронная сеть для деления чисел, представленных в системе остаточных классов» (патент RU 2318239, G06F, опубл. 27.02.2008), содержащее нейронную сеть для расширения кортежа числовой системы вычетов, нейронные сети конечного кольца для суммирования и умножения.

Недостатком устройства является низкая скорость деления чисел и ограниченная функциональная возможность, так как в качестве делителя выбирается один их модулей системы остаточных классов (СОК).

Наиболее близкой к данному изобретению является «Нейронная сеть основного деления модулярных чисел» (патент RU 2400813, G06F 3/02, G06F 7/72, опубл. 27.04.2010). Недостатком устройства является большой объем оборудования. Известная нейронная сеть предназначена для деления модулярных чисел в случае, когда в качестве делителя используется целое положительное число, попарно простое с p₁, p₂, …, p_n, либо целое положительное число, представляющее собой произведение чисел, попарно взаимно простых с p_i. Для выполнения этого условия возникает необходимость нахождения приблизительного делителя путем использования обобщенной позиционной системы счисления (ОПСС). При вычислении приблизительного делителя нарушается регулярность структуры устройства деления, так как используются модульные и немодульные операции.

Техническим результатом данного изобретения является упрощение устройства за счет использования регулярной структуры, расширения функциональных возможностей и сокращения оборудования, что позволяет использовать предложенное изобретение в динамике вычислительного процесса. Указанный технический результат достигается тем, что устройство использует только модульные операции, то есть вычисления выполняются параллельно, в формате СОК. Предлагается устройство для основного деления модулярных чисел в формате системы остаточных классов, содержащее входные регистры делимого и делителя, выходы которых коммутируются мультиплексором для поочередного преобразования делимого и делителя, представленных в основной СОК, во вспомогательную СОК, выход мультиплексора соединен со входом блока расширения, расширяющего базу СОК, выход которого соединен со входом демультиплексора, выходы которого соединены с регистрами хранения остатков по расширенным основаниям, выход регистра делимого по расширенным основаниям соединен со входом умножителя, а выходы регистра делителя соединены с LUT-таблицей, преобразующей делитель по расширенным основаниям в мультипликативную инверсию, выходы которой соединены с умножителем, где реализуется вычислительная модель $c_{i}^{'} = a_{i}^{'} b_{i}^{' - 1}$ , где $a_{i}^{'} \equiv (a \mod p_{i}) \mod p_{i}^{'}$ , $b_{i}^{'} \equiv (b \mod p_{i}) \mod p_{i}^{'}$ , a - делимое, b - делитель, $b_{i}^{' - 1}$ - мультипликативная инверсия делителя $b_{i}^{'}$ , p_i - основные модули СОК, $p_{i}^{'}$ - модули вспомогательной СОК, а выходы умножителя соединены через мультиплексор со входом блока расширения для перехода от вспомогательной СОК к основной СОК, выход которого через демультиплексор соединен с регистрами хранения значений b″^-1 и c, где $b_{i}^{" - 1} \equiv b_{i}^{' - 1} \mod p_{i}$ и $c_{i} \equiv c_{i}^{'} \mod p_{i}$ , представленных в основной СОК, выходы регистра b″^-1 соединены с первыми входами умножителей, на вторые входы которого поступают соответственно делимое и делитель, где реализуется вычислительная модель $a_{i} b_{i}^{" - 1}$ и $b_{i} b_{i}^{" - 1}$ , выходы которых соединены через схемы ключей с входными регистрами делимого и делителя соответственно, а также с первыми входами схем вычитания и умножения, а на вторые входы которых, соответственно, поступают данные регистра с и константа 1, на третьи входы поступает $q_{i}^{- 1}$ , где реализуются вычислительные модели $(a_{i} b_{i}^{" - 1} - c_{i}) \cdot q_{i}^{- 1}$ и $(b_{i} b_{i}^{" - 1} - 1) \cdot q_{i}^{- 1}$ , где $q_{i} = (\prod_{i = 1}^{m} p_{i}^{'}) \mod p_{i}$ , $q_{i}^{- 1}$ - мультипликативная инверсия q_i, выходы которых подключены, соответственно, к выходному ключу и схеме сравнения с единицей, если результат схемы сравнения равен 1, то подается управляющий сигнал на вход выходного ключа, на выходе которого формируется результат деления (частное), в противном случае, если результат сравнения не равен 1, то формируется управляющий сигнал, который открывает схемы ключей, выходы которых подключены к входным регистрам делимого и делителя, представленных в основной СОК.

Устройство для основного деления модулярных чисел в формате системы остаточных классов содержит: входные шины для подачи делимого, шина 1, входные шины для подачи делителя, шина 2, и выходную шину частного, шина 53; регистр делимого 3 и регистр делителя 4; мультиплексор 5 для коммутации делимого и делителя на вход блока расширения 6, который коммутирует шины 28 и 29 на шину 30, являющуюся входом блока расширения 6, который преобразует делимое и делитель из основной системы оснований во вспомогательную систему оснований; демультиплексор 7 коммутирует выход блока расширения 6, шина 32, на вход 34 регистра делимого 8 и вход 35 регистра делителя 9, которые временно хранят делимое и делитель, представленные во вспомогательной СОК; умножитель 11, который выполняет операцию умножения делимого и мультипликативной инверсии делителя, представленных во вспомогательной СОК, поданных соответственно по шинам 36 и 37, 38 через LUT-таблицу 10, в которой происходит выборка мультипликативной инверсии делителя; шины 38 и 39 подаются на вход мультиплексора 12, который поочередно их коммутирует на выход 40, являющийся входом блока расширения 13, осуществляющего расширение поданных значений, представленных во вспомогательной СОК, в основную СОК; выход блока расширения 13, шина 42, поочередно коммутируется демультиплексором 16 на вход регистра 15, шина 44, и вход регистра 17, шина 45, для временного хранения, соответственно, мультипликативной инверсии и произведения делимого и мультипликативной инверсии, представленных в основной СОК; выход регистра 15, шина 46, подается на первые входы умножителей 18, 19, на вторые входы которых поступает делимое и делитель, представленные в основной СОК, шины 28 и 29; выходы умножителей 18 и 19, шины 48 и 49, произведений, соответственно, делимого и делителя на мультипликативную инверсию, представленных в основной СОК поступают через схемы ключей 24 и 25 на вход, соответственно, регистра делимого 3 и регистра делителя 4 по шинам 26 и 27, и одновременно данные по шинам 48 и 49, соответственно, поступают на первые входы схем вычитания и умножения 20 и 21, а на вторые входы поступает, соответственно, выход регистра 17, шина 47, хранящий произведения делимого и мультипликативной инверсии, преобразованные в основную СОК, и константа «1»; в схемах вычитания и умножения 20 и 21 полученные значения умножаются на константу $q_{i}^{- 1}$ , шина 50; выходы схемы вычитания и умножения 20 подаются на выходной ключ 22, а выходы схемы вычитания и умножения 21 - на вход схемы сравнения 23; если результат сравнения равен 1, то подается управляющий сигнал по шине 51 на вход выходного ключа 22, на выходе которого, шина 53, формируется частное, если результат не равен 1, то формируется управляющий сигнал по шине 52, который открывает схемы ключей 24 и 25 и подает на вход регистров делимого 3 и делителя 4 новые значения, необходимые для следующей итерации.

Управление процессом деления осуществляется блоком управления 14, который формирует адресные входы мультиплексоров 5, 12, шины, соответственно, 31 и 41, и адресные входы демультиплексоров 7, 16, шины, соответственно, 33 и 43.

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

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

Специализированные процессоры на основе арифметики СОК могут сыграть важную роль в высокоскоростных системах обработки данных в режиме реального времени. Операции сложения, вычитания и умножения, называемые модульными операциями, могут быть реализованы очень быстро, без распространения межразрядных переносов. Немодульные операции деления, сравнения чисел, определения знака и переполнения диапазона остаются сравнительно медленными. Любое улучшение скорости этих медленных алгоритмов значительно улучшает производительность многомодульных арифметико-логических устройств (АЛУ) и расширяет приложения СОК. Обычно при рассмотрении деления в СОК выделяют три категории: деление с нулевым остатком, масштабирование и деление в общем случае. Проблема деления в СОК в общем виде привлекает внимание многих исследователей для разработки высокопроизводительных многомодульных АЛУ. Известные алгоритмы деления в СОК, основанные на масштабировании, округлении, расширении и других операциях, являются медленными и требуют выполнения большого количества арифметических действий. Большинство известных алгоритмов работает путем рекурсивного вычитания числа, кратного делителю, из делимого до тех пор, пока разность не станет меньше, чем делитель. В связи с этим возникает необходимость упростить структуру вычислений при делении. Одно из направлений упрощения структуры устройства деления состоит в том, что делимое, делитель и остаток представлены только в формате СОК.

Рассмотрим параллельный алгоритм деления в СОК, преимущество которого состоит в том, что делимое, делитель и все промежуточные вычисления выполняются в СОК.

Параллельный алгоритм.

1. Пусть p₁, p₂, …, p_m есть набор модулей, (a₁, a₂, …, a_m) - делимое и (b₁, b₂, …, b_m) - делитель.

2. Определим вспомогательную систему оснований $(p_{1}^{'}, p_{2}^{'}, \dots, p_{m}^{'})$ , где $Н О Д (p_{i}, p_{j}^{'}) = 1$ для i, j=1, 2, …, m.

3. Вычислим (q₁, q₂, …, q_m), где $q_{i} = p_{1}^{'} \cdot p_{2}^{'} \cdot \dots \cdot p_{m}^{'} \mod p_{i}$ .

4. Переведем (a₁, a₂, …, a_m) по основаниям p₁, p₂, …, p_m в $(a_{1}^{'}, a_{2}^{'}, \dots, a_{m}^{'})$ по основаниям $p_{1}^{'}, p_{2}^{'}, \dots, p_{m}^{'}$ методом расширения базы СОК.

5. Переведем (b₁, b₂, …, b_m) по основаниям p₁, p₂, …, p_m в $(b_{1}^{'}, b_{2}^{'}, \dots, b_{m}^{'})$ по основаниям $p_{1}^{'}, p_{2}^{'}, \dots, p_{m}^{'}$ методом расширения базы СОК.

6. Вычисляем $(b_{1}^{- 1}, b_{2}^{- 1}, \dots, b_{m}^{- 1})$ по основаниям p₁, p₂, …, p_m, $(b_{1}^{' - 1}, b_{2}^{' - 1}, \dots, b_{m}^{' - 1})$ по основаниям $p_{1}^{'}, p_{2}^{'}, \dots, p_{m}^{'}$ и $(q_{1}^{- 1}, q_{2}^{- 1}, \dots, q_{m}^{- 1})$ по основаниям p₁, p₂, …, p_m.

7. Вычисляем $(c_{1}^{- 1}, c_{2}^{- 1}, \dots, c_{m}^{- 1}) = (a_{1}^{'}, a_{2}^{'}, \dots, a_{m}^{'}) \cdot (b_{1}^{- 1}, b_{2}^{- 1}, \dots, b_{m}^{- 1})$ .

8. Переведем $(b_{1}^{' - 1}, b_{2}^{' - 1}, \dots, b_{m}^{' - 1})$ по основаниям $p_{1}^{'}, p_{2}^{'}, \dots, p_{m}^{'}$ в $(b_{1}^{" - 1}, b_{2}^{" - 1}, \dots, b_{m}^{" - 1})$ по основаниям p₁, p₂, …, p_m и $(c_{1}^{'}, c_{2}^{'}, \dots, c_{m}^{'})$ по основаниям $p_{1}^{'}, p_{2}^{'}, \dots, p_{m}^{'}$ в (c₁, c₂, …, c_m) по основаниям p₁, p₂, …, p_m методом расширения базы СОК.

9. Вычисляем $(a_{1}, a_{2}, \dots, a_{m}) = ((a_{1}, a_{2}, \dots, a_{m}) \cdot (b_{1}^{" - 1}, b_{2}^{" - 1}, \dots, b_{m}^{" - 1}) - (c_{1}, c_{2}, \dots, c_{m})) \cdot (q_{1}^{- 1}, q_{2}^{- 1}, \dots, q_{m}^{- 1})$ .

10. Вычисляем $(b_{1}, b_{2} \dots, b_{m}) = ((b_{1}, b_{2} \dots, b_{m}) \cdot (b_{1}^{" - 1}, b_{2}^{" - 1}, \dots, b_{m}^{" - 1})) - (1, 1, \dots, 1)) \cdot (q_{1}^{- 1}, q_{2}^{- 1}, \dots, q_{m}^{- 1})$ .

11. Если (b₁, b₂, …, b_m)=(1, 1, …, 1), то (a ₁, a ₂, …, a _m) есть частное; иначе - перейти к шагу 4.

Пример.

Возьмем исходную систему оснований (p₁, p₂, p₃)=(7, 11, 13) и вспомогательную систему оснований $(p_{1}^{'}, p_{2}^{'}, p_{3}^{'}) = (5, 17, 19)$ . Для делимого a=212, равного в СОК (2, 3, 4)_{(7, 11, 13),} и делителя b=16, равного в СОК (2, 5, 3)_{(7, 11, 13),} частное $z = ⌊ \frac{212}{16} ⌋ = 13$ равно в СОК (6, 2, 0)_{(7, 11, 13)}.

Операция деления выполняется следующим образом.

1. Вычисляем ${(q_{1}, q_{2}, q_{3})}_{(p_{1}, p_{2}, p_{3})} = {(5, 9, 3)}_{(7, 11, 13)}$ и ${(q_{1}^{- 1}, q_{2}^{- 1}, q_{3}^{- 1})}_{(p_{1}, p_{2}, p_{3})} = {(3, 9, 3)}_{(7, 11, 13)}$ .

2. Переводим ${(a_{1}, a_{2}, a_{3})}_{(p_{1}, p_{2}, p_{3})} = {(2, 3, 4)}_{(7, 11, 13)}$ в ${(a_{1}^{'}, a_{2}^{'}, a_{3}^{'})}_{(p_{1}^{'}, p_{2}^{'}, p_{3}^{'})} = {(2, 8, 3)}_{(5, 7, 19)}$ .

3. Переводим ${(b_{1}, b_{2}, b_{3})}_{(p_{1}, p_{2}, p_{3})} = {(2, 5, 3)}_{(7, 11, 13)}$ в ${(b_{1}^{'}, b_{2}^{'}, b_{3}^{'})}_{(p_{1}^{'}, p_{2}^{'}, p_{3}^{'})} = {(1, 16, 16)}_{(5, 7, 19)}$ .

4. Переводим ${(b_{1}^{'}, b_{2}^{'}, b_{3}^{'})}_{(p_{1}^{'}, p_{2}^{'}, p_{3}^{'})} = {(1, 16, 16)}_{(5, 7, 19)}$ в ${(b_{1}^{' - 1}, b_{2}^{' - 1}, b_{3}^{' - 1})}_{(p_{1}^{'}, p_{2}^{'}, p_{3}^{'})} = {(1, 16, 16)}_{(5, 7, 19)}$ .

5. Вычисляем $\begin{array}{l} {(c_{1}^{'}, c_{2}^{'}, c_{3}^{'})}_{(p_{1}^{'}, p_{2}^{'}, p_{3}^{'})} = {(a_{1}^{'}, a_{2}^{'}, a_{3}^{'})}_{(p_{1}^{'}, p_{2}^{'}, p_{3}^{'})} \cdot {(b_{1}^{' - 1}, b_{2}^{' - 1}, b_{3}^{' - 1})}_{(p_{1}^{'}, p_{2}^{'}, p_{3}^{'})} = \\ = (2, 8, 3) \cdot (1, 16, 6) = {(2, 9, 18)}_{(5, 17, 19)} . \end{array}$

6. Переводим ${(b_{1}^{' - 1}, b_{2}^{' - 1}, b_{3}^{' - 1})}_{(p_{1}^{'}, p_{2}^{'}, p_{3}^{'})} = {(1, 16, 16)}_{(5, 7, 19)}$ в ${(b_{1}^{" - 1}, b_{2}^{" - 1}, b_{3}^{" - 1})}_{(p_{1}^{'}, p_{2}^{'}, p_{3}^{'})} = {(1, 16, 16)}_{(5, 7, 19)}$ .

7. Переводим ${(c_{1}^{'}, c_{2}^{'}, c_{3}^{'})}_{(p_{1}^{'}, p_{2}^{'}, p_{3}^{'})} = {(2, 9, 18)}_{(5, 7, 19)}$ в ${(c_{1}, c_{2}, c_{3})}_{(p_{1}, p_{2}, p_{3})} = {(4, 10, 1)}_{(7, 11, 13)}$ .

8. Вычисляем $\begin{array}{l} (a_{1}, a_{2}, a_{3}) = ((a_{1}, a_{2}, a_{3}) \cdot (b_{1}^{" - 1}, b_{2}^{" - 1}, b_{3}^{" - 1}) - (c_{1}, c_{2}, c_{3})) \cdot (q_{1}^{- 1}, q_{2}^{- 1}, q_{3}^{- 1}) = \\ = ({| (2 \cdot 3 - 4) \cdot 3 |}_{7}, {| (3 \cdot 2 - 10) \cdot |}_{11}, {| (4 \cdot 10 - 1) \cdot 9 |}_{13}) = (6, 2, 0) . \end{array}$

9. Вычисляем $(b_{1}, b_{2}, b_{3}) = ((b_{1}, b_{2}, b_{3}) \cdot (b_{1}^{" - 1}, b_{2}^{" - 1}, b_{3}^{" - 1}) - (1, 1, 1)) \cdot (q_{1}^{- 1}, q_{2}^{- 1}, q_{3}^{- 1}) = (1, 1, 1) .$

Так как (b₁, b₂, b₃)=(1, 1, 1), то частное вычисляется как (6, 2, 0).

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

Делимое a и делитель b, представленные в основной системе остаточных классов, по шинам 1 и 2 поступают на входные регистры делимого 3 и делителя 4. Выходные данные с регистров делимого 3 и делителя 4 по шинам соответственно 28 и 29 поступают на информационные входы мультиплексора 5. Под действием адресного входа, шина 31, формируемого блоком управления 14, мультиплексор 5 вначале подает делимое по шине 30 на вход блока расширения 6, который представляет собой нейронную сеть для расширения кортежа числовой системы вычетов (патент RU 2256226, Бюл. №19 от 10.07.2005). Блок расширения 6 преобразует делимое a_i, представленное в основной СОК, в делимое $a_{i}^{'}$ , представленное во вспомогательной СОК, где i=1, 2, …, m. С выхода блока расширения 6 по шине 32 данные через демультиплексор 7 и шину 34 поступают на регистр делимого 8, который служит для временного хранения делимого, представленного во вспомогательной СОК. Адресные входы демультиплексора 7 подключены к блоку управления 14 посредством шины 33.

После преобразования делимого аналогичным образом осуществляется преобразование делителя b, представленного в основной СОК, в делитель b′, представленный во вспомогательной СОК. При этом демультиплексор 7 через шину 35 помещает данные делителя в регистр делителя 9. С выхода регистра делителя 9 по шине 37 делитель $b_{i}^{'}$ , представленный во вспомогательной СОК, поступает на вход LUT-таблицы 10, где происходит преобразование делителя в мультипликативную инверсию $b_{i}^{' - 1}$ , и далее по шине 38 поступает на информационный вход мультиплексора 12 и первый вход умножителя 11, на вход которого поступают данные делимого $a_{i}^{'}$ , представленные во вспомогательной СОК. Результат умножения в умножителе 11 $c_{i}^{'} = a_{i}^{'} \cdot b_{i}^{' - 1}$ по шине 39 поступает на информационный вход мультиплексора 12. Под действием адресного входа, поступающего с блока управления 14 по шине 41, мультиплексор 12 поочередно подает на вход блока расширения 13 $b_{i}^{' - 1}$ и $c_{i}^{'}$ . Блок расширения 13 аналогичен блоку расширения 6 и осуществляет расширение $b_{i}^{' - 1}$ и $c_{i}^{'}$ , представленных во вспомогательной СОК, в значения $b_{i}^{" - 1}$ и c_i, представленные в основной СОК. С выхода блока расширения 13 данные по шине 42 коммутируются демультиплексором 16 на регистры 15 и 17 соответственно, шины 44 и 45, для хранения значений $b_{i}^{" - 1}$ и c_i. Данные $b_{i}^{" - 1}$ с выхода регистра 15 поступают на первые входы умножителей 18, 19, а на вторые входы которых поступают, соответственно, делимое и делитель, представленные в основной СОК, соответственно по шинам 28, 29. Результаты умножения $a_{i} b_{i}^{" - 1}$ и $b_{i} b_{i}^{" - 1}$ поступают по шинам 48 и 49 на первые входы схем вычитания и умножения 20 и 21, на вторые входы которых поступают с и 1, с умножением результатов вычитания на константу $q_{i}^{- 1}$ , поступающих по шине 50, где $q_{i}^{- 1}$ - мультипликативная инверсия q_i, $q_{i} = (\prod_{i = 1}^{m} p_{i}^{'}) \mod p_{i}$ . Результаты вычитания $(a_{i} b_{i}^{" - 1} - c_{i}) \cdot q_{i}^{- 1}$ и $(b_{i} b_{i}^{" - 1} - c_{i}) \cdot q_{i}^{- 1}$ , соответственно схемы 20 и 21, поступают на вход ключей 22 по шине 51 и схемы сравнения 23 с единицей, схема 23. Если результат схемы сравнения 23 равен 1, то на выходе выходного ключа 22, шина 53, формируется частное, если результат не равен 1, то сигнал по шине 52 открывает схемы ключей 24 и 25, которые подключают данные $a_{i} b_{i}^{" - 1}$ и $b_{i} b_{i}^{" - 1}$ с умножителей 18 и 19 к входным регистрам делимого 3 и делителя 4 для следующей итерации.

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

Анализ сложности устройства базируется на числе модулярных вычислений. Вычислительная сложность определяется вычислениями только по одному остатку, так как применяется параллельный алгоритм обработки. Модульное умножение выполняется по одному разу, а модульное сложение m+1 раз в преобразованиях a, b к a′, b′ и m+1 раз при преобразовании c′, b′^-1 к c, b″^-1. Вычисление b′^-1 составляет O(d), где d - количество цифр в модуле. Сложность устройства представлена в таблице 1.

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

Устройство для основного деления модулярных чисел в формате системы остаточных классов, содержащее входные регистры делимого и делителя, выходы которых коммутируются мультиплексором для поочередного преобразования делимого и делителя, представленных в основной системе остаточных классов (СОК), во вспомогательную СОК, выход мультиплексора соединен со входом блока расширения, расширяющего базу СОК, выход которого соединен со входом демультиплексора, выходы которого соединены с регистрами хранения остатков по расширенным основаниям, выход регистра делимого по расширенным основаниям соединен со входом умножителя, а выходы регистра делителя соединены с LUT-таблицей, преобразующей делитель по расширенным основаниям в мультипликативную инверсию, выходы которой соединены с умножителем, где реализуется вычислительная модель $c_{i}^{'} = a_{i}^{'} b_{i}^{' - 1}$ , где $a_{i}^{'} \equiv (a \mod p_{i}) \mod p_{i}^{'}$ , $b_{i}^{'} \equiv (b \mod p_{i}) \mod p_{i}^{'}$ , a - делимое, b - делитель, $b_{i}^{' - 1}$ - мультипликативная инверсия делителя $b_{i}^{'}$ , p_i - основные модули СОК, $p_{i}^{'}$ - модули вспомогательной СОК, а выходы умножителя соединены через мультиплексор со входом блока расширения для перехода от вспомогательной СОК к основной СОК, выход которых через демультиплексор соединен с регистрами хранения значений b″^-1 и c, где $b_{i}^{" - 1} \equiv b_{i}^{' - 1} \mod p_{i}$ и $c_{i} \equiv c_{i}^{'} \mod p_{i}$ , представленных в основной СОК, выходы регистра b″^-1 соединены с первыми входами умножителей, на вторые входы которых поступают соответственно делимое и делитель, где реализуется вычислительная модель $a_{i} b_{i}^{" - 1}$ и $b_{i} b_{i}^{" - 1}$ , выходы которых соединены через схемы ключей с входными регистрами делимого и делителя соответственно, а также с первыми входами схем вычитания и умножения, а на вторые входы которых соответственно поступают данные регистра с и константа 1, на третьи входы поступает $q_{i}^{- 1}$ , где реализуются вычислительные модели $(a_{i} b_{i}^{" - 1} - c_{i}) \cdot q_{i}^{- 1}$ и $(b_{i} b_{i}^{" - 1} - 1) \cdot q_{i}^{- 1}$ , где $q_{i} = (\prod_{i = 1}^{m} p_{i}^{'}) \mod p_{i}$ , $q_{i}^{- 1}$ - мультипликативная инверсия q_i, выходы которых подключены соответственно к выходному ключу и схеме сравнения с единицей, если результат схемы сравнения равен 1, то подается управляющий сигнал на вход выходного ключа, на выходе которого формируется результат деления (частное), в противном случае, если результат сравнения не равен 1, то формируется управляющий сигнал, который открывает схемы ключей, выходы которых подключены к входным регистрам делимого и делителя, представленных в основной СОК.

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

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

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

Устройство для сравнения чисел в системе остаточных классов на основе интервально-позиционных характеристик // 2557444

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

Устройство для преобразования из полиномиальной системы классов вычетов в позиционный код // 2513915

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

Способ организации выполнения операции умножения двух чисел в модулярно-позиционном формате представления с плавающей точкой на универсальных многоядерных процессорах // 2509345

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

Устройство для определения знака модулярного числа // 2503995

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

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

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

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

Накапливающий сумматор по модулю // 2500017

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

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

Устройство расширения оснований модулярного кода // 2562366

Изобретение относится к вычислительной технике и, в частности, к непозиционным компьютерным системам, и предназначено для обеспечения требуемой точности при вычислении с использованием модулярного кода. Техническим результатом является снижение аппаратных затрат на выполнение операции расширения оснований в полиномиальном модулярном коде. Устройство расширения оснований модулярного кода характеризуется тем, что вход устройства, на который подается модулярный полиномиальный код A(z)=(α1(z), α2(z), …, αn(z)), где αi(z) - остатки по основанию pi(z), i=1, …, n, используемому в полиномиальном модулярном коде, подключается к первым входам умножителей по модулю pi(z) первого блока умножителей соответственно, а вторые входы этих умножителей соединены с выходами первого блока памяти, выход 2.i-го умножителя по модулю pi(z), первого блока умножителей подсоединен к первому входу 4.i-го умножителя по модулю pn+1(z) второго блока умножителей, при этом второй вход умножителя по модулю pn+1(z) подключен к выходу второго блока памяти, выходы умножителей второго блока умножителей подсоединены к входам сумматора по модулю два, выход которого является выходом устройства. 1 ил.

Криптография на упрощенной эллиптической кривой // 2574826

Изобретение относится к области шифрования сообщений на основе использования точек на эллиптической кривой. Технический результат - повышение надежности криптографического шифрования за счет выполнения аутентификации и идентификации за одно и то же время. Способ выполнения аутентификации пароля или идентификации идентификатора с использованием криптографического преобразования включает этапы, на которых выполняют криптографическое преобразование в электронном компоненте для получения точки Р (Х, Y) на эллиптической кривой исходя из по меньшей мере одного параметра t, связанного с указанным паролем или идентификатором; выполняют аутентификацию пароля или идентификацию идентификатора с использованием значений абсциссы (X) и ординаты (Y) полученной точки Р. 2 н. и 5 з.п. ф-лы, 3 ил.

Устройство для вычисления коэффициентов обобщенной полиадической системы с коррекцией ошибок // 2584495

Изобретение относится к вычислительной технике, в частности к модулярным нейрокомпьютерным средствам, и предназначено для вычисления коэффициентов обобщенной полиадической системы (ОПС), представленных в полях Галуа GF(2v). Техническим результатом является обеспечение возможности исправления ошибок в коэффициентах ОПС, которые были получены из кодовой комбинации, представленной в полиномиальной системе классов вычетов (ПСКВ). Устройство содержит двухслойную нейронную сеть, каждый слой которой содержит 15 нейронов, блок памяти и 7 корректирующих сумматоров по модулю два. 1 ил., 4 табл.

Модулярный полиномиальный вычислитель систем булевых функций // 2586575

Изобретение относится к вычислительной технике и может быть использовано как специализированный вычислитель - универсальный в классе логических вычислений. Техническим результатом является уменьшение объемов оборудования. Устройство содержит коммутатор, 2k блоков памяти хранения значений коэффициентов полиномов разложения, 2n-k блоков памяти хранения значений вычетов возведения переменной в i-тую степень (i=0, 1, …, 2n-k-1) по модулю Р, многоканальный мультиплексор выделения группы коэффициентов, многоканальный мультиплексор выделения группы вычетов, 2n-k умножителей по модулю Ρ, сумматор по модулю Ρ, n входов подачи булевых переменных устройства, управляющий вход устройства подачи значения количества переменных разложения, управляющий вход устройства подачи значений коэффициентов, управляющий вход устройства подачи значений вычетов возведения переменной в i-тую степень по модулю Р, d выходов устройства выдачи значений булевых функций. 1 ил.

Способ и устройство размещения групп чисел в однородных блоках цифрового регистра // 2591009

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

Многовходовой сумматор по модулю два // 2614370

Изобретение относится к вычислительной технике и может быть использовано в цифровых вычислительных устройствах, а также устройствах для формирования элементов конечных полей GF(2ν). Технический результат заключается в снижении схемных затрат, необходимых на реализацию многовходового сумматора по модулю два. Технический результат достигается за счет использования новой функции активации в скрытом слое, применения синаптических весов ωi,j, равных единице, что позволяет исключить из структуры формального нейрона умножители синатических весов, а также исключения из структуры нейрона выходного слоя блока, реализующего вычисления функции активации. 1 ил.

Устройство для вычисления сумм парных произведений в полиномиальной системе классов вычетов // 2622881

Изобретение относится к вычислительной технике и может быть использовано в процессорах обработки сигналов, в цифровых фильтрах для обнаружения и коррекции ошибки. Техническим результатом, достигнутым при осуществлении заявленного изобретения, является сокращение аппаратных затрат. Указанный технический результат достигается за счет того, что число переходов за пределы рабочего диапазона определяется только значениями остатков по рабочим основаниям ПСКВ, которые можно заранее просчитать и учесть в структуре нейронной сети блока коррекции. Это позволяет отказаться от счетчика числа переходов и дополнительного слоя нейронной сети, находящихся в блоке коррекции ошибки прототипа. 2 ил., 5 табл.

Устройство деления модулярных чисел // 2628179

Изобретение относится к вычислительным модулярным системам и предназначено для выполнения деления чисел, представленных в системе остаточных классов (СОК). Технический результат – обеспечение возможности деления с отрицательными числами, представленными в системе остаточных классов. Устройство деления модулярных чисел содержит вход тактового импульса, вход глобального сброса, вход делимого, вход делителя, элемент ИЛИ, блок вычисления позиционных характеристик, блок уточнения аппроксимационного ряда, блок вывода частного и выход вывода частного. При этом блок вычисления позиционных характеристик содержит регистр делимого, n инверторов делимого, n регистров хранения модуля pi, где i=1,…,n, n регистров хранения коэффициента ki, n сумматоров делимого, n умножителей отрицательного делимого, n умножителей положительного делимого, сумматор значения F(A), сумматор значения F(-A), регистр хранения значения F (-А), регистр хранения значения F(A), регистр делителя, n инверторов делителя, n регистров хранения модуля pi, n регистров хранения коэффициента ki, n сумматоров делителя, n умножителей отрицательного делителя, n умножителей положительного делителя, сумматор значения F(B), сумматор значения F(-B), регистр хранения значения F(-B), регистр хранения значения F(B), элемент XOR, мультиплексор делимого, мультиплексор делителя, блок сравнения. Блок уточнения аппроксимационного ряда содержит регистр сдвига, счетчик, регистр хранения , регистр хранения уменьшаемого, мультиплексор выбора уменьшаемого, инвертор, память хранения степеней «2» в СОК, сумматор, мультиплексор выбора следующего уменьшаемого, элемент НЕ, элемент И. Блок вывода частного состоит из элемента ИЛИ, элемента задержки, удерживающего регистра, n регистров хранения остатка по модулю pi, n сумматоров по модулю pi, n демультиплексоров по модулю pi, n регистров хранения суммы по модулю pi, n инверторов, n регистров хранения модуля pi, n сумматоров, n регистров хранения обратного значения суммы по модулю n мультиплексоров выбора суммы, удерживающего регистра знака, регистра хранения суммы в СОК, регистра хранения значения «1», регистра хранения значения «-1», мультиплексора равенства абсолютных величин делимого и делителя, мультиплексора вывода частного, регистра хранения частного. 4 ил.

Арифметико-логическое устройство для сложения и вычитания чисел по модулю // 2639645

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

Арифметико-логическое устройство для сложения и вычитания чисел по модулю // 2639645