Сумматор кодов фибоначчи

ОПИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз СеаетскнзСоциалистическихРеспублик о 11981993(И М. Кл.э Ь 06 Р 7/49 с присоединением заявки МоГосударстаеннмй омнтет СССР но делам нзобретеннЯ н отрытнЯОпубликовано,15,1282. бюллетень Но 46 Дата опубликования описания 15. 12. 82(71 ) Заявител ТОР КОДОВ ФИБОНАЧЧ Изобретение относится к автоматике и вычислительной технике и может быть использовано в специализированных вычислительныхмашинах.Известны устройства дпя суммирования кодов фибоначчи, которые содер. жат последовательно соединенные многоразрядный полусумматор, блок перезаписи инФормации, нормалиэатор 11 . 10Недостатком данного устройства является сложность и большое количеотво , в среднем тактов но рмализации, что ведет к уменьшению быстродействия.Наиболее близким к изобретению .является устройство, содержащее и одноименных одноразрядных сумматоров, выход переноса с -го одноразрядного сумматора0 = 1,2,п) соединен с входами (3+1)-го и (6+2)-го одноразрядных сумматоров 2 .Недостатком этого устройства.является большое количество в среднем циклов сложения и тактов нормализации при приведении кода суюн к нормальной Форме, что снижает быстродей. ствие сумматора.Цель изобретения - повннение быст-, родействия.сумматора.Поставленная цель достигается тем, что суьиатор кодов фибоначчи, содер 1 жащий одноразрядные двоичные сумматоры и элемент ИЛИ, причем первый и второй входы слагаеннх каждого о -го одноразрядного сумматора подключены, соответственно,к шинам первого и второ- .го слагаеьнх устройства, первый вход пе реноса. с -го одноразрядного сумматора псЬключен к первому выходу переноса (-1)-го одноразрядного сумматора, второй вход переноса 3 -го .одноразрядного сумматора подключен ко втором выходу переноса (0 т 2)-го одноазрядного суюитора, выход суюн -го одноразрядного суиаатора подклю чен к шине суюн, контрольный выход -го одноразрядного двоичного сумеатора подключен к-му входу элемента ИЛИ, выход которого является вы ходом контроля, содержит трехвходовой однораэрядйый двоичный сумматор, первый и второй входы слагаевнх которого подключены соответственно к шинам первого и второго слагаемых, вход переноса подключен к третьему выходу переноса второго одноразрядного двоичного сумматора, выход сумин трехвходового одноразрядного двоичного сумматора подключен к шине сумнн, а выход .переноса подключен к первому входу элемента ИЛИ, третийвход переноса Е -го одноразрядного сумматора подключен к третьему выходу переноса (Е -2)-го одноразрядного сумматора.Одноразрядный двоичный сумматор содержит трехвходовой одноразрядный 5 двоичный сумматор, элементы ИЛИ, элементы И и элементы НЕ, причем первый и второй входы слагаемых трехвходового одноразрядного двоичного сумматора являются соответственно, 1 О первым и вторым входами слагаемых одноразрядного двоичного сумматора, вход переноса трехвходового одноразрядного двоичного сумматора подключен к выходу первого элемента ИЛИ, первый и второй входы которого соединены .с первым и вторым входами первого элемента И, соответственно, и являются первым и третьим входами переноса одноразрядного двоичного сумматора, выход первого элемента И является контрольным выходом одноразрядного двоичного сумматора, выход суммы трехвходового одноразрядного двоичного сумматора подключен ко входу йервого элемента НЕ, к первым входам второго, третьего и. четвертого элементов Й и к первому входу второго элемента ИЛИ, выход первого элемента НЕ соединен с первыми входами пятого и шестого элементов И, вы- З 0 ход переноса трехвходового одноразрядного двоичного сумматора подключен ко входу второго элемента НЕ, ко вторым входам третьего и шестого элементов И и к первому входу седьмого элемен та И , выход второго элемента НЕ подключен ко вторым входам второго, четвертого и пятого элементов И, третьи вх ды третьего, четвертого и пятого элементов И подключены ко второму 40 входу второго элемента ИЛИ и ко входу третьего элемента НЕ, выход которого соединен с третьими входами второго и шестого элементов И, вход третьего элемента НЕ является вторым входом пе-45 реноса одноразрядного дво чикаго сумматора, выходы второго, третьего и пятого элементов И подключены, соот" ветственно, к первому, второму и третьему входам третьего элемента ИЛИ, выход которого является выходом сумма одноразрядного двоичного сумматора, выходы четвертого и шестого элементов И подключены, соответственно, к первому и второму входам четвертого элемента ИЛИ, выход которого является первым выходом переноса одноразрядного двоичного сумматора и подключен к первому входу пятого элемента ИЛИ, выход второго элемента ИЛИ подключен ко второму входу 0 седьмого элемента И, выход которого является вторым выходом переноса одноразрядного двоичного сумматора и подключен ко второму входу пятого элемента ИЛИ, выход которого является 650 О О О О О О О 1 1 О О 1 О О 1О О 1 1 О О 1 1 О О 1 О О 1 О О 1 О 1 1 О 1 О 1 1 О О 1 1 При составлении таблицы полагалось, что на входы трехвходового одноразрядного двоичного сумматора третьим выходом переноса одноразрядного двоичного сумматора.В результате на вход каждого 3 -го одноразрядного сумматора подаются пять сигналов. Одновременно единичные значения принимать могут только че-, тыре из них, так как слагаете поступают на вход сумматора в нормальной форме, т.е. в двух соседних разрядах кода слагаемого одновременно не могут находиться единицы, в результате одновременно не могут возникнуть переносы в 3 -й разряд из (В - 1)-го и (6 -2)-го разрядов. Суммирование в Е -м одноразрядном двоичном сумматоре происходит следующим образом: если на входах сумматора единичных сигналов нет, то единичные сигналы переносов в другие разряды не возникают, и формируется нулевой сигнал сумма в разряде; если на входах сумматора один единичный сигнал, то единичные сигналы переносов не позникают, формируется единичный сигнал сумки в разряде; если на входах сумматора два единичных сигнала, то формируются единичные сигналы переносов в (8+1)-й и в (6-2)-й разряды и нулевой сигнал суюсь в данном разряде; если на входах сумматора три единичных сигнала, то формируются единичныесигнапы переносов в (8+2)-й и (6-2)-й разряды и нулевой сигнал суммю.в данном разряде; если на входах сумматора четыре единичных сигналато формируются единичные сигналы переносов в +2)-й и Я)-й азряды и единичный сигнал суммя в данном разряде.В таблице представлены показатели, поясняющие работу 3 -го одноразрядного сумматора:ббдаются сигналы суммируежх цифр 1 в данном разряде а,ЬЕ и сигнал Р. ЕЧ РЕ.7 Е, где РЕ. Е - сигнал переноса иэ (е)-го разряда в 1 -й разряд 1 РЕ.2 Е - сигнал переноса из (8-2) го разряда в 1 -й разряд.В таблице обозначено: Я - сигнал суюы трехвходового одноразрядного двоичного сумматора Р - сигнал пере носа трехвходового одноразрядного двоичного сумматора; Речуге - сигнал переноса в 6 -й разряд из (8+2)-горазрядае Бе - сигнал сумьи одноразрядного сумматора 1 РД,Ьф РЕЕа Е,Е.2" сигналы переноса иэ 1 -го разряда соответственно в (6+1)-й,(В+2)-й, Я)-й разряды.На основе анализа приведенной таблицы запишем логические функции, реализуемые одноразрядным двоичным сумматором. Е 5 РРЕ 2,ЕЧ 5 Е 2,Е Ч 8 РРЕег.еюРЕ,Е+1 =5 РРЕ 7,ЕЧ РРЕг,Еф Р е,е=Ре,е 41 ЧРе,е+2кроме функций суммирования в одноразрядном сумматоре реализуется функция контроля Ке = Ре-,е Ре-г.егде КЕ - сигнал ошибки, которая следует от невозможности одновременного появления переносов из (С)-го и (Е)-го разрядов в В, -й.На основе данной логики строится сумматор Фибоначчи.На фиг. 1 приведена структурная схема сумматора кодов Фибоначчй; на фиг. 2 - Функциональная схема одноразрядного сумматора.Сумматор кодов фибоначчи содержит трехвходовой одноразрядный двоичный сумматор 1, и и+1) - число разрядов суммируемых кодов) одноразрядных двоичных сумматоров 2,фэлемент ИЛИ 3 на (и+1) входов 4. трехвходовой одноразрядный двоичный сумматор 1 предназначен для суммирования цифр нулевого разряда кодов Фибоначчи и переноса, который может возникнутьиз третьего разряда Фибоначчиевого кода с весом ф 2" при суммировании. Выход переноса трехвходового одноразрядного двоичного сумматора служйт для Фиксации сшибки. Одноразрядный сумматор, 2 служит для суммирования сигналов переносов и цифр слагаемых в данномразряде, а также для фиксации ошибки в работе сумматора кодов Фибоначчи. :Элемент ИЛИ 3 предназначен для сборки сигналов контроля Х Е Щ 0,1 п) от всех одноразрядных сувваторов и трехвходового одноразрядного двоичного сумматора и формирования общего сигнала ошибки К в работе сумМатора кодов Фибоначчи. На фиг. 1 не показаны неиспользуемые выходы и входы и-го (и)-го первого и второго одноразрядных сумматоров 2.Одноразрядный сумматор 2 содержит трехвходовой одноразрядный двоичный сумматор 5, три элемента НЕ 6-8,пять трехвходовых элементов 1 9-13, первый ,и второй двухвходовые элементы И 14 и 15, трехвходовый элемент ИЛИ, 16 е четыре двухвходовых элемента ИЛИ 17- 20, предназначенные для реализации логических функций. 8 Е РЕ,ЕРЕ,Е РЕ,Е+г ф КЕУстройство работает следующим образом.Одновременно на входы слагае 7 нх устройства поступают коды фнбоначчи в нормальной Форме (А и В)е Аа,аеа.еае ае а В ф ь Ь,Ьз е е ьеЬ 1 Ьу где а, ь - двоичные цифры в 1-м разряде кода .(1 ф 0,1 и).формируются переносы в калщом одноразрядном суикаторе 2 и первая промежуточная сузаеа, затем осуществляется подсуммирование переносов, образование второй промежуточной сум мя и новых переносов. И так до тех пор, пока не прекратится образование переносов и на выходах сумматоров 2 и 1 йе образуется код суюсьй 14 з 2. 7 1 фф где Я- двоичные цифры в 1-м разря-, де кода (1 ф 01,п) . В дальнейшем этот код переписыва ется иэ суьиатора на нормалиэатор,.где с помощью операции свертки про-;исходит нормализация кода результат .та. Если при суммировании нарушеноконтрольное соотношение, то Формиру 5 О ется соответствующий единичный сигнал К, который поступает на элементИЛИ 3 и порождает на его выходе еди"ничное знечение, т.е. Формируетсясигнал окибки К. При этом сигнал сшибки Крформируется исхОдя из тогор чтОсумкйруеже коды находятся в нормальной форме, и в их нулевых разрядахдолжны быть нули, а следовательно,единичный сигнал на выходе переносатрехвходового двоичного однораэрядно О го сумматора 1 сигнализирует об ошибке.ПРимеР сложениЯ: А=В=000101010101000981993 Веса разрядовФибоначчневогокода 610 377 233 144 89 55 34 21 13 8 5 3 2 1 1 0 0 0 1 0 1 0 1 0 1 0 1 0 0 0 А0001010.10101000 Первая промежуточная сумма 000000000000000 Возникшие переносыЮ 1 1 1 1 1 Р1,Ьл 1 Р.Вторая промежуточная сумма 0 0 .1 0 1 01 010001010100010. Код суммы В данном случае код суммы получился внормализованной форме. Сложение выполне ЗОно посредством трех циклов суммирования,Рассмотрим сложение этих же чисел А и В в известном сум- маторе 0 0 0 1 0 1 0 1 0 1 0 1 0 0 0 АфО 0 0 1 .0 1 0 1 0 1 0 1 0 0 О В: Первая промежу- О 0 0 0 0 0 0 0 0 0 о 0 0 О 0точная сумма Возникшие переносы 1 1 1 1 1 1 1 Рг,Е 1;РЕ,Е-г 0 0 1 0 1 1 1 1 1 1 1 1 0 1 0 Код суммы Код суммы получен в ненормализиро-, .произвести нормализациюванной форме, поэтому необходимо тата: резуль 1 1 1 1 1, 0 1 0 1 1 1 1 0 1 О 11110 1 О 1 ОО 1 О 1 0 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 0 1 0 Таким образом, для,суммирования чисел А и В посредством ивестного сумматора .необходимы два цикла сужярования н четыре такта нормализации. 65 В данном сумматоре кодов Фнбоначчи формируется частично нормализованный код суммы вместо ненормализованного, как это имеет место в из,вестных сумматорах, в результате чеО О 1 д . Я 1 О 0 1 1 О О У 0 1 0 0 0 1 0 1010100101 1 1 1 е,вРе,е-г1 1 РЕ,Е+г9981993 го возрастает среднее быстродействие р сумматора. в Формула изобретения 1.Сумматор кодов Фибоначчи, содер жащий одноразрядные сумматоры и элемент ИЛИ, причем первый и второй входы слагаежх каждого-го одноразрядного сумматора подключены к шинам первого и второго слагаемых соответ ственно, первый вход переноса 3 -го одноразрядного сумматора подключен к первому выходу переноса 1-1)-го одноразрядного сумматора, второй вход переноса 1 -го одноразрядного 5 сумматора подключен ко второму выхо" ду переноса (0 Ф 2)-го одноразрядного сумматора, выход суюы 1 -гоодноразрядного сумматора подключен к шине суммю контрольный выход 1 го одно 2 разрядного суьиатора подключен к 3-му входу. элемента ИЛИ, выход. которого является выходом контроля, о тл и ч а ю щ и й с я тем, что, с целью Повышения быстродействия, он содержит трехвходовой одноразрядный двоичный сумматор, первый и второй входы слагаемых которого подключены соответственно к шинам первого и второго слагаемых, вход переноса подключен к третьему выходу переноса второго одноразрядного сумматора, выход суммы трехвходового одноразрядного двоичного сумматора подключен к шине суюы, а выход переноса подключен к первому входу эле меНта .ИЛИ, третий вход переноса 1 -гб одноразрядного сумматора подключен к третьему выходу переноса (О)-го одноразрядного. сумматора.2. Сумматор по п.1, о т л и ч а ю щ и й с я тем, что, одноразрядный сумматор содержит трехвходовой одноразрядный двоичный сумматор,элементы ИЛИ, элементы И и элементы НЕ, причем первый и второй входы слагаемых трехвходового одноразрядного двоичного сумматора являются соответственно первым и вторым входами слагаемых одноразрядного сумматора, вход переносатрехвходового одноразрядного двоичного сумматора подключен к выходу первого элемента ИЛИ, первый и вто. рой входы которого соединены:соответ-. ственно с первым и вторым входами первого элемента И и являются первым и третьим входами переноса одноразядного сумматора соответственно,ыход первого элемента И являетсяконтрольным выходом одноразрядногосумматора, выход сумы трехвходовогоодноразрядного двоичногб сумматораподключен ко входу первого элементаНЕ, к первым входам второго, третьего и четвертого элементов И.и к первому входу второго элемента ИЛИ, выход первого элемента НЕ соединен спервыми входами пятого и шестогоэлементов И, выход переноса трехвходового одноразрядного двоичного сумматора подключен ко входу второгоэлемента НЕ, ко вторым входам третьего и шестого элементов И и к первомувходу седьмого элемента И, выходвторого элемента НЕ подключен ковторым входам второго, четвертогои гятого элементов И, третьи входытретьего, четвертого и пятого элементов И подключены ко второму входувторого элемента ИЛИ н ко входу третьего элемента НЕ, выход которогосоединен с третьими входами второгои шестого элементов И, вход третьего элемента НЕ является вторым входом переноса одноразрядного сумматора, выходи второго, третьего и пятого элементов И подключены соответственно к первому, второму и третьему входам третьего элемента ИЛИ, выход которого является выходом сумиюодноразрядного сумматора, выходы четвертого и шестого элементов И подключены соответственно к первому ивторому входам четвертого элементаИЛИ, выход которого является первымвыходом переноса одноразрядного сумматора и подключен к первому входупятого элемента ИЛИ, выход второгоэлемента ИЛИ подключен ко второмувходу седьмого элемента И, выход которого является вторым выходом переноса одноразрядного сумматора и подключен ко второму входу пятого элемента ИЛИ, выход которого являетсятретьим вйходом переноса одноразрядного сумлатора. Источники информации,принятые во внимание рн экспертизе1. Авторское свидетельство СССРВ 732864, кл, 6 Об Р 7/49, 1980.2. Стахов А.П, Введение в алгоритмическую теорию измерения, М.,аэ 9712/68 Тирак 731 ВНИИПИ ГОсударственного коми по делам иэобретений и от 113035, Москва, Ж, Раущская