Файл: Пакулов, Н. И. Мажоритарный принцип построения надежных узлов и устройств ЦВМ.pdf

элемента

М (хи х 2, •£,. О, 0) = х, х 2 х 3,

М (хи х 2, х 3, 1, 1 )= х, V *2 V ^з-

Условные обозначения трехвходовых элементов И, ИЛИ показаны на рис. 2.7.

2.2. СИНТЕЗ МАЖОРИТАРНЫХ УЗЛОВ КОМБИНАЦИОННОГО ТИПА

Алгоритм синтеза мажоритарных узлов комбинационного типа

Существует класс мажоритарных схем, который пол­ ностью реализуется па УМЭ без использования постоян­ ных уровней напряжения, т. е. а мажоритарном базисе. Количество мажоритарных схем этого класса невелико и

точно равно Mt = J/ N^, где = 22" — общее количе­

ство булевых функций п аргументов.

Однако схемы, реализованные па УМЭ, в ряде случа­ ев могут быть проще аналогичных схем, построенных на базе логических элементов И, ИЛИ, НЕ или па базе любой другой полной системы. Так, например, функция

реализуется на одном пятивходовом УМЭ:

М (хи х , л-,, х 3, л-4) -= л, (х, V -М V У,) V М М -V

Для реализации функции (2.7) на элементах булева ба­ зиса потребуются два элемента И и два элемента ИЛИ.

Рассмотрим один из методов синтеза комбинацион­ ных схем па МЭ [45]. Для эквивалентных преобразова­ ний мажоритарных функций приведем систему равно­ сильностей, вытекающих из свойств мажоритарных функ­ ций:

1)M#X2#Xi = Xl,

2) X i # X 2# X i = X2,

3) Xl#X2#X 3= *2# м # * 3 = =

= *2# * з # М = М # * з # * 2 = х з # Х 1# д : 2,

92

4) х, # л:2 # x 3 == x, # x s # x 3,

5) я, # jf2 # 1 = л-хV -«a.

6)X!#X2#0 = a:iX2,

=' ( * i # * 2 # 0 ) # X 3 # 0 .

10)(^i#x2# 0 ) (5Ji#X 2#0)#X iX3a:4 =

=(*1#*2#0) #(X3#*4#0) #0»

11)(Х1#л:2# х 3^4) # (xi-Qxz^XaXi) #*ix4=

=(*1# * 2#*з) # i 4# 0 ,

12)(*1#Х2#*з) # X # * 4 = (я4#*2#л:з) # * i# * 4,

16)# (*4#*2#* з) # х3=

=*4# (*1# * 2#Хз) #*з,

17)(X4#Xi#X2)# (х4#*1#Хз) #X4 = JC4#X 1#JC2,

18)Xl#.V2# (Х1#Х2#*з) =JCi#JC2#*3,

19)(х4#*1#*з) # * 2 # (*1#*4#*з) =

== (Л'4"Н*-,('141'Л'2) (хЧ^М^-^) ,

20)(*4#*1#X2)#(*4#*1#*3)#*5==

=X4#Xi# (a:2#X3#X5) ,

21)(Xi#*2#X3)#(xi#X2#X3)#X3 =

=*1# (X1#X2#X3)# (х!#Х2#Хз) ,

22)Л'1#х2# (*3#x4# x 5) = (*1#*2#*з) #

#(Xl#*2#*4)#*5-

Между переменными Xi, Хг, x3, *4 и Xs могут иметь ме­ сто только соотношения Xi=x2 или Xi= £2, х2=хз или х2—х 3, Хз=х4 или Хз=х4 и т. д. Поэтому доказательство

справедливости приведенных равносильностей выпол­ няется проверкой равенств 1)—-22) путем подстановки

93

указанных соотношений. Положив, например, в обеих чй стях равенства 17) х«= хь получим

(x !# x i# x 2) # (x i# x i# x 3) # х (= X i#X i#x2,

Xi—Xi.

Аналогично при X/,=xi

(xi#Xt#X2) # (Xi#X!#X3) #X i = X l#X i#X 2,

X2#Xi#.fi = Xl#X1#X 2, X2 = X2.

Следовательно, равносильность 17) доказана. Приведенная система равносильностей позволяет про­

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

Рассмотрим теорему, устанавливающую связь между булевыми и мажоритарными функциями.

Пусть f(xi, х2, х3, г) — произвольная булева функция, где xit xz, х3-— аргументы функции, a z — остаток, вклю­

чающий все остальные аргументы функции. Необходимо заданную булеву функцию f ( x ь Xz, х3, z) представить

вмажоритарном базисе с помощью трехвходовых МЭ. Введем для заданной функции следующие вспомога­

тельные соотношения:

94

Доказательство теоремы сводится к подстановке в при­ веденные равенства соотношений Xi=Xz или Xi = xz. Дей­ ствительно, ПрИ Xi = Xz

= М * М * Uxt = f w

при Xj = х 2

и т. д.

Синтез комбинационных схем на МЭ с помощью приве­ денной теоремы производится в следующем порядке.

1.Для заданной булевой функции определяются вспо­ могательные соотношения (2.8) —(2.11).

2.Из полученных вспомогательных функций выбира­ ют наиболее простые и подставляют их в те соотноше­ ния (2.12) —(2.15), с помощью которых можно получить

более простую мажоритарную форму заданной функции. 3. Если при первом шаге не найдена мажоритарная форма заданной функции, то соотношения (2.12) — (2.15) применяют повторно. При этом аргументы Xi и Хг каждый

раз выбираются независимо.

Если заданная функция принадлежит к классу ма­ жоритарных функций, теорема дает возможность пред­ ставить ее полностью па МЭ без использования постоян­ ных уровней напряжения. Поиск минимальной мажори­ тарной формы заданной функции проводится с помощью равносильностей 1)—22).

Пример 1. Необходимо функцию

2. Так как вспомогательные функции одинаково просты, то лю­ бая из них пригодна для подстановки в соотношения (2.12) —(2.15).

95

Для подстановки в соотношение (2.12) используем две первые функции:

}(хI, х2, х3) = (xi# ^ 2# ati) # (xi#.f2#Jft) 4Мз.

После применения равносильностей 1) и 2) получим следующее со­

отношение:

/(xi, Хг, х3) =Xi#x2#X3.

Схема, реализующая функцию '(2.16), содержит один МЭ.

Пример 2. Необходимо в мажоритарном базисе представить функцию

У— Xi Х2Х3 \/ Х\ Х2Х4 \/ Х1Х2Х3 \/ Х\ХзХц \ J Х1Х3Х5 \/

V Х\Х$х§ \J Х2Х3Х4 \ / Х2Х3Х5 \/ Х2Х4Х5 \J Х3Х4Х5.

Определим вспомогательные функции

К выражению, стоящему в последних круглых скобках, применим

МЭ. Для реализации этой функции на элементах булева базиса потребовалось бы 10 трехвходовых элементов И и один десятивхо­ довой элемент ИЛИ.

96

Пример 3. Представим в мажоритарном базисе функцию

Определим вспомогательные функции

f ххХ2 ~ V XjX3 V Х1Х3Х4 “ *

f — = Х1Х3 \/ Х1Х3Х4 = Х1Х3 \f Х3Х4.

Х\Х2

Представим выражение (2.17) с помощью соотношения (2.12):

2), получим следующие выражения:

f (Xi, Х3, Х4) — XjX3 \/X 3X4, fjejXj= Х]Х4,

f(Xi, Хз, Х4) — (Xi#X3#Xl)#(xi#S3#Xi)#XiX4= X1#X3#X1X4.

Окончательно получим

f(Xи Х2, Хз, Х4) =l[Xi#X2#(xi#X3#XlX4)]#

44[хi44x244 (xi44X344XlX4)]Xl = Xi#X2#(Xi#X3#XiX4) ===

=Xl#X2# [xi#X3# (X!#X4# 0 )]

—равносильности 17) и 6).

Следовательно, заданная функция (2.17) не принадлежит к классу мажоритарных функций.

Синтез типовых мажоритарных узлов комбинационного типа

На основании изложенного произведем синтез наибо­ лее распространенных в вычислительной технике узлов комбинационного типа па базе УМЭ.

Синтез узла равнозначности.

(Соотношение (2.12) и равносильность 4.)

Схема узла равнозначности, построенная на базе УМЭ согласно выражению (2.18), показана на рис. 2.8.

Синтез узла неравнозначности.

у = x tx 2V *iX, = х 3х 2V х ,х 2.

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