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

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

Иллюстрации

Показать все

Реферат

 

Союз Советскик

Социалмстическик

Республии

ОП ИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

""732864 (6! ) Дополнительное к авт. с вид-ву (22) Заявлено 22.12.76 (23) 2432391/18«24 с присоединением заявки Ж (23) Приоритет

Опубликовано 05.05.80. Бюллетень М 17

Дата опубликования описания 08.05.80

2 У (51)М. Кл.

G 06 Г 7/385

Гооударстееииый комитет

IIO делам изобретеиий и открытий (53) УДК 681,325,,5(088.8) (72) Автор изобретения

А. П. Стахов

Таганрогский радиотехнический институт им. B. Д Калмыкова (7I) Заявитель (54) СУММАТОР КОДОВ ФИБОНАЧЧИ

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

Известны сумматоры кодов Фибоначчи, построенные на основе алгоритма сложения кодов Фибоначчи (11, (21 и (3).

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

Наиболее близким к предлагаемому является сумматор кодов Фибоначчи, содержаший многоразрядный полусумматор, входы которого соединены со входами слагаемых сумматора и элемент ИЛИ, выход которого подключен к контрольному выходу сумматора (4).

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

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

Для достижения этой цели сумматор содержит нормализатор и блок перезаписи информации, входы которого соединены со входом начала сложения и выходами промежуточной сверхсуммы и запомненных стоп налов многоразрядного полусумматора, а выходы - со входами нормализатора, вы ходы нормалиэатора соединены с выходами результата сложения сумматора, окончания сложения сумматора и первым входом элемента ИЛИ, второй вход которого подклю чен к контрольному выходу многораэряд ного полусумматора.

К роме этого многоразрядный полусумматор содержит 11 однотипных одноразрядных полусумматоров (И вЂ” количество разрядов) и элемент ИЛИ, выход которого подключен к контрольному выходу многоразрядного полусумматора, а входы - a контрольным выходам одноразрядных полу« сумматоров, входы слагаемых g -ro од73286

3 норазрядного полусумматора (f = 1, ll ) подключены ко входам 9-го разряда многоразрядного полусумматора, выходы промежуточной сверхсуммы и запомненного сигнала В-го одноразрядного полусум- матора подключены к выходам f-ro разряда промежуточной сверхсуммы и запомненного сигнала многоразрядного полусумматора, выход запомненного сигнала 3-го одноразрядного полусумматора подключен 10 ко входу запомненного сигнала (g-1)-го одноразрядного полусумматора, выход переноса 3 -го одноразрядного полусумматора подключен ко входу переноса (f-1)-r o и (Я-2)-го одноразрядных полусуммато15 ров, входы переноса 3 -го одноразрядного полусумматора подключены к; выходам переноса (8+1)-го и (0+2)-го одноразрядных полусумматоров, выход сверхпереноса g-го одноразрядного полусуммато20 ра подключен ко входам сверхпереноса ((;-1)-го и (f-2)-ro одноразрядных полусумматоров, входы сверхпереноса -го одноразрядного полусумматора подключены к выходам сверхпереноса (6+1)-го и

25 (6+2)-ro одноразрядных полусумматоров, выход промежуточной суммы f -ro одноразрядного полусумматора подключен ко входу промежуточной суммы (+1)-ro од30 норазрядного полусумматора, вход промежуточной суммы g -ro одноразрядного полусумматора подключен к выходу промежуточной суммы (6-1)-го одноразрядного полусумматора, выходы переноса, сверхпереноса и промежуточной суммы первого одноразрядного полусумматора подключены ко входам элемента ИЛИ.

При этом одноразрядный полусумматор состоит из элементов И, ИЛИ и НЕ, причем вход элемента HE соединен со входом промежуточной суммы и первыми вхо.дами первого элемента И и первого элемента ИЛИ, а выход - с первым входом второго элемента И, второй вход которо4

ro соединен со вторым входом первого элемента И и выходом третьего элемента

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

ИЛИ, а второй вход — с первым входом третьего элемента И, первым входом третьего элемента ИЛИ и выходом шестого элемента ИЛИ, первый вход которого соединен со входом первого слагаемого и первым входом седьмого элемента И, второй вход — co входом второго слагаемого и вторым входом седьмого элемента И, выход которого соединен с выходом переноса и вторым входом первого элемента ИЛИ, третий вход которого соединен с выходом первого элемента И, выходом запомненного сигнала и первым входом пятого элемента И, второй вход которого соединен с входом запомненного сигнала, вход сверхпереноса из (0+1 )-ro разряда соединен со вторым входом третьего элемента ИЛИ и вторым входом пятого элемента ИЛИ, выход которого соединен с выходом промежуточной сверхсуммы, а третий вход — со вторым входом третьего элемента И, третьим входом третьего элемента ИЛИ и выходом седьмого элемента

ИЛИ, первый вход которого соединен со входом переноса из (0+2)-го разряда, а . второй вход — со входом сверхпереноса из (8 +2) -го разряда.

Кроме того, блок перезаписи информации состоит иэ однотипных ячеек по одной на два соседних разряда, начиная с младшего разряда, причем каждая ячейка содержит первый, второй, третий и четвертый входы, соединенные с соответствующими выходами промежуточной сверхсуммы и запомненных сигналов соответствующих двух разрядов многоразрядного полусумма;ора, пятый вход, первый, второй, третий и четвертый выходы, соединенные с соответствующими входами промежуточной сверхсуммы и запомненных сигналов соответствующих двух разрядов нормализатора, пятый выход, который для ячеек, за исключением младшей, соединен с пятым входом предыдущей ячейки, пятый выход младшей ячейки соединен с выходом блока, а пятый вход старшей ячейки соединен со входом начала сложения блока герезаписи информации, причем каждая ячейка блока перезаписи информации состоит из элементов И и элемента эадержки, вход которого соединен с пятым входом ячейки, а выход - с пятым выходом ячейки - и с первыми входами первого, второго, третьего и четвертого элементов

И, вторые входы которых соединены соо

732864 6 ветственно с первым, вторым, третьим и четвертым входами ячейки, а выходы со-ответственно с первым, вторым, третьим и четвертым выходами ячейки.

Кроме того, нормализатор состоит из однотипных ячеек по числу разрядов, каждая из которых содержит вход промежуточной сверхсуммы, вход запомненного сигнала, первый, второй, третий и четвертый входы связи, информационный вы- 10 ход, контрольный выход, первый и второй выходы связи, кроме того нормализатор содержит первый и второй элементы ИЛИ, фильтр, постоянная времени которого превышает время переходного процесса в нор- 5 мализаторе, триггер, элемент НЕ и элемент И, выход которого соединен с выходом конца сложения нормализатора, первый вход — с единичным выходом триггера, второй вход - с выходом элемента

НЕ, вход которого соединен с выходом первого элемента ИЛИ и входом фильтра, выход которого соединен с первым входом второго элемента ИЛИ, другие входы которого соединены соответственно с контрольными выходами ячеек нормализатора, единичный вход триггера соединен с входом нормализатора, входы первого элемента ИЛИ соединены с соответствующими вторыми выходами связи всех ячеек нормализатора, информационные выходы всех ячеек нормализатора соединены с выходом результата сложения сумматора, второй выход связи ячейки g --го разряда соединен с четвертым входом связи ячейки

35 (0-1)-ro разряда и третьим входом связи ячейки (8+1)-го разряда, первый вход связи ячейки 8 --го разряда соединен с информационным выходом ячейки (-1)-го

40 разряда, второй вход ячейки g -го разряда сОединен с первым выходом связи ячейки (6+1)-ro разряда, причем каждая ячейка нормализатора содержит элемент

ИЛИ первый второй и третий элементы 45

И, первый триггер и второй триггер, счетный вход которого соединен с третьим входом связи, единичный вход — со входом промежуточной сверхсуммы, нулевой вход — с выходом первого элемента И ячейки нормелизатора, единичный выход— с информационным выходом ячейки нормализатора и первым входом второго элемента И ячейки нормализатора, нулевой выход - с первым выходом связи ячейки нормализатора и первым входом третьего элемента И ячейки нормализатора, второй вход второго элемента И ячейки нормализатора соединен с первым входом связи ячейки нормализатора, третий вход — с вторым входом связи ячейки нормализатора, а выход — со вторым выходом связи и первым входом элемента ИЛИ ячейки нормализатора, втсрой вход которого соединен с четвертым .входом связи ячеЙи нормализатора, а выход — с первым входом первого элемента И и третьим входом первого триггера ячейки нормализатора, единичный вход которого соединен со входом запомненного сигнала, нулевой выход — со вторым входом первого элемента И ячейки нормализатора, а единичный выход - со вторым входом третьего элемента И ячейки нормализатора, выход которого соединен с контрольным выходом ячейки нормализатора.

На фиг, 1 приведена структурная схема сумматора кодов Фибоначчи; на фиг. 2 — схема многоразрядного полусумматора; на фиг. 3 - схема одноразрядного полусумматора; на фиг. 4- схема блока перезаписи информации; на фиг. 5схема ячейки блока перезаписи информации; на фиг. 6 — схема нормализатора; на фиг. 7 - схема ячейки нормализатора.

Сумматор кодов Фибоначчи содержит вход 1 первого слагаемого, вход 2 второro слагаемого, многоразрядный полусумматор 3, выход 4 промежуточной сверхсуммы, выход 5 запомненных сигналов, контрольный выход 6 полусумматора 3, вход

7 начала сложения, блок 8 перезаписи wформации, выход 9 промежуточной суммы блока 8 перезаписи информации„выход

10 запомненных сигналов блока 8 перезаписи информации, выход 11 сигнала окончания процесса перезаписи информации, нормализатор 12, выход 13 результата сложения, выход 14 окончания сложения, контрольный выход 15 нормализатора 12, элемент ИЛИ 16, контрольный выход 17 сумматора. Входы многоразрядного полу» сумматора 3 соединены со входами 1 и

2 слагаемых, а выходы 4 промежуточной сверхсуммы и запомненных сигналов 5 подключены к входам 11 блока перезаписи информации, к которым также подключен вход 7 начала сложения. Выходы 9 промежуточной суммы и запомненных сигналов 10 и выход 11 сигнала окончания процесса переэаписи информации блока 8 перезаписи информации подключены ко входам нормалиэатора 12, имеющем выходы

13 результата сложечия, окончания сложения 14 и контрольный выход 15. Контрольный выход 15 нормализатора 12 и контрольный выход 6 полусумматора 3 подклю»

7 7328 чены ко входам элемента ИЛИ 16, выход которого подключен к контрольному выходу сумматора 17.

Многоразрядный полусумматор 3» соо» держит И (l1 - количество разрядов) одноразрядных сумматоров 18; .6 — ый из которых имеет (g =1, ..., П ) выход 19 . промежуточной сверхсуммы, выход 20. за-» помненного сигнала, контрольный выход

21, выход 22 сверхпереноса, выход 23 !о переноса, вход 24 сверхпереноса иэ Я +

+ 1-го разряда, вход 25 сверхпереноса нэ (8+2)-го разряда, входы 26 и 27 слагаемых, вход 28 переноса из (8+2)-ro разряда, вход 29 переноса из (8+1.)-го 15 разряда, вход 30 промежуточной суммы, выход 31 промежуточной суммы, вход 32 запомненного сигнала. Многоразрядный полусумматор 3 содержит кроме того элемент ИЛИ 33. 20

При этом выходы 19 всех одноразрядных полусумматоров 18 соединены с соответствующими выходами 4 многоразряд1 ного полусумматора 3; выходы 20 всех одноразрядных полусумматоров 18 соединены с соответствующими выходами 5 мноI горазрядного полусумматора 3; входы

26 и 27 всех одноразрядных полусумматоров 18 соединены с соответствующими входами 1 и 2 многоразрядного полусум- ЗО матора 3; контрольные выходы 21 всех одноразрядных полусумматоров 18, а также выходы 20, 22, 23 и 31 одноразрядного полусумматора 18 младшего разряда соединены со входами элемента ИЛИ 33, ЗБ выход которого соединен с контрольным выходом 6 многоразрядного полусумматора 3; выход 22 одноразрядного полусумматора 18 g-го разряда соединен со входом 24 одноразрядного полусумматора 18 4О (3 -1)-го разряда и входом 28 одноразрядного полусумматора 18 (8-2)-го разряда; вход 30 одноразрядного полусумма- тора 18 3-го разряда соединен с выходом 31 одноразрядного полусумматора 4>

18 (6-1)-го разряда; выход 20 одноразрядного полусумматора 18 3-го разряда соединен со входом 32 однораэрядного (P-1)-го разряда, Одноразрядный полусумматор 18; со- Ы держит алементы ИЛИ 34, 35 и 36, але»мент И 37, элемент НЕ 38, элемент И

39, элементы ИЛИ 40 и 41, алементы

И 42 и 43, элемент ИЛИ 44, элемент

И 45, элемент ИЛИ 46, элементы И 47 и 48.

При этом вход элемента HE 38 соединен со входом ЗО промежуточной суммы

64 8 и первыми входами элементов ИЛИ 41 и

42, а выход — с первым входом элемента И 43, второй вход которого соединен со вторым входом элемента И 42 и выходом элемента И 39, а выход - с выходом 22 сверхпереноса и входом элемента

И 47, другой вход которого подключен к выходу элемента ИЛИ 41. Выход элемента И 47 подключен ко входу алемента

ИЛИ 46, выход которого соединен с конTpolIIHblM выходом 21, второй вход — с выходом элемента И 48, а третий вход— с выходом элемента И 45, первый вход которого соединен с выходом элемента

ИЛИ 40, а второй вход — со входом переноса из (ь+1)-ro разряда 29 и первым входом элемента ИЛИ 34, выход которого соединен с выходом 31 промежуточной суммы и первым входом элемента ИЛИ

44, а второй вход — с первым входом элем ен та И 3 S, элемен та ИЛ И 40 и выходом элемента ИЛИ 35. Входы элемента ИЛИ 35 соединены со входами 26 и

27 слагаемых, которые подключены также ко входам элемента И 37, выход которого соединен с выходом 23 переноса и вторым входом элемента.ИЛИ 41» третий вход которого соединен с выходом элемента И 42, выходом 20 запомненного сигнала и первым входом элемента И 48, второй вход которого соединен со входом запомненного сигнала 32. Вход сверхпереноса из (f +1)-го разряда 24 соединен со вторыми входами элементов ИЛИ

40 и 44.

Выход элемента ИЛИ 44 подключен к выходу 19 промежуточной сверхсуммы, а третий вход соединен со вторым входом элемента И 39, третьим входом элемента ИЛИ 40 и выходом элемента ИЛИ 36, первый вход которого соединен со входом

28 переноса из (6+2)-го разряда, а второй вход - со входом 25 сверхпереноса из (5+2)-го разряда 25.

Блок 8 перезаписи информации состоит из однотипных ячеек 49 каждая иэ которых связана с двумя разрядами многоразрядного полусуммвтора 3 и содержит входы 50, 51, 52, 53 и 54, выходы

55» -«6» 57» 58 и 59, алемент 6 О задержки, алементы И 6-1, 62, 63 и 64.

При этом входы 50, 51, 52 и 53 соеди иены с соответствуюшими выходами 4 промежуточной сверхсуммы и запомненных сигналов 5 двух соседних разрядов многоразрядного лолусумматора 3; выходы 55, 56, 57 и 58 соединены с вы,ходами 9 промежуточной суммы и эапом732864 10 ненных сигналов соответствующих разрядов блока перезаписи информации 8; выход 54 И-ой ячейки 49 блока 8 перезаписи информации соединен со входом

59 И-1-ой ячейки 49; выход 54 младшей.ячейки 49 соединен с выходом 11 сигнала окончания процесса перезаписи информации, вход 59 старшей ячейки подключен ко входу 7 начала сложения.

Вход элемента 60 задержки подключен io ко входу 59 ячейки 49 а выход — к выФ ходу 54 ячейки 49 и ко входам элемен тов И 61, 62, 63 и 64, вторые входы которых подключены соответственно Ко входам 51, 53, 50 и 52 ячейки 49, а выходы - к выходам 57, 55, 58 и 56 ячейки 49.

Нормализатор 12 содержит Vl однотипных ячеек 65, каждая из которых вктцсчает первый триггер 66, с единичным и ну- ?О левым входами 67 и 68 и нулевым и единичным выходами 69 и 70, второй триггер 71, с единичным входом 72, счетным входом 73 с запуском по заднему фронту нулевым входом 74, нулевым входом 75, единичным выходом 76, элемент И 77, элемент ИЛИ 78, элементы И 79 и 80; первый вход 81 связи, второй вход 82 связи, первый выход 83 связи, третий вход

84 связи, вход 85 промежуточной сверх- ЗО суммы, вход 86 запомненного сигнала, четвертый вход 87 связи, второй выход

88 связи, контрольный выход 89, информационный и выход 90.

К роме того, нормализатор 12 содер- ЗБ жит элемент ИЛИ 91, фильтр 92, постоянная времени которого превышает время переходного процесса в нормализаторе 12, элемент ИЛИ 93, триггер 94, с единичным входом 95 и единичным выхс - 40 дом 96, элемент И 97 и элемент НЕ 98.

При этом в нормализаторе 12 второй выход 88 связи ячейки 65 E -го разряда соединен с четвертым входом 87 связи ячейки 65 (ь -1) -го разряда, третьим входом связи 84 ячейки 65 (6+1)-го разряда и одним из входов элемента ИЛИ

91; первый вход 81 связи ячейки 65 -го разряда соединен с информационным выходом 90 ячейки 65 (f-1)-i o разряда; второй вход 82 связи ячейки 65 го разряда соединен с первым выходом

83 связи ячейки 65 (1+1)-го разряда; вход 11 сигнала окончания процесса перезаписи информации соединен с единичным входом 95 триггера 94, единичный. выход

96 которого соединен с одним из входов элемента И 97; выход элемента ИЛИ 91 соединен со вхсдом элемента HE 98, выход которого через элемент И 97 соединен с выходом 14 окончания сложения;

Выходы 88 всех ячеек нормализатора соединены через элемент ИЛИ Dl с фильтром 92 и далее через элемент ИЛИ 93 с контрольным выходом 15. Эта цепь соединений выполняет контрольные функции в нормализаторе. После нормализации на всех выходах 88 должны быть нулевые сигналы. Единичные сигналы на этих выходах появляются кратковременно, пока идет переходной процесс в нормализаторе. фильтр 92 не пропускает кратковременные сигналы на выходах 88 на контрольный выход 15. Если же на одном из выходов

88 появляется устойчивый единичный сиг» нал, то это приводит к появлению сигнала на контрольном выходе 15.

Выход элемента ИЛИ 91 соединен со входом элемента НЕ 98, а через элемент

И 97 с выходом 14 окончания сложения.

Эта цепь соединений вместе с триггером

94 и входом l l играет следующую роль.

Qo тех пор, пока длится переходной,процесс в нормализаторе, на выходе элемента ИЛИ 91 будет единичный сигнал, который через элемент НЕ 96 запрещает появление единичного сигнала на выходе

14. Как только на входе 11 появляется единичный сигнал (что свидетельствует об окончании первого этапа и перезаписи информации в нормализатор 12) он приводит z переходу триггера 94 в единичное состояние и появлению разрешающего сит нала на соответствующем входе элемента

И 97. После окончания переходного процесса в нормализаторе на выходе 14 появляется единичный сигнал. При устойчивом отказе нормализатора 12 на выходе

15 единичный (разрешающий) сигнал появиться не может.

В каждой ячейке нормализатора 65 триггер 71 своим счетным входом 73 подключен к третьему входу 84 связи, единичным входом 72 — ко входу 85 промежуточной сверхсуммы, нулевым входом

74 — к выходу элемента И 77. Единичный выход 76 триггера 71 подключен к информационному выходу 90 и к входу элемента И 79» а нулевой выход 75 — к первому выходу 83 связи и входу элемента И 80, другой вход которого подключен к единичному выходу 70 триггера 66, а выход - к контрольному выходу 89. Второй и третий входы элемента И 79 подключены соответственно к первому и второму входам 81 и 82 связи, а выход—

64 12 налом переноса из (1 +2)-го разряда.

Операция образования запомненных сигналов по существу совпадает с операцией образования переносов;

rl операция контроля сложения. Сигнал контроля сложения в 8 -м разряде равен

1, если одновременно равны 1 сигналы переносов .из (6+1)-го и (8 +2 )-ro разрядов.

2. Промежуточная сумма приводится к нормальной форме и над нормальным кодом Фибоначчи промежуточной суммы и комбинацией запомненных сигналов выполняют п. 1, 2 алгоритма до образования нулевой комбинации запомненных сигналов.

Пример 1. Сложить два числа

46 и 41 в 1 - коде Фибоначчи.

1. Представление чисел 46 и 41 в нормальных 1 - кодах Фибоначчи:

1) 34 21 13 8 5 3 2 1 1

411 О О 0 1 0 1 0 0

2.Выполнение п, 1 алгоритма:

2) 1 О О 1 О 1 О 1 О

1000101О0

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

3. Выполнение п. 2 алгоритма (нормализация промежуточной суммы):

1 в 1.Я .

1ОО1ОО111О

1001010010

4) 1001010010

00 01000010

6) 10 100100 10

00000 10000

1010100110

11 7328 ко второму выходу 88 связи и входу элемента ИЛИ 78, другой вход которого соединен с четвертым входом 87, связи, а выход - со входом элемента И 77 и нулевым входом 68 триггера 66, единичный вход 67 которого соединен со входом 86 запомненного сигнала, а нулевой выход 69 - с другим входом элемента

И 77.

Существо алгоритма сложения кодов 10

Фибоначчи состоит в следующем.

Слагаемые числа представляются в виде нормальных кодов Фибоначчи (в нормальном коде Фибоначчи две единицы подряд в коде не встречаются) и затем над 15 нормальными кодами Фибоначчи осуществляются следующие операции.

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

Сигнал 6-го разряда промежуточной сум мы и сигналы переносов из f -го разря- да в (К-1)ый и (Я-2)-й разряды образуются на основе следующей таблицы сложения одноразрядных чисел в коде Фибо25 наччи.

О+ О = О 110111110

0+0= 1 1

1+0-=1

1+1=111

ЗО

В указанном алгоритме сложения сигнал переноса из,f -ãî разряда в (6-1)-й разряд сразу же помещается в (8-1-)й разряд промежуточной суммы, а сигнал переноса в (В -2)-й разряд является запомненным сигналом в (< 2) м разряде

Таким образом, в процессе сложения в каждом разряде (5-м) анализируются четыре сигнала сигналы В f м раэря 4О де слагаемых и сигналы переноса из (6+1)-го и ((;+2)-ro разрядов в 6 -й разряд. При этом одновременно выполняется четыре операции:

5)10111(01 а) операция образования сигнала про- 4>

101010010 межуточной суммы, Сигнал промежуточной суммы в 6 -м разряде принимается равном 1, если равен 1 хотя бы один из сигналов в К-м разряде слагаемых или сигнал переноса иэ (.8+1)-го разряда, 101001 10 и нулю в противном случае; 1 б) операция образования сигнала пере« носа из 6-го разряда. Сигнал переноса 7) 1 0 1 О иэ f-го разряда принимается равным 1, 101010010 если равны 1 одновременно оба сигнала в 6 -м разряде слагаемых, 8) 1010100010

- в) операция образования запомненного 00000 00 1 00 сигнала в о -м разряде. Запомненный сигнал в 6 -м разряде совпадает с сиг13

732864 тат сло жения

Сложное закончено

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

В-ro в (8-1)-й и (0-2)- разряды ввести операцию образования сигнала промежуточной сверхсуммы в -м разряде, операцию образования сверхпереноса из

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

В предлагаемом сумматоре кодов Фибоначчи в каждом разряде (E-м) анализиру1 ются семь сигналов: сигналы в g-м разряде слагаемых, сигналы переносов из (+1 и(+2)-ro разрядов в 6 «й разряд, сиг

З налы сверхпереносов иэ (6+1)-го и (8+

+2)-го разрядов в 6-й разряд и сигнал промежуточной сверхсуммы из (6-1)-ro разряда; при этом в каждом разряде вы30 полняются одновременно шесть операций: а) операция образования сигнала промежуточной суммы в 6 -м разряде, которая совпадает с аналогичной операцией в известном способе и состоит в следую35 щем: сигнал промежуточной суммы принимают равным 1, если равен 1 хотя бы один из сигналов в -м разряде слагаемых, или сигнал переноса иэ E -го разряда, и нулю в противном случае; б) операция образования перекоса иэ (6+1)-го в (6-1)-й и (-2)-й разряды, которая совпадает с аналогичной операцией в известном способе и состоит в следующем: сигнал переноса из f -го разряда принимают равным 1, если равны 1 одновременно оба сигнала в 6-м разряде слагаемых, и нулю в противном случае; в) операция образования сигнала промежуточной сверхсуммы в 6-м разряде; сигнал промежуточной сверхсуммы принимают равным 1, если равен 1 хотя бы один из следующих сигналов: сигнал промежуточной суммы в 6 -м разряде, сигнал переноса из (6+2)-го разряда, сигнал сверхпереноса из (6+1)-ro либо из (6+2)-го разряда, и нулю в противном случае;

1111111010100-промежуточная сумма

1 1

I сигналы переносов из (6+2)-го разряда, 101010110

1 0 1 0 1 0 0 0 — резуль14

r) операция образования сигнала сверхпереноса иэ 8 -го разряда в (6-1)-й и (6-2)-й разряды: сигнал сверхперенс са из E. -го раэряца принима.от равным 1, если равен нулю сигнал промежуточной суммы в (-1)-м разряде и одновременно равен единице хотя бы один иэ сигналов переноса или сверхпереноса из (if+2)-ro разряда в 6-й разряд, и нулю в противном случае; д) операция образования запомненного сигнала в 6-м разряде: запомненный сигнал в 6-м разряде принимают равным

1; если одновременно равны 1 следующие сигналы: сигнал промежуточной суммы в (-1)-м разряде, хотя бы один из сигналов в C -м разряде слагаемых и хотя бы один иэ сигналов переноса и сверхпереноса из 6 +2-го разряда и нулю в противном случае; е) операция образования сигнала контроля; сигнал контроля принимают равным

1 (сигнал ошибки), если равен 1 сигнал переноса из (+1)-го разряда и одновременно равен 1 хотя бы один из следующих сигналов: сигнал в 0 -м разряде первого слагаемого, сигнал в К -м разряде второго слагаемого, сигнал переноса из (8+2)-ro разряда, сигнал сверхпереноса нз (6+1)-го разряда, сигнал сверхпереноса из (6+2)-го разряда, либо равен 1 сигнал сверхпереноса из P -го разряда и одновременно равен 1 хотя бы один из следующих сигналов: сигнал переноса иэ 6-го разряда, сигнал промежуточной суммы в (6-l)-м разряде, запомненный сигнал в 6-м разряде.

С учетом введенных операций образование промежуточной сверхсуммы и запомненных сигналов приведены в примере 2, Пример 2. Образовать промежуточную сверхсумму и запомненные сигна лы при сложении следующих 1-кодов Фибоначчи:

12 11 10 9 8 7 6 5 4 3 2 1 0 - но» мера разрядов

1 0 10 1000 10 100 1 0 10101010000 сигналы переносов иэ соответствующих разрядов

732864

16

Так как сигналы промежуточной суммы в 9-м и 7-м разрядах равны 1 и одновременно равны 1 сигналы в 10-м и

8-м разрядах промежуточной суммы, то в 10-м и 8-м разрядах образуют запомненные сигналы.

Так как сигнал промежуточной суммы .в 5-м разряде равен нулю, то это приводит к образованию сигнала сверхпереноса из 6-го разряда, а затем из 4-ro и 2-го разрядов:

1 1 1 1 1 1

1010100 ь Д

1 1 сигналы сверхперено 1ов

В результате образуется следующая промежуточная сверхсумма и запомненные сигналы:

1 1 1 1 1 1 1 1 1 1 1 1 1 - промежуточная сверхсумма запомненные сигналы

Если равен 1 сигнал переноса из (Ю+

+1 )-го разряда, то это означает, что в (8 +1)-м разряде слагаемых имеются единичные сигналы, отсюда вытекает, что в (<+2)-м и 6-м разрядах слагаемых заведомо должны быть нули (свойство нормальной формы кодов Фибоначчи), т.е. имеет место следующая ситуация:

Е+2 8+1

° ° ° е ° åå ° ° å ° å ° ° ° °

0 1 0

0 1 0 перенос из (К +1)-го разряда.

Следовательно, при единичном сигнале переноса из (6+1)-го разряда сигналы в

3-м разряде слагаемых должны быть нулевыми (первое контрольное соотношение). 4р

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

1 сигнал в (6+1)-м разряде промежуточной суммы (четвертое контрольное соот« ношение) .

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

10 0100110010010

10010 10000 100 10

Б сумматоре кодов Фибоначчи операция нормализации ведется с учетом значений запомненных сигналов в соответствующих разрядах и состоит в следующем: если в процессе нормализации возникает необходимость замены нуля в 6 -м разряде и единиц в ((;-1)-м и (8 -2)-м разряде своими отрицаниями, а запомненный сигнал либо в (б -1 ) -м, либо в (8-2 ) -м разряде равен 1, то в процессе нормализации единицу сохраняют в разряде с единичным запомненным сигналом, а запомненный единичный сигнал заменяют на нулевой.

Проведем нормализацию промежуточной сверхсуммы и заломненных сигналов в рассмотренном выше примере;

1 1

1) 1111111111111 1

2) 1 0 0 1 1 1 1 1 1 1 1 1 1 1

3)10010111111111

Ф 1 з

4) 10011101111111

10100110011111

10101000010111

5) 6) нала в ь-м разряде, который может появиться только при единичном сигнале промежуточной суммы в (8-1}-м разряде (шестое контрольное соотношение) и, нар У конец, появление единичного сигнала пер носа из 0-го разряда, который сразу же вызывает появление единичного сигнала промежуточной суммы в (g-1)-м разряде и запрет сигнала сверхпереноса из Я-ro разряда (седьмое контрольное соотношение).

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

Известная операция нормализации кода

Фибоначчи не учитывает запомненные сигналы и состоит, например в следующем:

17 732864

7)10101000101001 ди

0 1 О

О 1 1 0

8+2 6+1 Е

О

8) 10 10 100010 10 10— резуль ат сложения

Работа сумматора кодов Фибоначчи

5 п ротека ет следующим образом.

Сигналы на входах слагаемых 1 и 2 появляются одновременно с сигналом на входе 7 начала сложения. При этом начи10 нается процесс формирования сигнала в многоразрядном полусумматоре 3 (как будет показано ниже, сигнал переноса в полусумматоре распространяется от старразрядов K младшим) ° Влок 8 nepe» 5 записи информации представляет собой линию задержки с отводами в каждом разряде. Сигнал в блоке 8 перезаписи информации также распространяется от старших разрядов к.младшим и, начиная со старших разрядов, последовательно переписывает информацию с полусумматора 3 в нормалиэатор 12. Сигнал в нормалиэаторе 12 распространяется в направлении от младших разрядов к старшим, Поэтому нормализация старших разрядов начинается раньше, чем закончился переходной процесс в полусумматоре 3. 3а счет параллельной организации работы полусумматора 3 и нормализатора 12 удается в среднем повысить быстродействие сумматора. Появление сигнала на выходе 11 свидетельствует об окончании процесса перезаписи информации. Если хотя бы на одном из выходов 6 или 15 появляется сигнал ошибки, то через элемент ИЛИ 16 он поступает на контрольный выход 17 сумматора. После появления сигнала на выходе 11 и, после окончания переходного процесса в нормализаторе 12 на выходе 4О

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

Работу многоразрядного полусумматора

3 удобнее объяснить, если ввести как бы два этапа обработки информации в одноразрядном полусумматоре: этап образования промежуточной суммы (выход 31) и переноса (выход 23) и этап образования промежуточной сверхсуммы (выход 19), сверхпереноса (выход 22 ) и эапомненного сигнала в 6 -м разряде (выход 20).

На первом этапе сигналы могут появляться только на входах 26, 27, 28 и

29. Если хотя бы на одном из входов 26, 27 и 29 появляется единичный сигнал, то через элементы ИЛИ 35»34 это привот к появлению сигнала на выходе 31, а через элемент ИЛИ 44 — на выходе 19.

Если единичный сигпал появляется на входе 28, то через элементы ИЛИ 36 и 44 это приводит к появлению сигнала Н8 выходе 19, Если на входах 27 и 26 одновременно появляются единичные сигналы, то через элемент И 37 это приводит к появлению сигнала на выходе 23.

Первый этап обработки информации в полусумматоре хорошо, контролируется.

При сложении нормальных 1-кодов Фибоначчи из 16 кодовых комбинаций на входах 26, 27, 28 и 29 семь кодовых комбинаций являются эапрешенными, а именно.

28 26 27 29 — входы

О 0 0 О, О 0 0 1

0 0 1 1 - запрет

0 1 0 1 - запрет

О 1 1,1 — запрет

1 0 О О

1 0 О 1 — запрет

1 0 1 0

1 0 1 1 — запрет

1 1 О 0

1 1 О 1 — запрет

1 1 1 0

1 1 1 1 — запрет

Появление единичного сигнала переноса иэ (0 +l)-го разряда (вход 29) означает, что в (8+1)-м разряде слагаемых находятся единицы и, следовательно, в (4+2)-м и 5-м разрядах слагаемых заведомо должны быть нули:

1

Ь перенос

Следовательно наличие переноса из (8+1)-го разряда и наличие хотя бы одной единицы на входах 26, 27 и 28 является признаком ошибки.

В схеме одноразрядного полусумматора 18 эта идея контроля полусумматора на первом этапе обработки информации

1 000000000

1111101010 (1 1

1111111010

:1 Й„1

1111111110

111111111

1 Ф (Стрелками показаны единичные сигналы переноса и сверхпереноса в сумматоре), При возникновении сигнала переноса или сверхпереноса из 6 -го разряда в двух соседних разрядах полусумматора 3 одновременно начинается формирование выходных сигналов, Обозначим через Г время задержки сигнала в элементе И либо в элементе ИЛИ. Анализ схемы одноразрядного полусумматора 18 показывает, что

19 7328 реализуется следующим образом. Если на вхоле 29 появляется нелиничный сигнал и одновременно хотя бы на одном из входов

26, 27 и 28 появляется единичный сигнал, то через элементы ИЛИ 35 и 36 и далее через элемент ИЛИ 40, элемент И

45 и элемент ИЛИ 46 это приводит к появлению единичного сигнала на выходе

21.

Этап образования промежуточной сверх-10 суммы (выход 19), сигнала сверхпереноса (выход 22) и запомненного сигнала в

8-м разряде (выход 20) начинается после появления сигналов на входах 24, 25 и 30, Заметим, что единичный сигнал сверхпереноса из (8+1)-го разряда на входе 24 может появиться только в том случае, если равен нулю сигнал промежуточной суммы в б -м разряде (выход

31). Единичный сигнал на входе 24 че= ро рез элемент ИЛИ 44 приводит к появлению единицы на выходе 19 (сигнал промежуточной сверхсуммы). Единичный сигнал на входе 25 через элемент ИЛИ 36 и 44 также приводит к появлению едини- 25 цы на выходе 19.

Единичный сигнал на выходе 22 (сигнал сверхлереноса или ь -го разряда) появляется при следующих условиях: сигнал на входе 30 должен быть нулевым, что ЗО через элемент HE 38 приводит к появлению разрешающего (единичного сигнала) на одном из входов элемента И 43; хотя бы на одном из входов 27, 26 и одновременно хотя бы на одном из входов 3Б

25, 28 должны быть единичные сигналы что приводит к появлению единичных сигналов на выходах элементов ИЛИ 35 и

36, элемента И 39, и в конечном итоге, на выходе элемента И 43 и выходе 22.. 40

Если же появляется единичный сигнал на выходе элемента И 38 и одновременно на входе 30, то в этом случае через элемент И 42 формируется единичный сигнал на выходе 20 (запомненный сигнал).

Единичный сигнал на выходе 21 (ск нал ошибки) будет появля гься при следующих комбинациях входных сигналов

Я)

1) если единичный сигнал присутствует на входе 29 и одновременно хотя бы на одном из входов 24, 25, 26, 27 и

28 (пути прохождения сигналов: элемент

ИЛИ 35, либо элемент ИЛИ 36, элемент

ИЛИ 40, элемент И 45, элемент ИЛИ

46);

2) если единичный сигнал присутствует на выходе 22 и одновременно либо на

64 20 выходе 23, либо на входе 30, либо на выходе 20, (пути прохождения сигналов: элемент ИЛИ 41, элемент И 47, элемент

ИЛИ 46);

3) если единичные сигналы одновременно присутствуют на входе 32 и выходе

20 (пути прохождения сигналов: элемент

И 48, элемент ИЛ И 46 ) .

Время задержки Т элемента 60задержки 49 блока перезаписи информации 8 выбирается из следующих соображений. Наиболее неблагоприятная (с точки зрения времени распространения сигнала в сумматоре) ситуация возникает при сложении следующих 1-кодов Фибоначчи:

При сложен