Модуль для вычисления булевых функций

 

Изобретение относится цифровой вычислительной технике и может быть использбвано как основа для построения устройств аппаратной поддержки1 вычислений в системах автоматизированного анализа и синтеза цифровых автоматов, при их диагностике и контроле, в системах анализа и синтеза изображений, логического управления сложными объектами. Цель изобретения - расширение функциональных возможностей устройства за счет вычисления логических минимумов и максимумов булевых функций. Цель достигается тем, что в модуль, содержащий Т-триггер, первый, второй и третий коммутаторы, сдвиговый регистр, элемент задержки, первый элемент ИЛИ, введены элемент И и второй элемент ИЛИ. 6 ил., 2 табл.

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

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

РЕСПУБЛИК (я)5 G 06 F 7/04

ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕ

ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) ОПИСАНИЕ ИЗОБРЕТЕНИ

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

C (21) 4757265/24 (22) 09,11.89 (46) 23,03,93, Бюл, ¹ 11 (71) Минский радиотехнический институт (72) С,Н.Янушкевич, В,Г,Левашенко, А.А,Морозова и В.П,Шмерко (56) Авторское свидетельство СССР № 1667050, кл. G 06 F 7/04, 19.05.89.

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

N 1730617, кл. G 06 F 7/04, 11.10,89. (54) МОДУЛЬ ДЛЯ ВblЧИСЛЕНИЯ БУЛЕВЫХ ФУНКЦИЙ (57) Изобретение относится цифровой вычислительной технике и может быть использовано как основа для построения

Изобретение относится к области цифровой вычислительной техники и может бь!Ть использовано как основа для построения устройств аппаратной поддержки вычислений в системах автоматизированного анализа и синтеза цифровых автоматов, при их диагностике и контроле, в системах анализа и синтеза изображений, логического управления сложными объектами, Цель изобретения — расширение функциональных возможностей устройства за счет вычисления логических минимумов и максимумов булевых функций, Поставленная цель достигается тем, что в модуль для вычисления булевых функций, содержащий Т-триггер, первый, второй и третий коммутаторы, сдвиговый регистр, элемент задержки, первый элемент ИЛИ, причем первый информационный вход первого коммутатора соединен с информацион„„ Д„„1803908 А1 устройств аппаратной поддержки вычислений в системах автоматизированного анализа и синтеза цифровых автоматов, при их диагностике и контроле, в системах анализа и синтеза изображений, логического управления сложными объектами. Цель изобретения — расширение функциональных возможностей устройства за счет вычисления логических минимумов и максимумов булевых функций. Цель достигается тем, что в модуль, содержащий Т-триггер, первый, второй и третий коммутаторы, сдвиговый регистр, элемент задержки, первый элемент ИЛИ, введены элемент И и второй элемент ИЛИ. 6 ил.. 2 табл. ным входом модуля, информационный выход которого соединен с первым выходом второго коммутатора, введены элемент И и ! второй элемент ИЛИ, причем первый тактовый вход модуля соединен со входом Т-триг- ICO гера, выход которого соединен с тактовым С) выходом модуля и первыми управляющими () входами первого и второго коммутаторов, вторые управляющие входы которых соеди- ( нены с первым управляющим входом модуля,, (5О второй управляющий вход которого соединен с управляющим входом третьего коммутатора, первый и второй выходы которого соединены со входами элемента И, третий и четвертый выходы третьего коммутатора соединены со входами первого элемента ИЛИ, выход которого соединен с первым входом второго элемента ИЛИ, выход которого соединен со вторым информационным входом первого коммутатора и первым информаци1803908 образом:

1 1

1 1

1 1

1 1 ! 1

1 1

1 1 ! 1

1 1

1 1

1 1

1 1

1 1

11

11

11

11

11

11

11

Вычисление минимума и максимума по переменной х1 булевой функции f(X) =

25 =f(x1,õ2,хз) (n = 3) трех переменных, (Q (1) (2)„(З "(4) (5) (6) (7) 1 следующим образом:

MIN f(X) = f(x1, ..., х), „хп)д f(x1, ..., xj, ..., xn)

xi 30

x(6> Л >( х(> Л х""> х(з) Л ",.<6) х(з) Л х(7) х > Л x("> х(>) A x! (3) Л (7) x (» х(1) х( х(з), (4) (6), (6)

„(7) 1

1

1

1 !

1

1

1

1 (! )-.

= ().>з. )(.

Х!

Что эквивалентно матричной форме за- 35 писи: () .

MIN X= 02п X(Л), xi ()

MAX X= D2n X(V), xi

Х(6) V Л("> х(>Ч >( х(>V >

-х<з> V (О> V,(4> х(! > V >.(6> х(Х) V -(6) х(>V

Х(0)

„(!) х(4 >

x(4) х(4) х(. > х( х(1

1

1

ИЛ>: Х = ()..з )(-.

Х!

1

1 (2) 45

В табл. 1 приведены значения минимума и максимума булевой функции f(X) по

ПЕРЕМЕННЫМ Х1, Х2, ХЗ, 50 Из табл, 1 видно, что результат вычисления минимума булевой функции трех пере« рнных (и = 3), заданной вектором значений

Х, по переменной х1 можно представить в виде двух одинаковых векторов;

М1),) Х = (х(Я х(4) х(х() хР) х(6) х() хР))т и х1 онным входом второго коммутатора, второй информационный вход которого соединен с выходом старшего разряда сдвигового регистра, информационный вход которого соединен с первым выходом первого коммутатора, второй выход которого соединен с первым информационным входом третьего коммутатора, второй информационный вход которого соединен со вторым выходом второго коммутатора, второй тактовый вход модуля соединен со входом разрешения сдвига сдвигового регистра и входом элемента задержки, выход которого соединен со входом разрешения записи сдвигового регистра, выход элемента И соединен со вторым входом второго элемента ИЛИ.

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

B основу изобретения положены следующие математические модели функционирования компонентов и модуля в целом.

Операторы логического минимума и максимума булевой функции f(X) = f(x1, x2, „xn) и переменных по i-й переменной х! определяются соответственно соотношениями;

MAX f(X) = f(x1, ..., х>, ..., xn) v f(x1, ..., xj...,, хп)

xi где X — вектор значений булевой функции

f(X) (столбец обычной таблицы истинности, интерпретируемь(й как вектор бинарных данных: X = (х(о)х(1) „х(2" " ) ) (0

02п — матрица размерности 2" х 2", формируемая по соотношению (0

D2n= I2 ® 11 ®I2" (3) где I2i-1 и I2n — I единичные матрицы размерностей 2i 1 х 2i 1 и 2п — i х 2п-i соответственно; ® — символ кронекеровского произведения матриц, В выражении (1) вместо one ации сложения при умножении векI» тора на матрицу О и необходимо выполнять операцию конъюнкцию© а в (2) дизъюнкцию (V>), что указано справа от фор-, мул. з

Например, для и = 3 матрицы D2з

D2, D2 формируются следующим

MIN X = (хЯ х() хЩх(5 х() х() хР) х 7)) х1

1803908

7 7 ! 1

7 7

7

7 ()

1 ()

1 с

7

7 (.

7 г) е

MIN Х

15 х

7 .7

7 () I (i ()

I

1 1

1 7

1 1 и

7 7

7!

1 l

О

7 !

MAX Х х„

30

Ма- Х = (х(44(5)), хз

MAX (х1хга хЗ) = x2vx3. х7

40 рармерности 2 каждый (в общем случае для

2 функции п переменных эти два вектора имеют размерность 2" "). В результате вычисления минимума булевой функции по втОрой -:еременной хг можно выделить четыре вектора:

MIN Х = (х(о1 X@ хЯх(3))т хг ((о) (г) (7л1 (з))T х2

Мф " Х = (хфх® х(5) х(7))T хг

MILD X = =(x(4) х(б) х5 „(7))Т х раамериссти 2 каккдыи (е асщем саукае

1 размерность каждого из четырех векторов ра на 2" ), причем два из этих векторов по(1арно равны, т,е, )

hj1IN X = MIN" Х и MIN" Х = MIN X), х2 х2 х2 хг

Ана)логично для оператора нахождения минимума по переменной хз;

МП Г X = (Р4(7))т, MIN" X = (х(о), (7))т, xj хз

Mig" X = ((2 (3))Т MIN „Х = ((2 (3))Т хз хз

MIg Х = (хб х 5))Т хз

„,)((aÙ J)))T M)N, )т ((е) „(т))т хз хз

Здесь выделены восемь векторов размерности 2 каждый (в общем случае 2" ), при о это((попарно уавны следующие вектора:

MIN,, Х = MIN "Х, MIN" Х = MIN Г

MIN Х = MIN X, М!! ) "X = MIN" " Х. хз хз хз хз

Аналогичные результаты получаются при вычислении максимума булевой функции 7о переменной x;(i = 1 n) (табл. 1), Таким образом, искомый результат, т,е. вектор минимаксной операции по i-1 переменнойй MIN Х (МАХ X) состоит их 2 векторов

xi xi раз()4ернотси 2" каждый, среди которых имефтся попарно равные, Следовательно необходимо вычислять только один вектор из п р.

Пусть требуется вычислить минимум и максимум по переменной х1 булевой функции f(X) = х7хг хз трех (n = 3) переменных, Вектор значений булевой функции имеет

5 вид X = (0101 0111) . В соответствии с матет матическими моделями (1) и (2) определим минимум и максимум булевой функции х7х2 у хз по переменной х(:

По векторам значений MIN X (0101 0101) и

«де х7

МАХ Х = (0111 0111) строим их аналитичех! ские выражения:

35 MIN (х)хгкехз) = x2 хз. х!

На фиг. 1 и 2 представлены операционные графы алгоритма реализации математической модели (1) и (2): на фиг, 3 структурная схема модуля; на фиг, 4 — струк45 тура, позволяющая вычислять логический минимум булевой функции 1(Х) трех переменных; на фиг. 5 — диаграмма функционирования этой структуры; на фиг, 6 — процесс вычисления логического минимума булевой

50 функции (л = 3) переменных.

Модуль (фиг, 3) содержит Т-триггер 1, первый 2, второй 3 и третий 4 коммутаторы, сдвиговый регистр 5, элемент задержки 6, первый 7 и второй 8 элементы ИЛИ, элемент

55 И 9, два тактовых входа 10 и 11, два управляющих входа 12 и 13, информационный вход 14, информационный выход 15, тактовый выход 16, причем первый тактовый вход модуля соединен со входом Т-триггера 1, выход которого соединен с тактовым выхо1803908 дом модуля и первыми управляющими входами первого 2 и второго 3 коммутаторов, вторые управляющие входы которых соединены с первым управляющим входом модуля, второй управляющий вход которого соединен с управляющим входом третьего коммутатора 4, первый и второй выходы которого соединены со входами элемента И 9, третий и четвертый выходы третьего коммутатора 4 соединены со входами первого элемента ИЛИ 7, выход которого соединен с первым входом второго элемента ИЛИ 8, выход которого соединен со вторым информационным входом первого коммутатора 2 и первым информационным входом второго коммутатора 3, второй информационный вход которого соединен с выходом старшего разряда сдвигового регистра 5, информационный вход которого соединен с первым выходом первого коммутатора 2, второй выход которого соединен с первым информационным входом третьего коммутатора 4, второй информационный вход которого соединен со вторым выходом второго коммутатора 3, второй тактовый вход модуля соединен со входом разрешения сдвига сдвигового регистра 5 и входом элемента задержки 6, выход которого соединен со входом разрешения записи сдвигового регистра 5, выход элемента И 9 соединен со вторым входом второго элемента ИЛИ 8, первый информационный вход первого коммутатора 2 соединен с информационным входом модуля, информационный выход которого соединен с первым выходом второго коммутатора 3.

Триггер 1 со счетным входом и нулевым начальным состоянием предназначен для регламентирования работы модуля по времени, Первый коммутатор 2 обеспечивает передачу сигнала с первого информационного входа на первый выход при нулевом (низком) логическом уровне сигнала на первом или втором управляющих входах; в противном случае осуществляется передача сигнала с первого информационного входа на второй выход и со второго информационного входа на первый выход, Второй коммутатор 3 предназначен для передачи сигнала со второго информационного входа на первый выход при низком логическом уровне сигнала на первом или втором управляющих входах; в противном случае осуществляется передача сигнала со второго информационного входа на второй выход и с первого информационного входа на первый выход.

Третий коммутатор 4 обеспечивает передачу сигналов с первого и второго инфор5

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

Регистр 5 предназначен для хранения и преобразования (сдвига) кода, поступившего на информационный вход, Запись информации в регистр 5 осуществляется по управляющему сигналу на входе разрешения записи. Сдвиг содержимого в сторону старших разрядов выполняется по сигналу сдвига на входе разрешение сдвига. Емкость регистра 5 — 2" разрядов.

Элемент задержки 6 обеспечивает задержку входного сигнала на время Ж, Первый 7 и второй 8 элементы ИЛИ предназначены для логического анализа входных сигналов посредством выполнения над ними операции дизъюнкции.

Элемент И 9 предназначен для логического анализа входных сигналов посредством выполнения над ними операции конъюнкции, Модуль для вычисления булевых функций работает в двух режимах, определяемых сигналом на первом управляющем входе модуля. B первом режиме модуль функционирует когда на его первом управляющем входе высокой логический уровень напряжения, В этом режиме реализуется непосредственное вычисление минимума (максимума) булевой функции f(X) по i-й переменной х1.

Второй режим обусловлен низким логическим уровнем напряжения на первом управляющем входе модуля. При этом режиме функционирования данные проходят через модуль без изменений, т,е. в данном модуле вычисление минимума (максимума) булевой функции не происходит, Рассмотрим функционирование модуля в первом режиме, В период времени to tan;-1, т.е. на первых 2" тактах работы происходит загрузка регистра 5 элементами х, х, ..., x " вектора X (фиг, 5).

В следующий период (т2п -гт2*2п - i - 1), т.е. на следующих 2" тактах происходит вычисление первого вектора MIN 7(МАХ X)

xi xi из пары равных векторов MIN X и MIN"Х

xi xi (МАХ X и MAX" X) вектора результата

xi xi

MIN X (MAX Х).

xI xI

В периодвремени(12*2n i — 13*2n- - 1), т.е. на следующих 2" тактах, из регистра 5

1803908 о существляется выдача результата — второго ректора MIN "X (MAX"XTèç пары равных

xi xi векторов MIN X и MIN "X(MAX X и MAX" X).

xl xi xi xi 5

Одйовременно выполняется загрузка регистра 5 следующими элементами вектора Г, На остальных тактах вычисления осуществляются аналогично периоду t2n — i — сз*гп — I — 1. . На первом такте первый элемент х ) 10 вектора значений X = (x(о х(")...х(2" 1))т пос упае т с первого информационного входа первог коммутатора 2 на его первый выход (на

nepleoM управляющем входе — низкий логический уровень сигнала, передаваемый с 15 вы ода счетного триггера 1) и далее записывается в регистр 5, что осуществляется следующим образом. По синхросигналу, перйдаваемому со второго тактового входа мор уля на вход разрешения сдвига регистра 20

5, происходит сдвиг его содержимого на оди разряд влево (в сторону старших разряд в), По сигналу, поступающему на вход раз ешение записи регистра 5 через время

Ж с выхода элемента задержки 6, осущест- 25 вля тся запись сдвинутого содержимого в

per стр 5 (в его первый разряд записывается и формация, поступающая с первого вы1 ход коммутатора 21

На втором и последующих тактах (по 2" 30

-й т кт включительно) эта процедура порторяе ся для элементов х ...., х ", В рез льтате на 2" -м такте в первом, втором, -м разрядах регистра 5 находятся зна ения элементов х ", х " ), „35 х(о1 оответствен но. а (2" + 1)-м такте 2" + 1)-й элемент

x ": вектора значений X = (х х ...х " ) пер дается с первого информационного вхо а первого коммутатора 2 на его второй 40 вых д(на первом управляющем входе — высок и логический уровень сигнала) и далее на первый информационный вход третьего коммутатора 4, Одновременно с выхода регист а 5, через второй коммутатор 3 (на его 45 пер омуправляющем входе — высокийлогическ и уровень сигнала) на второй информационный вход третьего коммутатора 4 передается элемент x . С первого и второ(о) го иНформационных входов третьего комму- 50 татора 4 информация передается на входы элемента И 9 (при этом на управляющем вход1е коммутатора 4 — низкий логический уровень напряжения, передаваемый со второго управляющего входа модуля) или на 55 третий и четвертый выходы коммутатора 4 и дале на входы первого элемента ИЛИ 7 (при этом на управляющем входе коммутатора 4 — высокий логический уровень напряженйя). Таким образом реализуется разделение процесса вычисление минимума или максимума булевой функции. Результат конъюнкции с выхода элемента И 9 (при вычислении минимумов) или дизъюнкции с выхода первого элемента ИЛИ 7 (при вычислении максимумов) поступает соответственно на второй или первый вход второго элемента ИЛИ 8. С его выхода результат передается на второй информационный вход первого коммутатора 2 с первого выхода которого записывается в регистр 5. Кроме того результат поступает на первый информационный вход второго коммутатора 3, с первого выхода которого передается на информационный выход модуля.

Аналогично модуль функционирует на (2" +2)-м и последующих тактах(по2*2" -й включительно), при этом на информационный выход модуля поступают элементы первого из первой пары равны ; векторов

MIN X u MIN "X (MAX X u MAX "X) вектора—

XI Xi XI xi

MIN X (MAX X), значения этих элементов

xi xi записываются также в регистр 5.

Таким образом на 2*2" -м такте в регистре 5 записаны элементы первого вектора

MIN X(MAX Х из первой пары равных векторов.

xi xi

На (22" + 1)-м такте содержимое старя-i шего 2 -го разряда регистра 5 передается со второго информационного входа второго коммутатора 4 (на его первом управляющем входе низкий логический уровень сигнала) на информационныи выход модуля. Одновременно следующий элемент x " вектора значений Х =(х х ...х " j поступает с первого информационного входа первого коммутатора 2 на его первый выход и далее записывается в регистр 5.

Аналогично устройство функционирует на (2*2" + 2)-м и последующих тактах (по

3*2" -й включительно), при этом на информационный выход модуля пеоедаются элементы второго вектора MIN "X (MAX "Х) из

xi xi первой пары равных векторов MIN Х и MIN "X

xi xi (MAX X u MAX " Х).

xi xi

На остальных тактах вычисления выполняются аналогично вычислениям в моменты

ВРЕМЕНИ t2n — i - 1 t3*2n - i.

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

55 довательном соединении модулей, если в модуле не требуется производить вычисление минимума (максимума) булевой функции no i-й переменной.

На первом тауе первый элемента х() вектора значений Х=(х(о х " „,õ " )) поступает с первого информационного входа первого коммутатора 2 на его первый выход и далее записывается в регистр 5, На втором и последующих тактах (по 2"

-й такт включительно) эта процедура повторяется для значений х(1), ..., х

В результате на 2" -м такте в первом, втором,;... 2" -м разрядах оегистра 5 находятся значения элементов х " "), х(2" ..., х() соответственно, На (2" + 1)-м такте содержимое старшего разряда регистра 5 — элемент х(пере(о) дается со второго информационного входа второго коммутатора 3, на его первый выход и далее на информационный выход модуля, Одновременно на первый вход первого коммутатора 2 поступает следующий элемент х(" ) вектора значений Х = (х )х()...х(" )), который передается на первый выход первого коммутатора 2 и далее записывается в регистр 5.

Аналогично модуль функционирует на (2" + 2)-м и последующих тактах (по 2"-й включительно).

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

Рассмотрим конкретный пример построения и функционирования линейной структуры, позволяющей вычислять минимум по переменным х1, хг и хз булевой функции f(x) = f(x>, х2, хз) трех переменных (и = 3), заданной своим вектором значений

Х ((0) (1) (7))т

Данная структура представляет собой последовательное соединение трех модулей (фиг. 4), Информационный вход и тактовый выход первого модуля являются информационным входом и тактовым выходом устройства, информационным выходом и тактовым входом которого яваляются информационный выход и первый тактовый вход третьего модуля, первый тактовый вход и информационный выход k-ro (k=1,2) модуля соединены соответственно с такто8blM выходом и информационным входом (k + 11-ro модуля, второй тактовый вход i-го (i = 1, 3) модуля объединен с первым тактовым входом третьего модуля.

Работу устройства поясняют табл, 2 и фиг. 4-6, В табл. 2 отражено взаимодействие модулей (содержимое регистра 5 каждого

50 модуля) при вычислении минимума булевой функции заданной вектором значений ,х()), по переменным х>, х2 и хз, Предварительно на втором и первом управляющих входах i-го модуля устанавливается соответственно низкий и высокий логические уровни напряжения, которые регламентируют вычисление минимума по переменной хь

На первом такте (момент времени tp — t<, фиг. 4) первый элемент х поступает на ин(о) формационный вход первого модуля и через коммутатор 2t записывается в первый разряд регистра 51, Аналогично на втором, третьем и четвертом тактах в регистр 51 записывают:я значени ) элементов х ), х(), х ) вектора Х = (х х )...х ), В момент времени t4 (фиг, 5) триггер 11, устанавливается в единичное состояние, В результате на пятом такте выполняется конъюнкция элемента х поступившего с (о) выхода регистра 5l через второй 31 и третий

4t коммутаторы на вход элемента И 9, и элемента х, поступившего со второго выхода первого коммутатора 21 на первый вход третьего коммутатора 61 и далее на другой вхо(д элемента И 91, Результат коньюнкции у1 = х()A х() через элемент ИЛИ (о) (4)

81 и первый коммутатор 21 записывается B регистр 5l, а также через второй коммутатор

31 поступает на информационный выход первого модуля. С информационного выхода первого модуля y> ) передается на ино) формационный вход второго модуля и далее на первый информационный вход первого коммутатора 22 второго модуля. На шестомтакте (момент времени t5 — t6) на информационный выход первого модуля поступает результат у1(= х(х(), который также через первый коммутатор 41 записывается в регистр 5t. На седьмом и восьмом тактах на информационный выход первого модуля поступают соответственно результаты у1() = хЖ х(6) и у1() = х(р х(7), Кроме того, по окончании восьмого такта в регистре

5t оказываются записанными элементы у1, yl, yl(, у1 ) — элементы второго из (О1 1) (г1 (З) пары равных векторов вектора результата MIN X (MIN Х и MIN" 7).

xi xi xi

На девятом такте вычислений с выхода регистра 51 на информационный выход первого модуля поступают значения элемента у1() = y> результата, а на десятом — двенад(4) цатом тактах — соответственно значения (5) (1) (6) (2) (7) (3)

Y> =(y> )y> .„уР)= MIN Г Кроме того, на х1 девятом такте на третий вход первого моду13

1803908

14 ля могут поступать и обоабатываться элементы вектора значений Х следующей функции f(X ).

Таким образом, на первых четырех тактах выполняется загрузка перв< го модуля 5 значениями элементов вектора Х, на следующих восьми — выдача результата, причем, начиная с девятого такта может осуществляться загрузка первого модуля элементами следующего вектора Х, 10

Функционирование второго модуля, обеспечивающего вычисление минимума по переменной хг, начинается на пятом такте функционирования устройства (момент времЕни t4). 15

На первых двух тактах функционирования второго модуля (момент времени t4 — t5, t5 — t6) происходит загрузка в регистр 52 э7)ементов у1 и у1(вектора значений

О (1 у (у„(О)у,() у1()) 20

На третьем такте функционирования второго модуля (момент времени t) — t7) вычисляется конъюнкция yz = y1 ëó1, и результат yz поступает на информационный (О) выход второго модуля и, кроме того, записы- 25 вается в регистр 5z. К концу четвертого такта функционирования второго модуля (момент времени t7 — 18) на информационный выход второго модуля поступает результат уг ") = уй у1(, а в регистре 5z оказываются 30 записанными значения уг и yz ). На пятом (0) (1) и фестом тактах функционирования второго модуля (моменты времени тв — t9 и tg — t10) соответственно на информационный выход второго модуля с выхода регистра 5z по- 35 ступают значения элементов yz = уг и (О) уг ) = уг ), и в рЕгиСт 52 ЗапиСываЮтСя (1) ,5, — м. значения элементов у1(и y1 вектора У1.

На седьмом †восьм тактах функционирова))-сия второго модуля (моменты времени 40

t10— - t11 t11— - Иг) соответственно на информационный выход второго модуля поступак т (4) „(4) „(6) (5) „(51 (7) вектора Уг, а на девятом — десятом тактах (моменты времени t12 — t13 t13 — t14) — результаты 45 у2 ) у2(и у2 = y2 с выхода регистра 52, (4) 7) 5)

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

Г2 = (у2 y ...у2 ) = MIN (MIN RJ. 50 х2 х1

Функционирование третьего модуля обеспечивает вычисление минимума булевой функции по переменной хз и начинается на седьмом такте функционирования уст- 55 ройства (момент времени t6 — t7). На первом такте функционирования третьего модуля происходит загрузка регистра 53 первым (0) элвментом yz вектора значений Уг. На втором такте функционирования третьего модуля (момент времени тт-тф вылрлняетоа конъюнкция элементов y3(= уг )h уг(. (О)

Результат уз() поступает на информационный выход третьего модуля и, кроме того, записывается в регистр 53. На третьем такте функционирования третьего мок)уля IMoмент времени t8-t9) результат уз(= уз ) c (1 9) выхода регистра 5з поступает на информационный выход третьего модуля, при этом происходит загрузка модуля значением элемента уР, Далее на четных тактах (четвертом, шестом, восьмом) происходит формирование результатрв конъюнкции соответственно

УЗ У2 УиУ2 УЗ У2 -»yz И УЗ

=уг р, уг, а на нечетных (пятом, седьмом, девятом) на информационный выход модуля поступают элементы уз(= уз(, уз = y3 и (з) (г

Уз() = уз() соответственно.

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

Уз = (уз()уз()...уз())" = MIN (MIN (М IN Х))

Хз Х2 Х1

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

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

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

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

1803908

Т о б л и ).(о Х

NIN Х

МнХ Х

Х .. (0) .(2) х пх

Х(1) Лх(3),())) „(3 (O)p (с ) (2 2 (0),(7) .,(3) х, (3) () )$7 ( (4. ),. (а ) y(d )vx(Л) х " х х(5)Рх(Х (г ) х(2 х ух (4)A. (6) (6) (7) (3 (7) тый выходы третьего коммутатора соединены с входами первого элемента ИЛИ, выход которого соединен с первым входом второго элемента ИЛИ, выход которого соединен с вторым информационным входом первого коммутатора и первым информационным входом второго коммутатора, второй информационный вход которого соединен с выходом старшего разряда сдвигового регистра, информационный вход которого соединен с первым выходом первого коммутатора, второй выход которого соединен с первым информационным входом третьего коммутатора, второй информационный вход которого со- единен с вторым выходом второго коммута5 тора, второй тактовый вход модуля соединен с входом разрешения сдвига сдвигового регистра и входом элемента задержки, выход которого соединен с входом разрешения записи сдвигового регистра, 10 выход элемента И соединен с вторым входом второго элемента ИЛИ, 18

1803908

Первый иодупь

Запри +oPgsa

Хс(/) .«(/)

«и) g (г) у (o) g (4) ® ro) (о) с ) у" 9г ф")и y

y (OP у (г) g(of с() ,nó",, «) (3) у(О) ., ((>

2 hУа у (3) /

4 (г) (4)

/,(„),, ) Уг со) (2) у (2) 2

®(4) у (2) у ($)

„ (4) „(г) <3) г n9 и) (/) Л

Хс )и i() g (5) у (5) «(2)

«(/) уЩ

«(3)

Х сг)

Х с/) (со) g (+I g(4) л х")

«сг) х") Х(% ХЩ

Х Х") л д (3) (2) Х(г) Х") и х" х ) g пх ") Х (5) Хс» а)

Х(г)Х/4)

X(l) X(sj и х "Ь х") Хсз)Х Р) л

Хс(Х(4)

Хсзр Х(5) /и) х О ") у (/) е с/) (g)

/ nÕ у,а)

«(г)л Х (ь) д (5) (3) х(/) л (4)

Хсо)П Х(4) (3 ) с() (s) Ю ( ф ч4 ф Ч (3)

g2

«) (3) фбlпиУ ЯОдЦЯ

y (o)

Й /1Й

«) g лф" у (2) (2)h У (3) 1803908

Продолжение табл. 2

1803908 (а3 (4)

ИАХ Х

Хл (У) 1803908

1803908

1803908

P6f !

Ы ь= ! 3 сэ

Qg pQ 4 5 б 7В9

А.июни

° др ДЮОфЯК47

„Ьычислейие и ЮыЭоча яульй ол об д 5ыдочормульгпато6

Фиг 5

1803908

Peasccmp - - первого модуяя

„т у ) u) Х fs) Х ) Хи) Хг ) .2 ч (o) y(1) (2) (5) уМ) д(5) у (6) get) T

1егист 5б порогд обул

1егисп р 5гпрегпь его юЫуля

« 7 (уФ gled) y

5 4 5 б 8 9 1C Л 12 ó5 4 35

7 Я л 73у фар 6

Составитель С, Янушкевич

Редактор Т, Иванова Техред М.Моргентал Корректор Л. Ливринц

Заказ 1057 Тираж Подписное

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

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

Производственно-издательский комбинат "Патент", r. Ужгород. ул.Гагарина. 101

t ,1 и

ii . !