Минимизация систем переключательных функций

При минимизации систем ПФ необходимо учитывать вхождение конъюнкций в разные функции системы. Дело в том, что раздельная минимизация каждой функции системы может привести к тому, что ранг (сложность) каждой отдельной функции будет минимальным, а ранг системы – нет. В случае представления системы ПФ схемой это означает, что она будет состоять из изолированных подсхем, в то время как реализация с использованием объединения одинаковых участков подсхем будет проще [31].

Для минимизации систем ПФ используют, например, модифицированный метод Квайна-Мак-Класки. При этом из функций системы ПФ формируется псевдофункция j, содержащая множество А конъюнкций системы. Сумма рангов (число букв) конъюнкций множества А является показателем эффективности минимизации.

Пример. [31]: дана система из двух функций, заданных двоичными рабочими наборами:

f₁(х₃х₂х₁)=(000)Ú(101)Ú(110)Ú(111);

f₂(х₃х₂х₁)=(000)Ú(010)Ú(011)Ú(101).

Получим множество конъюнкций А:

А={000(1,2),010(2),011(2),101(1,2),110(1),111(1)}.

Здесь указаны индексы вхождения конъюнкций в функции. То есть, например, конъюнкция 000 (1,2), входит и в первую, и во вторую функцию.

Псевдофункция j выглядит следующим образом:

j=000(1,2)Ú010(2)Ú011(2)Ú101(1,2)Ú110(1)Ú111(1).

Склеиваться могут только конъюнкции с одинаковыми индексами!

Проводим склеивания с учетом индекса вхождения в функции:

1 – 2: (0-0)(2)Ú(010)(2)Ú(000)(1,2);

2 – 3: (01-)(2)Ú(010)(2)Ú(011)(2);

4 – 6: (1-1)(1)Ú(101)(1,2)Ú(111)(1);

5 – 6: (11-)(1)Ú(110)(1)Ú(111)(1).

После выполнения всех поглощений с учетом индекса каждой конъюнкции получаем сокращенную псевдофункцию:

j=(0-0)(2)Ú(000)(1,2)Ú(01-)(2)Ú(1-1)(1)Ú(101)(1,2)Ú(11-)(1).

Строим таблицу покрытий (табл. 40).

Таблица 40

Импликантная таблица системной минимизации

Простые импликанты			Наборы функции
			000		010	011	101		110	111
			1	2	2	2	1	2	1	1
0	-	0		+	+
0	0	0	+	+
0	1	-			+	+
1	-	1					+			+
1	0	1					+	+
1	1	-							+	+

 

Выделяем ядро покрытия и убеждаемся, что оно покрывает все конституенты j:

j=(000)(1,2)Ú(01-)(2)Ú(101)(1,2)Ú(11-)(1).

Ранг такой функции равен 10.

Таким образом, получаем:

f₁(х₃х₂х₁)=(000)Ú(101)Ú(11-);

f₂(х₃х₂х₁)=(000)Ú(01-)Ú(101).

В случае раздельной минимизации, например, по кубу соседних чисел, получаем:

f₁(х₃х₂х₁)=(000)Ú{(101)Ú(111)}Ú{(110)Ú(111)};

f₂(х₃х₂х₁)={(000)Ú(010)}Ú{(010)Ú(011)}Ú(101).

Поэтому:

f₁(х₃х₂х₁)=(000)Ú(1-1)Ú(11-);

f₂(х₃х₂х₁)=(0-0)Ú(01-)Ú(101),

то есть в случае раздельной минимизации получаем ранг 14.

Минимизация систем переключательных функций преобразованием таблиц соответствия [6].

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

Обобщенным кодом (ОК) называется позиционный n-разрядный код ω=ε_n…ε₂ε₁, в каждой позиции которого находится символ ε_iÎ{0,-,1,Æ}. Отсюда видно, что двоичный код a=s_n…s₂s₁, s_iÎ{0,1} является частным случаем обобщенного кода.

Символы ОК в i-м разряде имеют следующий физический смысл:

«0» – выключенное состояние соответствующего дискретного элемента x_i (нулевое значение сигнала x_i), или переменная со знаком инверсии;

«1» – включенное состояние соответствующего дискретного элемента x_i (единичное значение сигнала x_i), или переменная без знака инверсии;

«-» (тире) – безразличное состояние дискретного элемента x_i (безразличное значение сигнала x_i), или логическая единица, т.е. дизъюнкция переменной без инверсии и переменной с инверсией: ;

«Æ» (символ «пусто») – противоречивое состояние дискретного элемента x_i (невозможное значение сигнала x_i), или логический нуль, т.е. конъюнкция переменной без инверсии и переменной с инверсией: .

Обобщенный код, содержащий хотя бы один символ Æ, принято называть пустым или мнимым, что сокращенно записывается в виде A=Æ.

Обобщенные коды A и B равны между собой тогда и только тогда, когда они совпадают во всех разрядах, и не равны между собой во всех остальных случаях. Например: 0-0--01=0-0--01¹-00--01.

С обобщенными кодами могут производиться различные логические операции: поразрядная инверсия (полная или частичная), поразрядная конъюнкция, поразрядная дизъюнкция и т.п. Рассмотрим эти операции.

1. Поразрядная инверсия (полная инверсия) , где инверсия над каждым разрядом осуществляется по правилу табл. 41.

Таблица 41

Полная поразрядная инверсия

ε	0	-	1	Æ
	1	Æ	0	-

 

2. Обращение кода, или частичная поразрядная инверсия , где операция обращения каждого разряда осуществляется по правилу табл. 42.

Таблица 42

Частичная поразрядная инверсия

ε	0	-	1	Æ
^ε	1	-	0	Æ

 

3. Поразрядная конъюнкция двух ОК (пересечение двух ОК) ω₁Ùω₂, являющаяся результатом выполнения в каждом разряде операции, заданной табл. 43.

Таблица 43

Поразрядная конъюнкция

Ù		εj
		0	-	1	Æ
εi	0	0	0	Æ	Æ
	-	0	-	1	Æ
	1	Æ	1	1	Æ
	Æ	Æ	Æ	Æ	Æ

 

4. Поразрядная дизъюнкция двух ОК (объединение двух ОК) ω₁Úω₂, являющаяся результатом выполнения в каждом разряде операции, заданной табл. 44.

Таблица 44

Поразрядная дизъюнкция

Ú		εj
		0	-	1	Æ
εi	0	0	-	-	0
	-	-	-	-	-
	1	-	-	1	1
	Æ	0	-	1	Æ

 

Примеры выполнения операций с обобщенными кодами:

Обобщенные коды, поразрядная конъюнкция которых равна пустому (мнимому) коду, называют непересекающимися (противоречивыми или ортогональными).

Обобщенный код А включает в себя обобщенный код В (ОК А содержит в себе ОК В, ОК В включается в ОК А, ОК В содержится в ОК А), если АÙВ=В или АÚВ=А.

Вместо словесной формулировки «ОК А включает в себя ОК В» применяют запись АÊВ или ВÍА.

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

Исходная система переключательных функций представляется обобщенной таблицей состояний (ОТС, табл. 45).

Таблица 45

Обобщенная таблица состояний

№ п/п	Входы x4 – x1	Выходы z6 – z1
1	00-0	-111--
2	0-0-	1--1-1
3	0011	-101-1
4	011-	100111
5	1-00	----00
6	1-11	011011
7	1110	00--0-

 

Исходная таблица состояний является непротиворечивой (задает непротиворечивую систему логических функций), если каждой паре пересекающихся входных ОК (т.е. таких a_i и a_j, что a_iÙa_j¹Æ) соответствуют пересекающиеся выходные ОК (т.е. такие b_i и b_j, что b_iÙb_j¹Æ).

В частности, приведенная в качестве примера таблица состояний является непротиворечивой.

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

Построение первичной таблицы соответствия.

Таблица соответствия состоит из таких же столбцов, как и таблица состояний, но в качестве входных ОК в нее включаются минимизированные коды. Таблица соответствия заполняется по строкам путем преобразования очередной строки таблицы состояний в соответствии со следующей методикой.

Рассматривается очередная (i-я), ранее не рассмотренная строка таблицы состояний, содержащая наименьшее количество единиц в выходном ОК.

Если выходной ОК i-й строки не содержит ни одной единицы, то i-ю строку отмечают и переходят к рассмотрению следующей строки таблицы состояний.

В противном случае осуществляется минимизация входного кода рассматриваемой строки.

Для минимизации входной ОК i-й строки берется в качестве рабочего ОК, а в качестве запрещенных ОК берутся входные ОК тех строк таблицы состояний, в которых содержится хотя бы один 0 в тех же разрядах выходных ОК, в каких в рассматриваемой i-й строке находились единицы.

Так, при рассмотрении строки 2 исходной таблицы (см. табл. 45), имеем: f₂=a₂,[a₅,a₆,a₇]=0-0-,[1-00,1-11,1110]=0---.

В данном случае минимизация проведена методом на основе перебора обобщенных кодов [6]. Этот метод целесообразно применять в тех случаях, когда рабочие и запрещенные наборы непосредственно заданы совокупностями обобщенных кодов, либо когда в связи с большим количеством рабочих и (или) запрещенных кодов предварительно проведено их раздельное склеивание (например, методом Квайна-Мак-Класки).

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

Получив по одному из рабочих кодов результирующий минимизированный код, из множества рабочих кодов удаляют все рабочие коды, входящие в найденный результирующий. Затем рассматривается очередной рабочий код и т.д. до тех пор, пока список рабочих кодов не будет исчерпан.

В нашем случае рабочий код один, запрещенных кодов три: f₂=a₂,[a₅,a₆,a₇]=0-0-,[1-00,1-11,1110].

0	-	0	-
1	-	0	0
1	-	1	1
1	1	1	0

Рабочий код противоположен всем запрещенным кодам в одном разряде, который является обязательным и переносится в минимизированный код 0---.

Полученный минимизированный входной ОК записывается в очередную строку таблицы соответствия в столбец входов. В качестве выходного ОК в эту строку таблицы соответствия заносится выходной ОК рассматриваемой строки таблицы состояний (для строки 2 таким кодом является код 1--1-1).

После заполнения очередной строки таблицы соответствия отмечается i-я строка таблицы состояний как рассмотренная и осуществляется преобразование выходных ОК, находящихся в неотмеченных ранее строках таблицы состояний.

Если какой-либо входной ОК неотмеченной j-й строки таблицы состояний (a_j) включается в минимизированный входной ОК f_i последней строки таблицы соответствия (a_jÍ f_i), то в выходном ОК (b_j) j-й строки таблицы состояний единицы, находящиеся в тех же разрядах, в которых выходной код (b_i) i-й строки таблицы состояний содержат единицы, заменяются на тире.

Так, после минимизации входного кода строки 2 исходной таблицы (см. табл. 45) получаем a₁=(00-0)Í(0---)=f₂; b₂=(1--1-1), следовательно, b₁=(-111--) преобразуется в b₁^*=(-11---). Аналогично из a₃=(0011)Í(0---)=f₂ следует, что код b₃=(-101-1) преобразуется в b₃^*=(-10---), а из a₄=(011-)Í(0---)=f₂ вытекает преобразование кода b₄=(100111) в код b₄^*=(-00-1-).

После преобразования выходных ОК неотмеченных строк таблицы состояний рассматривается очередная строка и т.д. до тех пор, пока не будут рассмотрены все строки этой таблицы.

Построение первичной таблицы соответствия проиллюстрируем следующим примером.

Пусть задана исходная обобщенная таблица состояний (см. табл. 45), по которой требуется построить первичную таблицу соответствия.

Строки 5 и 7 исходной ОТС в выходных ОК не содержат ни одной единицы. Поэтому отмечаем эти строки (в табл. 46 они отмечены символом Ú₀) и отыскиваем следующую строку исходной ОТС, содержащую наименьшее количество единиц в выходном ОК. Такой строкой является строка 1. Производим минимизацию входного ОК этой строки: f₁=a₁,[a₃,a₄,a₆,a₇]=00-0,[0011,011-,1-11,1110]=-0-0.

Обобщенный код f₁=(-0-0) заносим в качестве входного в первую строку таблицы соответствия, а код b₁=(-111--) заносим в эту же строку в качестве выходного кода (см. строку 1 табл. 47). После этого отмечаем строку 1 исходной ОТС как рассмотренную. Поскольку минимизированный код f₁=(-0-0) не включает в себя ни одного входного ОК из неотмеченных строк исходной ОТС, то преобразование выходных ОК неотмеченных строк ОТС не осуществляется. На этом завершается первый шаг построения первичной таблицы соответствия.

Таблица 46

Обобщенная таблица состояний

№ п/п	Входы x4 – x1	Выходы z6 – z1
1	00-0	-111--	Ú1
2	0-0-	1--1-1	Ú2
3	0011	-10+-+	Ú3
4	011-	+00+++	Ú4
5	1-00	----00	Ú0
6	1-11	011011	Ú5
7	1110	00--0-	Ú0

 

Таблица 47

Первичная таблица соответствия

№ п/п	Входы x4 – x1	Выходы z6 – z1
1	-0-0	-111--
2	0---	1--1-1
3	-0--	-10---
4	0---	-00-1-
5	1--1	011011

 

На втором шаге отыскиваем очередную неотмеченную строку ОТС с наименьшим количеством единиц в выходном ОК. Такой строкой является строка 2. В результате минимизации входного ОК этой строки получаем: f₂=a₂,[a₅,a₆,a₇]=0-0-,[1-00,1-11,1110]=0---. Этот код заносим в качестве входного во вторую строку первичной таблицы соответствия, в качестве выходного кода этой строки записываем код b₂=(1--1-1), как это показано в строке 2 табл. 47. Затем отмечаем строку 2 ОТС как рассмотренную (в табл. 46 строка 2 отмечена символом Ú₂). Поскольку минимизированный код f₂=(0---) включает в себя входной код третьей строки, f₂=(0---)Ê(0011)=a₃, то в выходном коде b₃=(-101-1) единицы, содержащиеся в тех же разрядах, что и в выходном коде b₂=(1--1-1), заменяются на тире. Следовательно, вместо выходного кода b₃=(-101-1) теперь в ОТС будет записан код b₃^*=(-10---). Такая замена в табл. 46 условно показана знаком «+» в тех разрядах, где символ «1» был заменен на символ «-» (см. строку 3). Аналогично, так как f₂=(0---)Ê(001-)=a₄, то вместо b₄=(100111) в преобразованную ОТС заносится код b₄=(-00-1-), как это условно показано в строке 4 табл. 46.

На следующем шаге по строке 3 преобразованной ОТС заполняется строка 3 таблицы соответствия, затем по строке 4 ОТС – строка 4 таблицы соответствия и, наконец, по строке 6 ОТС – строка 5 таблицы соответствия. Поскольку все строки ОТС отмечены, то процесс построения первичной таблицы соответствия на этом этапе завершается (см. табл. 47).

Последовательное преобразование ОТС в процессе заполнения первичной таблицы соответствия условно отображено в табл. 46 следующим образом: отметка строки, выполненная на i-м шаге, делается символом «Ú_i», преобразование символа «1» в выходном коде в символ «-«показывается знаком «+» в соответствующем разряде.

Таким образом, в результате минимизации исходной ОТС (табл. 45) получена первичная таблица соответствия (табл. 47).

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

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

Преобразование таблицы соответствия состоит из двух этапов: объединения и поглощения.

На этапе объединения осуществляется, если это возможно, объединение всех строк, имеющих одинаковые входные ОК (a_i=a_j), при этом в качестве выходного ОК объединенной строки берется ОК, равный пересечению выходных ОК объединяемых строк (b_iÙb_j).

Так, в рассматриваемом примере (см. табл. 47) объединяются строки 2 и 4 первичной таблицы соответствия (a₂=a₄=0---), выходным ОК объединенной строки является код (1--1-1)Ù(-00-1-)=(100111).

Таблица соответствия после объединения строк имеет вид табл. 48.

 

Таблица 48

№ п/п	Входы x4 – x1	Выходы z6 – z1
1	-0-0	-111--
2	0---	100111
3	-0--	-10---
4	1--1	011011

Таблица соответствия

 

На этапе поглощения таблица соответствия проверяется на наличие выходных ОК, содержащихся друг в друге. Если какой-либо входной ОК a_i включает в себя некоторый другой код a_j (a_iÊa_j), то в выходном коде b_j осуществляется замена единиц, находящихся в тех же разрядах, в которых выходной код b_i содержит единицы, на тире.

Так, в рассматриваемом примере (см. табл. 48): a₃=(-0--)Êa₁=(-0-0), b₃=(-10---), b₁=(-111--).

Следовательно, в качестве выходного ОК строки 1 записываем b₁^*=(--11--).

Таблица соответствия после поглощения имеет вид табл. 49.

Таблица 49

№ п/п	Входы x4 – x1	Выходы z6 – z1
1	-0-0	--11--
2	0---	100111
3	-0--	-10---
4	1--1	011011

Таблица соответствия

 

Частные минимальные формы логических функций системы y_k-y₁ определяются из преобразованной таблицы соответствия по следующим правилам.

Частная минимальная форма логической функции y_j в общем случае равна дизъюнкции конъюнкций переменных, соответствующих тем входным обобщенным кодам, которые находятся в строках преобразованной таблицы соответствия, содержащих единицы в разрядах выходных ОК, сопоставленных с переменной y_j.

В рассматриваемом примере по табл. 49 получаем систему уравнений, заданную в виде совокупности обобщенных кодов:

Отсюда, переходя к алгебраической форме записи логических функций, получаем окончательную систему частных минимальных форм:

Множество конъюнкций системы равно  и имеет сложность S=6.

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

Множество конъюнкций системы при этом имеет вид  и имеет сложность S=8, что на 2 больше, чем при совместной минимизации системы.