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

ОПИСАНИЕ ИЗОБРЕТЕНИЯ Союз Советских Социалистических Республик(5 ЦМ. Кл.з 6 Об Г 7/49 с присоедииеиием заявки Йо Государственный комнтет СССР по делаи изобретений и открытий(54) ПАРАЛЛЕЛЬНЫЙ СУММАТОР КОДОВ ФИБОНАЧЧИ Изобретение относится к вычислительной технике и может быть использовано для параллельного суммирования многоразрядных чисел, представленных в фибоначчиевой системе счис . 5ления,Известен комбинационный сумматордля параллельного суммирования многоразрядных чисел., представленных вфибоначчиевой системе счисления, содержащий одноразрядные двоичные сумматоры, блок распределения сигналов,элементы И и ИЛИ 11.Известен также накапливающий сум"матор, содержащий триггеры со счетным 5входом, сумматоры по модулю 2, элементы Й, элементы ИЛИ и элементы задержки и осуществляющий сложение многораэрядных чисел, представленных вфибоначчиевой системе счисления Г 23. 20Недостатком известных сумматоровявляется низкое быстродействиеНаиболее близким по техническойсущности к предлагаемому являетсяпараллельный сумматор кодов фибоначчи, содержащий первый и второй регистры, параллельный полусумматор, блокопределения окончания суммирования,блок коммутации, блок контроля и блокормалиэации, причем выход суммы па 2раллельного полусумматора соединен с ,первым входом первого регистра и первым входом блока контроля, выход переноса параллельного полусумматора соединен со входом блока определения окончания суммирования и входом блока коммутации, первый и второй управляющие входы которого подключены к первой и второй управляющим шинам, выход блока коммутации соединен со входом второго регистра и с другим входом первого регистра, выход которого подключен также ко входу блока нормализации, управляющий вход которого подключен к первой управляющей шине, а выход соединен с третьим входом первого регистра 3,.Недостатками известного сумматора являются значительные затраты оборудования и низкое быстродействие.Цель изобретения -" повышение быстродействия и-уменьшение количества оборудования.Поставленная цель достигается тем, что параллельный сумматор кодов Фибоначчи , содержащий первый и второй регистры, блок определения окончания суммирования, блок контроля и блок нормализации, выход которого соединен с первым входом первого ре 840891А 1 В гистра, выход первого регистра соединен с первым входом блока нормализации, содержит блок элементов И,причем первый вход 1-го элемента Иблока соединен с нулевым выходом1-го разряда первого регистра, первымвходом блока контроля и первым входомблока определения окончания суммирования, второй вход 1-го элемента Иблока соединен с единичным выходом1-го разряда второго регистра, совторым входом блока нормализации,вторым входом блока контроля и вторым входом блока определения окончания суммирования, третьи входы всехэлементов И блока соединены междусобой, с третьим входом блока нормализации и с шиной управления, а ихвыходы соединены со вторым входомпервого регистра и входом второгорегистра.На чертеже приведена функциональная схема устройства.Устройствосодержит первый регистр1, прецназначенный для храненияпервого слагаемого в начале суммирования и конечного результата в концесуммирования, блок 2 нормализации,осуществляющий приведения кодов Фибоначчи к минимальной форме, второйрегистр 3, предназначенный для хранения второго слагаемого, блок элементов И 4, обеспечивающий выполнение операции суммирования, блок 5контроля, осуществляющий контроль впроцессе суммирования и контроль конечного результата, блок б определения окончания суммирования, шина 7управления.устройство работает следующимобразом,Первое и второе слагаемое заносится в первый 1 и второй 3 регистры вформе, отличной от минимальной. Вэтой форме каждая единица исходногокода заменяется путем развертки двумя единицами в соседних младших разрядах. Подобную Развертку легко осуществить схемотехнически. Информацияо состоянии 1-го разряда исходногокода заносися в (1-1) и (1-2)-й разряды регистра слагаемого. Например,входная шина, соответствующая разряду кода с весом "8"., заводится навходы разрядов регистра с весами"5" и. "3". Тогда некоторый исходныйкод Фибоначчи ..100100100 послезанесения в регистры слагаемого имеет.вид 011011011После поступления сигнала на шину 7 управления начинается процессприведения содержимого первого регист.ра 1 к минимальной форме с учетомсодержимого второго регистра 3, Условие свертки для 1-го разряда первого регистра 1 " наличие нуля в нем,единицы в (1-1) и (1-2)-м разрядахпервого регистра 1 и нуля в 1-м разряде. второго регистра 3. Если в 1-м разряде второго регистра 3 находится единица, а в 1;м разряде первого регистра 1 - нуль, посредством блока элементов И 4, происходит перезапись единицы из 1-го разряда второго ре-. гистра 3 в 1-й разряд первого регистра 1. При этом 1-й разряд второгорегистра 3 устанавливается в нуль.Процессы приведения к минимальнойформе содержимого первого регистра 1 и перезапись единиц из разрядов второго регистра 3 в соответствующие разряды первого регистра 1 продолжаютсядо тех пор, пока содержимое второгорегистра 3 не станет равным нулю, асодержимое первого регистра 1 не будет представлено в минимальной форме, Это является признаком окончаниясуммирования, на основании которогоблок б определения окончания суммирования вырабатывает соответствующийсигнал. Блок 5 контроля осуществляет контроль эа процессом суммирования и проверяет конечный результат на минимальность. Из свойства этого способа сложения вытекает следующая воэможность органиэации контроля правильности протекания процесса суммирования. Иризнаком нейравильного сложения является наличие единицы в 1-х разрядах первого и второго регистра и нулей в (1-1) и (1+1) -х разрядах, обоих регистров1 П р и м е р . Сложить числа А - 1000100010 и В1010010100. В соответствующие регистры слагаемые записываются в форме, отличной от минимальной А = 01100" 1001, В =0111101111. По приходу управляющего сигнала начинается процесс совместной нормализации.А = 001000100010 - второе слагаемое В = 001010010100 - первое слагаемое А = 000110011001 - содержимое второго регистраВ = 000111101111содержимое первого регистраФормула изобретения В= 100000001000 - содержимое первого регистра.Сложение закончено А+В = В Введение новых связей и представление, обоих слагаемых в специальной .Форме, отличной от нормальной, позволяет ускорить процесс суммирования и уменьшить количество оборудования. В предлагаемом устройстве процесс суммирования протекает асинхронно и заключается в проведении ряда операций приведения к минимальной форме кода Фибоначчи одного из слагаемых с учетом другого слагаемого. Обозначим черезов время, необходимое для выполнения одной элементарной свертки, т.е. когда код 011 перехо.дит в 100 . Наиболее неблагоприятным с точки зрения быстродействия будет такое суммироваиие, когда оба слагаемых представлены в виде А = 101010и В = 101010 .Если обозначить через и длину кодовой комбинации, максимальное время суммирования можно выразить Т(2 п)7 св, В устройстве, найболее близком к йредлагаемому, процесс суммирования протекает синхронно.Максимальное число тактов суммирования будет. Длительность одного такта суммирования определяется по времени проведения максимальной свертки прОмежуочной суммы. Оно равно Й ь" 8 . Тогда максимальное время суммирования Т, ,= -" Фу .При п = 20 быстродействие предлагаемого устройства будет в 2,6 раза больше, чем известного. В предлагаемом устройстве параллельный полусумматор содержит элемент И и сумматор по мо-, дулю два в каждом разряде, кроме того на каждый разряд приходится.только один элемент И. Поэтому 6 но содержит оборудования на и сумматоров по модулю два меньше, чем извест ное.Таким образом, введение блоков элементов И и организация, процесса суммирования как процесса совместной нормализации кодов Фибоначчи двух слагаемых позволяют повысить быстродействие и уменьшить затраты оборудования. Параллельный сумматор кодов Фибо наччи, содержащий первый и второйрегистры, блок определения окончания суммирования, блок контроля и баок нормализации, выход которого соединен с первым входом первого регист- Щ ра, выход первого регистра соединенс первым входом блока нормализации, о т л и ч а ю щ и й с я тем, что., с целью повышения быстродействия и уменьшения количества оборудования, сумматор содержит блок элементов И, ,причем первый вход 1-го элемента И блока соединен с нулевым выходом -го разряда первого регистра, первым входом блоха контроля и первым входом блока определения окончания ЗОсуммирования, второй вход 1-го элемен та И блока соединен с единичным выходом 1-го разряда второго регистра, со вторым входом блока нормализации, вторым входом блока контроля и вторым 35 входом блока определения окончаниясуммирования, третьи входы всех элементов И блока соединены ыежду собой, с третьим входом блока нормализации и с шиной управления, а их 4 о.выходы соединены со вторым входомпервого регистра и входом второго регистра. Источники информации,45 принятые во внимание при экспертизе1. Авторское свидетельство СССР9 570896,кл. 6 06 Г 7/50, 1975. 2. Авторское. свидетельство СССР50 В 577528, кл. 6 06 Г 7/50, 1976. 3. Авторское свидетальство СССРМ 558237, кл. С 06 Г 7/50, 1976840891 Заказ 4767/72 Тираж 745 ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 113035, Москва, Ж, Раушская наб., д. 4/