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

 

ПРЕОБРАЗОВАТЕЛЬ ФОРМЫ ПРЕДСТАВЛЕНИЯ ЛОГИЧЕСКИХ ФУНКЦИЙ, имею-щий 2 входов и 2 выходов (пколичество логических переменных), о т личающийся тем, что, с целью повьшения быстродействия, преобразователь содержит о. ярусов элементов неравнозначности по 2 элемеиjTOB неравнозначности в каждом, при .этом в каждом R-M ярусе (,,..,h) элементы наравнозначности обрузуют групп по 2 элементов неравнозначности в каждой) входы i-ro элемента неравнозначности первого яруса соединены с

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

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

РЕСПУБЛИК.,Я0„„112428!

g G 06 Р 5/00

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

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

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

ПИ ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3546096/18-24 (22) 28;.01.83 (46) 15.11.84. Бюл.№ 42 (72) М.Ф.Холодный, В.Ю.Ларченко, К.К.Фурманов и В.И.Хлестков (71) Харьковский ордена Ленина авиационный институт им. Н.Е.Жуковского (53) 681.3 (088.8) (56) 1. Авсаркисян Г.С. и др. Представление логических функций в виде полиномов Жегалкина. "Автоматика и вычислительная техника", 1975, № 6, с.6-10.

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

¹ 781822, кл. G 06 Р 15/31, 1978 (прототип). (54)(57) ПРЕОБРАЗОВАТЕЛЪ ФОР Ы ПРЕДСТАВЛЕНИЯ ЛОГИЧЕСКИХ ФУНКЦИЙ, имею41 и щий 2 входов и 2 выходов (n- количество логических переменных), о т— л и ч а ю шийся тем, что, с целью повьппения быстродействия, преобразователь содержит п.ярусов элемен-. тов неравнозначности по 2 " " элемен тов неравноэначности в каждом, при этом в каждом K -м ярусе (K=1,...,п) элементы наравнозначности обрузуют

2 " групп по 2 " " элементов неравнозначности в каждой, входы j-го элемента неравнозначности первого яруса соединены с (2 i -1)-м и 2 1 -м

% и"1ю входами преобразователя (1=1," 2 выходы элементов неравнозначности (39-1 1 -й и (2Д-й рупп Р-ro яруса (8=1,...,2 ""; Р= 1, ..., h-< 1 соединены со входами соответствующих элементов неравноэначности 8 -й группы (Р+1) -го яруса, выходы элементов неравнозначности 9(2q-1)-й и (5. 2q,) -й групп (g= 1 "-, 2" 2 1 1 т=1, ..., и-2! t -го яруса соединены со входами элементов неравнознач- I ности с (2 > )-го по (2 t+% g) -й g -й группы (t + 9 "1 )

-го яруса, входы(2 -го С» элемента неравнозначности .Ъ -й группы d-го яруса (8=1, 2""; d=2„, nf соединены с 2 1(2Ъ-4) -м и 2С" ° 2 h и входами преобразователя, выходы элементов неравноэначности последней группы каждогО яруса и 2 -й вход преобразователя явп ляются выходами преобразователя.

1 11242

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

Известен метод (1) преобразования совершенной дизъюнктивной нор- 10 мальной формы (СДНФ) в полиноминальную форму, который заключается в том, что коэффициенты полинома Жегалкина функции Е(Х1= ч О ч„х„Я

Яц „ х х могут быть вычислены че- 15 2"-1 -> и рез таблицу истинности функции f (x) (или СДНФ) путем умножения на матрицу 8 и суммирования произведений по модулю 2:

P+,tA О „„.О,,P+A„x x„..., )=

a,ot, ...,сх l=ff(OI...,О), Е(1,0(.-,0>,...0 1 -,..,)..., E (1,,1I) 5 и-1 и-1

5и 5 5 51 1 1

Устройство, реализующее такой метод, характеризуется большой аппаратной сложностью.

Наиболее близким к предлагаемому является преобразователь формы представления логических функций, содержащий счетчик, коммутатор, шифратор, счетные триггеры, элементы И и НЕ, З5 и и имеющие 2 входов и 2 выходов, где n — количество переменных логической функции, которое предназначено для преобразования логических функций из совершенной дизъюктивной нормальной формы в полиноминальнуюГ21

Этот преобразователь имеет низкое быстродействие, поскольку резуль1Ч тат формируется за 2 тактов.

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

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

2 входов и 2 выходов (и- количест- 5О во логических переменных), содержит и ярусов элементов неравнозначности по 2" элементов неравнозначности в каждом, при этом в каждом

К-м ярусе (К 1, ...,п) элементы нерав-55

1 ,нозначности образуют 2" групп по

2 элементов неравноэначности в каждой, входы i-ro элемента неравно81 2 значности первого яруса соединены с (2 " ) -м и (2Ц-м входами преобразователя (i 1,...,2" " ), выходы элементов неравнозначности (2 1-1) -й и, (2Ц-й групп P-го яруса (6=1,...,2"

Р=1,..., и-1) соединены со входами соответствующих элементов неравнозначности 1-й группы (Р+1)-го яруса, BhIxopbI элементов неравнозначности

S (2q-1)-й и (S 2q)-й групп, =1,...,Z" - ; m=2; =1,--, -2)

t-ro яруса соединены со входами элементов неравнозначности с (2 )-го

С+ф+ 2 по (2 -1 1 и q и группы (5+q.+1) -го яруса, входы (2 1 " )-ro элемента неравнозначности Ь-й группы d-ro яруса (Ъ= 1,„., 2" " d--2,." ) соединены с 2 (2Ъ.- 1 )-м и

2 ° 2h-м входами преобразователя, выходы элементов неравнозначности последней группы каждого яруса и 2 -й вход преобразователя являются выходами преобразователя.

На чертеже приведена функциональная схема преобразователя формы представления логических функций для случая n=3:

Преобразователь содержит входы

11 — 1, выходы 2„ — 2> элементы неравнозначности 3„ — 3+ первого яруса, элементы неравноэначности

4„ — 4 второго яруса, элементы неравнозначности 5 — 5 третьего яруса.

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

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

F()()=A,Q+A .„()Я х ()Я . х, ()Я,О

ЯЯхх Q+,...ЯА

513 ° 2и1" 2 " п

Особенностью этой формы представления является то что переменная Х> входит только в конъюнкции с номерами (2" "} †(2 "-11 т.е. во вторую половину полинома. Поэтому полином функции F (x) может быть представлен в виде

«(I=(A,О „,О,...,P+A „„ .„...,...Р

11242

3 т.е. полином функции F (х) от и пере. менных представляет собой сумму по модулю 2 полинома функции f от и-1 ( переменной.и умноженного на х„„ полинома функции f от и-1 переменной, причем порядок следования коньюнкций переменных в этих двух полиномах одинаков.

Из формулы (1).-при х = О имеем <"I x,= (", - ., ).,(", - ".- ( и откуда f„(x„, x„„)= F(х„,...,х„»„,p) а при х„=-1 имеем ххх> х ° х= (хq .- -хх-х )= х (хх,...зхх-х)О+

О+ 2(х1 -- ". 1) 81 4

СДНФ в полиноминальную форму ее подфункции Р(х ... х О) и (х ... Х 1)

Обозначим сигналы на входах 1 еобразователя чер сигналы на выходах 2 преобразователя чеРез "1 2 2

Для преобразования формы представления логической функции от переменных из СДНФ в полиноминальную на входы I преобразователя подается таблица истинности функции F(xI= Г(x ... х )

1х "х n) в порядке возрастания наборов, причем х считается младшим разрядом, а х „ — старшим. Таким образом, имеем х

6 - (О,о,, 0,0) 6» F(1,0,... О,О) ...,а „„=Р(11,,1,o), и „1 Е(0,0- Д7), Х ХХ ю.- ° Х

Следовательно, преобразователь формирует на своих выходах коэффи"циенты полинома Жегалкина функции

F (х), т.е. преобразует СДНФ функции F (х) :в ее полиноминальную форму.

В случае использования преобразователя на и переменных для вычисления коэффициентов полинома функции от. К переменных, ken, таблица истинности этой функции подается к на первые 2 входов преобразователя, а результат считывается с его первых 2 выходов:. к

0»пО+» х„О+,--,O+8 „„x„x,,...,x„.

Таким образом, преобразование 55 функции .F (х) из СДНФ в полиноминальную форму может быть получено, если предварительно преобразованы из откуда ()(... Х (... Х ) .

n-e у 1 1 - n-1 /

Пусть полином функции (х„,., «„1,0) имеет вид F (x „, х„,0) =An Q+ A x Q- г5

2 -1

Тогда согласно формуле (1) полином функции F (х) может быть получен следующим образом

F (X j= f (Õ„, ..., К„1) О+ Х„ f> (х„..., X„J=

=х(х„...,x„„o)p+х,(F(K х о(Ох о (, — „,"ц=(л,p+A„„p- о", *

-1 ххххх " х„хр(А Охл х Q+,,В4 х

2 "1

))= ОхА х Q+, Охх

2 -1, 45

"" "х -,",-хО(Я,ЯИ (х Q+(A У(.

P.Q+(<,- о „, ).„..

А ОА„х„О,." О" -, -„«,,"-л„„О

1 2 П-1..,6 n=F(1,1,...,1,1) . .2

Поскольку переменная х старшая, то и для всей первой половинш таблицы истинности х„= О, а для всей второй половины хп= I, Поэтому первая половина таблицы истинности функции F(x1,... ...,х„) представляет собой таблицу истинности ее подфункции F(x„...,x„,0), а вторая половина таблицы истинности функции Г(х,,..., х„,j представляет собой таблицу истинности ее подфункции F(х1,..., х, 1,1)

Предположим, что осуществляется преобразование СДНФ функций Р(х„...,х„ „,0)

Тогда на выходах 2 преобразовате-, ля имеем

-Я н А

2 +2 " 1 1 "

< =А +А п1

2 -1 2

1124281

6 =ся1

21 1Я 1

Имеем .

35

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

Подадим на вхдды преобразователя формы представления логических функ- 5 ,ций от j переменных коэффициенты полинома функции ()(„,...,x, а.„,...,Ы„)= С,QC, xÄQ+...®С„..

10 ... x. =C,,Q+C„x Q+,... Q+C

11 31 21 2-1

=F(x,...,x.,0,xf,„,...,oL„)Qxf(F(x,...,x хх

0,af,,и, )ЯЕ(х„,,х и,Х,иХ.их, ф, )), j+ х " а

3,,...,<„B(0,1) т.е. ь с 631 сy. f6) сУ

2 + 2 х<=F(fXÄfX,,:,fX,. „,0, Х,„,...,Ы„), j-1

14142 . . /3

1 1 ": k1 Ki1 к Я" Р 1- Р5 1 О (д+1 " в)®

В(Е (fxþ Фх;-, Xi x 0 d, х,- Ж„)В

Ое(Р„! Ех,—.. Р,х и . ". и))-и(0, / х0"

" Ff-х и хи "и и)

j-1

3-1 . 1 С: К-1 . 1-1

2.-3 +1 <21, Р„2 = -2

Ki1 т.е. на выходах преобразователя от j переменных формируется таблица истинности функции F(x ...,х aL +,...,о(„} +„ ...«„ 1,О,13, причем йеременная х> в ней считается старшей среди переменных х., — хт

В случае использования преобразователя на и переменных для преобразования формы ..представления функции от К переменных, k(n, на первые 2 входов преобразователя подаIoTcH коэффициенты А — А2 к ма функции, а коэффйциенты СДНФ формируются на первых 2" выходах преобразователя.

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

1124281

Составитель В. Кайданов

Техред М,Надь

Корректор М-. Розман

Редактор А.Долинич

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

Заказ 8280/37 Тираа 698 Подписное

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

113035, Москва, Ж-35, Раушская наб., д.415