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

VI ч XI

со ю

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

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

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

Наиболее близким к изобретению по выполняемым функциям и технической сущности (является устройство, содержащее регистр, п ячеек (п - количество переменных булевой функции f(X)) с соответствующими связями, причем ячейка состоит из двух мультиплексоров (коммутаторов), двух элементов И, двух элементов ИЛИ, элемента НЕРАВНОЗНАЧНОСТЬ (сумматора по модулю два). Известные устройства реализуют одну и ту же математическую модель.

Недостатки этих устройств заключаются в следующем: устройства не позволяют вычислять булевы дифференциалы, а в лучшем случае обеспечивают вычисление составных частей булевых дифференциалов, которые представляют собой булевы производные по мастным переменным; нетехнологичны в изготовлении из-за неоднородности объекта по структуре, что вызывает трудности при изготовлении на современной технологической базе сверхбольших интегральных схем; не ориентированы на конвейерные принципы обработки информации, позволяющие одновременно вычислять булевы производные по различным переменным,

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

Предлагаемое техническое решение ус0 траняет перечисленные недостатки.

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

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

0 функции f(X)), введены (2П - п - 1) вычисли- тельных ячеек, объединенных в п групп по 2 (I 1,п) вычислительные ячейки в каждой, и элемент задержки, причем информационный вход устройства соединен с

5 первым и вторым информационный входами первой вычислительной ячейки n-й группы, первый тактовый вход которой соединен с выходом элемента задержки, вход которого соединен с вторым тактовым входом пер0 вой вычислительной ячейки n-й группы и тактовым входом устройства, первый выход первой вычислительной ячейки m-й группы (т 2,п)соединен с первым и вторым информационными входами первой вычислитель5 ной ячейки (т-1)-й группы, второй выход первой вычислительной ячейки m-й группы соединен с первым информационным входом второй вычислительной ячейки m-й группы, третий выход k-й вычислительной

0 ячейки (к 2,) v-й группы (v 3,п) соединен с первым информационным входом (к+1)-й вычислительной ячейки v-й группы, вход задания режима первой вычислитель- ной ячейки р-й группы (р 1,п) соединен с

5 входом логического нуля устройства, входы задания режима всех вычислительных ячеек, кроме первой, m-й группы соединены с входом логической единицы устройства, четвертый выход и-й вычислительной ячей0 ки (и 1. ) m-й группы соединен с первым тактовым входом (иМ)-й вычислительной ячейки m-й группы, пятый и шестой выходы первой вычислительной ячейки m-й группы соединены соответст5 венно с первым и вторым тактовыми входами первой вычислительной ячейки (т-+1)-й группы, седьмой выход и-й вычислительной ячейки m-й группы соединен с вторым тактовым входом (и- 1)-й вычислительной ячейки m-й группы BOCLмой выход (и+1)-й вычислительной ячейки

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

2

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

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

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

Полный булев дифференциал функции алгебры логики f(xi, Х2..... xn) n переменных определяется соотношением (Бохманн Д., Постхоф X, Двоичные динамические системы.- М.: Энергоатомиздат, 1986)

df(X) f(X)©f(X©dX).(1)

dX) f(xi© dxi. X2©dx2xnЈ

dxn),

dxi, dx2dxnG(0,1) - булевы-дифференциалы переменных XL X2 xn, описывающие изменения соответствующих переменных (при изменении значения переменной xi ее булев дифференциал dx-, 1, при неизменном значении переменной xi ее булев дифференциал dxi 0).

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

d ) ),

dX © GX (mod2).

(2)

2

meXdx ... 2 x 1, составленный и;

вектор размерности из векторов значений

X (векторов истинности) булевой функции f(X) вида X х(0) х(1)... х()т размерностей 2П х 1; т - символ транспортирования; G - матрица размерности 22n x 2П, состоящая из 2 подматриц G размерности 2П х 2П (р 0,2п-1)со структурой вида

(ХР)

r- -rrA V V tr{n}f 1э2« (Ьг) (Ь2п )... () ,

(3)

2

Хр (xi ) - р-й подвектор

вектора переменных X (XL X2хп); xi1

xi, xj° означает отсутствие переменной xi в векторе Хр; - матрица размерности 2n x 2П, формируемая по рекуррентному соотношению (I 1,п)

2

)

i.

. 2й 2г (I ()

где 12,.1 , 1ги-; , U единичные матрицы размерности 2м х 2м, 2пН х , 2 х 2П

соответственно, pi. P2.. ставление параметра р причем

(Gfl,K

Хр (хГ , Х2Ргхпп ). булева производная

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

эЈМ зх0

Дх1,ха,...,хп)©{(,...)хргГ),

Изобретение относится к цифровой вычислительной технике и может быть использовано для аппаратной поддержки 8, вычислений в системах автоматизированного анализа и синтеза цифровых автоматов, при их диагностике и контроле, при анализе комбинационных схем, для исследования статических и динамических ограничений при их проектировании. Цель изобретения - расширение функциональных возможностей за счет вычисления булевх производных по всем переменным и векторам переменных. Устройство содержит п групп вычислительных ячеек 1/ по 2м ячейки в каждой (п - количество переменных булевой функции; I 1 ,n; J 1,2) и элемент задержки 2. На первом такте работы осуществляется загрузка ячеек, на последующих тактах производится формирование элементов под- векторов результата. 4 ил., 4 табл. (Л С

(g)- символ кронекеровского произведения матриц. При этом в модели (2) суммирование подмодулю два выполняется над векто- рами Xdx и GX поэлементно.

Математические модели (2)-(4) могут быть пояснены на конкретном примере. Пусть п 2. Матрица G в соответствии с изложенным формируется следующим об-

Можно показать, что вычисления вектора значений полного булева дифференциала функции алгебры логики f(X) по соотношению (2) можно свести к вычислениям на основе математической модели вида

(mod2),(5)

где D - матрица размерности 22n х 2П, состоящая из 2П подматриц Соразмерностей х 2П; подматрица D, формируется по пра

I)

(ХР) 2

(Ур) i

,©сг

Таким образом, вектор d)Ј представляет собой совокупность векторов

dX

где вектор dX есть вектор значений булевой производной по вектору переменных

Вектор вычисляется по матричному соотношению

d WOff)- D X

(mod2),(6)

02п- матрица размерности 2 x 2 из нулей; xi° xi; xi XL

Следующий пример поясняет математическую модель (5). Пусть для вектора значений X 0 1 1 булевой функции f(X) f(xi,x2) двух переменных (п 2) требуется вычислить вектор значений полного булева дифференциала dX. В соответствии с моделью (5) получают

PX.DX- 7--Т5

0

5

0

5

Интерпретируют вектор значений полного булева дифференциала dX в табличном виде (табл. 1).

Табл. 1 показывает, что для п 2 вектор значений полного булева дифференциала представляет собой последовательность 2г 4 подвекторов, которые являются результатами вычисления частных булевых производных по переменным xi и ха и по вектору переменных (XL X2) Следовательно, с помощью предлагаемого устройства можно вычислять как полный булев дифференциал булевой функции f(X), так и ее частные булевы производные по всем переменным и под- векторам Хр вектора переменных X.

Записывают рекуррентное правило

миоования матрицы Ь„Гв виде

формиоования матрицы ЦГр в виде

)-C(x;VXeWX;1 2. 2.г

(Xe,x;),x-,f Хе. , : Следовательно, подвектор

DЈ

(П

ХР

,

о„„х

(mod 2)

вычисляется, формуле

(f)

«JX1

согласно выражению

-Г((Хе)7шт1(Х; у 2П 2й

Достоинства модели (8) в том, что она имет прямое отображение в структурное решение и более предпочтительна для реализации.

На фиг. 1 представлена структурная схе- ма устройства; на фиг.2 - структурная схема вычислительной ячейки 1j (i 1,n, j 1,2rt); на фиг.З - операционный граф алгоритма вычисления полного булева дифференциала при п 2; на фиг.4 - схема информационных потоков в систолическом процессоре.

Устройство (фиг.1) содержит 2п-1 вычислительных ячеек 1j (i 1,п, где I - номер группы; j - номер ячейки в группе, j 1,2), объединенных в п групп по 2 вычислитель- ных ячеек в каждой группе, элемент задержки 2, тактовый вход 3, информационный вход 4 и группу выходов 5, причем информационный вход 4 устройства соединен с первым 6 и вторым 7 информационным входами первой вычислительной ячейки n-й группы 11П, первый тактовый вход 9 которой соединен с выходом элемента задержки 2, вход которого соединен с вторым тактовым входом 10 первой вычислительной ячейки п-й группы 1 ч и тактовым входом 3 устройства, первый выход 12 первой вычислительной ячейки m-й группы 1im (т 2,п) соединен с

первым 6 и вторым 7 информационными входами первой вычислительной ячейки (т- 1)-й группы . второй выход 13 первой вычислительной ячейки m-й группы 1 im соединен с первым информационным входом б второй вычислительной ячейки m-й группы 12™. третий выход 14 k-й вычислительной ячейки (k 2,) v-й группы 1nv (v 3,n) соединен с первым информационным входом 6 (к+1)-й вычислительной ячейки v-й группы 1k+iv, вход задания режима 8 первой вычислительной ячейки р-й группы (р 1,п) 1ip соединен с выходом логического нуля устройства, входы задания режима 8 всех вычислительных ячеек, кроме первой 1im, m-й группы соединены с входом логической единицы устройства, четвертый выход19 и-й вычислительной ячейки (и 1,2 -1) m-й группы 1U соединен с первым тактовым входом 10 (и+1}-й вычислительной ячейки m-й группы 1u-nm, пятый 11 и шестой 18 выходы первой вычислительной ячейки m-й группы 1im соединены соответственно с первым 10 и вторым 9 тактовыми входами первой вычислительной ячейки (т+1)-й группы 11тИ, седьмой выход 17 u-й вычислительной ЯЧРЙКИ m-й группы соединен с вторым тактовым входом 9 (и+1}-й вычислительной ячейки m-й группы 1и+1 . восьмой выход 15 (и-1)-й вычислительной ячейки n-й фуппы 1и+1п и девятый выход 16 с-й (с - 1 2Г| } вычислительной

где ki. k2,

ячейки nй группы 1СП соединены с информационным входом 5 устройства восьмой выход 15(и+1)-й вычислительной ячейки у-й группы 1и-ну (у 2,) соединен с вторым и н4 0Јм ационным входом 7 (2д-М)-й (д 1,) вычислительной ячейки (у+1)-й группы, девятый выход (и+1)-й вычислительной ячейки у-й группы IIH 1У соединен с вторым информационным входом (2д+ 2)-й вычислительной ячейки (у+ 1)-й группы , девятый выход 16 первой вычислительной ячейки (т-1)-й группы соединен с вторым информационным входом 7 второй вычислительной ячейкий m-й группы 12т.

Вычислительная ячейка 1i реализует математическую модель (б) и обеспечивает вычисление элементов вектора

где ki. k2,

(уЛ- -

1ГХ)Х Х©

-(хО

X.

Вычислительная ячейка (г 2,п. k

2,) обеспечивает вычисления в соотвествии с математической моделью (8) вида

(xk xkz уЦ-

-п ,х 2 , ..., АГМ f, J YЛ. .ki

Х

-i

(.MXrV |@DOVi x

Aгде ki. k2,

двоичное представление

}ЧЭ|

-1) в векторе

параметра k, xm1 xm, xm° означает отсутст

вне переменной хт (т 1,г- переменных (XL хаxr-i).

Элемент задержки 2 обеспечивает задержку сигнала, поступающего на его вход, на один такт (период времени t ti - to).

Вычислительная ячейка 1/ (i 1,n, J

1,2J ) имеет особенности схемотехнических решений и функционирования.

Вычислительная ячейка 1/ содержит (см. фиг.2) первый 20 и второй 21 сдвиговые регистры, первый 22, второй 23 и третий 24 коммутаторы, элемент сложения по модулю два 25, Т-триггер 26, первый 27 и второй 28 элементы ИЛИ и элемент задержки 29, выход которого соединен с входами разрешения записи первого 20 и второго 21 сдвиговых регистров. Выход первого сдвигового регистра 20 соединен с информационным входом 35 второго коммутатора 23, первый выход 37 которого соединен с первым входом первого элемента ИЛИ 27. Выход элемента ИЛИ 27 соединен с первым входом элемента сложения по модулю два 25, второй вход которого соединен с выходом второго сдвигового регистра 21. Первый информационный вход 6 вычислительной ячейки 1/ соединен с информационным входом второго сдвигового регистра 21 и первым выходом 12 вычислительной ячейки , второй выход 13 которой соединен с выходом элемента сложения по

модулю два 25. Второй вход последнего соединен с третьим выходом 14 вычислительной ячейки, восьмой выход 15 которой соединен с первым информационным входом 30 первого коммутатора 22 и вторым информационным входом 7 вычислительной ячейки 1j . Выход второго элемента ИЛИ 28 соединен с управляющими входами 30 и 36 первого 22 и второго 23 коммутаторов и с четвертым 18 и пятым 17 выходами вычислительной ячейки 1j . Первый вход второго элемента ИЛИ 28 соединен с первым выходом 41 третьего коммутатора 24. Информационный вход 39 коммутатора 24 соединен с первым тактовым входом 9 вычислительной ячейки 1j , вторым тактовым входом 10 соединенный с входами разрешения сдвига первого 20 и второго 21 сдвиговых регистров, входом элемента задержки 29 и шестым 11 и седьмым 19 выходами вычислительной ячейки, вход задания режима 8 и девятый выход 16 которой соединены соответственно с управляющим входом 40 третьего коммутатора 24 и выходом элемента сложения по модулю два 25. Второй выход 42 третьего коммутатора 24 соединен с входом Т-триггера 26, выход которого соединен с вторым входом второго элемента ИЛИ 28. Второй выход 38 второго коммутатора 23 соединен с вторым информационным входом 32 первого коммутатора 22, первый 33 и второй выходы которого соединены соответственно с вторым входом первого элемента ИЛИ 27 и информационным входом первого сдвигового регистра 20.

Первый сдвиговый регистр 20 (сдвиговый регистр, например, на элементах ИР8 серии К155) обеспечивает прием информации, поступающей на его информационный вход (младший разряд) по сигналу записи на его входе управления записью, сдвиг информации по сигналу на его входе управления сдвигом и выдачу информации с выхода старшего разряда, разрядность равна 2пН в каждом такте работы вычислительной ячейки 1/.

Второй сдвиговый регистр 21 (сдвиговый регистр, например, на элементах ИР8 серии К155) обеспечивает прием информации, поступающей на его информационный вход (младший разряд) по сигналу записи на его входе управления записью, сдвиг информации по сигналу на его входе управления сдвигом и выдачу информации с выхода старшего разряда, разрядность равна 2 для вычислительных ячеек 1i, разрядность ра вна2пн+1 для вычислительных ячеек lit1, k , в каждом такте работы вычислительных ячеек,

Первый коммутатор 22 обеспечивает передачу информации с первого информационного входа 30 на второй выход 34 при низком логическом уровне сигнала на управляющем входе 31 и с второго информационного входа 32 на второй выход 34, а с первого информационного входа 30 на первый выход 33 при высоком логическом уровне сигнала на входе 31 (табл, 2),

Второй коммутатор 23 обеспечивает передачу информации с информационного входа 35 на первый 37 или второй 38 выходы соответственно при низком или высоком логическом уровне сигнала на управляющем входе 36 (табл. 2).

Третий коммутатор 24 обеспечивает передачу информации с информационного входа 39 на первый 41 и второй 42 выходы соответственно при высоком или низком логическом уровне сигнала на управляющем входе 40 (табл. 2).

Элемент сложения по модулю два 25 предназначен для реализации операции сложения по модулю два операндов, посту пающих на его первый и второй входы, и выдачи результатов суммирования на выход.

Т-триггер 26 предназначен для управления работой первого 22 и второго 23 коммутаторов в вычислительных ячейках 1i (I 1.п). Конструктивно это триггер со счетным входом, управляемый по перепаду входного сигнала из в 1, Начальное состояние его - нулевое.

Первый 27 и второй 28 элементы ИЛИ предназначены для логического анализа входных сигналов посредством выполнения над ними операции дизъюнкции.

Элемент задержки 29 обеспечивает задержку сигнала, поступающего на его вход, на 1/2 такта (период времени r (ti -to)/2).

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

В период времен to , т.е. на первых 5 тактах работы устройства, вычислительная ячейка 11 функционирует в первом ре- жиме (табл. 3). При этом осуществляется загрузка сдвиговых регистров 20 и 21 элементами х(0), х(1)xPn-i-i) вектора X.

0

5

0

5

0

5

0

0

В период tgn.;- t22n.i. т.е. на следующих 2 тактах вычислительная ячейка 1г функционирует во втором режиме (табл. 3). При

тутем

суммирования по модулю два эдемантов x v (v - O.) и x( вектора X. поступающих на входы элемента сложения по модулю два 25, т.е. нэ выходе последнего формиру

(w)(v) x(vfex (v+2rH)

8 следующий период времени t т.е. на следующих 2 тактах, вычислитель.1

ная ячейка 1i Функционирует в первом репо,«Ч

модулю два 25 формируются (v+2nH) - y(w)(v) (v О.) век

жиме, на выходе элемента сложения по

элементы i вектора dXH. На этих же тактах в регистр 20 по сигналу записи на его входе управления записью последовательно записываются следующие 2

)

п-4

п.;

№

записывается элемент х вектора значений X x((V1)... . На втором и последующих тактах (по 2П -и включительно) эта процедура выполняется над элементами х .

(2)

Xх X

На ( 1)-м тэкте вычислительная ячейка 1i начинает функционировать во втором режиме При этом ю сигналу на первом тактовом оходе 9 пи --пительной ячей

элементов ( xt2 ..., х( ) вектора X.

На остальных (2П - 2-2пН) тактах вычисления выполняются аналогично вычислениям в период времени t2n.;- . При этом первый и второй режимы функционирова- ния вычислительной ячейки 1т1 чередуются через каждые 2пЧ такта (табл. 3).

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

На вход задания режима 8 вычислительной ячейки 1i поступает низкий логический уровень сигнала, который обеспечивает передачу сигналов с первого тактового входа 9 вычислительной ячейки 11 на вход 39 ком- мутатора 24, а с его выхода 42 - на вход триггера 26. На выходе триггера 26 формируется управляющий сигнал для коммутаторов 22 и 23. Первый 6 и второй 7 информационные входы вычислительной ячейки 1i объединены и обеспечивают одновременное поступление элементов х , х 1 ,,.., вектора ) на информационный вход сдвигового регистра 21 и вход 30 коммутатора 22.

С первого по ()-й такты вычислительная ячейка 1i функционирует в первом режиме. При этом на первом такте () на второй тактовый вход 10 вычислительной ячейки 111 поступает тактовый сигнал, кото- рый передается на вход элемента задержки 29 и на входы управления сдвигом сдвиговых регистров 20 и 21. В результате по этому сигналу осуществляется сдвиг содержимого сдвиговых регистровое и 21 на один разряд вправо в сторону старших. В момент времени to + г по сигналу записи, поступающему с выхода элемента задержки 29 на входы управления записью сдвиговых регистров 20 и 21, в младшие разряды этих регистров

j 5

10

15

20

25 30 35

40 45 50

55

ки 11 (пп спаду из 1 в 0). сюгтупчющгму на вход 39 коммутатора 2-1. нл выходе элемента ИЛИ 28 устанавливается высокий ло гический уровень сигналя В рсзультэте элемент х( вектора значений X передается с первого информационного входа б вычислительной ячейки 1i на вход 30 коммутатора 22 и далее на его выход 33. а затем поступает на первый вход элемента ИЛИ 27;одновременно элемент х(0 из старшего () разряда сдвигового регистра 20 передается на входе 35 коммутатора 23 и далее на его выход 38, а затем с входа 33 коммутатора 22 на его выход и записывается в младший разряд сдвигового регистра 20 по сигналу записи на его управляющем входе. На первый вход элемента сложения по модулю два 25 поступает элемент из старшего разряда сдвигового регистра 21, на е.го второй вход - элемент х с выхода элемента ИЛИ 27. В результате на выходе элемента сложения по модулю два 25 формируется результат (x °gx() . Этот результат передается на второй 13 и девятый 16 информационные выходы вычислительной ячейки 1i . Кроме того, элемент выхода сдвигового регистра 21 передается на третий выход 14 вычислительной ячейки 1i . В результате повторения этой процедуры на тактах с (2 +2}-го по формируются суммы по модулю .

(Ла) ( ( -к гоп-;+ х xv &с) . С 2. -го по

2П -и такты вычислительная ячейка 1i работает в первом режиме функционирования, на управляющие входы 31 и 36 коммутаторов 22 и 23 поступает низкий логический уровень сигнала. В этом режиме, длительность которого 2П тактов, элемен () (,) )

ты х ; xk ..... х вектора X, поступающие на первый информационный вход 6 вычислительной ячейки 1i , последовательно записываются в сдвиговый регистр 20 по сигналу записи на его входе управления за

писью. При этом элементы х® ,

хранящиеся в сдвиговом регистре 20, последовательно передаются по информационному тракту: вход 35 коммутатора 23 - выход 37 коммутатора 23 - элемент ИЛИ 27 - второй вход элемента сложения по модулю два 25. На первый вход последнего с выхода сдвигового регистра 21 поступают в соот- ветствующие такты элементы вектора X. Результаты вычислений с выхода элемента сложения по модулю два 25 передаются нэ второй 13 и девятый 16 выходы вычислительной ячейки 11.

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

).y(w (1)у(Л)(2п-1) вектора результата

dx w (w 2пЧ). При этом продолжается загрузка элементов вектора значений X. На (2п+1)-м также можно начинать загрузку следующего из обрабатываемых векторов X.

Функционирование вычислительной ячейки 1i (I 2,2 ) отличается от функционирования вычислительной ячейки 1i . Отличие заключается в следующем.

При функционировании вычислительной ячейки 1i на ее вход задания режима 8 поступает высокий логический уровень сигнала, обеспечивающий передачу сигналов по информационному тракту: первый тактовый вход 9 вычислительной ячейки 1| - вход 39 коммутатора 24 - выход 41 коммутатора 24 - первый вход элемента ИЛИ 28. Таким образом, сигналы, поступающие на первый тактовый вход 9 вычислительной ячейки 1i, являются управляющими для первого 22 и второго 23 коммутаторов.

В период времени (с ((2Ы))-го по ((21-1)2пН+2п 1 -й такты работы устройства) вычислительная ячейка 1| функционирует во втором режиме, При этом осуществляется загрузка сдвигового

(V;) регистра 21 элементами у (0),

y(X)(D.

(v;)

чп-1

„у (2-1) вектора dX

В период времени t z11-1 - ЪМ+АЧ (с (21 2nH+1)-ro по (21 2п +2й |)-й такты работы устройства) вычислительная ячейка функционирует в первом режиме. На этих тактах происходит загрузка сдвигового регистра

20 элементами у(У (0), у(чЬЛЬпН-1)

вектора (q %2n +1) и продолжается загрузка сдвигового регистра 21 следующи

(У;) ми элементами вектора dX .

В следующий период времени (t(2j«,)gn-i n-l

50

- t(2p.)- T-e. на следующих 2 тактах, на выходе элемента сложения по модулю два

25 формируются элементы у (0), у . (1),

(V;l n i-(Va.xO55

.... у (2 -1) вектора dX. которые

предстапляют собой сумм ы по модулю два (у( V (у)ву (v 1-2 )) (v - 0.2-1). и поступают на девятый выход 16 вычислительной ячейки V.

На следующих тактах происходит вып-1

числение следующих 2 элемен гоо вектора

- (Уо,: dX за счет суммирования по модулю два

на элементе сложения по модулю два 25

0

5 0 5

0

5

0

5

0

5

м.

чП-К

м,

п-1

элементов у r() и y (v) (v 0,). Результаты суммирования передаются на девятый выход 16 вычислительной ячейки 1|, Следовательно, вычислительная ячейка

,n-l

п-К

1| на тактах с ((2Ы))-го по ((21+1))-й функционирует в режиме загрузки данных, а на следующих 2П тактах - в режиме выдачи результата (табл. 3).

Компоненты вычислительной ячейки 1| в первом и во втором режиме работают так же. как и компоненты вычислительной ячейки li1.

Функционирование устройства в совокупности составляющих его компонентов может быть рассмотрено на конкретном примере вычисления полного булева дифференциала для функции трех переменных (n 3J.

Исходный вектор значений А х °У... х j функции f(X) подается поэлементно (начиная с младшего элемента х) на информа- ционный вход устройства. Устройство содержит вычислительных ячеек:

1l 112, 122, 113-143.

Вычислительные ячейки 1i1, 1i2, 1i3 и вычислительные ячейки 122, 123- 143(фиг.4) работают следующим образом.

На первом такте работы устройства вычислительные ячейки 1i , 1i и 1i3 функционируют в первом режиме. Принтом первый элемент х вектора значений X (момент времени to) передается с первых информационных входов 6 вычислительных ячеек 1г. It2 и 111, объединенных с входами 7 этих ячеек, на входы 30 коммутаторов 22. Далее элемент х с входа 30 каждого из коммутаторов 22 по низкому логическому уровню сигнала на их управляющих входах 31 передается на информационный вход каждого из сдвиговых регистров 20 и записывается в его младший разряд. Кроме того, элемент х 0 с первых информационных входов б вычислительных ячеек поступает на информационный вход каждого из сдвиговых регистров 21 и записывается в его младший разряд (по сигналу записи на входе управления записью сдвигового регистра 21) (табл. 4).

На втором такте (момент времени ti) вычислительные ячейки Ь1 и 11 продолжают функционировать в первом режиме, в них выполняются аналогичные вычисления

JD

X.

для элемента х1 вектора ЗМЯЧРНИП X, к-т к для ялнмента х °. ВЫЧИСПИТЯПЬИРЯ 1Г переходит РП топей ррч ии .ри

ровэния, и в ней вычисления осуществляются следующим образом: элемент х с входа 30 коммутатора 22 передается на его выход 33 и далее на первый вход элемента ИЛИ 27, с выхода которого передается на второй вход элемента сложения по модулю два 25. При этом коммутаторы 22 и 23 вычислительной ячейки 1г функционируют во втором режиме, и элемент х ° с выхода одноразрядного регистра 20 передается на информационный вход этого регистра и по сигналу записи на его входе управления записью перезаписывается в сдвиговый регистр 20. Кроме того, элемент записывается в одноразрядный регистр 21, а элемент х °. хра- нившийся в сдвиговом регистре 21, передается с его выхода на первый вход элемента сложения по модулю два 25. Результат суммирования (0) - х %х 1 с выхода элемента сложения по модулю два 25 передается на выходы 13 и 16 вычислительной ячейки 1i , с вывода 13 вычислительной

передается

ячейки 113 сумма (0)

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

На третьем такте (момент времени ta) на первый информационный вход б вычислительных ячеек 1i -1i3 поступает элемент

/одо

хк . При этом вычислительная ячейка 1 г переходит в первый режим работы, и элемент х , хранившийся в сдвиговом регистре 20 вычислительной ячейки 1i3, передается с его выхода на второй вход элемента сложения по модулю два 25 и суммируется с элементом , поступившим с выхода сдвигового регистра 21. Результат суммирования у д) передается на второй

13

и девятый 16 выходы вычислительной ячейки 1i3 и на первый информационный вход 6 вычислительной ячейки la3 и записывается в сдвиговый регистр 21 по сигналу записи на его входе управления записью (табл. 4). Одновременно в сдвиговые регистры 21 вычислительных ячеек 111, 112 и 1 г и в сдвиговые регистры 20 вычислительных ячеек 11 и 113 записывается элемент х®. На этом же такте вычислительная ячейка 1г переходит во второй режим функционирования, и на выходе элемента сложения по модулю два 25 вычислительной ячейки 1г формируется первый элемент вектора dXp :yp (0)- xto x 2), который передается на девятый выход 16 вычислительной ячейки 1v и на второй информационный вход 7 вычислительной ячейки 1г3, где элемент у 2 (0) записывается в сдвиговый регистр 21.

На пятом такте формируются следующие элементы вектора результата: у (3). (2) и (1) в вычислительных ячейках 1i ,

оо

1г и 12 соответственно. Вычислительная ячейка 1i1 на этом такте переходит во второй режим функционирования и на ее выходах формируется элемент у (0) х ЬУС

который с девятого выхода 16 вычислительной ячейки 111 передается на второй информационный вход 7 вычислительной ячейки 1i2, где записывается в сдвиговый регистр 20, и с девятого выхода 16 вычислительной

ячейки 1i2 передается на второй информационный вход 7 вычислительной ячейки 14

и записывается в ее сдвиговый регистр 20. Вычислительные ячейки Ъ . 1з . 14 функционируют в соответствии с табл. 4.

Таким образом,- на тактах с второго по девятый в вычислительной ячейке 1i3 формируются элементы у (О), у (1), .... у v) вектора d)v1 , элементы вектора - в вычислительной ячейке 1i2 на тактах с

третьего по десятый, элементы вектора dX - в вычислительной ячейке 12 на тактах с четвертого по одиннадцатый, элементы вектора dX - в вычислительной ячейке 11 на тактах с пятого по двенадцатый, элементы

вектора dx 5 - в вычислительной ячейке 1з3 на тактах с шестого по тринадцатый, элементы вектора dX - в вычислительной ячейке 12 на тактах с седьмого по четырнадцатый, элементы вектора - в вычислительной ячейке 1«3 на тактах с восьмого по пятнадцатый, в соответствии с табл. 4.

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

вычислительных ячеек 1i1. 1i2 и 1i3, на следующих четырнадцати- выдача результирующих элементов ),ys)(1), ., y(s (7) подвекторов результата dX (s 1,7). При этом, начиная с девятого такта, можно осуществлять загрузку устройства элементами следующего вектора значений X следующей булевой функции f(X).

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

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

и технологичностью изготовления на основе СБИС-технологии; сокращением затрат на изготовление.

Формула изобретения Устройство для вычисления булевых дифференциалов, содержащее п вычислительных ячеек (п - количество переменных булевой функции f(X)), каждая из которых содержит элемент сложения по модулю два, первый и второй коммутаторы и два элемента ИЛИ, отличающееся тем, что, с целью расширения функциональных возможностей за счет вычисления булевых производных по всем переменным и векторам переменных, оно содержит 2п-п -1 вычисли- тельных ячеек. объединенных в п групп по 2Г1 (I 1,п) вычислительных ячеек в каждой, и элемент задержки, причем информационный вход устройства соединен с первым и вторым информационными входами первой вычислительной ячейки n-й группы, первый тактовый вход которой соединен с выходом элемента задержки, вход которого соединен с вторым тактовым входом первой вычислительной ячейки n-й группы и тактовым входом устройства, первый выход первой вычислительной ячейки m-й группы (т 2,п) соединен с первым и вторым информационными входами первой вычислительной ячейки (т-1)-й группы, второй выход - с первым информационным входом второй вычислительной ячейки m-й группы, третий выход k-й вычислительной ячейки (k 2,2 -1) v-й группы (v 3,п) соединен с первым информационным входом (к+1)-й вычислительной ячейки v-й группы, вход задания режима первой вычислительной ячейки р-й группы (р - 1 ,п) соединен с входом логического нуля устройства, входы задания режима всех вычислительных ячеек, кроме первой, m-й группы соединен с входом логической единицы устройства, четвертый выход и-й вычислительной ячейки (и 1,2-1) m-й группы соединен с первым тактовым входом (и+1)-й вычислительной ячейки m-й группы, пятый и шестой выходы первой вычислительной ячейки m-й группы соединены соответственно с первым и вторым тактовыми входами первой вычислительной ячейки (т+1)-й группы, седьмой выход u-й вычислительной ячейки m-й группы соединен с вторым тактовым входом (и-М)-й вычислительной ячейки m-й группы, восьмой выход (и+1)-й вычислительной ячейки n-й группы и девятый выход с-й (с 1.2) вычислительной ячейки n-й группы соединены с информационным входом устройства, восьмой выход (ц-М)-й вычислительной ячейки у-й группы (у « 2.П--1) соединен с вторым информационным входом (2д+1)-й (д 1,2 Т) вычислительной ячейки (у-Н)-й группы, девятый выход (и+1)-й вычислительной ячейки у-й группы соединен с вторым информационным входом ()-й вычислительной ячейки (у+1)-й группы, девятый выход первой вычислительной ячейки ()-й группы соединен с вторым информационным входом второй вычислительной ячейки m-й группы, причем каждая вычислительная ячейка содержит два сдвиговых регистра. Т-триггер, третий коммутатор и элемент задержки, выход которого соединен с входами разрешения записи первого и второго сдвиговых регистров, выход первого сдвигового регистра соединен с информационным входом второго коммутатора, первый выход которого соединен с первым входом первого элемента ИЛИ, выход которого соединен с первым входом элемента сложения по модулю два, второй вход которого соединен с выходом второго сдвигового регистра, первый информационный вход вычислительной ячейки соединен с информационным входом второго сдвигового регистра и первым выходом вычислительной ячейки, второй выход которой соединен с выходом элемента сложения по модулю два. второй вход которого соединен с третьим выходом вычислительной ячейки, восьмой выход которой соединен с первым информационным входом первого коммутатора и вторым информационным входом вычислительной ячейки, выход второго элемента ИЛИ соединен с управляющими входами первого и второго коммутаторов и с четвертым и пятым выходами вычислительной ячейки, первый вход второго элемента ИЛИ соединен с первым выходом третьего коммутатора, инфор- мационный вход которого соединен с первым тактовым входом вычислительной ячейки, второй тактовый вход которой соединен с входами разрешения сдвига первого и второго сдвиговых регистров, входом элемента задержки и с шестым и седьмым выходами вычислительной ячейки, вход задания режима и девятый выход которой соединены соответственно с управляющим входом третьего коммутатора и выходом элемента сложения по модулю два, второй выход третьего коммутатора соединен с входом Т-триггера, выход которого соединен с вторым входом второго элемента ИЛИ. второй выход второго коммутатора соединен с вторым информационным входом первого коммутатора, первый и второй выходы которого соединены соответственно с вторым входом первого элемента ИЛИ и информационным входом первого сдвигового регистра

О О

о о 1 1 1 1 о о о о 1 1 1 1

о о 1 1 о о 1 1 о о 1 1 о о 1 1

о 1 о 1 о 1 о 1 о 1 о 1 о 1 о 1

Еыхрд 3 Зыход 37

Выход 33 Выход 3 Выход 38

(2j-1) +1 2j-1) +2 (2j-l)- +2 2j-2n-« -И 2J. +2

. (2j + 1)2n- +1 (2j-M) +2

y(M (2n-) у Р (2n%: +1)

у(М()

Таблица I

о о о о 1 1 о о 1 о 1 о 1 о о 1

Зыход 37

Выход 38

Выход 42 Выход 41

Таблица 3

Нагрузка регистра

10только для

11 k - 2,2S-

у( (0) У(Х1° (О

yttrf (.,)

y(M (2- ) yW(2h-1+,)

y(2n-1)

X

x

(ol

0 0

о

x

xw

0 0

,

K

„(«

x

(1)

,w

«)

X

X

(0

X1

х

x

yttl

x

„«

x« xw x x( l

x(0 W

X(.1

„m

x XM

х xw

xw

ХИ1

x

(M

x(

x(rt

xw о

x( x x«

X1

)

x(« x

x 4

xi.)

Xй

xw

X1

xwl

X(.l

x x(1

X

0

x

.«1

„(si

„(

„(«

10

v(5) о

Ю)

Kw

.1)

«« ,«t

t(s)

ЛЧ

.()

„M

«)

(0

,()

x«( )

w

.И1

Y(o) 0

v(4 TW

v«

0 0

yd)

,W)

0

0 0

,(il

v«

(o)

Y(« YM

,w

Y(e)

T

tw ,«l

„Wl

1

о

K(f)

,,«)

,(

f(«l

Yfl

t o

y()

YH)

Y

Tw Tw

Y

v№

Y«

YOI

ttr) TW

v(

.

ло

х

,

/

yvr

А

) ЭГ ,хз1

,(«

Ф X

Г )

xw

,

лз;

«

./х

.Й Х

W

/, -S

в )

ФигЗ

л)

г

Х ««Х« X wex J

rf

fi;

/

г

JT.

,г;

/ А