Арифметическое устройство по модулю Советский патент 1993 года по МПК G06F7/49 G06F7/72 

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

блока элементов ИЛИ 18, 20, 22, вычитающий счетчик 23, элемент ИЛИ-НЕ 24, вход 25 задания сложения, вход 26 задания вычитания, два элемента ИЛИ 27. 31, вход 29 задания умножения, вход 30 задания деления и установочный вход 35, соединенные между собой функционально, Т ил.

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

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

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

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

Операции модульного умножения и деления проводятся следующим образом. Со- гласно теории индексов

IA в ОА + iB)mod(m - 1),

lA/B (iA-lB)mod(m- 1)1 где m - модуль, 1д в - индекс произведения числа А и В, .

IA/B - индекс ча.стного от деления числа А на число В,

IA, 1в соответственно индексы чи- сел А и В.

Из приведенной формулы вытекает возможность замены умножения чисел сложением их индексов по модулю (т - 1), а деления чисел - вычитанием их индексов по модулю (т - 1). Для перехода от индексов к фактическому числу используются антииндексы N(JA), N(JB).

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

Таблица

А(В) 0123456 . |А(1В) -0452-13

0

5

0

5

0

5 0 5

б

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

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

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

2) операция умножения (деления) производится так:

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

б) производится сложение (вычитание) индексов по модулю (т-1);

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

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

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

кода в модулярный. 11 выход устройства, 12 - первый информационный вход устройства, 13 - дешифратор. 14 - пятый блок элементов И, 15 - шестой блок элементов И,

. .

16 - четвертый элемент И, 17 - пятый эле-- мент И, 18 - второй блок элементов ИЛИ, 19 - третий блок элементов И, 20 - третий блок элементов ИЛИ, 21 - четвертый блок элементов И, 22 - первый блок элементов ИЛМ, 23 - вычитающий счетчик. 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 информационный вход устройства соединен с (1од2гп) - разрядным входом дешифратора 13 (т - значения модуля) т - разрядный выход которого соединен соответственно с первыми входами элементов И пятого 14 и шестого 15 блоков, вторые входы элементов И пятого. 14 блока соединены с выходом четвертого 16 элемента И, вторые входы элементов И шестого 15 блока соединены с выходом пятого 17 элемента И, входы элементов И пятого 14 блока соединены соответственно-с первыми входами элементов ИЛИ второго 18 блока, вторые входы которых соединены соответственно с выходами элементов И шестого 15 блока, а выходы элементов ИЛИ второго 18 блока соединены соответственно с m информационными входами кольцевого регистра 8 сдвига, разрядные выходы которого с первого по (т - 1)-й соединены соответственно с первыми входами элементов И третьего 19 блока, выходы которых соединены соответственно с первыми входами элементов ИЛИ третьего

20 блока, вторые входы которых соединены соответственно с выходами элементов И второго 9 блока, выходы элементов ИЛИ третьего 20 блока соединены с входом

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

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

0 со счетным входом вычитающего123 счетчика, входы задания сложения 25 и вычитания

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

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

5 вторыми входами элементов И четвертого 21 блока и первым входом седьмого 28 элемента И, выход которого соединен со вторыми входами элементов И второго 9 блока, входы задания, умножения 29 и деления 30

0 устройства соединены с входами второго 31 элемент ИЛИ, выход которого соединен с первым входом пятого 17 элемента И, вторыми входами элементов И первого 3 блока и с первым входом шестого 32 элемента И,

5 выход которого соединен со вторыми входами элементов И третьего 19 блока, вход сдвига вправо кольцевого регистра 8 сдвига соединен с выходом второго 7 элемента И, с первым входом третьего 33 элемента И,

0 выход которого соединен с входом (т - 1)-го разряда кольцевого регистра 8 сдвига и с выходом второго 34 элемента запрета, информационный вход которого соединен с выходом т-го разряда кольцевого регистра

5 8 сдвига, управляющий вход второго 34 элемента запрета соединен со вторым входом третьего 33 элемента И и с выходом второго 31 элемента ИЛИ выход элемента ИЛИ-НЕ 24 соединен со вторым входом шестого 32 и

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

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

Рассмотрим, работу устройства. Кольцевой регистр 8 сдвига (КСР) содержит m двоичных разрядов (0 - (т - 1)), т - значение модуля. Исходное состояние КСР8 - нули во всех разрядах. Сигнал на выходе элемента ИЛИ-НЕ 24 появляется в том случае, когда на всех выходах счетчика 23 будут нули, Одиночный импульс, поступающий со входа 35 обеспечивает запись единицы в А-ом разряде (А 0 - m - 1) КСР8. Для упрощения схемы особенности двунаправленной передачи во втором 34 элементе запрета и в третьем 33 элементе И в зависимости от вида сдвига (вправо или влево) разрядов КСР8 на схеме не показаны. Работу устройства удобно рассмотреть в четырех режимах:

1) режим модульного сложения, В этом случае операнд А в двоичном коде поступа- ет на вход дешифратора 13. При поступлении импульса по входу 35 в А-ом разряде КСР8 будет записана единица, т.к. присут- ствует сигнал на шине 25 и следовательно открыты элементы И пятого 14 блока элементов И. Операнд В в двоичном коде поступает через четвертый 21 блок элементов И, первый 22 блок элементов ИЛИ. В счет- чике 23 устанавливается операнд В в двоичном коде. С тактового в хода 4 поступает через открытый первый 5 элемент запрета на вход счетчика 23, а также на вход сдвига вправо содержимого КСР8 через открытый элемент И 6 (присутствует сигнал на входе 25). В данном случае сигнала на управляющий вход второго 34 элемента запрета и второй вход третьего 33 элемента И не поступает, поэтому кольцевой регистр 8 сдвига обеспе- чивает сдвиг разрядов с циклом, равным m через элемент запрета 34. Производится продвижение единицы, записанной в КСР на В двоичных разрядов вправо. Когда содержимое счетчика 23 станет равно нулю, то сигнал с выхода ИЛИ-НЕ 24 закрывает элемент 5 запрета, запрещая прохождение импульсов на сдвиг двоичных разрядов КСР8 и одновременно этот сигнал поступает на второй вход седьмого 28 элемента И, с вы- хода которого сигнал поступает на второй вход второго 9 блока элементов И, обеспечивая прохождение результата операции модульного сложения, полученного в унитарном коде через третий 20 блок элементов ИЛИ-на вход преобразователя Юунитарно- го кода в модульный. С выхода преобразователя 10 унитарного кода в модулярный результат операции в двоичном коде поступает на-11 устройство.

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

производится сдвиг разрядов КСР8 на В двоичных разрядов влево.

3) режим модульного умножения. В этом случае на управляющий вход второго 34 элемента запрета и на второй вход третьего 33 элемента И поступает сигнал. В данном случае КСР8 представляет цепь из (т -1) двоичных разрядов, т.е. его цикл равен (т - 1). Следовательно производится работа по модулю (т - 1), Операнд А поступает на вход дешифратора 13, выходы которого скомму- тированы на входах шестого 15 блока элементов И в соответствии с индексами операнда А и с выходов шестого 15 блока элементов И (сигнал на выходе пятого 17 элемента И присутствует) через второй 18 блок элемента ИЛИ поступает на запись единицы (аналогично случаю модельного сложения в IA-OM разряде кольцевого 8 регистра сдвига. Операнд В поступает в двоичном коде на вход преобразователя 2 модулярного кода в код индекса. В счетчике 23 устанавливается значение IB в двоичном коде (сигнал на втором входе первого 3 блока элементов И присутствует). Дальнейший процесс до завершения сдвига разрядов КСР8 происходит аналогично операции модульного сложения, но затем результат(1д + IB) в унитарном коде поступает на соответствующий значению антииндекса ()А + IB) вход третьего 19 блока элементов И через третий 20 блок элементов ИЛИ, преобразователь 10 унитарного кода в модулярный значение результата операции (А х B)modm поступает на вход 11 устройства..

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

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

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

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

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

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

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

0-0-0-0-0-1-О

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

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

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

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

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

Это соответствует результату вычитания, равному 6 в унитарном коде. (2 - 3)mod 7 6. Результат поступает на вход преобразователя 10 унитарного кода в модулярный, с выхода которого значение 110 поступает на выход 11 устройства.

Приме рЗ. Определить A-B(mod 7) при А 3, В 4 (А и В - операнды).

В данном случае сигнал присутствует на втором входе И 33 и управляющем входе элемента 34 запрета, следовательно образуется цепь КСР8 из б двоичных разрядов. Первый операнд А 011 поступает на вход дешифратора 13 на выходах которого он будет представлен в следующем унитарном коде

0-0-0-1-0-0

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

0-0-0-0-0-1

Следовательно такой вид будет на разрядах КСР8. Второй операнд В поступает на

вход преобразователя 2 модулярного кода в

код индекса, на выходе которого имеем 010

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

0-1-0-0-0-0

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

20

0-0-0-0-0-1

Это соответствует результату операции

равному 5 в унитарном коде (3. х 4 mod 7 5

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

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

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

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

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

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

В этом случае все будет происходить аналогично третьему примеру, за исключением того, что сдвиг содержимого КСР8 (единицы) в JA-M двоичном разряде будет

происходить на IB двоичных разрядов влево. Содержимое КСР8 по завершении сдвига следующее

1-0-0-0-0-0

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

О-1-0-0-0-0

45

Это соответствует результату операции, равному 1 в унитарном коде (3/4 mod 7 1 mod 7). Этот результат через блок элементов ИЛИ 20 поступает на вход преобразователя

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

Техническое преимущество заявляемого изобретения в сравнении с прототипом

5 состоит в существенном увеличении числа пров одимых модульных операций (добавляются две модульные операции).

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

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

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

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

131809437 14

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