Устройство для вычисления булевых производных

 

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

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

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

РЕСПУБЛИН

09) (И)

С 06 F 7/04 (5D

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

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

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3693947/24 — 24 (22) 09.,12.83 (46) 23.07.85. Бюл. Р 27 (72) N.Ф. Холодный, В.Ю. Ларченко, К.К. Фурманов и Ю.И. Ялинич (71) Харьковский ордена Ленина авиационный институт им. H.Е. Жуковского (53) 681 ° 3(088.8) (56) Авторское свидетельство СССР

К - 780003, кл. G 06 F 7/04, 1978.

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

1016778, кл. G 06 F 7/04, 1982. (54)(57) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ

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

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

2 " соответственно, информационные входы блока определения значения функп- 1 ции от п переменных с (2 -1)-го по

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

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

Ф значения функции от п переменных, остальные (n 1) управляюцих входов блока определения значения функции Ц( от и переменных подключены к соответствуюцим управляющим входам блока определения значения функции от ., (n-1) переменных, выходы первого блока определения значения функции от ® (n -1) переменных соединены с первы- аий ! ми входами элементов ИЛИ с первого 1 ф

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

1- 1

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

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

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

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

1S

20 менных, выходы первого блока определения значения функции от (1 -1) переменных соединены с первыми входами элементов ИЛИ с первого по

1-1

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

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

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

Устройство для сравнения кодов (фиг.1) содержит информационные входы

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

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

И 9, 10.

Блок определения значения функции от (j+I) переменных на базе двух блоков определения значения функции от переменных (фиг.3) содержит информационные входы 11, входы 12 задания переменной, выходы 13, элементы И 14„

ИЛИ t5, блоки 16 и 17 определения значения функции от j (n-1) переменных.

Блок определения значения функции от и переменных (фиг,4) содержит информационные входы 18, входы 19 задаз 1! 68 ния переменной, выходы 20, элементы

И 21, ИЛИ 22, блоки 23 и 24 определения значения функции от (n-1) переменных.

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

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

Булевая производная функция Г(Х)

= Г(,...,Х,. . .Х„) по переменной

Х определяется по формуле

ЗГ(Х) () P(x, л.,, 20 х„)+P(X1,...,Ê,,x„) .

На входы 1 устройства подаются значения дифференцируемой функции

F.(Õ„,...,Х,...,Х ) (таблица истинности), прйчем номер соответствует номеру набора входных. переменных

%7 Ъ

Х„,...,-;,...,-„, и Х, считается старыим разрядом, а Х „ — младшим, т.е. на входы 1 устройства подаются в порядке возрастания значения исходной функции Г(О,О,...,О}, F(1 0,0,...,0),...,F(0,1,...,1), Р(1,1,...,1.), которые поступают затем на информационные входы блока

3 определения значения функции и первые входы элементов НЕРАВНОЗНАЧНОСТЬ 4.

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

Наличие в i-м разряде логической н и

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

Блок 3 определения значения функции в зависимости от поданного на его50 управляющие входы кода переменной

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

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

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

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

К(1), выходы первого и второго элементов И образуют соответствующие выходы блока К(1).

Обозначим информационные входы блока К(1) через 4„ и 6, управляющий вход — через С, а выходы — через 7 н . При этом выходные сигь2 ° налы блока К(1) могут быть вычИслены следующим образом

Т = С Й„Если на информационные входы блока

К(1) подается таблица истинности функции Г(Х ), т,е. 6„ = Р(0), 6 =

= F(l), то при С = 0 (отсутствие дифференцирования) имеем „ = Т = О, а при С = 1 (дифференцироцание по переменной Х„) (имеем t „= 6 = Р(1), ".,= =Ь„F(0) .

Таким образом, на выходах блока

К(1) при высоком потенциале на его управляющем входе имеем таблицу истинности .функции Г(Х „) .

Предположим, что блок K(j) (1 s jg

< n) в зависимости от подаваемого на него j-разрядного кода переменной, по которой ведется дифференцирование, производит преобразование подаваемой

1168925 на его информационные входы таблицы истинности функции F(X<,. XI,..., . ...,Х ) в таблицу истинности функции

F(X Õ,...,Õ ) или формирует ф ° . на всех своих выходах нули при подаче нулей на все его управляющие входы. Покажем, что в этом случае блок K(j+1), образованный с помощью двух блоков Е„(3) и K2(j) в соответствии с фиг. 3, также выполняет преобразование поданной íà его информационные входы таблицы истинности функции

Г(Х„,...,Х,. .,Х1+1) в таблицу истинности функции Г(Х„,...,Х . ..,Х +,) при подаче на его унравляющйе входы кода, соответствующего дифференцированию по переменной Х;, или формирует на всех своих выходах нули при

Ф подаче нулей на все его управляющие входы.

Обозначим информационные входы

11 блоков K(j+1) 3, К()) 16 .и К()) 17

ЧЕРЕЭ, y 2 ° ° ° y Zjy y 6 11 P 61 1 ° ° °

5 ° у 22 ) И 621 у 6 2 1 ° ° ° ) zzf Выходь

13 этих же блоков обозначим через

Р Р /М

Ф1у ь2 ° ° ° э с23+1 Ф ь и ъ 612 ь ° ° ° э ь ц 1 и, ° °,, 4 2 f СООтветственнО, управляющие входы блоков K(j+1) 12

10 обозначим через С„,С,...,С .+, причем первые j входов его образуют управляющие входы блоков K (j) (j) (фиг.3).

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

Ь1Р, если 1 6 (р « 2

P ),1+1

Ь, если2 +1 ñÐñ2

20 Сигнал на Р-м выходе блока может быть

1вычислен следующим образом

"1p 1.1 zp = "1p «1+, p,2 i

Ч С ° 6 ) = С "ЧС, ф ° 2f+gcP(2

2.1,Р-2 ) 1 11 Р 2 Z, Р-2 > 2Н Р-2»

4,р

Иа информационные входы блока

K„(j) подается первая половина таблицы истинности функции F(X1,..., ...,Х „), соответствующая случаю 3(1

Х +1 = О, на информационные входы блока К2(3) подается вторая половина таблицы истинности функции Р(Х„,..., ...,Х „ ), соответствующая случаю

При С„ = С =...= С = О, С + = 1, З +1 что соответствует случаю дифференцирования по переменной Х., получим

jу

4 по предложенному Г- = Г = 0 1 8 Р «<21

1Р откуда

АР 2, 1 4Р < 2

E р», 2 +1 <р <2

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

К()+1) формируется последователь- 4

НОсть 2Р11Ь21+21" 21 7 11 21 1 z11

° ....Ь 6 6 ... 6 или, что то же самое, последовательность F(0 0,1), Г(1,0,7,...,0,1), ...,F(1 1,0), т.е, таблица истинности функции Г(Х„,...,Х,Х +„).

ПриС„=С2=...=С;„=О, С1=1, С вЂ” С -+ †...-С вЂ” (. + — О, получим

1+1 1+2 (., 1 (Р(23 °

1 1

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

> 1Т1 функции подается на первые г, вхо55 дов устройства, а результат считыЮ вается с первых 2 его выходов.

P „ " ,- .. i, р„,г +1 F «<2

i 41

По предположению, на выходах блока К (j) формируется таблица

1 истинности функции F(X,...,Х,..., ...X,О), а на выходах блока К (j)

z таблица истинности функции F(X1 г ...,л„,...,Х, i) . Тогда на выходах блока K(j+1) сформируется таблица истинности функции Г(Х,...,Х

"l

° ° ° в Х J э.Х +1 ) °

При С1 = С = ..= С 1,1= 0 получим по предположению = = 0

"1Р 2р

1 4 P 2, и с учетом С„„„= 0 имеем оР О, 1 Р C 2J+1

Таким образом, из предложения о выполнении своих функций блоком

K(j) следует, что построенный на базе двух блоков блок К(3+1) также выполняет свои функции, а так как доказана работоспособность блока

К(1), то это утверждение справедливо для блоков производной размерности и.

2.1 2.2 2л

1168925

1168925

Составитель Е. Иванова

Редактор В. Данко Техред С.Йовжнй Корректор О. сигор

Закав 4б13/43 . Тираж 710 Подписное

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

313035, Иосква, Ж-35, Раушская наб., д. 4/5 филиал ППП "Патент", г. Ужгород, ул. Проектная, 4