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

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