Комбинационный сумматор кодов фибоначчи

.В. Харламов и А.С, Ша етельство СССР6 Г 7/49, 1987.детельство СССР Е 7(49, 1981,ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(54) КОМБИНАЦИОННЫЙ СУММАТОР КОДОВ ФИБОНАЧЧИ(57) Изобретение относится к автоматике и вычислительной технике и может быть использовано для параллельного суммирования многоразрядных двоичных чисел, Цель изобретения - сокращение аппаратурных затрат, Сумматор содержит в каждом разряде пятый элемент ИЛИ 10, элемент 11 запрета, четвертый элемент НЕ 12, первый и второй элементы НЕ 13 и 14, пятый элемент НЕ 15, третий элемент НЕ 16, первый и второй элементы ИЛИ 17 и 18, первый и второй элементы И 19 и 20, элементы ИСКЛЮЧАЮЩЕЕ ИЛИ 21, с третьего по шестой элементы И 22 - 25, третий и четвертый элементы ИЛИ 26 и 27 со связями, 1 ил.10 20 25 30 35 40 45 50 55 эом. Изобретение относится к области вычислительной техники и может быть использовано для параллельного суммирования многоразрядных двоичных чисел,Целью изобретения является сокращение аппаратурных затрат.На чертеже представлена схема- го разряда комбинационного сумматора кодов Ф ибо наччи.- й разряд сумматора содержит выход 1- го разряда выхода суммы сумматора, вход 2 -го разряда входа первого слагаемого сумматора, вход 3 ( + 1)-го разряда входа , первого слагаемого сумматора, вход 4 -го разряда входа второго слагаемого сумматора, вход 5 ( - 1) - го разряда входа второго слагаемого сумматора, вход 6 переноса из ( - 1)-го разряда сумматора., вход 7 переноса из (+ 2) - го разряда сумматора, выход 8 переноса в (+ 1)-й разряд сумматора, выход 9 переноса в ( - 2)-й разряд сумматора, пятый элемент ИЛИ 10, элемент 11 запрета, четвертый элемент НЕ 12, первый и второй элементы НЕ 13 и 14 соответственно, пятый элемент НЕ 15, третий элемент НЕ 16, первый и второй элементы ИЛИ 17 и 18 соответственно, первый и второй элементы И 19 и 20 соответственно, элемент ИСКЛЮЧАЮЩЕЕ или 21, с третьего по шестой элементы И 22-25 соответственно, третий и четвертый элементы ИЛИ 26 и 27 соответственно.Любое натуральное п-разрядное число А в кодах Фибоначчи представляется в видеи - 1 многочлена А =у где а (0,1) и=оОприО, ф) 1 при=Оу( - 1) + у( - 2) при0 (1)Предлагаемый способ сложения основан на соотношениях:р+ Р =р(+ 1)+ р( - 2) (2)Ф+Р(- 1)=р(+ 1) (3) вытекающих из рекурентного соотношения (1),В сумматоре кодов Фибоначчи форми. руется частично нормализованный,код суммы.Из сказанного вытекает алгоритм сложения чисел в кодах Фибоначчи: образование промежуточной суммы и сигналов переноса; суммирование промежуточной суммы и сигналов переноса; повторение указанных пунктов до тех пор, пока промежуточная сумма не станет эквивалентна окончательной.Сущность изобретения состоит в реализации выражений (2) и (3),Сумматор работает следующим обраНа входы 2-7- го разряда сумматора подаются шесть сигналов. Одновременно единичными могут быть только три из них, так как слагаемые поступают на входы сумматора в нормализованной форме, т. е. в двух соседних разрядах кода слагаемого одновременно не могут находиться единицы, в результате этого не может быть единичных сигналов одновременно на следующих входах: ( + 1) - го и- го разряда первого слагаемого; -го и ( - 1)-.го разряда второго слагаемого;- го разряда первого слагаемого и на входе переноса из- 1)-го разряда; ( - 1) - го разряда второго слагаемого и навходе переноса из( -1)-го разряда; (+ 1)-го разряда первого слагаемого и на входе переноса из (+ 2)-го разряда.Суммирование в- ом разряде сумматора происходит следующим образом.Если на его входе единичных сигналов нет или есть единичные сигналы на входах ( + 1) - го разряда первого слагаемого или ( - 1)-го разряда второго слагаемого, то единичные сигналы переносов в другие разряды не возникают и формируется нулевойсигнал суммы в разрядеЕсли есть только один единичный сигнал, но он находится на входе ( + 1)-го разряда первого слагаемого или ( - 1) - го разряда второго слагаемого, то возникает только один единичный сигнал - на выходе суммы -го разряда,Если на входах 1-го разряда первого и второго слагаемых единичные сигналы, а на остальных нули, то формируются единичныесигналы переносов в ( + 1) - й и в ( - 2)-й разряды и нулевой сигнал суммы в данном разряде,Если единичные сигналы только на входах -го первого разряда первого слагаемого и ( - 1)-го разряда второго слагаемого, то формируется единичный сигнал переноса в ( + 1)-й разряд и нулевые сигналы суммы в данном разряде и переноса в( -2)-й разряд.Если есть единичные сигналы только на входах слагаемых -го разряда и входе переноса из (+ 2)-го разряда, то формируются единичные сигналы переносов в (+ 1)-й и ( - 2)-й разряды и единичный сигнал суммы данного разряда.Если единичные сигналы только на входах- го разряда первого слагаемого, ( - 1) - го разряда второго слагаемого и входе переноса из ( + 2)-го разряда, то формируются единичные сигналы переноса из ( + 1)-й разряд, суммы в данном разряде и нулевой сигнал переноса в ( - 2) - й разряд,Если только на входах -х разрядов первого и второго слагаемых есть единичный сигнал и есть сигнал переноса из ( - 1)-горазряда, то возникают единичные сигналы ряда сумматора соединен с первым входом переносов в ( + 1) - й и ( - 2) - й разряды. третьего элемента ИЛИ того же разрядаРассмотрим работу разряда сумматора сумматора, выход элемента ИСКЛЮЧАЮ- на примере. ЩЕЕ ИЛИ разряда сумматора соединен сДопустим, есть единичные сигналы на 5 первым входомтретьего элемента Итогоже входах -х разрядов обоих слагаемых и пе- разряда сумматора, выход четвертого реноса из(+2)-го разряда, тогда на выходе элемента ИЛИ ( + 2)-го разряда сумма- элемента 11 запрета будет единичный сиг- тора( =1- п, и - разрядность кода) соединал, на втором и третьем входах элемента нен с вторым входом второго элемента И ИЛИ 17 установятся единичные сигналы, на 10 -го разряда сумматора, выход третьего элевыходе элемента ИЛИ 17 и на первом входе мента ИЛИ К-го (К = 1 - и - 1) разряда сумма- элемента И 24 установятся "1", на втором и тора соединен с первым входом первого третьем входах элемента И 24 тоже будут . элемента ИЛИ(К+1)-го разряда сумматора, "1", В результате на выходе элемента ИЛИ о т л и ч а ю щ и й с я тем, что, с целью 27 установится единичный сигнал, значит 15 сокращения аппаратурных затрат, каждый появится."1" на входе элемента ИЛИ 26 и на разряд сумматора содержит четвертый и пявыходах переносов появятся единичные тый элементы НЕ,элементзапрета, причем сигналы. На входах элемента ИСКЛЮЧАЮ- выходы четвертого и пятого элементов НЕ ЩЕЕ ИЛИ 21.будут единицы, на его выходе разряда сумматора соединены соответст- "0", который инвертируется в элементе НЕ 20 венно с вторым и третьим входами третьего 16 и на втором входе элемента И 25 будет элемента И того же разряда сумматора, вы- "1", на третьем входеэлемента И 25 устано- ход которого соединен с третьим входом вится единичный сигнал, который проходит пятого элемента ИЛИ того же разряда сумчерез элемент ИЛ И 18, так как на его втором матора, выход элемента запрета соединен с входе установлена "1". На первый вход зле входом первого элемента НЕ, с вторыми мента И 25 единичный сигнал подается от входами первого элемента ИЛИ и четвертозлемента НЕ 14, где инвертируется нулевой го элемента И, с первым входом элемента сигнал, В результате на всех трех входах ИСКЛЮЧАЮЩЕЕ ИЛИ того же разряда элемента И 25 устанавливаются "1", т, е. на сумматора, выход которого соединен с вхоего выходе тоже будет единичный сигнал, 30 дом третьего элемента НЕ того же разряда который пройдет через элемент ИЛИ 10 и сумматора, второй вход второго элемента И установится на выходе суммы- го разряда, . разряда сумматора соединен с вторымиФ о р м у л а и 3 о б р е т е н и я входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ и Комбинационный сумматор кодов Фи- пятого элемента И того же разряда суммабоначчи, содержащий в каждом разряде с 35 тора, вход разряда входа первого слагаемопервого по третий элементы НЕ, с первого го сумматора соединен с входом четвертого по шестой элементы И, с первого по пятый элемента НЕ, с третьим входом первого элеэлементы ИЛИ и элемент ИСКЛЮЧАЮЩЕЕ мента ИЛИ, с первыми входами второго эле- ИЛИ, причем выход первого элемента НЕ мента ИЛИ и первого элемента И разряда сумматора соединен с первым вхо соответствующего сумматора, вход разряда дом второго элемента И того же разряда входа второго слагаемого сумматора соедисумматора,выходкоторогосоединенспер- нен с информационным входом элемента вым входом пятого элемента ИЛИ того же запрета соответствующего разряда сумма- разряда сумматора, выход которого являет- тора, вход (К+ 1) - го разряда входа первого ся выходом соответствующего разряда вы слагаемого сумматора соединен с управляхода суммы сумматора, выход второго ющимвходомэлементазапретаК-горазряэлемента НЕ разряда сумматора соединен с да сумматора, вход второго элемента НЕ первыми входами пятого и шестого элемен- (К + 1)-го разряда сумматора соединен с тов И того же разряда сумматора, выход входом К-го разряда входа второго слагаетретьего элемента НЕ разряда сумматора 50 мого сумматора, второй вход первого элесоединен с вторым входом шестого элемен- мента И разряда сумматора соединен с та И того же разряда сумматора, выход ко- третьим входом второго элемента И того же торого соединен с вторым входом пятого разряда сумматора и с входом второго элеэлемента ИЛИ того же разряда сумматора, мента НЕ того же разряда сумматора, вход выход второго элемента ИЛИ разряда сум пятого элемента НЕ разряда сумматора соматора соединен с первым входом четвер- единен с вторым входом второго элемента того элемента И того же разряда сумматора,ИЛИ того же разряда сумматора и с первым выход которого соединен с первым входом входом первого элемента ИЛИ того же разчетвертого элемента ИЛИ того же разряда ряда сумматора, выход которого соединен с сумматора, выход первого элемента И раз- . третьим входом пятого элемента И того же1667052 Составитель А. Клюев Техред М.Моргентал Корректор.О, Кравцова Редактор О. Спесивых Заказ 2524 Тираж 397 Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж, Раушская наб., 4/5 Производственно"издательский комбинат "Патент", г, Ужгород, ул,Гагарина, 101 разряда сумматора, выход второго элемента ИЛИ разряда сумматора соединен с третьим входом шестого элемента И того же разряда сумматора, выход второго элемента НЕ разряда сумматора соединен с третьим входом четвертого элемента И того же разряда сумматора, выход пятого элемента И разряда сумматора соединен с вторым входом четвертого элемента ИЛИ того же разряда сумматора, выход которого соеди нен с вторым входом третьего элементаИЛИ того же разряда сумматора,