Устройство для сложения и вычитания чисел по модулю Советский патент 1992 года по МПК G06F7/49 G06F7/72 

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

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

Недостаток устройства - низкое быстродействие выполнения модульных операций.

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

Недостаток устройства - низкое быстродействие модульных операций.

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

Данное устройство позволяет реализовать сложение и вычитание по модулю с уменьшенным количеством сдвигов кольцевого сдвигающего регистра путем использоХ|

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

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

Шод2тИ I) Цель изобретения - повышение быст- родействия.

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

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

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

а , четные (#, входные операнды) 2(й - и) modm («-/) modm

2(+S)modm (a-b/S) тоёта-нечетное, /5-четное 2( -§) modm (a -/3)-1 modm

2( - §) modm К а +/SH1 modm

а- четное, нечетное

2(т; ) modm {(a -/3)+1 modm

2(| ) modm (а +/3)+1 modm а, / нечетные 2( -2О modm (2-/)modm

2( 2-т ) modm («-)-$ modm

Отметим, что коммутация первого операнда огне зависит от типа модульной операции, коммутация второго операнда / зависит от типа операции (сложение или вычитание), но результат коррекции связан только с соотношением четности перйого и второго операндов. Рассмотрим более подробно эти связи при модуле операции m 5. В табл. 1, 2 отражено соответствие кодов первого и второго операндов при уменьшении их диапазона значений.

Таблица 1

а

(23Таблица 2

aQS) + 1 2

Это соответствие относительно операнда /3 реализуется соответственно вторым и первым блоками деления на два. Преобразование результатов операции требует трех блоков умножения на два, таблицы которых соответствуют номерам 3, 4, 5.

Таблица 3

2Х

Таблица 4

2(Х+1)

Таблица 5

2 (Х-1)

Быстродействие работы определяется величиной второго операнда /3, так как от него зависит количество тактов сдвига КСР для получения результата.

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

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

0 новая совокупность признаков способствует повышению быстродействия.

На чертеже представлена структурная схема устройства, где 1 - первый информационный вход устройства; 2 - дешифратор,

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

0 по третий блоки элементов И, 10 - сумматор по модулю два, 11 - третий элемент И, 12 - четвертый элемент И, 13 - первый блок элементов И, 14-выход устройства, 15-второй информационный вход устройства, 16-пер5 вый и второй блоки деления на два, 17 - пятый блок элементов И, 18 - шестой блок элементов И, 19 - второй блок элементов ИЛИ, 20 - счетчик, 21 - элемент ИЛИ-НЕ, 22 - элемент запрета, 23 - первый элемент И,

0 24 - второй элемент И, 25 - тактовый вход устройства, 26 - вход задания сложения устройства, 27 - вход задания вычитания устройства, 28 - второй элемент НЕ, 29 - первый элемент НЕ.

5 Входы разрядов первого 1 информаци- . онного входа устройства соединены с входами разрядов входа Дешифратора 2, (2К-1)-й и 2К-й (К 1 - т/2. т - значение модуля, - округление до ближайшего

0 большего целого), выходы которого соединены соответственно с первым и вторым входами К-ro элемента ИЛИ 3 группы, выходы которых соединены с входами соответствующих разрядов первого входа четвертого

5 блока 4 элементов И, второй вход которого соединен с входом начальной установки 5 устройства, выходы разрядов выхода четвертого 4 блока элементов И соединены с входами соответствующих младших разря0 дов кольцевого 6 регистра сдвига, выходы разрядов которого соединены с соответствующими входами шифратора 7, выход которого соединен с входами с первого по третий блоков 8 умножения на два, выходы

5 которых соединены с входами блоков 9 и элементов И, вторые входы которых соединены соответственно с выходами сумматора 10 по модулю третьего 11 и четвертого 12 элементов И, а выходы соединены с соответствующими входами первого 13 блока злементов И, выход которого является выходом 14 устройства, входы разрядов второго 15 информационного входа устройства соединены с входами соответствующих разрядов входов первого и второго блоков 16 деления на два, выходы которых соединены соответственно с первыми входами пятого 17 и шестого 18 блоков элементов И, выходы которых соединены соответственно с первым и вторым входами второго 19 блока элементов ИЛИ, выход которого соединен с информационным входом счетчика 20, выходы разрядов которого соединены с соответствующими входами элемента ИЛИ-НЕ21, выход которого соединен с управляющим входом элемента 22 запрета, выход которого соединен с вычитающим входом счетчика 20 и с первыми входами первого 23 и второго 24 элемента И, выходы которых соединены соответственно с входами задания сдвига вправо и влево кольцевого регистра б сдвига, вход разрешения записи которого соединен с входом начальной установки 5 устройства, тактовый вход 25 которого соединен с информационным вх- дом элемента 22 запрета, вход 26 задания сложения устройства соединен с вторыми входами первого 23 элемента И и пятого 17 блока элементов И, вход 27 задания вычитания устройства соединен с вторыми входами второго 24 элемента И и шестого 1S блока элементов И, вход младшего разряда первого 1 информационного входа устройства соединен с первым входом сумматора

10по модулю два, с вторым входом третьего

11элемента И и с входом второго 28 элемента НЕ, вход младшего разряда второго 15 информационного входа устройства соединен с вторыми сумматора 10 по модулю два и четвертого 12 элемента И, с входом первого 29 элемента НЕ, выходы первого 29 и второго 28 элементов ЧЕ соединены соответственно с первыми входами третьего 11 и четвертого 12 элементов И.

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

Кольцевой регистр сдвига (КСР) содержит m двоичных разрядов (0 - т-1), т - значение модуля. Исходное состояние КСРб нули во всех разрядах. Сигнал на выходе элемента ИЛИ-НЕ21 появляется в том случае, когда на всех выходах счетчика 20 будут нули. При проведении операции модульного сложения операнд а поступает на вход дешифратора 2, с выхода которого, пройдя через группу 3 элементов ИЛИ, первый

0

входной операнд а преобразуется в вид

аа-1

-у при а- четном, либо -п-при анечетном. Одиночный импульс, поступающий с входа 5 на второй вход четвертого 4 блока элементов И, обеспечивает запись

единицы в -j()м разряде кольцевого

регистра 6 сдвига. Операнд /3 поступает на вход 15, с выхода первого 16 блока деления

в в+ 1 на два он в виде Ј либо t-n- через пятый

блок элементов И, второй 19 блока элементов ИЛИ поступает на установочный вход 5 счетчика 20. С тактового входа 25 через открытий элемент 22 запрета поступают импульсы на вычитающий выход счетчика 20, а также на вход сдвига вправо содержимого КСРб через открытый элемент И 23 (присутствует сигнал на входе 26). Производится продвижение единицы, записанной в КСРб

ft к Р+ 1

на Ј либо Ј-гт- двоичных разрядов вправо.

Когда содержимое счетчика 20 станет равно нулю, то сигнал с выхода ИЛИ-НЕ21 закрывает элементов 22 запрета, запрещая прохождение импульсов на сдвиг двоичных разрядов КСРб (этот сигнал является сигналом окончания модельной операции). Предварительный результат операции с выходов разрядов КСРб, полученный в унитарном коде, поступает на входы информатора 7, с выхода которого предварительный результат операции в двоичном коде поступает на входы с первого по третий блоков 8 умножения на два, с выходов которых он поступает на первые входы соответственно с первого по третий блоков 9 элементов И. На второй вход одного из них (в зависимости от соотношения четностей операндов а и/5) поступает сигнал и результат операции модельного сложения через первый 13 блок элементов ИЛИ поступает на выход 14 устройства.

Рассмотрим подробнее формирование сигналов, поступающих на один из вторых входов блоков 9 элементов И. Если в нулевых разрядах двоичного представления опе- 0 рандов аи/3 будут единицы (оба операнда нечетные), то сигнал с выхода сумматора 10 по модулю два (используется его инверсный выход) поступает на вход первого 9 блока элементов И, на второй вход которого поступает результат операции, равный удвоенному предварительному результату операции Аналогично происходит в том случае, когда оба операнда четные. Если а- четный, а/ - нечетный, то сигнал поступает на вход

0

5

0

5

0

5

5

третьего 9 блока элементов И с выхода четвертого 12 элемента И. В этом случае помимо удвоения предварительно результата происходит еще и вычитание единицы (коррекция результата). При а- нечетном, J3 - четном сигнал поступает на вход второго 9 блока элементов И с выхода третьего 11 элемента И. Здесь происходит удвоение предварительного результата модульной операции сложения с прибавлением единицы к окончательному результату.

Работа устройства при выполнении операции модульного вычитания ( a -fy modm отличается от предыдущего режима только тем, что присутствует сигнал на входе 27, поэтому производится сдвиг разрядов КСР6 на Ј при р - четном, либо на

,

с-TJ-- при нечетном влево (используется

для обработки второго операнда второй 16 блок деления на два).

Изобретение иллюстрируется следующими примерами при m 5.

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

ГО-1-O-O-Qj

Второй операнд / 011 поступит на вход первого блока 16 деления на два, с выхода которого число 010 (см, табл. 2) проходит через пятый 17 блок элементов И (сигнал на входе 26 присутствует), через второй 19 блок элементов ИЛИ устанавливается в содержимом счетчика 20. В данном случае сигнал с выхода четвертого 12 элемента И поступит на второй вход третьего 9 блока элементов И. С тактового входа 25 через элемент 22 запрета поступают два импульса, которые продвигают единицу в КСР6 на два двоичных разряда вправо и уменьшают содержимое счетчика 20 до нуля, так как поступают на его вычитающий вход. С выхода элемента ИЛИ-НЕ-21 поступает сигнал окончания модульной операции), который закрывает элемент 22 запрета. Содержимое КСР6 следующее

г-0

-О1

О

Следовательно предварительный результат операции получился равным трем. Этот результат поступает на входы шифратора 7, с выхода которого поступает на первый вход третьего блока 8 умножения на два (см. табл. 5) и результат операции, равный нулю, поступает через третий 9 блок элементов И и далее первый 13 блок элементов ИЛИ на выход 14 устройства. (2+3)mod5

(0)mod5.

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

входы дешифратора 2, на третьем выходе которого будет сигнал. Он поступит на второй вход второго элемента ИЛИ 3 группы, с выхода которого поступит через четвертый 54 блок элементов И (после импульса с входа 5) в первый разряд КСР6 (см. табл. 1), содержимое которого будет следующее

гр - - о-о-о-|

Второй операнд / 100 поступает на вход второго блока 16 деления на два, с выхода которого число 010 (см. табл. 1) проходит через шестой 18 блок элементов И (сигнал на входе 27 присутствует), через второй 19 блок элементов ИЛИ устанавливается в содержимом счетчика 20. В данном случае сигнал третьего 11 элемент И поступит на второй вход второго 9 блока элементов И. С тактового входа 25 через элемент

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

45

О-0 -00 - 1-|

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

на первый вход второго блока 8 уменьшения на два (см. табл. 4) и результат операции модульного вычитания поступает через второй блок 9 элемент И и далее первый 13 блок элементов ИЛИ на выход 14 устройства (34)mod5 (4) mod 5.

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

Jlog2m +1) -о™ , g Раз при сложении и в

(Iog2m +1) лт х при вычитании) повышении быстродействия выполнения модульных операций.

Достоверность достижения цели подтверждается конкретными примерами выполнения операций сложения и вычитания при m 5.

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

элементов И, ыходы которых соединены соответственно с первым и вторым входами второго блока элементов ИЛИ, выход которого соединен с информационным входом

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

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

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

два, выходы которых соединены соответственно с первыми входами с первого по третий блоков элементов И, вторые входы которых соединены соответственно с выходами сумматора по модулю два, третьего и четвертого элементов И (2К-1)-й и 2К-й (К 1 ,

где т - значение модуля, - округление

до ближайшего большего целого), выходы

дешифратора соединены соответственно с

первым и вторым входами к-го элемента

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

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

Редактор И.Касарда

Техред М.Моргентал

Корректор С.Лисина

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

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

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж-35, Раушская наб., 4/5

Производственно-издательский комбинат Патент, г. Ужгород, ул.Гагарина, 101