Устройство для вычисления импликант

 

Изобретение относится к вычислительной технике и может быть использовано для аппаратной поддержки вычислений при минимизации булевых функций в задачах синтеза цифровых автоматов, оптимизационных задачах с булевыми переменными, задачах на графах. Цель изобретения - расширение функциональных возможностей за счет нахождения всех импликант минимизируемой функции. Поставленная цель достигается тем, что устройство содержит блок 1 ввода, блок 2 синхронизации, п вычислительных блоков 3 и п блоков 4 буферной памяти, где п - число переменных булевой функции. 2 з.п. ф-лы, 5 ил.

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (s>)s G 06 F 15/353

ГОСУДАРСТВЕННЫИ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

Инфо онныи

P

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4746850/24 (22) 14.08.89 (46) 23.10.91. Бюл. М 39 (71) Минский радиотехнический институт (72) И.Н.Бондарь, Е.B,Äóáðîâà, В.П.Шмерко и С.Н.Янушкевич (53) 681.325(088.8) (56) Авторское свидетельство СССР

N 428387, кл. G 06 F 15/34, 1973.

Авторское свидетельство СССР

N. 1275427. кл. G 06 F 7/38, 1985.

„„Я „„1686460 À1 (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ИМПЛИ КАНТ (57) Изобретение относится к вычислительной технике и может быть использовано для аппаратной поддержки вычислений при минимизации булевых функций в задачах синтеза цифровых автоматов, оптимизационных задачах с булевыми переменными, задачах на графах. Цель изобретения — расширение функциональных возможностей за счет нахождения всех импликант минимизируемой функции. Поставленная цель достигается тем, что устройство содержит блок 1 ввода, блок 2 синхронизации, и вычислительных блоков 3 и и блоков 4 буферной памяти, где п — число переменных булевой функции. 2 з.п. ф-лы, 5 ил.

1686460

Изобретение относится к вычислительной технике и может быть использовано для аппаратной поддержки вычислений при минимизации булевых функций в задачах синтеза цифровых автоматов, оптимизационных задачах с булевыми переменными и в задачах на графах.

Цель изобретения — расширение функциональных воэможностей за счет нахождения всех импликант минимизируемой функции, На фиг. 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 записать импликанты.

Формально логическое преобразование булевой функции f(X), представленной вектором значений Х, определяется соотношением 0 )= Я - ), где в матричных операциях используются только конъюнкции:

К = < К), ..., К -i, Kr+>, .... Kh > — кортеж из ф Т,п-1) целых положительных чисел (индексов), упорядоченных по возрастанию и соответствующих индексам тех переменных, по которым осуществляется склеивание ходных термов; — матрица импликантного преобразования (импликантная матрица) размер5 ности 2" х 2", формируемая по правилу и

s =Q» ((r,) "о(м,,) "), параметр y>Q0,1) — определяется соотноше10 нием

), n=k

Ь p,nfК, Ki — )-й элемент кортежа К.

Степени матриц 2 (О < и М2 =( () вычисляются по формулам

Ь . ),lh=0

25 (MRi) = Г il

) )h °

Вычисление вектора импликант З ) формально записывается как

30 (и1 (1 (к21 (Р 11 (к + д с- (кь ,Ь " дЬ

Эта процедура представлена в форме иттерационного процесса (;i (к,1 (! 4

35 . К =Q „Х, 1,И, < PV. .

Рассмотрим функционирование устройства при вычислении импликант булевой функции f(Xj трех переменных (n = 3), задан40 ной своим вектором значений х = (X ) х " ... х(" ), Последовательность вычисления импликант

45 определяются соотношением

i-1,2. -(, i = " 2, k-13

n->

)=1 и является следующей

О ), 0() 0 з), О()) 0(з 0 2) О(В момент времени to осуществляется запуск устройства по сигналу, подаваемому на вход запуска генератора 9 тактовых им55 пульсов. При этом на выходе генератора 9 формируется импульсный сигнал, который поступает на входы синхронизации блоков 41-4з и блока 1 ввода, В результате в сдвигающем регистре 7 блока 1 ввода выполняется сдвиг содержи1686460 мого на один разряд вправо. Через 1/2 такта осуществляется запись в старший разряд регистра 7 одного бита информации, поступающей с выхода элемента ИЛИ 5, на первый вход которого поступает элемент Х о) исходного вектора значений Х

Кроме того, элемент X в момент времени to поступает на первый вход элемента

ИЛИ 6 блока ввода 1, а с выхода элемента

ИЛИ 6 передается на выход блока 1 ввода и далее на первый информационный вход вычислительного блока 31.

На первом такте (моменты времени to—

t1) элемент Х(о) передается через вычислительные блоки 31 и 32 транзитом и поступает на первый информационный вход вычислительного блока Зз, С первого информационного входа блока Зз элемент Х(передается на его второй выход и на информационный вход блока 4з буферной памяти и в момент

С1 — С, времени to + — записывается в ре2 гистр 261 этого блока. Кроме того, в момент времени t< на вход режима блока 2 управлен и я поступ ает содержи мое регистра 261 блока 4з. На четвертом выходе блока 2 управления в течение первого такта (to — t1) сохраняется низкий логический уровень сигнала, На втором такте (t1 t2) устройство функционирует следующим образом.

В момент времени t1 импульсный сигнал с генератора 9 тактовых импульсов поступает на третий выход блока 2 управления, Импульсный сигнал с выхода элемента

13 задержки передается на счетный вход счетчика 11, поэтому на выходе элемента

ИЛИ 10, входы которого подключены к выходам счетчика 11, формируется высокий логический уровень сигнала. Он передается на вход элемента И 15, в результате этого информация с другого входа элемента И 15 передается на четвертый выход блока 2 управления, Импульсный сигнал, выдаваемый в момент времени t1 на третий выход блока 2, поступает на вход синхронизации блока 1 ввода и блоков 41, 42 и 4з буферной памяти, Поступающий на информационный вход устройства второй элемент Х передается с информационного входа блока 1 ввода на его выход и, кроме того, в момент времени

tp

t, + 2 записывается в старший разряд сдвигающего регистра 7.

С выхода блока ввода 1 элемент Х() передается на первый информационный вход блока 31, Элемент Х() передается тран(1) зитом через блоки 31 и 32 на первый информационный вход блока 3. Далее элемент X ) передается на первый информационный вход коммутатора 18, а затем с его выхода

5 на первый вход элемента И 16. Одновременно на второй вход элемента И 16 с выхода соответствующего регистра 26 поступает элемент Х(о). В результате на выходе элемента И 16 в момент времени И Е>ормирует10 ся конъюнкция вида б = Х(о) Х вЂ” первый элемент вектора импликант, Этот элемент передается на первый выход блока Зз и далее на вход режима блока 2 управления. С выхода эле уента И 15 элемент d о вектора

15 импликант Dp) передается на четвертый выход блока 2 управления, т.е. на информационный выход устройства.

Кроме того, элемент d() = Х(о) Х() в момент времени t1 поступает с выхода эле20 мента И 16 на второй информационный вход коммутатора 18 и с его первого выхода передается на соответствующий выход блока

Зз. Далее элемент d(0) поступает на информационный вход блока 4з буферной памяти

25 t1 — to и в момент времени t + 2 записывается в регистр 261 блока 43 (B момент времени t1 выполняется сдвиг его содержимого вправо), 30 На тактах с третьего по восьмой моменты времени t2 — t3, ..., t7 — 18 устройство работает следующим образом.

Элементы Х(, ..., Х поступают на.вы(7) ход блока 1 ввода и, кроме того, последова35 тельно записываются в регистр 7 блока 1.

Тем самым по окончании восьмого такта в регистре 7 оказываются записанными векторы значений X (Х(о) Х() .... Х(! булевой функции f(X) трех переменных (п = 3).

40 На третьем такте на первом выходе блока Зз формируется элемент d = d"). На (1) (о тактах с четвертого по восьмой на первом выходе блока Зз формируются элементы d(=

Х(2) Х(3) )(з) с (2) )(4) X(4) л X(5) )(5) ДЦ)

45 и б(6) = X(6) " X().

На девятом такте (t8 — tg) на первом выходе блока Зз формируется последний, восьмой элемент j = d " "вектора импликант и

= (d(o) ) 1 7))т

50 Кроме того, в момент времени ta в блоке

2 происходит следующее изменение состояний и сигналов, Счетчик 11 в момент времени te переходит из состояния 1...11 в состояние 0...00, и по окончании девятого

55 такта на выходе элемента ИЛИ 10 формируется низкий логический уровень сигнала. В результате в момент времени tg на втором входе элемента И 15 и, следовательно, на четвертом выходе блока 2 управления на

1686460

15

20 десятом такте (tg-(1п) устанавливается низкий логический уровень сигнала. Таким образом, векторы импликант формируются каждый за 2" тактов.

Кроме того, задний фронт высокого логического уровня сигнала на выходе элемента ИЛИ 10 является сигналом сброса счетчика 11 и по этому сигналу счетчик 12 переходит из состояния 0...00 в состояние

0...01, На тактах с девятого по восемнадцатый (т17 t18) в вычислительных блоках 33 и 32 выполняется вычисление вектора импликант О(), элементы которого d() ..., d(формируются на четвертом выходе блока 2 в тактах с одиннадцатого (t1o — t11) по восемнадцатый (t17-t18), На тактах с семнадцатого (t16-t17) по двадцать седьмой (t26 t27) в вычислительном блоке 32 вьуолняется вычисление вектора импликант 0, элементы которого последовательно формируются на четвертом выходе блока 2.в тактах с 20-го (t tg t28) по 27-й (т26 t27)

На тактах с 29-ro (t28-t2g) по 36-й (1з6— - 1з6) на четвертом выходе. блока 2 формируются векторы импликант u, на тактах с 38-ro (t37 l38) по 45-й (tnn-t48) — элементы вектора импликантЮ, на тактах с 47-го (т46 — t47) по

54-й сбз-tвn) — ) элементы вектора импликант D " и в тактах с 56-ro (t66 — t66) по 63-й

gt — ty) — элементы вектора импликант

0 . Наконец, по окончании 63-го акта (т62-тбз)на выходе элемента ИЛИ 10 формируется низкий логический уровень сигнала и по заднему фронту высокого логического уровня сигнала (момент времени 16з) счетчик

12 переходит из состояния 1...10 е состояние 1...11. При этом на выходе элемента И

15 формируется высокий логический уровень сигнала, который является сигналом останова генератора 9 тактовых импульсов, В момент времени т64 работа устройства завершается.

Формула изобретения

1. Устройство для вычисления импликант, содержащее п блоков буферной памяти, где n — число переменных булевой функции, и блок управления, причем вход запуска блока управления подключен к входу запуска устройства, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных воэможностей за счет нахождения всех импликант минимизируемой функции, устройство содержит и вычислительных блоков и блок ввода, при этом информационный вход устройства подключен к информационному входу блока ввода, выход которо о подключен к первому информационному входу первого вычислительного блока, пер25

55 вый выход I-го вычислительного блока подключен к первому информационному входу (1+1)-го вычислительного блока (где = 1, ..., п-1), первый выход и-го вычислительного блока подключен к входу режима блока управления, первый выход которого подключен к информационному выходу устройства, второй информационный вход j-го вычислительного блока (где j = 1..., и) подключен к выходу J-го блока буферной памяти, информационный вход которого подключен к еторому выходу j-ro вычислительного блока, первый управляющий вход I-го вычислительного блока подключен к третьему выходу (I+1)-го вычислительного блока, первый управляющий вход n-ro вычислительного блока подключен к первому выходу блока управления, второй выход которого подключен к вторым входам управления всех вычислительных блоков, третий выход блока управления подключен к входам синхронизации всех блоков буферной памяти, и блок ввода, четвертый выход блока управления подключен к информационному выходу устройства.

2, Устройство по и. 1, о т л и ч а ю щ е е i с я тем, что блок ввода содержит первый и второй элементы ИЛИ, сдвигающий регистр и элемент задержки, причем информационный вход блока подключен к первым входам первого и второго элементов ИЛИ, выходы которых подключены соответственно к информационному входу сдвигающего регистра и к выходу блока, вход синхронизации которого подключен к входу сдвига сдвигающего регистра и к входу элемента задер-, жки, выход которого подключен к входу; записи сдвигающего регистра, выход которого подключен к вторым входам первого и второго элементов ИЛИ, 3. Устройство по п, 1, о т л и ч а ю щ е ес я тем, что вычислительный блок содержит с первого по третий триггеры, первый и второй коммутаторы, первый и второй элементы И и элемент ИЛИ, причем первый управляющий вход блока подключен к информационному входу первого триггера, первый информационный вход блока подключен к первым информационным входам первого и второго коммутаторов, первый выход второго коммутатора подключен к первому выходу блока, второй информационный вход которого подключен к второму информационному входу второго коммутатора, первый выход первого коммутатора подключен к второму выходу блока, вторые выходы первого и второго коммутаторов подключены соответственно к первому и второму входам первого элемента И, выход которого подключен к второму информаци10

1686460 л8х

4Ьг.2

Информ юыо Юх онному входу первого коммутатора и к третьему информационному входу второго коммутатора, выход первого триггера подключен к третьему выходу блока, к входу установки в "0" второго триггера, к управляющему входу первого коммутатора, к первому управляющему входу второго коммутатора и к первому входу второго элемента И, выход которого подключен к информа ци он ному входу третьего триггера, выход которого подключен к счетному входу счетчика, выход переноса которого подключен к первому входу элемента ИЛИ и к входу установки в "1" второго триггера, выход которого подключен к второму входу второго

5 элемента И и к второму входу элемента

ИЛИ, выход которого подключен к второму управляющему входу второго коммутатора, второй управляющий вход блока подключен к входу установки в "0" первого триггера и к

10 входу установки в "0" третьего триггера и к входу установки счетчика.

1686460

1686460

Составитель В.Смирнов

Техред М.Моргентал Корректор, М.Демчик

Редактор В.Данко

Заказ 3599 Тираж Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб„4/5

Производственно-издательский комбинат "Патент", r. Ужгород, ул.Гагарина, 101

ОГП i.- и 5ычОСЛОП Иь. ноо ячейки 3;

A i 0D бычисиигпеььной ячейки З