Устройство для вычисления булевых производных

(51) 4 3ИМАЯ) о 1)А НИ ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ ПИСАНИЕ ИЗ А ВТОРСКОМУ СВИДЕТЕЛЬСТВ(71) Днепропетровский государственный университет им. 300-летия воссоединения Украины с Россией(56) Авторское свидетельство СССР У 940166, кл, С 06 Р 15/31, 1980.Авторское свидетельство СССР У 1277089, кл. С 06 Р 7/00, 1985.Авторское свидетельство СССР У 1128263 э клф С 06 Р 15/31 ъ 1982(54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ БУЛЕВЫХ ПРОИЗВОДНЫХ(57) Изобретение относится к области автоматики и вычислительной техники и может быть использовано при построении систем тестового и аппаратурно-, го контроля цифровых устройств. Цель изобретения состоит в расширении функциональных возможностей за счет ориентированного и неориентированного дифференцирования булевой функции попеременным (1 = 1, и, где и - число переменных), Устройство содержит две группы входов 1, 2, два коммутатора 3, 4, группу элементов НЕРАВНОЗНАЧНОСТЬ 5, дна сдвиговых регистра6, 7, блок вычислений 8, блок памяти 9. На группы входов подаются соответственно вектор истинности и двоичный код, эапис )ваемый в сдвиговые регистры, который определяет для каждойпеременной необходимость дифференцирования, а также тип производной,Полный цикл функционирования устройства составляет и тактон (и - числопеременных). Счетчик хранит номер текущего такта и управляет работой первого коммутатора, на выходах которого в первом такте имеет место вектористинности, а в последующих тактах - дпреобразованный вектор с выходов бло" Жка памяти. Преобразования осуществляются группой элементов НЕРАВНОЗНАЧНОСТЬ, если дифференцирование неориентированное, и блоком вычислений,если производная по данной переменной ориентирована. Выбор соответствующих сигналов с целью записи вблок памяти производится вторым коммутатором под управлением двоичногокода с выходов сдвигоных регистров.3 з.п. ф-лы, 6 ил.1370651 50Группа 5 элементов НЕРАВНОЗНАЧ- функции Е(Х), где Х = хНОСТЬ состоит из 2 " сумматоров по по переменной х называетс7модулю два 55, - определяемая по формуле:с й (Х)х,д Г(Х)Производная характеризуетд х,изменение Функции Г(Х) при изменениипеременной х и равна единице на тех Изобретение относится к автоматике и вычислительной технике и можетбыть использовано при построении систем тестового и аппаратуиного контроля цифровых устройств,Цель изобретения - расширениефункциональных воэможностей за счеториентированного и неориентированногодифференцирования булевой функции попеременным (1 = 1, и, где и - количество переменных),На фиг. 1 приведена функциональная схема устройства для вычислениябулевых производных; на фиг. 2 - 6 -схемы блока памяти, первого коммутатора, группы элементов НЕРАВНОЗНАЧНОСТЬ, блока вычислений и второгокоммутатора соответственно.Устройство для вычисления буленыхпроизводных содержит группы 1 и 2входов, коммутаторы 3 и 4, группу 5элементов НЕРАВНОЗНАЧНОСТЬ, сдвиговые регистры 6 и 7, блок 8 вычислений, блок 9 памяти, счетчик 10 по модулю и, тактовый вход 11 устройстваи вход 12 установки в исходное состояние.Блок 9 памяти включает в себя 2П-триггеров 9 9 , 9 9 , "оединенных по входам синхронизации ивходам установки н нулевое состояние.Первый коммутатор 3 содержит 2"мультиплексоров 3,32, 1. 1 ои 1адресных входов которых подключейы кшине 13 (1" 1 - знак округления доближайшего целого числа), Первыеинформационные входы мультиплексоровобразуют первую группу информационных входов 14,14 ь коммутатора 3. Остальные информационныевходы каждого мультиплексора, числокоторых составляет по меньшей мереи, подключены к соответствующемувходу второй группы 15.,15 п информационных входов коммутатора 3,Выходы 16,16мультиплексоров3 ,. ,3являются выходами комму 9 1татора 3. Блок 8 вычислений содержит 2 злементов НЕ 17 17н 2 " элемен 1тов И 18,18 ,. Каждый из нходов19119 блока 8 вычислений подключен к входу соПвахствующего элемента И 18, ( = 1, 2") и через элемент НЕ 17; ко входу элемента И 18.(18), если- нечетное (1 - чет 1 О ное). Выходы 20,20 и-нечетнь 1 хи выходы 2121 ь- четных элементов И 18 .18 и образуют соответственно первую и вторую группывыходов блока 8 вычислений.15 Второй коммутатор 4 содержит 2"мультиплексоров 44 , адресныевходы которых соединены с управляющими входами 22 и 22коммутатора4. Выходами 23 23 ь коммутатоУЭ20 ра 4 являются выходы соответствующихмультиплексоров 4 4Управление устройством осуществляется с помощью двух сдвиговых регистров 6 и 7, По группе входов 2 насдниговые регистры подаются управляю-.щие сигналы й иЬ. Четные Ьвеличины поступают на параллельныевходы сдвигового регистра 6, нечетныеЬ - на соотнетствующие входы реги 30 стра 7 (1 = 1, и). Согласно кодовойкомбинации (Ь , Ь .,), хранимой в1-м разрядерегистров, устройство выполняет следующие преобразования булевой функции:00 - по переменной х, (1 = 1, и)булева функция не дифференцируется;01 - булева функция дифференцируется неориентированно;40 10 - булева функция дифференцируется ориентированно .науменьшение;11 - булева функция дифференцируется ориентированно на45 увеличение.Рассмотрим алгоритм вычисления булевых производных, реализуемых устройством,д Е(х)Производной от булевой3 х,х )1я функция,входных наборах, на которых изменениепеременной хприводит к изменениюфункции,(2) Е(1,1)Е(0) Е(1) Ориентированные булевы производныед Г(Х) дГ(Х)и характеризуютд х1не только изменение, но и направление Г(хх 0 хх3 Гх)) рр 1 б.)р р 11 р 1дх,и равна единице на тех входных наборах, на которых функция Г(Х) возрастает (убывает) с возрастанием (убыванием) переменной х.,1РУ (х)(хх О хд х РР 1 в)Р Р1 и равна единице на тех входных наборах, на которых функция Е(Х) возрастает (убывает) с убыванием (возрастанием) переменной хВычисление производных по всем или несольким переменным булевой функции можно рассматривать как ее преобразование с помощью произведения п операторов:рЧгде зс дифференцирует Г (Х) только по меременной хПри и = 1 оператор д представим единичной матрицей: если булева функция не дифференцируется, а также матрицей: если дифференцирование неориентированно.В случае ориентированного дифференцирования оператор Ч являясь нелинейным, может быть представлен сигнальными графами вида: Г(0) - С-.-О --Г(0) Й Г(1) Г (0) Г(1) изменения функции Е(Х) при изменениипеременной х,.3 Г (Х)Воэрастан)щая производная3 хле определяется по форму Убывающая производная опд Г(Х) 10 дх1ределяется по формуле:,х) Г(х 1 зххх ) где через ч и О обозначены операцииинвертирования и логического умножения,Эти сигнальные графы реализуются20 при вычислении возрастающей и убывающей производных соответственно,11 ри и = 2 оператор д (1 = 1, 2)1представим матрицами: 1 О) если булева функция соответственно не дифференцируется или дифференциЗ 5 руется неориентированно (остальнымиэлементами этих матриц являются нули). Вычисление возрастающей и убываю 40 щей производной по переменной х; (1= 1, 2) задается сигнальными графами: Г(0,0 - О 9 Г(0,0) 45 Г(0, 1) Г(1,0) й(1,0) Г(0,0) Г(1,1) Г(1,0) Е(0,0)0 Г(0,0) Е(0, 1) Г(1,0)1370651 При п3 матрицы Вйчисление возрастающей и убыва)ощей производных по переменной х. (1 = 1, 3) задается следующими сигнальными графами: К(0,0,0) (0,0,1)(0,1,0) Г(0,1,)оо задается и неорие тсутствие диффтированное диффиной х (ь = 1ентами этих матр ренцированияренцирование 2 О3) (остальиц явлются Г (1,О,(1,1,) О) К(1,1 Расс устройства на левых функций трим раб ычислени ентиренно уменьшение примере от двухП р по перем45 В этом тора истин переменных мер 1, имо диффере на увеличен Булеву функцию ировать ориен е по перемени еобхо ованн ся следующим Е (0,0) Е (1,О К(0,0) Е(1,0) Г(1,ов 2 на т н сдвиговые правляющи руппе в ы 6 и 7 сигналы ЬЬ, поступаю Ь, . Величины Ь араллельные входы) учае преобразование векти Г(х , х ) описываетграфом:дов под тор Инф 233 информ и запи одов 23, 23,а 4 подается наы блока 9 памятго по окончании ация скоммутонные в в не ыва е в такта сдвигового регистра 6, а Ь , Л, - назсоответствующие входы сдвигового регистра 7. На выходах регистров 6 и 7в первом такте присутствуют сигналыЬ, Ь, а во втором такте - Ь, 11соответственно. Для того, чтобы булеву функцию дифференцировать ориентированно на увеличение по переменнойх, и ориентированно на уменьшениепо переменной х 2, на группу входов 2подается кодовая комбинация Ь = 1ЭЯ-По входу 12 поступает сигнал,который устанавливает счетчик 10 иблок 9 памяти в нулевое состояние,а также разрешает запись в сдвиговыерегистры 6 и 7 кодовой комбинации,присутствующей на группе входов 2.С группы входов 1 на первые информационные входы 14 , 14 , 14,14 коммутатора 3 подаются сигналыК(0,0), К(0,1), К(1,0), Г(1,), определяющие заданную булеву функцию,В первом такте с выходов счетчика 1 О по шине 3 на адресные входымультиплексоров 3 , 3 , 3 , 3 по 1ступает кодовая комбийация 00, Врезультате величины Г(0,0), Г(0,1),Й(1,0), Г(1,1) передаются на выходы 3016 16 , 16 , 16 коммутатора 3.Сигналы с выходов 16 , 16 , 16,16 поступают на группу входов 19блока 8 вычислений, который формирует на выходах 21 и 21 величиныК(О,О) К(0,1) и"К(1,0) К(1,1) соответственноСигналы с выхо 21 и 21 блока 8 вычислений аются на входы27 и 27 2 коммута а 4С выходов 40сдвиговых регистров 6 и 7 через входы 22 и 22 на адресные входы муль 1 2типлексоров 4, 4, 4, 4 поступаютсигналы Ь = 1, Ь = 1. Благодаряэтому информация с четвертых информа 4ционных входов мультиплексоров 41,4, 4 З, 4 передается на их выходы.В результате на выходах 23, 232,233, 23 коммутатора 4 присутствуютсоответственно сигналы Г(0,0) Е(0,1),Е(1,0) й(1,1), Г(0,0) Е(0,1),Е(1,0) й(1,1), описываемые выражением (3).В результате на выходах устройства, а следовательно, и на входах 1515 , 5 , 5 появляются сигналы Г(0,0) Г(0,1), Г(1,0)Е(1,1), Г(О,О) К(0,1), Т(1 О) К(1,1) соответственно, описываемые результирующим вектором из (3).По заднему фронту синхроимпульса с входа 11 счетчик 10 переводится в состояние "01", а в сдвиговых регистрах 6 и 7 происходит сдвиг содержимого в сторону младших разрядов,Во втором такте коммутатора 3 по шине 13 передается кодовая комбинация "01", Благодаря этому сигналы Г(0,0)Г(0,1), Г 1,0) Г(1,1), Г(0,0) Г(0,1), Г(1,0)Г(,1), присутствующие на входах 15 , 15215., 15 поступают на группу выходов 16 коммутатора 3.С выходов 16 16 , 16 , 16 сигналы поступают на группу входов 19 блока 8 вычислений. В результате преобразований на выходах 20, и 202 прив. У,п) ,.1(,О) (, ).Сигналы с выходов 20, и 20 блока 8 вычислений передаются на входы 261 и 26, коммутатора 4, с выходов сдвиговых регистров 6 и 7 через входы 22, и 22 на адресные входы мультиплексоров 4, 4, 4, 4 поступают сигналы Ь= 1, 1, = О, В результате величина Г(0, 0) Е (0,1) Е (1, 0) Г (1, ) с входов 26 и 262 передается на выходы мультиплексоров 4 1, 4 2, 4., 4 , На выходах 231, 232, 23 23 коммутатора 4 присутствует одна и та же величина Г(0,0) Г(0,1)Г(1,0) Г(1,1), сформированная в соответствии с выражением (7).Информация, переданная с группы выходов 23 коммутатора 4, присутствует на информационных входах блока 9 памяти и записывается в него по заднему фронту синхроимпульса с входа . Следовательно, сигналы, присутствующие на выходе устройства, тождественны величинам, получаемым согласно выражению (7).П р и м е р 2. Булева функция дифференцируется неориентированно по переменной х 1 и не дифференцируется по переменной х 2В процессе неориентированного дифференцирования по переменной х, вектор истинности 1(х , х ) преобразует 2 1ся следующим образом:(9) Отсутствию дифференцирования похсоответствует следующее преобраВыполнение преобразования вектораистинности Г(х , х,) с помощью предлагаемого устройства для вычислениябулевых производных,По входу 12 поступает сигнал, который устанавливает счетчик 10 иблок 9 памяти в нулевое состояние, атакже разрешает запись в сдвиговыерегистры 6 и 7 кодовой комбинациий = 1, 113 = О, Ь = О, Ь = О Напервые информационные входы коммутатора 3 через группу входов 14 подаются сигналы Е(0)0 Г(0)1 Г(1)0Г(1)1),В первом такте с выходов счетчика10 по шине 13 на адресные входы мультиплексоров 3 3 , 3., 3 поступает кодовая комбинация 00 . В результате информация с первых информационных входов подается на выходы 1616 , 16 ,. 16 коммутатора 3.дов 6 6 6) 64 сигналы Г(0)0 Е(0) Г(1)0 Е(1)1)поступают на входы группы элементовНЕРАВНОЗНАЧНОСТЬ 5.В результате преобразований навыходе этой группы присутствуют величины Г (0,0) Г(0, 1), Г(1,0) И Г(1, 1),которые поступают на группу входов24 коммутатора 4.С выходов сдвиговых регистров 6 и7 через входы 22 и 22 на адресныевходы мультиплексоров 4,) 4 ) 4 ) 4поступают сигналы Ь = 1, Ь = О.Благодаря этому информацйя с четвер 1 ъ 1 х информационных входов мультиплексоров 4 , 4 , 4, 4 передаетсяна их выходы, На выходах 23 , 231 Озование вектора, полученного в (8): 23 , 23, коммутатора 4 присутствуютсигналы соответственно Г(0)0) 9 Г(0)1)Г(1, 0) О К (1, 1), Г(0,0) 9 Г(0, 1),25 Й (1, 0) И Й (1, 1), которые формируютсясогласно выражению (8) .Сигналы с группы выходов 23 мультиплексоров 4 , 4 , 4 , 44 подаются1)на информационные входы блока 9 памяти, По заднему фронту синхроимпульса сигналы с информационных входовблока памяти 9 записываются в триггеры 91, 9) 9) 9, В результате навыходе устройства и на группе входов15 коммутатора 3 имеются соответст 35венно сигналы Г(0)0) О+6(0)1 Е(1)0)0+Ой(1,1), Г(О,О)О+1(0,1), й(1,0)ЭИ Г(1) 1),По окончании такта счетчик О переводится в состояние "01", а всдвиговых регистрах 6 и 7 происходитсдвиг содержимого влево наразряд,Во втором такте с выходов счетчика 1 О на управляющие входы коммута 45тора 3 по шине 13 передается кодоваякомбинация "01". Следовательно, сигналы Г(0)0)Я Г(0)1 Г(1)0)О+ Г(1)1),й(0,0) О+ Е(0,1), Е(1,0) О+ Е(1,1), присутствующие на группе входов 15, через вторую группу информационных входов коммутатора 3 передаются на еговыходы 16, 162) 1 бз) 64 .С группы вйходов 16 сигналый(0,0) О+ Е(0)1), Г(1)0)О+ Г(1)1),й(0)0) О+1(0)1 й(1)0)0+ й (1,1) поступают на входы 25, 25, 25, 254коммутатора 4,2С выходов сдвиговых регистров 6и 7 через входы 22 и 22 на управ 9ляющие входы коммутатора 4 поступают сигналы Ь= О, и, = О. В результате информация с первых информационных входов передается на выходы муль 5типлексоров 4 , 4 , 4 , 4 . На выходах 23 , 23 , 23 , 23, коммутатора 4присутствуют соответственно сигналыГ(0,0)0+ Г(0,1), й(0,0)9 Г(0,1),Е(1,0) 0+1(1,1), Г(1,0) Я Г(1, 1), которые тождественны величинам, полученным согласно выражению (9),Информация, переданная с группывыходов 23 коммутатора 4, присутствует на информационных входах блока 15памяти 9 и записывается в триггеры9 9, 9 З, 94 с приходом синхроимпульса по входу 11.Сигналы, поступающие на выход устройства, тождественны величинам, полученным согласно выражению (9).Формула изобретения251, Устройство для вычисления булевых производных, содержащее первый и второй сдвиговые регистры, первый и второй коммутаторы, групчу элементов НЕРАВНОЗНАЧНОСТЬ и блок вычислений, 30 причем первая группа входов устройства соединена с информационными входами первой группы первого коммутатора, выходы которого соединены с входами блока вычислений, выходы элементов НЕРАВНОЗНАЧНОСТЬ группы соединены с информационными входами первой группы второго коммутатора, тактовый вход устройства соединен с тактовыми входами первого и второго сдвиговых 40 регистров, о т л и ч а ю щ е е с я тем, что, с целью расширения функциойальных возможностей за счет ориентированного и неориентированного дифференцирования булевой функции по Е переменным (к = 1, и, где и - количество переменных), в него введены блок памяти и счетчик, причем выходы первого коммутатора соединены попарно с входами элементов НЕРАВНОЗНАЧНОСТЬ группы и информационными входами второй группы второго коммутатора, информационные входы третьей и четвертой групп которого соединены с выходами первой и второй групп блока55 вычислений с оотв етс тв енио выходы второго коммутатора соединены с информационными входами блока памяти,выходы которого соединены с выходами устроиства и информационными входамивторой группы первого коммутатора,управляющие входы которого соединеныс выходами счетчика, тактовый входкоторого соединен с тактовым входомустройства и тактовым входом блокапамяти, вход сброса которого соединен с входом сброса счетчика, входомустановки начального состояния устройства и входами установки начального состояния первого и второгосдвиговых регистров, информационньевходы которых соединены с входамивторой группы устройства, выходы первого и второго сдвиговых регистровсоединены с управляющими входамивторого коммутатора.2, Устройство по п. 1, о т л и -ч а ю щ е е с я тем, что первый коммутатор содержит 2 мультиплексоров,причем первый информационный входд-го мультиплексора (д = 1, 2") соединен с -м информационным входомпервой группы первого коммутатора,с второго по (и)-й информационныевходы 1-го мультиплексора объединеныи соединены с д-м информационным входом второй группы коммутатора, управляющие входы которого соединеныс управляющими входами мультиплексоров, выходы которых явдяются выходами первого коммутатора,3. Устройство по п. 1, о т л ич а ю щ е е с я тем, что второйкоммутатор содержит 2 " мультиплексоров, причем управляющие входы второго коммутатора соединены с управляющими входами мультиплексоров, первыеинформационные входы с первого по2 "-й мультиплексоров и с (2 ++ 1)-го по 2 -й мультиплексоров соединены с нечетньии и четными информационными входами второй группы второго коммутатора, информационные входы первой, третьей и четвертой группкоторого соединены соответственно свторыми, третьими и четвертыми информационными входами мультиплексоров, выходы которых являются выходами второго коммутатора. 4, Устройство по и. 1, о т л и - ч а ю щ е е с я тем, что блок вычислений содержит 2 элементов НЕ и н2 элементов И, причем 1-й вход блока соединен с первым входом -го элемента И и 1-го элемента НЕ, выход (2 ш)-го элемента НЕ (ш = 1, 2 ) соединен с вторым входом 2 пгго элемента И, выход 2 пгго элемента НЕ соединен с вторым входом (2 пг.1) то элемента И, выход (2 пг.1)-го элемента И является 1-м выходом= 1, 2" )первой группы блока, )-й выход второй группы которого соединен с выходом 2 пт-го элемента И.