Устройство для вычисления булевых дифференциалов
Изобретение относится к цифровой вычислительной технике и может быть использовано для аппаратной поддержки 8, вычислений в системах автоматизированного анализа и синтеза цифровых автоматов, при их диагностике и контроле, при анализе комбинационных схем, для исследования статических и динамических ограничений при их проектировании. Цель изобретения - расширение функциональных возможностей за счет вычисления булевх производных по всем переменным и векторам переменных. Устройство содержит п групп вычислительных ячеек 1/ по 2м ячейки в каждой (п - количество переменных булевой функции; I 1 ,n; J 1,2) и элемент задержки 2. На первом такте работы осуществляется загрузка ячеек, на последующих тактах производится формирование элементов подвекторов результата. 4 ил., 4 табл. (Л С
, Ф
СОК)3 СОВЕТСКИХ
СОЦИАЛИСТИЧЕСКИХ
РЕСПУБЛИК (st)s G 06 F 7/00, 7/04
ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕ
ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) I
ОПИСАНИЕ ИЗОБРЕТЕНИЯ
° Ф
1 1 ° д4г 1
К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4771326/24 (22) 18.12.89 (46) 23.11.92. Бюл. М 43 (71) Минский радиотехнический институт (72) И.Л.Колодиева, Н.Н.Парамонова, В.П,Шмерко и С.Н,Янушкевич (56) Авторское свидетельство СССР
М 1370651, кл, G 06 F 7/00. 1986.
Авторское свидетельство СССР
М 1317430, кл. G 06 F 7/00. 1986.
Авторское свидетельство СССР
% 1388843, кл. G 06 F 7/00, 1986. (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ БУЛЕВЫХ ДИФФЕРЕНЦИАЛОВ (57) Изобретение относится к цифровой вычислительной технике и может быть использовано для аппаратной поддержки 0 1777132 А1 вычислений в системах автоматизированно. го анализа и синтеза цифровых автоматов. при их диагностике и контроле, при анализе комбинационных схем, для исследования статических и динамических ограничений при их проектировании, Цель изобретения — расширение функциональных возможностей за счет вычисления булевх производных по всем переменным и векторам переменных. Устройство содержит и групп вычислительных ячеек 1 по 2 ячейки в каждой (и — количество переменных булевой функции;! = 1 n; J = 1,2 ) и элемент задержки
2. На первом такте работы осуществляется загрузка ячеек, на последующих тактах производится формирование элементов подвекторов результата. 4 ил., 4 табл, 1777132
Изобретение относится к автоматике и вычислигельной технике и может быть использовано для аппаратной поддержки вычислений в системах автоматизированного анализа и синтеза цифровых автоматов, при их диагностике и контроле, при анализе комбинационных схем, для исследования статических и динамических ограничений при проектировании комбинационных схем.
Известно устройство, предназначенное для вычисления булевых производных и содержащее элементы неравнозначности, блок определения значений функции с соответствующими связями.
Известно также устройство, содержащее счетчик, группу элементов неравнозначности. мультиплексор, элемент И, генератор импульсов, демультиплексор, группу триггеров с соответствующими связями, обеспечивающее вычисление булевых производных, Наиболее близким к изобретению по выполняемым функциям и технической сущности (является устройство, содержащее регистр, и ячеек (n — количество переменных булевой функции f(X)) с соответствующими связями, причем ячейка состоит из двух мультиплексоров (коммутаторов), двух элементов
И. двух элементов ИЛИ, элемента НЕРАВНОЗНАЧНОСТЬ (сумматора по модулю два).
Известные устройства реализуют одну и ту же математическую модель, Недостатки этих устройств заключаются в следующем: устройства не позволяют вычислять булевы дифференциалы, а в лучшем случае обеспечивают вычисление составных частей булевых дифференциалов, которые представляют собой булевы производные по частным переменным; нетехнологичны в изготовлении из-за неоднородности объекта по структуре, что вызывает трудности при изготовлении на современной технологической базе сверхбольших интегральных схем; не ориентированы на конвейерные принципы обработки информации, позволяющие одновременно вычислять булевы производные по различным переменным, В результате не обеспечивается эффективное решение большого класса прикладных задач, контроль и диагностика цифровых автоматов, решение логических уравнений как составного этапа синтеза цифровых устройств и функционирования систем принятия решений в управлении ресурсами, распознавании и классификации обьектов, управлении роботами-манипуляторами и гибкими автоматизированными производствами. Эффективность решения здесь понимается прежде всего в плане на5
35
45 иболее простого отображения решения задачи в виде алгоритма в структуры вычислительных средств, ориентированных на современную и перспективную микроэлектронную технологию. Это обеспечивает создание мощных средств аппаратной поддержки вычислений в ЭВМ и комплексах различного назначения.
Предлагаемое техническое решение устраняет перечисленные недостатки.
Цель изобретения — расширение функциональных воэможностей устройства за счет вычисления полного булева дифференциала логической функции, в том числе— булевых производных по всем переменным и векторам переменных.
Указанная цель достигается тем, что в устройство, содержащее и вычислительных ячеек (n — количество переменных булевой функции f(X)), введены (2" — n — 1) вычислительных ячеек, объединенных в и групп по
2 (! = 1,п) вычислительные ячейки в каж1-1 дой, и элемент задержки, причем информационный вход устройства соединен с первым и вторым информационныи входами первой вычислительной ячейки и-й группы, первый тактовый вход которой соединен с выходом элемента задержки, вход которого соединен с вторым тактовым входом первой вычислительной ячейки и-й группы и тактовым входом устройства, первый выход первой вычислительной ячейки m-й группы (m = 2,п) соединен с первым и вторым информационными входами первой вычислительной ячейки (m-1)-й группы, второй выход первой вычислительной ячейки m-й группы соединен с первым информационным входом второй вычислительной ячейки m-й группы, третий выход k-й вычислительной ячейки (k - 2,2 -1) ч-й группы (ч = 3,n) соединен с первым информационным входом (k+1)-й вычислительной ячейки v-й группы, вход задания режима первой вычислительной ячейки р-й группы (р = 1.п) соединен с входом логического нуля устройства, входы задания режима всех вычислительных weек, кроме первой, m-й группы соединены с входом логической единицы устройства, четвертыфвыхрд и-й вычислительной ячей50 ки (u - 1, 2 -1) m-й группы соединен с первым тактовым входом (u4-1)-й вычислительной ячейки m-й группы, пятый и шестой выходы первой вычислительной ячейки m-й группы соединены соответст55 венно с первым и вторым тактовыми вхо. дами первой вычислительной ячейки (m+1)-й группы, седьмой выход в-й вычислительной ячейки rn-й группы соединен с втОрым тактовым входом (u41)-й вычислительной ячейки m-й rpynnu. вось1777132 мой выход (u+1)-й вычислительной ячейки и-й группы и девятый выход с-й (с = 1,2" ) вычислительной ячейки и-й группы соединены с информационным входом устройства, восьмой выход (u+1)-й вычислительной ячейки у-й группы (у = 1,2п-1) соединен с вторым информационным входом (2g+1)-й(р
1,2 — 1) вычислительной ячейки (у+1)-й группы, девятый выход(о+1)-й вычислительной ячейки у-й группы соединен с вторым информационным входом (2д+2)-й вычислительной ячейки (у+1)-й группы, девятый выход первой вычислительной ячейки (m — 1)-й группы соединен с вторым информационным входом второй вычислительной ячейки
m-й группы, причем в вычислительную ячейку, содержащую элемент сложения по модулю два, первый и второй коммутаторы и два элемента ИЛИ, введены два сдвиговых регистра, Т-триггер, третий коммутатор и элемент задержки, выход которого соединен с входом разрешения записи первого и второго сдвиговых регистров, выход первого сдвигового регистра соединен с информационным входом второго коммутатора, первый выход которого соединен с первым входом первого элемента ИЛИ. выход которого соединен с первым входом элемента сложения по модулю два, второй вход которого соединен с выходом второго сдвигового регистра, первый информационный вход вычислительной ячейки соединен с информационным входом второго сдвигового регистра и первым выходом вычислительной ячейки, второй выход которой соединен с выходом элемента сложения по модулю два, второй вход которого соединен с третьим выходом вычислительной ячейки, восьмой выход которого соединен с первым информационным входом первого коммутатора и вторым информационным входом вычислительной ячейки, выход второго элемента
ИЛИ соединен с управляющими входами первого и второго коммутаторов и с четвертым и пятым выходами вычислительной ячейки, первый вход второго элемента ИЛИ соединен с первым выходом третьего коммутатора, информационный вход которого соединен с первым тактовым входом вычислительной ячейки, второй тактовый вход которой соединен с входами разрешения сдвига первого и второго сдвиговых регистров, входом элемента зад"ржки и с шестым и седьмым выходами вычислительной ячейки. вход задания режима и девятый выход которой соединены соо1вегственно с управляющим входом третьего коммутатора и выходом элемента сложения по модулю два, второй выход третьего оммутатора соединен с входом Т-триг(ера. выход которого
dX =4x О+ 6Х (mod2), (2) где Х (х = (Х", Х",...I X ) — вектор размерности
40 2 "х 1, составленный из векторов значений
Х (векторов истинности) булевой функции
f(X) Х = (о) () х(2" — ))
2" х 1; т —; G—, матрица размерности 2 "х 2", состоящая иэ
45 2",подматриц G, размерности 2 х 2" (р =
ll г"
0,2 — 1) со структурой вида (3)
Ра Ра Pq
50 Xp = (x1, х2...„xД ) — р-й подвектор
- вектора переменных Х = (х1, х2, ..., Xn); xl
xl, xl означает отсутствие переменной x(в о векторе ХР, 6 „ — матрица размерности 2" х
2", формируемая по рекуррентному соотно55 шению (! = 1,п) 6 „= !;9(1 Q !2),, (i1 (4) где 1,, )2-, — единичные матрицы размерности 2 х 2, 2" x 2", 2" х 2" соединен с вторым входом BIOp0(0 элемента ИЛИ, второй выход второго коммутатора соединен с вторым информационным входом первого коммутатора, первый и второй
5 . выходы которого соединены соответственно с вторым входом первого элемента ИЛИ и информационным входом первого сдвигового реги тра.
Сущ сть изобретения заключается в
10 организац и однОродного вычислительного процесса получения полных булевых дифференциалов булевой функции на принципах параллельно-конвейерной обработки.
В основу предлагаемого объекта поло15 жены следующие математические модели функционирования компонентов и устройства в целом, Полный булев дифференциал функции алгебры логики 1(х1, х2, ..., хп) и переменных
20 определяется соотношением (Бохманн Д., Постхоф Х. Двоичные динамические системы.— М.: Энергоатомиэдат, 1986)
df(X) = 1(Х)0+f(X 8MX), (1) гдЕ f(XQ+ dX) = f(x19 dxl, x2 0+dx2, ..., x@f3
25 " бхр(), dx1, dx2, ..., dxn <(0,1) — булевы дифференциалы переменных х1, х2, ..., X>, описы- вающие изменения соответствующих переменных(при изменении значения пере30 менной xl ее булев дифференциал dx; = 1, при неизменном значении переменной х(ее булев дифференциал dxl = О).
В матричном виде данные операции представляются следующей математиче35 ской моделью:
1777132 соответственно; р), рр... pn -- двоичное представление параметра р; причем (<) р Д." <Р<
1 д«(<)
21< 1 Р< разом
I a (x Q R С- ()(г1 2 г С (Хь) р2 (XI) Подматрицы Огг матрицы G в соответствии с выражением (4) имеют вид (хе) (2) r,;Ox (1 ® (Х2) () Г 11 . чг* г г ®LI .(() г" 1 (Х<) (<) г сг г Можно показать, что вычисления вектора значений полного булева дифференциала функции алгебры логики f(X) по соотношению (2) можно свести к вычислениям на основе математической модели вида Ы = ОХ (mod2). (5) где 0 — матрица размерности 2 " х 2", состоП (Х1) ящая из 2 подматриц D „ )размерностей 2"" и, х 2; подматрица 0гД формируется по правилу (y) Я 2< — 2<,3 )1 Таким образом, вектор dX представляет собой совокупность векторов Dô Х; d (<) \ ДК -< (qn 1) -« О„К Э (x«l Х.qn.Э(Х «-,)Х 1 << где вектор бХ р есть вектор значений булевой производной по вектору переменных ®- символ кронекеровского произведения матриц, При этом в модели (2) суммирование по модулю два выполняется над векторами XI)x u GK поэлементно. Математические модели (2) — (4) могут быть пояснены на конкретном примере. Пусть n = 2, Матрица G e соответствии с изложенным формируется следующим обХр = (x), x2,..., х2<" ). булева производная Рг I x< по вектору переменных в аналитическом виде определяется следующим образом: о о о о 1 о о 1 о 1 1 о о I о о о « 1 1 1 1 « 1 1 1 1 I I т 1 25 о 1 1 пх-пх30 Интерпретируют вектор значений пол35 ного булева дифференциала dX в табличном виде (табл. 1). Табл. 1 показывает, что для n = 2 вектор значений полного булева дифференциала представляет собой последовательность 2 = 40 = 4 подвекторов, которые являются результатами вычисления частных булевых производных по переменным х! и хг и по вектору переменных (х), хг). Следовательно, с помощью предлагаемого устройства можно 45 вычислять как полный булев дифференциал булевой функции f(X), так и ее частные булевы производные по всем переменным и подвекторам Хр вектора переменных Х. Записывают рекуррентное правило 50 формирования матрицы Офв виде . (Х Р) (Х Р,)()) (x;) (X(,) ()I; ) Д2 = g2< /II ® ) Щ, 7 (11 Х р (Xg )(,) ) )(Следовательно, подвектор 55 (Хе) dX(l 0 2< Х (mod 2) вычисляется, согласно выражению (7). по формуле (у)(() l - (х ) г)(Хе) + (x;l 8) t — -цх„х„„,,x„)p+f(x,", х",,...,xx„"}, Р Вектор бХ(Р) вычисляется по матричному соотношению (Х) Х(Р) = 0,X (mod2), (6) Оо - матри(а размерности 2" х 2" из. нулей; х) =x), xi = х). Следующий пример поясняет математи15 ческую модель (5). Пусть для вектора значений X = (О 1 1 1) булевой функции f(X) = f(xi,xz) двух переменных (и = 2) требуется вычислить вектор значений полного булева дифференциала бК В соответствии с мо20 делью (5) получают 1777132 Достоинства модели (8) в том, что она имет прямое отображение в структурное решение и более предпочтительна для реализации. На фиг.1 представлена структурная схема устройства; на фиг.2 — структурная схема вычислительной ячейки 1 (1 = 1,n,j = 1,2 ); I — — 1Т. на фиг.3 — операционный граф алгоритма вычисления полного булева дифференциала при и =2; на фиг.4 — схема информационных потоков в систолическом процессоре. Устройство (фиг.1) содержит 2" — 1 вычислительных ячеек 11 (! = 1,п, где I — номер группы; J — номер ячейки в группе, J = 1,2"). объединенных в и групп по 2 вычислительных ячеек в каждой группе, элемент задержки 2, тактовый вход 3, информационный вход 4 и группу выходов 5, причем информационный вход 4 устройства соединен с первым 6 и вторым 7 информационным входами .первой вычислительной ячейки и-й группы 11", первый тактовый вход 9 которой соединен с выходом элемента задержки 2, вход которого соединен с вторым тактовым входом 10 первой вычислительной ячейки и-й группы 11" и тактовым входом 3 устройства, первый выход 12 первой вычислительной ячейки m-й группы 11 (m = 2 n) соединен с первым 6 и вторым 7 информационными входами первой вычислительной ячейки (m— 1)-й группы 11m ". второй выход 13 первой вычислительной ячейки m-й группы 11 соединен с первым информационным входом 6 второй вычислительной ячейки m-й группы 12, третий выхрд 14 k-й вычислительной ячейки (k = 2,2 -1) ч-й группы 1>" (v = 3,n) соединен с первым информационным вхо-, дом 6 (k+1)-й вычислительной ячейки v-й группы 1 +1", вход задания режима 8 первой вычислительной ячейки р-й группы (р = 1,п) 11Р соединен с выходом логического нуля устройства, входы задания режима 8 всех вычислительных ячеек, кроме первой 11, m-й группы соединены с входом логической единицы устройства, четвертый выход 19 и-й вычислительной ячейки (u = 1,2 -1) m-й группы 1 " соединен с первым тактовым входом 10 (0+1}-й вычислительной ячейки m-й группы 1 +1, пятый 11 и шестой 18 выходы первой вычислительной ячейки m-й группы 11 соединены соответственно с первым 10 и вторым 9 тактовыми входами первой вычислительной ячейки (m+1)-й группы 11", седьмой выход 17 и-й вычислительной ячейки п1-й группы 1и соединен с вторым тактовым входом 9 (ц+1 и вычислительной ячейки m-й группы 1ц+1, восьмой выход 15 fu-1)-й вычислительной ячейки п-й группы 1«1" и девятый выход 16 с-й (с =- 1,2 ) вь числительной 15 ячейки и-й группы 1С соединены с информационным входом 5 устройства. восьмой выход 15 (0+1)-й вычислительной ячейки у-й группы 1„+1" (у =- 2,п-1) соединен с вторым информационным входом 7 (2g+1)-й (g =1,2 г-1) вычислительной ячейки (у+1)-й группы, девятый выход (u+1)-й вычислительной ячейки у-й группы 1 +1" соединен с вторым информационным входом (2g+ 2)-й вычислительной ячейки (у+ 1)-й группы 1," „, 1ег девятый выход 16 первой вычислительйойячейки (m — 1)-й группы 11 1 соединен с вторым информационным входом 7 второй вычислительной ячейкий m-й группы 1z . Вычислительная ячейка 11 реализует I математическую модель (6) и обеспечивает вычисление элементов вектора д(т) g g O Q(Х т1 )(20- Вычислительная ячейка 1k (r = 2,n. k = 2,2 ) обеспечивает вычисления в соответствии с математической моделью (8) вида г "1- kr 1 р(Хь, х р, ... е Х „,, Х 1. () (25 k< 1, Ь (х \(пт» "т э- ° 1х т- к Igg(" 1 и 1 где k1. kz, ..., k> — двоичное представление параметра К xm = xm, х означаетотсутст1 0 30 вие переменной xm (m = 1,г — 1) в векторе ПЕРЕМЕННЫХ (Х1, Х2, .„Хг-1). Элемент задержки 2 обеспечивает задержку сигнала, поступающего на его вход, на один такт (период времени t = t1 — t0). 35 вычислительная ячейка 11 (I = 1,n, J = 1,2 ) имеет особенности схемотехнических решений и функционирования, Вычислительная ячейка 111 содержит (см. фиг.2) первый 20 и второй 21 сдвиговые 40 регистры, первый 22, второй 23 и третий 24 коммутаторы, элемент сложения по модулю два 25, Т-триггер 26, первый 27 и второй 28 - элементы ИЛИ и элемент задержки 29, выход которого соединен с входами разреше45 ния записи первого 20 и второго 21 сдвиговых регистров. Выход первого сдвигового регистра 20 соединен с информационным входом 35 второго коммутатора 23, первый выход 37 которого соединен с пер50 вым входом первого элемента ИЛИ 27. Выход элемента ИЛИ 27 соединен с первым входом элемента сложения по модулю два 25, второй вход которого соединен с выходом второго сдвигового регистра 21. Пер55 вый информационный вход 6 вычислительной ячейки 11 соединен с инI формационным входом второго сдвигового регистра 21 и первым выходом 12 вычислигельной ячейки 11, второй выход 13 которой соединен с выходом элемента сложения по 1777132 модулю два 25. Второй вход последнего соединен с третьим выходом 14 вычислительной ячейки, восьмой выход 15 которой соединен с первым информационным входом 30 первого коммутатора 22 и вторым информационным входом 7 вычислительной ячейки 11, Выход второго элемента ИЛИ 28 соединен с управляющими входами 30 и 36 первого 22 и второго 23 коммутаторов и с четвертым 18 и пятым 17 выходами вычислительной ячейки 11. Первый вход второго i элемента ИЛИ 28 соединен с первым выходом 41 третьего коммутатора 24. Информационный вход 39 коммутатора 24 соединен с первым тактовым входом 9.вычислительной ячейки 1, вторым тактовым входом 10 I . соединенный с входами разрешения сдвига первого 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" a каждом такте работы вычислительной ячейки 11. Второй сдвиговый регистр 21 (сдвиговый регистр, например, на элементах ИР8 серии К155) обеспечивает прием информации, поступающей на его информационный вход(младший разряд) по сигналу записи на его входе управления записью, сдвиг информации по сигналу на его входе управления сдвигом и выдачу информации с выхода старшего разряда, разрядность равна 2 для вычислительных ячеек 11; разрядность ! раааа 2" +" для вычислительных ячеек 1, k "2,2, в каждом такте работы вычислительных ячеек. Первый коммутатор 22 обеспечивает передачу информации с первого информационного входа 30 на второй выход 34 при низком логическом уровне сигнала на управляющем входе 31 и с второго информационного входа 32 на второй выход 34, а с первого информационного входа 30 на первый выход 33 при высоком логическом уровне сигнала на входе 31 (табл, 2), Второй коммутатор 23 обеспечивает передачу информации с информационного входа 35 на первый 37 или второй 38 выходы соответственно при низком или высоком логическом уровне сигнала на управляющем входе 36 (табл. 2). Третий коммутатор 24 обеспечивает передачу информации с информационного входа 39 на первый 41 и второй 42 выходы соответственно при высоком или низком ла20 гическом уровне сигнала на управляющем входе 40 (табл. 2), Элемент сложения по модулю два 25 предназначен для реализации операции сложения по модулю два операндов, посту. 25 пающих íà его первый и второй входы, и выдачи результатов суммирования на выход. Т-триггер 26 предназначен для управления работой первого 22 и второго 23 комму30 таторов в вычислительных ячейках 1l (l1,п). Конструктивно это триггер со счетным входом, управляемый по перепаду входного сигнала из м0" в "1". Начальное состояние . его — нулевое. 35 Первый 27 и второй 28 элементы ИЛИ предназначены для логического анализа входных сигналов посредством выполнения над ними операции дизьюнкции. Элемент задержки 29.обеспечивает за40 держку сигнала, поступающего на его вход, на 1/2 такта(период времени т- (t> — to)/2). г Вычислительная ячейка 1ц функцйонй- . : рует следующим. образом. В период времен to- t;, т.е..на первых 45 2" тактах работы устройства, вычислительная ячейка 11 функционирует в первом ре1 жиме (табл. 3). При этом осуществляется загрузка сдвиговых регистров 20 иЯ1 элвментами х, хг, ..., х вектора Х. 50 В период t<,— t,,.;, т.е. на следующих 2 тактах вычйслительная ячейка 11 функционирует во втором режиме (табл. 3). При этом выполняется вычисление элементов 55 (у((О) yW(1) y((2" -1)) . (w - 2л ) путве суммирования по мо улн5 два элементов x (v - 0,2 -1) и х " " вектора Х. поступающих на входы элемента сложения по модулк, два 2), т.е. нв еыхоое лооледнего фермеру ется у" () " x "" x " " В следующий период времени 1 гит 1„ n-I гг" т.е. на следующих 2 тактах. вычислительная ячейка 1I функционирует в первом реI жиме, на выходе элемента сложения по модулю два 25 фоомдичются элементь| у( (ч+2" ) = у (ч)(ч = 0,2 -1) вектора dX(. На этих же тактах в регистр 20 по сигналу записи на его входе управления записью последовательно записываются следующие 2 Ф элементов (х, х, ..., х ) вектора Х. На остальных (2" — 2 2" ) тактах вычисления выполняются аналогично вычислениям в период времени т „; — t -, При этом первый и второй режимы функционирования вычислительной ячейки 11 чередуются 1 через каждые 2" такта (табл. 3). Компоненты вычислительной ячейки 1t I в процессе работы функционируют следующим образом. На вход задания режима 8 вычислительной ячейки 11 поступает низкий логический уровень сигнала, который обеспечивает передачу сигналов с первого тактового входа 9 вычислительной ячейки 1i на вход 39 комI мутатора 24, а с его выхода 42 — на вход триггера 26, На выходе триггера 26 формируется управляющий сигнал для коммутаторов 22 и 23. Первый 6 и второй 7 информационные входы вычислительной ячейки 11 объединены и обеспечивают о(I новременное поступление элементов х х, ..., х " вектора ) на информационный вход сдвигового регистра 21 и вход 30 коммутатора 22. С первого по (2" +1)-й такты вычислительная ячейка 1t функционирует в первом 1 режиме. При этом на первом такте (to-t>) на второй тактовый вход 10 вычислительной ячейки 11 поступает тактовый сигнал, который передается на вход элемента задержки 29 и на входы управления сдвигом сдвиговых регистров 20 и 21. В результате по этому сигналу осуществляется сдвиг содержимого сдвиговых регистров 20 и 21 на один разряд вправо в сторону старших. В момент времени to + t по сигналу записи, поступающему с выхода элемента задержки 29 на входы управления записью сдвиговых регистров 20 и 21, в младшие разряды этих регистров (п(1 записывается элемент х вектора значений ) - (х х 1... х " . На втором и последующих тактах(по 2" -й включительно) эта процедура выполняется над элементами х, х, ..., х Q) (2 -1) На (2" + 1)-м такте вычислительная I ячейка 1t начинает функционировать во втором режиме. При этом Io сигналу на первом тактовом вхпле 9 p l . -. ительнпй ячейки 11 (пп спаду из I" в П"). ипг тчпз ОиГ ч ) на вход 39 коммутатора 2". нл лыкоде элемента ИЛИ 20 устанавливается высокий логический уровень сигнала В результате 5 элемент х" вектора значений X передается с первого информационного входа 6 вы-! числительной ячейки 1I на вход 30 коммутатора 22 и далее на его вь ход 33. а затем поступает на первый вход элемента 10 ИЛИ 27; одновременно элемент х из стар(п1 шего (2" -го) разряда сдвигового регистра 20 передается на входе 35 коммутатора 23 и далее на его выход 38, а затем с входа 33 коммутатора 22 на его выход и записывает15 ся в младший разряд сдвигового регистра 20 по сигналу записи íà его управляющем входе. На первый вход элемента сложения по модулю два 25 поступает элемент х(1 из (0) старшего разряда сдвигового оегистра 21, 20 на его второй вход — элемент х " с выхода элемента ИЛИ 27. В результате на выходе элемента сложения пр модулю два 25 формируется результат (х gx< ) . Этот результат передается на второй 13 и девятый 16 25 информационные выходы вычислительной ячейки 11. Кроме того, элемент х У с выхода сдвигового регистра 21 передается на третий выход 14 вычислительной ячейки 1>. В результате повторения этой процедуры на 30 тактах с (2 к-1 -то оо 2" " -и фоомисуюток суммы по модулю два х Q x " 1. x(+ (2 t2) (2 4 (2. -ь и-i+I х,...,х Ох ), С2 -го по 2 -й такты вычислительная ячейка 1i раи-I+2- 1 35 ботает в первом режиме функционирования, на управляющие входы 31 и 36 коммутаторов 22 и 23 поступает низкий логический уровень сигнала. В этом режиме, и-I длительность которого 2" тактов. элементы х, х, ..., х вектора Х, поступающие на первый информационный вход 6 вычислительной ячейки 1t, последовательно записываются в сдвиговый регистр 20 по 45 сигналу записи на его входе управления за Ич (2 -т) писью. При этом элементы x, х, „„х хранящиеся в сдвиговом регистре 20, последовательно передаются по информационно50 му тракту: вход 35 коммутатора 23 — выход 37 коммутатора 23 — элемент ИЛИ 27 — второй вход элемента сложения по модулю два .25. На первый вход последнего с выхода сдвигового регистра 21 поступает всоот55 ветствующие такты элементы вектора X. Результаты вычислений с выхода элемента сложения по модулю два 25 передаются на второй 13 и девятый 16 выходы вычислительной ячейки 1.1 . 1Г) 1777132 )акил< образом, вычислительная ячейка 1< с первого по 2 -й такты работает в перI n-iaoIvI режиме -- режиме загрузки данных (без выдачи результатов), на тактах с (2" +1)-ro по (2"" +)")-и — в дожиме выдачи элементов 5 у()(0), у " (1)...., у" (2"-1) вектора результата dX() (w = 2" ). При этом продолжается загрузка элементов вектора значений Х. На (2"+1)-м также можно начинать загрузку (;ледующего из обрабатываемых векторов Х, 10 Функциони(зование вычислительной ячейки 1((1 = 2,2 ) отличается от функционирования вычислительной. ячейки 11. ОтI личие заключается в следующем. При функционировании вычислительной 15 ячейки 1I на ее вход задания режима 8 постуI пает высокий логический уровень сигнала, обеспечивающий передачу сигналов по инфор. мационному тракту: первый тактовый вход 9 вычислительной ячейки 1(— вход 39 коммутатора 20 24 — выход 41 коммутатора 24 — первый вход элемента ИЛИ 28. Таким образом, сигналы, поступающие на первый тактовый вход 9 вычислительной ячейки 1I, являются управляющими для первого 22 и второго 23 коммутаторов. 25 В период времени т(г<,1г - — тq.q> (c ((21 — 1)2" +1)-го по ((21-1)2" +2" -й такты работы устройства) вычислительная ячейка 1I функционирует во втором режиме, При 30 этом осуществляется загрузка сдвигового (Х,) (Х;) регистра 21 элементами у (О), у (1), ., у (2" -1) вектора dX (y ) n — i - (х;) В период времени туг - — ((,<) - (с (21 2" +1)-го по (21 2" +2 )-й такты работы устройства) вычислительная ячейка 1I функционирует в первом режиме. На этих тактах 40 происходит загрузка сдвигового регистра (У ) (Х ) (Х1). „, 20 элементами у " (О), у (1)...„у 1(2" -1) вектора dX ) (о =- 1 2" +1) и продолжается загрузка сдвигового регистра 21 следующи 45 (Х;) ми элементами вектора dX В следующий период времени (т(„) <-:— - t(< 1 „,), т.е. на следующих 2" тактах, на выходе элемента сложения по модулю два ()4,Ч (х,к;) 25 формируются элементы у (О), у, (1), (Ь,,к;) (хо, х:1 у (2" -1) вектора dX . которые представляют собой сумтмы по модулю два (у ) (к) {v)I)y(" ) {ч <2" )) (v — 0.2" -1). и поступают на девятый выход 16 вычислительной ячейки 1(. На следующих тактах происходит Bhlu-t числение следующих 2 элементов вектора —. (У,к;) dX за счет суммирования по модулю два на элементе сложения по модулю два 25 (х4 I (к) элементов у (ч+2" ) и у (v) (ч = 0,2" -1), Результаты суммирования передаются на цевятый выход 16 вычислительной ячейки 1I, Следовательно, вычислительная ячейка 1(на тактах с ((21 — 1)2" +1)-го по ((21+1)2" )-й функционирует в режиме загрузки данных, а на следующих 2" тактах — в режиме выдачи результата (табл, 3), Компоненты вычислительной ячейки 1I в первом и во втором режиме работают так же. как и компоненты вычислительной ячейки 1). Функционирование устройства в совокупности составляющих его компонентов может быть рассмотрено на конкретном примере вычисления пол ного булева диффере н циала для функции трех переменных (n = 3J, Исходный вектор значений )(= (х х (о),1, х(т)) функции f(X) подается поэлементно(начиная с младшего элемента х )) на информационный вход устройства. Устройство содержит 2 — 1 = 7 вычислительных ячеек: э 11, 11, 1?, 11 — 14 Вычислительные ячейки 11 1i 11 и вычислительные ячейки 12, 12 — 14 (фиг.4) работают следующим образом. На первом такте работы устройства вычислительные ячейки 11 11 и 11 функцио1 нируют в первом режиме, При этом первый о) элемент х вектора значений Х(момент времени tp) передается с первых информационных входов 6 вычислительных ячеек 1(. 11 и 11 Обьединенных С входами 7 Этих ячеек, 1 на входы 30 коммутаторов 22, Далее элемент х с входа 30 каждого иэ коммутаторов 22 по низкому логическому уровню сигнала на их управляющих входах 31 передается на информационный вход каждого из сдвиговых регистров 20 и записывается в его младший разряд, Кроме того, элемент х(о) с первых информационных входов 6 вычислительных ячеек поступает на информационный вход каждого из сдвиговых регистров 21 и записывается в его младший разряд(по сигналу записи на входе управления записью сдвигового регистра 21) (табл. 4). На втором такте (момент времени tl) вычислительные ячейки 1< и 1I продолжа2 ют функционировать в первом режиме, в них выполняются аналогичные вычисл<энич (Ц для элемента х вектора значений Х, ка« для элемента x (. Бы <ис«итал ьна< ч <в<<ха (о) з 1< пепеходит ао «<ооой р . иг< j «э «ч-.э«< 1777132 18 рования, и в ней вычисления осущечтвляютЯ ся следующим образом: элемент х с входа 30 коммутатора 22 передается íà его выход 33 и далее на первый вход элемента ИЛИ 27, с выхода которого х ) передается на второй 5 вход элемента сложения по модулю два 25. При этом коммутаторы 22 и 23 вычислительной ячейки 11 функционируют во втором режиме, и элемент х() с выхода одноразрядного регистра 20 передается на информаци- 10 онный вход этого регистра и по сигналу записи на его входе управления записью перезаписывается в сдвиговый регистр 20. Кроме того. элемент х записывается в одноразрядный регистр 21, а элемент х(, хра- 15 нившийся в сдвиговом регистре 21, передается с его выхода на первый вход алемента сложения по модулю два 25, Результат суммирования у (О) =- х "Юх с выхода элемента сложения по модулю два 25 20 передается на выходы 13 и 16 вычислительной ячейки 11, с в1Р1рода 13 вычислительной ячейки 1 1з сумма у 1 (О) = х )®х . передается на первый информационный вход 6 вычислительной ячейки 1г и записывается в ее 25 сдвиговый регистр 21. На третьем такте (момент времени тг) на первый информационный вход 6 вычислит ьных ячеек 11-11 поступает элемент Э x . При этом вычислительная ячейка 11з пе- 30 реходит в первый режим работы, и элемент х о, хранившийся в сдвиговом регистре 20 вычислительной я ейки 11 передается с его выхода на второй вход элемента сложения по модулю два 25 и суммируется с эле- 35 ментом х, поступившим,с выхода сдвитового регистра 21. Результат суммирования у (1) х Вх ) передается на второй (1) 13 и девятый 16 выходы вычислительной ячейки 11 и на первый информационный 40 вход 6 вычислительной ячейки 1гз и записывается в сдвиговый регистр 21 по сигналу записи на его входе управления записью (табл. 4). Одновременно в сдвиговые регистры 21 вычислительных ячеек 11, 11 и 11 и 45 1 в сдвиговые регистры 20 вычислите1 ных ячеек 11 и 11 записывается элемент х . На этом же такте вычислительная ячейка 11 переходит во второй режим функционирования, и на выходе элемента сложения пог 50 модулю два 25 вычислительной ячейки 11 формируется первый элемент вектора dX"):уР (О) - х ) х ", который передается на девятый выход 16 вычислительной ячейки 11 и на второй информационный вход 7 55 вычислительной ячейки 1z . где элемент у (0) записывается в сдвиговый регистр 21. Не пятом такте формируются следуюотие впар виты вектора рлзулвтата: у (3). у (2) и у (1) в вычислительнь.х ячейках 11, 11 и 1г соответственно. Вычислительная г з ячейка 11 на этом такте переходит во вто1 рой режим функционирования и на ее выходах формируется элемент у (0) = x Рх ) который с девятого выхода 16 вычислительной ячейки 11 передается на второй информационный вход 7 вычислительной ячейки 11, где записывается в сдвиговый регистр 20, и с девятого выхода 16 вычислительной ячейки 11 передается на второй информационный вход 7 вычислительной ячейки 14 и записывается в ее сдвиговый регистр 20. Вычислительные ячейки 1г, 1з, 14 функциз онируют в соответствии с табл. 4, Таким образом; на тактах с второго по девятый в вычислительной ячейке 113 формируются элементы у )(О), у (1), .... у (7) вектора dX(), элементы вектора dX — в вычислительной ячейке 11 на тактах с третьего по десятый, элементы вектора сЖ вЂ” в вычислительной ячейке 1г на тактах с 3 четвертого по одиннадцатый, элементы вектора dX — в вычислительной ячейке 11 на тактах с пятого по двенадцатый, элементы вектора dX() — в вычислительной ячейке 1j на тактах с шестого по тринадцатый, эле(6) менты вектора dX — в вычислительной ячейке 1г на тактах с седьмого по четырнад (7) цатый, элементы вектора dX — в вычислительной ячейке 14 на тактах с восьмого по пятнадцатый, в соответствии с табл, 4. Таким образом, в целом функционирование устройства заключается в следующем: на первом такте происходит загрузка вычислительных ячеек 11 11 и 11, на сле1 дующих четырнадцати - выдача результирующих элементов у(0),,у )(1), ..., у((7) подвекторов результата dX ) (s = 1,7). При этом, начиная с девятого такта, можно осуществлять загрузку устройства элементами следующего вектора значений X следующей булевой функции 1(Х). Таким образом, изобретение характеризуется следующими технико-экономическими преимуществами по сравнению с аналогами и прототипом: расширением функциональных возможностей за счет того, что устройство позволяет вычислять полный булев дифференциал и булевы производные по переменным и векторам переменных функции алгебры логики, при этом вычисление отдельных частей полного булева дифференциала осуществляется параллельно; простотой технических решений и технологичностью изготовления на основе СБИС-технологии; сокращением затрат на изготовление. Формула изобретения Устройство для вычисления булевых дифференциалов, содержащее и вычисли17771:32 20 тельных ячеек (n — количество переменных булевой функции S(X)), каждая из которых содержит элемент сложения по модулю два, первый и второй коммутаторы и два элемента ИЛИ, о т л и ч а ю щ е е с я тем, что, с .целью расширения функциональных возможностей за счет вычисления булевых и роизводных по всем переменным и векторам переменных, оно содержит 2"-и--1 вычислительных ячеек, объединенных в и групп по 21 (1 = 1,n) вычислительных ячеек в каждой, -1 и элемент задержки, причем информационный вход устройства соединен с первым и вторым информационными входами первой вычислительной ячейки п-й группы, первый тактовый вход которой. соединен с выходом элемента задержки, вход которого соединен с вторым тактовым входом первой вычислительной ячейки и-й группы и тактовым входом устройства, первый выход первой вычислительной ячейки m-й группы (m = 2,n) соединен с первым и вторым информационными входами первой вычислительной ячейки (m-1)-й группы, второй выход — с первым информационным входом второй вычислитепвиои вче тви m-В труллы, третити выход Ьй вычислительной ячейки (k =- 2,2 — 1) v-й группы (v = З,n) соединен с первым информационным входом (k+1) и вычислительной ячейки v-й группы, вход задания режима первой вычислительной ячейки р-й группы (р = i,n) соединен с входом логического нуля устройства, входы задания режима всех вычислительных ячеек, кроме первой, m-й группы соединен с входом логической единицы устройства, четвертый evx o u-й вычислительной ячейки (u = 1,2 — 1) m-й rðónnû соединен с первым тактовым входом (о+1)-й вычислительной ячейки m-й группы, пятый и шестой выходы первой вычислительной ячейки m-й группы соединены соответственно с первым и вторым тактовыми входами первой вычислительной ячейки (m+1)-й группы, седьмой выход и-й вычислительной ячейки m-й группы соединен с вторым тактовым входом (и+1)-й вычислительной ячейки m-й группы, восьмой выход (и+1)-й вычислительной ячейки п-й группы и девятый выход с-й (с - 1.2" 1) вычислительной ячейки и-й группы соединены с информационным входом устройства, восьмой выход(в+Я-й вычислительной ячейки у-й группы (у - 2.п-1) соединен с вторым информационным входом (2g+1)-й.(g = 1,2 -1) вычислительной ячейки (у+1)-й группы, девятый выход (u+1)-й вычислительной ячейки у-й группы соединен с вторым информационным входом (2g+2)-й вычислительной ячейки (у+1)-й группы, девятый выход первой вычислительной ячейки (m — 1)-й группы соединен с вторым информационным входом второй вычислительной ячейки m-й группы, причем каждая вычислительная ячейка содержит два сдвиговых регистра. Т-триггер, третий коммутатор и элемент задержки, выход которого соединен с входами разрешения записи первого и второго сдвиговых регистров, выход первого сдвигового регистра соединен с информационным входом второго коммутатора, первый выход которого соединен с первым входом первого элемента ИЛИ, выход которого соединен с первым входом элемента сложения по модулю два, второй вход которого соединен с выходом второго сдвигового регистра, первый информационный вход вычислительной ячейки соединен с информационным входом второго сдвигового регистра и первым выходом вычислительной ячейки, второй выход которой соединен с выходом элемента сложения по модулю два. второй вход которого соединен с третьим выходом вычислительной ячейки, восьмой выход которой соединен с первым информационным входом первого коммутатора и вторым информационным входом вычислительной ячейки, выход второго элемента ИЛИ соединен с управляющими входами первого и вто-, рого коммутаторов и с четвертым и пятым выходами вычислительной ячейки, первый вход второго элемента ИЛИ соединен с первым выходом третьего коммутатора, информационный вход которого соединен с первым тактовым входом вычислительной ячейки, второй тактовый вход которой соединен с входами разрешения сдвига первого и второго сдвиговых регистров. входом элемента задержки и с шестым и седьмым выходами вычислительной ячейки, вход задания режима и.девятый выход которой соединены соответственно с управляющим входом третьего коммутатора и выходом элемента сложения по модулю два, второй выход третьего коммутатора соединен с входом Т-триггера, выход которого соединен с вторым входом второго элемента ИЛИ, второй выход второго коммутатора соединен с вторым информационным входом первого коммутатора. первый и второй выходы которого соединены соответственно с вторым входом первого элемента ИЛИ и информационным входом первого сдвигового регистра, 1777132 Таблица l Полный булев диооеренциал Переменные дифференциалы перемен ных I х! I ° 2 dx< dxI Таблица 2 Номер выхода, на который передается сигнал Логический уровень сигнала на управляющем входе коммутатора Второй коммутатор Третин коммутатор Первый коммутатор Вход 30 Вход 23 Вход 35 Вход 39 Выход 42 Выход 41 Ниэкий (лог.0). Высокий (лог.l.) Выход 34 - Выход 37 ! Выход 33 Выход 34 Выход 38 Такты конвейера ячейки первый (2j-1) 2 +1 (2j-1) 2 +2 (2j-1) 2" +2 2j г»- +! 2j 2" +2 Загрузка регистра 10 только для 1 k 22" .к (Хp) (0) у ()IP) (I ) Яагруэка регистров 9и 10 ° ° 2! 2 +2 (2j+1) 2 + (2j+1) 2 +2 ° ° у(т) (2 -1) ° ° ° (23+1)2" +2" (2j+2) 2 +1 (2j+2) 2 +2 у(УР) (2" ) М (2 +1) (2j+2) 2 +2 ° ° ° у (" (2" " ) (2j+2 ) 2 +1 (г)+2 ) г" +! ° ° „(lIp) (2л-I ) у (М (2 +1) (2j+2 )2" +г"- у (" 1 (2 !) 0 0 0 0 1 1 1 1 I 0 0 1 1 0 0 1 0 1 0 1 0 1 0 1 1 1 О 0 0 0 0 0 0 1 0 1 1 1 0 Табли.ц Режим работы 1 -й вычислительной ! 24 lакты работы Вход устрой стеа )г! г г Солериимое регистров Вход <)Х I" <) Вход <)х (гс1 Вход Л (<1) ! « Х <0) <оl I о) (0l О О О 0 х(<0) X(!) <о) О О О 0, <о) (0) Х, (г! О О „ (0) О О Х(!) ,(0) Х Х Х О О „ <г! Х
0 (о) (г! О X(s), (г! Х <
Х(51 ,О), (01 Х ,< (41 Х(0, (0) X<9) (41 Х(!1 Х(!) (01 (
Y 10) ISl (!! (4) ((! Х (0l Х Х<4) Х(%! Х
Х (4) Х(<1 Ч < .! О Х(! Х01 О Х Х. Х«! Х(гl „(т) Х <4! О Х О Х (11 10 (ь) О! Х (41, <0) О, (т) ° (C1 Х(т! Х(! О О X< О О „<т) (4) О О О <01 О „ (т) . I4) О О О О О О х(О (о) О Х .Х(0 X(0) О Х(Ы (гl X i<1 Х (0), (1) х (г) Х Х<) Х (0) х (31 Х <г) Х< ) Х (<1 <ы Х (01 Х X I4I XО) О О О ( О О Х(г) Х (0) 0 (%) Х Х Х Х< ) Х(» ХВ» X( Х ) Х(!. X(И ((г! Х (01 X(4! X(0 Х Х <(! Х 1777132 Вычислительная ячейка Содериимое регистров (4) <4! Ч Ч Х<<1,(<41 „ r0I < т! 0 О « ISI ь (т) Таблица 4 CO!IeP«««Oe РЕГИстрое х (" х < т) 20 I 21 О О 1.:Г 7- Cl Ьи 2-а ma аобый f-й та Вый Ь pPpQlM02 ъ ъ 3- 0 Асхад Я-У Pheon 7-й выход 5-У &@ 1777132 о о о о dA-,(O> х" е х") хо>е хо) х" е x("") х("е х (3 Фх (1) dX х" x "e х") х" е х") x(o) е x(2) хо} dx ) х "> х(з) хне хУ) X(00)9 Х(З) ХО1 Е <(2) х(1) е х") х(" е х(з) dХ - (з),7(х рх Э 0 Х х ,х )» Составитель И.Колодиева Техред M.Ìîðãåíòàë Корректор Н.Милюкова Редактор Г.Бельская Заказ 4122 Тираж Подписное ВНИИПИ Государственного ком : -ета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж-35, Раушская наб., 4/5 Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина. 101
