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

 

Изобретение относится к автоматике и вычислительной технике и может быть использовано как при синтезе цифровых устройств, так и с целью обеспечения их тестового и аппаратурного контроля. Целью изобретения является расширение функциональных возможностей за счет нахождения, исходя из вектора истинности булевой функции N переменных, не только ее ориентированных и неориентированных производных произвольной кратности, но и коэффициентов любого из 2<SP POS="POST">п</SP> ее полиномиальных представлений /полиномов Жегалкина/. Выбор режима работы осуществляется посредством подачи потенциала логического нуля или единицы на управляющий вход. При этом код в регистрах указывает тип производной по каждой из переменных - в первом режиме, а коэффициенты каждого из 2<SP POS="POST">п</SP> полиномиальных представлений необходимо вычислить - во втором режиме. Вычисление 2<SP POS="POST">п</SP> - компонентного вектора искомых величин осуществляется за п рекурсивных шагов, каждый из которых выполняется за такт. В течение каждого шага над определенными компонентами обрабатываемого вектора выполняются логические операции И, НЕ или НЕРАВНОЗНАЧНОСТЬ. Результаты этих операций, необходимые в данном режиме, выбираются коммутатором и по окончании такта заносятся в блок памяти. В первом такте обрабатываемый вектор считывается со входной шины данных, а в последующих - с выходов блока памяти. По завершении п-го такта на выходах блока памяти имеет место, в зависимости от режима, вектор коэффициентов полинома Жегалкина или вектор истинности булевой производной. 6ил.

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

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

РЕСПУБЛИК

„.SUÄÄ 1518825 A 2 (51)4 G 06 F 7 04 15 31

ВЖВ 638АН

plTLHT}l3;}. „ ",.-; }.:i Êö

Е " .),I..А

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

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

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

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

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

9 1370651, кл. С 06 F 7/04, 1986. (54), УСТРОЙСТВО ДПЯ ВЬ1 П1СЛЕНИЯ ЕУЛЕBbIX ПРОИЗВОДНЫХ (57) Изобретение относится к автоматике и вычислительной технике и може1 быть использовано как при синтезе цифровых устройств, так и с целью обеспечения их тестового и аппаратурного контроля, Целью изобретения является расширение функциональных воэможностей sa счет нахождения, исходя из вектора истинности булевой функции и переменных, не только ее ориентированных и неориентированных производных произвольной кратности, но и коэффициентов любого из 2 ее полинои миальных представлений (полиномов

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

Целью изобретения является расширение функциональных возможностей

Жегалкина) . Выбор режима работы осуществляется посредством подачи потенциала логического нуля кпи единицы на упр-.àëÿþùèé вход. При этом код в регистрах указывает тип производной по каждой из переменнык — в первом pe h жиме, а коэффициенты каждого из 2 полиномиачьных представлений необходимо вычислить во втором режиме. Вычисление 2 — компонентно ro вектора ь искомь:х вел .чин осуществляется sa n рекурсивных шагов, каждый иэ которых выполняеrcH за такт. В течение каждсго шага над определенными компонентами обрабатываемого вектора выполняю.ся логические операции И, НЕ или ф

НЕРАВНОЗНАЧНОСТЬ. Результаты этих операций, нсобходимые в данном режиме, выбираются коммутатором и по окончании такта заносятся в блок памяти.

В первом такте обрабатываемый вектор считывается со входной шины данньос, а в последующих — с выходов блока памяти. По завершению п-го такта на выходах блока памяти имеет место, в за а висимос т.— от режима, вектор коэффициентов полинома Жегалкина или вектор 0 7 истинности булевой производной. 6 ил. 00 за счет нахождения коэффициентов полинома Жегалкина булевой функции.

На фиг. 1 приведена блок-схема устройства для вычисления булевых произ- 1 ) водных; на фиг. 2-6 — структура первого коммутатора, блока памяти, группы элементов НЕРАВНОЗНАЧНОСТЬ, блока вычислений и второго коммутатора соответс твенно.

15!882

Устройство (фиг. 1) содержит входы

1 и 2, коммутаторы 3 и 4, группу 5 элементов НЕРАВНОЗНАЧНОСТЬ, сдвиговые регистры 6 и 7, блок 8 вычислений, блок 9 памяти, счетчик 10, вход ус5 тановки в исходное состояние 11,, тактовый вход 12 и управляющий вход

13.

Первый коммутатор 3 (фиг. 2) сои держит 2 (n — количество переменных булевой функции) мультиплексоров

3,,..., 3. „, Управляющий вход 14, информационные входы 15 и 16, выход 17.

I5

Блок 9 памяти (фиг. 3) включает в себя 2 D-триггеров 9,,...,9 .

Группа 5 элементов НЕРАВНОЗНАЧНОСТЬ (фиг . 4) состоит иэ 2" сумматоров по модулю два 5 „...,5,„

Блок 8 вычислений (фиг. 5) содер" жит 2 элементов НЕ 20,. ..20 „ и

2 элементов И 18,,...,18 „, вход 19 и выходы 21 и 22.

Коммутатор 4 (фиг. 6) содержит и

2 мультиплексоров 4,...,4,, управляющие входы 23, информационные входы

24-27, выходы ?8.

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

Управление устройством осущестьляется с помощью дву.: сдвиговых ре истров 6 и 7 и у ;.равляющего входа 13.

Для работы устройства в режиме 1 на вход 13 подается сигнал "0", а на сдвиговые регистры 6 и 7 по входу 2 подаюгся управляющие сигналы Ь

h, ЧEòíûe h (" =- i и) Величиль; по

1 11 Э ступают с входа 2 на параллельные входы сдвигового регистра 6, а нечетнь;е 11,, — с входа 2 на соответствующие нхоцы регистра 7. Cогласно

45 кодовои комбинации (О, h ;, h z,,) устройство в режиме 1 выполняет следующие преобразован и булево.:- : функции по ле х

001 -- булева функция дифферен пру50 ется неориентировано; 010 — булева функция дифференцируется ориентировано на уменьшение; 011 — булеза функция цибференцирована ориентировано

55 на увеличение.

Для работы устройства в режиме 2 на вход 13 подается сигнал "1", на вход 2 — и спеповательность управля1 4 клцих сигналов О, ?1„, О, h„,,0, h Причем нули с входа 2 подаются на параллельные входы сдвигового регистра 6, а значения Ь (д=!,п) — на входы регистра 7. Величина h. равна

1 нулю, если переменная х! не инвертирована, и h, I, если соответствующая переменная инвертирована. В соответствии с информацией, хранимой в регистре 7, устройство выполняет необходимые преобразования исходной булевой функции.

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

Рассмотрим работу устройства в режиме 2 (вычисление коэффициентов полинома Жегалкина) в случае булевых Функций от двух переменных.

Для работы устройства в этом режиме на управляющий вход !3 подается сигнал "1", а на вход 2 — последовательность сигналов О, h 1, О,,h,. Причем сигналы "0" подаются на управлякидие параллельные входы регистра 6, а значения ht u h на входы регистра 7.

На выходах регистров 6 и 7 в первом такте присутствуют сигналы 0 и

h, а во втором 0 и h, соответственно.

На вход il поступает сигнал, который устанавливает счетчик 10 и блок

9 памяти s нулевое состояние, а так же разрешает запись в сдвиговые регистры 6 и 7 информации со входа 2.

Со входа 1 на информационные входы 15 коммутатора 3 подаются сигналы

Й, f „ f, f3, определяющие данную оулеву функцию.

В первом такте с выходов счетчика

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

3,, 3, 3, 3 первого коммутатора 3 поступает кодовая комбинация (0,0).

В результате величины f,, f.„, передаются на выходы 17, 17, 17 г

17 коммутатора 3.

Зти сигналы с выходов 17 коммутатора 3 поступают на группу входов 24 второго коммутатора 4 и на группу 5 элементов НЕРАВНОЗНАЧНОСТЬ. После преобразований на выходах группы 5 получаем сигналы (f,8 f,) и (f O f >), которые поступают на входы 25„ и 25, второго коммутатора 4 соответственно.

1518825

С управляющего входа 13 на первый адресный вход АО мультиплексоров 41, 4,, 4З, 44 второго коммутатора 4 по1 дается сигнал "1". С выводов. 23 и

23 на адресные входы А! и А2 тех же мультиплексоров поступают сигналы

0 и h,, которые приходят с выходов регистров 6 и 7 соответственно. В результате на выходах первого и второго мультиплексоров коммутатора 4 присутствуют значения (f,h,Vf, h,) и (f Ь,vf>h,), тождественные (f h,э

& f,h,) и (f,ti,ä f, h,) соответственно. В алгебре Жегалкина имеет место тождество х vy>: & у+ ху, которое в данном случае записывается следующим образом:

f,h,V f,h, f,h,e f, h,elf,h f, h, .

Поскольку h,h, О, то данное выражение имеет вид:

f h,чй, h1,f 0h,O f, Ь,.

На выходах двух других мультиплексоров 4 и 44 присутствует информация с пятых и шестьж, в зависимости от значения Ь, информационных входов, а именно (f„Ж f .) и (f„О f з). 3О

Сигналы с выходов 28,, 28, 28 з и

284.коммутатора 4 поступают на информационные входы блока 9 памяти.

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

35 величины (fog@f, Ь1) (f h

Во втором такте информация с выходов устройства поступает на группу входов 16 коммутатора 3. С выводов 23

1 и 23 на адресные входы А) и А2 тех же мультиплексоров поступают сигналы 0 и h» которые приходят с выходов регистров 6 и 7 соответственно. В результате на выходах мультиплексоров

4, и 4 коммутатора 4 присутствуют значения (f h, u f,h,) и (f Ь„vf h „), тождественные (Е„Ь, f,h ), (f Ü, E

Ы f >h,) соответственно.

На выходах двух других мультиплексоров присутствует информация с 5-х или 6-х (в зависимости от значения

h ) информационных входов, а именно (1 & f,) и (f O f q). информация с выходов мультиплексоров 4,, 4, 4, 44 поступает на соответствующие вьмоды 28,, 28,, 28, 28 коммутатора 4, с которых проходит на информационные входы блока 9 памяти. По окончании синхроимпульса эта информация записывается в D-триггеры и на выходах устройства присутствуют следующие величины:

I (f h<& Г,Ь,), (Е,Ь, О f УЬ,) 4 (Е,Ю Еч) э (4 з ) °

Во втором такте информация с выходов устройства поступает на вторую групЬу входов 16 первого коммутатора

3. С выхода счетчика 10 на управляющие входы мультиплексоров 3,...,3 коммутатора по входу 14 передается кодовая комбинация (01). Следовательно, подключается вторая группа информационных входов 16 первого коммутатора 3 и на его выходы 17„, 17, 17, и !7+ проходят величины (f h,0 f,h, ), if „h Ы f Ь,), (Е Ю f,), (f

24 второго коммутатора 4 и на входы группы 5 элементов НЕРАВНОЗНАЧНОСТЬ, получают значения (Е„Ь,Ы f,h,) O

&(f h 5 fэЬ,) и (f OЕ,) Ю(f Г ), которые подаются на информационные входы 25, и 25 т второго коммутато— ра 4.

На адресных входах АО, Al, А2 мультиплексоров 4,,...,44 коммутатора 4 во втором такте присутствуют величины 1, О, h q с управляющего входа 13 и выходов сдвиговых регистров 6 и 7 соответственно.

В результате, на выходы 28...;., 28 4 коммутатора 4 проходят сигналы (ОЬ1 f hi)h+(f h4O+f >h1)h и (Е,С f )hi®(f С f )hi с выходов мультиплексоров 4, и 4 и сигналы (f h,Ã

G f,h,) &(f h,РЕ Ь,) и (f Of,)(8

O+ (f ® f ) с мультиплексоров 4 3 и 44 со отв етс твенно .

Эти значения поступают на информационные входы блока 9 памяти и по окончании синхроимпульса с входа 12 записываются в триггеры.

Таким образом, на выходах устройства, функционирующего в режиме 2, по окончании п=2 тактов присутствуют сигналы: а O< f h )h ©(f,уh (f 3Ь1)h21 (й,СЕ, )h 8(f 0+ f, ) Ьг; (foh,P f4h )O(f h,<+ f5h,); (foЯ,) C3(fqO,), 1518825

15 соответствующие коэффициентам полинома Жегалкина.

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

1. Устройство для вычисления буле- 15 вых производных по авт. св. - 1370651, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет дополнительного вычисления коэффициентов полиномов Жегалкина булевых функций, в него введен вход управления режимом,который подключен к третьему.управляющему входу второго коммутатора, 2. Устройство по п. 1, о т л и ч а ю щ е е с я тем, что второй коммутатор содержит 2 мультиплексоров, где n — количество переменных булевой функции, причем i-й разряд первого инФормационного входа второго ком- 30 и мутатора, i=1,3,5,...,2 — 1 соединен с гервым и пятым разрядами информациill онного входа (---)-rn мультиплексора

1

j H разряд первого информационного входа второго коммутатора, j =2,4,6..., н

2, соединен с шестым разрядом информационно ro входа (j /2) — го мультиплексора и первым разрядом информаUHoHHoro входа (2" + j /2) -го мультиплексора, К-й разряд второго информационного входа второго коммутатора, K=1,2...,,2", соединен с вторым разрядом информационного входа -ro мультиплексора и вторым, пятым и шестым разрядами информационного входа (2" +К)-го мультиплексора, К-й разряд третьего информационного входа второго коммутатора соединен с третьим разрядом информационного входа К-ro мультиплексора и третьим разрядом информационного входа (2 +К)-го мультиплексора, K-й разряд четвертого информационного входа второго коммутатора соединен с четвертыми разрядами информационных входов К-го и (2" +К)-го мультиплексоров, управляющие входы второго коммутатора соединены с адресными входами всех мультиплексоров, выходы которых соединены с выходом второго коммутатора.

1518825

1518825

01 Zf?

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

Редактор Т.Лазоренко Техред Л. Сердюкова

Ко! ректор В. Кабаций

Заказ 6605/53

Тираж 668

Подписное

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

113035, Москва, )i(-35„ Рау.нская наб., д. 4/5

Производственно-издательский комбинат "11птент", г . Ужгород, ул. Гагарина, )0>