Параллельный сумматор кодов фибоначчи Советский патент 1981 года по МПК G06F7/49 

1

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

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

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

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

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

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

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

Поставленная цель достигается

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

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

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

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

Устройство работает следующим образом.

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

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

разряде второго регистра 3 находится единица, а в irM разряде первого регистра 1 - нуль, посредством блока элементов И 4, происходит перезапись единицы из i -го разряда второго ре-; гистра 3 в t-и разряд первого регистра 1, При этом1-й разряд второго регистра 3 устанавливается в нуль. Процессы приведения к минимальной форме содержимого первого регистра 1 и перезапись единиц из разрядов второго регистра 3 в соответствующие раряды первого регистра 1 продолжаются до тех пор, пока содержимое второго регистра 3 не станет равным нулю, а содержимое первого регистра 1 не бу.дет представлено в минимальной форме. Это является признаком окончания суммирования, на основании которого 6j:oK 6 определения окончания суммирования вырабатывает соответствующий сигнал.

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

Пример . сложить числа А 1000100010 и В 1010010100. В соответствующие регистры слагаемые записываются в форме, отличной от минимальной: А 0110011001, В 0111101111. По приходу управ ляющего сигнала начинается процесс совместной нормализации.

А 001000100010 - второе слагаемое В 001010010100 - первое слагаемое

000110011001

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

OOOMiOOOlOOl

ooiifcriiiilii

000000001001 001111111111 t±J t±J

Ш

tu

ООООООООМ0.1 010101010TD11

ill OOOOOOOOOOOCh В 010101011100 U- А 000000000000 в/ 100000000101 ,™- ---- - -- - в 100000001000 - содержимое перво го регистра. Сложение закончено А+В В . Введение новых связей и представ ление .обоих слагаемых в специальной форме, отличной от нормальной, позволяет ускорить процесс суммировани и уменьшить количество оборудования В предлагаемом устройстве процесс суммирования протекает асинхронно и заключается в проведении ряда опера ций приведения к минимальной форме кода Фибоначчи одного из слагаемых с учетом другого слагаемого. Обозна чим через1 время,необходимое для выполнения одной элементарной сверт ки, т.е. когда код ...011... перехо дит в ...100... . Наиболее неблагоприятным с точки зрения быстродейст вия будет такое су «4ированиё, когда оба слагаемых представлены fe виде А 101010и В 101010 ... .Если обозначить через п длину кодовой комбинации, максимальное время суммирования можно выразить Т {2п-2) устройстве, наиболее близком к предлагаемому, процесс сум мирования протекает синхронно. Максимальное число тактов суммирова Длительность одного ния будет такта суммирования определяется по Бремени проведения максимальной свертки промежуточной суммы. Оно равно у ьа Тогда максимальное п1мя суммирования Р п 20 быстродействие предлагаемого устройства будет в 2,6 раза больше, чем известного. В предлагаемом устройстве параллельный полусумматор содержит элемент И и сумматор по MOдулю два в каждом разряде, кроме того на каждый разряд приходится .только один элемент И. Поэтому бно содержит оборудования на п сумматоров по модулю два меньше, чем известное. Таким образом, введение блоков элементов И и организация 1процесс9 суммирования как Процесса совместной нормализации кодов Фибоначчи двух слагаемых позволяют повысить быстродействие и уменьшить затраты оборудования. Формула изобретения Параллельный сумматор кодов Фибоначчи, содержащий первый и второй регистры, блок определения окончания суммирования, блок контроля и блок нормализации, выход которого соединен с первым входом первого регистРа, выход первого регистра соединен с первым входом блока нормализации, отличающийся тем, что, с целью повышения быстродействия и уменьшения количества оборудования, сумматор содержит блок элементов И, .причем первый вход i-ro элемента И ;блока соединен с нулевым выходом i-ro разряда первого регистра, первым входом блока контроля и первым входом блока определения окончания суммирования, второй вход 1-го элемента И блока соединен с единичным выходом i-ro разряда второго регистра, со вторым входом блока нормализации, вторым входом блока контроля и вторым входом блока определения окончания суммирования, третьи входы всех элементов И блока соединены иежду собой, с третьим входом блока нормализации и с шиной управления, а их выходы соединены со вторым входом первого регистра и входом второго егистра.. Источники информации, принятые во внимание при экспертизе 1.Авторское свидетельство СССР 570896, кл. 6 Об F 7/50, 1975. 2.Авторское свидетельство СССР 577528, кл. 6 06 F 7/50,.1976. 3.Авторское свидетельство СССР 558237, кл. G 06 F 7/50, 1976 (прототип).