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

(19) (1 7/ 1)5 С ИСАНИЕ ИЗОБРЕТЕ ЕТЕЛЬСТВУ ВТОРСКОМУ 2(54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ЗНАЧЕНИЙ БУЛЕВЫХ ФУНКЦИЙ (57) Изобретение относится к цифровой вычислительной технике и может быть использовано для вычисления булевых функций в системах контроля и управления. Целью изобретения является повышение производительности. Устройство содержит счетчик, к блоков памяти, К функциональных преобразователей, два триггера, девять элементов И, формирователь импульсов, генератор импульсов, три элемента ИЛИ, элемент ИЛИ - НЕ и элемент И,2 ил. ражкии,мационный выход 25, выход 26 признака окончания вычислений, выходы 27 блоков 7, выход 28 вычисления конъюнкции, выходы 29 вычисления дизъюнкции, выход 30 признака кода операции,Функциональный преобразователь 1 (фиг, 2) содержит группу элементов НЕ 31, группу элементов И 32, первую, вторую группу 33 элементов И, группу 34 элементов ИЛИ - НЕ, первую и вторую группы 35 и 36 элементов ИЛИ, элемент ИЛИ 37 и элемент И 38. ся к цифровой выожет быть испольулевых функций в вления.повышение произделения значений ено на фиг. 1; на а функциональнообрам В исходшен и запревыходе 26 -щий отсутстНа выходещий результстояние счет ном состо щает раб нулевой вие момен 25 - поте ату предьчика 8 бе янии триггероту генератораотенциал, фикта конца вычинциал, соотведущей операцразлично. 6 сбро; на сируюсления. тствуюии. СоОСУДАРСТВЕННОЕ ПАТЕНТНЕДОМСТВО СССРОСПАТЕНТ СССР)(71) Московский институт инженероданской авиации(56) Авторское свидетельство СССРМ 1315965, кл. 0 06 Р 7/00, 1985.Авторское свидетельство СССРМ 1508204, кл, 6 06 Е 7/00, 1987. Изобретение относит числительной технике и м зовано для вычисления б системах контроля и упраЦель изобретения - водительности.Устройство для опре булевых функций привед фиг. 2 - структурная схем го преобразования.Устройство для опре булевых функций содерж функциональных преоб вый, шестой элементы И НЕ 4, первый и второй тр блоков памяти 7, счетчик 9 импульсов, генератор 1 мой, девятый, третий, се пятый, второй элементы НЕ 18, второй, третий, ИЛИ 19 - 21, установочны запуска, информационны деления значенийит(фиг, 1) группу 1 разователей, пер, 3, элемент ИЛ Ив иггеры 5, 6, группу 8, формирователь 0 импульсов, восьдьмой, четвертый, И 11-17, элемент первый элементы й вход 22, вход 23 е входы 24, инфортройство работает следуюВ блоки памяти 7 информация заносится до начала вычисления булевых функций; в каждой ячейке блока 7 записано управляющее слово следующего формата: код поля номеров, причем для каждого номера аргумента в управляющем слове зарезервировано два бита - для самого аргумента и для его инверсии; для 1-го аргумента соответственно - :27 и 27 а. При этом, если в некотором терме участвует сам аргумент, сочетание сигналов на выходах 27 равно "10", если - инверсия аргумента - "01"; если ни аргумент, ни его инверсия не участвуют в терме, - "00",Булевы функции в устройстве вычисляются либо на основе дизъюнктивной нормальной формы (ДНФ), либо на основе конъюнктивной нормальной формы (КНФ), Каждый терм (тип задания функции определяется дополнительным сигналом с выхода 30 первого блока памяти; для ДН Ф - "1", для КНФ - "0" (вычисляется из значений аргументов на входе 24 устройства и поля номеров аргументов соответствующего блока памяти по данному адресу - функциональным преобразователем, связанным с данным блоком памяти. Пусть число аргументов в некоторой функции равно Й, Пусть число блоков памяти 7 равно К, Пусть также максимальное число термов в некоторой функции равно М. Если МК, очевидно, не все ячейки соответствующего адреса, задаваемого счетчиком 8, будут заняты термами и вычисление функции производится за один такт работы. Если же МК, то вычисление функции требует более одного такта работы; назовем значение функции после некоторого (не последнего) такта частичной ДНФ (КНФ) - сокращенно: ЧДНФ (ЧКНФ). В свободные, не используемые ячейки блоков памяти достаточно для корректной работы записать любые уже использованные в данной функции термы, Еще одно условие корректного заполнения ячеек памяти - после исчерпания термой некоторой функции по следующему адресу во все блоки памяти записываются нулевые значения в поля номеров аргументов.Цепи предварительного занесения информации в блоки памяти 7 и цепи начальной установки устройства не показаны.Перед началом работы непосредственно на входы 24 подаются значения аргументов, а на входы 22 - начальный адрес, по которому в блоках памяти записаны управляющие слова данной функции. Изменяя начальный адрес, можно вычислять требуемое значение необходимого пользователю количества различных булевых функций, 5 10 15 20 25 30 35 40 45 50 55 Положительный короткий сигнал, подаваемый на вход 23 запуска устройства, инициирует начало работы: записывает всчетчик 8 код начального адреса требуемойфункции, устанавливает триггер б в единичное состояние. Адрес с выхода блока 8 поступает на адресные входы блоков памяти,на выходах которых(поля номеров аргументов) формируются управляющие сигналы вфункциональные преобразователи 1, На дополнительном выходе 30 блока памяти 71формируется сигнал типа операции; этотсигнал - один и тот же для всех последовательных ячеек блока 71 для данной булевойфункции.Пусть МК(более общий случай). Пустьфункция должна быть также представлена ввиде ДНФ,В этом случае единичный сигнал с выхода 30 открывает элементы И 2, 11 и 13,Элементы И 3, 12 и 14 - в закрытом состоянии.Под управлением разрешающего сигнала с триггера 6 генератор 10 формирует тактовые импульсы, Первый импульс поступаетна элементы И 2 и 3 и устанавливает триггер5 в начальное состояние; (для нашего примера - ДНФ - в нулевое состояние), Импульс поступает и на элемент И 16,осуществляя опрос состояния элементаИЛИ - НЕ 4. В первом такте работы хотя быодин терм - ненулевой (иначе - пустая булева функция), На выходе элемента ИЛИ - НЕ- нулевой сигнал, следовательно, сигнал навыходе элемента И 16 не формируется.Формирователь импульсов формируетзадержанный относительно входных импульсы сначала на первом, затем - на втором выходах. Импульс с первого выходаформирователя 9 проходит на тактовых входтриггера 5 и записывает в него значениеЧДНФ (по первым К термам), сформированное на выходе элемента 20 ИЛИ,Частичная (или полная - при МК)ДНФ формируется в блоках 1 следующимобразом;На входы 24 функционального преобразователя (фиг. 2) поступают значения аргументов - в прямом виде - на элементы И 32и в инверсном виде - на элементы И 33.Сигналы на входах 37 коммутируют на выходы элементов И 32 и 33 соответствующиезначения аргумента, которые подвергаютсяоперации дизъюнкции на элементе ИЛИ 35.На элементе ИЛИ 37 формируется "внутренняя" дизъюнкция данного (для конкретногоблока 1) терма при реализации функции ввиде КНФ путем логического "ИЛИ" выбранных значений аргументов. На элементеИ 38 формируется "внутренняя" конъюнк1805462 35 не влияет на корректность работы эле-. 5мента ИЛИ 37, но, чтобы сохранить коррек 15 20 ция терма по тем же аргументам при реализации выходной функции в виде КНФ. Если некоторый аргумент не участвует в данной терме, нулевой сигнал на выходе элемента тность для элемента И 38, используются элементы ИЛИ - НЕ 34 и ИЛИ 36, которые в случае нулевых значений сигнала на обоих входах 27 формируют для данного аргумента на соответствующем входе элемента 38 единичный сигнал.На элементах ИЛИ 19 и И 12 формируются соответственно частичные ДНФ и КНФ требуемой булевой функции. Для рассматриваемого примера значение ЧДНФ коммутируется через элементы И 11 и ИЛИ 20 на информационный вход триггера 5 и записывается в него импульсом с первого выхода формирователя 9, Импульс с второго выхода блока 9 инкрементирует содержимое счетчика 8, задающего для данной функции следующие адреса, и подает сигнал опроса на элементы И 13 и 14. Опрос осуществляется со следующей целью: если реализуется ДНФ и ЧДНФ, устанавливает триггер 5 в единичное состояние, дальнейшее вычисление функции не имеет значения, так как ее значение заведомо единичное, Аналогично, при КНФ можно прекратить дальнейшее вычисление, если ЧДНФ устанавливает триггер 5 в "0". Итак, если триггер устанавливается при вычислении ДНФ в единичное состояние, по сигналу с второго выхода формирователя 9 срабатывает элемент И 13 и сигнал через элемент ИЛИ 21 поступает на выход 26 устройства, сигнализируя об окончании процесса вычисления функции, а также на вход сброса триггера 6, с прямого выхода котоаого после этого снимается разрешающий сигнал на генератор 10 и вычисление прекращается, Аналогично при КНФ срабатывает элемент И 14 и дальнейший процесс аналогичен.Если в промежуточном такте не сформировался сигнал об окончании вычисления, генератор 10 формирует следующий тактовый импульс, по которому аналогично описанному осуществляется обработка следующей "порции" термав. Так происходит до исчерпания всех термов функции, В последнем такте, после исчерпания термов, все сигналы на входах элементов ИЛИ - НЕ принимают нулевое значение и сигнал с выхода генератора 10 открывает элемент И 16, формируя сигнал окончания процесса на выходе элемента ИЛИ 21. Устройство устанавливается в исходное состояние, причем установка триггера 6 в нулевое состояние 25 30 35 40 50 55 открывает элемент И 15, с выхода которого вычисленное значение булевой функции подается на выход 25. При этом по окончании процесса вычисления по нулевому содержимому блоков памяти нулевое значение сигнала на прямом выходе триггера 6 запрещает запись информации в триггер 5, не искажая информацию.Таким образом, устройство позволяет вычислить значение булевой функции с максимальным быстродействием параллельным вычислением по ряду термов; реализацию "досрочного вычисления в ряде случаев, Устройство обеспечивает корректную работу не только с самими аргументами, но и с их инверсиями, что расширяет область применения; возможно и вычисление множества булевых функций. Достоверность повышается посредством жесткой синхронизации работы узлов устройства и за счет формирования сигнала окончания процесса вычисления функций. Формула изобретения Устройство для определения значений булевых функций, содержащее генератор импульсов, формирователь импульсов, счетчик, первый блок памяти, первый функционэльный преобразователь, первый и второй элементы И и двэ триггера, причем выход генератора импульсов соединен с входом формирователя импульсов, первый выход которого соединен со счетным входом счетчика, информационный вход которого соединен с установочным входом устройства, информационные входы которого соединены с входами первой группы первого функционального преобразователя, входы второй группы которого соединены с выходом первого блока памяти, адресный вход которого соединен с выходом счетчика, выход первого элемента И соединен с входом сброса первого триггера, о т л и ч а ю щ е ес я тем, что, с целью повышения производительности, в него введены со второго па К-й блоки памяти, (К - количества дизьюнктивных или коньюнктивных членов в функции), с второго по К-й функциональные преобразователи, элемент НЕ, элемент ИЛИ - НЕ, с третьего по девятый элементы И и три элемента ИЛИ, причем вход запуска устройства соединен с синхровходом счетчика и установочным входом втооого триггера, прямой выход которого соединен с входом генератора импульсов и первым входом второго элемента И, выход которого соединен с тактовым входом первого триггера, прямой выход которого соединен с первыми входами третьего и четвертого элементов И, вторые входы которых соединены1805462 222 У соответственно с вторым выходом формирователя импульсов и инверсным выходом второго триггера, вход сброса которого соединен с выходом первого элемента ИЛИ и является выходом признака окончания вычислений устройства, информационные входы которого соединены с входами первой группы с второго по К-й функциональных преобразователей, входы второй группы которых соединены с выходами с второго по К-й блоков памяти соответственно, выходы всех блоков памяти соединены с входами элемента ИЛИ - НЕ, выход которого соединен с первым входом пятого элемента И, второй вход которого соединен с выходом генератора импульсов и первыми входами первого и шестого элементов И, а выход - с установочным входом первого триггера, инверсный выход которого соединен с первым входом седьмого элемента И, второй вход которого соединен с первым выходом формирователя импульсов, второй выход которого соединен с вторым входом второго элемента И, второй вход первого элемента И соединен с выходом признака кода операции первого блока памяти, третьим вхог дом третьего элемента И, первым входом восьмого элемента И и входом элемента Н Е, выход которого соединен с вторым входом шестого элемента И, третьим входом седь мого элемента И, выход которого соединенс первым входом первого элемента ИЛИ, второй и третий входы которого соединены соответственно с выходами третьего и пятого элементов И, выход счетчика соединен с 10 адресными входами с второго по К-й блоковпамяти, выходы вычисления конъюнкции всех функциональных преобразователей соединены с входами второго элемента ИЛИ, выход которого соединен с вторым входом 15 восьмого элемента И, выход которого соединен с первым входом третьего элемента ИЛИ, второй вход которого соединен с выходом девятого элемента И, первый вход которого соединен с выходом элемента НЕ, 20 а остальные входы девятого элемента И соединены с выходами значений дизъюнкции всех функциональных преобразователей, выход третьего элемента ИЛИ соединен с информационным входом первого триггера, 25 выход четвертого элемента И является информационным выходом устройства.1805462 Составитель С.КишенскийТехред М,Моргентал Корректор О,Густи ктор роизводственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101 аказ 942 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж, Раушская наб 4/5