Арифметическое устройство по модулю

 

Изобретение относится к автоматике и вычислительной технике и может быть использовано в вычислительных структурах, функционирующих в модулярной системе счисления. Технический результат заключается в повышении надежности и уменьшении аппаратурных затрат. Технический результат достигается за счет того, что в устройство, содержащее два шифратора, с первого по третий блоки элементов И, введены первый и второй мультиплексоры, с первого по четвертый табличные вычислители, два регистра, два преобразователя кода числа Х в код [Х/к] (к - внутренний модуль устройства), два преобразователя кода числа Х в код Х modк, первый и второй блоки умножения на константу по модулю, два квадратора по модулю, блок деления на четыре по модулю. Этим достигается уменьшение аппаратурных затрат за счет существенного уменьшения числа логических элементов для построения табличных узлов, составляющих основной объем оборудования. 6 табл., 1 ил.

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

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

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

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

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

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

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

Поставленная цель достигается тем, что в устройство, содержащее первый табличный вычислитель, два шифратора, с первого по третий блоки элементов И, введены первый и второй мультиплексоры, со второго по четвертый табличные вычислители, два регистра, два преобразователя кода числа X в код [X/к] (к - внутренний модуль устройства), два преобразователя кода числа X в код X modк, первый и второй блоки умножения на константу по модулю, два квадратора по модулю, блок деления на четыре по модулю, причем входы первого и второго операндов соединены с первыми информационными входами соответственно первого и второго мультиплексоров, первые адресные входы которых соединены с первым управляющим входом устройства и первыми входами первого и второго блоков элементов И, а вторые адресные входы - со вторым управляющим входом устройства и первым входом третьего блока элементов И, выход первого мультиплексора соединен с входами первого преобразователя кода числа X в код [X/к] и первого преобразователя кода числа X в код X modк, выходы которых соединены с первыми входами соответственно первого и второго табличных вычислителей, выход второго мультиплексора соединен с входами второго преобразователя кода числа X в код [X/к] и второго преобразователя кода числа X в код X modк, выходы которых соединены со вторыми входами соответственно первого и второго табличных вычислителей, первый и второй выходы которого соединены с первыми входами соответственно третьего и четвертого табличных вычислителей, входы которых соединены соответственно с выходами первого и второго блоков умножения на константу по модулю, входы которых соединены соответственно с первым и вторым выходами первого табличного вычислителя, выход третьего табличного вычислителя соединен с входом первого квадратора по модулю и вторым входом первого блока элементов И, выход которого является выходом сложения устройства, выход четвертого табличного вычислителя соединен с входами второго квадратора по модулю, блока деления на четыре по модулю и вторым входом второго блока элементов И, выход которого является выходом вычитания устройства, выходы первого и второго квадраторов по модулю соединены с входами соответственно первого и второго шифраторов, выходы которых соединены с входами первого и второго регистров, выходы которых соединены со вторыми информационными входами соответственно первого и второго мультиплексора, выход блока деления на четыре по модулю соединен со вторым входом третьего блока элементов И, выход которого является выходом умножения устройства.

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

(A·B) mod m = [((A + B)² mod m - (A - B)² mod m)/4] mod m, где m - модуль операции, A (B) - операнды.

Операции модульного сложения и вычитания реализуются при помощи следующих соотношений: (A+B)mod m = [к(Aʹ+Bʹ)+(Δ_A+Δ_B)]mod m, (A-B)mod m = [к(Aʹ-Bʹ)+(Δ_A-Δ_B)]mod m, где A' = [A/к]; B' = [B/к]; Δ_A= A mod к; Δ_B= B mod к. Исходя из минимизации количества используемого оборудования целесообразно выбирать к ≈ √m. При этом общее число логических элементов, необходимое для построения четырех табличных вычислителей, составит N ≈ 2(√m)²+2(2√m·2√m) = 10·m,
т. е. величина аппаратурных затрат относительно модуля заявленного устройства изменяется по линейному закону.

Рассмотрим реализацию основных узлов устройства при m = 61, к = 8.

Для выполнения операций модульного сложения и вычитания по внутреннему модулю к = 8 необходимо, чтобы первый и второй табличные вычислители 12, 13 работали в соответствии с таблицами 1, 2 (сложение) и таблицами 3, 4 (вычитание). С первых выходов первого 12 и второго 13 табличных вычислителей снимается результат сложения, полученный соответственно из таблиц 1, 2, а со вторых выходов первого 12 и второго 13 табличных вычислителей снимается результат вычитания, полученный соответственно из таблиц 3, 4.

Для восстановления операций сложения и вычитания по модулю устройства m = 61 необходимо, чтобы третий и четвертый табличные вычислители 16, 17 работали в соответствии с таблицами 5 (сложение) и 6 (вычитание).

Операция деления в блоке 23 деления на четыре по модулю производится умножением на γ-обратную мультипликативную величину числа "4", которая определяется из уравнения [γ[C]_m]_m= 1, где C - делитель. В нашем случае при m = 61, C = 4 имеем [γ[4]₆₁]₆₁= 1, откуда γ = 46.

На чертеже представлена структурная схема устройства, где 1 - вход первого операнда, 2 - вход второго операнда, 3 - первый мультиплексор, 4 - второй мультиплексор, 5 - первый управляющий вход устройства, 6 - первый блок элементов И, 7 - второй блок элементов И, 8 - второй управляющий вход устройства, 9 - третий блок элементов И, 10 - первый преобразователь кода числа X в код [X/к], 11 - первый преобразователь кода числа X в код X modк, 12 - первый табличный вычислитель, 13 - второй табличный вычислитель, 14 - второй преобразователь кода числа X в код [X/к], 15 - второй преобразователь кода числа X в код X modк, 16 - третий табличный вычислитель, 17 - четвертый табличный вычислитель, 18 - первый блок умножения на константу по модулю, 19 - второй блок умножения на константу по модулю, 20 - первый квадратор по модулю, 21 - выход сложения устройства, 22 - второй квадратор по модулю, 23 - блок деления на четыре по модулю, 24 - выход вычитания устройства, 25 - первый шифратор, 26 - второй шифратор, 27 - первый регистр, 28 - второй регистр, 29 - выход умножения устройства.

Вход первого 1 и второго 2 операндов соединены с первыми информационными входами соответственно первого 3 и второго 4 мультиплексоров, первые адресные входы которых соединены с первым управляющим входом 5 устройства и первыми входами первого 6 и второго 7 блоков элементов И, а вторые адресные входы - со вторым управляющим входом 8 устройства и первым входом третьего блока 9 элементов И, выход первого 3 мультиплексора соединен с входами первого 10 преобразователя кода числа X в код [X/к] и первого 11 преобразователя кода числа X в код X modк, выходы которых соединены с первыми входами соответственно первого 12 и второго 13 табличных вычислителей, выход второго 4 мультиплексора соединен с входами второго 14 преобразователя кода числа X в код [X/к] и второго 15 преобразователя кода числа X в код X modк, выходы которых соединены со вторыми входами соответственно первого 12 и второго 13 табличных вычислителей, первый и второй выходы которого соединены с первыми входами соответственно третьего 16 и четвертого 17 табличных вычислителей, вторые входы которых соединены соответственно с выходами первого 18 и второго 19 блоков умножения на константу по модулю, входы которых соединены соответственно с первым и вторым выходами первого 12 табличного вычислителя, выход третьего 16 табличного вычислителя соединен с входом первого 20 квадратора по модулю и вторым входом первого 6 блока элементов И, выход которого является выходом 21 сложения устройства, выход четвертого 17 табличного вычислителя соединен с входами второго 22 квадратора по модулю, блока 23 деления на четыре по модулю и вторым входом второго 7 блока элементов И, выход которого является выходом 24 вычитания устройства, выходы первого 20 и второго 22 квадраторов по модулю соединены с входами соответственно первого 25 и второго 26 шифраторов, выходы которых соединены с входами соответственно первого 27 и второго 28 регистров, выходы которых соединены со вторыми информационными входами соответственно первого 3 и второго 4 мультиплексоров, выход блока 23 деления на четыре по модулю соединен со вторым входом третьего 9 блока элементов И, выход которого является выходом 29 умножения устройства.

Работу устройства удобно рассматривать в двух режимах.

1. Режим определения результата операций модульного сложения и вычитания.

2. Режим определения результата операции модульного умножения.

В первом режиме на первый 5 и второй 8 управляющие входы первого 3 и второго 4 мультиплексоров соответственно поступают коды 0 и 1, открывающие первые информационные входы первого 3 и второго 4 мультиплексоров. Операнд A в двоичном коде с входа 1 поступает на первый информационный вход первого мультиплексора 3, с A-го выхода которого одновременно поступает на вход первого преобразователя 10 кода числа A в A' = [A/к] и на вход первого преобразователя 11 кода числа A в Δ_A= A mod к. Операнд B в двоичном коде с входа 2 поступает на первый информационный вход второго мультиплексора 4, с B-го выхода которого одновременно поступает на вход второго преобразователя 14 кода числа B в B' = [B/к] и на вход второго преобразователя 15 кода числа B в Δ_B= B mod к. С выходов первого 10 и второго 14 преобразователей кода числа операнды, преобразованные в коды чисел A' и B', в унитарном коде поступают [A/к] -й и второй [B/к]-й входы первого табличного вычислителя 12, где реализуются операции сложения (A'+ B') mod m и вычитания (A'- B') mod m. Одновременно с выходов первого 11 и второго 15 преобразователей кода числа, операнды, преобразованные в коды чисел Δ_A и Δ_B в унитарном коде поступают соответственно на первый A mod к-й и второй B mod к-й входы второго табличного вычислителя 13, где реализуются операции сложения (Δ_A+Δ_B) mod m и вычитания (Δ_A-Δ_B) mod m. С первого выхода первого табличного вычислителя 12 результат операции сложения (A' + B') mod m и одновременно со второго выхода первого табличного вычислителя 12 результат операции вычитания (A' - B') mod m соответственно через первый 18 и второй 19 блоки умножения на константу поступают на первый к·(A' + B')-й вход третьего 16 и на первый к·(A' - B')-й вход четвертого 17 табличных вычислителей. С первого выхода второго табличного вычислителя 13 результат операции (Δ_A+Δ_B) mod m и одновременно со второго выхода второго табличного вычислителя 13 результат операции (Δ_A-Δ_B) mod m поступают соответственно на вторые входы третьего 16 и четвертого 17 табличных вычислителей.

С выходов третьего 16 и четвертого 17 табличных вычислителей соответственно результаты операции модульного сложения (A + B) mod m и операции модульного вычитания (A - B) mod m через соответствующие элементы первого 6 и второго 7 блоков элементов И поступают на выходы сложения устройства 21 и вычитания устройства 24.

Результаты операций (A + B) mod m и (A - B) mod m соответственно через первый 20 и второй 22 квадраторы по модулю устройства, преобразованные в числа (A + B)² mod m и (A - B)² mod m, поступают соответственно на входы первого 25 и второго 26 шифраторов, с выходов которых в двоичном коде заносятся соответственно в первый 27 и второй 28 регистры.

Во втором режиме на первый 5 и второй 8 управляющие входы первого 3 и второго 4 мультиплексоров соответственно поступают коды 1 и 0, открывающие вторые информационные входы первого 3 и второго 4 мультиплексоров. С выходов первого 27 и второго 28 регистров операнды D = (A + B)² mod m и F = (A - B)² mod m в двоичном коде поступают соответственно на вторые информационные входы первого 3 и второго 4 мультиплексоров. Аналогично работе устройства в первом режиме числа D и F поступают соответственно на входы первого 10 и второго 14 преобразователей кода числа D в D' и числа F в F', а также на входы первого 11 и второго 15 преобразователей кода числа D в Δ_D и числа F в Δ_F. С выходов первого 10 и второго 14 преобразователей кода числа, преобразованные числа D' и F', в унитарном коде поступают на D'-й и F'-й входы первого табличного вычислителя 12, где реализуется операция вычитания (D' - F') mod m. Одновременно с выходов первого 11 и второго 15 преобразователей кода числа преобразованные числа Δ_D и Δ_F, в унитарном коде поступают на Δ_D-й и Δ_F-й входы второго табличного вычислителя 13, где реализуется операция вычитания (Δ_D-Δ_F) mod m. Со второго выхода первого табличного вычислителя 12 результат операции вычитания (D' - F') mod m через блок 19 умножения на константу поступает на первый к· (D' - F')-й вход четвертого 17 табличного вычислителя, на второй (Δ_D-Δ_F)-й вход которого поступает результат операции вычитания (Δ_D-Δ_F) mod m со второго выхода второго табличного вычислителя 13. Результат операции модульного вычитания (D - F) mod m с выхода четвертого табличного вычислителя 17, преобразованный в блоке 23 деления на четыре в значение [(D - F)/4] mod m = (A·B) mod m, поступает через открытый третий блок 9 элементов И на выход 29 умножения устройства.

Рассмотрим примеры конкретного выполнения операций при m = 61, к = 8.

Пусть необходимо определить результаты модульного сложения, вычитания и умножения для A = 15, B = 30 (A, B - операнды). В первом режиме работы устройства операнды A и B в двоичном коде поступают соответственно на первые информационные входы первого 3 и второго 4 мультиплексоров, на первый 5 и второй 8 управляющие входы которых соответственно поступают коды 0 и 1, открывающие первые информационные входы первого 3 и второго 4 мультиплексоров. С выхода первого мультиплексора 3 операнд A = 15 поступает на входы первого 10 и первого 11 преобразователей кода числа. С выхода первых преобразователей 10, 11 кода числа операнд A = 15, преобразованный соответственно в числа A' = [15/8] = 1 и Δ_A = 15 mod 8 = 7, в унитарном коде поступает на первые входы соответственно первого 12 и второго 13 вычислителей. С выхода второго мультиплексора 4 операнд B = 30 поступает на входы второго 14 и второго 15 преобразователей кода числа. С выхода вторых преобразователей 14, 15 кода числа операнд B = 30, преобразованный соответственно в числа B' = [30/8] = 3 и Δ_B = 30 mod 8 = 6, в унитарном коде поступает соответственно на вторые входы первого 12 и второго 13 табличных вычислителей. В соответствии с таблицей 1 на первом выходе первого табличного вычислителя 12 будет число (A' + B') mod m = (1 + 3) mod 61 = 4. На втором выходе первого табличного вычислителя 12 будет число (A' - B') mod m = (1 - 3) mod 61 = 59 (см. таблицу 3). В соответствии с таблицей 2 на первом выходе второго табличного вычислителя 13 будет число (Δ_A+Δ_B) mod m = (7+6) mod 61 = 13, на втором выходе которого будет число (Δ_A+Δ_B) mod m = (7-6)mod 8 = 1 (см. таблицу 4). Число 4 с первого выхода первого табличного вычислителя 12 поступает на вход первого блока 18 умножения на константу к = 8 по модулю, в котором преобразуется в число (4·8) mod 61 = 32. Число 32 с выхода первого блока 18 умножения на константу по модулю поступает на первый вход третьего табличного вычислителя 16, на второй вход которого поступает число 13 с первого выхода второго табличного вычислителя 13. В соответствии с таблицей 5 на выходе третьего табличного вычислителя 16 будет число 45. Число 45 через открытый первый блок 6 элементов И поступает на выход 21 сложения устройства. Число 59 со второго выхода первого табличного вычислителя 12 поступает на вход второго блока 19 умножения на константу к = 8 по модулю, в котором преобразуется в число (59·8) mod 61 = 45. Число 45 второго блока 19 умножения на константу по модулю поступает на первый вход четвертого табличного вычислителя 17, на второй вход которого поступает число 1 со второго выхода второго табличного вычислителя 13. В соответствии с таблицей 6 на выходе четвертого табличного вычислителя 17 будет число 46. Число 46 через открытый второй блок 7 элементов И поступает на выход 24 вычитания устройства. Одновременно число 45 с выхода третьего табличного вычислителя 16 поступает на вход первого квадратора 20 по модулю устройства, в котором преобразуется в число 45² mod 61 = 12. Число 12 с выхода первого квадратора 20 по модулю устройства поступает на вход первого шифратора 25, преобразуется в двоичный код и заносится в первый 27 регистр. Аналогично число 46 с выхода четвертого табличного вычислителя 17 поступает на вход второго квадратора 22 по модулю устройства, в котором преобразуется в число 46² mod 61 = 42. Число 42 с выхода второго квадратора 22 по модулю устройства поступает на вход второго шифратора 26 преобразуется в двоичный код и заносится во второй 28 регистр.

Во втором режиме работы устройства на первый 5 и второй 8 управляющие входы первого 3 и второго 4 мультиплексоров соответственно поступают коды 1 и 0, открывающие вторые информационные входы первого 3 и второго 4 мультиплексоров. С выхода первого 27 регистра число (A + B) mod m = 45, поступает на второй информационный вход первого мультиплексора 3. С выхода первого мультиплексора 3 число 12 одновременно поступает на входы первого 10 и первого 11 преобразователей кода числа, c выходов которых преобразованное соответственно в числа [12/8] = 1 и 12 mod 8 = 4 в унитарном коде поступает на первые входы первого 12 и второго 13 табличных вычислителей. С выхода второго 28 регистра число (A - B) mod m = 42 поступает на второй информационный вход второго мультиплексора 4. C выхода второго мультиплексора 4 число 42 одновременно поступает на входы второго 14 и второго 15 преобразователей кода числа, c выходов которых преобразованное соответственно в числа [42/8] = 5 и 42 mod 8 = 2 в унитарном коде поступает на вторые входы первого 12 и второго 13 табличных вычислителей. В соответствии с таблицей 3 на втором выходе первого табличного вычислителя 12 будет число 57. B соответствии с таблицей 4 на втором выходе второго табличного вычислителя 13 будет число 2. Число 57 со второго выхода первого табличного вычислителя 12 поступает на вход второго блока 19 умножения на константу к = 8 по модулю, в котором преобразуется в число (57·8) mod 61 = 29. Число 29 с выхода второго блока 19 умножения на константу по модулю поступает на первый вход четвертого табличного вычислителя 17. Число 2 со второго выхода второго табличного вычислителя 13 поступает на второй вход четвертого табличного вычислителя 17. В соответствии с таблицей 6 на выходе четвертого табличного вычислителя 17 будет число 31, которое преобразуется в блоке 23 деления на четыре по модулю в число (31/4) mod m = (31·46) mod m = 23 и поступает через открытый третий блок 9 элементов И на выход 29 умножения устройства.

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

Арифметическое устройство по модулю, содержащее два шифратора, с первого по третий блоки элементов И, отличающееся тем, что в него введены первый и второй мультиплексоры, с первого по четвертый табличные вычислители, два регистра, два преобразователя кода числа Х в код [Х/к] (к - внутренний модуль устройства), два преобразователя кода числа Х в код Х modk, первый и второй блоки умножения на константу по модулю, два квадратора по модулю, блок деления на четыре по модулю, причем входы первого и второго операндов соединены с первыми информационными входами соответственно первого и второго мультиплексоров, первые адресные входы которых соединены с первым управляющим входом устройства и первыми входами первого и второго блоков элементов И, а вторые адресные входы - со вторым управляющим входом устройства и первым входом третьего блока элементов И, выход первого мультиплексора соединен с входами первого преобразователя кода числа Х в код [Х/к] и первого преобразователя кода числа Х в код Х modk, выходы которых соединены с первыми входами соответственно первого и второго табличных вычислителей, выход второго мультиплексора соединен с входами второго преобразователя кода числа Х в код [Х/к] и второго преобразователя кода числа Х в код Х modk, выходы которых соединены со вторыми входами соответственно первого и второго табличных вычислителей, первый и второй выходы которого соединены с первыми входами соответственно третьего и четвертого табличных вычислителей, вторые входы которых соединены соответственно с выходами первого и второго блоков умножения на константу по модулю, входы которых соединены соответственно с первым и вторым выходами первого табличного вычислителя, выход третьего табличного вычислителя соединен с входом первого квадратора по модулю и вторым входом первого блока элементов И, выход которого является выходом сложения устройства, выход четвертого табличного вычислителя соединен с входами второго квадратора по модулю, блока деления на четыре по модулю и вторым входом второго блока элементов И, выход которого является выходом вычитания устройства, выходы первого и второго квадраторов по модулю соединены со входами соответственно первого и второго шифраторов, выходы которых соединены со входами соответственно первого и второго регистров, выходы которых соединены со вторыми информационными входами соответственно первого и второго мультиплексоров, выход блока деления на четыре по модулю соединен со вторым входом третьего блока элементов И, выход которого является выходом умножения устройства.

РИСУНКИ

Рисунок 1, Рисунок 2, Рисунок 3, Рисунок 4