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

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

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

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

Устройство для вычисления булевых функций (фиг. 1) содержит накапливаю щий сумматор 1, блок 2 памяти констант, блок 3 управления, элемент ИС fCГПO L Юll;I :E или 4, пресбразоиатель 5 параллельного кода в последовател)- ный, DJieNtenT 6 запрета, тактовьй вхо 7, группу входов 8 аргумента, цнфор- мацно1П Ы1 1 выход 9, выход 10 признака конца работы, выход I1 признака конца преобразоиапия и выход 12 разреше цця сброса.

Преобрапонатель 5 параллельного кода в последонательиьп (фиг. 2) содержит элемент ШШ 13, первую группу элементов И 14.1-1Д.П+1 (п - число . переменных реализуемой функции), вторую группу элементов И 15.1-15.П+1, группу элементов И-НЕ I6.1-16.п+1, группу RS-триггеров 17.1-17.П+1 и группу распределителей 18.1-18.П+1 импульсов.

Б. юк 3 управления (фиг. 3 и 4) содержит элемент И 19, элемент ИЛИ 20, RS-триггер 21, элемент 22 задержки, элемент И 23, второй 24, первьй 25 и третм 26 входы, первый 27 и второй 28 выходы.

Рх юк 3 управления реализуется в соответствии с фиг. 3, если вычисляемая функции представлена в порогово- дизъюпкт1 вной форме, и в соответствии с фиг. 4, если она представлена в порогово-копъюиктивной форме.

Реализуемая функция представляется в порогово-дизъюнктивной форме:

Л/ Sgn Ы;; X j - А, J

JsgnL u ;{ }

Sen у w

КГ

, + J .у

Z |wTi I i - Ь-5j ,м

V

j-(Л;

.у

.

W,j X

О

. -А.-1

X, ) (1)

где Sgn - символ пороговой функции; u)j- - вес переменной; Л,- - порог;

{i 5 - множество номеров переменной с отрицательными весами;

fi) - множество номеров переменных с положительными весами;m - разрядность накапливающего

сукмятора 1.

При этом в блок 2 памяти констант устройства последовательно записываются значения весов переменньпх W , , w ,..., Wnj и значение кода порога AJj - Л .. Причем в разряды ячеек значения веса блока 2 памяти констан записывается двоичньп код веса соответствующей входной переменной, а в разряд значения знака блока 2 памяти констант - признак знака веса: О для положительного веса и 1 для отрицательного. После записи весов все переменн|- х записывается двоичный код порога Л - с признаком знака, равным О.

Реализуемая функция может быть представлена в порогово-конъюнктивной форме:

Г 1

у bJ,., X i - А. J

,

д

5

0

X X +

ы| X; +Z |u.;

bi ГГ

- (A. 1 I , fl I иЛ J , j- nr + X X. - A;..(2)

T

При этом запись информации в блок 2 памяти констант осуществляется в том же порядке.

Разрядность блока 2 памяти констант определяется в соответствии с формулой

г logjR + 1 j + 1, (3)

n

где R max 1. I cOij I , ,(j ГТЙ).

Устройство при реализации функции по ее порогово-дизъюнктивному представлению работает следующим образом

В исходном состоянии накапливающий сумматор 1, преобразователь 5 параллельного кода в последовательный и блок 3 управления обнулены, при этом на выходе 10 признака конца работы устройства формируется сигнал логического О, разрешающиз1 прохож515

деине тактовых импульсов с тактового входа 7 через элемент 6 запрета на вход разрешения преобразования преобразователя 5 параллельного кода в последовательный и на вход разрешения чтения блока 2 памяти констант. Входная информация с группы входов 8 аргумента через преобразователь 5 параллельного кода в последовательный по одному разряду поступает каждый такт работы устройства на первый вхо элемента ИСКЛЮЧАЮПЕЕ ИЛИ 4, Одновременно из i-й ячейки блока 2 памяти констант считывается код веса i-й переменной (i 1, п). Если вес данной переменной положительньй, то на выходе значения знака блока 2 памяти констант, соединенного с входом элемента ИСБЛЮЧАЮЩЕЕ ИЛИ 4, формируется сигнал нулевого уровня. Сигнал с выхода преобразователя 5 параллельного кода в последовательный поступает на вход разрешения суммирования накапливающего сумматора 1 через элемент ИСКЛЮЧА ОЩЕЕ ИЛИ 4. К содержимому накапливающего сумматора 1 при этом прибавляется код веса i-fi переменной Если вес i-й переменной положительный, а на информационном выходе преобразователя 5 параллельного кода в последовательный - сигнал нулевого уровня, то в накапливающем сумматоре 1 действий не производится. Если вес данной переменной отрицательный (на выходе значения знака блока 2 памяти констант формируется единичный сиг- пал) , а на информационном выходе преобразователя 5 параллельного кода в последовательный - сигнал нулевого уровня, то к содержимому накапливающего сумматора 1 прибавляется абсолютное значение веса i-й переменной, а если на информационном выходе преобразователя 5 параллельного кода в последовательный - сигнал единичного уровня (при этом на обоих входах элемента ИСКЛЮЧАЮЦЕЕ ИЛИ 4 присутствует сигнал единичного уровня), то в накапливающем сумматоре 1 действий не производится. При поступлении (п+1)- го тактового импульса на выходе преобразователя 5 параллельного кода в последовательный формируется сигнал единичного уровня, разрешающий прохождение двоичного кода порога Ai с выхода блока 2 памяти констант на накапливающий сумматор 1. При этом, если входной код удовлетворяет условию

7018

Ubj,,

(4)

то На выходе переноса HaKanJuiBafiuitM-o сумматора 1 формируется сигнал еди- Н1гчного уровня, поступаю1ций на перньп вход блока 3 управления, одновременно па его третий вход поступает един1гч- ный импульс с выхода I1 признака кон- ца преобразования.

Если входной код не удовлетворяет условию (4), то на выходе переноса накапливающего сумматора 1 в момент поступления (n-t-l)-ro тактового им- пульса формируется сигнал нулевого уровня. При этом сигнал с выхода 11 признака конца преобразования преобразователя 5 параллельного кода в последовательный поступает на третга вход блока 3 управления, на выходе 12 разрешения сброса которого вырабатывается сигнал, обнуляющий нaкaпливл - щий сумматор 1. Лри этом преобразователь 5 параллельного кода в последо- вательный после поступления (n-t-l)-ro импульса принимает исходное состояние. Далее начинается очередной цикл работы устройства, при котором в течение (п+1)-го такта проверяется реа- лизация второго элемента порогово- дизъюнктивного представления функции. Если при проверке всех элементов по- рого-дизъюнктивного представления функции ни для одного из HIK не выполняется условие (4), то по окончании опроса блока 2 памяти констант на выходе признака конца опроса появляется единичньй сигнал, которьш поступает на второй вход блока 3 управле- ния, что вызывает формировапие единичного сигнала на выходе 10 признака конца работы устройства. Одновременно этот сигнал блокирует дальнейшее прохождение тактовых импульсов через элемент 6 запрета.

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

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

Таким образом, вычисление значения булевой функции в устройстве про исходит не более, чем за N (п+1) тактов.

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

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

Устройство для вьршсления булевых функций, содержащее элемент ИСКЛЮЧАЮЩЕЕ ИЛИ и блок памяти констант, отличающееся тем, что, с целью повышения производительности, оно содержит блок управления, накап- ливающий сумматор, преобразователь параллельного кода в последовательный и элемент запрета, причем такто- вьш вход устройства соедш1ен с первы входом элемента запрета, выход кото- рого соединен с входом разрешения считывания блока памяти констант и

входом разрешения преобразования преобразователя параллельного кода в последовательный, информационные входы которого соединены с группой входов аргумента устройства, информационный выход преобразователя параллельного кода в последовательный соединен с первым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, второй вход которого соединен с выходом разряда значения знака блока памяти констант, выходы разрядов значения веса которого соединены с соответствующими информационными входами накапливающего сумматора, выход переноса которого соединен с информационным выходом устройства и входом признака результата блока управления, вход признака конца преобразования которого соединен с выходом признака конца преобразования преобразователя параллельного кода в последовательный, выход признака конца опроса блока памяти констант сое- с входом признака конца опроса блока управления, выход управления сбросом которого соединен с входом разрешения сброса преобразователя параллельного кода в последовательный и входом разрешения сброса накапливающего сумматора, вход разрешения суммирования которого соединен с выходом элемента ИСКЛЮЧЛЮО ЕЕ ИЛИ, выход признака конца работы блока управления соед1шен с вторым входом элемента запрета и выходом признака конца работы устройства.

F

-С}1

:

25 t6

Фиг.:

Zf

27

25 26

Фиг.

Изобретение относится к автоматике и вычислительной технике и предназначено для вычисления булевых функций. Цель изобретения - повышение производительности устройства. Устройство для вычисления булевых функций содержит накапливающий сумматор 1, блок памяти констант 2, блок управления 3, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ 4, преобразователь 5 параллельного кода в последовательный и элемент запрета 6. В блок памяти констант последовательно записываются значения знаков и весов переменных, а также значение кода порога. Каждый такт работы устройства в зависимости от кода знака и значения входной переменной фомирует сигнал, поступающий через элемент ИСКЛЮЧАЮЩЕЕ ИЛИ на вход разрешения суммирования накапливающего сумматора, на информационные входы которого подается значение веса переменной. В последнем такте работы устройства из полученной суммы значений весов вычитается значение кода порога. Результат вычисления снимается с выхода переноса накапливающего сумматора. 4 ил.