Параллельный сумматор кодов фибоначчи

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

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

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

Республик

«iI84 0891

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. саид-ву— (22) Заявлено 150578 (23) 2617011/18-24 (53)М. Кл з

G F 7/49 с присоединением заявки ¹

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

СССР по делам изобретений и открытий (23) Приоритет

Опубликовано, 230681.Бюллетень № 23

Дата опубликования описания 230681 (53) УДК 681.325..5(088.8) A.II. Стахов, Н.A ° Соляниченко, В.А; Лужецкий, .А.Â. Оводенко и A.A. Козак (72) Авторы изобретения (7) ) Заявитель (54) ПАРАЛЛЕЛЬНЫЙ СУММАТОР КОДОВ ФИБОНАЧЧИ

Изобретение относится к вычислительной технике и может быть использовано для параллельного суммирования многоразрядных чисел, пре )ставленных в фибоначчиевой системе счип 3 ления.

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

Известен также накапливающий сумматор, содержащий триггеры со счетным )$ входом, сумматоры по модулю 2, элементы Й, элементы ИЛИ и элементы задержки и осуществляющий сложение мно гораэрядных чисел, представленных в фибоначчиевой системе счисления f2). 2О

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

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

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

Цель изобретения -" повышение быстродействия и-уменьшение количества оборудования.

Поставленная цель достигается тем, что параллельный сумматор кодов

Фибоначчи, содержащий первый и второй регистры, блок определения окончания суммирования, блок контроля и блок нормализации, выход которого соединен с первым входом первого ре840891 гистра, выход первого регистра соединен с первым входом блока нормализации, содержит блок элементов И, причем первый вход i-ro элемента И блока соединен с нулевым выходом

i-го разряда первого регистра, первым входом блока контроля и первым входом блока определения окончания суммирования, второй вход 1-ro элемента И блока соединен с единичным выходом

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

На чертеже приведена функциональная схема устройства.

Устройство содержит первый регистр

1, прецназначенный для хранения первого слагаемого в начале суммирования и конечного результата в конце суммирования, блок 2 нормализации, осуществляющий приведения кодов Фибоначчи к минимальной форме, второй регистр 3, предназначенный для хранения второго слагаемого, блок элементов И 4, обеспечивающий выполнение операции суммирования, блок 5 контроля, осуществляющий контроль в процессе суммирования и контроль конечного результата, блок б определения окончания суммирования, шина 7 управления. устройство работает следующим образом, Первое и второе слагаемое заносится в первый 1 и второй 3 регистры в форме, отличной от минимальной. В этой форме каждая единица исходного кода заменяется путем развертки двумя единицами в соседних младших разрядах. Подобную развертку легко осуществить схемотехнически. Информация о состоянии i-го разряда исходного кода заносится в (i-1) и (i 2)-й разряды регистра слагаемого. Например, входная шина, соответствующая разряду кода с весом "8"., заводится на входы разрядов регистра с весами

"5" и. "3". Тогда некоторый исходный код Фибоначчи ...100100100... после занесения в регистры слагаемого имеет .вид В.. 011011011 ° . .

После поступления сигнала на шину 7 управления начинается процесс приведения содержимого первого регистра 1 к минимальной форме с учетом содержимого второго регистра .3. Условие свертки для i-го разряда первого регистра 1 - наличие нуля в нем, единицы в (i i) и (i-2)-м разрядах первого регистра 1 и нуля в i-м разряде. второго регистра 3. Если в i-м

А = 0003 10001001

В = 001 1111111

A (!

В"=

000000001001

001111111111

ТИ

И

Ltd

00000000 001

010101010 11

)Й3

А lt

Вн

50 разряде второго регистра 3 находится единица, а в i;M разряде первого регистра 1 — нуль, посредством блока элементов И 4, происходит перезапись единицы из i-ro разряда второго ре-. гистра 3 в 1-й разряд первого регистра 1. При этом i-й разряд второго регистра 3 устанавливается в нуль.

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

Блок 5 контроля осуществляет контроль эа процессом суммирования и проверяет конечный результат на минимальность. Из свойства этого способа сложения вытекает следующая воэможность органиэации контроля правильности протекания процесса суммирования. Иризнаком нейравильного сложения является. наличие единицы в i-x разрядах первого и второго регистра . и нулей в (1-f) и (1+1) -х разрядах. обоих регистров °

Пример . Сложить числа А—

1000100010 и В 1010010100. В соответствующие регистры слагаемые записываются в форме, отличной от минимальной A = 01100 1001, В

0111101111. По приходу управляющего сигнала начинается процесс совместной нормализации.

А = 001000100010 — второе слагаемое

В = 001010010100 — первое слагаемое

A = 000110011001 - содержимое второго регистра

В = 000111101111 содержимое первого регистра

&40&91

A - =0000000000001

В" 010101011100

t2

Ж 2

Аип = 000000000000

В"" = 100000000101

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

10p0p0001000 — содержимое первого регистра.

Сложение закончено A+B = B

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

В предлагаемом устройстве процесс суммирования протекает асинхронно и заключается в проведении ряда операций приведения к минимальной форме кода Фибоначчи одного из слагаемых с учетом другого слагаемого. Обозначим черезов & время, необходимое для выполнения одной элементарной свертки, т.е. когда код ...011... переходит в ...100... . Наиболее неблагоприятным с точки зрения быстродействия будет такое суммироваиие, когда оба слагаемых представлены в виде

А = 101010 ....... и В = 101010 .Если обозначить через и длину кодовой комбинации, максимальное время суммирования можно выразить Т (2п-2) с&. В устройстве, найболее близком к йредлагаемому, процесс суммирования протекает синхронно.

Максимальное число тактов суммирования будет . Длительность одного такта суммирования определяется по времени проведения максимальной свертки прОмежудочной суммы. Оно равно -" Фь8 . Тогда максимальное speЬ суммирования Т = „. бои .При п = 20 быстродействие предлагаемого устройства будет в 2,6 раза больше, чем известного. В предлагаемом устройстве параллельный полусумматор содержит элемент И и сумматор по мо-, дулю два в каждом разряде, кроме того на каждый разряд приходится.только один элемент И. Поэтому 6но содержит оборудования на и сумматоров по модулю два меньше, чем извест ное.

Таким образом, введение блоков элементов И и организация;процесса суммирования как процесса совместной нормализации кодов Фибоначчи двух слагаемых позволяют повысить быстродействие и уменьшить затраты обо-!

О рудования

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

i-ro разряда первого регистра, первым входом блоха контроля и первым входом блока определения окончания

Зр суммирования, второй вход i-го элемен° та И блока соединен с единичным выходом i-го разряда второго регистра, ао вторым входом блока нормализации, вторым входом блока контроля и вторым

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

4р.выходы соединены со вторым входом первого регистра и входом второго регистра.

Источники информации, 45 принятые во внимание при экспертизе

1. Авторское свидетельство СССР

Р 570&96, кл. G 06 F 7/50, 1975.

2. Авторское.свндетельство СССР

50 В 577528, кл. 6 06 F 7/50, 1976.

3. Авторское свидетальство СССР 9 558237, кл. G 06 F 7/50, 1976 (прототип).

840891

Составитель Н. Слвсарев

Техред Н.Ковалева КорректорВ. ВутягФ

Редактор В. Лазаренко

Подписное

Заказ 4767/72 Тираж 745

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

113035, Москва, Ж-35, Раушская наб., д. 4/5 ( филиал IIIIII ."Патент",. г. ужгород, ул. Проектная, 4