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

союз советснихСОЦИАЛИСТИЧЕСНИХ 1 б 1541 СПУБЛИ 7/00 15/31 В ЕСОВЗНАЯсЮ": ЯИЕЯ 3ЯО ТЕ 1 АА ИЗОБР У СВИДЕТЕАТОРС ский инстиайцев 5. 4, 198 о СССР 4, 198 ЕСКОГО ОВАНИЯ ДИФ- БУЛЕсодержблокови блок4 ил. к вычисл х,. К =.хаа бУ Уа а 1к 1 лк 1 к е задают в системе атри в ц"-1) и разГОСУДАРСТВЕННЫЙ НОМИПО ИЗОБРЕТЕНИЯМ И ОТНРЬГГПРИ ГННТ СССР(54) УСТРОЙСТВО ДЛЯ ЛОГИЧФЕРЕНЦИРОВАНИЯ И ИНТЕГРИРВЫХ ФУНКЦИЙ(57) Устройство относитс Изобретение относится к вычислительной технике и может быть использовано для аппаратной поддержки вычислений в системах анализа, синтеза и контроля цифровых автоматов, исследования переходных процессов в схемах, сжатия данных, синтеза топологии БИС, обработки изображений.Сущность изобретения заключается в логической обработке систем булевых функций на основе использования кон-. вейерных принципов обработки данных.В основу изобретения положены следующие математические модели функционирования компонентов и устройства Пусть система булевых функци й (х) - й (х , х х ) (1-О переменных представлена матриц 2тельной технике и может быть испбльзовано для аппаратной поддержки вычислений в системах анализа, синтеза и контроля цифровых автоматов, исследования переходных процессов в схемах сжатия данных синтеза топологии БИС, обработки изображений. Целью изобретения является расширение функциональных возможностей за счет вычисления логических производных и интегралов систем булевых функций. Цель изобретения достигается тем, что устройствоит генератор импульсов, гРуппувычислений, блок ввода данныхвывода данных. 3 з.п.ф-лы,ости 2"к 2 " их векторов эначен ординат х и у, где х - координата изменения индекса д значения хфункции Е(х) на наборе (х , х х ),(1 = 0;2 -1), у - координата изменении инДекса б вектоРа х ь в системе Ц = 0,2"-1), Тогда логическая производная системы К булевых функций в матричном виде определяется следующим образом;("-) 45Д(т,х) а("к, (11) С ф 3 л - К 81,К . (т )аГ 2 а" 1." э")к( ) к)--- -(1=- к е к .т. 3 -, (г)а(т,у)где символ " Д+ " обозначает операциюпоэлементного сложения по модулю два,1.- матрица сдвига размерности2 "2", нид которой зависит от значения параметра Т 6 Е, Е = 1, 2"-1 - целые числа, и Формируется по рекуррентному соотношению Из соотношений (1) и (2) следует,что алгоритм логического дифференцирования по координате х позволяет обрабатывать столбцы матрицы К л, а по20координате у - строки матрицы КПредлагаемое техническое решениепозволяет решить и обратную задачу:восстановить исходную систему булевыхФункций (матрицу К ,) по результатулогического дифференцирования. Назовем эту процедуру логическим интегрированием,Логический интеграл системы К ьбулевых функций в матричном виде определяется на основе свойства периодич-.ности логической производной:где ре Е (Е - множество целых положительных чисел).Из свойства (3) следует определение логического интеграла(Ц д(т,у) Очевидно, что для вычисления 1 скратного логического интеграла системы Кдостаточно нычислить ее ("-)с)- кратную производную.Цель изобретения - расширение функ циональных возможностей за счет вычисления логических производных и интегралов систем булевых Функций,На фиг. 1 изображена структурнаясхема устройства, на Фиг. 2 - схемаблока Формиронания последовательностивходных данных; на фиг. 3 - схема блока вычислений на фиг, 4 - схема блока вывода данных,Устройство (фиг. 1) содержит блок1 ввода данных, И блоков 2 вычисленийблок 3 вывода данных и генератор 4импульсов, причем первый информационный нход К-го блока 2 вычисленийподключен к первому выходу К+1-гоблока 2 вычислений (К = 1 М), апервый информационный вход И-го блока вычислений является входом константы нуля устройства, информационныевходы первой группы блока выводаданных подключены к вторым выходамблоков 2 вычислений соответственно,входы синхронизации блока 1 ввода данных и блока 3 вывода данных подключены к выходу генератора импульсов 4,выход блока 3 вывода данных являетсявыходом устройства, информационныйвход, блока 1 ввода данных являетсявходом устройства, входы параметраблоков 1 ввода данных и блока 3 вывода данных являются входами первого ивторого параметров дифференцированияустройства соответственно, вторые информационные входы блоков 2 вычислений подключены к входам первой группыблока 1 ввода информации, третьи информационные входы блоков 2 вычислений подключены к выходам второй группы блока 1 ввода информации, адресныевходы блоков 2 вычислений подключенык выходу адреса блока 1 ввода данных,Блок 1 ввода данных (Фиг.2) содержит счетчик 5, элемент ИЛИ 6, регистр 7 циклического сдвига, коммутатор 8, узел 9 сравнения и регистр 10,причем первый информационный вход коммутатора является информационным входом блока, выходами первой группы которого являются выходы коммутатора 8,информационные входы группы которогоподключены к выходам регистра 7 цикли"ческого сдвига, выходы которого образуют выходы второй группы блока .1. Информационный вход регистра 7 циклического сдвига подключен к выходу элементафИЛИ б, выходы счетчика 5 подклю.чены к входам элемента ИЛИ 6 и первыминформационным входам группы узла 9сравнения, вторые информационные входы группы которого подключены к выходам регистра 10, образующих адресныйвыход блока 1 ввода данных, а входпараметра регистра 10 является входомпараметра блока 1 ввода данных, входсброса счетчика 5 подключен к выходуузла 9 сравнения,Блок 2 вычислений (фиг, 3) содержит первый 11 и второй 12 коммутаторы, регистр 13 и сумматор 14 по модулю два, причем первый информационныйвход первого коммутатора 11 являетсявторым информационным входом блока 2вычислениИ, управляющий вход первого11 коммутатора является третьим информационным входом блока 2 вычислений,второй информационный вход первого 11коммутатора подключен к выходу сумматора 14 по модулю два, первый информационный вход которого является первым информационным входом блока 2 вычислений, выход второго коммутатора12 подключен к второму информационному входу сумматора 14 по модулю два иобразует второй информационный выходблока 2 вычислений, вход адреса второго 12 коммутатора является входомадреса блока 2 вычислений, информационные входы второго 12 коммутатораподключены к выходам регистра 13, выход первого коммутатора 11 подключен к информационному входу регистра13 и образуют первый информационныйвыход блока 2 вычислений.Блок 3 вывода данных (фиг. 4) со-35держит счетчик 15, элемент ИЛИ 1 б,регистр 17 циклического сдвига, коммутатор 18, узел 19 сравнения, регистр20, вход параметра которого являетсявходом параметра блока 3 вывода данных информационные входы первой груптпы узла 19 сравнения годключены к выходам регистра 20, информационныевходы второй группы узла 19 сравненияи входы элемента ИЛИ 16 подключены 45к выходам счетчика 15, управляющийвход которого является входом синхронизации блока 3 вывода данных, входсброса счетчика 15 подключен к выходу узла 19 сравнения, выход элементаИЛИ 1 б подключен к информационномувходу регистра 17 циклического сдвига, выходы которого подключены к информационным входам первой группыкоммутатора 18, информационные входывторой группы коммутатора 18 образуют информационные входы блока 3 вывода данных, а выходы коммутатора 18 -выход блока 3 вывода информации,Рассмотрим функционирование устройства в совокупности составляюших его компонентов. Поясним принцип его работы на конкретном примере.Пусть необходимо выполнить трехкратное дифференцирование (вычислить трехкратную производную) матрицы- ,х 1) х,)7 6евекторов значений х , системы буле-13вых функций Й.,(х).т(х), (х)с параметром Т = 2. Устройство дляданного примера содержит четыре блока 2 вычислений.На первых двух тактах (Т = 2) происходит загрузка регистра 13,первогоблока 2 вычислений данными х х(а) (т)поступающими на первый вход коммутатора 11 (по высокому логическому уровню напряжения на управляющем входе).На третьем и четвертом тактах аналогичным образом происходит загрузкарегистра 13, второго блока 2 вычислений элементами х(," и хпо высокомулогическому уровню напряжения на втором (управляющем) входе коммутатора11. Причем на этих же тактах, а именно на третьем, в регистр 13 первогоблока 2 вычислений поступает сУммавида х(," 6 х( , а на четвертом -(Цх 9 х ) с выхода сумматора 14 помодулю два (по низкому логическомууровню сигнала на втором, управляющемвходе коммутатора 11).Таким образом, по окончании четвертого такта в регистре 13 первогоблока 2 вычислений оказываются значения первых двух элементов у,)= х)йОх(а)и у(,"= х,х, вектора у- у ) у.у) )результата вычисления з К з/а(2 х), а в регистре 13второго блока 2 вычислений значениях и х) вектора х . На пятом иГашестом тактах происходит загрузка третьего блока 2 вычислений и вычисления в первом и втором блоках 2 вычислений,а на седьмом и восьмом тактах - загрузка четвертого вычисления в первомвтором и третьем блоках 2 вычислений.И, наконец, на девятом и десятом тактак на выходе первого блока 2 вычислений формируются соответственно результаты у(а)= х(а) у х)г) и у ( ) (т)о а а аЖ х), на одиннадцатом и двенадцазультаты у (г) х(1541592блока 2 вычислений, на тринадцатом и че- тырнадцатом - результаты у, -х,в х, и у, = х Я х(, на выходе третьего блока 2 вычислений и на пятнадцатом и шестнадцатом гактах - элементы у, = х,1(т) (т)и у, = х, - на выходе четвертого блока 2 вычислений. При этом на девятом такте можно начинать загрузку перваго блока 2 вычислений элемента О ми х"1 вектора х матрицыи т,д,1 ЕАналогичным образом можно вычислять производные по координате у с шагом Т, однако при этом загрузка матрицы выполняется по строкам, а не по столб цам.1Кроме того, подобным образом можно вычислять логические интегралы по координатам х и у с параметром Т, одна 20 ко на второй вход параметра Т и третий вход параметра (К+1)Т устройства следует подавать соответственно значения 2 -Т и (2 - К+1)Т.25Формула изобретения1. Устройство для логического дифференцирования и интегрирования булевых функций, содержащее генератор иМ блоков вычислений, причем первый инФормационный вход К-го блока вычислений подключен к первому выходу К+ 1-го блока вычислений (К = 1 М), а вход константы нуля устройства является первым информационным входом М-го бло 35 ка вычислений, о т л и ч а ю щ е,е -с я тем, что, с целью расширения Функциональных возможностей за счет вычисления логических производных и логических интегралов систем булевых функций, в устройство введены блоки ввода и вывода данных, причем информационный вход блока ввода данных является информационным входом устрой 45 ства, а выход блока вывода данных является выходом устройства, входы первого и второго параметров дифференцирования устройства являются входами параметра блоков ввода и вывода дан 50 ных соответственно, выход генератора импульсов подключен к входам синхро- низации блоков ввода и вывода данных вторые информационные входы блоковвычислений подключены к выходам первой группы блока ввода данных, а вы 55 ходы второй группы этого блока подключены к третьим информационным входам блоков вычислений соответственно, адресные входы блоков вычислений подключены к выходу адреса блока ввода данных, а выходы блоков вычислений подключены к информационным входам блока вывода данных.2, Устройство по п, 1, о т л и ч аю щ е е с я тем, что блок ввода данных содержит счетчик, элемент ИЛИ, регистр циклического сдвига, коммутатор узел сравнения и регистр, причем информационный вход блока является информационным входом коммутатора, вход синхронизации блока является управляющим входом счетчика, а вход параметра блока является информационным входом регистра, выходы которого являются адресным выходом блока и подключены к информационным входам первой группы узла сравнения, информационные входы второй группы которого подключены к выходам счетчика., к которым также подключены входы элемента ИЛИ, выход которого подключен к информационному входу регистра циклического сдвига, выходы которого образуют вторые выходы группы блока и подключены также к информационным входам группы коммутатора, вход сброса счетчика подключен к выходу узла сравнения. 3. Устройство по и. 1, о т л и - ч а ю щ е е с я тем, что блок вычислений содержит первый и второй коммутаторы, регистр и сумматор по модулю два, причем первый информационный вход блока является первым информационным входом сумматора по модулю два, а второй и третий информационные входы блока являются первым и вторым информационными входами первого коммутатора, третий информационный вход которого подключен к выходу сумматора по модулю два, второй информационный вход которого подключен к выходу второго коммутатора, который является также первым выходом блока, выход первого коммутатора является вторым выходом блока и подключен к информационному входу регистра, выход которого подключен к входам первой группы второго коммутатора, адресный вход блока является входами второй группы второго коммутатора.4. Устройство по п, 1, о т л и ч аю щ е е с я тем, что блок вывода данных содержит счетчик, элемент ИЛИ, регистр циклического сдвига, узел сравнения, коммутатор и регистр, причем вход параметра блока является информационным входом регистра, вход синхронизации блока является входом синх 5 рониэации счетчика, а информационные входы блока являются информационными входами первой группы коммутатора, информационные входы второй группы которого подключены к выходам регистра циклического сдвига, а выход является 1 выходом блока, информационный вход регистра циклического сдвига подключенк выходу злемента ИЛИ, входы которогоподключены к выходам счетчика, которыеподключены также к информационным входам второй группы узла сравнения, информационные входы первой группы которого подключены к выходам регистра,а выход схемы сравнения подключен квходу сброса счетчика.Составитель А.доброхотТехред М.Ходаннч Корректор А о,Коз ираж 569 1 ар вецно 11303 издательский комбинат "Патент", г. Ужгород, ул. Гагарин ПРоизводнн ака ВНЕ омитета по изо осква, Ж, Р Подписноетениям и открытиям при ГКНТ ССС ская наб., д. 4/5