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

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

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

CoIo3 Co&& TcKNx

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

Республик

<11981993

1 (61) Дополнительное к авт. свид-ву(22) Заявлено 23.02, 81 (21) 3251800/18-24 р1) М. Кл.э.

6 06 F 7/49 с присоединением заявки Но»

ГосударстаеннмЯ «омнтет

СССР но делам нзобретеннЯ н от«рытнЯ (23) Приоритет—

РЗ1УДК681. 325 (088. 8) Опубликовано.15.1-282. бюллетень HP 46

Дата опубликования описания 15. 12. 82 (72) Авторы изобретения

Г.В.Кремез, И.A.Âàðàíos, В.В.Роздобара, В.П.Лачугин и И.Й.Захарчук

/ р у

Ь е (71 ) Заявитель (54) СУИИАТОР КОДОВ ФИБОНАЧЧИ

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

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

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

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

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

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

Поставленная цель достигается тем, что суьиатор кодов Фибоначчи, содер1жащий одноразрядные двоичные сумматоры и элемент ИЛИ, причем первый и второй входы слагаенаах каждого о -го одноразрядного сумматора подключены, соответственно, к шинам первого и второ" го слагаемых устройства, первый вход пе« реноса е -го одноразрядного сумматора пс ключен к первому выходу переноса

1p (g-1)-го одноразрядного сумматора, второй вход переноса Г -го .одноразрядного сумматора подключен ко втоpoesy выходу переноса (с t2)-го одно1 азрядного сумматора, выход суван

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

8-го одноразрядного двоичного су«&еатора подключен к 6 -му входу элемента ИЛИ, выход которого является вы ходом контроля, содержит трехвходо-. вой одноразрядйый двоичный сумматор, первый и второй входы слагаемых которого подключены соответственно к шинам первого и второго слагаемых, вход переноса подключен к третьему выходу переноса второго одноразрядного двоичного сумматора, выход сум мы трехвходового одноразрядного двоичного сумматора подключен к шине сумвн, а выход .переноса подключен к первому входу элемента ИЛИ, третий

981993 вход переноса F -ro одноразрядного сумматора подключен к третьему выходу переноса (Š— Z)-го одноразрядного сумматора.

Одноразрядный двоичный сумматор содержит трехвходовой одноразрядный двоичный сумматор, элементы ИЛИ, элементы И и элементы НЕ, причем первый и второй входы слагаемых трехвходового одноразрядного двоичного сумматора являются соответственно, 10 первым и вторым входами слагаемых одноразрядного двоичного сумматора, вход переноса трехвходового одноразрядного двоичного сумматора подключен к выходу первого элемента ИЛИ, первый и второй входы которого соединены с первым и вторым входами первого элемента И, соответственно, и являются первым и третьим входами переноса одноразрядного двоичного сумматора, выход первого элемента И является KQHTpoJIbHHM выходом одноразрядного двоичного сумматора, выход суммы трехвходового одноразрядного двоичного сумматора подключен ко входу йервого элемента НЕ, к первым входам второго, третьего и. четвертого элементов Й и к первому входу второго элемента ИЛИ, выход первого элемента НЕ соединен с первыми входами пятого и шестого элементов И, выход переноса трехвходового одноразрядного двоичного сумматора подключен ко входу второго элемента НЕ, ко вторым входам третьего и шестого элементов

И и к первому входу седьмого элемен- 35 та И, выход второго элемента НЕ подключен ко вторым входам второго, четвертого и пятого элементов И, третьи вх. ды третьего, четвертого и пятого элементов И подключены ко второму 40 входу второго элемента ИЛИ и ко входу третьего элемента НЕ, выход которого соединен с третьими входами второго и шестого элементов И, вход третьего элемента НЕ является вторым входом пе- 45 реноса одноразрядного дво чикаго сумматора, выходы второго, третьего и пятого элементов И подключены, соот" ветственно, к первому, второму и третьему входам третьего элемента

ИЛИ, выход которого является выходом сумм одноразрядного двоичного сумматора, выходы четвертого и шестого элементов И подключены, соответственно, к первому и второму входам четвертого элемента ИЛИ, выход которого является первым выходом переноса одноразрядного двоичного сумматора и подключен к первому входу пятого элемента ИЛИ, выход второго элемента ИЛИ подключен ко второму входу 0 седьмого элемента И, выход которого является вторым выходом переноса одноразрядного двоичного сумматора и подключен ко второму входу пятого элемента ИЛИ, выход которого является 65

s (v Pt,t-2 ею,е sg ре,е. ре,а+

О О 0 О О О

0 О 1 1 О О

1 0 О 1 О

0 1 1 О О 1

1 О О 1

О О

1 0

О 1

О 1

1 О

1 О

1 1 О О

1 1

При составлении таблицы полагалось, что на входы трехвходового одноразрядного двоичного сумматора тРетьим выходом переноса одноразрядного двоичного сумматора.

В результате на вход каждого Е -ro одноразрядного сумматора подаются пять сигналов. Одновременно единичные значения принимать могут только че-, тыре из них, так как слагаемые поступают на вход сумматора в нормальной форме, т.е. в двух соседних разрядах кода слагаемого одновременно не могут находиться единицы, в результате одновременно не могут возникнуть переносы в 3 -й разряд из (В - 1)-го и (3 -2)-го разрядов. Суммирование в Е -м одноразрядном двоичном сумматоре происходит следующим образом: если на входах сумматора единичных сигналов нет, то единичные сигналы переносов в другие разряды не возникают, и формируется нулевой сигнал сумма в разряде; если на входах сумматора один единичный сигнал, то единичные сигналы переносов не позникают, формируется единичный сигнал сумки в разряде; если на входах сумматора два единичных сигнала, то формируются единичные сигналы переносов в (8+1)-й и в (e-2)-й разряды и нулевой сигнал сумьы в данном разряде; если на входах сумматора три единичных сигнала, то формируются единичные сигнапы переносов в (8+2)-й и (6-2)-й разряды и нулевой сигнал сумки в данном разряде; если на входах сумматора четыре единичных сигнапа то формируются единичные сигналы переносов в (f+2)-й и Я-2)-й азряды и единичный сигнал суммл в данном разряде.

В таблице представлены показатели, поясняющие работу 8 -го одноразрядного .сумматора

981993

РЕ,е.г =Р(Ре.г,е vS) ЗО

:ббдаются сигналы суммируеиих цифр

Is данном разряде а,Ье и сигнал

Pe e Ч РЕ.г е где РЕ. e - сигнал переноса иэ ((-1)-го разряда в f -й разряд; РЕ. g - сигнал переноса из (Е-Z)го разряда в 3 -й разряд.

В таблице обозначено: S - -сигнал суюы трехвходового одноразрядного двоичного сумматора: Р - сигнал пере» носа трехвходового одноразрядного двоичного сумматора; PgiZg - сигнал переноса в Е -й разряд из (8+2)-го разряда БЕ - сигнал сумки одноразРядного сумматорами РЕЕ«, РЕ,Е+г, РЕЕ.g -" сигналы переноса иэ 3 -ro разряда соответственно в (6+1)-й, (В+2)-й, (f-2)-й разряды.

На основе анализа приведенной таблицы запишем логические функции, реализуемые одноразрядным двоичным сумматором. РРе.г.еЧ 8 Ъке V SPPe 2,ð

РЕ,е« = РРЕг,еЧ ЯРРЕ

P е,е-г=Pe е.1ЧРе,е+ кроме функций суммирования в одноразрядном сумматоре реализуется функция контроля

Ке = Ре-,е Ре-г.е где КŠ— сигнал ошибки, которая следует от невозможности одновременного появления переносов из (Е -1) -го и (Е-2)-ro разрядов в Е. =й.

На основе данной логики строится сумматор Фибоначчи.

На фиг. 1 приведена структурная схема сумматора кодов Фибоначчи; на фиг. 2 - функциональная схема одноразрядного сумматора.

Сумматор кодов Фибоначчи содержит трехвходовой одноразрядный двоичный сумматор 1, и ((и+1) - число разрядов суммируемых кодов) одноразрядных двоичных сумматоров 2, элемент ИЛИ 3 на (и+1) входов 4. Трехвходовой одноразрядный двоичный сумматор 1 предназначен для суммирования цифр нулевого разряда кодов Фибоначчи и переноса, который может возникнуть из третьего разряда Фибоначчиевого кода с весом

"2" при суммировании. Выход переноса трехвходового одноразрядного двоичного сумматора служйт для фиксации сшибки. Одноразрядный сумматор, 2 служит для суммирования сигналов переносов и цифр слагаеыас.в данном разряде, а также для фиксации ошибки в

:работе сумматора кодов Фибоначчи.

:Элемент ИЛИ 3 предназначен для сборки сигналов контроля Х Е ((О, 1..... и) от всех одноразрядных сумматоров и трехвходового одноразрядного двоичного сумматора и формирования общего сигнала ошибки K в работе сумМатора кодов Фибоцаччи. На фиг. 1 не пока заны неиспользуемые выходы и входы

n-ro (n-1)-го первого и второго одноразрядных сумматоров 2.

Одноразрядный сумматор 2 содержит трехвходовой одноразрядный двоичный сумматор 5, три элемента HE 6-8,пять трехвходовых элементов P. 9-13, первый ,и второй двухвходовые элементы И 14

Ia 15, трехвходовый элемент ИЛИ, 16р четыре двухвходовых элемента ИЛИ 1720, предназначенные для реализации логических. функций.

8е Ре,е. ° Ре.е-г ° Ре, е z ° Ке

Устройство работает следующим образом.

Одновременно на входы слагаеьнх устройства поступают коды Фибоначчи в нормальной форме (А и В):

А - алан1 ап ° а2 а < aà ° В * ьь Ь„.,b„.z ... ьеЬ„Ье, где а,, ь„- двоичные цифры в i è разряде кода .(i 0,1,...., n)

Формируются переносы в калщ@м одноразрядном сумматоре 2 и первая промежуточная сузанна, затем осуществляется подсуммирование переносов, образование второй промежуточной сум мя и новых переносов. И так до тех пор, пока не прекратится образование переносов и на выходах сумматоров

2 и 1 йе образуется код суви а Sll 4Sll 2 . 2 1 0 ° где S - двоичные цифры в i-м разря-, де кода (10,1,...,n).

В дальнейшем этот код переписыва45 ется иэ сувзеатора на нормалиэатор, .где с помощью операции свертки про-; исходит нормализация кода реэульта.с . та. Если при суммировании нарушено контрольное соотношение, то формиру5О ется соответствующий единичный сигнал КЕ, который поступает на элемент

ИЛИ 3 и порождает íà его выходе единичное знечение, т.е. формируется сигнал ошибки K. При этом сигнал сшибки Кзформируется исходя из того, что сумкйруеьые коды находятся в нормальной форме, и в их нулевых разрядах должны быть нули, а следовательно, единичный сигнал на выходе переноса трехвходового двоичного одноразрядного сумматора 1 сигнализирует об ошибке.

Пример сложения: A=B=000101010101000

981993

Веса разрядов

Фибоначчневого кода

610 377 233 144 89 55 34 21 13 8 5 3 2 .1 1

0 0 О 1 О 1 О 1 0 1 0 1 0 0 0 A

0 0 О 1 0 1 0.1 0101000

Первая промежуточная сумма

О О О О 0 О О О О 0 0 О О 0 О

Возникшие переносы

° ° ° ° ° ° °

1 1 1 1 1 р

1„ +л

1 1 Р р .Вторая промежуточная сумла . 0 О . 1 0 1 0

0 1 О 0 0 1 О 1 0 1 0 О О 1 О.

Код суммы

В данном случае код суммы получился в нормализованной форме. Сложение выполне-30 но посредством трех циклов суммирования.

Рассмотрим сложение этих же чисел A и В в известном сумматоре

О О О 1 0 1 О 1 0 1 О 1 0 О О А т

0 0 О 1 .0 1 0 1 0 1 0 1 О О 0

Первая промежу- 0 0 0 0 0 0 0 0 О 0 v 0 0 0 0 точная сумма

Возникшие переносы

1 1 1

1 1 1 1

Рг,Е1;

РЕ,Е-Z

О О 1 О 1 1 1 1 1 1 1 1 0 1 0

Код суммы

Код суммы получен в ненормализиро-. .произвести нормализацию ванной фореле, поэтому необходимо тата: резуль1 1 1 1 1 О 1 О

1 1 1 1 О 1 О

1.0 1 0

0 1 0 1 О

1 0 1 О 0 О 1 0

О 1 О О 0 1 О

О 1 О О О 1 О

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

В данном сумматоре кодов Фнбоначчи формируется частично нормализованный код суммы вместо ненормализованного, как это имеет место в из,вестных сумматорах, в результате че0 О 1 Р 1 1

О 0 . 1 О 0 1

О 1 О О О 1 0

1 0 1 О 1 О 0 1 0 е е

Р е,е-г

1 1 РЕ,Е+г

981993 го возрастает среднее быстродействие р сумматора. Ъ

Формула изобретения

1.Сумматор кодов Фибоначчи, содер- 5 жащий одноразрядные сумматоры и элемент ИЛИ, причем первый и второй входы слагаеьых каждого -го одноразрядного сумматора подключены к шинам первого и второго слагаемых соответ- 10 ственно, первый вход переноса 3 -го одноразрядного сумматора подключен к первому выходу переноса ((-1) -го одноразрядного сумматора, второй вход пеРеноса 8 -го одноразрядного )5 сумматора подключен ко второму выходу переноса (0+2)-ro одноразрядного сумматора, выход сумы k -го одноразрядного сумматора подключен к шине сумма, контрольный выход 3 -ro одно- О разрядного суьиатора подключен к

3-му входу элемента ИЛИ, выход. которого является выходом контроля, о тл и ч а ю шийся тем, что, с целью Повышения быстродействия, он содержит трехвходовой одноразрядный двоичный сумматор, первый и второй входы слагаемых которого подключены соответственно к шинам первого и второго слагаемых, вход переноса подключен к третьему выходу переноса второго одноразрядного сумматора, выход суммы трехвходового одноразрядного двоичного сумматора подключен к шине сумы, а выход переноса .подключен к первому входу эле- 35 меНта .ИЛИ, третий вход переноса 0 -rd одноразрядного . сумматора подключен к третьему выходу переноса (О-2)-ro одноразрядного. сумматора.

2. Сумматор по п.1, о т л и ч а ю- 40 шийся тем, что, одноразрядный сумматор содержит трехвходовой одноразрядный двоичный сумматор,эле.менты ИЛИ, элементы И и элементы НЕ, причем пеРвый и втоРой входы слагае- 45 алых трехвходового одноразрядного двоичного сумматора являются соответственно первым и вторым входами слаraewx одноразрядного сумматора, вход переноса трехвходового одноразрядного двоичного -сумматора подключен к выходу первого элемента ИЛИ, -первый и второй входы которого соединены:соответственно с первым и вторым входами первого элемента И и являются первым и третьим входами переноса одноразядйого сумглатэра соответственно, ыход первого элемента И является контрольным выходом одноразрядного сумматора, выход сумы трехвходового одноразрядного двоичногб сумматора подключен ко входу первого элемента

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

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

Источники информации, принятые во внимание рн экспертизе

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

Р 732864, кл ° G Об F 7/49, 1980.

2. Стахов. A.Ï. Введение в алгоритмическую теорию измерения, М., "Советское радио", 1977, с. 132-138; (прототип).

98199 3

flic. 8

Составитель Н. Захаревич

Техред A.Лч Корректор И. Король

Редактор М. Товтин

Закаэ 9712/68 Тирак 731 Подписное

ВНИИПИ ГОсударственного комитета СССР по делам иэобретений и открытий

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

Филиал ППП "Патент", г. Ужгород, ул; Проектная, 4