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

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

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

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

Устройство содержит коммутатор 1, демультиплексор 2, операционный блок 3, группу 4 триггеров, блок 5 управления, информационный вход 6 устройства, три управляющих входа 7-9 устройства, выход 10 устройства, выход 11 коммутатора 1, выход 12 управления коммутацией, выход 13 разрешения сдвига влево, выход 14 управления

4

ас

со со

314

режимом коммутатора, ныход 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 предназначен для регламентирования работы устройства при дифференцировании матрицы по переменной X m раз и представляет собой m-разрядный двоичный суммирующий счетчик. Исходное состояние счетчика 42 - нулевое.

Счетчик 43 предназначен для регламентирования работы устройства при дифференцировании результата а(|гтЛ Лг„/ЭХ(Ип1 по переменной В 1 раз и представляет собой 1-разрядный двоичный суммирующий счетчик. Исходное состояние счетчика 43 - нулевое.

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

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

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

Регистры 50-52 являются m, l и r-разрядными регистрами соответственно. Шифратор 55 кодирует входные сигналы в соответствии с табл.1.

Таблица 1

17934

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

Таблица 2

1 ...11

1...11

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

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

i|jЈ- M. (mod 2), (1)

где R-ц - матрица размерности

2П 2П, образованная 2 векторами значений (j 0,2rt-1). булевых функций fi (X) переменных,т.е.

R „ х, - 1х, ...|х, 1

2 L iati, I I ioJ

где X, В - координаты матрицы Кгп соответственно строки и столбцы);

40

M.rv - матрица размерности

, формируемая по правилу

1 1

1 1 л

М,

1 1

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

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

v txp xijxjx0

iiii

0000 0101 1010

Эта матрица образована четырьмя булевыми функциями f:(X), где (j 0,3), которые заданы своими векторами значений .

В соответствии с (1) смешанная булева производная первого типа имеет вид

В общем виде соотношение (1) но записать следующим образом D . Гг -.1X1

J

3

ЗХ(

Ь± ГГМ Iй

ijn 2

-.cei

Hu-odl)

(2)

)

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

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

8(№lR,n -Э(ж аП кЧ

3xtm,

gx ) J

Э Rt, Rg gBie эв(

Для соотношения (2) это свойство выражается в виде формулы

3( кя Rg, 8X ml3Bltl gxim+i.k) )(з

Из соотношения (3) следует, что для матрицы R2n существует 2П производных по каждой из осей и, кроме того, при 1, m 2П - К (К 0,1,2, ...) матрица восстанавливается.

4817936

Данное свойство использовано в устройстве для восстановления исходной системы Ren векторов булевых функций Ј|(Х).Для этого необходимо систему R-ч, подвергшуюся обработке оператором дифференцирования по одной из координат X и В m и 1 раз соответственно, продифференцировать 2п-ю и 2п-1 раз соответственно.

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

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

10

15

QRs.

9(Х,В)

2

V2

2 }

(4) мож(2)

где LS - матрица сдвига размерности 2П- 2, формируемая по правилу

25

01 01

г

01

зо

Поясним соотношение (4) на примере вычисления (X,B) матрицы

35

40

45

50

55

Данный оператор также обладает свойством периодичности, которое может быть записано в виде

a RI

Э(х,в)«) 3 (х,в)

(6)

причем при г 2П К (К 0,1,2,...) матрица R,, восстанавливается. Соответственно, для восстановления исходной системы векторов Xi булевых функций fj (X) необходимо систему, подвергшуюся обработке оператором дифференцирования по (Х,В) г раз, продифференцировать по (Х,В) (2П - г) раз.

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

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

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

Первый режим позволяет по заданной системе Rg векторов значений Хij J 0,2-1) логических функций f;(X) п переменных вычислять смешанную булеву производную первого типа 3( R2h/ (е) по направлению осей координат X и В (столбцов и строк соответственно), т.е. -по направлению возрастания переменной X (X101 , Xй ,...,Х(ПЪ и переменной весов векторов X.

Второй режим позволяет по заданной системе векторов значений X ,. логических функций fj(X) п переменных вычислять смешанную булеву производную второго типа по (Х,В) вида 3(0 „/Э(Х,В) П т.е. по направлению диагонали между осями X и В. Работу устройства рассмотрим на примере реализации математической модели вида )R .,/ЭХ. Выходные параметры этой модели имеют следующие значения: г 0, in 1, 1 0.Исходная матрица

1001

R

0101 1001 0101,

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

В первом такте в сдвиговый регистр 20 и регистр 23 заносятся зна- чения элементов первого столбца Х матрицы R,M« В сдвиговом регистре ° 20 происходит сдвиг содержимого на один разряд в сторону младших разря- дов, под управлением ствола с выхода 17 разрешения сдвига вправо, и далее поразрядное суммирование по модулю два содержимого сдвигового регистра 20 и содержимого регистра 23 (в группе 21 элементов НЕРАВНОЗНАЧНОСТЬ), т.е. исходного и сдвинутого векторов. Результат (Эх, /Зх) заносится в

/ ±0 группу 4 триггеров.

Во втором также в сдвиговый регистр 20 и в регистр 23 заносятся значения элементов второго вектора X, , матрицы Rni и далее повторяются процедуры, аналогичные процедурам первого такта.

После завершения последнего такта результат 3R-г/ЭХ записывается в группу 4 триггеров.

Рассмотрим реализацию математической модели вида 9 R, /9(Х,В) . Входные параметры этой модели имеют следующие значения: ,, 1 0.

Исходная матрица

1 О О Г

0

5

0

1ог

0101 1001 0101

по столбцам подается на информационный вход операционного блока 3. В первом такте на регистр 23 заносятся

значения элементов вектора X/ , а в сдвиговый регистр 20 - значения элементов вектора Х.Ј , которые затем сдвигаются на один разряд вправо в сторону разрядов. Группа 21 элементов

НЕРАВНОЗНАЧНОСТЬ выполняет операцию сложения по модулю два содержимых сдвигового регистра 20 и регистра 23, а результат 3 X/ /9(Х,В) записывается в группу 4 триггеров.

Во втором такте происходит сдвиг содержимого сдвигового регистра 20 в сторону старших разрядов под управлением сигнала с выхода 13 разрешения сдвига влево, далее происходит запись

результата в регистр 23, а затем в сдвиговый регистр 20 записывается

следующий вектор X и происходит

Ј

сдвиг на один разряд вправо в сторону младших векторов Х.. Группа 21

осущест

элементов НЕРАВНОЗНАЧНОСТЬ вляет операцию сложения по модулю два содержимого сдвигового регистра 20 и регистра 23, и результат вычисления записывается в группу 4 триггеров .

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

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

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

В первом режиме реализуется математическая модель (2) вида КV /ЗХ ЭВ При этом можно выделить два этапа.

На первом этапе первого режима устройство реализует вычисления вида Кг„/3х(т.

В начальных тактах на второй и третий управляющие входы 8 и 9 устройства подаются значения параметров m и 1 соответственно. В операционный блок 3 с информационного входа 6 через коммутатор 1 записывается вектор - столбец ХЈ (j 1,2 матрицы Rlh хь„( | ix.fj Xio(

осупествляв соответствии с математической моделью вида 3lm1 ХЈ. /ЭХ1™ .

Под управлением сигнала низкого уровня с выхода 18 разрешения запис полученный в операционном блоке 3 результат ( ХЈ /8X(w1 ) записывается в группу 4 триггеров.

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

3ie)(3(m1Rf/axim))/3BtE).

На этапе по высокому логическому уровню сигнала с выхода 18 разрешения записи (признак считывания информации по строкам) результат вычисления первого этапа дифференцирования Э1Гй1 Ру,/ЭХ(т) из группы 4 триггеров через демультиплексор 2 и коммутатор 1 (под управлением сигнала с выхода 12 управления коммутацией) передается в операционный бло 3. Операционный блок 3 выполняет обработки матрицы 3(ml RJh/9X(m) в соответствии с математической моделью gU) (3(i fc/ax(m|)/9BtM . Результат в виде матрицы (т)Э В(е) записывается в группу 4 триггеров и далее через демультиплексор 2 поступает на выход 10 устройства.

вектора X, , ется обработка вектора

начиная с

)

10

10

15

20

25

30

5

0

5

0

5

поступает 2 на выход 10

Таким образом, в первом режиме устройство реализует математическую модель вида R7n/9X(m13 B(e.J

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

3U) va() начальных тактах на первый управляющий вход 7 устройства подается значение параметра г. В операционный блок 3 с информационного входа 6 через коммутатор 1 записывается вектор Xfj 0 1,2) матрицы R1njxiih i|,,. . . . IX.J начиная с вектора Х$.0Операционным блоком 3 выполняется обработка матрицы R .п (каждого из ее векторов ХЈ ) в соответствии с математической моделью (5) вида дКг„/3(Х,В)(ЭХ{)/3(Х,В). Результат обработки поступает на группу 4 триггеров. Полученный результат через демультиплексор 2 и коммутатор 1 поступает в операционный блок 3 (по векторам 9 X-fj /9(Х,В) г - 1 раз.После обработки резтаьтат в виде мат- рицы Э -Кг„/Э(Х,В)М через демультиплексор устройства.

Таким образом, во втором режиме устройство реализует математическую модель вида RIW /Э(Х,В)(Ц).

Для восстановления исходной системы по результату дифференцирования а(И14е) ( первого режима достаточно подать на второй и третий управляющие входы 8 и 9 устройства параметры (2n-m) и (2 -() соответственно.В результате обработки в соответствии с математической моделью (2) и свойством (3) исходная матрица восстановится. Аналогично для восстановления исходной системы по результату дифференцирования 3 Rnn/ /9(Х,В) г второго режима необходимо на первый управляющий вход 7 устрой- ства подать параметр (2 -г), и в результате обработки в соответствии с математической моделью (5) и свойством (6) исходная матрица восстановится. Формула изобретения

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

ft

. i

12

f3

к

15

8

,r

,m

Л

Ik

4

10

f6

П

18

k 1 /.

г

1 ™ф

eemvi

Дирффрциробакив /юх Дифференцирование ПО в т раз {первый зтап раёогга1} t раз (второй j/яа/ paffoatt)

ц4.-Ц

ИЦII-

Счетчиц IS 8 состоянии

Обработка 2я Векторов

(столбцов}

Выход 15

Выход 16 Выход 17

дыхов /J Вы ход 12

S сторону старших р#зря

U U W

-th

4h

Обра&отка

г-:-п- g-R---r-tt--«г

5 Суммирование UMWCU о олок памяти

I

Признак записи 8 блок памяти

$ПЈкmoffpff один роз

ЦСТq

Обработка 2Л НекшороЯ {М)ра±

----- --.-. -п, i -i--mi l. -..3

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

-Ґ . in .1., Ir..i.j. ...-...л.j..j -гт-г-- л-ri-1--

Дифференцира8а#Ј/е Xg/i no IX.SJF раз

фие.5°

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

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

-

Обработка 2лстр9К

Фив

-н «

-th

4h

«г

и

Ц

а

-