Сумматор кодов фибоначчи
Изобретение относится к автоматике и вычислительной технике и может быть использовано в специализированных вычислительных машинах, к которым предъявляются требования повышенной надежности. Целью изобретения является повышение надежности за счет обеспечения функционирования при отказах одноразрядных узлов суммирования. Поставленная цель достигается за счет новой организации связей и решения одноразрядного узла суммирования в сумматоре кодов Фибоначчи, содержащем одноразрядные узлы суммирования и элемент ИЛИ. 1 з.п.ф-лы, 2 ил., 10 табл.
СОЮЗ СОВЕТСКИХ
СОЦИАЛИСТИЧЕСКИХ
РЕСПУБЛИК (Я) 4 G 06 F 7/49, l 1/00
ОПИСАНИЕ ИЗОБРЕТЕНИЙ
Н А ВТОРСКОМ,Ф СВИДЕТЕЛЬСТВУ
ГОСУДАРСТ8ЕННЫЙ КОМИТЕТ
ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ
ПРИ ГКНТ СССР
1 (21) 4337360/24-24 (22) 04.12.87 (46) 30.12.89 Бюл. У 48 (72) А.М.Гусаков (53) 681.325.5(088.8) (56) Авторское свидетельство СССР
Ó 1411735, кл. G 06 F 7/49, 1987.
Авторское свидетельство СССР
В 981993, кл. G 06 F 7/49, 1981. (54) СУММАТОР КОДОВ ФИБОНАЧЧИ (57) Изобретение относится к автоматике и вычислительной технике и может быть использовано в специалиИзобретение относится к автоматике и вычислительной технике и может быть использовано в специализирован ных вычислительных машинах, к кото-: рым предъявляются требования повышенной надежности.
Цель изобретения — повышение надежности за счет обеспечения функционирования при отказах одноразрядных узлов суммирования.
На фиг. 1 представлена схема сумматора кодов Фибоначчи; на фиг. 2 - схема одноразрядного узла суммирования °
Сумматор образуют выход 1 ошибки сумматора, (n + 1) одноразрядных ysлов 2 суммирования и элемент ИЛИ 3.
Одноразрядный узел 2 суммирования содержит с первого по четвертый элементы НЕ 4 — 7, с первого по шестой элементы И 8 — 13, с первого по четвертый элементы И-НЕ 14 — 17, первый 18 и второй 19 элементы ИЛИ, „„ЯО„„1532915 д1
2 зированных вычислительных машинах, к которым предъявляются требования повышенной надежности. Целью изобретения является повышение надежности за счет обеспечения функционирования при отказах одноразрядных узлов суммирования. Поставленная цель достигается за счет новой органиэации связей и решения одноразрядного узла суммирования в сумматоре кодов Фибоначчи, содержащем одноразрядные узлы суммирования и элемент ИЛИ. 1 з.п. ф-лы, 2 ил., 10 табл.
:седьмой элемент И 20, двоичный одноразрядный сумматор 21, с пятого по седьмой элементы НЕ 22 — 24, с восьмого по двенадцатый элементы И 25—
29, с третьего по пятый элементы
ИЛИ 30 — 32, тринадцатый элемент
И 33 и шестой элемент ИЛИ 34.
На фиг. 1 и 2 использованы следующие обозначения: а и  — значения
1-х разрядов суммируемый чисел;
Р;- — значение переноса c . .i-ro ll) ! разряда.в -й разряд; V — сигнал
2 запрета Р g, Vt — сигнал запреь та Р q,g,, V — сигнал запрета
Pl C Vt — сигнал запрета PE fi
6 ь
VC сигнал запрета Рь,, V8 — сигнал запрета Рь„e„Б — сигнал суммы двоичного одноразрядного сумматора; P — - сигнал переноса двоичного одноразрядного сумматора; $ g сигнал суммы одноразрядного узла суммирования; К вЂ” сигнал ошибки, которая следует от невозможности одно1532915 временного появления переносов из ,(1 — 1)-го и (1 — 2)-ro разрядов в
-й в случае всех исправных одноазрядных узлов суммирования.
Незадействованные входы переноса запрета одноразрядных узлов суммиования подключаются к потенциалу
: О"
Ф
Сумматор работает следуищим об разом.
На входы элемента ИЛИ 3 поступает, сигнал ошибки с каждого из однораз рядных узлов суммирования.
На выходе элемента ИЛИ 3 формируется сигнал о наличии ошибки К. На входы слагаемых сумматора поступают а; и В; коды Фибоначчи в нормальной форме. Формируются переносы в каждом одноразрядном узле суммирования, за( тем осуществляется суммирование переносов, образование второй промежуточной суммы и новых переносов. И так до тех пор, пока не прокатится образование переносов и на выходах узлов 25 суммирования не образуется код сум) мы °
Функционирование 1-ro одноразрядного узла суммирования, Пусть на входы запретов V 1-го ,одноразрядного узла суммирования по даются значения согласно табл. 1.
Т а б л и ц а 1
, 1 О 1 О 1 О
40 В этом случае на 1-й одноразрядный узел суммирования поступают переносы с (1 + 2)-ro, (1 — 1)-ro u (1 — 2)-го одноразрядных узлов сум45 мирования. Сигналы поступают согласно табл. 2.
Таблица 2
S0
О 0
t! в
Сигнал 1" с входа U поступает на вторые входы элемента И 8 и элемента И-НЕ 14. Так как сигнал Р, имеет значения "1" и поступает на первый вход элемента И 8 и на вход элемента НЕ 4, .то на выходе элеиента
И 8 формируется сигнал "1". Выход элемента 4 подключен к первому входу элемента И-НЕ 14, следовательно, на первом входе элемента И-НЕ 14 появляется "О" и на выходе этого элемента И-НЕ 14 формируется "l". Так как на втором входе запрета имеется
"0", поступающий на вторые входы элемента И 9 и элемента И-НЕ 15, то на выходе элемента И 9 формируется
"0", а на выходе элемента И-НЕ 15lt1tt
На вторые входы элемента И 10 и элемента И-НЕ 16 поступает "1" с третьего входа запрета 1-го одноразрядного узла суммирования, сигнал
Р р имеет значение "О" и поступает на первый вход элемента И 10 и на вход элемента НЕ 6, поэтому на выходе элемента НЕ 6 формируется
"1", следовательно, на выходе элемента И 10 формируется сигнал "0".
Так как выход элемента НЕ 6 подключен к первому входу элемента И-НЕ 16 и имеет значения ")", на выходе элемента И-НЕ 16 формируется сигнал
It tt
0 . Поскольку сигнал U< имеет знар чение "0" и поступает на вторые входы элемента И ll и элемента И-HE 17, на выходе элемента И 11 формируется сигнал "0", а на выходе элемента
И-НЕ 17 — "1". Сигнал V имеет зна11 И
0 чение 1 и поступает на второй вход элемента И 12. Так как сигнал
Р „р Р имеет значение "l" и поступает на первый вход элемента И 12, на выходе элемента И 12 формирует-.
33 It ь ся 1 . Сигнал 7 имеет значение
"0" и поступает на второй вход элемента И 13, поэтому на выходе элемента И 13 формируется сигнал "0".
Выход элемента И-НЕ 16 подключен к третьему входу элемента И 20. Независимо от значений сигнала на первом, втором и четвертом входах, на выходе элемента И 20 формируется сигнал "0", поступающий на выход К .
Выход элемента И 8 подключен к первому входу элемента ИЛИ 19, поэтому независимо от значений сигналов на втором, третьем и четвертом входах элемента ИЛИ 19 формируется сигнал поступающий на вход переноса элемента одноразрядного двоичного
5 !
О
О О О
0 .. О О
1 О О
1 О О
О 1 О
О I О
1 О
О О 1
О О 1
1 О 1
0 1
О О
1 О
1 О
О 1
1 О
О 1
I 1
1 О
О I
О 1
0 1
О
О
О
1
О
0
50
О
I
О.
1
О
О
1
55
5 153 сумматора 21. Выход элемента И 12 подключен к первому входу элемента
ИЛИ 18 и имеет значения "1", поэтому на выходе элемента ИЛИ 18 формируется сигнал "1".
Значение сигналов а и В равно
"О". На выходе переноса одноразрядного двоичного сумматора 21 имеется значение "!". На выходе суммы S формируется сигнал "!", а на выходе переноса — сигнал "О", Выход суммы имеет значение 1 и подключен к входу элемента НЕ 22. На выходе элемен та НЕ 22 с формируется сигнал "0", поступампий на первые входы элемен-, тов И 25 и 28, на выходе которых формируется сигнал "О", значения вторых и третьих входов элементов И 25 и 28 можно не рассматривать. Сигнал "О" с выхода переноса P двоичного сумматора 21 поступает на вход элемента НЕ 23 и на вторые входы элементов И 27, 28 и 33, поэтому на выходах элементов И 2? и 33 формируется сигнал "О", первые и третьи входы элемента И 27 и первый вход элементов И 33 можно не рассматривать, а на выходе элемента НЕ 23 формируется сигнал "1", поступающий на первые входы элементов И 25, 26 и 29. Так как выход элемента
ИЛИ 18 имеет .значение "1" и поступает на третий вход элемента
И 29» второй вход которого подключен к выходу элемента НЕ 23 и имеет значение "1", на выходе элемента И 29 формируется сигнал "1". Выход элемента ИЛИ 18 подключен к входу элемента НЕ 24, поэтому на выходе эле мента НЕ 24 формируется сигнал "0" ° поступающий на третий вход элемента
И 26. На выходе элемента И 26 формируется сигнал "О" независимо от saaчений на первом и втором входе элемента И 26.
Так как выходы элементов И 25, 26 и 27 имеют значения "О" и подключены к первому, второму и третьему входам соответственно элемента ИЛИ 31, то на выходе элемента ИЛИ 31 формируется сигнал "О", поступающий на выход Sg 1-ro одноразрядного узла суммирования. Так как выход элемемта И 29 имеет значение "1" и подключен к.второму входу элемента ИЛИ 32, на выходе элемента ИЛИ 32 формируется сигнал "1", поступакщий на выход
Р „ . переноса 1-го одноразрядного
2915 6 узла суммирования и на первый вход элемента ИЛИ 34, поэтому на выходе элемента ИЛИ 34 формируется сигнал
"1", поступающий на выход переноса
Р < < 1-го одноразрядного узла
1 суммирования. Так как на выходе элемента И 33 сформирован сигнал Лог. О, поступающий на выход переноса, значение сигнала P ».< 1-го одноразрядного узла суммирования равно "О".
В табл. 3 представлены сведения, поясняющие работу двоичного сумматора, где Т = Р .„ f, Ц = Р, для случая, когда все одноразрядные ysлы суммирования исправны.
1 Таблица 3
Так как слагаемые поступают на вход сумматора в нормальной форме, 35 т е. в двух соседних разрядах могут находиться единицы, в результате одновременно не могут возникнуть переносы в 1-й разряд из (1 — 1)-го и (l — 2)-ro ; В случае появ ления двух .переносов из (1 — 1)-ro и (1 — 2)-ro разрядов йоявляется сигнал К .
В табл. 4 представлены показатели, поясняющие работу 1-ro однораз 5 рядного суммирования.
Таблица 4
I I II I I
S Р R S Р Р P
0 1 1 0 О
1 О О 1 О
1 1 О О 1
О О 1 О О
О 1 О 1 О
1 О О О 1
1 1 1 О 1
1532915 где $; — двоичные цифры в i-и разряде кода.
В дальнейшем этот код переписы5 вается иэ сумматора на нормализатор, где с помощью операции свертки происходит нормализация кода результата. Если нарушено контрольное соотношение, то формируется соответствующий единичный cHFHcUI К, КОТорМ3 поступает на третий элемент ИЛИ и порождает на его выходе единичные значения, т.е. формируется сигнал ошибки K. При этом сигнал ошибки К фОрмируется исходя из тогор что сум мируемые коды находятся в нормальной форме, в их нулевых разрядах должны быть нули, а следовательно, единичный сигнал на выходе переноса двоичного сумматора 1 сигнализирует об ошибке.
Рассмотрим работу сумматора при одном отказе 1-ro одноразрядного узла суммирования.
А=а„...аа
Я = S„... S S
Таблица 5
Сиг
Блок, У
+1 1 1-1 1-2 нал за- +3 1 прета
1-3
V l 1 О 0 1 1 1
V2 О О 1 О 0 О О
V 1 О О О
V 0 1 1 О 0
1 1 1 О 0
U 0 0 0 0 1
О О
О 1
l 0
Сигналы переносов 1-го одноразряд-, ного узла суммирования запрещены, 1-й одноразрядный .узел суммирования в работе не участвует.
П р и м е ч а н и е. Для случжг, с с когда R = Р, S = Sg Р
= Р ц Р = Р „, Р = Рe,евсе одноразрядные узлы суммирования исправны.
Одновременно на входы слагаемых сумматора поступают коды Фибоначчи в нормальной форме (А и.В), В = В e ° еЭ Вр где а;, В; - двоичные цифры в1:
i-м разряде кода (i
= О,l,...n).
Формируются переносы в каждом одноразрядном узле суммирования и первая промежуточная сумма, затем, осуществляется суммирование перено1 . сов, образование второй промежуточ; ной суммы и новых переносов и так, до тех пор, пока не прекратится образование переносов и на выходах одноразрядных узлов суммирования не
Образуется код суммы
В этом случае значение сигналов соответствует табл. 5.
Сигналы переносов указаны в табл. 6.
1532915
Таблица б
Блок, (<
Сиг(нал
РЕ-(,й О
Ра е О
Р «э, .(О
Рб-ъ.е-я
Я
РЕ-,И
Р я-r, p.-ü
Таблица 7
I 1 I
Сигнал запрета
О 1
0
1(4
1 9 . уа
1
0
Таблица В
Блок, Р
Сигнал
1+б
1+5 1+4
1+3 1+2 1+1
1 1-1 1-2 переносов
0 Ре-я,е-< Pe, ee
Рс-4,е-6
РС-s,««6
Ре«,e 6
Pei«,e<
Ре<, e. Pe-<, е
0 Pe Pe««,е«в Pe«e, 4«4 Ре.,e.s Рьа,е.э РС., Е.6 РС «6,Е-4 P e-6,е-< Р с-(,6-4 0 Pelf,ew Pe«4< е Р РЕ.а,e РС.(,Е-(1+3 1+2 1+1 1 Для одноразрядных узлов суммирования, не указанных в табл. 6, сигналы переносов такие же, как для (1 + 3)-ro и (1 - 3)-го блоков. В формировании суммы а и b(. не участвуют и значения их не рассматри- 20 ваются. В формировании переносов переносы. 1-го одноразрядного сумматора не участвуют, следовательно, сумма1III 1+6 1+5 1+4 1+3 1+2 О 0 0 0 О 1 0 0 .О 1 Сигналы переносов T, Q, В, постутор не теряет функционирования при выходе из строя одного одноразрядного узла суммирования. Рассмотрим работу сую<атора для случая выхода из строя 1-го и.(1+3)-ro одноразрядных узлов суммирования„ Сигналы запретов имеют значения согласно табл. 7. 1+1 1 1-1 1-2 1-3 0 0 I 1 1 1 0 0 0 0 0 0 1 .1 1 1 0 0 0 0 0 0 0 0 1 1 0 1 1, 0 лающие в узлы, указаны в табл, 8, 1532915 Таблица 9 1 Блок, В tie +8 1+7 1+6 1+5 1+4 1+3 1+2 1+1 1 1-1 1"2 1-3 Ч 1 7 О 7 О 4 7 1 Ч О О О 1 О О 1 О О 1 1 1 О . О 1 О О 1 0 О О О 1 1 1 О О О О О О О О 1 . О 1 1 О О 0 0 О О О О О О О 1 1 О 1 1 О 1 1 О О О О 1 Таблице 10 1 ! Сигнал елок P лерено са Ф 1+8 1+7 1+6 1+5 1+4 1+3 1+2 1+I 1 1-l 1-2 1-3 т а R ге+т,е е Pc„c cps рс+в,с е Pc.c,cic Pt с,С.с Pc it сс Pc„c,eely Pcqc.c Pc- r, e Pt c,t O Pc-tie. Р с-,сЕ Pt.е,l с.ь,с а P c-cic-c Pc< t-I Pc. °, t-в PC-с, C.c Рс-,с ° Pt- cn Рс,и >с-i,cPc.a,t-с Pc i,c«c Р c ц c.i О Рс а,е.с PC-iC-t Как видно, сумматор не теряет функционирования при выходе иэ строя двух узлов. При вычислении суммы значения а, В), а,ь и Вр,с. не участвуют и на ) результат суммы не влияют. Как видно из табл. 10 и 9, сигнаы переносов с отказом трех .однораовых узлов суммирования блокируютя и сумматор не теряет функционироания. Таким образом, сумматор правильно функционирует при отказах не только 1-го, но и последующих эа ним 3К (где К вЂ” целое число) одноразрядных узлов суммирования. Формула изобретения 1. Сумматор кодов Фибоначчи, содержаший и+1 одноразрядных узлов суммирования (n+1-разрядность кода) и элемент ИЛИ, причем первый и второй входы слагаемых 1-ro одноразрядного узла суммирования (1 1... и+1) соединены с входами 1-х разрядов первого и второго слагаемых сумматора соответственно, выход сум« мы 1-ro одноразрядного узла суммиВ случае отказа трех одноразрядных узлов суммирования 1, 1 + 3, 1 + 6, значения сигналов запретов указаны в табл. 9; значения T Ц и 8 5 находят из табл. 10. рования является выходом 1-ro разряда суммы сумматора, выход ошибки которого соединен с вйходом элемента ИЛИ, 1-й вход которого соединен с контрольным выходом 1-го одноразрядного узла суммирования, первый вход переноса 1-ro одноразрядного узла суммирования подключен к перво45 му выходу переноса (1-1)-ro. одноразрядного узла суммирования, второй вход переноса 1-го одноразрядного узла суммирования подключен к третьему выходу йереноса (1+2)-го одноразрядного узла суммирования, третий вход переноса 1-ro одноразрядного узла суммирования подключен к второму выходу переноса (1-2)-го одноразрядного узла суммирования, отличающийся тем что с целью повышения надежности за счет обеспечения функционирования при отказах одноразрядных узлов суммирования, четвертый вход перено13 1532915 са 1-го одноразрядного узла суммирования подключен к первому выходу переноса (1-2)-го одноразрядного узла суммирования, пятый вход переноса 1-ro одноразрядного узла суммирования к второму выходу переноса (1-3)-ro одноразрядного узла суммирования, шестой вход переноса 1-го одноразрядного узла суммирования подключен к третьему выходу перено.са (1+3)-го одноразрядного узла суммирования с первого по шестой входы запрета 1-ro одноразрядного узла суммирования являются соответствующими входами запрета 1-й группы сумматора. 2 ° Сумматор по п. 1, о т л и— ч а ю шийся тем, что одноразрядный узел суммирования содержит с ,первого по седьмой элементы НЕ, с первого по тринадцатый элементы И, с первого по четвертый элементы И-НЕ, с первого по шестой элементы, ИЛИ и двоичный одноразрядный сумматор, причем первый вход переноса одноразрядного узла суммирования подключен к первому входу первого элемента И и к входу первого элемента НЕ, второй вход переноса одноразрядного узла суммирования подключен к первому входу пятого элемента И, третий вход переноса одноразрядного узла суммирования подключен к первому входу третьего элемента И и к входу третьего элемента НЕ, четвер35 тый вход переноса одноразрядного узла суммирования подключен к первому входу второго элемента И и входу второго элемента НЕ, пятый вход переноса одноразрядного узла суммирования подключен к первому входу четвертого элемента И и к входу четвертого элемента НЕ, шестой вход переноса одноразрядного узла сумин- 4 рования подключен к первому входу шестого элемента И, выходы с первого по четвертый элементов НЕ соединены с первыми входами соответствующих элементов И-НЕ, первый вход запрета одноразрядного узла суммирования подключен к вторым входам первых элементов И и И-НЕ, второй вход запрета одноразрядного суммирования подключен к вторым входам вторых элементов И и И-НЕ, третий вход запрета одноразрядного узла суммиронания подключен к вторым входам третьих элементов И и И-НЕ, четвертый вход запрета одноразрядного узла суммирования подключен к вторым входам четвертых элементов И и И-НЕ, выходы пятого и шестого элементов И подключены соотве:гственно к входам первого элемента ИЛИ, вход переноса двоичного одноразрядного сумматора поцключен к выходу второго элемента ИЛИ, выход седьмого элемента И подключен к контрольному выходу одноразрядного узла суммирования, выход суммы двоичного одноразрядного сумматора подключен к входу пятого элемента НЕ, к первым входам девятого, десятого, двенадцатого элементов И и к первому входу третьего элемента ИЛИ, выход переноса двоичного одноразрядного сумматора подключен к входу шестого элемента НЕ, к второму входу десятого элемента И и к первым входам одиннадцатого и тринадцатого элементов И, пятый вход запрета одноразрядного узла суммирования подключен к второму входу пятого элемента И, шестой вход запрета одноразрядного узла суммирования подключен к второму входу шестого элемента И, первый и второй входы слагаемых двоичного одноразрядного сумматора подключены к перному и второму входам слагаемых одноразрядного узла суммирования, выходы первого, второго, третьего и четвертого элементов И подключены соответственно к входам второго элемента ИЛИ, выходы первого, второго, третьего и четвертого элементов И-НЕ подключены соответственно к входам седьмого элемента И,. выход пятого элемента НЕ соединен с первым входом восьмого элемента И и с вторым входом одиннадцатого элемента И, выход шестого элемента НЕ подключен к вторым вхо-дам BocbMoго, девятого и двенадцатого элементов И, выход первого элемента ИЛИ подключен к входу седьмого элемента НЕ, к третьим входам восьмого, десятого, двенадцатого элементов И и к второму входу третьего элемента ИЛИ, выход седьмого элемента НЕ подключен к третьим входам девятого и одиннадцатого элементов И, выходы восьмого, девятого и десятого элементов И подключены соответственно к входам четвертого элемента ИЛИ, выходы одиннадцатого и двенадцатого элементов И подключены соответственно к входам пятого элеl6 15329)5 рп-1,М Составитель А. Клюев ТехредЛ,Олийнык Корректор С.Черни Редактор Л. Пчолинская Заказ 8100)53 Тираж 668 . Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж-35, Раушская наб., д. 4/5 Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101 мента ИЛИ, выход третьего элемента ИЛИ подключен к второму входу тринадцатого элемента И, выход четвертого элемента ИЛИ подключен к выходу суммы одноразрядного узла суммирования, выход пятого элемента ИЛИ Подключен к первому входу шестого Ьлемента ИЛИ и к первому выходу переноса одноразрядного узла суммирования, выход тринадцатого элемента И подключен к второму входу шестого элемента ИЛИ и второму выходу пере" носа одноразрядного узла суммирования, выход шестого элемента ИЛИ подключен к третьему выходу переноса одноразрядного узла суммирования.