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

(51)5 6 06 Г 7/72 ТЕНТНО ГОСУДАРСТВЕ ННОЕ ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) АНИЕ ИЗОБРЕТЕНИЯ ТОРСКОМ ИДЕТЕЛЬСТВ(56) Авторское свидетельство СССРМ 1257643, кл, 6 06 Р 7/72, 1984,Авторское свидетельство СССРЬ 1168934, кл, 6 06 Г 7/72, 1985,Авторское свидетельство СССРМ 1546976, кл, 6 06 Р 7/72, 1988(54) УСТРОЙСТВО ДЛЯ СЛОЖЕНИЯ И ВЫЧИТАНИЯ ЧИСЕЛ ПО МОДУЛЮ(57) Изобретение относится к автоматике ивычислительной технике и может быть использовано в вычислительных машинах на Ы1820380 Д устройствах, функционирующих в системе остаточных классов.Цель изобретения - повышение быстродействия. Цель достигается за счет уменьшения в два раза количества импульсов для продвижения содержимого кольцевого регистра 6 сдвига путем введения трех преобразователей 14, 15, 9 кода, третьего блока 4 элементов И, третьзго 25 и четвертого 26 элементов И, двух элементов ИЛИ 22, 29, двух элементов НЕ 24, 30, элемента ИЛИ - НЕ 17, сумматора 23 по модулю два, Сущность изобретения состоит в повышении быстродействия выполнения модульных операций сложения и вычита- . ния, которое достигается уменьшением диапазона значений входных операндов 1 ил., 3 табл,.1820380 10 блиц где е - модул Лекс операнда д(ц)О О, если 0 уд (ув) в +, если --Таблица Изобретение относится к автоматике и вычислительной технике и может быть использовано в вычислительных машинах и устройствах, функционирующих в системе остаточных классов.Цель изобретения - повышение быстродействия.Сущность изобретения состоит в повышении быстродействия выполнения модульных операций сложения и вычитания путем уменьшения диапазона значений входных операндов, Известно, что. в схеме модульного умножения используются свойства симметрии арифметической таблицы относительно правой и левой диагонали, а также вертикали и горизонтали, проходяа - 1 в+1 щих между величинами и в ь устройства. Обозначив ин- как а А(В) " а - А(В), можно получить следующие соотношения для операций модульногосложения и вычитания;при уд =уЬ-О(А+ В)аобе в - (А+ В)аобв; (А -В)аоба а - (А - В)аоба,Данные соотношения позволяют существенно уменьшить величину входных опе. рандов, Рассмотрим их реализацию прие - 5, Для определения величины уВ первый преобразователь кода необходимо выполнить согласно табл. 1. Второй и третий преобразователи кода (табл, 2 и 3) реализуют соответственно функции преобразования В-ф В и (в - Х), где Х - предварительное значение результатаоперации,Таблица 2 Быстродействие работы определяетсявеличиной второго операнда В, так как отнего зависит количество тактов сдвига для25 получения результата. 8 изобретении мака всимэльная величина Вмзкс 2. Группаэлементов ИЛИ в данном случае (в - 5)состоит из двух элементсв, к первым входам30 которых подключены соответственно первый и второй выходы дешифратора, э к вторым - соответственно четвертый и третий.Возможность достижения положительного эффекта от использования изобрете 35 ния состоит в повышении быстродействияработы устройства, ввидууменьшения количества сдвигов регистра для получения ре зультата.Дополнительным положительным эф 40 фектом является уменьшение количестваоборудования и коммутаций, что позволяетупростить устройство и повысить его надежность,На чертеже представлена структурная.45 схема устройства, где 1 - первый информационный вход устройства, 2 - дешифратор,3- группа элементов ИЛИ, 4 - третий блокэлементов И, 5 - вход начальной установкиустройства, 6 - кольцевой регистр сдвига,50 7- шифратор, 8 - первый блок элемента И,9 - третий преобразователь кода, 10 - второй блок элементов И. 11 - блок элементовИЛИ, 12 - выход устройства, 13 - второйинформационный вход устройства, 14- пер 55 вый преобразователь кода, 15 - второй преобразователь кода, 16 - счетчик, 17 -элемент ИЛИ - НЕ, 18 - элемент запрета, 19- тактовый вход устройства, 20 - первыйэлемент И, 21 - второй элемент И, 22 -первый элемент ИЛИ, 23 - сумматор по мо 18203805 10 20 25 30 35 40 45 50 55 дулю два, 24первый элемент НЕ, 25 - третий элемент И, 26 - четвертый элемент И, 27 - вход задания операции сложения устройства, 28 - вход задания операции вычитания устройства, 29 - второй элемент ИЛИ, 30 - второй элемент НЕ,Первый информационный вход 1 устройства соединен с входом дешифраторэ 2, младшие и старшие выходы которого соединены соответственно с первыми и вторыми входами соответствующих элементов ИЛИ 3 группы, Выходы последних соединены с первыми входами соответствующих элементов И третьего блока 4, вторые входы которых соединены с входом 5 начальной установки устройства и входом разрешения записи кольцевого регистра 6 сдвига, а выходы - с входами соответствующих младших разрядов кольцевого регистра б сдвига. Выходы разрядов регистра 6 соединены с соответствующими входами шифратора 7, выход которого соединен с первыми входами элементов И первого блока 8 и с входом третьего преобразователя 9 кода, выход которого соединен с первым входом второго блока 10 элементов И, Выходы первого 8 и второго 10 блоков элементов И соединены соответственно с первым и вторым входами блока 11 элементов ИЛИ, выход 12 которого является выходом устройства. Второй информационный вход 13 усгройства соединен свходами первого 14 и второго 15 преобразователей кода, выход которого соединен с информационным входом счетчика 16. выходы разрядов счетчика 16 соединены с соответствующими входами элемента ИЛ И-Н Е 7, выход которого соединен с вторым входом элемента 18 запрета. Первый вход последнего соединен с тактовым входам 19 устройства, а выход - с вычитающим входом счетчика 16 и с первыми входами первого 20 и второго 21 элементов И, выходы которых соединены соответственно с входами задания сдвига вправо и влево кольцевого регистра б сдвига. Старшие выходы дешифратора 2 соединены с соответствующими входами первого элемента ИЛИ 22, выход которого соединен с первым вхо дом сумматора 23 по модулю два, вторыми входами элементов И второго блока 10 и с входом первого элементами НЕ 24, выход которого соединен с вторыми входами элементов И первого блока 8, Выход младшего разряда первого преобразователя 14 кода соединен с вторым входом сумматора 23 по модулю два, инверсный и прямой выходы которого соединены с первыми входами соответственно третьего 25 и четвертого 26 элементов И. вторые входы которых соединены соответственно с входами задания операций сложения 27 и вычитания 28 устройства, Выходы третьего и четвертого элементов И соединены с первым и вторым входами второго элемента ИЛИ 29, выход которого соединен с вторцм входом первого элемента И 20 и с входом второго элемента НЕ 30, выход которого соединен с вторым входом второго элемента И 21.Работу устройства удобно рассматривать в двух режимах: режиме определениярезультата операции модульного сложения и режиме определения результата операции модульного вычитания,Кольцевой регистр б сдвига содержит а двоичных разрядов (О - в). гп - значениемодуля. Исходное состояние регистра - нули во всех разрядах. Сигнал на выходе элемента ИЛИ - НЕ 17 появляется в том случае, когда на всех выходах счетчика 16 нули. При проведении операции модульного сложения операнд А поступает на вход дешифратора 2, с выхода котороо, пройдя через группу 3 элементов ИЛИ, преобразуется в А при уд = 1, Одиночный импульс, поступающий с входа 5 на второй вход блока 4 элементов И, обеспечивает запись единицы в А(А)-м разряде кольцевого регистра б сдвига. Операнд В поступает на вход 13, с выхода второго преобразователя 15 кода он в виде В(В при ув = 1) поступает на установочный вход счетчика 16. С тактового входа 19 через открытый элемент 18 запрета по. ступают импульсы на вычитаюгций вид счетчика 16. Сигнал с выхода первого элемента ИЛИ 22 поступает, если уд = 1, а с выхода преобразователя 14 кода - ес,и ув -= 1, С инверсного выхода сумматора 23 по модул о два поступает сигнал, если уд =1 д, В данном случае (присутствует сигнал на входе 27) при уд =ув сигнал с выхода третьего элемента И 25 через второй элемент ИЛИ 29 поступает на вход сдвига вправо содержимого ретистра 6 через открытый элемент И 20 (на другой его вход поступает тактовые импульсы). Производится продвижение единицы, записанной в регистр, на В(В) двоичных разрядов вправо, когда содержимое счетчика 16 равно нулю, сигнал с выхода элемента ИЛИ - НЕ 17 закрывает элемент 18 запрета, запрещая прохождение импульсов на сдвиг двоичных разрядов регистра (этот сигнал является сигналом окончания модульной операции), Результат операции с выходов разрядов регистра, полученный в унитарном коде, поступает на охолц шифратора 7, с выхода которого он поступает на входы первого блока 8 элементов И и через третии преобразователь 9 кода (произ;,одит операцию гл - Х) на входы второго 10 .локэ(-0-0- 1-0-0-) Второй операнд В = 100 поступает на вход второго преобразователя 15 кода, с выхода которого число В = 001 (см, табл, 2) устанавливается в содержимом счетчика 16. На выходе первого элемента ИЛИ 22 сигнала нет. а с выхода первого преобразователя 15 кода(см, табл. 1) поступает сигнал. В этом случае (сигнал на входе 27 присутствует) сигнал поступает с выхода второго элемента НЕ 30 на вход второго элемента И 21. Сигнал также поступает с выхода первого элемента НЕ 24 на вход первого блока 8 элементов И, С тактового входа 19 через элемент 18 запрета поступает один импульс, который продвигает единицу в регистре на один двоичный разряд влево и уменьшает содержимое счетчика 16 до нуля, так как поступает на его вычитающий вход. С выхода элемента ИЛИ - НЕ 17 поступает 40 45 50 55 элементов И, Если уд= 1. то производится коррекция результата путем поступления сигнала на другой вход второго блока 10 элементов И с выхода первого элемента ИЛИ 22. В противном случае поступает сиг нал с выхода первого элемента НЕ 24 на другой вход первого блока 8 элементов И и результат операции через блок 11 элементов ИЛИ поступает на вход 12 устройства. Если уд Фув, то сигнал с оцхода второго 10 элемента НЕ 30 поступает на вход сдвигавлево содержимого регистра через открытый элемент И 21, Иначе говоря, при удув производится изменение Сдвига двоичных разрядов регистра с правого на 15 левое.Работаустройстоа при выполненииоперации. модульного вычитания отличается от модульного сложения только тем, что в данном случае при уд Ф ув производится изме нение сдвига двоичных разрядоо регистра с левого на правое.Рассмотрим примеры конкретного выполнения операций модульного сложения и вычитания при а = 5. 25П р и м е р 1, Пусть необходимо определить результат операций модульного сложения для А = 2, В = 4 (А. В - операнды). Первый операнд А =- 010 поступает на вход дешифратора 2, на втором выходе которого 30 будет сигнал. Этот сигнал поступает на первый оход второго элемента ИЛИ 3 группы, с выхода которого он поступает через третий блок 4 элементов И (после импульса с входа 5) оо второй разряд регистра (см. табл. 2), содержимое которого следующее сигнал, который закрывает элемент 18 запрета. Содержимое регистра следующее.Следовательно, результат операции равен единице, Он поступает на входы шифра тора, с выхода которого поступает в двоичном коде (001) на первый вход первого блока 8 элементов И и с его вцхода через блок 11 элементов ИЛИ на вцход 12 устрой. ство (2+ 4)щоб 5 = (1)по 05.П р и м е р 2. Пусть необходимо определить результат операции модульного вычитания для А = 4, В =- 3 (А, В - операнды). Первый операнд А = 100 поступает на вход дешифратора 2, на четвертом выходе которого будет сигнал, Этот сигнал поступает на второй вход первого элемента ИЛИ 3 группы, с выхода которого он поступает через блок 4 элементов И (после импульса с входа 5) в первый разряд регистра (см, табл, 2), содержимое которого следующеег.0-1-0-0-0-,Второй операнд В = 011 поступает на вход второго преобразователя 15 кода, с выхода которого число В "010 (см, табл. 2) устанавливается о содержимом счетчика 16. Сигналы поступают с вцхода пероого элеме та ИЛИ 22 и с выхода первого преобразователя 14 кода (см. табл, 1), В этом случае (сигнал на входе 28 присутствует) сигнал поступает с выхода второго элемента НЕ 30 на вход второго элемента И 21, а с выхода первого элемента ИЛИ 22 на вход второго блока 10 элементов И. С тактового входа 19 через элемент 18 запрета поступают два импульса, которые продвигают единицу в регистре на два двоичных разряда влево и уменьшают содержимое счетчика 16 до нуляСодержимое регистра следующеег.о-о-о-о-Этот результат (100) в двоичном коде поступает с выхода шифратора 7 на третий преобразователь 9 кода, с выхода которого окончательный результат 001 (см. табл. 3) через второй блок 10 элементов И, блок 11 элементов ИЛИ поступает на выход 12 устройства (4 - 3)гпоб 5 = (1)еоб 5.Техническое преимущество изобрете ния в сравнении с прототипом состоит существенном (максимально в )1 о 92 а( х10 1820380 дами соответственно третьего и четвертого элементов И, вторые входы которых соеди 35 нены соответственно с входами задания операций сложения и вычитания устройства, а выходы третьего и четвертого элементов И соединены с первым и вторым входами второго элемента ИЛИ, выход которого соединен с вторым входом первого элемента И и входом второго элемента НЕ, выход которого соединен с вторым входом второго элемента И,40 Составитель В, Ирхин Редактор С. Кулакова Техред М.Моргентал Корректор Н. КорольЗаказ 2031 Тираж ПодписноеВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР113035, Москва. Ж, Раушская наб 4/5 Производственно-издательский комбинат "Патент", г. Ужгород. ул,Гагарина, 101 а - 2с --- рве) повышении быстродеиствия выполнения модульных операций. Дополнительным преимуществом является уменьшение количества оборудования и связей, приводящее к упрощению устройства,Достоверность достижения цели подтверждается конкретными примерами выполнения операций сложения и вычитания при гп =5. Формула изобретения Устройство для сложения и вычитания чисел по модулю. содержащее дешифратор, кольцевой регистр сдвига, шифратор, первый и второй элементы И, элемент запрета, счетчик, первый и второй блоки элементов И, блок элементов ИЛИ и группу элементов ИЛИ, причем первый информационный вход устройства соединен с входом дешифратора, выходы первого и второго элементов И соединены соответственно с входами задания сдвига вправо и влево кольцевого регистра. сдвига, вход разрешения записи которого соединен с входом начальной установки устройства, выходы первого и второго блоков элементов И соединены с соответствующими входами блока элементов ИЛИ, выход которого является выходом устройства, тактовый вход которого соединен с первым входом элемента запрета, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия. оно содержит с первого по третий преобразователи кода, третий блок элементов И, третий и четвертый элементы И, два элемента ИЛИ, два элемента НЕ, элемент ИЛИ-НЕ, сумматор по модулю два, причем второй информационный вход устройства соединен с входами первого и второго преобразователей кода, выход которого соединен с информационным входом счетчика, выходы разрядов которого соединены с соответствующими входами элемента ИЛИ - НЕ, выход которого 5 10 15 20 25 30 соединен с вторым входом элемента запрета. выход которого соединен с вычигающим входом счетчика и первыми входами первого и второго элементов И, младшие и старшие выходы дешифратора соединены с первыми и вторыми входами соответствующих элементов ИЛИ группы, выходы которых соединены с первыми входами соответствующих элементов третьего блока И, вторые входы которых соединены с входами начальной установки устройства, выходы элементов И третьего блока соединены с входами соответствующих младших разрядов кольцевого регистра сдвига, выходы разрядов которого соединены с соответствующими входами шифратора, выход которого соединен с первыми входами элементов И первого блока и с входом третьего преобразователя кода, выход которого соединен с первым входом второго блока элементов И, старшие выходы дешифратора соединены с соответствующими входами первого элемента ИЛИ. выход которого соединен с первым входом сумматора по модулю два, вторыми входами элементов И второго блока и с входом первого элемента НЕ, выход которого соединен с вторым элементом И первого блока, выход младшего разряда первого преобразователя кода соединен с вторым входом сумматора по модулю два, инверсный и прямой выходы которого соединены с первыми вхо