Устройство для вычисления импликант
Похожие патенты | МПК / Метки | Текст | Заявка | Код ссылки
Текст
(19) 6 Г 15/35 1)5 ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР Е ИЗОБРЕТЕ РСКОМ К ИДЕТ Т 39хнический институт,Дуброва,нушкевич тельство СССР15/34, 1973.тельство СССРР 7/38, 1985,ОнФор Онныб рлацц дыкод Фо(54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ИМПЛИ КАНТ(57) Изобретение относится к вычислительной технике и может быть использовано для аппаратной поддержки вычислений при минимизации булевых функций в задачах синтеза цифровых автоматов, оптимизационных задачах с булевыми переменными, задачах на графах. Цель изобретения - расширение функциональных возможностей за счет нахождения всех импликант минимизируемой функции. Поставленная цель достигается тем, что устройство содержит блок 1 ввода, блок 2 синхронизации, и вычислительных блоков 3 и и блоков 4 буферной памяти, где п - число переменных булевой функции. 2 з.п. ф-лы, 5 ил.Изобретение относится к вычислительной технике и может быть использовано для аппаратной поддержки вычислений при минимизации булевых функций в задачах синтеза цифровых автоматов, оптимизационных задачах с булевыми переменными и в задачах на графах.Цель изобретения - расширение функциональных воэможностей за счет нахождения всех импликант минимизируемой функции,На фиг, 1 приведена схема устройства; на фиг, 2 - схема блока ввода; на фиг, 3 - схема блока управления; на фиг. 4 - схема вычислительного блока; на фиг. 5 - схема блока буферной памяти.Устройство для вычисления импликант содержит блок 1 ввода, блок 2 управления, и вычислительных блоков 3 и и блоков 4 буферной памяти, где п - число переменных булевой функции.Блок 1 ввода содержит первый и второй элементы ИЛИ 5 и 6, сдвигающий регистр 7и элемент 8 задержки.Блок 2 управления содержит генератор 9 тактовых импульсовэлемент ИЛИ 10, первый 11 и второй 12 счетчики, элемент 13 задержки, первый и второй элементы И 14 и 15.Каждый вычислительный блок 3 содержит первый 16 и второй 17 элементы И, первый 18 и второй 19 коммутаторы, элемент ИЛИ 20, с первого по третий триггеры 21-23 и счетчик 24.Блок 4 буферной памяти содержит элемент 25 задержки и регистры 26 сдвига,Под импликантом булевой функции понимается логическая функция, которая равна нулю на том обороте, на котором функция принимает нулевое значение,Суть подхода сводится к поиску импликант минимизируемой булевой функции и состоут в следующем, Над вектором значений Х минимизируемой булевой функции выполняется логическое преобразование, результатом которо является бинарный вектор импликант, 0 Номера позиций его. (к)единичных элементов позволяют однозначно записать импликанты.Формально логическое преобразование булевой функцр (Х), представленной вектором значений Х, определяется соотношениемОк)=82 . Х,где в матричных операциях используются только конъюнкции:К = ( К 1, , Кг.1, К+1, , Кл- кортеж из т(тТ,п) целых положительных чисел (индексов), упорядоченных по возрастанию и соответствующих ийдексам тех перемен ных, по которым осуществляется склеивание ходных термов;2 - матрица импликантного преобразования (импликантная матрица) размер 5 ности 2" х 2", формируемая по правилуив",-а " а(м),параметр уЯ 0,1) - определяется соотноше 10 нием1, и=);,Ь О,вк,К - 1-й элемент кортежа К. 15 Степени матриц"О, иМ = вычисляются по формулам, =0 25 М= Г 1Г 1Вычисление вектора импликант З ) формально записывается как(" (к ("- (кф"5(к)"ь 22дЭта процедура представлена в форме иттерационного процесса- (;1 (К,) - (4 35 К =5 и",(,и".Рассмотрим функционирование устройства при вычислении импликант булевой функции 1(Х) трех переменных (и = 3), задан ной своцм вектором значенийХ (Х(о) Х(1) Х(2 пТПоследовательность вычисления импликант 45 определяются соотношением 1(,2 1) 1= 2 )",3и-))=и является следующей 50 Оз), О(2) 02 з), О(1), Оз 0(12 0123В момент времени ьо осуществляется запуск устройства по сигналу, подаваемому на вход запуска генератора 9 тактовых им пульсов. При этом на выходе генератора 9 формируется импульсный сигнал, который поступает на входы синхронизации блоков41-4 з и блока 1 ввода,В результате в сдвигающем регистре 7блока 1 ввода выполняется сдвиг содержи 1686460мого на один разряд вправо, Через 1/2 такта осуществляется запись в старший разряд регистра 7 одного бита информации, поступающей с выхода элемента ИЛИ 5, на первый вход которого поступает элемент Хо) исходного вектора значений ХКроме того, элемент Х в момент времени 1 о поступает на первый вход элемента ИЛИ 6 блока ввода 1, а с выхода элемента ИЛИ 6 передается на выход блока 1 ввода и далее на первый информационный вход вычислительного блока 31,На первом такте (моменты времени 10 - 11) элемент Х(о) передается через вычислительные блоки 31 и 32 транзитом и поступает на первый информационный вход вычислительного блока Зз, С первого информационного входа блока Зз элемент Хф передается на его второй выход и на информационный вход блока 4 з буферной памяти и в моментв 1 вовремени 1 о + -записывается в ре 2гистр 261 этого блока. Кроме того, в момент времени то на вход режима блока 2 управления поступает содержимое регистра 261 блока 4 з, На четвертом выходе блока 2 управления в течение первого такта (то - 11) сохраняется низкий логический уровень сигнала,На втором такте (11-т 2) устройство функционирует следующим образом.В момент времени 11 импульсный сигнал с генератора 9 тактовых импульсов поступает на третий выход блока 2 управления,Импульсный сигнал с выхода элемента 13 задержки передается на счетный вход счетчика 11, поэтому на выходе элемента ИЛИ 10, входы которого подключены к выходам счетчика 11, формируется высокий логический уровень сигнала. Он передается на вход элемента И 15, в результате этого информация с другого входа элемента И 15 передается на четвертый выход блока 2 управления,Импульсный сигнал, выдаваемый в момент времени 11 на третий выход блока 2, поступает на вход синхронизации блока 1 ввода и блоков 41, 42 и 4 з буферной памяти, Поступающий на информацио)нный вход устройства второй элемент Х передается с информационного входа блока 1 ввода на его выход и, кроме того, в момент временив 1 вот, + 2 записывается в старший разряд сдвигающего регистра 7.С выхода блока ввода 1 элемент Х передается на первый информационный вход блока 31, Элемент Х( ) передается тран(1) зитом через блоки 31 и 32 на первый инфо)- мационный вход блока 3. Далее элемент Х)передается на первый информационныйвход коммутатора 18, а затем с его выхода5 на первый вход элемента И 16, Одновременно на второй вход элемента И 16 с выходасоответствующего регистра 26 поступаетэлемент Хф. В результате на выходе элемента И 16 в момент времени т 1 Еюрмирует 10 ся конъюнкция вида с) = Х(о) Х ) - первыйэлемент вектора импликант, Этот элементпередается на первый выход блока Зз и далее на вход режима блока 2 управления. Свыхода элемента И 15 элемент б о вектора15 импликант О(з) передается на четвертый выход блока 2 управления, т.е, на информационный выход устройства.элемент г ) Х(о) Хмомент времени 11 поступает с выхода эле 20 мента И 16 на второй информационный входкоммутатора 18 и с его первого выхода передается на соответствующий выход блокаЗз. Далее элемент с 1 поступает на информационный входблока 4 з буферной памяти25 т 1 - 1 ои в момент времени т + 2 записывается в регистр 261 блока 4 з(в момент времени 11 выполняется сдвиг его содержимоговправо),30 На тактах с третьего по восьмой моменты времени 12 - 1 з, , 17 - 1 в устройство работает следующим образом.Элементы Х( , , Х поступают на. вы(7)ход блока 1 ввода и, кроме того, последова 35 тельно записываются в регистр 7 блока 1.Тем самым по окончании восьмого такта врегистре 7 оказываются записанными векторы значений У= Х Х( ), Х( )1 булевойфункции т(Х) трех переменных (и = 3).40 На третьем такте на первом выходе блока Зз фоРмиРУетсЯ элемент б= Оо) На(1) отактах с четвертого по восьмой на первоьвыходе блока Зз формируются элементы б( =Х(2) г Х(3) (з) (2) (4) Х(4) л Х(5) (5) ЦФ45 и б(6): Х(б) - Х(7),На девятом такте (М - 19) на первом выходе блока Зз формируется последний, восьмой элер 1)ент о = дщ вектора импликант и(( (о)1 С(7 т50 Кроме того, в момент времени В в блоке2 происходит следующее изменение состояний и сигналов, Счетчик 11 в момент времени 1 а переходит из состояния 111 всостояние 000, и по окончании девятого55 такта на выходе элемента ИЛИ 10 формируется низкий логический уровень сигнала. Врезультате в момент времени 19 на второмвходе элемента И 15 и, следовательно, начетвертом выходе блока 2 управления надесятом такте (ип) устанавливается низкий логический уровень сигнала. Таким образом, векторы импликант формируютсякаждый за 2" тактов.Кроме того, задний фронт высокого логического уровня сигнала на выходе элемента ИЛИ 10 является сигналом сбросасчетчика 11 и по этому сигналу счетчик 12переходит из состояния 000 в состояние001,На тактах с девятого по восемнадцатый(117 11 в) в вычислительных блоках Зз и 32выполняется вычисление вектора импликант О ), элементы которого б " , с) ) формируются на четвертом выходе блока 2 втактах с одиннадцатого (11 о - с 11) по восемнадцатый (117-т 1 В),На тактах с семнадцатого (т 1 в) подвадцать седьмой (т 2 в) в вычислительномблоке 32 вьуолняется вычисление вектораимпликант О , элементы которого после(2,3)довательно формируются на четвертом выходе блока 2.в тактах с 20-го (с 19 - т 2 о) по 27-й(сз 7-язв) по 45-й (ьи-т 4".) - элементы вектораимпликант й , на тактах с 47-го (146 - т 47) по2(1,З)54-й 15 з-твл) - ) элементы вектора импликант О "2 и в тактах с 56-го (тв 5 - т 5 в) по 63-йлбу-Саз) - элементы вектора импликантО". Наконец, по окончании 63-го акта(1 в 2-твз)на выходе элемента ИЛИ 10 формируется низкий логический уровень сигналаи по заднему фронту высокого логическогоуровня сигнала (момент времени айвз) счетчик12 переходит из состояния 110 в состояние 111. При этом на выходе элемента И15 формируется высокий логический уровень сигнала, который является сигналомостанова генератора 9 тактовых импульсов,В момент времени тв 4 работа устройствазавершается.Формула изобретения1. Устройство для вычисления импликант, содержащее и блоков буферной памяти, где и - число переменных булевойфункции, и блок управления, причем входзапуска блока управления подключен к входу запуска устройства, о т л и ч а ю щ е е с ятем, что, с целью расширения функциональных воэможностей за счет нахождения всехимпликант минимизируемой функции, устройство содержит и вычислительных блокови блок ввода, при этом информационныйвход устройства подключен к информационному входу блока ввода, выход которооподключен к первому информационномувходу первого вычислительного блока, первый выход 1-го вычислительного блока подключен к первому информационному входу (1+1)-го вычислительного блока (где= 1 и), первый выход и-го вычислительного 5 блока подключен к входу режима блока управления, первый выход которого подключен к информационному выходу устройства, второй информационный вход)-го вычислительного блока (где= 1, и) подключен к 10 выходу )-го блока буферной памяти, информационный вход которого подключен к второму выходу )-го вычислительного блока, первый управляющий вход 1-го вычислительного блока подключен к третьему выхо ду +1)-го вычислительного блока, первыйуправляющий вход и-го вычислительного блока подключен к первому выходу блока управления, второй выход которого подключен к вторым входам управления всех вы числительных блоков, третий выход блокауправления подключен к входам синхронизации всех блоков буферной памяти, и блок ввода, четвертый выход блока управления подключен к информационному выходу уст ройства.2, Устройство по п. 1, о т л и ч а ю щ е е Сс я тем, что блок ввода содержит первый ивторой элементы ИЛИ, сдвигающий регистри элемент задержки, причем информацион 30 ный вход блока подключен к первым входампервого и второго элементов ИЛИ, выходыкоторых подключены соответственно к информационному входу сдвигающего регистра и к выходу блока, вход синхронизации35 которого подключен к входу сдвига сдвигающего регистра и к входу элемента задер-;жки, выход которого подключен к входузаписи сдвигающего регистра, выход которого подключен к вторым входам первого и40 второго элементов ИЛИ,3. Устройство по п, 1, о т л и ч а ю щ е ес я тем, что вычислительный блок содержитс первого по третий триггеры, первый и второй коммутаторы, первый и второй элемен 45 ты И и элемент ИЛИ, причем первыйуправляющий вход блока подключен к информационному входу первого триггера,первый информационный вход блока подключен к первым информационным входам50 первого и второго коммутаторов, первыйвыход второго коммутатора подключен кпервому выходу блока, второй информационный вход которого подключен к второмуинформационному входу второго коммута 55 тора, первый выход первого коммутатораподключен к второму выходу блока, вторыевыходы первого и второго коммутаторовподключены соответственно к первому ивторому входам первого элемента И, выход которого подключен к второму информаци1 онному входу первого коммутатора и к третьему информационному входу второго коммутатора, выход первого триггера подключен к третьему выходу блока, к входу установки в "0" второго триггера, к управляющему входу первого коммутатора, к первому управляющему входу второго коммутатора и к первому входу второго элемента И, выход которого подключен к информационному входу третьего триггера, выход которого подключен к счетному входу счетчика, выход переноса которого подключен к первому входу элемента ИЛИ и к входу установки в "1" второго триггера, выход которого подключен к второму входу второго 5 элемента И и к второму входу элементаИЛИ, выход которого подключен к второму управляющему входу второго коммутатора, второй управляющий вход блока подключен к входу установки в "0" первого триггера и к 10 входу установки в "0" третьего триггера и квходу установки счетчика.1686460 Редактор В.Данко Терд р Корректор, М.Демчик Заказ 3599 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ ССС 113035, Москва, Ж,Раушская наб 4/5 Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 10 ОГО -О БЫЧОСЛОПИЬ. ноо ячеоки 3;
СмотретьЗаявка
4746850, 14.08.1989
МИНСКИЙ РАДИОТЕХНИЧЕСКИЙ ИНСТИТУТ
БОНДАРЬ ИГОРЬ НИКОЛАЕВИЧ, ДУБРОВА ЕЛЕНА ВЛАДИМИРОВНА, ШМЕРКО ВЛАДИМИР ПЕТРОВИЧ, ЯНУШКЕВИЧ СВЕТЛАНА НИКОЛАЕВНА
МПК / Метки
МПК: G06F 17/17
Метки: вычисления, импликант
Опубликовано: 23.10.1991
Код ссылки
<a href="https://patents.su/7-1686460-ustrojjstvo-dlya-vychisleniya-implikant.html" target="_blank" rel="follow" title="База патентов СССР">Устройство для вычисления импликант</a>
Предыдущий патент: Спектроанализатор
Следующий патент: Сплайн-интерполятор
Случайный патент: Контактная система вакуумной дугогасительной камеры