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

(/

С

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

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

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

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

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

Логическая производная булевой функции f(x) f(x,, х2, ..., , переменных по перемнной x(i I,m) определяется соотношением ЭЈ(х)

Ж{

- «(XL

-X

I

mb

xJefCx,, (1)

СЛ

Јь

.

СЛ

со

В матричном виде данная процедура представляется следующей математической моделью:

ЭЈ(х)

ЭХ;

- ., (mod 2),

(2)

где Хг - вектор значений (вектор истинности) булевой функции

,- t - г- (М Ml{ft Ч

f(x), ХЈ ...

,- матрица дифференцирования размерности 2т, формируемая по рекуррентному соотношению

D

(И

г РП

де ®

Ч

т

г1М)® ®I7(m-U

-символ кронекеровского про- 10 иэведения матриц;

-единичная матрица размерности 2 р х 2Р.

Операции сложения при перемножении матрицы и вектора Хг в (2) также выполняются но модулю два.

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

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

Блок 1 вычислений (фиг.2) содержит регистр входных данных 4, сумматор 5 по модулю два, коммутатор 6, причем информационный вход и вход синхронизации коммутатора 6 являются информационным входом и входом синхронизации блока соответственно, первый и в,торой выходы коммутатора 6 подключены к первому информационному входу сумматора 5 по модулю два и к информационному входу регистра 4 входных данных соответственно, выход регист- ра 4 входных данных подключен к второму информационному входу сумматора по модулю два 5, выход которого является выходом блока.

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

7 выходных данных соответственно, информационный вход регистра 7 вы

0

5

0

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

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

Пусть необходимо вычислить логическую производную «Xj/ax,, эХс/дХр к булевой функции f(x) f(x1, хг, х) трех переменных. Исходный вектор значений Х xj, x(4.. хс тфункции f(x) подается поэлементно, начиная с младшего элемента х (0 на информационный вход устройства. Устройство содержит три блока вычислений и три блока вывода данных и блок синхронизации.

Рассмотрим работу первых, вторых и третьих блоков вычислений и блоков вывода данных.

На тактах с первого по четвертый происходит загрузка первого блока

5

0

5

.(о)

X

О)

X

(г)

вычислений элементами х

/ Я)

их1 вектора значений Хг. Это осуществляется следующим образом: на первом такте первый элемент х 0 вектора Хр поступает на информационный вход коммутатора 6 и передается на его второй выход по низкому логическому уровню сигнала на его входе синхронизации и записывается в регистр 4. На втором такте элемент х вектора Xf х(0 х0)... х (1)Г записывается в регистр 4 аналогично. Одновременно элемент перезаписывается из первого во второй разряд регистра 4. На третьем и четвертом тактах значения элементов х и вектора X,, последовательно записываются в регистр 4. Таким образом, к концу четвертого такта знало)

til

„ u v (31

, А , Л

чения элементов , х оказываются записанными соответственно в четвертом, третьем, втором и первом разрядах регистра 4. На пятом такте происходит суммирование по модулю два элемента , поступившего с выхода регистра 4, и элемента х , поступившего с первого выхода коммутатора 6 по высокому логическому уровню напряжения на его входе синхронизации. Результат суммирования у т(0) х(0 ®х t4 поступает на информационный вход регистра 7 и по высокому логическому уровню сигнала на входе синхронизации коммутатора 8 передается на его выход, т.е. на первый выход устройства. На шестом такте на выход устройства передается результат у х° вх (5, этот же результат записывается в регистр 7. На седьмом и восьмом тактах на выход устройства передаются соответственно результаты у x(2kx и у (3 х э ® х 7 и, кроме того, по окончании восьмого такта в регистре 7 ока-

(о)

зываются записанными элементы у

(о)

v(M v(tj У , У 1

У W- элементы второго

из пары равных векторов S X.f/ 3х- и «ЭХрк/ х;, составляющих вектор

и у{ х ex (7 вектора результата Y-/X.J, а на девятом и десятом - результаты у( и у ( ( .

Таким образом, на первых двух тактах происходит загрузка второго

ми - выдача результата YP/XJ

rvt° v о

результата 3X1 На девятом так- )5 блока вычислений, на следующих вось- те вычислений с выхода регистра 7 через коммутатор на выход устройства поступает значение элемента вектора результата Yr/x,, а на десяyC jT.

20

у7у,

Рассмотрим функционирование третьего блока 1 вычислений и третьего блока 3 вывода данных.

том - двенадцатом тактах соответственно значения у у (,1 , У11) У , и у1,7 У вектора Yf/x, у(,° у W У 1 г На девятом такте в устройстве можно вводить для обработки элементы следующего вектора X.

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

Функционирование второго блока 1 вычислений и второго блока 3 вывода данных, обеспечивающих вычисление вектора Y-/x4 происходит следующим образом.

На первых двух тактах выполняется загрузка второго блока вычислений элементами х ° и х

чений Xf х (о)х

О)

вектора знахо)

П1

т:

на

первом такте элемент х записывается в регистр 4 (его первый разряд), на втором также в регистр 4 (его первый разряд) записывается элемент х 1 , а элемент х перезаписывается во второй разряд регистра 4. На третьем такте происходит суммирование по модулю два элементов х ( и х и результат у (7° х 1° ®х поступает на выход устройства и, кроме того, записывается в регистр 7 выходных данных. К концу четвертого такта на выход устройства поступает результат у ( l xu) , а в регистре 7 оказываются записанными значения элементов у 1° и у . На первом и

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

(«

элементов у у у и у « - , а в регистр 4 последовательно записываются значения элементов

х и

ю

X

(Я

вектора Х/. На седьмом и восьмом тактах на выход устройства поступают элементы у х ® х

«)

и у{ х ex (7 вектора результата Y-/X.J, а на девятом и десятом - результаты у( и у ( ( .

Таким образом, на первых двух тактах происходит загрузка второго

ми - выдача результата YP/XJ

rvt° v о

- )5 блока вычислений, на следующих вось- ° .

20

й

25

у7у,

Рассмотрим функционирование третьего блока 1 вычислений и третьего блока 3 вывода данных.

При вычислении Yr/x на первом такте происходит загрузка третьего блока вычислений первым элементом вектора значений Х„. На втором такте выполняется суммирование по модулю два элементов х 0 и х . Результат суммирования у ° хсо в х 1 поступает на выход устройства и, кроме того, записывается в регистр 7. На третьем такте результат у у1/ с выхода регистра 7 поступает на выход устройства, при этом происходит загрузка блока вычислений значением элемента х 7 . Далее на четных ,с тактах (четвертом, шестом и восьмом) происходит формирование результатов

30

№

и

у (4).

суммирования соответственно

х(1|эх01 , у (/ x(x(S

x(t ® хп , а на нечетных (пятом,

40 седьмом и девятом) на выход устройства поступают результаты у(з у / - у и У lj У1/ соответственно.

Таким образом, на первом такте

45 происходит загрузка вычислительной ячейки, а на втором и последующих - выдача результата Yn/x3 у ( у (1) ... У((по девятый такт включительно).

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

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

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

Выходные данные Yf/q Фиг. 1

0

5

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

Фуг. I Информ. Упрабя. Вход

Фиг.З