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

переменных, 2i элементов И и 2 элементов ИЛИ, причём информационные входы блока определения значения функции от j переменных с первого по 2 -и соединены с соответствуюпщми информационными входами первого блока определения значения функции от (j-1) переменных.и с первыми входами элементов И с ()-го по соответственно, информационные входы блока определения значения функции от j переменных с (2+1)-го по соединены с информационными входами второго блока определения значения функции от (j-1) переменных и с первыми, входами элементов И с первого по соответственно, вторые входы элементов И блоков определения значения функции от j переменных соединены с у-м управляющим входом блока определения значения функции от J переменных, остальные (j-1) управляющих входов блока определения значения функции от (i-1) переменных подключены к соответствующим управляющим входам блоков определения значения функции от (j-1) переменных, вьпсоды первого блокаопределения значения функции от (у-1) переменных соединены с первыми входами элементов ИЛИ с первого по о i-f -iJ -и соответственно, выходы.второго

блока определения значения функции от (у-1) переменных соединены с первыми входами элементов {ШИ с (2-+1)го по 21-й соответственно, выходы элементов И соединены с вторыми входами соответствующих элементов ИЛИ, выходь которых являются выходами блока определения значения функции от j переменных, каждый из входящих блоков определения значения функции от двух переменных блоков определения значения функции от одной переменной содержит два элемента И, первые входы .которых являются информационными входами блока опре-. деления значения .функции от двух переменных, вторые входы которых соединены с управляющим входом блока определения значения функции от двух переменных, а выходы элементов И являются выходами блока определения значения функции от двух переменных.

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

1

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

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

На фиг. 1 приведена структурная схема устройства; на фиг.2 - схема блока определения значения функции от одной переменной; на фиг.З - схема блока определения значения функции от (J+1) переменных на базе двух блоков определения значения функции от j переменных (Г j п, где п произвольное целое положительное число, не равное 1); на фиг.4 - схема . блока определения значения функции от п переменных, построенного на базе двух блоков определения значения функции от (п-1) переменных; на фиг.З - полная схема блока определения значения функции от 3 переменных.

Устройство для сравнения кодов (фиг.1) содержит информационные входы 1 устройства, входы 2 задания переменной, блок 3 определения значения функции, элементы НЕРАВНОЗНАЧНОСТЬ 4, выходы 5 устройства.

Блок определения значения функции от одной переменной (фиг.2) содержит информационные входы 6, входы 7 задания цеременной, выходы 8, элементы И 9, 10.

Блок определения значения функции от (J+1) переменных на базе двух блоков определения значения функции от

j переменных (фиг.З) содержит информационные входы 1 1 , входы 12 задания переменной, выходы 13, элементы И 14„ ИЛИ 15, блоки 16 и 17 определения значения функции от j (п-1) переменных.

Блок определения значения функции от п переменных (фиг.4) содержит информационные входы 18, входы 19 задания переменной, выходы 20, элементы И 21, ИЛИ 22, блоки 23 и 24 определения значения функции от (п-1) переменных.

Блок определения значения функции от 3 переменных (фиг.5) содержит информационные входы 25, входы 26 задания переменной, выходы 27, блоки 28 определения значения функции от одной переменной, блоки 2S) определения значения функции от двух переменных, элементы И 30, ИЛИ 31. .

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

Булевая производная функция F(X) F(X|,.. . Д,-, .. .,Х) по переменнойX определяется по формуле

. f(X) - -,7 F(X,,..,X.

X|)+F(X ,. . . ,Х ,. . . ,Хр) .

На входы 1 устройства подаются значения дифференцируемой функции Р.(Х,..., Х,..., X (таблица истинности), причем номер соответствует номеру набора входных переменных Х ,.. . ,,... ,Xfj, и Xi считается старшим разрядом, а Х - младшим, т.е. на входы 1 устройства подаются в порядке возрастания значения исходной функции F(0,0,...,0), F(1.0,0,... ,0) ,...-. ,F(0,1,.. . , 1) . F(1,1,..., 1.) , которые поступают затем на информационные входы блока 3 определения значения функции и первые входы элементов НЕРАВНОЗНАЧНОСТЬ 4.

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

Блок 3 определения значения функции в зависимости от поданного на ег управляющие входы кода переменной X. преобразует поданную на его информационные входы таблицу истинности функции F(X,...,Х,...,Хр) в таблицу истинности функции F(X ,..,, ...,Xj,...,Х), которая подается на вторые входы элементов НЕРАВНОЗНАЧНОСТЬ 4.

Соответствующие элементы двух таблиц истинности суммируются по модулю два на соответствующих элементах НЕРАВНОЗНАЧНОСТЬ 4, на выходах которых формируется таблица истинности функции

F(X)

f(X)

Если на все входы устройства 2 подать нули, Td на выходах блока 3 будут сформированы нули, в результате чего на выходах устройства 5 будет повторена таблица истинности исходной функции F(X).

Рассмотрим работу блока определения значения функции К(п)К(1) для обработки логических функций от одной переменной, т.е. F(X)F(X) (фиг.2). В этом случае блок 3 содержит два элемента И 9, 10, первые входы которых соединены между собой и подключены к управляющему входу 7 блока К(1), вторые входы первого и второго элементов И подключены соответственно к второму и к первому информационным входам б коммутатора К(1), выходы первого и второго эле ментов И образуют соответствующие выходы блока К(1). Обозначим информационные входы блока К(1) через 6 и 6 , управляющий вход - через С , а выходы - чрез Г и 2 . При этом выходные сигналы блока К(1) могут быть вычислены следующим образом

Ч C,(J,,;

г-I

2 т 1

Если на информационные входы блока К(1) подается таблица истинности функции F(X,), т.е. d F(0), 6 F(1), то при (отсутствие дифференцирования) имеем Zjj О, а при С Т (дифференцирование по переменной X ) (имеем .62 F(l), F(0).

Таким образом, на выходах блока К(1) при высоком потенциале на его управляющем входе имеем таблицу истинности функции F(X) .

Предположим, что блок K(j) (1 J4l п) в зависимости от подаваемого на него j-разрядного кода переменной, по которой ведется дифференцирование, производит преобразование подаваемой

на его информационные входы таблиць истинности функции F{X,...,Х,..., . ...,р в таблицу истинности функции F(X ,...,Х;,...,Ху) или формирует на всех своих выходах нули при подаче нулей на все его управляющие входы. Покажем, что в этом случае блок K(j+1) образованный с помощью двух блоков lC(j) и Kx(j) в соответствии с фиг. 3, также выполняет преобразование поданной на его информационные входы таблицы истинности функции F(X ,.. . ,Х,... ,Xj+t) таблицу истинности функции F(X,... ,Х,-,... ,Xj« при подаче на его управляющие входы кода, соответствующего дифференцирован1Ш по переменной Х, или формирует на всех своих выходах нули при подаче нулей на все его управляющие входы ..

Обозначим информационные входы 11 блоков K(j+1) 3, K(j) 16 и K(j) 17 через 6, d., ,..., 2.1 ; 6 1 , 6,,, . .., . .., j и i , (bj2,. . ., 22 j выходы 13 этих же блоков обозначим через

f F

. f u 21 г 22- соответственно, управляющие входы блоков K(j+1) 12 обозначим через С ,0,,... ,С ; , приче первые j Входов его образуют управляющие входы блоков K(j) и K,.j(j) (фиг.З).

При этом обозначении имеем:

, если 1 Р

А

J+1 ,jp, если 2 + 1 Р 2

Сигнал на Р-м выходе блока может быть вычислен следующим образом

Па информационные входы блока K(j) подается первая половина таблицы истинности функции F(X,..., ...jXj.), соответствз ощая случаю Х; О, на информационные входы блока KjCj) подается вторая половин-а таблицы истинности функции F(X,...,

,Xj4. ) , соответствующая случаю

Х

U1

При С С... Cj О,

1 что соответствует случаю дифференцирования по переменной Х-, получим по преддюженному 0, 1 Р l) откуда

1 4 Р : 2

Р t2J

гр

1 Р 1

. Р-21 Согласно этому, на выходах блока

K(j+1) формируется последовательность .ч., , , - ( Ji-,7 - J 2 2 или, что то же самое, последовательность F(0,...,0,1), F(1,0,7,...,0,l) F(1,....,1), F(0,...,0), F(1,0,;..,0) ...,F(1,...,1,0), т.е. таблица истинности функции F(X jX-,X jV). При C. C ...C.:, 0, C. 1,

По предположению, на выходах блока К (j) формируется таблица истинности функции FCXv,...,Х,,..., ...Х;,0), а на выходах блока IG(j) таблица истинности функции F(X,..,, J...,Xj,1). Тогда на выходах блока K() сфррмируется таблица истинности функции F(X ,...,X.,...,

C-i - Cj - .. Cj+-t о получим по предположению . 1 4 Р 4 2J, и с учетом С,, О lii

liMeeM €р О, 1 4 Р . - Таким образом, из предложения о выполнении своих функций блоком K(j) следует, что построенный на базе двух блоков блок K() также выполняет свои функции, а так как доказана работоспособность блока К(1), то это утверждение справедливо для блоков производной размерности п.

При использовании устройства размерности п для дифференцирования логических функций от m переменных (т п) таблица истинности такой функции подается на первые 2 , входов устройства, а результат считы brt

вается с первых 2 его выходов

2J 2.2 гл

1168925