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

 

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

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

Известно устройство (аналог) (авт. св. СССР N 1617439, кл. G 06 F 7/72, Б.И. N 48, 1990), содержащее группу блоков умножения на константу по модулю, дешифратор, группу блоков элементов И и блок элементов ИЛИ.

Недостатком устройства является большое количество оборудования.

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

Недостатком данного устройства является большое количество оборудования.

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

Общее количество логических элементов И коммутатора составляет m²/8, где m - модуль операции, что обуславливает основной недостаток устройства.

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

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

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

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

Сущность изобретения состоит в использовании функционально законченной части полной арифметической таблицы для нахождения промежуточного результата модульной операции с последующей его коррекцией путем применения расширенного понятия индекса операнда. В прототипе используется деление арифметической таблицы на две части по вертикали и горизонтали, при этом индекс операнда γ_A(γ_B) имеет два значения 0 или 1 (A, B-операнды), в зависимости от того, в какой половине диапазона находится операнд. При делении таблицы на d частей . В этом случае A(B) = A(B)mod]m/d[+γ_A(γ_B)]m/d[, , где m - модуль операции, тогда, обозначив Δ = ]m/d[, , имеем (A+B)mod m = [(Aʹ+Bʹ)+(γ_A+γ_B)Δ]mod m, (1) , где Aʹ(Bʹ) = A(B)mod Δ. .

Обычно для реализации операции модульного вычитания используют соотношение (A - B)mod m = [A + (m - B)]mod m.

В данном случае будем использовать более экономичное, с точки зрения аппаратурных затрат, выражение ,
где
операции (m' - B') и (γ_A-γ_B) производятся соответственно блоком 17 определения дополнительного кода остатка и блоком 18 определения инверсии индекса операнда, которые технически представляют собой узлы перенумерации входных шин, ввиду того, что первый 2 и второй 9 блоки определения кода остатка, а также первый 3 и второй 10 определения индекса операнда представляют выходную информацию в унитарном коде.

Таким образом, операция модульного сложения согласно (1) распадается на три микрооперации. Величина (A' + B')mod m выполняется первым 4 табличным вычислителем, (γ_A+γ_B)Δ mod m - вторым 5 табличным вычислителем, а окончательный результат определяется при помощи выбора одного из блоков 21 сложения с константой по модулю. Операция модульного вычитания (3), как показано ранее, происходит с тем же быстродействием. Обычно получение окончательного результата модульной операции производится табличным методом, что требует при выборе использования еще одного табличного вычислителя с числом элементов ≈m. В предлагаемом устройстве требуется число логических элементов , что экономичней, особенно при больших по величине модулях.

При m = 11 и d = 3 для реализации первого 4 и второго 5 табличных вычислителей требуются две таблицы (табл. 1 и 2).

Первый 4 табличный вычислитель в этом случае имеет 7 выходов (в общем случае 2Δ-1 ), второй 5 табличный вычислитель - 5 выходов (для произвольного d будет 2d - 1). В случае проведения операции модульного сложения при γ_A= γ_B= 0 коррекция промежуточного результата не производится (используется нулевой блок элементов И 20 группы). Общее число блоков 21 сложения с константой по модулю составляет 2d - 2, которые целесообразно выполнить на программируемых логических матрицах в соответствии с табл. 3, где отражена функциональная зависимость их от величины (γ_A+γ_B) .

Блок 17 определения дополнительного кода остатка и блок 18 определения инверсии индекса операнда реализуются согласно табл. 4 и 5.

Число связей для реализации операции модульного вычитания согласно (2) составляет величину m, а в данном случае их число примерно равно (табл. 4 и 5), что также сказывается на увеличении надежности предлагаемого устройства.

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

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

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

Работу устройства удобно рассматривать в двух режимах: 1) режим проведения операции модульного сложения, 2) режим проведения операции модульного вычитания.

В первом режиме операнд A поступает в двоичном коде на вход первого блока 2 определения кода остатка, с выхода которого число AmodΔ в унитарном коде поступает на информационный вход первого 4 табличного вычислителя. Одновременно операнд A поступает на вход первого блока 3 определения индекса операнда, с выхода которого число γ_A в унитарном коде поступает на информационный вход второго 5 табличного вычислителя. Операнд B в двоичном коде поступает на вход второго блока 9 определения блока остатка, с выхода которого число BmodΔ в унитарном коде поступает через открытый второй блок 11 элементов И (сигнал на входе 13 задания сложения устройства присутствует) и далее через второй блок 6 элементов ИЛИ - на управляющий вход первого 4 табличного вычислителя. Одновременно операнд B поступает на вход второго блока 10 определения индекса операнда, с выхода которого число γ_B в унитарном коде через открытый четвертый блок 12 элементов И и далее через третий блок 7 элементов ИЛИ - на управляющий вход второго 5 табличного вычислителя. С выхода первого 4 табличного вычислителя поступает сигнал на (A' + B')-й вход шифратора 19, с выхода которого число (A' + B') в двоичном коде поступает на первые входы нулевого блока 20 элементов И группы и на входы блоков 21 сложения с константой по модулю. С выхода второго 5 табличного вычислителя сигнал поступает на вторые входы (γ_A+γ_B)-го блока 20 элементов И группы, и результата операции модульного сложения с выхода соответствующего блока 21 сложения с константой по модулю поступает через первый блок 22 элементов ИЛИ на выход 23 устройства. Отметим, что при γ_A = γ_B = 0 результат операции не корректируется.

Работа устройства во втором режиме отличается только тем, что число B' преобразуется в дополнительный код остатка, а индекс γ_B инвертируется. При этом, если γ_A = 0, а γ_B= d-1, , то результат модульной операции не корректируется.

Рассмотрим конкретные примеры выполнения модульных операций при m = 11, d = 3. При этом Δ = 4 .

Пример 1. Необходимо провести операцию (5 + 3)mod11. В этом случае A = 0101₂ поступает на вход первого блока 2 определения кода остатка, с выхода которого поступает сигнал на первый информационный вход первого 4 табличного вычислителя. Операнд A поступает на вход первого блока 3 определения индекса операнда, с выхода которого сигнал - на первый информационный вход второго 5 табличного вычислителя. Операнд B = 0011₂ поступает на вход второго блока 9 определения кода остатка, с выхода которого сигнал поступает через открытый второй блок 11 элементов И, далее через второй блок 6 элементов ИЛИ - на третий управляющий вход первого 4 табличного вычислителя. Операнд B одновременно поступает на вход второго блока 10 определения индекса операнда, с выхода которого сигнал поступает через открытый четвертый блок 12 элементов И, далее через третий 7 блок элементов ИЛИ - на нулевой управляющий вход второго 5 табличного вычислителя. С четвертого выхода первого 4 табличного вычислителя (табл. 1) сигнал поступает на четвертый вход шифратора 19, на выходе которого будет код 0100₂. С первого выхода второго 5 табличного вычислителя (табл. 2) сигнал поступает на вторые входы первого блока 20 элементов И группы, и с выхода первого блока 21 сложения с константой по модулю группы результат модульной операции 1000₂ (табл. 3) через первый блок 22 элементов ИЛИ поступает на выход 23 устройства.

Пример 2. Необходимо провести операцию (5 - 3)mod 11. В этом случае прохождение первого операнда A на информационные входы первого 4 и второго 5 табличных вычислителей аналогично первому примеру. Операнд B = 0101₂ поступает на вход второго блока 9 определения кода остатка, с выхода которого сигнал поступает на третий вход блока 17 определения дополнительного кода остатка, с нулевого выхода которого (табл. 4) сигнал проходит через открытый первый блок 14 элементов И и второй блок 6 элементов ИЛИ на нулевой управляющий вход первого 4 табличного вычислителя. Также операнд B поступает на вход второго блока 10 определения индекса операнда, с выхода которого сигнал поступает на нулевой вход блока 18 определения инверсии операнда, с второго выхода которого (табл. 5) сигнал проходит через открытый третий блок 15 элементов И и третий блок 7 элементов ИЛИ на второй управляющий вход второго 5 табличного вычислителя. С первого выхода первого 4 табличного вычислителя (табл. 1) сигнал поступает на первый вход шифратора 19, на выходе которого будет код 0001₂. С третьего выхода второго 5 табличного вычислителя (табл. 2) сигнал поступает на вторые входы третьего блока 20 элементов И группы, и результат модульной операции 0010₂ (табл. 3) с выхода третьего блока 21 сложения с константой по модулю группы через первый блок 22 элементов ИЛИ поступает на выход 23 устройства.

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

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

РИСУНКИ

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