Устройство для логического дифференцирования и интегрирования булевых функций

 

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

СОЮЗ сОВЕтСНИХ

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

РЕСПУБЛИН (51)5 С Об F 7/00 15/31

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

В ЕСОЮЗНАЯ

ПНЮ,": = ЯИЕЯ6

E.: ЯО ТЕ АА их векторов значений мерности 2""2 " х,. х" е х" о х х х = х ...х >

1 аб Zn y

R „=-tx, ...,х 2

Х1 х, й"-1) (1ц ) ГОСУДАРСТВЕННЫЙ КОМИТЕТ

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

ПРИ ГННТ СССР

1 (21) 4378658/24-24 (22) 12.02.88 (46) 07.02.90. Бюл. У 5 (71) Минский радиотехнический институт (72) С,Н.Янушкевич, E.Н.Зайцева, Г.А.Кухарев и В.П.Шмерко (53) 681.327.6(088.8) (56) Авторское свидетельство СССР

У 1168925, кл. G 06 Р 7/04, 1985.

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

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

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

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

Пусть система булевых функций

f ° (х) — f .(х, х,...,х ) (j=0,2 1)п переменных представлена матрнцей раз1

„„SU, 1541592 А1

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

Матрицу R, задают в системе кот ординат х и у, где х — координата изменения индекса i значения х функции f (õ) на наборе (х„, х „,. ° °,х„), (1. = 0;2 -1), у — координата изменении индекса j вектора х ь в системе (j = 0,2"-1) . Тогда логическая производная системы К „ булевых функций в матричном виде определяется следующим образом:

1541592 а " R (Я к1 — — - - — ГЕ 81. 1()

- (T >)1k g» n

t (k}R (тх} (k! — — - -(1,,=- (R „e R „L 1, (2)

8(T27) где символ " СQ++) " обозначает операцию поэлементного сложения.по модулю два,, — матрица сдвига размерности

2 " 2", нид которой зависит от значения параметра Тc Z Z = 1,2"-1 — целые числа, и формируется по рекуррент. ному соотношению (т} (> (r-1}

2П . I- L. п

15 (k+2» pf (м}

3 R3» d Rzn д(Т,х) (" »p> д(Т, х) " 35 и д(Р} Кх" д(}R< (4) (Т у) " " (Т У) ic где ре Z (Z — множество целых положи- 40 тельных чисел).

Из свойства (3) следует определение логического интеграла

45 ((} Д(Т, х) I (k}

R d(T у) = — — — — — —, (6) » (»и k} (Ц Л(Т У) 50

Очевидно, что для вычисления kкратного логического интеграла системы R » достаточно нычислить ее (?"- с)кратную производную.

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

Из соотношений (1) и (2) следует, что алгоритм логического дифференцирования по координате х позволяет обрабатывать столбцы матрицы Б », а по

20 координате у — строки матрицы R

Предлагаемое техническое решение позволяет решить и обратную задачу: восстановить исходную систему булевых функций (матрицу К,) по результату логического дифференцирования. Назовем эту процедуру логическим интегрированием, Логический интеграл системы К »булевых функций в матричном виде определяется на основе свойства периодич-. ности логической производной:

На фиг. 1 изображена структурная схема устройства; на фиг. ? — схема блока формиронания последовательности входных данных; на фиг. 3 — схема блока вычислений„ на фиг. 4 — схема блока вывода данных.

Устройство (фиг. 1) содержит блок

1 ввода данных, M блоков 2 вычислений блок 3 вывода данных и генератор 4 импульсов, причем первый информационный нход К-го блока 2 вычислений подключен к первому выходу К+1-ro блока 2 вычислений (К = 1 ° ..M-2), а первый информационный вход И-ro блока вычислений является входом константы нуля устройства, информационные входы первой группы блока вывода данных подключены к вторым выходам блоков 2 вычислений соответственно, входы синхронизации блока 1 ввода данных и блока 3 вывода данных подключены к выходу генератора импульсов 4, выход блока 3 вывода данных является выходом устройства, информационный вход, блока 1 ввода данных .является входом устройства, входы параметра блокон 1 ввода данных и блока 3 вывода данных являются входами первого и второго параметров дифференцирования устройства соответственно, вторые информационные входы блоков 2 вычислений подключены к входам первой группы блока 1 ввода информации, третьи информационные входы блоков 2 вычислений подключены к выходам второй группы блока 1 ввода информации, адресные входы блоков 2 вычислений подключены к выходу адреса блока 1 ввода данных, Блок 1 ввода данных (фиг.2) содержит счетчик 5, элемент ИЛИ 6, регистр 7 циклического сдвига, коммутатор 8, узел 9 сравнения и регистр 10, причем первый информационный вход коммутатора является информационным входом блока, выходами первой группы которого являются выходы коммутатора 8, информационные входы группы которого подключены к выходам регистра 7 циклического сдвига, выходы которого образуют выходы второй группы блока .1. Информационный вход регистра 7 циклического сдвига подключен к выходу элемента ИЛИ 6, выходы счетчика 5 подключены к входам элемента ИЛИ 6 и первым информационным входам группы узла 9 сравнения, вторые информационные входы группы которого подключены к выходам регистра 10, образующих адресный

1541592 выход блока 1 ввода данных, а вход параметра регистра 10 является входом параметра блока 1 ввода данных, вход сброса счетчика 5 подключен к выходу узла 9 сравнения.

Блок 2 вычислений (фиг. 3) содержит первый 11 и второй 12 коммутаторы, регистр 13 и сумматор 14 по модулю два, причем первый информационный вход первого коммутатора 11 является вторым информационным входом блока 2 вычислениИ, управляющий вход первого

11 коммутатора является третьим информационным входом блока 2 вычислений, второй информационный вход первого 11 коммутатора подключен к выходу сумматора 14 по модулю два, первый информационный вход которого является первым информационным входом блока 2 вычислений, выход второго коммутатора

12 подключен к второму информационному входу сумматора 14 по модулю два и образует второй информационный выход блока 2 вычислений, вход адреса второго 12 коммутатора является входом адреса блока 2 вычислений, информационные входы второго 12 коммутатора подключены к выходам регистра 13, выход первого коммутатора 11 подключен к информационному входу регистра

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

Блок 3 вывода данных (фиг. 4) со-

35 держит счетчик 15, элемент ИЛИ 16, регистр 17 циклического сдвига, коммутатор 18, узел 19 сравнения, регистр

20, вход параметра которого является входом параметра блока 3 вывода дан- 40 ных информационные входы первой груп1 пы узла 19 сравнения годключены к выходам регистра 20, информационные входы второй группы узла 19 сравнения и входы элемента ИЛИ 16 подключены 45 к выходам счетчика 15, управляющий вход которого является входом синхронизации блока 3 вывода данных, вход сброса счетчика 15 подключен к выходу узла 19 сравнения, выход элемента

ИЛИ 16 подключен к информационному входу регистра 17 циклического сдвига, выходы которого подключены к информационным входам первой группы коммутатора 18, информационные входы второй группы коммутатора 18 образуют информационные входы блока 3 вывода данных, а выходы коммутатора 18выход блока 3 вывода информации.

Рассмотрим функционирование устройства в совокупности составляюших его компонентов. Поясним принцип его работы на конкретном примере.

Пусть необходимо выполнить трехкратное дифференцирование (вычислить трехкратную производную) матрицы, — tx),х 1. ° ° !х 3

7 о векторов значений х . системы буле-

Fj вых функций <1(x), ° ° °, <,(х), <,(х) с параметром Т = 2. Устройство для данного примера содержит четыре блока 2 вычислений.

На первых двух тактах (Т = 2) происходит загрузка регистра 13 первого блока 2 вычислений данными х,, х,, (o7 (il поступающими на первый вход коммутатора 11 (по высокому логическому уровню напряжения на управляющем входе).

На третьем и четвертом тактах аналогичным образом происходит загрузка регистра 13, второго блока 2 вычислений элементами х(," и х, по высокому логическому уровню напряжения на втором (управляющем) входе коммутатора

11. Причем на этих же тактах, а именно на третьем, в регистр 13 первого блока ? вычислений поступает сУмма вида х(," Щ х(, а на четвертом— (а! (9 x (c выхода сумматора 14 п модулю два (по низкому логическому уровню сигнала на втором, управляющем входе коммутатора 11) .

Таким образом, по окончании четвертого такта в регистре 13 первого блока 2 вычислений оказываются значения первых двух элементов y = х !69

C& x(,!H у("= х,©х, вектора у — (у у, !...у 1) результата вычисления aR з/a(2x), а в регистре 13 г. второго блока 2 вычислений значения х и х вектора х . На пятом и

fo шестом тактах происходит загрузка третьего блока 2 вычислений и вычисления в первом и втором блоках 2 вычислений, а на седьмом и восьмом тактах — загрузка четвертого вычисления в первом втором и третьем блоках 2 вычислений.

И, наконец, на девятом и десятом тактак на выходе первого блока 2 вычислений формируются соответственно результаты у(1= х" & х1г1 и у (1 = х(Я ф о о О о

® х 1, на одиннадцатом и двенадцаз JIbTGTb1 g (1 Y(9 х (4 H (г1 у „! = х (33 х на вьгходе второго

1541592 блока 2 вычислений, на тринадцатом и че- тырнадцатом — результаты у, -х,и. х, и у. х С9 х< ), на выходе третьего блока

2 вычислений и на пятнадцатом и шестнадцатом гактах — элементы у, = х, (6) (Г) (1) <т} и у, = х, — на выходе четвертого блока 2 вычислений. При этом на девятом такте можно начинать загрузку перваго блока 2 вычислений элемента- 10 ми х") вектора х матрицы R<1 и т.д.

1 Е1

Аналогичным образом можно вычислять производные по координате у с шагом

Т, однако при этом загрузка матрицы выполняется по строкам, а не по столб-15 цам.

Кроме того, подобным образом можно вычислять логические интегралы по координатам х и у с параметром Т, одна20 ко на второй вход параметра Т и третий вход параметра (К+1)Т устройства следует подавать соответственно значения 2 -Т и (2 — К+1)Т.

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

1. Устройство для логического дифференцирования и интегрирования булевых функций, содержащее генератор иМ 30 блоков вычислений, причем первый информационный вход К-ro блока вычислений подключен к первому выходу К+ 1-ro блока вычислений (К = 1...М-2), а вход константы нуля устройства является первым информационным входом М-го бло35 ка вычислений, о т л и ч а ю щ е,е— с я тем, что, с целью расширения функциональных возможностей за счет вычисления логических производных и логических интегралов систем булевых функций, в устройство введены блоки ввода и вывода данных, причем информационный вход блока ввода данных является информационным входом устрой45 ства, а выход блока вывода данных является выходом устройства, входы первого и второго параметров дифференцирования устройства являются входами параметра блоков ввода и вывода дан50 ных соответственно, выход генератора импульсов подключен к входам синхро-: низации блоков ввода и вывода данных вторые информационные входы блоков вычислений подключены к выходам первой группы блока ввода данных, а вы55 ходы второй группы этого блока подключены к третьим информационным входам блоков вычислений соответственно, адресные входы блоков вычислений подключены к выходу адреса блока ввода данных, а выходы блоков вычислени)) подключены к информационным входам блока вывода данных.

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

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

4. Устройство по п. 1, о т л и ч аю щ е е с я тем, что блок вывода данных содержит счетчик, элемент ИЛИ, регистр циклического сдвига, узел срав1541592 (k+l)f

Ябреены0 Ьи

ФАР нения, коммутатор и регистр, причем вход параметра блока является информационным входом регистра, вход синхронизации блока является входом синх5 рониэации счетчика, а информационные входы блока являются информационными входами первой группы коммутатора, информационные входы второй группы которого подключены к выходам регистра циклического сдвига, а выход является

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

Составитель А.Доброхотов

Техред M.Õoäàíè÷ Корректор A-0 РУ аР

Редакто, Козориз

Заказ 2 Тираж 569 Подписное

1 НИИПИ арственногo Ko H e a EIQ H ape eHH H QTKpbITHHM при ГКНТ СССР

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

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