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

(5)5 3;."Ядц )11 с ЕНИЯ ВТОРСКО ИДЕТЕЛ ЬСТВУ Ъао ТаюЪФ ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯПРИ ГКНТ СССР ОПИСАНИЕ ИЗОБ(71) Минский радиотехнический институт(56) Авторское свидетельство СССРМ 1269146, кл. 6 06 Р 15/31, 1985,Авторское свидетельство СССРМ 1001107, кл. 6 06 Г 15/332, 1982,(54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ БУЛЕВЫХ ДИФФЕРЕНЦИАЛЬНЫХ УРАВНЕНИЙ(57) Изобретение относится к цифровой вычислительной технике и может быть использовано в качестве аппаратной поддержкивычислений в системах автоматизированно.Ы 2, 1661791 А го проектирования цифровых автоматов, при анализе и диагностике комбинационных схем, в системах логического управления роботами-манипуляторами, - гибкими автоматизированными производствами. Цель изобретения - расширение функциональных возможностей за счет решения булевых дифференциальных уравнений. Поставленная цель достигается тем, что устройство содержит 2" блоков 1 управления, где и - число булевых переменных, 2" блоков 2 дешифрации, 2" вычислительных блоков 3 и коммутатор 4. Исходное булевое дифференциальное уравнение, представляемое как система булевых уравнений в форме Жегалкина, решается посредством быстрого дискретного преобразования Фурье в коньюнктивном базисе, 4 ил.Изобретение относится к цифровой вычислительной технике и может быть использовано в качестве аппаратной поддержкивычислений в системах автоматизированного проектирования цифровых автоматов, 5при анализе и диагностике комбинационных схем, в системах логического управления роботами-манипуляторами, гибкимиавтоматизированными производствами.Цель изобретения - расширение функциональных возможностей за счет решениябулевых дифференциальных уравнений,Устройство (фиг. 1) содеожит 2" блоков1 управления, 2" блоков 2 дешифрации, 2"вычислительных блоков 3 и коммутатор 4, 15Каждый блок 1 управления (фиг. 2) содержитпервый 5 и второй 6 триггеры и элемент И 7,Каждый блок 2 дешифрации (фиг. 3) содержит дешифратор 8, регистры 9, элементы И10 первой группы, элементы И 11 второй 20группы и элемент ИЛИ 12. Каждый вычислительный блок 3 (фиг, 4) содержит сумматор13 по модулю два, элементы И 14, сдвигающие регистры 15, первый 16 и второй 17элементы ИЛИ и элемент 18 задержки. 25Устройство имеет следующий алгоритмработы.На первом этапе выполняют усеченноедискретное преобразование фурье в коньюнктивном базисе согласно матричному соотношению;Х = К 2 Р п (л)ос 12),где Р " - матрица дифференцирования35размерности 2"х 2", формируемая по соотношениюр л =, ,)2 21 1 4 " , = 1,п,40ГдЕ 1 1 ИлЕДИНИЧНЫЕ МатрИцЫ раэмерностей 2 х 2 и 2" х 2"соответственно;Ж - символ кронекеровского произведения матриц, причем при умножении 45матрицы Р " и вектора Хиспользуются операции конъюнкции и суммирования по модулю два.п 2 л 50Матрица К размерности 2 х 2 формируется из матрицы конъюнктивного преп г"образования К размерности 2 х 2путем выделения столбцов с номерами2 - (т=0,2"-1) и удаления остальных:К, = К, - 1 бГКт; На втором этапе над векторами Х" системы Х выполняется операция поэлементной дизъюнкции, В итоге получают вектор решения Х (как результат объединения ре-, шений отдельных уравнений системы).На третьем этапе алгоритма определяют нулевые элементы вектора решений Х и соответствующие им наборы переменныхПф),Х,Х ", являющиеся коэффициентами векторов значенийХ: (О) Х)искомых булевых функций 1(Х).Функционирование 1-го блока 1 управления (1=1,2") рассмотрим на примере блока 11 управленияВ момент времени 10 на счетный вход триггера 5 поступает тактовый импульс и на выходе триггера 5 формируется уровень логического "0", Он передается с выхода триггера 5 на первый вход элемента И 7 и на третий выход блока 11. В момент времени то на вход установки в "1" триггера 6 поступает высокий логический уровень сигнала и на выходе триггера 6 формируется уровень логической "1", который передается на второй выход блока 11. Сигнал высокого уровня подается на второй вход элемента И 7, с выхода которого низкий логический уровень сигнала передается на четвертый выход блока 11,В момент времени 11 на счетный вход триггера 5 поступает тактовый импульс, который устанавливает триггер 5 в состояние логической "1". С выхода триггера 5 высокий логический уровень сигнала поступает на первый вход элемента И 7 и на третий выход блока 11. В момент времени 11 на второй вход элемента И 7 поступает высокий логический уровень сигнала, с выхода элемента И 7 этот сигнал передается на вход установки в "0" триггера 6 и на четвертый выход блока 11, На выходе триггера 6 устанавливается низкий логический уровень сигнала, который передается на второй выход блока 11и(он сохраняется на нем по 2 -й такт включительно),На третьем такте (момент времени тз) в схеме происходят те же переключения, что и на первом такте, за исключением того, что на вход установки в "1" триггера 6 сигнал не поступает. На четвертом, пятом и т.д. по22 -й такт включительно блок 11 функционирует так же, как на втором и третьем, однако при этом на второй вход элемента И 7 поступает низкий логический уровень сигнала.Функционирование блока 12 отличается лишь тем, что на его тактовый вход поступа 1661791 6ют сигналы, которые формируются на первом выходе блока 11.Процесс функционирования блока 2 осуществляется следующим образом; на тактах с первого по 2"-й выполняется загрузка элесРбб() Его столбца матрицы преобразования Е 2 п, так что на К-м (К=1,2") такте загружается элемент бф. Этот элемент передается на выход на соответствуютих тактах работы устройства (элемент б"на тактах с (2 +1)-го по 2 -й), Процесс завершается на 2 -мтакК п те,На первом такте на входы с первого по 2"-й дешифратора 8 поступает код 0,0,.,0. В результате на первом выходе дешифратора 8 формируется высокий логический уровень сигнала, который передается на первый вход элемента И 101, на второй вход которого поступает тактовый импульс. В результате импульс записи с выхода элемента И 101 передается на вход записи считывания регистра 191, на информационный входО,-1)которого поступает элемент б1-го столбца матрицы преобразования Е 2", На этом такте на выход блока через элемент ИЛИ 12 с выхода элемента И 11 к (на его втором входе - низкий логический уровень сигнала) передается низкий логический уровень сигнала.На втором такте (момент времени 11) на входы с первого по 2"-й дешифратора 8 поступает код 1,00. В результате на втором выходе дешифратора 8 формируется высокий логический уровень сигнала, который передается на первый вход элемента И 102. При этом на его второй вход поступает тактовый импульс, он передается на вход записи региСтра 92, на информационный вход кото 0 ого поступает следующий элемент б"1-гостолбцаматрицы преобразования Е 2". На этом такте на выход блока через элемент И 111(на его втором входе - высокий логический уровень сигнала) и элемент ИЛИ 12 передается содержимое регистра 91-бф(на остальных входах элемента ИЛИ 12 - сигналы логического "О").Наконец, нэ 2"-м такте работы устройства 2"-й элемент б( 1 ) 1-го столбца матрицы преобразования Е 2" записывается в 2"-й регистр 9, При этом элементы с выходов регистров 9 к(К=1,2 ) передаются на выход блока со следующей последовательнссти: на третьем и четвертом тактах -б, на пятом-восьмом ит,д., так что К-й элемент б() 1-го столбца матрицы преобразования Е 2 п передается на выход блока 2с (2 +1)-го такта по 2 -й такт включительно.Функционирование вычислительногоблока 3 рассмотрим на примере вычислительного блока 31.На первом такте (момент времени 10) навторые входы элементов И ,4 к поступаеткод 0,00, В результате с выходов элементов И 14 к низкий логический уровень сигнала передается на входы элемента ИЛИ 17. Свыхода элемента ИЛИ 17 низкий логическийуровень сигнала передается на второй входсумматора 13 по модулю два, на первый15 вход которого поступает сигнал логическогоО . В этот момент времени 10 по сигналусдвига в регистрах 15 к выполняется сдвигсодержимого на один разряд влево (в сторону старших разрядов), По сигналу, поступающему на вход записи/считываниярегистров 15 к через 0,5 такта осуществляется запись этого содержимого в регистры 15 к(в первый регистр записывается результатсуммирования по модулю двэ - логический"0", который поступаеттакже на второй входэлемента ИЛИ 16). В результате на выходеэлемента ИЛИ 16 формируется результат(логический "0"), который передается на выход блока 31.На втором такте(момент времени 11) навторые входы элементов И 14 к поступаеткод 1,0,0. В результате на выход элементаИ 141, а затем на первый вход элемента ИЛИ17 передается содержимое регистра 151, Свыхода элемента ИЛИ 17 содержимое регистра 151(логический "0") передается на второй вход сумматора 13 по модулю два. Наего первый вход поступает элемент Опервого столбца матрицы преобразованияЕ 2 П. В этот момент времени т 1 по сигналусдвига в регистрах 15 к выполняется сдвигсодержимого на один разряд влево (в сторону старших разрядов), По сигналу, по 45 ступающему на вход записи/считываниярегистра 15 к через 0,5 такта с выхода элемента 18 задержки, осуществляется запись этого содержимого в регистры 15 к,При этом в первый регистр записываетсярезультат суммирования по модулю два(офк) О), Кроме того, он поступает такжена второй вход элемента ИЛИ 16. В результате на выходе элемента ИЛИ 16 формируется результат б, который передается навыход блока 31,2 пНа третьем и последующих (по 2 -й)тактах блок 31 функционирует, как и на втором, При этом элементе б(К=0,2") первого столбца матрицы преобразования Е "поступают на второй информационный вход блока 3 в такой последовательности; на(к-,о)матрицы преобразования Р 2" поступает с (2 +1)-го такта по 2"-й такты включительно.функционирование блока 32 отличается от функционирования блока 3 тем, что на его первый информационный вход сигналы поступают с выхода блока 3, а на второй информационный вход блока 32 поступают элементы бвторого столбца матрицы преобразования Р 2". На выход блока 3 передаются результаты, формируемые на выходе его элемента ИЛИ 16. Формула изобретения Устройство для решения булевых дифференциальных уравнений, содержащее с первого по и-й вычислительные блоки, где и - число булевых переменных, с первого по и-й блоки управления и с первого по п-й блоки дешифрации, при этом тактовый вход устройства подключен к тактовому входу первого блока управления, первый выход 1-го блока управления (где 1=1п - 1) подключен к тактовому входу (1+1)-го блока управления, вход нулевого потенциала устройства подключен к первому информационному входу первого вычислительного блока, выход 1-го вычислительного блока подключен к первому информационному входу (1+1)-го вычислительного блока, первый информационный вход устройства подключен к информационному входу первого блока дешифрации, выход)-го блока дешифрации (где )=1, .и) подключен к второму информационному входу)-го вычислительного блока, отлича ющее с я тем; что, с целью расширения функциональных возможностей за счет решения булевых дифференциальных уравнений, устройство содержит с (и+1)-го по.2"-й блок управления, с (и+ 1)-го по 2"-й блок дешифрации, с (и+1)-го по 2"-й вычислительный блок и коммутатор, причем первый выход К-го блока управления (где К=п, 2"-1) подключен к тактовому входу (К+1)-го блока управления, первый выход 2"- го блока управления подключен к первым входам режима всех блоков управления, вход единичного потенциала устройства подключен к второму входу режима 2"-го блока управления, второй вход режима Ь-го блока управления (где Ь= 12"-1) подключен к второму выходу (Ь+ 1)-го блока управления, второй выход первого блока управления подключен к выходу признака такта устройства, выход К-го вычислительного блока подключен к первому информационному входу (К+ 1)-го вычислительного блока, выход с-го блока дешифрации (где 5 с=п+12") подключен к второму информационному входу с-го вычислительного блока, выход 2"-го вычислительного блока подключен к управляющему входу коммутатора, выходы которого подключены соответ ственно к информационным выходамустройства, информационные входы которого с второго по 2"-й подключены соответственно к информационным входам блоков дешифрации с второго по 2"-й, 1-й тактовый 15 вход группы устройства (где 1=12") подключен к тактовым входам 1-го блока дешифрации и 1-го вычислительного блока, третьи выходы блоков управления с первого по 2"-й подключены соответственно к инфор мационным входам с первого по 2"-й первойгруппы всех блоков дешифрации и к информационным входам с первого по 2"-й коммутатора,четвертые выходы блоков управления с первого по 2"-й подключены 25 соответственно к информационным входамс первого по 2"-й второй группы всех блоков дешифрации и к информационным входам с первого по 2"-й группы всех вычислительных блоков, при этом каждый блок управле ния содержит два триггера и элемент И,причем в каждом блоке управления тактовый вход блока управления, первый и второй входы режима блока управления подключены соответственно к счетному вхо ду первого триггера, к входу установки в "1"второго триггера и к первому входу элемента И, выход первого триггера подключен к первому выходу блока управления, к второму входу элемента И и к третьему выходу 40 блока управления, выход элемента И подключен к четвертому выходу блока управления и к входу установки в "0" второго триггера, выход которого подключен к второму выходу блока управления, при этом 45 каждый вычислительный блок соержит дваэлемента ИЛИ, 2" элементов И, элемент задержки, сумматор по модулю два и 2" сдвигающих регистров, причем в каждом вычислительном блоке тактовый вход вы числительного блока подключен к входамсдвига всех сдвигающих регистров и к входу элемента задержки, выход которого подключен к входам записи-считывания всех сдвигающих регистров, информационные 55 входы с первого по 2"-й группы вычислительного блока подключены соответственно к первым входам элементов И с первого по 2 -й, первый информационный вход вычислительного блока подключен к первому входу первого элемента ИЛИ, выход которогоподключен к выходу вычислительного блока, второй информационный вход которого подключен к первому входу сумматора по модулю два, выход которого подключен к второму входу первого элемента ИЛИ и к 5 информационному входу первого сдвигающего регистра, выход р-го сдвигающего регистра (где р= 12" - 1) подключен к информационному входу (р+1-го сдвигающего регистра и к второму входу р-го элемента И, 10 выход 2"-го сдвигающего регистра подключен к второму входу 2"-го элемента И, выходы элементов И подключены к входам второго элемента ИЛИ, выход которого подключен к второму входу сумматора по моду лю два, при этом каждый блок дешифрации содержит дешифратор, две группы элементов И, элемент ИЛИ и с первого по 2"-й регистры, причем в каждом блоке дешиф-рации информационные входы первой 20 группы блока дешифрации подключены к входам дешифратора, выходы которого подключены соответственно к первым входам элементов И с первого по 2"-й первой группы, выходы которых подключены соответственно к входам записи-считывания регистров с первого по 2"-й, выходы которых подключены соответственно к первым входам элементов И с первого по 2"-й второй группы, выходы которых подключены к входам элемента ИЛИ, выход которого подключен к выходу блока дешифрации, информационные входы с первого по 2"-й второй группы которого подключены соответственно к вторым входам элементов И с первого по 2"-й второй группы, тактовый вход блока дешифрации подключен к вторым входам элементов И первой группы, информационный вход блока дешифрации подключен к информационным входам всех регистров.1661791 Редактор А, Козор ре Производственно-из аказ 2126 ВНИИПИ Го Составитель В. СмирноТехред М.Моргентал Тираж 413 Подписноерственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж, Раушская наб., 4/5 кий комбинат "Патент", г, Ужгород, ул.Гагарина, 10