Устройство для логического дифференцирования и интегрирования булевых функций Советский патент 1990 года по МПК G06F17/13 G06F7/00 

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

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

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

Пусть система булевых функций f.(x) - f (х„ хг,...,хп) (,2n-1)n переменных представлена матрицей размерности векторов значений х,

fj

К

х

г I

ll 0

Матрицу Rtn

задают в системе ко- где х - координата изординат х и у,

менения индекса i значения xfl) функции f, (х) на наборе (х0, х.,,...,хп), (i 0,2 -1), у - координата изменения индекса j вектора х о в системе (j 0,2п-1). Тогда логическая производная системы R.n булевых функций в матричном виде определяется следующим образом:

i(V RJLl - FR 0T(Tl .R 1

Хт,х) LR2..0V кг„ j

W,

(1)

r

CR

, D т (тг)-,СМ гп® 2n 1

(2) 5

где символ © обозначает операцию поэлементного сложения по модулю два4, Ьг„ - матрица сдвига размерности 2 п х 2П, вид которой зависит от значе- ния параметра Т€ Zy Z 1,2h-1 - целые числа, и формируется по рекуррентному соотношению

(т)

1 2

Ы (T-1J

V г

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

Логический интеграл системы

3

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

--.Ј

з(т7хП ;

амИг

(3)

) Кг„

jj%2«

a(T4y) э(т1У)й

(4)

где ре Z (Z - множество целых положи- 40 тельных чисел).

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

U1

Г R d(Tx).«

) R nd(T,x) -, (5)

noa(T1x)v

i Vd(Tiy,4 - -f--kl f ,

(kl3(T,y)

(6)

Очевидно, что для вычисления k- кратного логического интеграла системы RI(I достаточно вычислить ее ( кратную производную.55

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

5

° 15

20

25

30

35

40

«

50

-55

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

Устройство (фиг. 1) содержит блок 1 ввода данных, М блоков 2 вычислений блок 3 вывода данных и генератор 4 импульсов, причем первый информационный вход К-го блока 2 вычислений подключен к первому выходу К+1-го блока 2 вычислений (К 1...М-2), а первый информационный вход М-го блока вычислений является входом константы нуля устройства, информационные входы первой группы блока вывода данных подключены к вторым выходам блоков 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 циклического сдвига подключен к выходу элемента1 ИЛИ 6, выходы счетчика 5 подключены к входам элемента ИЛИ 6 к первым информационным входам группы узла 9 сравнения, вторые информационные входы группы которого подключены к выходам регистра 10, образующих адресный

5154

выход блока 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) содержит счетчик 15, элемент ИЛИ 16, регистр 17 циклического сдвига, коммутатор 18, узел 19 сравнения, регистр 20, вход параметра которого является входом параметра блока 3 вывода данных (информационные входы первой грул- пы узла 19 сравнения подключены к выходам регистра 20, информационные входы второй группы узла 19 сравнения и входы элемента ИЛИ 16 подключены к выходам счетчика 15, управляющий вход которого является входом синхронизации блока 3 вывода данных, вход сброса счетчика 15 подключен к выходу узла 19 сравнения, выход элемента ИЛИ 16 подключен к информационному входу регистра 17 циклического сдви-

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

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

Пусть необходимо выполнить трехкратное дифференцирование (вычислить трехкратную производную) матрицы

to

R

з I г 1. . | х г

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

На первых двух тактах (Т 2) происходит загрузка регистра 13 первого

(0) VO)

блока 2 вычислений данными х

о

5

5

0

5

0

5

0

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

Ы

и х

(3)

р .... 0 по высокому

логическому уровню напряжения на втором (управляющем) входе коммутатора 11. Причем на этих же тактах, а именно на третьем, в регистр 13 первого блока 2 вычислений поступает сумма вида х(° © x(cf a на четвертом - х(1) © х 03 с выхода сумматора 14 по модулю два (по низкому логическому уровню сигнала на втором, управляющем входе коммутатора 11).

Таким образом, по окончании четвертого такта в регистре 13 первого блока 2 вычислений оказываются значения первых двух элементов у х(° ® & х(0г) и у У х(01 © х Г0М вектора у 0 У о° у д1 . . .у д1 1 результата вычисления зКгз/э(2х), а в регистре 13 второго блока 2 вычислений значения и х о вектора Хг На пятом я шестом тактах происходит загрузка третьего блока 2 вычислений и вычисления в первом и втором блоках 2 вычислений, а на седьмом и восьмом тактах - загрузка четвертого вычисления в первом, втором и третьем блоках 2 вычислений. И, наконец, на девятом и десятом так- так на выходе первого блока 2 вычис- , лений формируются соответственно результаты у(0 х(о1 в х(а и у(У О х((

v(o; (0| лч „(2

у о - х & х0 « у о „ на одиннадцатом и двенадцатом - результаты у „Uj ,rui а v (SI °

ч|

х

в

х(и

- х

ф х

на выходе второго

блока 2 вычислений, на тринадцатом и четырнадцатом - результаты у I - х(0 , на выходе третьего блока

2 вычислений и на пятнадцатом и шест- г

.(.D - „(О э

надцатом тактах - элементы у

х

и у о7 x(J - на выходе четвертого блока 2 вычислений. При этом на девятом такте можно начинать загрузку первого блока 2 вычислений элемента- 10 ми х (( вектора х матрицы и т.д.

Аналогичным образом можно вычислять производные по координате у с шагом Т, однако при этом загрузка матрицы выполняется по строкам, а не по столб-/5

цам.

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

20

25

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

35

40

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

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

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

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

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

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

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

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

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

Информ.бход

ЛОресный быход Фиг. 2

Фиг. 3 Адресный (з)

41

15

16

сдби

Л/Г

t l/ f

l

/v

/

Bxobrjpg мет п

Я7

1

Редакто.козориз

Фиг4

Составитель А.Доброхотов Техред М.Ходанич

%

n

18

выход

Л Л 7

r/;

«

Ннфорн. бход

Корректор А.Обручар