Модуль для логических преобразований булевых функций Советский патент 1991 года по МПК G06F7/04 

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

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

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

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

Пусть система из 2П булевых функций f| (X) О 0,2м-1) переменных представлена матрицей R2n размерности 2n x 2П их векторов значений Xfi: .,

(о) (о) (о)

x2n-4 xi x0 (О 0) О)

Х2П-1..Х1 X0

R2n Xf2n-t..iXf1.Xf0h

I2n-1) (2n- X2n-1 .Xi

-1)(2n-1 X0i

Матрицу R2n зададим в системе координат X и Y, где X - координата изменения индекса I значе н1й Х|| функций на наборе

(Хо, XiXn)(i - 0,2П - 1), a Y - координата

изменения индекса j векторов значений . Тогда логические дифференциальные операторы системы R2 булевых функций в матричном виде определяются следующим образом: оператор вычисления минимума по координате X

.Urn k,(1)

(ПХ)

оператор вычисления минимума по координате Y

MIN (k R2n - ,R2nL2 2 kl(2)

(Г2Х)

оператор вычисления максимума по координате X

MAX W R2n R2nVL2 (Ч (ПХ)

оператор вычисления максимума по координате Y

(3)

0

5

0

5

0

0

5

MAX (k) R2r (Г2Х)

fo) R2nVL2h }

k

(4)

где L2 - матрица размерности 2 n x 2 , которая при г 0 (г 0) имеет верхнюю (нижнюю) диагональ, параллельную главной и отстоящую от нее на расстоянии г элементов и формируемую согласно формуле

Ф.,

L2 k - кратное повторение вычислительной процедуры А означает

)АМ при этом операции коньюнкции и дизъюнкции выполняются поэлементно. Соотношения (1 - 4) являются математическими моделями функционирования изобретения.

Из формулы (1 -4) следует, что при реализации операторов (1) и (3) вычисления по координате X сводятся к обработке столбцов матрицы R2n , а при реализации операторов (2) и (4) по координате Y - срок матрицы R2n .

Поясним особенности организации вычислительного процесса на основе математических моделей (14) на конкретном примере.

Пусть требуется вычислить двухкратный логический минимум (k - 2) по координате X с параметром г + 1 системы из восьми булевых функций fj (X) (j - 0,7), трех переменных (п -- 3):

ffo(X) X2VX2X3 fi(X) X2VXiX2X3

f2(X)XiX2

f3(X) Xi (X2 v ) f4(X)XiX2V/XiX2 fs(X) XiX2X3VXiX2 fe(X)-XiX2 XiX2X3 lf7(X)X2 Исходная матрица имеет вид:

R23

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

MINl(9 R23 R23A L23 . (X)

Выделим в процессе вычисления две итерации. В первой итерации получим:

MINR23 (х)

После выполнения второй итерации получим искомый результат:

-MINR23. (X)(X)(х)

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

Модуль (фиг. 1) содержит регистр 1, два элемента И 2 и 3. два элемента ИЛИ 4 и 5, две схемы 6 и 7 сравнения, суммирующий счетчик 8, вычитающий счетчик 9, узел 10 пересчета, три коммутатора 11-13, сдвиговый регистр 14, элемент 15 задержки, группу входов 16 задания параметра, два тактовых входа 17 и 18, вход 19 задания знака, информационный вход 20, вход 21 задания режима, выход 22.

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

Элемент ИЛИ 5 обеспечивает логический анализ операндов, поступающих на его первый и второй входы путем выполнения над ними операции дизъюнкции.

Элемент И 3 обеспечивает логический 5 анализ операндов, поступающих на входы первого по n-й, путем выполнения над ними операции конъюнкции.

Коммутатор 12 обеспечивает передачу информации с выхода элемента И 3 (режим 10 вычисления минимума) либо с выхода элемента ИЛИ 5 (режим вычисления максимума) под управлением сигнала с входа 21 задания режима.

Коммутатор 11 осуществляет передачу 15 информации на выход 22 в соответствии с табл. 2.

Модуль 23 функционирует следующим

образом. Предварительно в регистр 1 с

группы входов 16 задания параметра зано0 сится абсолютное значение параметра

г (где rЈ Z; Z, - целые числа, кроме нуля из

интервала-(2П- 1)-(2п-1), а в(п + 1)-й разряд

регистра 1 с входа 19 задания знака - О,

если п 0, и единица, если г, 0. Суммиру5 ющий счетчик 8 устанавливается в исходное

состояние (1 1), а вычитающий счетчик 9

устанавливается в начальное (нулевое) состояние (0.... 0).

Рассмотрим функционирование модуля 0 при г X). На втором входе узла 10 пересчета сигнал нулевого уровня (так как г 0).

Узел 10 пересчета генерирует последовательность сигналов на своем выходе в соответствии с табл. 1 (2 и 3 столбца). 5В первом такте суммирующий счетчик 8

переходит из состояния 1.... 1 в состояние 0.... 0. В результате по перепаду сигнала из 1: в О на первом входе узла 10 пересчета на его выходе формируется код 00, который 0 сохраняется в течение (г - 1)тактов.

В такте на выходе первой схемы 6 сравнения в результате совпадения кодов на ее входах формируется сигнал единичного уровня, поступающий на первый вход 5 элемента ИЛИ 4 и далее с его выхода на первый вход узла 10 пересчета. В результате по заднему фронту этого сигнала на выходе узла 10 пересчета формируется код 01, который сохраняется до оконча- 0 ния (2П-т Но такта.

В (2п -т )-м такте на выходе второй схемы 7 сравнения в результате совпадения кодов на ее входах формируется сигнал единичного уровня, поступающий на первый вход элемента ИЛИ 4 и далее с его выхода на первый вход узла 10 пересчета. В результате по заднему фронту этого сигнала на выходе узла 10 пересчета формируется код 10, который сохраняется с (2П - г + 1}-го такта до окончания 2п-го такта.

В каждом такте по сигналу с первого тактового на второй вход с входа 17 осуществляется сдвиг информации на один разряд вправо (в сторону старших разрядов) в сдвиговом регистре 14, через время

t 1„ ° (полтакта) в младший разряд сдвигового регистра 14 записывается элемент, поступающий с информационного входа 20. Одновременно по коду (значению г) на управляющих входах коммутатора 13 значение элемента из г -го разряда сдвигового регистра 14 подается на элемент И 3 и элемент ИЛИ 5, на вторые входы которых поступает текущий элемент обрабатываемого вектора. Результат логических преобразований в зависимости от режима поступает через коммутатор 12 и 11 на выход 22.

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

Пусть устройство реализует композицию операторов вида

MIN ( МАХ ( MAX R23)) (-4)-20 00

в соответствии с операционным графом, приведенным на фиг. 3 (п - 3). Устройство содержит три модуля для логических преобразований булевых функций. На группы входов 16.1, 16.2, и 16.3 параметра гподаются соответственно значения 3, 2 и 4, а на входы 19.1, 19.2 и 19.3 задания знака соответственно значения 0 (знак плюс) 1 и 1 (знаки минус), на входах 21.1 и 21.2 задания режима сигналы единичного уровня (режим вычисления максимума), а на входе 21.3 задания режима сигнал нулевого уровня (режим вычисления минимума). Запись значений параметров n ,TZ ,и Гз и их знаков в (п + 1)-разрядный регистр 1 стробируется сигналами с второго тактового входа 18.

Функционирование устройства начинается при поступлении сигналов с первого тактового входа 17.

В первом такте на информационный вход 20.1 первого модул я поступает значение первого элемента Х(0) век гора (0)Х(1) .. V

-

10

системы R2n(J 0,2 - 1), сопровождаемое тактовым импульсом с первого тактового входа 17. Этот элемент записывается в первый разряд сдвигового регистра 14 первого модуля. Аналогичным образом в тактах с второго по Ti 3 в сдвиговый регистр 14 первого модуля последовательно записываются значения элементов ... X т 1 вектора Xf0.

15

На четвертом (Гц + 1)-м такте на выходе 22.1 формируется значение элемента Y/0 X(0)VX(3) вектора результата YI MAXXf0.

(Э)

На тактах с пятого по (2 + 3}- и на выходе 22.1 формируются соответственно значения элементов Yi 1 ..., Y/2n 1 вектора результата YL

Кроме того, в четвертом такте (с начала функционирования устройства) значение 20 первого элемента Уг результата YI поступает на информационный вход 20.2 второго модуля. В тактах с четвертого по (2П + 3)-й на выходе 22.2 формируются значения элементов Y2 1 вектора результата

25 у2 MAXYi. В тактах с четвертого по (2п + 4)-й

(-&)

на выходе 22.3 третьего модуля формируются значения элементов Уз ..., УЗ вектора результата Y3 MIN Ya. 30(-4к)

Таким образом, вычисление Уз - MIN

НИ

(МАХ(МАХХг0.)) реализуется за (2 + 3) такта. (-2) (30

35 Одновременно по окончании 2п-го такта на выход первой вычислительной ячейки 21 поступает первый элемент вектора Xfi системы R2n, а результат вычисления

Y MIN (MAX(MAXR23)) 40(-4) (-20 0С)

системы R2n формируется за (22п + 3 акта.

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

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

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

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

модуля соединен с тактовым входом регистра, (п + 1)-й информационный вход которого соединен с входом задания знака, выход первого коммутатора является выходом модуля.

Таблица 1

Изобретение относится к цифровой вычислительной технике и может быть использовано для аппаратной поддержки вычислений в системах анализа бинарных динамических систем и синтеза цифровых автоматов. Цель изобретения - расширение функциональных возможностей за счет обработки булевых функций минимаксного типа. Устройство содержит регистр 1, два элемента И 2 и 3, два элемента ИЛИ 4 и 5, две схемы сравнения 6 и 7, суммирующий счетчик 8, вычитающий счетчик 9, узел перерасчета 10, три коммутатора 11 - 13, сдвиговый регистр 14 и элемент задержки 15. В регистр 1 заносится значение параметра Τ(Τ*98эZ

Z = 1, 2^N - 1) и его знак. В зависимости от знака параметра и режима вычисления (минимума или максимума) узел перерасчета 10 генерирует последовательность управляющих сигналов, обеспечивающих обработку булевых функций минимаксного типа. 3 ил., 2 табл.

Таблица2

«Ф

fcs

3

c

tx

un

VJ «Si

c

s 777

il J.J J Sj

«

h

14

У

1

гпт

V oei

v v о, gS

-. tV|

V

5

«м

I

«Si

JT

«M

n

VJ «Si

5a cri

tS4

Й

NS

N

y/W

y/V V A ур-аР

( %v,y, vy;,2) „0,,,/c

#ДАХ

Г J

У4УУу,

/,(7)хМ I

1 (зх)

(-2Х) Итерация 1Итервиия 2

Фиг.З

sfl.s,m

y/W/;

v,y, vy;,2) „0,,,/c;

у/г

tfLsfysJ

iy/V

Ду/Т;

A(3)

M) ИтероццяЗ