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

 

Изобретение относится к автоматике и вычислительной технике и может быть использовано для параллельного суммирования многоразрядных двоичных чисел. Цель изобретения - сокращение аппаратурных затрат. Сумматор содержит в каждом разряде пятый элемент ИЛИ 10, элемент 11 запрета, четвертый элемент НЕ 12, первый и второй элементы НЕ 13 и 14, пятый элемент НЕ 15, третий элемент НЕ 16, первый и второй элементы ИЛИ 17 и 18, первый и второй элементы И 19 и 20, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ 21, с третьего по шестой элементы И 22 - 25, третий и четвертый элементы ИЛИ 26 и 27 со связями. 1 ил.

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (я)з G 06 F 7/49

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4740391/24 (22) 25.09.89 (46) 30.07.91. Бюл, М 28 (72) А,В. Ткаченко, Д.В. Харламов и А.С, Шарафутдино в (53) 681.325 (088.8) (56) Авторское свидетельство СССР

М 1411735, кл. G 06 F 7/49, 1987.

Авторское свидетельство СССР

М 9&1993, кл. G 06 F 7/49, 1981. (54) КОМБИНАЦИОННЫЙ СУММАТОР К0ДОВ ФИБОНАЧЧИ

„„Я „„1667052 А1 (57) Изобретение относится к автоматике и вычислительной технике и может быть использовано для параллельного суммирования многоразрядных двоичных чисел. Цель изобретения — сокращение аппаратурных затрат. Сумматор содержит в каждом разряде пятый элемент ИЛИ 10, элемент 11 запрета, четвертый элемент НЕ 12, первый и второй элементы НЕ 13 и 14, пятый элемент

НЕ 15, третий элемент НЕ 16, первый и второй элементы ИЛИ 17 и 18, первый и второй элементы И 19 и 20, элементы ИСКЛЮЧАЮЩЕЕ ИЛИ 21, с третьего по шестой элементы И 22 — 25, третий и четвертый элементы ИЛИ 26 и 27 со связями, 1 ил.

1667052

40

55 эом.

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

Целью изобретения является сокращение аппаратурных затрат.

На чертеже представлена схема I — го разряда комбинационного сумматора кодов

Фибоначчи.

I — и разряд сумматора содержит выход 1

I — ro разряда выхода суммы сумматора, вход

2 1-ro разряда входа первого слагаемого сумматора, вход 3 (1 + 1)-ro разряда входа !, nepeoro слагаемого сумматора, вход 4 1-го разряда входа второго слагаемого сумматора, вход 5 (1 - 1) — ro разряда входа второго слагаемого сумматора, вход 6 переноса из (1 - 1)-го разряда сумматора., вход 7 переноса из (1+ 2)-го разряда сумматора, выход 8 переноса в (I+ 1)-й разряд сумматора, выход

9 переноса в (1 - 2)-й разряд сумматора, пятый элемент ИЛИ 10, элемент 11 запрета, четвертый элемент HE 12, первый и второй элементы НЕ 13 и 14 соответственно, пятый элемент НЕ 15, третий элемент НЕ 16, первый и второй элементы ИЛИ 17 и 18 соответственно, первый и второй элементы И 19 и

20 соответственно, элемент ИСКЛЮЧАЮЩЕЕ или 21, с третьего по шестой элементы

И 22-25 соответственно, третий и четвертый элементы ИЛИ 26 и 27 соответственно.

Любое натуральное п-разрядное число

А в кодах Фибоначчи представляется в виде и — 1 многочлена А = (у(1) где а (0,1) и (=о

0 при(< О, p(l) 1 при(=О

p (I - 1) + p (1 - 2) и ри I > 0 (1)

Предлагаемый способ сложения основан на соотношениях: р(!)+ у(!) =р(!+ 1)+ р(! - 2) (2)

97(I)+ CP(I -1) = 5p(l+ 1) (3) вытекающих из рекурентного соотношения (1).

В сумматоре кодов Фибоначчи форми. руется частично нормализованный.код суммы.

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

Сущность изобретения состоит в реализации выражений (2) и (3), Сумматор работает следующим обраНа входы 2-7 1 — ro разряда сумматора подаются шесть сигналов. Одновременно единичными могут быть только три из них, так как слагаемые поступают на входы сумматора в нормализованной форме, т. е. в двух соседних разрядах кода слагаемого одновременно не могут находиться единицы, в результате этого не может быть единичных сигналов одновременно на следующих входах: (1 + 1) — го и I — го разряда первого слагаемого; I-го и (1 - 1)-.ro разряда второго слагаемого; 1 — ro разряда первого слагаемого и на входе переноса из (1 - 1)-ro разряда; (1 - 1) — ro разряда второго слагаемого и на входе переноса из(1 - 1)-ro разряда; (1+ 1)-го разряда первого слагаемого и на входе переноса из (I+ 2)-го разряда.

Суммирование в 1 — ом разряде сумматора происходит следующим образом.

Если на его входе единичных сигналов нет или есть единичные сигналы на входах (1 + 1) — го разряда первого слагаемого или ((- 1)-го разряда второго слагаемого, то единичные сигналы переносов в другие разряды не возникают и формируется нулевой сигнал суммы в разряде

Если есть только один единичный сигнал, но он находится на входе (1 + 1)-го разряда первого слагаемого или (l - 1) — го разряда второго слагаемого, то возникает только один единичный сигнал — на выходе суммы 1-го разряда.

Если на входах 3-ro разряда первого и второго слагаемых единичные сигналы, а на остальных нули, то формируются единичные сигналы переносов в (I + 1) — и и в (1 - 2)-й разряды и нулевой сигнал суммы в данном разряде.

Если единичные сигналы только на входах I-ro первого разряда первого слагаемого и (I - 1)-ro разряда второго слагаемого, то формируется единичный сигнал переноса в (I + 1)-й разряд и нулевые сигналы суммы в данном разряде и переноса в (1 -2)-й разряд.

Если есть единичные сигналы только на входах слагаемых I-ro разряда и входе переноса из (I+ 2)-го разряда, то формируются единичные сигналы переносов в (1+ 1)-й и (1 - 2)-й разряды и единичный сигнал суммы данного разряда.

Если единичные сигналы только на входах (— го разряда первого слагаемого, (1 - 1) — го разряда второго слагаемого и входе переноса из (1 + 2)-го разряда, то формируются единичные сигналы переноса из (I + 1)-й разряд, суммы в данном разряде и нулевой сигнал переноса в (1 - 2) — и разряд.

Если только на входах 1-х разрядов первого и второго слагаемых есть единичный сигнал и есть сигнал переноса из (1 - 1)-го

1667052 разряда, то возникают единичные сигналы ряда сумматора соединен с первым входом переносов в (I + 1) — и и (1 - 2) — и разряды. третьего элемента ИЛИ того же разряда

Рассмотрим работу разряда сумматора сумматора, выход элемента ИСКЛЮЧАЮна примере. ЩЕЕ ИЛИ разряда сумматора соединен с

Допустим, есть единичные сигналы на 5 первым входомтретьего элемента Итогоже входах I-x разрядов обоих слагаемых и пе- разряда сумматора, выход четвертого реноса из(!+2}-ro разряда, тогда на выходе элемента ИЛИ (I + 2)-го разряда суммаэлемента 11 запрета будет единичный сиг- тора(! =1- п-2, n — разрядность кода) соединал, на втором и третьем входах элемента нен с вторым входом второго элемента И

ИЛИ 17 установятся единичные сигналы, на 10 I-ro разряда сумматора, выход третьего элевыходе элемента ИЛИ 17 и на первом входе мента ИЛИ К-ro (К = 1 - и - 1) разряда суммаэлемента И 24 установятся "1", на втором и тора соединен с первым входом первого третьем входах элемента И 24 тоже будут . элемента ИЛИ(К+1)-ro разряда сумматора, "1", В результате на выходе элемента ИЛИ отличающийся тем, что, с целью

27 установится единичный сигнал, значит 15 сокращения аппаратурных затрат, каждый появится."1" на входе элемента ИЛИ 26 и на разряд сумматора содержит четвертый и пявыходах переносов появятся единичные тый элементы НЕ,элементзапрета. причем сигналы. На входах элемента ИСКЛЮЧАЮ- выходы четвертого и пятого элементов НЕ

ЩЕЕ ИЛИ 21.будут единицы, на его выходе разряда сумматора соединены соответст"0", который инвертируется в элементе НЕ 20 венно с вторым и третьим входами третьего

16 и на втором входе элемента И 25 будет элемента И того же разряда сумматора, вы"1", на третьем входеэлемента И25устано- ход которого соединен с третьим входом вится единичный сигнал, который проходит пятого элемента ИЛИ того же разряда сумчерез элемент ИЛ И 18, так как на его втором матора, выход элемента запрета соединен с входеустановлена "1". На первый входэле- 25 входом первого элемента НЕ, с вторыми мента И 25 единичный сигнал подается от входами первого элемента ИЛИ и четвертозлемента НЕ 14, где инвертируется нулевой го элемента И, с первым входом элемента сигнал, В результате на всех трех входах ИСКЛЮЧАЮЩЕЕ ИЛИ того же разряда элемента И 25 устанавливаются "1", т. е. на сумматора, выход которого соединен с вхоего выходе тоже будет единичный сигнал, 30 дом третьего элемента HE того же разряда который пройдет через элемент ИЛИ 10 и сумматора, второй вход второго элемента И установится на выходе суммы I — го разряда.. разряда сумматора соединен с вторыми

Ф о р м у л а и з о б р е т е н и я входами элемента ИСКЛЮЧАЮЩЕЕ ИЛИ и

Комбинационный сумматор кодов Фи- пятого элемента И того же разряда суммабоначчи, содержащий в каждом разряде с 35 тора, вход разряда входа первого слагаемопервого по третий элементы НЕ, с первого ro сумматора соединен с входом четвертого по шестой элементы И, с первого по пятый элемента НЕ, с третьим входом первого элеэлементы ИЛИ и элемент ИСКЛЮЧАЮЩЕЕ мента ИЛИ, с первыми входами второго элеИЛИ, причем выход первого элемента НЕ мента ИЛИ и первого элемента И разряда сумматора соединен с первым вхо- 40 соответствующего сумматора, вход разряда дом второго элемента И того же разряда входа второго слагаемого сумматора соедисумматора, выходкоторогосоединен спер- нен с информационным входом элемента вым входом пятого элемента ИЛИ того же запрета соответствующего разряда суммаразряда сумматора, выход которого являет- тора, вход (К+ 1) — ro разряда входа первого ся выходом соответствующего разряда вы- 45 слагаемого сумматора соединен с управляхода суммы сумматора, выход второго ющимвходомэлементазапрета К-горазряэлемента НЕ разряда сумматора соединен с да сумматора, вход второго элемента HE первыми входами пятого и шестого элемен- (К + 1)-го разряда сумматора соединен с тов И того же разряда сумматора, выход входом К-го разряда входа второго слагаетретьего элемента НЕ разряда сумматора 50 мого сумматора, второй вход первого элесоединен с вторым входом шестого элемен- мента И разряда сумматора соединен с та И того же разряда сумматора, выход ко- третьим входом второго элемента И того же торого соединен с вторым входом пятого разряда сумматора и с входом второго элеэлемента ИЛИ того же разряда сумматора, мента НЕ того же разряда сумматора. вход выход второго элемента ИЛИ разряда сум- 55 пятого элемента НЕ разряда сумматора соматора соединен с первым входом четвер- единен с вторым входом второго элемента того элемента И того же разряда сумматора, ИЛИ того же разряда сумматора и с первым выход которого соединен с первым входом входом первого элемента ИЛИ того же разчетвертого элемента ИЛИ того же разряда ряда сумматора, выход которого соединен с сумматора, выход первого элемента И раз- . третьим входом пятого элемента И того же

1667052

Составитель А. Клюев

Техред М.Моргентал

Корректор.О, Кравцова

Редактор О. Спесивых

Заказ 2524 Тираж 397 Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., 4/5

Производственно-.издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101 разряда сумматора, выход второго элемента ИЛИ разряда сумматора соединен с третьим входом шестого элемента И того же разряда сумматора, выход второго элемента НЕ разряда сумматора соединен с третьим входом четвертого элемента И того же разряда сумматора, выход пятого элемента

И разряда сумматора соединен с вторым входом четвертого элемента ИЛИ того же разряда сумматора, выход которого соеди5 нен с вторым входом третьего элемента

ИЛИ того же разряда сумматора.