Минимизация не полностью определенных ФАЛ

Если при синтезе логической схемы, реализующей некоторую ФАЛ n переменных, окажется, что некоторые наборы из общего числа 2ⁿ никогда не смогут появиться на входах схемы, то данная логическая функция не определена на этих наборах. Тогда 2ⁿ наборов переменных можно подразделить на три группы: множество наборов L, на которых функция принимает единичное значение, множество наборов D, на которых функция принимает нулевое значение, и множество наборов N, на которых функция не определена (неопределенные наборы). ФАЛ, содержащая неопределенные наборы, называется не полностью или частично определенной. Неопределенные наборы могут быть использованы для улучшения качества минимизации. При этом неопределенные наборы (при минимизации, например, картами Вейча, Карно) могут участвовать в образовании контуров как с единичными, так и с нулевыми наборами. Это приводит к формированию более простой минимизированной логической функции.

	x2
x1	1		1	*
	*
	x 3

Звездочками на карте (рис. 21) отмечены наборы, на которых функция f не определена. Если не учитывать неопределенные наборы, то минимальная форма будет иметь вид: . В случае если неопределенные наборы участвуют в образовании контуров, а следовательно, и f_МДНФ, то функция примет следующий вид: . Таким образом, схемная реализация получен- ной f_МДНФ будет ”дешевле”.

Приведем примеры минимизации частичных булевых функций (рис.22).

Кубическое задание функций алгебры логики

Как следует из рассмотренного выше, функция алгебры логики (булева функция) может быть задана:

§ аналитически (системой булевых функций);

§ словесным описанием;

§ таблицей истинности;

§ картами (диаграммами) Венна, Вейча, Карно;

§ логической схемой.

Более компактной формой записи функций алгебры логики является форма, когда вместо полного перечисления всех конъюнкций (дизъюнкций) используют номера наборов, на которых функция принимает единичное значение. Так, например, форма записи f(x₁x₂x₃)=V F(0,2,3) означает, что функция от трех переменных принимает единичное значение на 0, 2 и 3 наборах таблицы истинности. Такая форма записи называется числовой.

Некоторые методы минимизации ориентируются на задание булевой функции в виде кубического покрытия. При этом логическая функция удобно интерпретируется с использованием ее геометрического представления. Так, функцию двух переменных можно интерпретировать как плоскость, заданную в системе координат х₁х₂. Получится квадрат, вершины которого соответствуют комбинациям переменных. Для геометрической интерпретации функции трех переменных используется куб, заданный в системе координат х₁х₂х₃ .

Новое представление булевой функции получается путем отображения булевой функции n переменных на n-мерный куб (n-куб).

Для отображения булевой функции n переменных на n-кубе устанавливается соответствие между членами СДНФ и вершинами n-куба. На n-кубе определим координатную систему с координатами (e₁,......,e_n), e_i=0,1.

Установим соответствие между членом СДНФ x₁^e1 x₂^e2... x_n^en и некоторой вершиной e₁,e₂,....,e_n куба. При этом x_i^ei = x_i, если e_i=1, и x_i^ei = x_i, если e_i=0.

Рис.23. Геометрическое представление функции двух и трех переменных

Каждый набор при кубическом задании ФАЛ называется кубом.

Как следует из таблицы истинности (табл. 14), функция f определена на трех группах наборов переменных: L={3,4,5,6,7}, D={0,2} и N={1}.

Конъюнкции максимального ранга (конституенты единицы) принято называть 0-кубами. Множество 0-кубов образуют кубический комплекс

Таблица 14
	х1	х2	х3	f
				-

011

К⁰ = 101.

Над 0-кубами, кодовое расстояние которых равно 1, выполняется операция склеивания, в результате которой образуются новые кубы, содержащие свободные координаты. Свободная (независимая) координата может принимать как нулевое, так и единичное значение, остальные компоненты называются связанными. Куб, содержащий свободные координаты, покрывает кубы, на которых он образован. Куб с одной независимой координатой х называется кубом первой размерности и в геометрическом представлении это ребро, покрывающее обе вершины. Кубы, образующиеся в результате последовательного выполнения операции склеивания, назовем r-кубами, где r – размерность полученного куба.

Геометрическая интерпретация сказанного приведена на рис. 24. В результате склеивания кубов 101 и 111 (0-кубы, вершины) образован 1-куб 1x1 (ребро), а 1-кубов 00x и 10х - 2-куб х0х (грань).

Рис. 24. Образование новых кубов

Кубическое представление ФАЛ позволяет обойтись тремя переменными 0,1,х вместо х₁, х₂,...,х_n .

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

Цена схемы определяется количеством входов элементов, используемых для ее реализации:

,

где k − количество полученных кубов; n-r_i − количество единичных и нулевых значений

Два r-куба могут образовать r+1-куб, если в этих r-кубах все координаты, в том числе и свободные, совпадают, за исключением лишь какой-либо одной, которая в этих кубах имеет противоположное значение.

На рис. 25 приведено изображение куба, соответствующего булевой функции от четырёх переменных (гиперкуб).

Рис. 25. Геометрическое представление функции четырех переменных

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

Метод Квайна −Мак-Класки

Этот метод ориентирован на числовое задание ФАЛ в виде кубического комплекса, состоящего из 0-кубов. Метод представляет собой формализованный на этапе нахождения простых импликант метод Квайна. Основной недостаток метода Квайна – необходимость выполнения полного сравнения (склеивания) всех первичных импликант. В случае большого их количества сложность этого сравнения существенно возрастает. В рассматриваемом методе все исходные n-кубы разбиваются на непересекающиеся подгруппы по количеству единиц в кубе. Пусть, например, задана функция

f _СДНФ(x₁x₂x₃x₄) = V (2, 3, 4, 6, 9, 10, 11, 12).

Сформируем кубический комплекс K, состоящий из 0-кубов:

K=(0010, 0011, 0100, 0110, 1001, 1010, 1011, 1100).

Выполнив разбиение комплекса K на группы, получим:

, , .

Попарное сравнение можно проводить только между соседними по номеру группами кубов, так как кубы, порождающие новые кубы, должны иметь кодовое расстояние, равное 1. В результате сравнения кубов получим:

, .

После выполнения первого шага алгоритма простых импликант не выявлено. Полученные 1-кубы разобьем на n групп кубов в зависимости от местоположения свободной координаты в кубе.

, , , .

Далее выполняется сравнение кубов внутри каждой из групп. В результате могут быть получены 2-кубы, которые, в свою очередь, аналогично 1-кубам будут объединены в группы по совпадению свободных координат и вновь будет выполнено сравнение. На каждом шаге сравнения выявляются кубы, не участвовавшие в образовании новых кубов, и исключаются из дальнейшего упрощения. Для рассматриваемого примера сравнение в группах … привело к образованию двух новых кубов х01х и х01х и кубов, не образовавших новых {х100, 0х10, 10х1, 01х0}.

, .

Дальнейшее сравнение не приводит к формированию новых кубов . Таким образом, получено множество простых импликант:

f_{сокр.ДНФ}={х100, 0х10, 10х1, 01х0, х01х}.

Далее аналогично методу Квайна строится импликантная таблица (табл.15). Формирование минимального покрытия сводится к выявлению обязательных простых импликант и построению на их основе тупиковых форм.

Таблица 15

	Простые импликанты	Конституенты единицы
	Х100		*		*
	0х10	*				*
	10х1						*		*
	01х0		*			*
	Х01х	*		*				*	*

Из таблицы следует, что простые импликанты x100, 10x1, x01x являются обязательными. Оставшиеся две простые импликанты не являются обязательными и образуют следующие две тупиковые формы.

f _МДНФ = {х100, 10х1, х01х, 0х10} – 1-я тупиковая форма;

f _МДНФ = {х100, 10х1, х01х, 01x0} – 2-я тупиковая форма.

Алгоритм извлечения (Рота)

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

Специальные логические операции алгоритма Рота: *, ∩, #

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

Операция умножения кубов (*). Операцияумножения кубов а=а₁а₂...а_n и b=b₁b₂...b_n обозначается как с=а*b и служит для образования r-куба, противоположные (r-1) грани которого содержатся в кубах а и b. Предварительные координаты куба c определяются в соответствии с таблицей, приведенной ниже.

*			х
		Y
ai 1	у
x			х

^{î ______________}_Ú^{_________________þ}

b_i

Окончательно координаты куба формируются:

m(a₁*b₁)m(a₂*b₂)... m(a_n*b_n), если a_i*b_i=y только для одного i,

a*b=

Æ, если a_i*b_i=y для i ³ 2,

где m(a_i*b_i) – окончательная i-я координата куба с; m(0)=0; m(1)=1; m(x)=x;

y – условное обозначение того, что координаты a_i и b_i противоположны.

Эта операция соответствует операции склеивания: образуется новый r-куб, если кодовое расстояние двух исходных кубов равно 1.

Рассмотрим некоторые примеры, графическая интерпретация которых приведена на рис. 26.

1) 011 2) 11х

* 001*01х

0y1 Þ 0x1– ребро покрывает две вершины у1х Þ х1х – грань

3) 0х1 4) х1х

*1х0 *011

уху Þ Æ – две координаты имеют значение у. 011

Операция пересечения кубов (∩). Операция пересечения кубов а=а₁а₂...а_n и b=b₁b₂...b_n обозначается как с=а ∩ b и служит для выделения куба с=с₁с₂...с_n , являющегося общей частью кубов а и b. Координаты с₁с₂...с_n определяются согласно следующей таблице.

∩			x
		Æ
ai 1	Æ
x			x

^{î______________}_Ú^{_________________þ}

b_i

m(a₁∩b₁)m(a₂∩b₂)... m(a_n∩b_n,),

a∩b=

Æ, если существует такое i, для которого a_i ∩ b_i =Æ,

где m(a_i*b_i) – окончательная i-я координата куба с; m(0)=0; m(1)=1; m(x)=x.

Рассмотрим примеры и их графическую интерпретацию (рис. 27).

1) _Ç100 2) _Ç1х0

00110х

Æ0Æ Þ Æ общей части у 100 Þ 100 общая часть

кубов нет кубов (рёбер) - вершина

3) _Çх1х 4) _Ç0хх

0хх 0х0

01х Þ 01х общая часть – ребро 0х0 (совпадает с

операцией *)

Операция вычитания кубов (#). Операция вычитания из куба а=а₁а₂...а_n куба b=b₁b₂...b_n обозначается как с=а#b и служит для удаления из куба а общей части кубов а и b.

Координаты куба с формируются согласно следующей таблице.

#			x
	z	y	z
ai 1	y	z	z
x			z

^{î ______________}_Ú^{_________________þ}

b_i

Æ, если для любого i а_i#b_i=z,

c=а#b= a, если существует такое i, что а_i#b_i=y,

U а₁а₂...а_i-1 a_i а_i+1 ... а_n, если a_i равно 0 или 1 для одного или

ⁱ⁼¹ нескольких i,

где z означает, что координаты совпадают, а y, как для операции *, означает, что координаты a_i и b_i противоположны.

По этим a_i-координатам производится объединение (U) кубов, получаемых в результате замены в кубе а символа х на соответствующее значение (0,1) координаты a_i. Рассмотрим примеры выполнения операции # и их графическую интерпретацию (рис. 28).

1) _#х1х 2) _# х1x

x11110

zz0 Þ x10 0z1 Þ 01x

3) _#хx1 4) _#х11 x11

x10 xx1

z0y Þ xx1 zzz Þ Æ

5) _# 0ххx

хх01

zz10 Þ 0x1x

0xx0

Далее рассмотрим алгоритм извлечения (Рота) на примере минимизации булевой функции, заданной покрытием С₀ (рис.29).

Рис. 29. Геометрическое задание исходного покрытия

Исходное покрытие С₀ задано объединением множеств кубов L и N. Кубы комплекса N − это наборы, на которых функция не определена и которые включаются в покрытие ради возможного дополнительного упрощения комплекса L в процессе минимизации. Минимальное покрытие комплексов L и N, С _min называется К-покрытием L.

Общий алгоритм построения минимального К-покрытия называется алгоритмом извлечения и состоит в следующем:

▪ нахождении множества Z простых импликант комплекса К;

▪ выделении L-экстремалей на множестве Z;

▪ применении алгоритма ветвления при отсутствии L-экстремалей;

▪ нахождении абсолютно минимального покрытия из некоторого множества избыточных покрытий.

Дата добавления: 2014-12-26