Сумматор кодов Фибоначчи Советский патент 1982 года по МПК G06F7/49 

(54) СУММАТОР КОДОВ ФИБОНАЧЧИ

Изобретение относится к автоматике и вычислительной технике и быть использовано в специгшизированных вычислительных{Машинах.

Известны устройства для cyMWipoван.ия кодов Фибоначчи, котоЕя е содержат последовательно соединенные многоразрядный полусумматор, блок перезаписи информации, нормгшизатор ij.

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

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

с входами (EtT)-ro и (в+2)-го одноразрядных сумматоров 2j.

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

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

Поставленная цель достигается тем, что сумматор кодов Фибоначчи, содер|жащий одноразрядные двоичные сумматоры и элемент ИЛИ, причем первый и входы слагаемых казкдого в-го одноразрядного сумматора подключены, соответствен но,Тс шинам первого и второго слагаемых устройства, первый вход переноса. 6 -го одноразрядного суиЛкатора пб ключен к первому переноса (f-l)-ro одноразрядного сумматора,

10 второй вход переноса 6 -го одноразрядного сумматора подключен ко второму выходу переноса (Вt2)-ro одноразрядного сумматора, выход су|«4ы е-го одноразряднохч} cyNMaTopa подключен к шине суммы, контрольный выход в-го одноразрядного двоичного сукматсра подключен к 6 -му входу эле1юнта ИЛИ, выход которого является выходом контроля, содержит трехвходо-20вой одноразрядный д1воич1Шй сумматор, первый и второй входы слагаемых которого подключены соответственно К шингш первого и второго слагаемз1Х, вход переноса подключен к третьег у

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

30 первому входу элт1емёнта ИЛИ, третий вход переноса Р -го одноразрядного сумматора подключен к третьему выходу переноса ft-2)-го одноразрядног сумматора. Одноразрядный двоичный сгумматор содержит трехвходовой одноразрядный двоичный сумматор, элементы ИЛИ, элементы И и элементы НЕ, причем первый и второй входы слагае1 ых трех входового одноразрядного двоичного сумматора являются соответственно, первым и вторым входами слагаемых од норазрядного двоичного сумматора, вход переноса трехвходовог-о одноразрядного двоичного сумматора подключен к выходу первого элемента ИЛИ, первый и второй входы которого соединены с первым и вторым входами пер вого элемента И, соответственно, и являются первым и третьим входами переноса одноразрядного двоичного сумматора, выход первого элемента И является контрольным выходом одноразрядного двоичного сумматора, выход суммы трехвходового одноразрядного двоичного сумматора подключен ко входу первого элемента НЕ, к первым входам второго, третьего и. четвертого элементов И и к первому вход второго элемента ИЛИ, выход первого элемента НЕ соединен с пергалми входа ми пятого и шестого элементов И, выход переноса трехвходового одноразря ного двоичного сумматора подключен к входу второго элемента НЕ, ко вторым входам третьего и шестого элементов И и к первому входу седьмого элемента И , выход второго элемента НЕ под ключен ко вторым входам второго, чет вертого и пятого элементов И, третьи входы третьего, четвертого и пятого элементов И подключены ко второму входу второго элемента ИЛИ и ко вход третьего элемента НЕ, выход которого соединен с третьими входами второго и шестого элементов И, вход третьего элемента НЕ является вторым входом переноса одноразрядного двоичного сумматора, выходы второго, третьего и пятого элементов И подключены, соответственно, к первому, второму и третьему входам третьего элемента ИЛИ, выход которого является выходом суммы одноразрядного двоичного сумматора, выходы четвертого и шестого элементов И подключены, соответственно, к первому и второму входам четвертого элемента ИЛИ, выход которого является первым выходом переноса одноразрядного двоичного сумматора и подключен к первому входу пятого элемента ИЛИ, выход второго элемента ИЛИ подключен ко второму входу седьмого элемента И, выход которого является вторым выходом переноса одн разрядного двоичного сумматора и под ключен ко второму входу пятого элемента ИЛИ, выход которого является ;третьим выходом переноса одноразрядного двоичного сумматора, В результате на вход каждого Е-го одноразрядного сумматора подаются пять сигналов. Одновременно единичные значения принимать могут только че- . тыре из них, так как спагаемле поступают на вход сумматора в нормальной форме, т.е. в двух соседних разрядах кода слагаемого одновременно не могут находиться единицы, в результате одновременно не могут возникнуть переносы в 6 -и разряд из (6-1)-го и (8-2)-го разрядов. Суммирование в В -м одноразрядном двоичном сумматоре происходит следующим образом: если на входах сумматора единичных сигналов нет, то единичные сигналы переносов в другие разряды не возникают, и формируется нулевой сигнал суммл в разряде; если на входах сумматора один единичный сигнал, то единичные сигналы пере.носов не позникают, формируется единичный сигнал суммы в разряде; если на входах сумматора два единичных сигнала, то формируются единичные ,сигналы переносов в (-«-1)-й и в (г-2)-й разряды и нулевой сигнал сумлы в данном разрядеJ если на входах сумматора три единичных сигнала, то формируются единичные сигналы переносов в (0+2)-й и (е-23-й разряды и нулевой сигнал сумглл в данном разряде; если на входах сумматора четыре единичных сигнала, то формируются единичные сигналы переносов в (-«-2)-й и СС-2)-й разряды и единичный сигнал сумг«л в данном разряде. В таблице представлены показатели, поясняющие работу 6 -го одноразрядного сумматора S р , Ре«.ё1 Sg .J:i i-J:i При составлении таблицы полагалось, что на входы трехвходового одноразрядного двоичного сумматора :НбДаются сигналы суммируемых цифр IB данном разряде ag,bg и сигнал Рен.е f-rei де Pg-.e - сигнал пере носа из (Р-1)-го разряда в ь -и раз ряд; Pj.5 J - сигнал переноса из (в-2) го разряда в В -и разряд. В таблице обозначено: S - сигнал суммы трехвходового одноразрядного двоичного сумматора; Р - сигнал пер носа трехвхоДового одноразрядного двоичного сумматора; Pt42e сигнал переноса в t -и разряд из (2+2)-го разряда; Sg - сигнал суммд одноразрядного сумматора; f.e+i. Рг, Ре,г-2 сигналы переноса из с -го разряда со ответственно в (Й+1)-й, (+2)-й, (Р-2)-й разряды. На основе анализа приведенной таблицы запишем логические функции, реализуемые одноразрядным двоичным сумматором. Se spPe,2.eV sPPf.j.e v spp.jf, SPPe.;.eVSPPe,2.e Pe,.2,eVS), Pe,,e4iVPg j+2 Кроме функций суммирования в одноразрядном сумматоре реализуется функция контроля Kj Р.,,С Ре-2.Р где Kg - сигнат ошибки, которая следует от невозможности одновременного появления переносов из )-го и (-2)-го разрядов вв,-й. На основе данной логики строится сумматор Фибоначчи. На фиг. 1 приведена структурная схема сумматора кодов Фибоначчи; на фиг. 2 - функциональная схема одноразрядного сумматора. Сумматор кодов Фибоначчи содержит трехвходовой одноразрядный двоич1е2й сумматор 1,п ((n+l) - число разрядо суммируемых кодов} одноразрядных дво ичных сумматоров 2,«элемент ИЛИ 3 на (п+1) входов 4. Трехвходовой однораз рядный двоичный Сумматор 1 предназна чен для суммирования цифр нулевого разряда кодов Фибоначчи и переноса, который может возникнуть из третьего разряда Фибоначчиевого кода с весом 2 при суммировании. Шход переноса трехвходового одноразрядного двоичного сумматора служит для фиксации сшибки. Одноразрядный сумматор. 2 слу жит для суммирования сигналов п ереносов и цифр cлaгae лыx в данном разряде, а также для фиксгщии ошибки в работе сумматора кодов Фибоначчи. ;Элемент ИЛИ 3 предназначен для сборк сигналов контроля К j (Р « 0,1.... .h) ;0т всех одноразрядных суьмат1И ов и трехвходового одноразрядного двоичного сумматора и формирования общего сигнала ошибки К в работе cyм(aтopд кодов Фибоначчи. На фиг. 1 не показаны нейспельзуе«ле выходы и входы п-го (n-l)-ro первого и второго одноразрядных сумматоров 2. Одноразрядный сумматор 2 содержит трехвходовой однор азрядный двончный сумматор 5/ три элемента НЕ 6-8,пять трехвходовых элементов И 9-13, первый и второй двухвходовые элемента И 14 |и 15, трехвходовый элемент 1ШИ, 16 четыре двухвходовых элемента ИЛИ 1720, предназначенные дпя реализации логических, функций. в c,f4i t.e-г , е Устройство работает следующим образом. Одновременно на входы слагаемых устройства поступают коды Фнбоначчи В нормальной форме (А и В): А а„а„.а V В - Ьд .2 ... ,, где а , t - двоичные цифры в 1-м разряде кода ,1,...., п). Формируются переносы в каждсж одноразрядном су 4маторе 2 и первая промежуточная сумма, затем осуществляется подсукмирование п еносов, образование второй промежуточной суммы и новых переносов. И так до тех пор, пока не прекратнтся образование пе носов и на выходах сумматоров 2 и 1 не образуется ксп суммы я в-4 «-7 .г где S - двоичные цифры в i-м разря- , да кода (,1,...,п). .В дальнейшем этот код переписывается из сукматора на нормализатор, где с покюс1ью операции свертки про- . . исходит нормализация кода результат та. Если при сумкшровании нарушено контрольное соотношение, то форкдаруется соответствующий единичный сигнал Kj, который поступает на элекюнт ИЛИ 3 и пороящает на его выходе единичное знечение, т.е. формируется сигнал ошибки К. При этом сигналошибки Кдформ1фуется исходя из того, что суммируемое коды находятся в нормальной форме, и в их нулевых разрядах должны быть нули, а следовательно, единичный сигнал на выходе переноса трехвходового двоичного одноразрядного сумматора 1 сигнализирует об ошибке... Пример сложения: А В 000101010101000 Веса разрядов Фибоначчиевого кода610 377 233 144 89 55 34 О О 010 10 О О О 1010 Первая промежуточная суммаО О О 00 00

Возниюиие переносы

Вторая промежуточная сумма 1 О 0010 Код суммы D лак ном случае код суммы получился в нормализованной форме.Сложение выполне но посредством трех циклов суммирования,

00010101010 00010101010 0000000 о Первая промежуточная сумма Возникшие переносы

О о

Код суммы код суммы получен в ненормализированной форме, поэтому необходимо

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

1 о о о А 1 О О О в: 1 1 11

010

1-1111111

(

В данном сумматоре кодов Фибоначчи формируется частично нормализованный код суммл вместо ненормализованногОг как это имеет место в из45 ;вестных сумматорах, в результате че21 13 8 5 3 2 1 1 10101000 А 10101000В 000000 10100010 Рассмотрим сложение этих же чисел А и В в известном сумматореооиоооо 1 1 1 .произвести нормализацию резульго, возрастает среднее быстрсщействие сумматора. Формула изобретения 1.Сумматор кодов Фибоначчи, содер жащий бднораэрядные сумматоры и элемент ИЛИ , причем первый и второй вхо ды слагаекых каждого 2 -го одиораэрядного сумматора подключены к шинам первого и второго слагаемых соответственно, первый вход переноса 6 -го одноразрядного сумматора подключен к первому выходу переноса (6-1)-го одноразрядного сумматора, второй вход переноса 8-го одноразрядного сумматора подключен ко второму выходу переноса (t2) -го одноразрядного сумматора, быход суммы в -го однораз рядного сумматора подключен к шине суммл, контрольный выход 6 -го одно разрядного сумматора подключен к -му входу элемента ИЛИ, выход которого является выходом контроля, от личающийся тем, что, с целью повьйцения &1стродействия, он содержит трехвходовой одноразрядный двоичный сумглатор, первый и второй входы слагаемых которого подключены соответственно к итнам йервого и вто рого слагаемых, вход переноса подключен к третьему выходу переноса второго одноразрядного сумматора, выход суммы трехвходового одноразрядного двоичного сумматора подключен к ишне суммы а выход переноса подключен к первому входу элемента ИЛИ, третий вход переноса -г одноразрядного сумматора подключен к третьему выходу переноса (Й-2)-го одноразрядного сукматора. 2. Сумматор по п,1, о т л и ч а ю щ и и с я тем, что, одноразрядный сумматор содержит трехвходовой одноразрядный двоичный сумматор,элементы ИЛИ, элементы. И и элемен- НЕ, причем первый и второй входы слагавмых трехвходового одноразрядного двоичного сумматора являются соответ ственно первым и вторым входами слагаемых одноразрядного сумматора,вход .переноса трехвходового одноразрядног двоичного сумматора подключен к выхо ду первого элемента ИЛИ, первый и вт рой входы которого соединены соответ ственно с первым и вторым входами первого элемента И и являются первым и третьим входами переноса одноразрядйого сумматора соответственно, Выход первого элемента И является контрольным выходом одноразрядного сумматора, выход сумил трехвходового од норазрядного двоичного сумматора подключен ко входу первого элемента НЕ, к первым входсш второго, третьего и четвертого элементов И. и к первому входу второго элемента ИЛИ, выход первого элемента НЕ соединен с первыми входами пятого и шестог о элементов И, выход переноса трехвходового одноразрядного двоичного сумматора подключен ко входу второго элемента НЕ, ко вторым входам третьего и шестого элементов И и к первому входу седьмого элемента И, выход второго элемента НЕ подключен ко вторым входш второго, четвертого и пятого элементов И, третьи входы третьего, четвертого и пятого элементов И подключены ко второму входу второго элемента ИЛИ и ко входу третьего элемента НЕ, выход которого соединен с третьими входами второго и шестого элементов И, вход третьего элемента НЕ является втсчым входом переноса одноразрядного сумматора, выходы второго, третьего и пятого элементов И подключены соответственно к первому, второму и третьему входам третьего элемента ИЛИ, выход которого является выходом одноразрядного сумматора, выходы четвертого и шестого элементов И подключены соответственно к первому и второму входам четвертого элемента ИЛИ, выход которого является первым выходом переноса одноразрядного сумматора и подключен к первому входу пятого элемента ИЛИ, выход второго элемента ИЛИ подключен ко второму входу седьмого элемента И, выход которого является вторым выходом переноса одноразрядного сумматора и подключен ко второму входу пятого элемента ИЛИ, выход которого является третьим выходом переноса одноразрядного суьматора. Источники информации, принятые во внимание 1ри экспертизе 1.Авторское свидетельство СССР №732864, кл. G 06 F 7/49, 1980. 2.Стахов А.П. Введение в алгоритмическую теорию измерения, М., Советское радио, 1977, с. 132-138 ; (прототип).

11н Лг,

T1 r ГП I

Sn-t

Hn-t Л-/.%1