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

 

1. УСТРОЙСТВО ДЛЯ РЕАЛИЗАЦИИ БУЯЕИЛХ ФУНКЦИЙ, содержащее блок управления, элементы ИЛИ, элемент И, входы которого соединены с выходами элементов ИЛИ, отличающееся тем, что, с целью повышения быстродействия, в него введены блок памяти адресов, блок ассоциативной памяти, первый регистр, второй регистр, третий регистр, четыре группы схем сравнения, счетчик и дешифратор, причем входы первого регистра соединены с входами устройства , информационные входы второго регистра соединены с выходами блока ассоциативной памяти, первые входы схем сравнения первой группы подключены к первой группе выходов блока памяти адресов, вторые входы - к прямым выходам первого регистра, а выходы - к первым входам элементов ИЛИ первой группы, первые входы схем сравнения второй группы подключены к второй группе выходов блока памяти адресов, вторые входы к прякым выходам второго регистра, а выходы - к первым входам элементов ИЛИ второй группы, первые входы схем сравнения третьей группы подключены к третьей группе выходов бло ка памяти адресов, вторые входы - к инверсным выходам первого регистра , а выходы - к вторым входам элементов ИЛИ первой группы. Первые входы схем сравнения четвертой группы подключены к четвертой группе выходов блока памяти адресов, вторые входы - к инверсным выходам второго регистра, а выходы - к вторым входам элементов ИЛИ второй группы, входы элемента И соединены с выходами элементов ИЛИ первой и второй групп, первые информационные входы третьего регистра подключены к выходу элемента И, вторые информационные входы - к выходам дешифратора, а выходы - к информационным входам блока ассоциативной памяти, выходы счетчика соединены с адресными входами блока памяти адресов и входами дешифратора, первый вход блока уп (Л равления подключен к выходу элемента и, второй вход.- к входу пуска устройства, третий вход - к установочному входу устройства, первый выход - к управляющим входам первого и третьего регистров и к установочному входу счетчика, второй выход к управляющему входу блока памяти адресов, третий выход - к счетному входу счетчика, четвертый выход к управлякнцим входам второго регистсо ю ра и блока ассоциативной памяти, а с выходами устройства соединены пря4i мые выходы второго регистра, 2. Устройство по п. 1, отлисл чающееся тем, что блок ассоциативной памяти содержит регистры , элементы И и элементы ИЛИ, причем прямые выходы каждого регистра соединены с первыми входами соответствующих элементов И, выходы которых соединены с входами соответствующего элемента ИЛИ, выходы элементов ИЛИ являются вьЕсодами блока, информационные входы блока соединены с вторыми входами соответствующих элементов И, третьи входы элементов И подключены к управляющему входу блока.

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

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

РЕСПУБЛИК

„„SU„„1032451 А

) II G 06 F 7/00

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

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

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3418462/18-24 (22) 06.04.82 (46) 30.07.83. Бюл. Р 28 (72) Г.В.Куклин, В.В.Бодунов иГ.М.Ревяко (71) Могилевский машиностроительный институт (53) 681.325 (088.8) (56) 1. Авторское свидетельство СССР

9 383043, . G 06 F 15/20, 1974.

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

Р 276516, кл. G 06 F 7/00, 1970 (прототип). (54)(57) 1. УСТРОЙСТВО ДЛЯ РЕАЛИЗАЦИИ БУЛЕВЫХ ФУНКЦИЙ, содержащее блок управления, элементы ИЛИ, элемент И, входы которого соединены с выходами элементов ИЛИ, о т л ич а ю щ е е с я тем, что, с целью повышения быстродействия, в него введены блок памяти адресов, блок ассоциативной памяти, первый регистр, второй регистр, третий регистр, четыре группы схем сравнения, счетчик и дешифратор, причем входы первого регистра соединены с входами устройства, информационные входы второго регистра соединены с выходами блока ассоциативной памяти, первые входы схем сравнения первой группы подключены к первой группе выходов блока памяти адресов, вторые входы — к прямым выходам первого регистра, а выходы — к первым входам элементов ИЛИ первой группы, первые входы схем сравнения второй группы подключены к второй группе выходов блока памяти адресов, вторые входык прямым выходам второго регистра, а выходы — к первым входам элементов ИЛИ второй группы, первые входы схем сравнения третьей группы подключены к третьей группе выходов бло ка памяти адресов, вторые входы - к инверсным выходам первого регистра, а выходы — к вторым входам элементов ИЛИ первой группы, первые входы схем сравнения четвертой группы подключены к четвертой группе выходов блока памяти адресов, вторые входы - к инверсным выходам второго регистра, а выходы — к вторым входам элементов ИЛИ второй группы, входы элемента И соединены с выходами элементов HJIH первой и второй групп, первые информационные входы третьего регистра подключены к выходу элемента И, вторые информационные входы — к выходам дешифратора, а выходы — к информационным входам блока ассоциативной памяти, выходы счетчика соединены с адресными входами блока памяти адресов и входами I дешифратора, первый вход блока управления подключен к выходу элемента И, второй вход .- к входу пуска устройства, третий вход - к уста- С новочному входу устройства, первый выход - к управляющим входам первого и третьего регистров и к установочному входу счетчика, второй выход к управляющему входу блока памяти адресов, третий выход - к счетному входу счетчика, четвертый выход - (, ) к управляющим входам второго регистра и блока ассоциативной памяти, а с выходами устройства соединены пря- Я мые выходы второго регистра. „ф

2. Устройство по п. 1, о т л и ч а ю щ е е с я тем, что блок ас- Ql социативной памяти содержит регистры, элементы И и элементы ИЛИ, причем прямые выходы каждого регистра соединены с первыми входами соответствующих элементов И, выходы которых,Ф соединены с входами соответствующего элемента ИЛИ, выходы элементов

ИЛИ являются выходами блока, информационные входы блока соединены с вторыми входами соответствующих элементов И, третьи входы элементов

И подключены к управляющему входу блока.

1032451

3. Устройство по и. 1, о т л и ч а ю щ е е с я тем, что блок управления содержит генератор сннхроим3 пульсов, счетчик, первый и второй триггеры,дешифратор, пять элементов И и шесть элементов ИЛИ, причем входы йервого элемента И соединены с инверсными выходами счетчика, вход первого элеМента ИЛИ соединен с первым входом блока управления, первый вход второго элемента И подключен к второму входу блока, второй вход — к первому выходу .дешифратора, а выход — к

Первому выходу блока, первый вхсд второго элемента ИЛИ подключен к второму выходу дешифратора, второй вход — к четвертому выходу дешифратора, а выход — к второму выходу блока, вход третьего элемента ИЛИ соединен с выходом первого элемента И, первый вход третьего элемента И подключен к третьему выходу дешифратора, второй вход — к ин-версному выходу первого элемента

ИЛИ, третий вход — к инверсному выходу третьего элемента ИЛИ, а выход — к третьему выходу блока, первый вход четвертого элемента И подключен к третьему выходу дешифратора, второй вход — к инверсному выходу первого элемента ИЛИ, третий вход — к выходу первого элемента И, первый вход пятого элемента И под1

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

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

Недостатком устройства является низкое быстродействие, ввиду того, 15

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

Наиболее близким к предлагаемому

Но технической сущности является логический автомат, содержащий блок ввода переменных, блок памяти, блок р5 ключен к третьему выходу дешифратора, второй вход — к первому входу блока, первый вход четвертого элемента ИЛИ подключен к выходу четвертого элемента И, второй вход — к выходу пятого элемента И, а выход к четвертому выходу блока, первый вход пятого элемента ИЛИ подключен к второму выходу дешифратора, второй вход — к выходу четвертого элемента ИЛИ, а выход — к счетному входу первого триггера, первый вход шестого элемента ИЛИ подключен к выходу второго элемента И, второй вход— к выходу второго элемента ИЛИ, третий вход — к выходу третьего элемента И, а выход — к счетному входу второго триггера, первый прямой вход дешифратора подключен к прямому выходу первого триггера, первый инверсный вход — к инверсному выходу первого триггера, второй прямой вход — к прямому выходу второго триггера, второй инверсный вход— к инверсному выходу второго триггера, информационные входы счетчика подключены к третьим входам блока, вычитающий вход — к выходу второго элемента ИЛИ, управляющий вход — к выходу второго элемента И, выход генератора синхроимпульсов соединен .с синхровходами первого и второго триггеров и дешифратора. задержек, программоноситель с вентилями, элемент И, элементы ИЛИ. и НЕ блок вывода j2).

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

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

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

1032451 с выходами блока ассоциативной памяти, первые входы схем сравнения первой группы подключены к первой группе выходов блока памяти адресов, вторые входы — к прямым выходам первого регистра, а выходы — к первым входам элементов ИЛИ первой группы, первые входы схем сравнения второй группы подключены к второй группе выходов блока памяти адресов, вторые входы — к прямым выхо- 10 дам второго регистра, а выходы — к первым входам элементов ИЛИ второй группы, первые входы схем сравнения третьей группы подключены O третьей группе выходов блока памяти адресов, 35 вторые входы к инверсным выходам первого регистра, а выходы— к вторым входам элементов ИЛИ первой группы, первые входы схем сравнения четвертой группы подключены к четвер- р той группе выходов блока памяти адресов, вторые входы — к инверсным выходам второго регистра, а выходы к вторым входам элементов ИЛИ второй группы, входы элемента И соединены с выходами элементов ИЛИ первой и второй групп, первые информационные входы третьего регистра подключены к выходу элемента И, вторые информационные входы — к выходам дешифратора, а выходы — к информационным входам блока ассоциативной памяти, выходы счетчика соединены с адресными входами блока памяти адресов и входами дешифратора, первый вход блока управления подключен к выходу элемента И, второй вход " к входу пуска устройства, третий вход — к установочному входу устройства, первый выход - к управляющим входам первого и третьего регистров и к устано-. 49 вочному входу счетчика, второй выход к управляющему входу блока памяти адресов, третий выход - к счетному входу счетчика, четвертый выход— к управляющим входам второго регистра и блока ассоциативной памяти, а .с выходами устройства соединены прямые выходы второго регистра.

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

И подключены к управляющему входу блока. 60

Блок управления содержит генератор синхроимпульсов, счетчик, первый и второй триггеры, дешифратор, пять элементов И и шесть элементов ИЛИ, причем вхоДы первого элемента И сое- 65 динены с инверсными выходами счетчика, вход первого элемента ИЛИ соединен с первым входом блока управления, первый вход второго элемента

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

ИЛИ, управляющий вход к выходу второго элемента И, выход генератора синхроимпульсов соединены с синхровходами первого и второго триггеров и дешифратора.

На фиг. 1 изображена структурная схема устройства для реализации булевых функций, на фиг. 2 - схема блока ассоциативной памяти, на фиг. 3 схема блока управления.

Устройство (фиг. 1) содержит блок 1 управления, блок 2 памяти адресов, блок 3 ассоциативной памяти, 1032451 первый регистр 4, второй регистр 5, третий регистр 6, четыре группы схем сравнения 71 ... 7,„, Bg ...8, 9 ... 9д, 101... 101... элементы ИЛИ

11„ ...1111,щ, элемент И 12, счетчик

13, дешифратор 14.

В блок 3 ассоциативной памяти фиг. 2) входят регистры 15 ...15,, элементы И 16 ...169, элементы ИЛИ

17 ...17, причем первый выход блока 1 управления подключен к управляю- tO щим входам первого и третьего регистров и к установочному входу счетчика второй выход — к управляющему входу блока памяти адресов, третий выходк счетному входу счетчика, четвер- )5 тый выход — к управляющим входам второго регистра и блока ассоциативной памяти, с выходами устройства соедийены прямые выходы второго регистра, и тем, что блок ассоциативной памяти содержит регистры, элементы И и элементы ИЛИ, причем прямые выходы каждого регистра соединены с первими входами соответствующих эле ментов И, выходы которых соединены с входами соответствующего элемента ИЛИ, выходы элементов ИЛИ являются выходами блока ассоциативной памяти, информационные входы блока ассоциативной памяти соединены с вто рыми входами соответствующих элементов И, третьи входы элементов И подключены к управляющему входу блока ассоциативной памяти; а также тем, что блок управления содержит генератор синхроимпульсов, счетчик, пер- 35 вый и второй триггеры, дешифратор, пять элементов И и шесть элементов ИЛИ, причем входы первого элемента И соединены с инверсными выходами счетчика, вход первого эле- 40 мента ИЛИ соединен с первым входом блока управления, первый вход второго элемента И подключен к второму входу блока управления, второй вход к первому выходу дешифратора, а выход — к первому выходу блока управления, первый вход второго элемента ИЛИ подключен к второму выходу дешифратора, второй вход — н: четвертому выходу дешифратора а 5О выход - к второму выходу блон:а управления, вход третьего элемента ИЛИ соединен с выходом первого элемента И, первый вход третьего элемента

И подключен к третьему выходу дешифратора, *торой вход — к инверсному выходу первого элемента ИЛИ, третий вход - к инверсному выходу третьего элемента ИЛИ, а выход — к третьему выходу блока управления, первый вход четвертого элемента И подключен к третьему выходу дешифратора, второй вход - к инверсному выходу первого элемента ИЛИ, третий вход — к .:.выхо,ду первого элемента И, первый вход пятого элемента, первый информацион- 65 ный вход блока 3 ассоциативной памяти соединен с вторыми входами элементов И 16, 16 -,1 и 16 1=, второй информационный вход блока ассоциативной памяти 3 соединен с вторыми входами элементов И 16, 161

16 „, и т.д., 1" -й вход блока 3 ассоцйативной памяти соединен со вторыми входами элементов И 16, 16.1»-,„, 16(e,= и, -, где ю — число уравнений, 1" — число различных конъюнкций). .Первые входы элементов И

164, ...16 аналогичным образом сое- :. -.",. динены с соответствующими выходами регистров 15,...15р„ третьи входы элементов И 16,...1бз соединены с управляющим входом блока 3 ассоциативной памяти. Выходы элементов И 16,...161- соединены с входами элемента ИЛИ 17, выходы элементов И 16Г+.1, 1621-, выходы элементов И 16 +>,...16 соединены с входами элемента ИЛИ 17щ„

В блок 1 управления (фиг. 3) входят генератор синхроимпульсов 18, счетчик 19, первый 20 и второй 21 триггеры, дешифратор 22, элементы И

23, 25, 27-29, элементы ИЛИ 24, 26, 30-33.

В блок 2 памяти адресов записана информация о всех различных элементарных конюнкциях,которые хотя бы один раз встречаются в записях ДНФ, реализуемых устройством булевых функций. Причем независимо от того, в записях какого числа функций встречается та или иная элементарная конъюнкция, информация о ней записывается в блок 2 памяти адресов только один раз. Каждая ячейка блока 2 памяти адресов соответствует одной элементарной конъюнкции, длина ячейки равна 2-(И + п) разрядов, где И вЂ” число входных переменных х, м — число выходных пере-менных g (функций), входящих в систему. Запись информации в первые разрядов <-и ячейки блока 2 памяти адресов производится согласно правилу:

О, если 7-я переменная х входит в данную -ю конъюнкцию с отрицанием;

1, если -я переменная х входит в 1.-ю коньюнкцию без отрицания, либо отсутствует.

Аналогично заполняются следующие

vn разрядов 4 -й ячейки:

О, если К-я переменная 1 входит в -ю конъюнкцию с отрипанием, 1, если К я переменная входит в 3 --ю конъюнкцию без отрицания, либо отсутствует.

1032451

Для заполнения второй части -й ячейки блока 2 памяти адресов используются следующие правила:

О, если -я переменная х входит в -ю конъюнкцию без отрицания, 1, если 1-я переменная х входит в -ю конъюнкцию с отрицанием, либо отсут- . ствует, О, если К,-я переменная JJ вхо-! дит в 4-ю конъюнкцию без отрицания, 1 если K, — ÿ переменная ) входит at.-w конъюнкцию с отрица1,R?2nt

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

Набор входных сигналов, характеризующих состояние объекта управления, параллельным кодом принимается в первый регистр 4 и сохраняется в нем до окончания цикла работы устройства. Одновременно с приемом набора входных сигналов происходит сброс третьего регистра б и установка начального кода в счетчике 13.

Затем считывается первое слово из блока 2 памяти адресов по адресу, хранящемуся в счетчике 13 (в начале каждого цикла в счетчике хранится код адреса первой по счету ячейки блока 2 памяти адресов. Считанное

55 нием, либо отсутствует, 15

=1,2,..., Vl>,К=1 2,..., w, В приведенных правилах g„.

011110110011 (номера разрядов считаются слева направо) .

В блоке 3 ассоциативной памяти в каждый из регистров 15. ...15, 3( число .которых равно числу реализуемых устройством булевых функций, записана информация о вхождении элементарных конъюнкций в соответствующую

ФУнкцию. При этом Разрядность каждо- 35 го из регистров 15 ...15„, равна количеству ячеек блока 2 памяти адресов.

Запись информации в К-й регистр 15к, блока 3 ассоциативной памяти производится согласно правилу:

О, если i-я конъюнкция не 40 входит в К-ю функцию, 1, если -я конъюнкция входит в К-ю функцию.

Здесь b — значение < --го разК>1 ряда регистра 15< блока 3 ассоци- 45 ативной памяти.

Первый регистр 4 служит для приема входных сигналов.

l слово поступает на соответствующие входы схем сравнения 7 ... 7, 8„... 8,, n

9 ...9,, 10 ...10„„, и на выходе элемента И 12 появляется сигнал, соответствующий значению первой элементарной конъюнкции при конкретных значениях входных переменных. Это значение записывается в соответствующий разряд третьего регистра 6 по первым информационным входам. Выбор этого разряда осуществляется с помощью дешифратора 14, указывающего по вторым информационным входам третьего регистра б, в какой именно разряд этого регистра производится запись.

Если значение первой элементарной конъюнкции равно нулю, то содержимое счетчика 13 по счетному входу увеличивается на 1. Считывается следующее слово из блока 2 памяти адресов, вычисленное значение элементарной коньюнкции с выхода элемента И 12 поступает на первые информационные входы третьего регистра 6 и запоминается в соответствующем разряде. Так происходит до тех пор, пока очередная элементарная конъюнкция не примет значение "1", либо пока не будут вычислены все различные элементарные конъюнкции, входящие в систему реализуемых устройством булевых функций.

После этого подается сигнал на управляющий вход блока 3 ассоциативной памяти, в Результате происходит сравнение содержимого третьего регистра б с содержимым каждого из регистров 15„ ...15„„ блока ассоциативной ггамяти 3 и на выходах элементов ИЛИ

174 ...17 формируются сигналы, соответствующие значениям булевых функций при данном наборе входных переменных. Эти значения засылаются в соответствующие разряды второго регистра 5 и могут участвовать в дальнейших вычислениях. устройство для реализации булевых функций позволяет сократить время на вычисление значений функци за счет исключения несущественных участ ков вычислений, которые не могут повлиять на значение функции в силу свойства дизъюнкции: 110=1.

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

Минимальное время вычисления значений булевый функций в данном устройстве равно: Т =f< в силу того, что первая вычисляемая элементарная конъюнкция может принять значение, равное "1".

1032451

1О

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

1 9 " °

1032451

ВНИИПИ Заказ 5401/52

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

Филиал ППП "Патент", r.Óæãîðoä,óë.Проектная,4