Устройство для вычисления булевых производных

 

Изобретение относится к области автоматики и вычислительной техники и может быть использовано как при синтезе цифровых устройств, так и с целью обеспечения их тестового и аппаратурного контроля. Целью изобретения является расширение функциональных возможностей за счет нахождения, исходя из вектора истинности булевой функции N переменных, не только ее ориентированных и неориентированных производных произвольной кратности, но и коэффициентов любого из 2<SP POS="POST">N</SP> ее полиномиальных представлений ( полиномов Жегалкина). Выбор режима работы осуществляется посредством подачи потенциала логического "0" или "1" на управляющий вход. При этом код на первой группе входов указывает тип производных по каждой из переменных в первом режиме, а также коэффициенты которого из 2<SP POS="POST">N</SP> полиноминальных представлений необходимо вычислить во втором режиме. Вычисление 2<SP POS="POST">N</SP>-компонентного вектора искомых величин осуществляется исходя из вектора истинности заданной булевой функции и реализуется за такт с помощью сети из арифметических ячеек, соединенных определенным образом. Сеть состоит из N уровней, а каждый уровень содержит 2<SP POS="POST">N-1</SP> арифметических ячеек, имеющих по два информационных входа и выхода. С целью настройки арифметические ячейки подключаются к управляющему входу, а также к первой группе входов устройства. По завершении такта вектор искомых величин заносится в блок памяти, поэтому в зависимости от режима работы на его выходах и

(51) 5 G 06 F 7/00, 15/31

В3 ;с,;р,- i i,,I.

° "- <1 Ф

И :"-" 1

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

К д BTOPCHOMY СВИДЕТЕЛЬСТВУ,=. Ф ъ»., г,; ф, СОЮЗ СОВЕТСКИХ

-.. "- 4 г ", ф ;. .:: СОЦИАЛИСТИЧЕСКИХ

4- ;i==- РЕСПУБЛИК

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ П НТ СССР (61) 1388843 (21) 4393839/24-24 (22) 17.03.88 (46) 07.01.90. Бюл. И - 1 (71) Днепропетровский государственный университет им. 300-летия воссоединения Украины с Россией (72) Г.Ф. Криворучка и В.А. Пащенко (53) 681.325(088.8) (56) Авторское свидетельство СССР

У 1388843, кл. G 06 F 15/31, 1986. (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ БУЛЕBbK ПРОИЗВОДНЫХ (57) Изобретение относится к области автоматики и вычислительной техники и может быть использовано как при синтезе цифровых устройств, так и с целью обеспечения их тестового и аппаратурного контроля. Целью изобретения является расширение функциональных возможностей за счет нахождения исходя из вектора истинности булевой функции и переменных не только ее ориентированньгх и неориентированньгх производных произвольной кратности, но и коэффициентов любого и из 2 ее полиномнальных представлений (полиномов Жегалкина). Выбор режима

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

Р 1388843.

„„80„„1534456 А2

2 работы осуществляется посредством подачи потенциала логического "0 или

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

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

1 з.п. ф-лы, 2 ил. ь@ь

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

На фиг. 1 приведена блок-схема устройства для вычисления булевых

1534456

Управление устройством осущест30 вляется подачей на управляющий вход 8 сигнала логического "О" или логической "1" в зависимости от режима работы устройства ("0" — работа в первом режиме "1" — работа во втором режиме)35 и подачей на входы 1, - 16 управляющих сигналов h < -h, åñëè устройство работает в первом режиме, и сигналов

h, 0, h,, 0 0, h 0, если устройство работает во втором режиме.

f,h; f;„h;= f;h; О+ Е;., и;.

Следовательно, на выходах подблока

4, присутствуют величины

Е,ЬЯ f h,; f,0+ Е, > fah,Q+ f3h,; 4О Е, f4пiC) f h, Е4. (0 3f s i Е ",O+ f h1У

f ОЕ79 которые поступают на входы подблока 4 . адресные входи мульт

6 7 иплексо ов 11 и а

1

На входах 10, и 10< арифметических 11< арифметических ячеек 5 подблока 4 ячеек подблока 4 присутствуют сигна- поступают сигналы,, р у

О h . В es льлы f h,® Е,h,; f

Благодаря наличию перекрестных связей на выходы подблока 4 поступроизводных для n = 3 (n — количество переменных булевой функции); на фиг ° 2 — структура арифметической ячейки.

При n = 3 устройство для вычисления булевых производных содержит

2 и 6 входов 1„ — 1, образующих первую группу входов, вторую группу входов 2 - 2> (2 8) усти ройства, 3 — разрядный регистр 3, состоящий из 2 " = 8D = триггеров

34- 38, арифметический блок 4, состоящий из n = 3 подблоков 4 — 4, арифметические ячейки 5, 2 " "= 8 выходов 6 устройства, тактовый вход

7 и управляющий вход 8.

Арифметическая ячейка 5 (фиг. 2) состоит из входов 9 и 9, 10 и

10, двух мультиплексоров 11„ и 20

11, элементов И 12 » и 12, элементов НЕ 13, и 13 и элемента НЕРАВНОЗНАЧНОСТЬ 14 и выходов 15, и 15 ячейки.

Устройство работает в двух режимах: первый режим — вычисление булевых производных; второй режим — вычисление коэффициентов полинома Жегалкина.

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

t.

Рассмотрим работу устройства в режиме вычисления коэффициентов полинома Жегалкина.

На управляющий вход 8 подается сигнал логической "1". На первую группу входов 1< — 16 устройства подаются сигналы h<, О, h< О,.h О, причем

h = О, если соответствующая переменная x;(i = 1,3) входит непосредственно, и h = 1, если она инвертирована.

На вторую группу информационных входов 2 -2 устройства подаются сигналы, определяющие данную функцию, foþ Е1в 4» Е Е4ь

f 6, f„. Эти сигналы поступают на входы 10 < и 10 каждой арифметической ячейки 5 подблока 41 . Через входы 8, 9 „ и 9 на адресные входы мультиплексоров 11< и 11 поступают управляющие сигналы 1, О, h<. Благодаря этому на выходы 15 и 15 мультиплексоров передается информация, сформулированная на пятом или шестом информационном входе мультиплексоров 11, и 11< °

В результате на выходах арифметических ячеек 5 подблока 4 появляется величина f„h; ЧЕ +, h;/j = 0,2" -2 . В алгебре Жегалкийа имеет место тождество xvy=x(g yQ+ху, которое в данном случае записывается в следуюшем виде:

h;Vf „h, = f;h; Cb Е „1;0+ Е,Е М

Поскольку Ь; Ь; = О, то это выражение записывается

1534456

)» 1 (г ® i )hz + (z(+-) (1-,0 К„) О (К,О К,);

)» 1 (0 ) 0 (0 7) ()-40 5) О fg@ 7) метических ячеек 5 подблока 4> пост1 пают величины 1 »,Я Г Ь,)» + (1 h ® Е Ь,)Ь (,О+ 4)»,0+ (f6O+ f7)1,1 (4»,® Ь,) {) (fh)0,Ь,); (f 0+ f ) О+ (f,О+ f,) ° ством перекрестных связей передаются на выходы подблока 4.. В результате на информационные входы D-триггеров 3 -38 регистра 3 поступают сигналы (f,h,О+ Г, Ь,)»,0+ (f,»,0+ f,1, (Е,Ь,О+,Ь,) 0+ (, »,0+,» ) (Е Ь ® f »1)Ь О+ (Г Ь,О+ й7», (Ь)О+ 4Ь)) О+ (4»(®, Ь,)

С входов подблока 4> посредством перекрестных связей на входы ариф(Г,h,@ Г,Ь,)»,0+ (,Ь,Ю f,»,)Ь„ (Ц3+ ()1 0+ (0+ з)»а (о»(® fight) (йЬ(® "з»))1 (fî® f, ) О+ (fz® f );

На адресные входы мультиплексоров

11, и 11 арифметических ячеек 5 подблока 4> через входы 8, 9(и 9 поступают сигналы 1, О, h . Следовательно, величины, сформированные на выходах мультиплексоров, посред((Г0 Ь„О+ й(Ь1) » 9 (fg»(0+ f h> ) »zan»g>+ ((-(1 »,@ fg»() ЬгО+ (4 ЬО+ тЬ<)Ьа)»з ю ((.0+ 4Ь,® (,0+ fg)>)7> O+5(f<>+,)Ь,О+ (.+ )» 3»з

Bfp h) ® f qh() 0 (fzh(0+ 4Ь, )) »P+$(fph(O+ fgh, ) О+ (f hP f y»()j » y

j(f()O+ f q ) @ (fZ8 4 )3»з{+> ((f40+ f5) 0+ (1 О+ Е7)) »Зi

L(f()h(O+, Ь, )»,О+ (fzha®,Ь,)ЬД® ((4»,0+,Ь Ь,О+ (f()h(® f,h, )»Ä, ((Е ® Е, )Ь 9 (fg® и ) Ь )(+3 C(f40+ fg)hzQ+ (fgO+ fg )hz) (((Ь Ю (h, ) Ю ((ah,O+ (ah ) J О+ ((Тi,Ж (5h ) 0+ ((ah,O+ f,h,)j ((® f<) 0+ (0+ ) 0+ P(f Q+ ) 0+ (ьО+ Л

Технико-эк-.::ëæò÷åñêèé эффект. от . ными входами первого и второго мульиспользования изобретения заключа- З типлексоров, выходы которых соединены ется в возможности вычислять не толь- с выходами ячейки, первый информационко производные функции, но и коэф- ный вход которой соединен с входом фициенты полинома Жегалкина за один первого элемента НЕ, первым входом такт при незначительном усложнении первого элемента И, первым входом самого устройства. 40 элемента НЕРАВНОЗНАЧНОСТЬ и первым и пятым информационными входами перФ о р м у л а и з о б р е т е н и.я вого мультиплексора, второй информа1. Устройство для вычисления буле- ционный вход которого соединен с вывых производных по авт. св. 11) 1388843, ходом первого элемента И и вторым о т л и ч а ю щ е е с я тем, что, 45 информационным входом второго мульс целью расширения функциональных типлексора, первый информационный возможностей за счет нахождения коэф- вход которого соединен с вторым инфициентов полиномов Жегалкина буле- формационным входом ячейки, вторым вой функции, в него введен вход за- входом элемента НЕРАВНОЗНАЧНОСТЬ, дания режима, подключенный к третьему 50 входом второго элемента НЕ, первьи настроечному входу каждой арифмети- входом второго элемента И и шестым ческой ячейки. информационным входом первого муль2. Устройство по п. 1, о т л и- типлексора, третий информационный ч а ю щ е е с я тем, что арифмети- вход которого соединен с выходом вточеская ячейка содержит два мульти- 55 рого элемента И и третьим информационплексора, два элемента И, два эле- ным входом второго мультиплексора, мента НЕ и элемент НЕРАВНОЗНАЧНОСТЬ, информационные входы с четвертого по причем настроечные входы ячейки с шестой которого соединены с выходом первого по третий соединены с адрес- элемента НЕРАВНОЗНАЧНОСТЬ и четвер15344 56

Фи. 7

Составитель A. Зорин

Редактор 0. Урковецкая Техред Х.Яндык Корректор В. Кабаций

Тираж 556 Подписное

ВНИИ)1И Государственного комитета по изобретениям и открытиям кри ГКНТ СССР

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

Проиэводственно-иэдательский комбинат "Патент", г.Ужгород, ул. Гагарина, 101 тLM информационным вxopîм гIåðâoãî мультиплексора, выход первого элемента НЕ соединен с вторым входом

7(>5

1у г; я второго элемента И, выход вторс го элемента НЕ соединен с вторым входом первого элемента И.