Способ сложения двоичных чисел

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

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

l76 724

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

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

Республик а 1.(АЧО Ц1:, Я

; p flATEITl!0Л.ХНМЧЕС11А Я

БИБ- 1НОТЕКд

Зависимое от авт. свидетельства №

1,л. 42л», 140:»

Заявлено 06.11.1964 (№ 880153/26-24) с присоединением заявки №

Государственный комитет ло делам изобретений и открытий СССР

11ПК G 06f

Приоритет

Опубликовано 17.Х1.1965. Б»о.»лете»»ь ¹ 23

УД К 681.142 — 523.8,07 (088.8) Дата опубликования o»II»ca>III»I 28.XI1.1965

Авторы изооретения

P Б. Мнацаканов, Г. Г. Ладария и О. Г. Агдгомелашвили

Заявитель

СПОСОБ СЛОЖЕНИЯ ДВОИЧНЫХ ЧИСЕЛ

Подписная аруппа Л3 174

Известны способы сложения двоично-кодированных чисел.

Предложенный способ отличается от известных тем, что формируют два слова: сумму 110

mod 2 исходных слагаемых и конъюнкцию исходных слагаемых со сдвигом на один разряд влево, после чего одноименные разряды полученных слов разбивают на группы так, что группы первого типа ограничены справа ком1 би»»ацией вЂ, а слева — первои же комоина1

0 цие„-, —, оставшиеся же разряды образуют

0 группы и-гo типа, а окончательный результат получают инвертированием разрядов первого слова, входящих в группы первого типа и суммированием по mod2 одноименных разряJOI3 ОООИХ С 10»3, ВХОДЯЩИХ В ГPX ППЫ IITOPOI O типа.

Это позволяет ускорить процесс суммирования.

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

Слагаемые представле»»ы 13 следующем 13»ue:

4 = а„и„»... а;а,а,,а,,а, В l>n бл — 1 . 6,1 "4" 341>1

При этом знаковых разрядов не выделяют, т. е. считаюг все разряды разрядами модуля.

Первым шагом по предлагаемому способу является нахождение по mod 2 исходных слагаемых. Каждый i-й разряд суммы по mod 2 обозначен через q;, а результат первого шага можно представить следующим образом:

qÄ qÄ 1 .. Ч>Ч4ЧЗЧ2Ч1 (1)

Вторь»м шагом в рассматриваемом способе является уже не распространение переноса, а образование переносов нз каждых i-х разря,oI3 c÷àãàåìûõ в соседние (i + 1)-е разряды.

Обозначим переносы нз каждых 1-х разрядов в (»+ 1)-е разряды через Р«, ц, тогда результаT второго шага можно записать следующим образом: п Ри ° 1 Р.з 4Р;»Р2 1 (2)

15 В описываемом способе первый, и второй шаг параллельны и описываются простыми уравнениями с аргументами, относящимися к одному разряду.

Полученные величины записывают так, что20 бы одноименные разряды оказались друг под другом. дополнив при этом величину (1) разрядом q„+1, а величину (2) разрядом P,:

q„ + 1 q„ q„ — 1 q1

25 Р, »Р„Р,, 1... Ð1

Как можно видеть из способа образования величин (1) и (2), q, »» P1 всегда имеют нулевое значение, так как образующие их разряды слагаемых А и .1> фактически не сущест30 в уют.

176724

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

Составитель Б. Тимохин

Корректоры: Т. Н. Костикова и Л. Е. Марисии

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

Редактор Л. Утехина

Заказ 712, 19 Тираж 976 Формат бум 60)<90 /„Сбз ем 0,21 изд. л. Цена 5 коп.

ЦНИИПИ Государственного комитета по делам изобретений и открытий СССР

Москва, Центр, пр. Серова, д. 4

Типография, пр.

Сапунова, 2

Если дг есть единица. то Р; ь ««««««согда не может быть, ед««««ицей, поскольку они образуются одними и теми же разрядами слагаемых

А и В (a,- Ф гг,7 при помощи соответственно логической,«щррации неравнозначности и лог««ческого 3 мно>кения, которые не имеют значений, раты1ьтх единице на одинаковых наборах. Поэтому мо«кно утверждать, что одновременно в i-x и (i+1)-х разрядах величин (1) и (2) единицы встретиться не могут.

Тогда, если в i-x разрядах (1) и (2) одновременно содержатся единицы, то в ближайших старших разрядах величин (1) и (2) может наблюдаться только один из следующих двух случаев: дг+«=0 и P;+« --0; рг+«=1 и Рг+«=О.

Два других случая исключаются согласно изложенному.

Если имеет место первый случай, то в (i+2)-х разрядах может наблюдаться любая комбинация единиц и нулей.

Во втором случае в (i+2)-х разрядах оудут опять иметь место вышеуказанные первый или второй случаи и т. д.

Дальнейшее описание способа для большей наглядности продолжим на примере. Допустим, . А = 101 101 011 010 111 010 1

В = 110 Oll 010 101 011 001 0 (3)

Как уже известно, первыми двумя шагами нужно получить сумму по mod 2 чисел А и В и переносы из каждых i-x разрядов А и В в (i + 1) -е разряды. Получим эти величины и запишем их аналогично (3)

001 111 000 111 110 001 11

100 001 010 000 011 000 00 (4)

Рассматривая совместно величины (1) и (2), в общем случае можно выделить группы одноименных разрядов, которые начинаются комбинацией один — один и заканчиваются комбинацией поль — ноль. В приведенном примере из четырех таких групп две. Эти группы будем называть группами «первого типа». Все пары одноименных разрядов, которые не вошли в группы «первого типа», объединим в группы «второго типа». Группы «первого типа» включают в себя разряды, в которых происходит распространение переносов. В группах «второго типа» процесс распространения переносов не имеет места.

Окончательный результат, соответствующий группам «первого типа», можно получать од5

35 повременным инвер1ирова «ием всех разрядов величины (1), входящих в эти группы, а окончательный результат, соответствующий группам «второго типа», получается суммированием по mod 2 одноименных разрядов (1) и (2), входящих в эти группы. Окончательный результат, соответствующий рассматриваемому примеру, запишется следующим образом:

110 000 011 000 001 001 11 (5)

Может иметь место случай, когда нет HH одной пары одноименных разрядов, сог«ержащих одновременно единицы. Тогда группы

«первого типа» будут отсутствовать, а будет одна сплошная группа «второго типа».

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

Поскольку группы «первого типа» имеют четко выраженные начало и конец, то в описываемом способе опи выделяются одновременно, параллельно друг другу и, следовательно, для этого не требуется последовательного просмотра разрядов величин, которые разбиваются па группы. Группы «второго типа» при этом получаются автоматически.

Третий этап дает окончательный результат.

Для этого в группах «первого типа» достаточно инвертировать одновременно все разряды величины (1), а в группах «второго типа» произвести суммирование по mod 2 одноименных разрядов величин (1) и (2).

Способ сложения двоичных чисел, от.гичаюгчийая тем, что, с целью ускорения процесса суммирования, формируют два слова: сумму по модулю 2 исходных слагаемых и конъюнкцию исходных слагаемых со сдвигом на один разряд влево, после чего одноименные разряды полученных слов разбивают на группы так, что группы первого типа ограничены справа комбинацией вЂ, а слева — первой же комби1

0 нацией —, оставшиеся же разряды ооразуют

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