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

 

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

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

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

РЕСПУБЛИК (gg 4 G 06 F 15/31

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

OflHCAHHE ИЭОБРКт ниЯ „-. -,;: - . =, К А BTOPCHOMY СВИДЕТЕЛЬСТВУ

Ф 1 (21) 4315768/24-24 (22) 12. 10. 87 (46) 23. 05. 89. Бюл. ¹ 19 (71) Минский радиотехнический институт (72) В.М. Дашенков, Д. В. Кузьмицкий, В.Д. Тупиков, В.П. Лмерко и С.Н. Янушкевич (53) 681.3 (088.8) (56) Авторское свидетельство СССР

¹ 1128263, кл. G 06 F 15/31, 1982.

Авторское свидетельство СССР № 1277089, кл . G 06 F 7/04, 1985. (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ БУЛЕВЫХ ПРОИЗВОДНЫХ (57) Изобретение относится к автоматике и вычислительной технике и пред. назначено для аппаратной поддержки вычислений в системах анализа и синтеза цифровых автоматов, сжатия данных, синтеза топологии БИС, обраИзобретение относится к автоматике и вычислительной технике и предназначено для аппаратной поддержки вычислений в системах анализа и синтеза цифровых автоматов, сжатия данных,- синтеза топологии БИС, обработки изображений.

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

На фиг. 1 изображена блок-схема ус трой ст ва для вычисле ни я булевых производных, на фиг, 2 — блок-схема операционного блока; на фиг.3 — ва„„SU„„1481793 А 1

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

Устройство содержит коммутатор 1, демультиплексор 2, операционный блок

3, группу 4 триггеров, блок 5 управления, информационный вход 6 устройства, три управляюших входа 7-9 устройства, выход 10 устройства, выход

11 коммутатора 1, выход 12 управления коммутацией, выход 13 разрешения сдвига влево, выход 14 управления

1481793

Та бли ца 2

Сигналы на входе шифратора 56

1 0

Сигналы на выходе шифратора 56 .

0...00

0...01

О... 10

0....00

0....00

0....10

1...11

1...11

25 где R

35 где Х, Вь

¹0

1 1

1 1

° °

1 1

Таблица 1

Сигналы на входе шифратора 55

Сигналы на выходе шифратора 55

1 1 1 1

01 01

1 0 1 0

QO

01

01

10 режимом коммутатора, выход" 15 разрешения записи в сдвиговый регистр, выход 16 разрешения записи в регистр, выход 17 разрешения сдвига вправо, выход 18 разрешения записи. Операционный блок 3 содержит коммутатор

19, сдвиговый регистр 20, группу

21 элементов НЕРАВНОЗНАЧНОСТЬ, демультиплексор 22, регистр 23, выход

24 блока, элементы ЗАПРЕТ 25 и 26, элементы И 27-35, элементы ИЛИ 36-41, счетчики 42-46, схемы 47-49 сравнения, регистры 50-52, триггеры 53 и 54, дешифраторы 55 и 56, генератор

57 импульсов, элементы 58-61 задержки.

Счетчик 42 предназначен для регламентирования работы устройства при дифференцировании матрицы R по пеC. ременной Х m раэ и предсТавляет собой m-разрядный двоичный суммирующий счетчик. Исходное состояние счетчика 4 2 — нул евое.

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

8 1 К „/ЭХ 1 по переменной В 1 раз и представляет собой 1-разрядный двоичный суммирующий счетчик. Исходное состояние счетчика 43 — нулевое.

Счетчик 44 предназначен для регламентирования работы устройства при дифференцировании матрицы 2. по переменным (Х,В) r раз и представляет собой r-разрядный двоичный суммирующий счетчик. Исходное состояние счетчика 44 — нулевое.

Счетчик 45 — двухразрядный двоичный суммирующий счетчик. Исходное состояние счетчика 45 — нулевое.

Счетчик 46 — 2 -разрядный двоичный суммирующий счетчик. Исходное состояние счетчика 46 — нулевое.

Регистры 50-52 являются ш 1 и

r-разрядными регистрами соответственно. Нифратор 55 кодирует входные сигналы в соответствии с табл.1.

Шифратор 56 кодирует входные сигналы в соответствии с табл.2.

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

К „ 1 1 > (mod 2}> (1) матрица размерности

2 2, образованная 2 векторами ввачевий Х (j 0,2 -1); булевых функций Г (Х) переменных,т.е. координаты матрицы R2n соответственно строки и

1 столбцы); матрица размерности

2 й2 „ формируемая по правилу

Поясним соотношение (1) на конкретном примере. Пусть и = 2 (булевые функции двух переменных) и матрица Кр задана в виде

5 1481793 6

Эта матрица образована четырьмя Данное свойство использовано в

I булевыми функциями f (Х), где (j устройстве для восстановления исход0,3), которые задайы своими векто- ной системы R (Х) .Для этого необходимо

5. систему К<«, подвергшуюся обработке

В соответствии с (1) смешанная оператороМ диффервнцирова а я по одбулева производная первого типа име- ной из координат X u B m a 1 pas ет вид соответственно, продифференцировать .

2"-m н 2"-1 раз соответственно.

Математическая модель (2) реалиг г2 «2 зуется устройством в первом режиме работы.

Смешанная булева производная вто1 1.

1 1

1 !

1 1 1 1

0101

1010

1 1

1 1

0111

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

В общем виде соотношение (1) можно записать следующим образом где L )4 — матрица сдвига ра змериости формируемая по правилу (2)И) «М «)1

"1) 1г

01

) где операции в квадратных скобках повторяются ш и 1 раз соответственно. а

° °

30

Поясним соотношение (4) на примере вычисления 8R " /З(Х,В) матрицы

1 1 1

О1 01

1010

B соответствии с (4) получим

40 RR) - R R, Ю L Ra к,л ь, л а(в1 (™1

R2«g

) 11101

000 01

101 01

010 0

3Х() ЯХ

0000 01

45 0101 01

1 О! 0 О уЕ) В „ale г" к) Для соотношения (2) это свойство выражается в виде формулы

1 1 1 1

001 0

1010

50 le+)+ z к) .(3,) Эх г "1 ВИ

И общем виде соотношение (4) можно записать следующим образом

Из соотношения (3) следует, что

4) для матрицы Р г)) существует 2 производных по каждой из осей и, кроме того, при 1, m = 2" — К (К = 0,1,2, ...) матрица Р«) восстанавливается. «iR „М

4()Д«т ((л(л) Lp Rg" LL 3 . (Л) Выражение (2) может быть использовано для вычисления смешанной булевой производной первого типа любого порядка по координатам Х и В.

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

)) 20 Ь )(Е\, „Ел„L „(4)

g(q B) а"

1481793!

О элементов НЕРАВНОЗНАЧНОСТЬ осуществляет операцию сложения по модулю два с одержимог о сдвигов or о реги стра

20 и регистра 23, и результат вычисления записывается в группу 4 триггеров.

В четвертом такте в группу 4 триггеров записывается вектор Х

Таким образом, в группе 4 триггер ров формируется результат дифференцирования (> Р > / Э(Х,В).

Теперь рассмотрим работу устройства н общем, выделив два режима.

В первом режиме реализуется математическая модель (2) вида Э(Р, «/ («>1, () 2

/3X - ЭВ . При этом можно выделить два этапа.

На первом этапе первого режима устройство реализует вычисления вида 31 ) К«/ЗХ™

В начальиых тактах на второй и третий управляющие входы 8 и 9 устройства подаются значения параметров m и 1 соответственно, В операционный блок 3 с информационного входа 6 через коммутатор 1 записывается вектор — столбец Х((j = 1, 2")

1 матрицы К„« = tÕ « (.. °

Я (Х /!(Х (Под управлением сигнала низкого уровня с выхода 18 разрешения записи полученный в операционном блоке 3 результат ((((Х ; /ОХ() записынается в группу 4 триггеров, На втором этапе первого режима устройство реализует вычисления вида а "(а К,„ДХ ")/ав(", На этапе по высокому логическому уровню сигнала с выхода 18 разрешения записи (признак считынания информации по строкам) результат вычисления первого этапа дифференцирования g(1 Р «/дХ из группы 4 триггеров через демультиплексор 2 и коммутатор 1 (под управлением сигнала с выхода 12 управления коммутацией) передается в операционный блок

3. Операционный блок 3 выполняет обработки матрицы (I(Р „ /дХ(в соответствии с математической моделью д (el (д(R „/д Х() /дВ((! . Результат в виде риц Э(";»„/àÕ(Э В(! записывается в группу 4 триггеров и далее через демультиплексор 2 поступает на выход 10 устройства.

Таким образом, в первом режиме устройство реализует математическую модель вида Д (! !» /ОХ(«! Э (P)

Во втором режиме реализуется математическая модель (5) вида

3""! К,„/д (X,В)(", В начальных тактах на первый управляющий вход 7 устройства подается значение параметра r. В операционный

5

10 блок 3 с информационного входа 6 через коммутатор 1 записывается вектор Х(; (j=1,2") матрицы К «(Х „, „, ... t X., I Х начиная с вектора

Операционным блоком 3 выполняется обработка матрицы К „ (каждого из ее векторов Х ) в соответствии с

J математической моделью (5) вида (IR«/3(X,B) (3Xg; /З(Х,В). Результат

20 обработки поступает на группу 4 триггеров. Полученный результат через демультиплексор 2 и коммутатор 1 поступает в операционный блок 3 (по векторам (> Х /Д (Х,В) r — 1 раз. Пос25 ле обработки результат н виде матрицы Э (К „ /д(Х,В) " поступает через демультиплексор 2 на выход 10 устройства.

Таким образом, во втором режиме устройство реализует математическую модель вида 3("! R « /Э(Х,В)(, Для восстановления исходной системы по результату дифференцирования Я (K<« /3 X (1 оо В ((! первого ре жима достаточно подать на второй и третий управляющие входы 8 и 9 устройства параметры (2"-m) и (2 -f) соответственно.В результате обработки в соответствии с математической моделью (2) и

40 свойством (3) исходная матрица R>n

- восстановится. Аналогично дпя носстановления исходной системы по результату дифференцирования 3 ("1 Р „/

/(1(Х,В) " второго режима необходимо

45 на первый Управляюп(ий вход 7 УстРойства подать параметр (2 -r), и н

« результате обработки в соответствии с математической моделью (5) и свойством (6) исходная матрица К > вос2 становится.

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

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

12

I1 1481 7

O производных, оно содержит коммутатор, операционный блок и блок управления, причем информационный вход устройства соединен с первым информацион5 ным входом коммутатора, второй информационный вход которого соединен с первым выходом демультиплексора, а выход соединен с;информационным входом операцйоиного блока, выход которого соединен с информационным входом триггеров группы, первый,второй и третий управляющие входы устройства соединены соответственно с первым, вторым и третьим входами 15 блока управления, выход управления коммутацией которого соединен с управляющими входами коммутатора и демультиплексора, выход разрешения сдвига влево, выход управления режи- 2ц мом коммутатора, выход разрешения записи в сдвиговый регистр, выход разрешения записи в регистр и выход разрешения сдвига вправо соединены соответственно с первым, вторым, треть- 25 им, четвертым и пятым управляющими входами операционного блока, выход разрешения записи соединен с управляющим входом триггеров группы,второй выход демультиплексора является Зп выходом устройства.

2. Устройство IIo II 1, о T Jl H ч а ю щ е е с я тем, что операционный блок содержит коммутатор, сдвиговый регистр, регистр, группу элементов НЕРАВНОЗНАЧНОСТЬ,демультиплексор, причем информационный вход операционного блока соединен с первым информационным входом коммутатора, второй информационный вход которого соединен с первым выходом демультиплексора, а выход соединен с информационным входом сдвигового регистра, выход которого соединен с первым входом элементов НЕРАВНОЗНАЧНОСТЬ группы и информационным входом регистра, выход которого соединен с входом элементов НЕРАВНОЗНАЧНОСТЬ группы, выход которой соединен с входом демультиплексора, первый, второй, третий четвертый и пятый управляющие входы операционного блока соединены соответственно с первым входом разрешения сдвига сдвигового регистра, с управляющим входом коммутатора и демультнплексора, с управляющим входом сдвигового регистра, с управляющим входом регистра, с вторым входом разрешения сдвига сдвигового регистра, второй выход демультиплексора является выходом операционного блока.

1ч81 793

1481 793 врещиродакие

Жив 1ß дыюУ 17

АчИЦ

ЙиИИ

Выход g

8ыхИ 9

8мхоФ17 дихюУ ц дихИ 12

Редактор В. Данко

Заказ 2692!51 Тираж 669 Подписное

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

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

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

BbNdlb длока удРИлЮия

АиюУм Апйа у рИмнн1 5

Составитель В. Сорокин

Техред М.Ходанич КорректорВ, Гирняк