Двоичный сумматор

||и 43635Î

ОПИСАНИЕ

ИЗОБР ЕТЕ Н И Я

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Союз Советских

Социалистических

Реслублик (61) Зависимое от авт. свидетельства (22) Заявлено 14.06.71 (21) ii668560/18-24 с присоединением заявки № (32) Приоритет

Опубликовано 15.07.74. Бюллетень № 26

Дата опубликования описания 30.01.75 (51) М, Кл. G 06f 7/385

ГвсуАарственный комитет

Совета Министров СССР но делам изооретений и открытий (58) УДК 681.3255 (088.8) (72) Авторы изобретения

1О. Н. Корнев, С. В. Пискунов и С. H. Сергеев

Институт математики Сибирского отделения АН СССР (71) Заявитель (54) ДВОИЧНЫЙ СУММАТОР

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

Известны двоичные сумматоры, состоящие из m рядов по и разрядов в каждо .,I, причем каждый разряд сумматора содержит схемы

«И», «ИЛИ», «НЕ» и триггер, единичный выход которого соединен с первы и входами первой и второй схем «И», а единичный и нулевой входы его соединены соответственно с выходами первой и второй схем «ИЛИ».

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

Целью изобретения является увели .ение производительности сумматора.

Предлагаемый сумматор отличается от известных тем, что в нем первый вход любого разряда соединен со вторым входом первой схемы «И», второй вход — с третьим входом первой схемы «И», третий вход соединен со вторым входом второй схемы «И» и через схему «HE» — с четвертым входом первой схемы «И». Четвертый вход соединен с пятым входом первой схемы «И» и с третьим входом второй схемы «И», пятый вход соединен с шестым входом первой схемы «И» и с четвертым входом второй схемы «И». Шестой и седьмой входы соединены соответственно с псрвым и вторым входами первой схемы «ИЛИ», восьмой вход соединен с первым входом второй

10 схемы «ИЛИ». Первый выход соединен с нулевым выходом триггера, второй и третий выходы соединены соответственно с выходами первой и второй схем «И» и вторым и третьим входом второй схемы «ИЛИ». При этом у

15 каждого i-го разряда Й-го ряда первый вход соединен с первым выходом (i+ 1)-го разряда k-го ряда, второй вход — с первым выходом (i+ 1)-го разряда (/г — 1)-го ряда, третий вход соединен с первым выходом i-Io

20 разряда (Й+ 1)-го ряда, четвертьш вход соединен с первым выходом i-го разряда (А — 1) -го ряда, пятый вход соединен с управляющим входом устройства, шестой вход соединен со вторым выходом i-го разряда

25 (k — l) -го ряда, седьмой вход соединен с третьим выходом (| — 1)-го разряда /г-го ряда, а восьмой вход соединен с третьим Выходом i-го разряда (/г — 1)-го ряда.

На фиг. 1 приведена логическая схема од30 ного разряда сумматора; на фиг. 2 — схема

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

5 соединений входов каждого разряда сумматора с выходами других разрядов сумматора.

Логическая схема разряда сумматора содержит шестивходовую схему «И» 1, четырехвходовую схему «И» 2, схему «НЕ» 3, двухвходовую схему «ИЛИ» 4, трехвходовую схему «ИЛИ» 5 и триггер 6.

Единичный выход 7 триггера соединен с первыми входами 8 и 9 первой и второй схем

«И» 1 и 2. Первый вход 10 разряда соединен со вторым входом 11 первой схемы «И» 1, второй вход 12 — с третьим входом 13 первой схемы «И» 1, третий вход 14 соединен со вторым входом 15 второй схемы «И» 2 и через схему «НЕ» — с четвертым входом 16 первой схемы «И» 1, четвертый вход 17 соединен с пятым входом 18 первой схемы «И» 1 и с третьим, входом 19 второй схемы «И» 2, пятый вход 20 соединен с шестым входом 21 первой схемы «И» 1 и с четвертым входом 22 второй схемы «И» 2, шестой 23 и седьмой 24 входы соединены соответственно с первым 25 и вторым 26 входами первой схемы «ИЛИ» 4, восьмой вход 27 соединен с первым входом 28 второй схемы «ИЛИ» 5.

Первый выход 29 разряда соединен с нулевым выходом 30 триггера 6, второй 31 и третий 32 выходы соединены соответственно с выходами 33 и 34 первой и второй схем

«И» и вторым 35 и третьим 36 входами второй схемы «ИЛИ». Пятый вход 20 разряда сумматора соединен с управляющим входом устройства.

Разряды сумматора нумеруются справа налево, ряды — снизу вверх. В каждом i-ом разряде 37 k-го ряда сумматора первый вход

10 соединен с первым выходом 29 (i+1)-го разряда 38 k-ro ряда, второй вход 12 соединен с первым выходом 29 (i+1)-го разряда

39 (k — 1) -ro ряда, третий вход 14 соединен с первым выходом 29 i-ro разряда 40 (1+1)-го ряда, четвертый вход 17 соединен с первым выходом 29 i-го разряда 41 (k — 1)-ro ряда, шестой вход 23 соединен с третьим выходом

32 i-го разряда (k — 1)-го ряда, седьмой вход

24 соединен со вторым выходом 31 (i — 1)-го разряда 42 k-ro ряда, восьмой вход 27 соединен со вторым выходом 31 i ãî разряда (k — 1) -го ряда.

Преобразование информации в сумматоре осуществляется в два такта: в такте считывания информация с триггеров разрядов поступает на комбинационные схемы разрядов, в такте записи информация с выходов комбинационных схем разрядов записывается в тр иггер ы р азр ядов.

Настройка сумматора на тот или иной режим работы (сложение чисел в нескольких независимых зонах, конвейерный режим сложения в нескольких независимых зонах) осуществляется по входам 20 разрядов. В том случае, если на входы 20 всех разрядов подан сигнал «1», сумматор представляет собою одну зону, и алгоритм сложения состоит в преобразовании прямоугольной, бинарной таб(2) 10

15 подконфигурация из конфигурации 1) заменяется на конфигурацию

30 а подконфигурация

40 из конфигурации 2) заменя .-.тся на и т. д. пока такие преобразования возможны.

50 Когда такие преобразования невозможны (в таблице нет ни одной конфигурации вида 1, 2), это значит, что сумма вычислена.

Константы, подаваемые на свободные входы крайних разрядов сумматора (на входы

55 10, 12, 14, 17 поступает сигнал «1», на входы

23, 24, 27 — сигнал «О»), связи между логическими элементами в каждом разряде сумматора и связи между разрядами сумматора подобраны так, что сумматор выполняет ал60 горитм сложения, описанный выше. Действительно, пусть, например, разряды 37 — 41 сумматора образуют конфигурацию 1). Это значит, что на единичных выходах триггеров разрядов 37 — 41 соответственно сигналы «1», «О».

65 «О», «1», «О». В такте считывания информа436350 на конфигурацию

50

55 зоне сумматора. ции с триггеров разрядов сумматора на входы

10, 12, 14, 17, 20 i-го разряда 37 k-ro ряда и входы 8 и 9 первой и второй схем «И» этого разряда поступают соответственно сигналы

«1», «1», «О», «1», «1», «1», «1». Легко убедиться, что при таком наборе входных сигналов на выходах 29, 31 и 32 разряда 37 будут соответственно сигналы «О», «1», «Î, и в такте записи в триггер разряда 37 будет записан сигнал «О», в триггер разряда 38 в сигнал

«1», в триггер разряда 40 в сигнал «О». Это и означает, что произошла замена подконфигурации

При рассмотрении работы i-го разряда k-го ряда не учитывается влияние входов 23, 24 и

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

Аналогичное рассмотрение можно провести для различных наборов состояний i-го разряда k-го ряда и его соседей и убедиться что сумматор работает в соответствии с описанным алгоритмом сложения.

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

Чтобы осуществить разбиение, на входы 20 разрядов рядов с номерами 1, 2, ..., (1 — 1), (l+2), (l+ 3), ..., (m — 1), т подается сигнал «1», на входы 20 разрядов рядов с номерами 1, (1+ 1) подается сигнал «О». Итак, сумматор настроен. Этот сумматор может одновременно вычислять суммы l слагаемых в нижней зоне и (т — l — 1) слагаемых в верхней зоне (слагаемое, записанное в строке (l+1) верхней зоны, для правильной работы сумматора должно быть нулем). Сумма слагаемых нижней зоны получается в l-ой строке, верхней зоны — в т-ой строке сумматора. Легко убедиться, что при такой настройке передача информации из зоны в зону не происходит. Для этого достаточно рассмотреть все возможные расположения конфигураций 1, (2) относительно рядов l (i+1).

1О

25 зо

Наиболее эффективно применение сумматора в конвейерном режиме. Такое применение увеличивает среднюю скорость вычислений и обеспечивает совмещение оборудования.

Работа сумматора в конвейерном режиме осуществляется следующим образом.

Первоначально на входы 20 разрядов всех рядов сумматора подан сигнал «О». Первое слагаемое записывается в первый ряд, второе — во второй, третье — в третий; в момент записи третьего слагаемого на входы 20 разрядов первого ряда сумматора подается сигнал «1», в момент записи четвертого слагаемого на входы 20 второго ряда подается сигнал «1» и т. д., т. е, разряды рядов сумматора вовлекаются в параллельное сложение со скоростью записи информации, другими словами, когда осуществляется запись k-го слагаемого, (k — 2) слагаемых уже участвуют в параллельном сложечии.

Алгоритм сложения таков, что в пропессг вычислений ряды освобождаются (обнуляются), начиная снизу, один за другим. Как только освободится первый ряд, на входы 20 всех разрядов этого ряда подается сигнал «О»; клк только освободится втооой ряд, на входы 20 всех разрядов этого ряда подается сигнал

«О»; как только освободится третий ряд, на входы 20 всех разрядов этого ряда подается сигнал «О». В момент обнхления третьего ряда в первый ряд записывается пепвое слагаемое новой группы слагаемых, и на входы 20 всех оазрядов этого ряда подается сигнал

«1». В момент обнуления четвеотого рялл нл входы 20 всех разрядов этого ряда подается

«О», а во втовой рял записывается второе слагаемое новой группы слагаемых. и нл входы

20 всех разnÿäîâ этого ряда подается сигнал

«1» и т. д.

Итак, в ппедллглемом сумматоре ждать получения результата прелылущего вычисления не нужно: по мере освобождения строк сумматора, до получения этого результата, их можно загружать слагаемыми очепедной rn . ипы, которые сразу же вовлекаготся в плпл tлельное сложение. Результлт сложения последующей группы чисел получается в верхней стпоке сум атора по истечении времени, необхочимого для параллельного сложения четырех последних чисел из предыду цен группы чисел и никак не зависящего от числа рядов в сумматоре. В сумматоре с достаточно больп.им числом пялов m на одном и том же обопуловлнии могхт одновпеменпо вычислит.ся гх ммы многих групп слагаемых. число сллглемых в каждой группе может быть m.

Фиксируя разбиение суммлтопл нл зонин описанный процесс можно наладить в каждой

Предмет изобретения

Двоичный сумматор. состоящий из m рядов по и разрядов в каждо.я, причем каждый плзряд сумматора содержит схемы «И», «ИЛИ», 436350

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

«ИЛИ», восьмой вход соединен с первым входом второй схемы «ИЛИ», а первый выход соединен с нулевым выходом триггера, второй и третий выходы соединены соответственно с выходами первой и второй схем «И» и вторым и третьим входами второй схемы «ИЛИ», при этом у каждого -го разряда k-го ряда первый вход соединен с первым выходом (i+1)-ro разряда k-го ряда, второй вход— с первым выходом (i + 1) -го разряда (k — 1)10 го ряда, третий вход соединен с первым выходом i-го разряда (k+1)-го ряда, четвертый вход соединен с первым выходом -ro разряда (k — 1) -ro ряда, пятый вход соединен с управляющим входом устройства, шестой вход

15 соединен со вторым выходом i-ro разряда (k — 1) -го ряда, седьмой вход соединен с третьим BbIxogIoM (i — 1)-го разряда k-го ряда, а восьмой вход соединен с третьим выходом i-го разряда (k — 1)-го ряда.

436350

2З

70 12

79 17 20

Фиг 2

Составитель С. Пискунов

Техред Т. Курилко

Корректор В. Брыксина

Редактор Е, Семанова

Типография, пр, Сапунова, 2

Заказ 54/3 Изд. № 1977 Тираж 624 Подписное

Ll;HHHIIH Государственного комитета Совета Министров СССР по делам изобретений и открытий

Москва, 7К-35, Раушская наб., д, 415