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

 

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

сОюз сОВетских

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (я)5 G 06 F 7/49, 7/72

ГОСУДАРСТВЕН-ЮЕ ПАТЕНТНОЕ

ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) ВО .1 МЭЙДА

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

{21) 4904210/24 (22) 22.01.91 (46) 15.04.93. Бюл, N. 14 (72) В.А,Краснобаев, В.П.Ирхин, М,В,Квасов, И,В,Приходько и В.Д.Экста (56) Авторское свидетельство СССР

N. 1312572, кл. G 06 F 7/72, 1987.

Авторское свидетельство СССР

ЬЬ 1683012, кл. 6 06 F 7/72, 1989.

Авторское свидетельство СССР

М 1633400, кл. G 06 F 7/72, 1989, „„50 1809437 А1 (54) АРИФМЕТИЧЕСКОЕ УСТРОЙСТВО ПО

МОДУЛЮ (57) Изобретение относится к автоматике и вычислительной технике и может быть использовано в вычислительных машинах и устройствах, функционирующих в системе остаточных классов. Цель изобретения— расширение функциональных возможностей.операций сложения и вычитания. Арифметическое устройство по модулю содержит первый и второй информационнь е входы 1, 1809437

iA в = (!д+ ig)mod(m - 1) 12, преобразователь 2 модулярного кода в унитарный код индекса, шесть блоков элементов И 3, 9, 14, 15, 19, 21, тактовый вход

4, два элемента 5, 34, семь элементов И 6, 7, 16, 17, 28, 32, 33, кольцевой регистр 8 сдвига, преобразователь 10 унитарного кода в модулярный, выход 11, дешифратор 13, три

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

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

Операции модульного умножения и деления проводятся следующим образом. Согласно теории индексов! дув = (IA - I B)mod(m - 1), где m — модуль, IA в — индекс произведения числа А и В, ! дув — индекс частного от деления числа

А на число В, . ° IA, ie — соответственно индексы чисел А и В.

Из приведенной формулы вытекает возможность замены умножения чисел сложением их индексоа по модулю (m - 1), э деления чисел — вычитанием их индексов по модулю (m - 1), Для перехода от индексов к фактическому числу используются антииндекСы N(IA), N(ie), За счет использования унитарного кода числа А (после дешифратора 13) преобразование А IA сводится к соответствующей коммутации выходных шин дешифратора 13 нэ входах шестого блока 15 элементов И; а преобразователь 9 унитарного кода индекса 8 в модулярный реализуется соответствующей коммутацией входных шин.

Преобразователь 2 модулярного кода а код индекса предназначен для преобразования одного двоичного числа в другое и реализуется на базе элементов И и ИЛИ, например для модуля m = 7 согласно табл.1.

Таблица 1

А(В) 0 1 2 3 4 5 6

IA(le) — 0 4 5 2 1 3

5 блока элементов ИЛИ 18, 20, 22, вычитающий счетчик 23, элемент ИЛИ-НЕ 24, вход

25 задания сложения, вход 26 задания вычитания, два элемента ИЛИ 27. 31, вход 29 задания умножения, вход 30 задания деления и установочный вход 35, соединенные между собой функционально, 1 ил.

Исходя из приведенных рассуждений, необходимо обеспечить всего две операции (сложение и вычитание по модулю), но для проведения умножения и деления по моду5 лю эти операции нужно реализовать их с модулем (m - 1). Это производится путем, введения третьего 33 элемента И и второго

34 элемента запрета, которые реализованы при помощи логики КМОП и позволяют про10 водить двунаправленную передачу (как с . входа на выход, тэк и с выхода на вход.

Устройство работает по следующему алгоритму;

1) операция сложения (вычитания) про15 изводится обычным путем с помощью кольцевого 8 регистра сдвига, при сложении производится запись операнда А в унитарном коде в KCP 8 и затем сдвиг содержимого вправо на В разрядов (при вычитании вле20 во).

2) операция умножения (деления) производится так; а) с помощью преобразователя 2 вычисляется индекс второго операнда В;

25 б) производится сложение (вычитание) индексов по модулю (m-1); в) индекс результата преобразуется из унитарного кода в модулярный путем соответствующей коммутации шин на входах

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

Возможность достижения положитель35 ного эффекта от использования данного изобретения состоит а расширении функциональных возможностей за счет выполнения дополнительно операций модульного сложения и вычитания, 40 На чертеже.представлена структурная схема устройства, где 1 — второй информационный вход устройства, 2 — преобразователь модулярного кода устройства в унитарный код индекса, 3 — первый блок

45 элементов И, 4 — тактовый вход устройства, 5 — первый элемент запрета, 6 — первый элемент И,? — второй элемент И„8 — кольцевой регистр сдвига, 9 — второй блок элементов И, 10 — преобразователь унитарного

1 8094:37 элементов ИЛИ, 21 — четвертый блок элементов И, 22 — первый блок элементов ИЛИ, ГЗ вЂ” вычитающий счетчик, 24 — элемент

ИЛИ-НЕ, 25 — вход задания сложения устройства, 26 — вход задания вычитания устройства, 27 — первый элемент ИЛИ, 28— седьмой элемент И, 29 — вход задания умножения устройства, 30 — вход задания деления устройства, 31 — второй элемент ИЛИ, 32 — шестой элемент И, 33 — третий элемент

И, 34 — второй элемент запрета, 35 — установочный вход устройства, Второй 1 информационный вход устройства соединен с входом преобразователя 2 модулярного кода в унитарный код индекса, выход которого соединен с первыми входами элементов И первого 3 блока, тактовый вход 4 устройства соединен с информационным входом первого 5 элемента запрета, выход которого соединен с информационным входом первого 5 элемента запрета,,выход которого соединен с первыми входами первого 6 и второго 7 элементов И, выходы которых соединены соответственно с входами сдвига вправо и влево кольцевого регистра 8 сдвига, разрядные выходы которого соединены с первыми входами элементов

И второго 9 блока, а выход преобразователя

10 унитарного кода в модулярный соединен с выходом 11 устройства, первый 12 информационный вход устройства соединен с (logjam) — разрядным входом дешифратора

13 (m — значения модуля) m — разрядный выход которого соединен соответственно с первыми входами элементов И пятого 14 и шестого 15 блоков, вторые входы элементов

И пятого 14 блока соединены с выходом четвертого 16 элемента И, вторые входы элементов И шестого 15 блока соединены с выходом пятого 17 элемента И, входы элементов И пятого 14 блока соединены соответственно.с первыми входами элементов

ИЛИ второго 18 блока, вторые входы которых соединены соответственно с выходами элементов И шестого 15 блока, а выходы элементов ИЛИ второго 18 блока соединены соответственно с m информационными входами кольцевого регистра 8 сдвига, разрядные выходы которого с первого по (m - 1)-й соединены соответственно с первыми входами элементов И третьего 19 блока, выходы которых соединены соответственно с первыми входами элементов ИЛИ третьего

55 кода в модулярный, 11 выход устройства, 12 - flppRblA информационный вход устройства. 13 — дешифратор, 14 — пятый блок элементов И, 15 — шестой блок элементов И, 16 — четвертый элемент И, 17 -- пятый эле-. 5 мент И, 18 — второй блок элементов ИЛИ, 19 — третий блок элементов И, 20 — третий блок

20 блока, вторые входы которых соединены соответственно с выходами элементов И второго 9 блока, выходы элементов ИЛИ третьего 20 блока соединены с входом преобразователя унитарного кода 10 в модулярный, второй 1 информационный вход устройства соединен с первыми входами элементов И четвертого 21 блока, выходы которых соединены соответственно с первыми входами элементов ИЛИ первого 22 блока, вторые входы которых соединены соответственно с выходами элементов И первого блока, выходы элементов ИЛИ первого

22 блока соединены с установочными входами вычитающего счетчика 23, разрядные выходы которого соединены с входами элемента ИЛИ-НЕ 24, ьыход которого соединен с управляющим входом первого 5 элемента запрета, выход которого соединен со счетным входом вычитающего 23 счетчика, входы задания сложения 25 и вычитания

26 устройства соединены с входами первого

27 элемента ИЛИ, выход которого соединен с первым входом четвертого 16 элемента И, вторыми входами элементов И четвертого

21 блока и первым входом седьмого 28 элемента И, выход которого соединен со вторыми входами элементов И второго 9 блока, входы задания. умножения 29 и деления 30 устройства соединены с входами второго 31 элемента ИЛИ, выход которого соединен с первым входом пятого 17 элемента И, вторыми входами элементов И первого 3 блока и с первым входом шестого 32 элемента И, выход которого соединен со вторыми входами элементов И третьего 19 блока, вход сдвига вправо кольцевого регистра 8 сдвига соединен с выходом второго 7 элемента И, с первым входом третьего 33 элемента И, выход которого соединен с входом (m — 1)-го разряда кольцевого регистра 8 сдвига и с выходом второго 34 элемента запрета, информационный вход которого соединен с выходом m-го разряда кольцевого регистра

8 сдвига, управляющий вход второго 34 элемента запрета соединен со вторым входом третьего 33 элемента И и с выходом второго

31 элемента ИЛИ выход элемента ИЛИ-НЕ

24 соединен со вторым входом шестого 32 и седьмого 28 элементов И, входы задания сложения 25 и умножения 29 соединены со вторым входом первого 6 элемента И, входы задания вычитания 26 и деления 30 соединены со вторым входом второго 7 элемента

И, установочный вход 35 устройства соединен со вторыми входами четвертою 16 и пятого 17 элементов И и с входом разрешения записи кольцевого регистра 8 сдвига, Рассмотрим, работу устройства. Кольцевой регистр 8 сдвига (KCP) содержит m дво1809437

10

15 мах

25

35

50

0-0-1-0-0-0-0 ичных разрядов (Π— (m - 1)), m — значение модуля. Исходное состояние КСР8 — нули во всех разрядах. Сигнал на выходе элемента

ИЛИ-НЕ 24 появляется в том случае, когда на всех выходах счетчика 23 будут нули, Одиночный импульс, поступающий со входа

35 обеспечивает запись единицы в А-ом разряде (А = 0 — m - 1) КСР8. Для упрощения схемы особенности двунаправленной передачи во втором 34 элементе запрета и в третьем 33 элементе И в зависимости от вида сдвига (вправо или влево) разрядов

КСР8 на схеме не показаны. Работу устройства удобно рассмотреть в четырех режи1) режим модульного сложения, В этом случае операнд А в двоичном коде поступает на вход дешифратора 13. При поступлении импульса по входу 35 в А-ом разряде

КСР8 будет записана единица, т.к. присутствует сигнал на шине 25 и следовательно открыты элементы И пятого 14 блока элементов И. Операнд В в двоичном коде поступает через четвертый 21 блок элементов

И, первый 22 блок элементов ИЛИ, В счетМике 23 устанавливается операнд В в двоич- ном коде, С тактового в хода 4 поступает через открытый первый 5 элемент запрета на вход счетчика 23, а также на вход сдвига вправо содержимого КСРВ через открытый элемент И 6 (присутствует сигнал на входе 25).

В данном случае сигнала на управляющий вход второго 34 элемента запрета и второй вход третьего 33 элемента И не поступает, поэтому кольцевой регистр 8 сдвига обеспечивает сдвиг разрядов с циклом, равным m через элемент запрета 34. Производится продвижение единицы, записанной в КСР на В двоичных разрядов вправо. Когда содержимое счетчика 23 станет равно нулю, то сигнал с выхода ИЛИ-HE 24 закрывает элемент 5 запрета, запрещая прохождение импульсов на сдвиг двоичных разрядов КСР8 и одновременно этот сигнал поступает на второй вход седьмого 28 элемента И, с выхода которого сигнал поступает на второй вход второго 9 блока элементов И, обеспечивая прохождение результата операции модульного сложения, полученного в унитарном коде через третий 20 блок элементов

ИЛИ-на вход преобразователя 10 унитарного кода в модульный. С выхода преобразователя 10 унитарного кода в модулярный результат операции в двоичном коде поступает на.11 устройство.

2) режим модульного вычитания. Работа устройства при выполнении операции модульного вычитания (А - B)modm отличается от модульного сложения только тем, что присутствует сигнал на входе 26, поэтому. производится сдвиг разрядов КСР8 на В двоичных разрядов влево.

3) режим модульного умножения. В этом случае на управляющий вход второго 34 элемента запрета и на второй вход третьего 33 элемента И поступает сигнал. В данном случае КСР8 представляет цепь из (m - 1) двоичных разрядов, т.е, его цикл равен (m -.1), Следовательно производится работа по модулю (m - 1), Операнд А поступает на вход дешифратора 13, выходы которого скоммутированы на входах шестого 15 блока элементов И в соответствии с индексами операнда А и с выходов шестого 15 блока элементов И (сигнал на выходе пятого 17 элемента И присутствует) через второй 18 блок элемента ИЛИ поступает на запись единицы (аналогИчно случаю модельного сложения s iA-ом разряде кольцевого 8 регистра сдвига. Операнд В поступает в двоичном коде на вход преобразователя 2 . модулярного кода в код индекса, В счетчике

23 устанавливается значение !в в двоичном коде (сигнал на втором входе первого 3 блока элементов И присутствует). Дальнейший процесс до завершения сдвига разрядов КСР8 происходит аналогично операции модульного сложения, но затем результат(!А+ !п) в унитарном коде поступает на соответствующий значению антииндекса (iA+ щ) вход третьего

19 блока элементов И через третий 20 блок элементов ИЛИ, преобразователь 10 унитарного кода в модулярный значение результата операции (А х B)modm поступает на вход 11 устройства.

4) режим модульного деления. Работа устройства при выполнении модульного давления (A/B)modm отличается от модульного умножения только тем, что присутствует сигнал на входе 30, поэтому производится сдвиг разрядов КСР8 íà !ц двоичных разрядов влево.

Рассмо.трим примеры конкретного выполнения модульных операций для модуля m = 7.

Пример 1. Необходимо определить результат операции модульного сложения для А = 2, В = 3. (А и  — операнды).

Первый операнд А = 010 поступает на вход дешифратора 13 и после импульса со входа 35 во втором разряде КСР8 будет записана 1 (остальные разряды КСР8 — нули). Второй операнд В = 011 устанавливается в содержимом вычитающего счетчика 23. Следовательно содержимое КСР8 представлено в виде

Со входа 4 через элемент 5 поступает три импульса (В = 3), которые продвигают

1809437

0-0-0-0-0-1-0

0-1-0-0-0-0

0-0-0-0-0-1

0-0-0-0-0-0-1

1-0-0-0-0-0

0-1-0-0-0-0

0-0-0-1-0-0

0-0-0-0-0-1 единицу в. КСР8 на три двоичных разряда вправо и уменьшают содержимое вычитающего счетчика до нуля. С выхода ИЛИ-НЕ 24 поступает сигнал, который закрывает элемент 5 и открывает второй 9 блок элементов 5

И. Содержимое КСР8 следующее

Следовательно, результат операции ра- 10 вен 5.

f(2 + 3)mod7 = 5). Этот результат поступает через блок элементов ИЛИ 20 на вход преобразователя 10 унитарного кода в модулярный, с выхода которого значение 101 15 поступает на выход 11 устройства.

Пример 2. Пусть необходимо определить результат операции модульного вычитания для А = 2, B = 3 (А и. — операнды).

В этом случае все будет происходить 20 аналогично первому примеру, за исключением того, что сдвиг содержимого КСР8 (единицы в А-м двоичном разряде будет производиться влево, Содержимое КСР8 по . завершении сдвига следующее . 25

Это соответствует результату вычитания, равному 6 в унитарном коде. ((2 - 3)mod 30

T = 6), Результат поступает на вход преобразователя 10 унитарного кода в модулярный, с выхода которого значение 110 поступает на выход 11 устройства.

Пример 3. Определить А B(mod 7) при 35

А = 3, B =4 (А и  — операнды).

В данном случае сигнал присутствует на втором входе И 33 и управляющем входе элемента 34 запрета, следовательно образуется цепь КСР8 из 6 двоичных разрядов. 40

Первый операнд А = 011 поступает на вход дешифратора 13 на выходах которого он будет представлен в следующем унитарном коде

Выходные шины дешифратора 13 скоммутированы на входах шестого 15 блока элементов И согласно таблицы 1, сле- 50 довательно на его выходах имеем унитарный код IA в виде

Следовательно такой вид будет на разрядах КСР8. Второй операнд В поступает на вход преобразователя 2 модуля рного кода в код индекса, на выходе, которого имеем 010 (см. таблицу 1), Это значение устанавливается в счетчике 23. Со входа 4 через элемент

5 поступают два импульса (ig = 2), которые продвигают единицу в КСР8 на два двоичных разрядов вправо и уменьшают содержимое вычитающего 23 счетчика до нуля. С выхода ИЛИ-НЕ 24 поступает сигнал, который закрывает элемент 5 и открывает третий 9 блок элементов И, Содержимое КСР8 следующее

Оно соответствует значению (iA + !в) в унитарном коде. Выходы КСР8 скоммутиро-. ваны на входах третьего 19 блока элементов

И таким образом, что на выходах его мы имеем значение антииндекса в унитарном коде, т.е. имеем

Это соответствует результату операции равному 5 в унитарном коде (3. х 4 mod 7 =5

mod 7). Этот результат через блок элементов

ИЛИ 20 поступает на вход преобразователя

10 унитарного кода в модулярный, с выхода которого значение 101 поступает на выход

11 устройства.

Пример4. Определить А/B(mod 7) при

А = 3, В = 4. (А и B — операнды).

В этом случае все будет происходить аналогично третьему примеру, за исключением того, что сдвиг содержимого KCPS (единицы, в iA-м двоичном разряде будет происходить на 1ц двоичных разрядов влево.

Содержимое КСР8 по завершении сдвига следующее

На выходах третьего 19 блока элементов И имеем

Это соответствует результату операции, равному 1 в унитарном коде (3!4 mod 7 = 1

mod 7). Этот результат через блок элементов

ИЛИ 20 поступает на вход преобразователя

10 унитарного кода в модулярный, с выхода которого значение результата операции 001 поступает на выход 11 устройства.

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

25

35

45

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

Достоверность достижения поставленная цели подтверждается конкретными примерами выполнения всех модульных операций для m = 7, Формула изобретения

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

ИЛИ-НЕ, первый элемент запрета, первый и второй информационные входы, информационный выход, входы задания умножения и деления и тактовый вход, причем второй информационный вход устройства соединен с входом преобразователя модулярного кода в унитарный код индекса, выход которого соединен с первыми входами элементов И первого блока. тактовый вход устройства соединен с информационным входом первого элемента запрета, выход которого соединен с первыми входами первого и второго элементов И, выходы которых соединены соответственно с входами сдвига вправо и влево кольцевого регистра сдвига, разрядные выходы которого соединены соответственно с первыми входами элементов И второго блока, а выход преобразователя унитарного кода в модулярный соединен с выходом устройства, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей путем выполнения операций сложения и вычитания, в него введены дешифратор, четвертый, пятый и шестой блоки элементов И, второй и третий блоки элементов ИЛИ, второй элемент запрета, входы задания сложения и вычитания и установочный вход, причем первый информационный вход устройства соединен с (! осргп)-разрядным входом дешифратора (m — значение модуля), m — разрядный выход которого соединен соответственно с первыми входами элементов.И пятого и шестого блоков, вторые входы элементов И пятого блока соединены с выходом четвертого элемента И, вторые входы элементов И шестого блбка соединены с выходом пятого элемента И, выходы элемснтов И пятого блока соединены соответственно с первыми входами элементов ИЛИ второго блока, втоФ рые входы которых соединены соответственно с выходами элементов И шестого блока, а выходы элементов ИЛИ второго блока соединены соответственно с m информационными входами кольцевого регистра сдвига, разрядные выходы которого с первого по (m - 1)-ый соединены соответственно с первыми входами элементов И третьего блока, выходы которых соединены соответственно с первыми входами элементов ИЛИ третьего блока, вторые входы которых соединены соответственно с выходами элементов И второго блока, выходы элементов ИЛИ третьего блока соединены с входом преобразователя унитарного кода в модулярный, второй информационный вход устройства соединен с первыми входами элементов И. четвертого блока, выходы которых соединены соответственно с первыми входами.элементов ИЛИ первого блока, вторые входы которых соединены соответственно с выходами элементов И первого блока, выходы элементов ИЛИ первого блока соединены с установочными входами вычитающего счетчика, разрядные выходы которого соединены с входами элемента ИЛИ-НЕ, выход которого соединен с управляющим входом первого элемента запрета, выход которого соединен со счетным входом вычитающего счетчика, входы задания сложения и вычитания устройства соединены с входами первого элемента ИЛИ, выход которого соединен с первым входом четвертого элемента И, вторыми входами элементов И четвертого блока и первым входом седьмого элемента И, выход которого соединен с вторыми входами элементов И второго блока, входы задания умножения и деления устройства соединены с входами второго элемента ИЛИ, выход которого соединен с первым входом пятого элемента И, вторыми входами элементов И первого блока и с первым входом шестого элемента И, выход которого соединен со вторыми входами элементов И третьего блока, вход сдвига вправо кольцевого регистра сдвига соединен.с выходом второго элемента И, а первым входом третьего элемента И, выход которого соединен с входом (m - 1)-го разряда кольцевого регистра сдвига и с выходом второго элемента запрета, информационный вход которого соединен с выходом m-ro разряда кольцевого регистра сдвига, управляющий вход второго элемента запрета соединен со вторым входом третьего элемента

И и выходом второго элемента ИЛИ, выход элемента ИЛИ-НЕ соединен со вторыми входами шестого и седьмого элементов И, входы задания сложения и умножения соединены с вторым входом первого элемента

1809437

Составитель В, Краснобаев

Техред М.Моргентал Корректор Е. Папп

Редактор

Заказ 1286 Тираж Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., 4/5

Производственно-издательский комбинат "Патент", r. Óæãîðoä, ул.Гагарина, 101

И, входы задания вычитания и деления соединены со вторым входом второго элемента

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