Устройство для вычисления импликант Советский патент 1991 года по МПК G06F17/17 

инфорпдци-, онный

фНЗ-й- tg№

I

- tg№

§L JE

г

инфорпацион- ,ный быход

О

со о -N о о

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

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

На фиг. 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 сдвига.

Под импликантом булевой функции понимается логическая функция, которая равна нулю на том обороте, на котором функция принимает нулевое значение.

Суть подхода сводится к поиску импликант минимизируемой булевой функции и состоит в следующем. Над вектором значений X минимизируемой булевой функции выполняется логическое преобразование, результатом которого является бинарный вектор импликант Номера позиций его единичных элементов позволяют однозначно записать импликанты.

Формально логическое преобразование булевой функц f(X), представленной вектором значений X, определяется соотношением(цч ,

г5к - Ф - ,

где в матричных операциях используются только конъюнкции:

К° KiКг-1, Кг+1Кп - кортеж из

t(tЈT,rT-l) целых положительных чисел (индексов), упорядоченных по возрастанию и соответствующих индексам тех переменных, по которым осуществляется склеивание исходных термов;

521 - матрица импликантного преобразования (импликантная матрица) размер- ности 2 х 2 , формируемая по правилу

00 г - (м JtM2 ,

2-Я м

параметр упб(0,1) - определяется соотноше- 10 нием

и

Я«- Ь.г-к,

KI - 1-й элемент кортежа К. Степени матриц 0 и вычисляются по формулам

М2«

;;

20

Ч(

о

J)

Ч« г

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

1Ю С(кг-Лс0 (

SV-ч цуг-/. сч-г- с г Ч v

nn 2 2 2 2П

Эта процедура представлена в форме иттерационного процесса

-(i с(к;) . -- . , ,

х1 52„ -X , .H.n.ifr.

Рассмотрим функционирование устройства при вычислении импликант булевой функции f(X) трех переменных (п 3). задан- ной своим вектором значений )( Х(о))...Х()т. Последовательность вычисления импли амт aMvy-v

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

Sa.k-Ts

1,2г-1,

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

р(3) (2) Ј(2.3) pd) (1.3). -511.2). р(1.2.3)

В момент времени to осуществляется

запуск устройства по сигналу, подаваемому

на вход запуска генератора 9 тактовых импульсов. При этом на выходе генератора 9

формируется импульсный сигнал, который

поступает на входы синхронизации блоков

4т-4з и блока 1 ввода.

В результате в сдвигающем регистре 7 блока 1 ввода выполняется сдвиг содержимого на один разряд вправо. Через 1/2 такта осуществляется запись в старший разряд регистра 7 одного бита информации, поступающей с выхода элемента ИЛИ 5, на первый вход которого поступает элемент х исходного вектора значений А.

Кроме того, элемент Х(0 в момент времени t0 поступает нл первый вход элемента ИЛИ 6 блока ввода 1, а с выхода элемента ИЛИ 6 передается на выход блока 1 ввода и далее на первый информационный вход вычислительного блока 3i.

На первом такте (моменты времени to ti) элемент х ° передается через вычислительные блоки 3i и 32 транзитом и поступает на первый информационный вход вычислительного блока Зз. С первого информационного входа блока Зз элемент передается на его второй выход и на информационный вход блока 4i буферной памяти и в момент

, ti-to

времени t0 +-у- записывается в регистр 26i этого блока. Кроме того, в момент времени to на вход режима блока 2 управления поступает содержимое регистра 26i блока 4з. На четвертом выходе блока 2 управления в течение первого такта (t0-ti) сохраняется низкий логический уровень сигнала.

На втором такте (ti-t2) устройство функ- ционирует следующим образом.

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

Импульсный сигнал с выхода элемента 13 задержки передается на счетный вход счетчика 11, поэтому на выходе элемента ИЛИ 10, входы которого подключены к выходам счетчика 11, формируется высокий логический уровень сигнала. Он передается на вход элемента И 15, в результате этого информация с другого входа элемента И 15 передается на четвертый выход блока 2 управления.

Импульсный сигнал, выдаваемый в момент времени ti на третий выход блока 2, поступает на вход синхронизации блока 1 ввода и блоков 4i, 42 и 4з буферной памяти. Поступающий на информационный вход ус- тройства второй элемент передается с информационного входа блока 1 ввода на его выход и, кроме того, в момент времени

, ti-to t, H-д-записывается в старший разряд

сдвигающего регистра 7.

С выхода блока ввода 1 элемент передается на первый информационный вход блока 3i. Элемент х 1 передается транзитом через блоки 3i и 32 на первый информационный вход блока 3. Далее элемент Х передается на первый информационный вход коммутатора 18. а затем с его выхода на первый вход элемента И 16. Одновременно на второй вход элемента И 16 с выхода соответствующего регистра 26 поступает элемент X . В результате на выходе элемента И 1б| в момент времени ti формируется коньюнкция вида х ° л - первый элемент вектора импликант. Этот элемент передается на первый выход блока Зз и далее на вход режима блока 2 управления. С выхода элемента И 15 элемент сг вектора импликант (5(з) передается на четвертый выход блока 2 управления, т.е. на информационный выход устройства.

Кроме того, элемент d(o) Х(о) л Х(1) в момент времени ti поступает с выхода элемента И 16 на второй информационный вход коммутатора 18 и с его первого выхода передается на соответствующий выход блока Зз. Далее элемент d ° поступает на информационный вход блока 4з буферной памяти

, ti-to

и в момент времени t записывается в регистр 261 блока 4з(в момент времени ti выполняется сдвиг его содержимого вправо).

На тактах с третьего по восьмой моменты времени t2 t317-te устройство работает следующим образом.

(7}

Элементы Xv X1 поступают на выход блока 1 ввода и, кроме того, последовательно записываются в регистр 7 блока 1. Тем самым по окончании восьмого такта в регистре 7 оказываются записанными век- торы значений Х Х(о)Х(1) .... Х(7)т булевой функции f(X) трех переменных (п 3).

На третьем такте на первом выходе бло(D

). На

ка Зз формируется элемент d тактах с четвертого по восьмой на первом выходе блока Зз формируются элементы d;2 Xй X®, d(3) d(2. d(4 X(4) - X(5), d(5)

Hd(6)

m

На девятом такте () на первом выходе блока Зз формируется последний, восьмой элемент о/ d вектора импликант и L

d(o)dfl....

Кроме того, в момент времени te в блоке 2 происходит следующее изменение состояний и сигналов. Счетчик 11 в момент времени & переходит из состояния 1...11 в состояние 0...00, и по окончании девятого такта на выходе элемента ИЛИ 10 формируется низкий логический уровень сигнала. В результате в момент времени tg на втором входе элемента И 15 и, следовательно, на четвертом выходе блока 2 управления на

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

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

На тактах с девятого по восемнадцатый (m-tia) в вычислительных блоках Зз и 32 выполняется вычисление вектора импликант D , элементы которого d .... d формируются на четвертом выходе блока 2 в тактах с одиннадцатого (tio-tn) по восемнадцатый (t17 tie).

На тактах с семнадцатого () по двадцать седьмой () в вычислительном блоке За выполняется вычисление вектора импликант D , элементы которого последовательно формируются на четвертом выходе блока 2 в тактах с 20-го (tig-t2o) по 27-й ().

На тактах с 29-го (t28-t29) по 36-й () на четвертом выходе: блока 2 формируются векторы импликант D , на тактах с 38-го () по 45-й (I44-U5) - элементы вектора импликант , на тактах с 47-го () по 54-й Jt53-t54) -) элементы вектора импликант D11 2) и в тактах с 56-го (tss-tsc) по 63-й ) элементы вектора импликант Ь . Наконец, по окончании 63-го такта ()Ha выходе элемента ИЛИ 10 формируется низкий логический уровень сигнала и по заднему фронту высокого логического уровня сигнала (момент времени ) счетчик 12 переходит из состояния 1...10 в состояние 1...11. При этом на выходе элемента И 15 формируется высокий логический уровень сигнала, который является сигналом останова генератора 9 тактовых импульсов, В момент времени tw работа устройства завершается.

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

(1+1)-го вычислительного блока (где

п-1), первый выход n-го вычислительного

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

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

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

5 которого подключен к входу сдвига сдвигающего регистра и к входу элемента задержки, выход которого подключен к входу записи сдвигающего регистра, выход которого подключен к вторым входам первого и

0 второго элементов ИЛИ.

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

0 первого и второго коммутаторов, первый выход второго коммутатора подключен к первому выходу блока, второй информационный вход которого подключен к второму информационному входу второго коммута5 тора, первый выход первого коммутатора подключен к второму выходу блока, вторые выходы первого и второго коммутаторов подключены соответственно к первому и второму входам первого элемента И. выход соторого подключен к второму информационному входу первого коммутатора и к третьему информационному входу второго коммутатора, выход первого триггера подключен к третьему выходу блока, к входу установки в О второго триггера, к управляющему входу первого коммутатора, к первому управляющему входу второго коммутатора и к первому входу второго элемента И, выход которого подключен к информационному входу третьего триггера, выход которого подключен к счетному входу

счетчика, выход переноса которого подключен к первому входу элемента ИЛИ и к входу установки в Г второго триггера, выход которого подключен к второму входу второго элемента И и к второму входу элемента ИЛИ, выход которого подключен к второму управляющему входу второго коммутатора, второй управляющий вход блока подключен к входу установки в О первого триггера и к входу установки в О третьего триггера и к входу установки счетчика.

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

- Выход

фие.г

Фиг.З

От i-й дычислитель- ной ячейки 3i

Ki-ой бычислительной ячейки 3i

Фиг 5