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

 

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

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

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

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

РЕСПУБЛИК (19) (1 1 у (si)s G 06 F 7/04

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

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

ПРИ ГК1 Г СССР

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

1б

18

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4693373/24 (22) 19.05.89 (46) 30.07.91. Бал. М 28 (71) Минский радиотехнический институт (72) С.Н, Янушкевич, А.А, Морозова, Г.А. Кухарев и В.П. Шмерко (53) 681.3 (088.8) (56) Авторское свидетельство СССР

hL 1277089, кл. G 06 F 7/04, 1985.

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

hL 1481793, кл. 6 06 F 7/00, 1987. (54) МОДУЛЬ ДЛЯ ЛОГИЧЕСКИХ ПРЕОБРАЗОВАНИЙ БУЛЕВЫХ ФУНКЦИИ (57) Изобретение относится к цифровой вычислительной технике и может быть и1польэовано для аппаратной поддержки вычислений в системах анализа бинарных динамических систем и синтеза цифровых автоматов. Цель изобретения — расширение функциональных возможностей за счет обработки булевых функций минимаксного типа. Устройство содержит регистр 1, два элемента И 2 и 3, два элемента о

О

Ql

1667050 (о) (о) (о)

X Z" — ).".X1 Хо (1) () ()

xz — 1" х1 хо

-Ъ вЂ”.м

RZ (Х(2 — Г...:Х1 Xf())»

| (2 — 1 1 (2 -- 1) (2 — ) х zп — 1..х1 хо

30 (2) ИЛИ 4, 5, две схемы сравнения 6 и 7, суммирующий счетчик 8, вычитающий счетчик 9, узел пересчета 10, три коммутатора 11 — 13, сдвиговый регистр 14 и элемент задержки

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

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

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

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

Пусть система из 2" булевых функции 20

11 (X} 11 = 0,2 -1) переменных представлена матрицей Rz >азмерности 2" х 2" их векторов значений Мц:

Матрицу Р2" зададим в системе координат X и У, где Х -- координата изменения индекса l значений Х) функций на наборе 35 (X0, X1, ..., Хп) (I == 0,2" -1), à Y — координата изменения индекса ) векторов значений З г).

Тогда логические дифференциальные операторы системы Rz" булевых функций в матричном виде определяются следующим образом: оператор вычисления минимума по координате X (Г1) м)м ) Рр" =(Р2"Л(П )("), (1) (АХ) оператор вычисления минимума по координате Y

М)(у) у Rz =- (Р2 у Р2 (-2 ) (zx)

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

MAX Rz" =(Р2"VLz" )(), (3) (т1Х) оператор вычисления максимума по координате Y

МАХ Rz" =(Р2"Viz" )(), (4) (rzx)

Ж где Lz — матрица размерности 2 х 2, которая при т> 0 (t< О) имеет верхнюю (нижнюю) диагональ, параллельную главной и отстоящую от нее на расстоянии т элементов и формир емую согласно формуле, л (1 2т,— ) (1.1)

Й f +1)

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

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

Rzn

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

fo(X) = Xz Y ÕzÕ3

f1(X) = Х2УХ1Х2хз

1г(Х) = X1Xz

fa(X) -- Х1 (Х2 Х2хз)

11(Х) = X1Xz VXiXz

f5(X) =- X1XzX3V Х1Х2

1г(Х) =- X1Xz i X1XzX3

f7(X) =- Xz

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

1667050

Rz3 =

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

М! ИЯ В23 (Rz h Lz Rz ) (Х)

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

М з (х)

Ма(Ъ2 = (х)

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

+s)

Мщ(%2з = мав зн 2" мвя2з (х) (х) (х)

На фиг. 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 задания параметра зано20 сится абсолютное значение параметра т(где т 6 Z; Z, — целые числа, кроме нуля из интервала -(2"-1) — (2" -1), а в(п+ 1) — и разряд регистра 1 с входа 19 задания знака — "О", если т > О, и единица, если < О. Суммиру25 ющий счетчик 8 устанавливается в исходное состояние (1..... 1), а вычитающий счетчик 9 устанавливается в начальное (нулевое) состояние (О.... О).

Рассмотрим функционирование модуля

30 при r . О. На втором входе узла 10 пересчета сигнал нулевого уровня (так как t > О).

Узел 10 пересчета генерирует последовательность сигналов на своем выходе в соответствии с табл, 1 (2 и 3 столбца).

35 В первом такте суммирующий счетчик 8 переходит из состояния 1.... 1 в состояние

О..., О. В результате по перепаду сигнала из

"1:" а ""О" на первом входе узла 10 пересчета на его выходе формируется код 00, который

40 сохраняется в течение (т- 1) тактов.

В r-м такте на выходе первой схемы 6 сравнения в результате совпадения кодов на ее входах формируется сигнал единичного уровня, поступающий на первый вход

45 элемента ИЛИ 4 и далее с его выхода на первый вход узла 10 пересчета. В результате по заднему фронту этого сигнала на выходе узла 10 пересчета формируется код 01, который сохраняется до оконча50 ния (2" - г) — го такта, 1667050

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

10, который сохраняется с (2" - r+ 1)-ro такта до окончания 2"-го такта, В каждом такте по сигналу с первого тактового на второй вход с входа 17 осуществляется сдвиг информации на один разряд вправо (в сторону старших разрядов) в сдвиговом регистре 14, через время

t1 tO (полтакта) в младший разряд сдви2 гового регистра 14 записывается элемент, поступающий с информационного входа 20.

Одновременно по коду (значению т) на управляющих входах коммутатора 13 значение элемента из т — Io разряда сдвигового регистра 14 подается на элемент И 3 и элемент ИЛИ 5, на вторые входы которых поступает текущий элемент обрабатываемого вектора. Результат логических преобразований в. зависимости от режима поступает через коммутатор 12 и 11 на выход 22.

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

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

MIN (MAX (МАХ Rg1 ) ) () (— >) СИ в соответствии с операционным графом, приведенным на фиг. 3 (n =- 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 задания режима сигнал нулевого уровня (режим вычисления минимума). Запись значений параметров r1,т,и тз и их знаков в (п

+ 1) — разрядный регистр 1 стробируется сигналами с второго тактового входа 18, Функционирование устройства начинается при поступлении сигналов с первого тактового входа 17.

8 первом такте на информационный вход

20.1 первого модуля поступает значение перво2"— го элемента Х вектора Xrо(Х X ...Õ())) 45

5

40 системы В2"(j = 0,2" - 1), сопровождаемое тактовым импульсом с первого тактового входа 17, Этот элемент записывается в первый разряд сдвигового регистра 14 первого модуля, Аналогичным образом в тактах с второго по t1 = 3 в сдвиговый регистр 14 первого модуля последовательно записываются значения элементов Х .„Х вектора Х1О.

На четвертом (tg + 1) — м такте на выходе (о

10) (3)

22.1 формируется значение элемента У1(= Х УХ вектора результата Y1 - МАХХ . (Зс)

На тактах с пятого по (2" + 3)- и на выходе

22.1 формируются соответственно значения элементов У1 „„Y1 " вектора результата У1.

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

Yz = МАХУ1. B тактах с четвертого по(2" + 4) — и (— >) на выходе 22,3 третьего модуля фоомиоуются значения элементов Уз, ..., Уз " вектора результата Уз = MIN Уг. (— 4к)

Таим образом, вычисление Уз = MIN (— 4() (МАХ(МАХХг,.)) реализуется за (2" + 3) такта. (- ) (>)

Одновременно по окончании 2" — го такта на выход первой вычислительной ячейки 21 поступает первый элемент вектора Хг1 системы Rz", а результат вычисления

Y = MIN (MAX(MAXRgз)) (— 4() (— 2() (3() системы Rz" формируется эа (22" +3 )такта, Формула изобретения

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

1667050

Таблица1

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

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

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

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

1667050

1б67050 (gJ (О (0) (0) (д/ (О) (7) Составитель В. Сорокин

Редактор О. Спесивых Техред M.Ìîðãåíòàë Корректор О. Кравцова

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

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

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

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

3 =IN X у (5X) Фтерпаия f

У =Ю/УУ

t- x) ИшграииИ