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

 

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

СОВХОЗ СОВЕТСКИХ

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

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

U1J" f „- 5,

- ЕПЕ, Р;, .".=

ЛИОТЕ,, ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ. СССР

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4821449/24 (22) 03.05.90 (46) 15.08.92. Бюл. E 30 (72) В, А. Краснобаев, В, П, Ирхин; И. B.

Милехин, M. В, Юмашев и А. A. Сахно (56) Авторское свидетел ьство СССР

К - 1683012, кл. G 06 F 7/72, 1989, Авторское свидетельство СССР

М 1546976, кл. 6 06 F 7/72, 1988 (прототип). (54) УСТРОЙСТВО ДЛЯ СЛОЖЕНИЯ И ВЫЧИТАНИЯ ЧИСЕЛ ПО МОДУЛЮ (57} Изобретение относится к автоматике и вычислительной технике и может быть исИзобретение относится к области автоматики и вычислительной техники и может быть использовано в вычислительных машинах и устройствах, функционирующих в системе остаточных классов.

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

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

Близким по технической сущности изобретению является устройство, содержащее входные регистры, выходной регистр, де5U 1755275 Al

non 3OaaHo a aW CameJtbHuX. VamvaaX v устройствах, функционирующих в системе остаточных классов. Цель изобретения — повышение быстродействия. Устройство содержит дешифратор, группу элементов

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

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

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

Данное устройство позволяет реализовать сложение и вычитание по модулю с уменьшенным количеством сдвигов кольцевого сдвигающего регистра путем исйользо1755275 вания двух исходных состояний кольцевого регистра, Недостаток прототипа — низкое быстродействие при выполнении модульных one" раций сложения и вычитания ввиду того, что максимальное количество тактов сдвига кольцевого регистра прототипа равно ((1осрп)) + 1)

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

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

50 а 1Р- четные (а, Р- входные операнды)

2(— () modm =(а -р) modm

2(-1- ) modm =(a+P) modm а- нечетное, Р- четное ,Q — 1

2(— — — () modm = ((a —,9)-1) modm

Q — 1

2(— () modm = ((a +P)-1) modm

Q четное; Р- нечетное а Л вЂ” 1

2((— — ) modm = ((а — j3)+1) modm

2 — — у — ) modm = j(Q+p+1) modm, р+1

Q, p- нечетные а — 1  — 1

2(—,)г — — ) modm = (а — /3) modm элементов И, вход задания вычитания устройства соединен с вторыми входами второго элемента И и шестого блока элементов И, вход младшего разряда первого информа5 ционного входа устройства соединен с первым входом сумматора по модулю два, с вторым входом третьего элемента И и с входом второго элемента НЕ, вход младшего разряда второго информационного входа

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

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

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

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

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

40 помощи использования следующих соотношений:

1755275

Таблица 1

Таблица 2

Таблица 3

2Х

Таблица 4

2(Х+1) Таблица 5

45. блока 4 элементов И, второй вход которого

2 (Х-1) а-1 А+1

2(— 2 —,— ) modm =(а+Р) modem

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

В табл. 1 2 отражено соответствие кодов первого и второго операндов при уменьшении их диапазона значений.

3Т0 соответствие относительно операнда Р реализуется соответственно вторым и первым блоками деления ка два, Преобразование результатов операции требует трех блоков умножения на два, таблицы которых соответствуют номерам 3, 4, 5, Быстродействие работы определяется величиной второго операнда Р, так как от него зависит количество тактов сдвига КСР для получения результата, Возможность достижения положительного эффекта от использования изобретения состоит в повышении быстродействия работы устройства ввиду уменьшения количества сдвигов КСР для получения результата.

Введенные новые признаки (с четвертого по шестой блоки элементов И, элемент

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

Входы разрядов первого 1 информационного входа устройства соединены с входами разрядов входа Дешифратора 2, (2К-1)-й и 2К-й (К = 1 — )а/2(, m — значение модуля, 1. (— округление до ближайшего большего целого), выходы которого соедикены соответственно с первым и вторым входами К-го элемента ИЛИ 3 группы, выходы которых соединены с входами соответствующих разрядов первого входа четвертого соединен с входом начальной установки 5 устройства, выходы разрядов выхода четвертого 4 блока элементов И соединены с входами соответствуЮщих младших разрядов кольцевого 6 регистра сдвига, выходы разрядов которого соединены с соответствующими входами шифратора 7, выход которого соединен с входами с первого по третий блоков 8 умножения на два, выходы которых соединены с входами блоков 9 и элементов И, вторые входы которых соединены соответственно с выхбдами сумматора

10 по модулю третьего 11 и четвертого 12 элементов И, а выходы соединены с соответствугощими входами первого 13 блока эле1755275 ментов И, выход которого является выходом

14 устройства, входы разрядов второго 15 информационного входа устройства соединены с входами соответствующих разрядов входов первого и второго блоков 16 деления на два, выходы которых соединены соответственно с первыми входами пятого 17 и шестого 18 блоков элементов И, выходы которых соединены cooTBGTGTBGHHQ с первым и вторым входами второго 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 элементов И, Работу устройства удобно рассматривать в двух режимах: режим определения результата операции модульного сложения; режим определения результата операции модульного вычитания, Кольцевой регистр сдвига (КСР) содержит m двоичных разрядов (Π— m-1), m— значение модуля, Исходное состояние КСР6 нули во всех разрядах. Сигнал на выходе элемента ИЛИ-НЕ21 появляется в том. случае, когда на всех выходах счетчика 20 будут нули, При проведении операции модульного сложения операнд а поступает на вход дешифратора 2, с выхода которого, пройдя через группу 3 элементов ИЛИ, первый входной операнд Q преобразуется в вид

Q Q — 1 при а — четном, либо — 2 — при ив нечетном, Одиночный импульс, поступаю5 щий с входа 5 на второй вход четвертого 4 блока элементов И, обеспечивает запись аа — 1 единицы в (— 2 — )-м разряде кольцевого регистра 6 сдвига, Операнд Р поступает на

10 вход 15, с выхода первого 16 блока деления

8+1 надва он в виде либо —, через пятый блок элементов И, второй 19 блока элементов ИЛИ поступает на установочный вход

15 счетчика 20, С тактового входа 25 через открытый элемент 22 запрета поступают импульсы на вычитающий выход счетчика 20, а также на вход сдвига вправо содержимого

КСР6 через открытый элемент И 23 (присут20 ствует сигнал на входе 26), Производится продвижение единицы, записанной в КСР6

+ на либо †2 двоичных разрядов вправо.

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

40 вход одного из них (в зависимости от соотношения четностей операндов а NPJ поступает сигнал и результат операции модельного сложения через первый 13 блок элементов ИЛИ поступает на выход 14 уст45 ройства.

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

1755275

Второй операнд P = 011 поступит.на вход первого блока 16 деления на два, с выхода которого число 010 (см, табл. 2) проходит через пятый 17 блок элементов И (сиг-. нал на входе 26 присутствует), через второй

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

КСР6 следующее

40 следующее — 0 — 0 — 0 0 — 1 — 1

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

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

-0 — 0

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

Работа устройства при выполнении операции модульного вычитания (а — P

modm отличается от предыдущего режима только тем, что присутствует сигнал на входе 27, поэтому производится сдвиг разрядоа КСР6 íà f npu P — четном, либо на

+ 1 при нечетном влево (используется для обработки второго операнда второй 16 блок деления на два).

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

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

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

Следовательно предварительный результат операции получился равным трем.

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

ИЛИ на выход 14 устройства. (2+3)mod5 =

10 (0)mod5.

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

Первый операнд a = 011 поступает на

15 входы дешифратора.2, на третьем выходе которого будет сигнал. Он поступит на второй вход второго элемента ИЛИ 3 группы, с выхода которого поступит через четвертый

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

0 1 0 0 0 3

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

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

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

1755275

m — 2 (jlog2m)+1) 2 +2 раз при сложении и в

2m+2

m — 2 ((logzm)+1) и ри вычитании) повышении быстродействия выполнения модульных операций;

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

Формула изобретения

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

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

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

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

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

30 два, выходы которых соединены соответственно с первыми входами с первого по третий блоков элементов И, вторые входы которых соединены соответственно с выходами сумматора по модулю два, третьего и четверто35 го элементов И (2К-1)-й и 2К-й (K =. 1 -)m/2(, где m — значение модуля, ) (— округление до ближайшего большего целого), выходы дешифратора соединены соответственно с первым и вторым входами к-го элемента

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

1755275

Редактор И.Касарда Техред M.Ìîðãåíòàë

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

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

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

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

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