Устройство для вычисления булевых производных Советский патент 1989 года по МПК G06F17/10 G06F7/04 

1

(61) 1370651

(21)4387308/24-24

(22)01.03.88

(46) 30.10.89. Бюл. S 40

(71)Днепропетровский государственный университет им. 300-летия воссоединения Украины с Россией

(72)Г.Ф.Криворучка и В.А.Пашенко (53) 681.325(088.8)

(56)Авторское свидетельство СССР 1370651, кл. G 06 F 7/04, 1985.

(54). УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ БУЛЕВЫХ ПРОИЗВОДНЫХ

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

Жегалкина). Выбор режима работы осу- ществл чется посредством подачи потенциала логического нуля или единицы на управляющий вход. При этом код в регистрах указывает тип производной по каждой из переменных - в первом режиме, а коэффициенты каждого из 2 полиномиальных представлений необходимо вычислить во втором режиме. Вычисление 2 - компоиентного вектора искомь. х величин осуществляется за п пекурсивных шагов, кажп.ый из которых выполниется за такт. В течение каждого шага над определенными компонентами обрабатываемого вектора выпол- няю .тя логические операции И, НЕ или НЕРАЕНОЗНАЧ1 0СТЬ. Результаты этих операций, необходимые в данном режиме, выбираются коммутатором и по окончании такта заносятся в блок памяти. В первом такте обрабатываемый вектор считывается со входной шины данных, а в последующих - с выходов блока памяти. По завершению п-го такта на выходах блока памяти имеет место, в зависимости от режима, вектор коэффициентов полинома Жегалкина или вектор НСТИННОСТ1-. булевой производной. 6 ил.

СП

|пМ

ел

00 00

1ч

ел

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

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

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

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

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

rsj

315

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

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

Первьй коммутатор 3 (фиг. 2) со- держит 2 (п - количество переменных булевой функции) мультиплексоров 3,,...,, управляющий вход 14, информационные входы 15 и 16, выход 17.

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

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

Елок 8 вычислений (фиг. 5) содержит 2 элементов НЕ 20,,..., 2 элементов И 18,.,.,18, вход 19 и выходы 21 и 22.

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

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

Устройство работает в двух режимах: 1-й - вычисление булевых произ- водных; 2-й вычисление коэ4х})ици- .iTOB полинома Жегалкина.

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

Для работы устройства в режиме 1 на аход 13 подается сигнал О, а на сдвиговые регистры 6 и 7 по входу 2 подаготся управляю1ци е сигналы h,.., b . Ь, (,n) величины поступают с входа 2 на параллельные входы сдвигового регистра 6, а нечетные h

i-i

с входа 2 на соответствующие входы регистра 7. Со но кодовой комбинации (О, Ь,;, ) устройство в режиме 1 выполняет следующие преобратования булевой функции по переменной x,(,n): 000 - булева функция не дифференцируется; 001 -- булева функция дифференцируется неориентировано; 010 - булева функция дифференцируется ориентировано на уменьшение; ОН - булева функция )ференцирована ориентировано на увеличение,

Для работы устройства в режиме 2 на вход 13 подается сигнал 1, на вход 2 - последовательность управля-

Q

5

5

5

0

5

5 4

ющих сигналов О, Ь, О, h,,..,0, h. Причем нули с входа 2 подаются на параллельные входы сдвигового регистра 6, а значения h (,n) - на входы регистра 7. Величина h. равна нулю, если переменная Х( не инвертирована, и h j I, если соответствующая переменная инвертирована. В соответствии с информацией, хранимой в регистре 7, устройство выполняет необходимые преобразования исходной булевой функции.

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

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

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

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

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

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

Со входа 1 на информационные входы 15 коммутатора 3 подаются сигналы fp, f ,, fj, 3, определяющие данную булеву функцию.

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

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

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

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

С управляющего входа 13 на первый адресный вход АО тультиплексЬров 4 , tt j« 4 второго KONfMyraropa 4 подается сигнал . С выводов.23 и 23-2 на адресные входы AI и А2 тех же мультиплексоров поступают сигналы О и h, которые приходят с выходов регистров 6 и 7 соответственно, В результате на выходах первого и второго мультиплексоров коммутатора 4 присутствуют значения (fohvVf h,) и (,vfjh,), тождественные (,® ®f,h,) и (fjlij Jf h,) соответственно, В алгебре Жегалкина имеет место тождество X Vy x6 y+-xy, которое в данном случае записывается следующим образом:

f,h,Vf,h,-f,h,ef,h,®feh,f,h, ,

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

f,h,vf,h,-fji,@f,h,.

На выходах двух других мультиплексоров 4.J и 4 присутствует информация с пятых и шестых, в зависимости от значения h , информационных входов, а именно () и (,,). Сигналы с выходов 28,, 2В j, 28 3 и

10

ды 28,, 28J, 28, 28 коммутатора 4, с которых проходит на информационные входы блока 9 памяти. По окончании синхроимпульса эта информация записывается в D-триггеры и на выходах устройства присутствуют следующие величины:

(,® f,h,), (fjh,©f,h,), („©5,), (f fi).

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

15 3, С выхода счетчика 10 на управляющие входы мультиплексоров 3,,,,3 , коммутатора по входу 14 передается кодовая комбинация (01), Следовательно, подключается вторая группа инфор20 мационных входов 16 первого коммутатора 3 и на его выходы 17, 17, I7j, и 17, проходят величины (,® f,h, ), (f,h,6)f h,), (f,6)f,), (f,efj).3TH сигнады поступают на группу входов

25 24 второго коммутатора 4 и на входы группы 5 элементов НЕРАВНОЗНАЧНОСТЬ, получают значения (fph,®fih,)0 ®(f,h,6)f3h,) и (f,©f,)©(f ,(5f ,), которые подаются на информационные

30 входы 25, и 25J второго коммутатора 4,

На адресных входах АО, А1, А2 муль типлексоров 4,...,4 коммутатора 4 во втором такте присутствуют величивеличины

информация записывается в D-триггеры ны 1, О, hj с управляющего входа 13 и и на выходах устройства присутствуют выходов сдвиговых регистров 6 и 7

соответственно,

В результате, на выходы 28,,,,,, 284 коммутатора 4 троходят сигналы 40 (fob, ® f ,h,)h(f2h,©f3h,)ht и Во втором такте информация с выхо- (g, f )hj®(f,е f j)ht с выходов муль- дов устройства поступает на группу типлексоров 4, и 4, и сигналы (foh , входов 16 коммутатора 3. С выводов 23 (5 f ,h, ) @ (f h , © f jh J и ( f ,) ® и 23, на адресные входы A1 и А2 тех же ©(f,,©f с мультиплексоров 4з и 44

45 соответственно.

Эти значения поступают на информа(foh,©f,h,), (f,h,fjh,), (fo©f,), ().

мультиплексоров поступают сигналы О и h, которые приходят с выходов регистров 6 и 7 соответственно, В результате на выходах мультиплексоров 4, и 4 коммутатора 4 присутствуют значения (fj,h, V f h,) и (f ) , тождественные (,), ( ©fjh,) соответственно.

Ha выходах двух других мультиплексоров присутствует информация с 5-х или 6-х (в зависимости от значения h) информационных входов, а именно (,) и (f f,). Информация с выходов мультиплекгоров 4,, 4, 4, 44 поступает на соответствующие выхо50

55

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

Таким образом, на выходах устройства, функционирующего в режиме 2, по окончании тактов присутствуют сигналы:

(, -п,® f ,h,)hj®(f ,h,S)f зЬ,)Ь,; (fc©f,)h2©(fi® f,) (foh, f,h,)© (fnh,g зЬ,); (f,,) ©(f,©f,).

ды 28,, 28J, 28, 28 коммутатора 4, с которых проходит на информационные входы блока 9 памяти. По окончании синхроимпульса эта информация записывается в D-триггеры и на выходах устройства присутствуют следующие величины:

(,® f,h,), (fjh,©f,h,), („©5,), (f fi).

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

3, С выхода счетчика 10 на управляющие входы мультиплексоров 3,,,,3 , коммутатора по входу 14 передается кодовая комбинация (01), Следовательно, подключается вторая группа информационных входов 16 первого коммутатора 3 и на его выходы 17, 17, I7j, и 17, проходят величины (,® f,h, ), (f,h,6)f h,), (f,6)f,), (f,efj).3TH сигнады поступают на группу входов

24 второго коммутатора 4 и на входы группы 5 элементов НЕРАВНОЗНАЧНОСТЬ, получают значения (fph,®fih,)0 ®(f,h,6)f3h,) и (f,©f,)©(f ,(5f ,), которые подаются на информационные

входы 25, и 25J второго коммутатора 4,

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

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

Таким образом, на выходах устройства, функционирующего в режиме 2, по окончании тактов присутствуют сигналы:

(, -п,® f ,h,)hj®(f ,h,S)f зЬ,)Ь,; (fc©f,)h2©(fi® f,) (foh, f,h,)© (fnh,g зЬ,); (f,,) ©(f,©f,).

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

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

Формула изобретения

0

0

5 Q

с первым и пятым разрядами информацил+к

онного входа (,-г-)-го мультиплексора,

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

Фиг

, 1Г.

Риг.Ч

21, 2i,

11

Ш щтяV wV 9V w

V-Г

юЛ

Составитель А.Зорин Редактор Т.Лазоренко Техред Л.Сердюкова

Заказ 6605/53

Тираж 668

ВПИШИ Государственного комитета по изобрг-уениям и открытиям при ГКНТ СССР 113035, Москва, , Рау.иская наб., д. 4/5

Фиг. 5

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

Подписное