Устройство для вычисления булевых функций

 

Изобретение относится к вычислительной технике и предназначено для вычисления булевых функций, представленных в виде алгебраических уравнений . Цель изобретения - расширение области применения устройства за счет вычисления скобочных форм булевых функций, представленных в виде алгебраических уравнений. Устройство содержит сумматор по модулю два, триггер , группу коммутаторов, реверсивный счетчик. На входы команды устройства подаются сигналы Значение аргумента, указанное в уравнении, Дизъюнкция, Открывающая скоба и Закрывающая скоба. На информационный вход устройства подаются действительные значения аргументов уравнения. Вычисление булевого уравнения ведется в порядке естественной записи аргументов. После вычисления последнего аргумента полученное значение функции считывается с выхода тригге ра. 4 ил. , 1 табл. W tc iU N5 50, CN

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

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

РЕСПУБЛИК

„„SU„„) 242928 A 1

yg 4 < С 06 F 7/00

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

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

Ф

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3787418/24-24 (22) 04.09.84 (46) 07.07.86. Бюл. Ф 25 (71) Московский автомобильный завод им, И. А, Лихачева (72) В . И, Хохлов и А, И. Андерсон (53) 681 .3(088.8) (56) Авторское свидетельство СССР

У 610104, кл, С 06 F 7/00, 1975.

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

У 1049898, кл. G 06 F 7/00, 1982.

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

Ф 1160391, кл, G 06 F 7/00, )983. (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ БУЛЕSS1X фУН ЦИЙ (57) Изобретение относится к-вычислительной технике и предназначено для вычисления булевых функций, представленных в виде алгебраических уравнений. Цель изобретения — расширение области применения устройства за счет вычисления скобочньж форм булевых функций, представленных в виде алгебраических уравнений. Устройство содержит сумматор по модулю два, триггер, группу коммутаторов, реверсивный счетчик. На входы команды устройства подаются сигналы "Значение аргумента, указанное в уравнении, Дизъюнкция", "Открывающая скоба" и

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

ИЭОс)РОТЕ((3)Е 0 ()(О("H 1 с.я К ВЬ(с(ИСЛИ— тель)той техник(- ., а бг>лее кснкретнс к программному упра)зленик) технологичесI(HM 060py)TOBB)!Hera.

Цель r!(=06ðeòeíил -- ряс?Яирение обJIB C TH П РИМ«>)ТОНИЯ ЗЯ СЧЕ Г БЬ(ЧИСЛЕНИЯ

ct(o6oчных форм булевых (руцкций, представлен:(ых B виде алгебраич еских уравнений).

На фиг. т привецена структурная схема устройства,цлл т)ычис>пения булевых функций; на фиг. 2 — пример реализации устройства ня уровне стан-. дартных функциональных элементов; на фиг. 3 — времеьтная диаграмма ра-боты устройства: ня фигс 4 — япго1) и ть! p B o o т ы у с т р 0 и (т Г а,, Устройство (фиг,, 1 и 2) r.ogepz) сумматор 1 ))o моду Tto два, триггер 2,.: группу 3 коммутаторов, ревеpcHBI(?)A счетчик 4. -руппу входов 5 команды, информационный вход 8 и вь?ход 7.

Первый коммутатор группы 3 (фиг. 2) может быть выг>олнен в виде элемента

ЗАПРЕТ 8, второй коммутатор может быть выполнен на элементе НЕ-ИЛИ 9 и элементе ("--4) H--2ИПИ 10, установка устсройства в исходное состояние и синхронизация осуп(ествляются по вхОду 1 тстсlн013ки в и(ходное состОя" ние и синхровходу 12.

На фи". "-. приведена временная диаграмма рабогы ус .ройства,, где показано взаимное расположение сигналов на информациоьтном входе 6, входе 5 команды и синхровходе 12 устройстга, ВЬГХОДЯХ СУ)>1«!а 7 О Р> а . 1)0 МОДУЛ1(),Ц)За > триггера 2> т:ервого и второго коммуTaTopoB =pyttHT) 3 и Bürõîäà реверсивного счетчика

Ст(етчик 4 и то)те.-ет) 2 т фиг 3 2 моу у> НP l>ет(?1(!)чятьст > например т ?70 !Te" реднему фри))ту с)?гь)а:T(1 поступа)()(кего на синхровхо(2, 12 у< Т1:ойст)за, С при:«c!

ДОМ СИНХ ((ОН r(3I>p Jl(2) С ИМПУЛЬСЯ Ирв

ОДИНсаКОВЫХ,> РОВНЯХ .(:.ОГИТIЕСКИХ Ьlгна

ЛОВ IIR ВХОдс)) 06В > т: >ОГО И IlpB!! 10ГО

П)РИРЯ()?ЕНИЯ С.-(етт(;")-Т.:, ЦЕ ИЗМЕНИТ СВОЕ-го состот)т)ия. С)((>;"-(ронизирутций импульс поцяе-ся,(а : инхровход 12 уст-ройства., когда сиг"алы на входах

ЭЛРМРЬIТОВ >JC ipoHC В Я Т?р))и>(2)а(1)! >>СТЯ новивтт))те ся знач- нил ., Сигнал устянс !2(и устройства в ис)тОДНОЕ Co((ОЯ)2)ТР ПЕР ПОт)л()2(Т)Т СЧР Г-чик 4 в состояние "0 а триггер 2 в состояние "1, 110",-(ется асинхронно

HB вход 1 I ) Г тановк)1 в исxo JIHoe со"" стол)гие у(тро)- :(тн; ) еред каждым цикJ)o)f вычисления очередной 6ут)евой фУ-FT I(2 f) (H

11Я фиг. - пре,(ставлен. алгоритм ра6О ГЫ т>СТР()ЙС":За, )101 ИЧЕСКИЕ 6ЛОКИ

КОТО>201 0 1)Ы)10.))ТЯ!1)1 C:, )e(i>»9>T)(H!З ДСЙСТ

13)лт ". блэк —. у стано?зить состояние r r

r -TeтЧИКа -, Оя ВНОе 0 И СОСтОяНИЕ

«)риггера ". ря зное "1"," блок " — npo::epHть состоя)Не счетчика 4 на раген—

-.тво 0 ",. 6лсх 3 — проверить состоя>> „ пис триггера 2 на равенство 0 (>лок 4 — проверить, cOB)IBDBe T JIH .=-AC ГВИТЕЛс>ЦОЕ Зиат)Р>IHP ЯРГУМЕН; =" СО

ЯНаЧЕНИЕМ > УК Зат?НЫМ В УРЯВ))ЕЬ!ИИ;

6!7oI(5 — )гроперить, имеетсB ли знак

2 И »)т) lкцlти l (бЛОТ«< у Стсэцоь1> f B

ll, «с стояние триггe))5 2 peBI(oe 0 блок — Уст,--:.(IOBHTь состо.=.ние триг—

)7 : †;=.ря 2 равное 1"; блок 8 — -.>рове")ить имеетс-; ли эакрыва)()щяя скоба

>), "т)лок з — проверить, имеется ли с)ткрь)?)а(о(пал с)(эбя (11; блок 10

),велит!ить содержимое счетчика 4 на бл)зк — умень)лить содержимое

«. 1е (чика - . Нс(1

У(. . рОйство испОльз 5тет цля вычисле -Тя 6-;rJI>reBT>1)". ф-ТНКцнй аЛГЕбраИЧЕСКИХ

) )r1B11E1НИй Зцс(1(,цнэуЬЮНКIIИИ + ОТ ! pb1B121)Щие (и э а к рь)в Яюl)тиР ) с к О б11 I ки.

»= 1цят?ет>ие аргумента,,указанное в !

Ir!! )r1)B Внении Оа?3 10 > сли э тОт аргу

frrr>T(÷- вход? 2 ) 1> -,>равнение без знака т.-quet)(HH В ))Р )7> HВЦО.-> СЛ>тттаЕ ОН; — явно 0

Т(1ки)1 (>бра(эом, ре.=-удьтят опера))Ни

".1 1С1<ЛНЗЧМОШЕЕ 11.8И" равный "0 нац

> т

С)(ГНЯ))ЯМ(? >((се))С. TBHTCJ!BBO(" „"", Я ЕН) (>

"->рГУМРНТЯ> И:1>таЧЕ::-;Т Е а!» уыента т>=.(а()аl(НОЕ 3, 1)ав))Е)(ИИ СВ)) 1(= ТЕЛЬС ВУЕТ

ТС)). «Что2 Д,:.Н)ТЫй ЯРГУМЕ(tт ITr тИНЕН, . 1)О(ИВ)>:.C!I."((:Л (т>-(ЯЕ Or> Ложа ц, 1) а(.с >о.; рт)7(!7oä.eð урал>ь)ения.

Х) ° (;<2 ":-:;3- -у,4) и (Х5х7гэ (Х7 (-",т8) ) х

;, Я-:->",10-:--=" " (1) ,:.IITFf .27)060гсс 6 улРНОГО У )Явненил вы .- -)CJ,er(ИЯ >ЗŠ—... т В ПОря),(e eст=СтВЕ-)Íoé з,)писи ар)у)- Рнтоь., слева напэаво, .(> .>>1>;"B?т; — Н).-с. (1 ) И((ПЕКСЬ) ттри at)—

T 1!(åü .> Ях Определяют пооядок зычисле— пия.

В На (аЛЕ ВЫЧИСЛЕНИсл УСТЯНЯВЛИВак т значение Ь?,нкь)ии рагное "I, Рес с

1)2 а ю т у р я В ц е H и =.,;. и ь (- и с..л я я и О и о р я д х $ яргумен(ы,.

Б 1:ðîöåññе вьг>испания у()а)знения

C .,> 7цЕ(тВ)>7()т ДВЯ уе?трВ>>(>ц()Т(=рЕ.;<ода:

1242928

50

55 когда вычисленный аргумент истинен и после него стоит знак дизъюнкции

"+, когда вычисленный аргумент ложен и после него нет знака цизъюнкции (т.е, стоит знак конъюнкции).

В примере (уравнение (!) ) знак дизъюнкции стоит после аргументов

Х2, XÇ, Х5, Х7 и Х9.

В первом случае процедура условного перехода такова: функции присваи.вается значение "единицы", накладывается запрет на вычисление остальных слагаемых дизъюнкции до отыскания последнего аргумента, входящего в данную дизъюнкцию, после чего вычисление продолжается.

Очевидно, если уравнение заканчивается последним членом этой дизъюнкции, то результатом .решения этого уравнения будет "1".

Во втором случае функции присваивается значение "ноль", накладывается запрет на вычисление остальных сомножителей данной конъюнкции до отыскания последнего аргумента, обнаруживается диэъюнктивный член к этой части функции, в которую входит только что вычисленная конъюнкция, функции присваивается значение "1" и вычисление продолжается. Очевидно„ что если уравнение заканчивается последним числом данной конъюнкции, то результатом решения этого уравнения будет "О". Для отыскания послед-. него аргумента дизъюнкции при первом условном переходе рассмотрим дизъюнкцию вида

Хl+Х2+ХЗ...Xn=Y (2)

Если эта дизъюнкция входит в состав более сложного аргумента, то она должна быть заключена в скобки (Xl+X2+X3. ° .+Х„)хХ„+1=7 (3) или

Х„+1(Х1+Х2+ХЗ+...+Х„)+Х„+2=7 (4) где Х„+1 и Х„+2 — любые сколь угодно сложные аргументы.

Из уравнений (3) и (4) видно, что окончание дизъюнкции определяется наличием закрывающей скобки. Однако любой член дизъюнкции может быть в свою очередь сложным аргументом и .содержать скобки. Например Х2=В1(В2+

+ВЗ), тогда уравнение (3) принимает вид (Хl+В!(В2+ВЗ)+ХЗ+...Х )X„+1=Y (5)

При этом по ходу вычисления, если, например, действительное значение

Х! равно "1" и совпадает со значением, указанным в уравнении, то результат операции "ИСКЛЮЧАЮ!ЦЕЕ ИЛИ" над сигналами "Действительное значение аргумента" и "Значение аргумента, указанное в уравнении" равен "О".

Зто означает, что аргумент Хl, являющийся членом дезъюнкции, истинен, так как после Xl стоит знак дизъюнкции "+", то и вся дизъюнкция истинна.

Для продолжения вычислений необходимо найти последний член этой дизъюнкции.

Однако закрывающая скобка после аргумента ВЗ не характеризует окончание данной дизъюнкции. Такие скобки, принадлежащие сложным аргументам, характеризуются тем, что каждой закрывающей скобке соответствует открывающая скобка и лишь последняя закрывающая скобка, указывающая на конец дизъюнкции, оказывается нескомпенсированной открывающей скобкой. Поэтому правило для отыскания последнего члена дизъюнкции можно трактовать так: по ходу вычисления подсчитывается количество открывающих и закрывающих скобок и тот наиболее близкий . шаг вычислений, в котором число saкрывающих скобок хотя бы на одну больше числа открывающих скобок, указывает на конец дизъюнкции.

Для отыскания последнего аргумента конъюнкции при втором условном переходе рассмотрим конъюнкцию

ХlхХ2хХЗ...Х =Y (6)

Если эта конъюнкция входит в сос35 тав более сложного аргумента, то после нее должен стоять знак дизъюнкции, с помощью которого . к ней присоединяется в общем случае любой, сколь угодно сложный аргумент ХlхХlх

40 хХЗ...Х„+Х„+!=У (7) .

Из уравнения (7) видно, что окончание конъюнкции определяется наличи. ем знака дизъюнкции "+ . Однако как . и при первом условном переходе, каждьrA из аргументов может быть сколь угодно сложным, содержащим в свою очередь знак дизъюнкции и скобки.

Например Х2х(В!+В2)хХЗ...Х„+Х„+

+I=Y (8) .

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

1242928

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

Устройство работает следующим t5 образом (фиг. 1 — 4).

В начале вычислений счетчик 4 устанавливается в состояние "ноль (значение его выходного сигнала равно "единице), а триггер 2 — в состо- 20 яние единица . В процессе вычислений последовательно по шагам для каждого аргумента булевого уравнения сумматор 1 по модулю два проверяет совпадение сигналов "Действительное зна — 25 чение аргумента (на информационном входе) и "Значение аргумента, указанное в уравнении". Если для какоголибо аргумента его действительное состояние совпадает со значением, 30 указанным в уравнении, то на выходе сумматора 1 по модулю два появляется сигнал логический "ноль" ° Если к тому же имеется знак дизъюнкции + то выполняются условия для первого условного перехода и сигнал +" (через второй коммутатор группы 3) увеличивает на единицу значение содержимого счетчика 4.

Когда содержимое счетчика 4 отличается от исходного, то значение его выходного сигнала принимает состояние равное нулю, при этом нак,ладывается запрет на вычисление последующих аргументов и изменение состояния триггера 2.

Начинается подсчет счетчиком 4 открывающих и закрывающих скобок.

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

"Открывающая скоба". Когда количество закрывающих скобок хотя бы на одну 55 больше числа открывающих скобок, счетчик 4 устанавливается в исходное состояние "0", a его выходной сигнал принимает значение 1, и вычисления продолжаются.

Если для какого †ли аргумента его действительное состояние не совпадает со значением, указанным в уравнении, то на выхоце сумматора 1 по модулю два появляется сигнал логическая

"1

Если отсутствует знак дизъюнкции +, то выполняются условия для второго условного перехода. Триггер 2 сбрасывается в состояние "0", а на его выходе 7 устанавливается значение выходного сигнала (функции) равное

"0". Счетчик 4 подготовлен к отсчету открывающих и закрывающих скобок, причем закрывающие скобки подсчитываются лишь тогда, когда имеется хотя бы одна открывающая скобка, Если на ходу вычисления все открывающие скобки скомпенсированы закрывающими (состояние счетчика 4 равно "0") и имеется знак дизъюнкции "+", то триггер

2 устанавливается в исходное состояние, равное "1", и вычисления продолжаются.

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

"1" снимается с выхода 7 триггера 2.

Это значение является результатом решения уравнения.

Рассмотрим в качестве примера работу устройства. при вычислении урав нения (1). Для определенности предйоложим, например, что аргументы Х1, ХЗ, Х7, Х10 находятся в состоянии логической единицы, а остальные аргументы в состоянии логического

"нуля

Составим таблицу, характеризующую состояние устройства в процессе вычисления.

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

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

Нет

Х2

Есть

0 !

ХЗ

Х4

Есть

Нет

Нет

Х5

+1

0

Хб

Х7

Нет

Есть

2

+1

Х8

Х9

Нет

Есть

0 .

Х10

Нет

М вЂ” номер условного перехода.

Вычисленное значение функции в данном случае равно "единице". входом устройства, входы сумматора по модулю два соединены с информационным входом устройства и входом команды "Значение аргумента, указанное в уравнении" устройства, о т— л и ч а ю щ е е с я . тем, что„ с целью расширения области применения устройства за счет вычисления скобочных форм булевых функций, представленных в виде алгебраических уравнений, первый коммутатор состоит из элемента ЗАПРЕТ, второй коммутатор группы состоит из элемента

НЕ-ИЛИ и элемента (2-4)И-2ИЛИ, причем выход признака нуля реверсивного счетчика соединен с инверсным входом элемента ЗАПРЕТ, первым входом элемента НЕ-ИЛИ, первым прямым входом первой группы входов элемента (2-4)И-2ИЛИ, первым входом первой .группы входов установки единицы и первым прямым входом группы входов установки нуля триггера, второй вход первой группы входов установки единицы и инверсный вход группы входов установки нуля которого соединен с входом команды "Дйзьюнкция" устройства и вторым прямым входом первой группь входов элемента (2-4)И-2ИЛИ, третий прямой вход первой группы входов которого соединен с выходом триггера, .выходом устройства и вторым входом элемента НЕ-ИЛИ, выход которого соединен с первым входом второй группы

1р входов элемента (2-4)И-2ИЛИ, второй вход второй группы входов которого соединен с входом команды Открывающая скоба" устройства, вход команды

"Закрывающая скоба" которого соеди15 нен с прямым входом элемента ЗАПРЕТ, инверсный вход первой группы входов элемента (2-4)И-2ИЛИ соединен с, выходом сумматора по модулю два и вторым прямым входом группы входов уста2р новки нуля триггера, синхровход и вход начальной установки которого соединены соответственно с синхровходом и входом установки в исходное состояние устройства, вход сброса

25 реверсивного счетчика соединен с входом установки в исходное состояние устройства.

)242928

« Яс ры

c cosh

О пр сто& о

Дизь ци ,7иач аргую

fl7+gh е иое Р

ИРИИИ

Ии Рпри гиеной К

Уюча о

/ис пРиюе состоявшие

1242928

Иифпрма ци пнмый йхпдб асхад Х кпмаидп/

Гинхрпйхад

Юыхпа счептчи4аО

Редактор Е. Папп

Заказ 3705/47 Тираж 671

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

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

Подписное

Производственно-полиграфическое предприятие, г.. Ужгород, ул, Проектная, 4 йыхпй сумматора 1 па модула

dA дыхпо mpuzzepa Р

Выход кпммушатпроб груты Я

„-/ "

Выхоо кпмму пвгпоро6 групаы3

+l f и

Составитель А. Федоров

Техред Н.Бонкало Корректор М. Пожо