устройство для умножения чисел по модулю

Классы МПК:G06F7/52 для умножения; для деления
G06F7/72 с помощью арифметического остатка
Автор(ы):, , ,
Патентообладатель(и):Воронежский государственный университет
Приоритеты:
подача заявки:
1998-07-29
публикация патента:

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

Формула изобретения

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

Описание изобретения к патенту

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

Известно устройство (аналог) (авт. св. СССР N 1615714, МКИ G 06 F 7/49, 7/72, Б.И. N 47, 1990 г.), содержащее два дешифратора, три группы элементов ИЛИ, два блока элементов И, коммутатор, шифратор, блок инвестирования, вычитатель по модулю, две группы элементов И, сумматор по модулю два. Недостаток устройства - большое количество оборудования.

Известно также устройство (аналог) (авт. св. СССР N 1775721, МКИ G 06 F 7/49, 7/72, Б.И. N 42, 1992 г.), содержащее два дешифратора, группы элементов ИЛИ, элементы ИЛИ и И, элементы НЕ, блоки элементов И, элемент запрета, коммутатор, сумматор по модулю два, шифраторы. Недостаток устройства - большое количество оборудования.

Наиболее близким по технической сущности (прототипом к предлагаемому изобретению) является устройство (авт. св. СССР N 1667055, МКИ G 06 F 7/49, 7/72, Б.И. N 28, 1991 г.), содержащее дешифратор, две группы элементов ИЛИ, два элемента ИЛИ, пять элементов И, две группы элементов И, шифратор, регистр и коммутатор. Общее количество логических элементов И коммутатора составляет m2/8, где m - модуль устройства, что обуславливает основной недостаток устройства.

Недостаток прототипа - большое количество используемого оборудования, ввиду того, что количество логических элементов коммутатора пропорционально квадрату модуля.

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

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

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

Сущность изобретения состоит в совмещении операций по двум внутренним модулям устройства на одном табличном вычислителе за несколько тактов работы, ввиду чего происходит уменьшение числа логических элементов, необходимых для реализации устройства. Обозначим через m - модуль устройства, m1 - первый внутренний модуль устройства, m2 - второй внутренний модуль устройства (m1 > m2). Для взаимно простых модулей m1 и m2 операцию модульного умножения с операндами A и B можно представить в виде

Aустройство для умножения чисел по модулю, патент № 2143723B mod m = (устройство для умножения чисел по модулю, патент № 21437231устройство для умножения чисел по модулю, патент № 2143723устройство для умножения чисел по модулю, патент № 21437231,устройство для умножения чисел по модулю, патент № 21437232устройство для умножения чисел по модулю, патент № 2143723устройство для умножения чисел по модулю, патент № 21437232) = (t1,t2),

где устройство для умножения чисел по модулю, патент № 21437231(устройство для умножения чисел по модулю, патент № 21437231) = A(B)mod m1, устройство для умножения чисел по модулю, патент № 21437232(устройство для умножения чисел по модулю, патент № 21437232) = A(B)mod m2.

Исходя из минимизации количества используемого табличного оборудования, целесообразно выбирать m1 устройство для умножения чисел по модулю, патент № 2143723 m2, т. е. устройство для умножения чисел по модулю, патент № 2143723 Рассмотрим реализацию основных узлов устройства при m = 12, m1 = 4, m2 = 3. Для выполнения операции модульного умножения по внутренним модулям m1 = 4, m2 = 3 необходимо иметь соответствующие таблицы 1 и 2.

Табличный 6 вычислитель представляет наложение таблиц 1 и 2, общее количество логических элементов N которого составит

устройство для умножения чисел по модулю, патент № 2143723

т.е. пропорционально модулю устройства.

Преобразователи 2, 10 двоичного кода числа реализуют таблицу 3.

Преобразователь 3, 11 двоичного кода числа реализуют таблицу 4.

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

Результат операции модульного умножения по первому m1 и второму m2 внутренним модулям устройства можно представить в виде

Aустройство для умножения чисел по модулю, патент № 2143723B mod m = (t2, t2) mod m = [(t1, 0) + (0, t2)] mod m,

где t1 = устройство для умножения чисел по модулю, патент № 21437231устройство для умножения чисел по модулю, патент № 21437231mod m1, t2 = устройство для умножения чисел по модулю, патент № 21437232устройство для умножения чисел по модулю, патент № 21437232mod m2, а устройство для умножения чисел по модулю, патент № 21437231(устройство для умножения чисел по модулю, патент № 21437231) и устройство для умножения чисел по модулю, патент № 21437232(устройство для умножения чисел по модулю, патент № 21437232) - остатки, которыми представлены операнды A и B по соответствующим внутренним модулям m1 и m2.

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

Aустройство для умножения чисел по модулю, патент № 2143723B mod m=[f(t1)+f(t2)] mod m,

где f(t1) и f(t2) - позиционные представления соответственно кодов (t1, 0) и (0, t2) в диапазоне чисел устройство для умножения чисел по модулю, патент № 2143723.

Подобный прием можно использовать для перевода чисел из системы остаточных классов (СОК) в позиционную систему счисления по нескольким модулям. Если число C изображается набором остатков по всем модулям устройство для умножения чисел по модулю, патент № 2143723

C = (C1,C2...,Cn) =(C1, 0,...,0)+(0,C2,...,0)+...+(0,0,...,Cn), то (C)10 = [f(c1) + f(c2) +...+f(cn)] mod M,

где устройство для умножения чисел по модулю, патент № 2143723

Такое представление числа в СОК аналогично разложению по соответствующим модулям m1 в позиционном коде и является однозначным. В отличие от ряда известных алгоритмов перевода числа из СОК в позиционную (десятичную) систему, этот алгоритм не требует для его выполнения операций умножения и деления. Преобразование C1--->f(C1) соответствует переводу числа (C1, 0,..., 0) из СОК в позиционный код. В частности, согласно табл. 5 число 6 = (2, 0) по внутренним модулям m1 = 4, m2 = 3; а число 4 = (0, 1) по соответствующим внутренним модулям согласно табл. 6. Сумматор 15 по модулю устройства является арифметико-логическим устройством комбинационного типа. Следует отметить, что предварительный анализ операндов A и B на равенство нулю позволит упростить схематическое решение предлагаемого устройства за счет дополнительного уменьшения количества оборудования при построении его отделочных узлов.

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

На чертеже представлена структурная схема, где: 1 - первый информационный вход устройства, 2 - первый преобразователь двоичного кода числа в унитарный код по первому внутреннему модулю устройства, 3 - первый преобразователь двоичного кода числа в унитарный код по второму внутреннему модулю устройства, 4 - первый блок элементов И, 5 - второй блок элементов И, 6 - табличный вычислитель, 7 - пятый блок элементов И, 8 - шестой блок элементов И, 9 - второй информационный вход устройства, 10 - второй преобразователь двоичного кода числа в унитарный код по первому внутреннему модулю устройства, 11 - второй преобразователь двоичного кода числа в унитарный код по второму внутреннему модулю устройства, 12 - третий блок элементов И, 13 - четвертый блок элементов И, 14 - преобразователь унитарного кода числа по второму внутреннему модулю в двоичный позиционный код, 15 - сумматор по модулю устройства, 16 - выход устройства, 17 - регистр, 18 - преобразователь унитарного кода числа по первому внутреннему модулю устройства в двоичный позиционный код, 19 - первый тактовый вход устройства, 20 - второй тактовый вход устройства.

Первый 1 информационный вход устройства соединен с входами первых 2, 3 преобразователей двоичного числа в унитарный код соответственно по первому и второму внутренним модулям устройства, выходы которых соединены с первыми входами соответственно первого 4 и второго 5 блоков элементов И, выходы разрядов которых соединены с соответствующими информационными входами табличного 6 вычислителя, выходы которого соединены с соответствующими первыми входами разрядов пятого 7 и шестого 8 блоков элементов И, второй 9 информационный вход устройства соединен с входами вторых 10, 11 преобразователей двоичного числа в унитарный код соответственно по первому и второму внутренним модулям устройства, выходы которых соединены с первыми входами третьего 12 и четвертого 13 блоков элементов И, выходы разрядов которых соединены с соответствующими управляющими входами табличного 6 вычислителя, выход 8 блока элементов И соединен со входом преобразователя 14 унитарного кода числа по второму внутреннему модулю устройства в двоичный позиционный код, выход которого соединен со вторым входом сумматора 15 по модулю устройства, выход которого является выходом 16 устройства, выход пятого 7 блока элементов И соединен со входом регистра 17, выход которого соединен со входом преобразователя 18 унитарного кода числа по первому внутреннему модулю устройства в двоичный позиционный код, выход которого соединен с первым входом сумматора 15 по модулю устройства, первый 19 тактовый вход устройства соединен со вторыми входами первого 4, третьего 12 и пятого 7 блоков элементов И, второй 20 тактовый вход устройства соединен со вторыми входами второго 5, четвертого 13 и шестого 8 блоков элементов И.

Работа устройства происходит на два такта.

При первом такте работы поступает сигнал на первый 19 тактовый вход устройства. Одновременно этот сигнал поступает на вторые входы первого 4, третьего 12 и пятого 7 блоков элементов И. Операнд A в двоичном коде поступает с первого 1 информационного входа устройства на вход первого преобразователя 2 двоичного кода в унитарный код по первому внутреннему модулю устройства, с выхода которого A mod m1 в унитарном коде поступает на первый вход устройство для умножения чисел по модулю, патент № 21437231-го разряда первого 4 блока элементов И и далее на соответствующий информационный вход табличного 6 вычислителя. Операнд В в двоичном коде поступает со второго 9 информационного входа устройства на вход второго преобразователя 10 двоичного кода числа в унитарный код по первому внутреннему модулю устройства, с выхода которого B mod m1 в унитарном коде поступает на первый вход устройство для умножения чисел по модулю, патент № 21437231-го разряда третьего 12 блока элементов И и далее на соответствующий управляющий вход табличного 6 вычислителя. Результат операции устройство для умножения чисел по модулю, патент № 21437231устройство для умножения чисел по модулю, патент № 2143723устройство для умножения чисел по модулю, патент № 21437231 mod m1 поступает с t1-го выхода табличного 6 вычислителя на первый вход соответствующего разряда пятого 7 блока элементов И, с выхода которого результат модульного умножения по первому внутреннему модулю устройства фиксируется записью единицы в t1-м разряде регистра 17. С выхода регистра 17 унитарный код операции устройство для умножения чисел по модулю, патент № 21437231устройство для умножения чисел по модулю, патент № 2143723устройство для умножения чисел по модулю, патент № 21437231 mod m1 поступает на вход преобразователя 18 унитарного кода числа по первому внутреннему модулю устройства в двоичный позиционный код, с выхода которого результат преобразования в двоичном коде поступает на первый вход сумматора 15 по модулю.

На втором такте работы сигнал поступает на второй 20 тактовый вход устройства и процесс определения результата операции умножения по второму m2 внутреннему модулю устройства устройство для умножения чисел по модулю, патент № 21437232устройство для умножения чисел по модулю, патент № 2143723устройство для умножения чисел по модулю, патент № 21437232 mod m2, с точностью до соответствующих элементов, происходит аналогичным образом. Отличие заключается в том, что с выхода шестого 8 блока элементов И единичный код результата операции модульного умножения по второму внутреннему модулю устройства поступает на вход преобразователя 14 унитарного кода числа по второму внутреннему модулю устройства в двоичный позиционный код, с выхода которого результат преобразования в двоичном коде поступает на второй вход сумматора 15 по модулю. С выхода сумматора 15 по модулю результат операции Aустройство для умножения чисел по модулю, патент № 2143723B mod m поступает на выход 16 устройства.

Рассмотрим пример выполнения операции Aустройство для умножения чисел по модулю, патент № 2143723B mod m при m = 12, A=5, B=7, m1 = 4, m2 = 3. В этом случае операнд A= 01012 и B = 01112 поступают соответственно на первый 1 и второй 10 информационные входы устройства. По первому такту работы с выходов первого 2 и второго 10 преобразователей двоичного кода в унитарный код по первому внутреннему модулю поступают сигналы на первый информационный и третий управляющий входы табличного 6 вычислителя через соответствующие разряды первого 4 и третьего 12 блоков элементов И (см. табл. 3). С выходов табличного 6 вычислителя сигнал поступает через пятый 7 блок элементов И на запись единицы в третий разряд регистра 17 (см. табл. 1). Единичный код результата операции умножения по первому внутреннему модулю поступает с выхода регистра 17 на вход преобразователя 18 унитарного кода числа по первому внутреннему модулю устройства в двоичный позиционный код. Результат преобразования 00112 (см. табл. 5) поступает далее на первый вход сумматора 15 по модулю.

При втором такте работы устройства с выходов первого 3 и второго 11 преобразователей двоичного кода числа в унитарный код по второму внутреннему модулю поступают сигналы на второй информационный и первый управляющий входы табличного 6 вычислителя через соответствующие разряды второго 5 и четвертого 13 блоков элементов И (см. табл. 4). С выходов табличного 6 вычислителя сигнал поступает на первый вход второго разряда пятого 8 блока элементов И, с выхода которого унитарный код результата операции умножения по второму внутреннему модулю поступает на вход преобразователя 14 унитарного кода числа по второму внутреннему модулю устройства в двоичный позиционный код. Результат преобразования 10002 (см. табл. 6) поступает далее на второй вход сумматора 15 по модулю, с выхода которого результат операции модульного умножения 10112 = 1110 поступает на выход 16 устройства. Проверка: 5устройство для умножения чисел по модулю, патент № 21437237 mod 12 = 11 mod 12.

Класс G06F7/52 для умножения; для деления

способ организации умножения чисел с плавающей запятой, представленных в системе остаточных классов -  патент 2485574 (20.06.2013)
устройство для умножения чисел в коде "1 из 4" -  патент 2475812 (20.02.2013)
устройство и способ комбинаторного кодирования сигналов с низкой сложностью -  патент 2438235 (27.12.2011)
ускоренный умножитель на нейронах -  патент 2322688 (20.04.2008)
нейронная сеть для деления чисел, представленных в системе остаточных классов -  патент 2305312 (27.08.2007)
способ, устройство и команда для выполнения знаковой операции умножения -  патент 2275677 (27.04.2006)
целочисленное умножение высокого порядка с округлением и сдвигом в архитектуре с одним потоком команд и множеством потоков данных -  патент 2263947 (10.11.2005)
устройство для умножения чисел в коде "1 из 4" -  патент 2251144 (27.04.2005)
делитель на нейронах -  патент 2249846 (10.04.2005)
умножитель на нейронах -  патент 2249845 (10.04.2005)

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

устройство для преобразования из полиномиальной системы классов вычетов в позиционный код -  патент 2513915 (20.04.2014)
способ организации выполнения операции умножения двух чисел в модулярно-позиционном формате представления с плавающей точкой на универсальных многоядерных процессорах -  патент 2509345 (10.03.2014)
устройство для определения знака модулярного числа -  патент 2503995 (10.01.2014)
устройство для сравнения чисел, представленных в системе остаточных классов -  патент 2503992 (10.01.2014)
способ организации умножения чисел с плавающей запятой, представленных в системе остаточных классов -  патент 2500018 (27.11.2013)
накапливающий сумматор по модулю -  патент 2500017 (27.11.2013)
способ организации умножения чисел с плавающей запятой, представленных в системе остаточных классов -  патент 2485574 (20.06.2013)
полный одноразрядный сумматор по модулю -  патент 2484519 (10.06.2013)
устройство для обнаружения переполнения динамического диапазона, определения ошибки и локализации неисправности вычислительного канала в эвм, функционирующих в системе остаточных классов -  патент 2483346 (27.05.2013)
ячейка однородной вычислительной среды, однородная вычислительная среда и устройство для конвейерных арифметических вычислений по заданному модулю -  патент 2477513 (10.03.2013)
Наверх