Здавалка
Главная | Обратная связь

Метод диаграмм Вейча



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

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

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

Четыре верхних клетки диаграммы соответствуют двоичным наборам, в которых переменная х1 принимает значение 0; четыре нижних клетки соответствуют наборам, в которых переменная х1 принимает значение 1.

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

Рис. 1.

 

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

На рис. 2 приведены пример разметки диаграммы для логических функций четырех переменных.

Рис. 2.

 

Диаграммы Вейча для большего числа переменных могут быть составлены из диаграмм меньшего числа переменных. Например, диаграмму Вейча для пяти переменных можно составить, соединив две диаграммы для четырех переменных. При этом удобно подсоединять их друг к другу одноименными столбцами (рис. 3). Тогда соседними клетками будут также клетки столбцов, симметрично расположенных относительно линии присоединения диаграмм Вейча четырех переменных для одноименных строк.

Рис. 3.

 

В клетки, соответствующие конституентам единицы минимизируемой булевой функции, записываются единицы, а в остальные — нули. Поэтому исходная минимизируемая функция первоначально должна быть представлена в СДНФ. Если функция задана аналитически, то она приводится к СДНФ с помощью операции развертывания, заключающейся в умножении некоторых членов на выражение вида .

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

Для диаграммы Вейча четырех переменных (рис. 2) соседними клетками будут также клетки, расположенные в верхних и нижних строках для одноименных столбцов.

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

Каждой такой группе будет соответствовать группа склеивающихся конституент единицы. Причем количество клеток, входящих в одну группу, равно 2k (где k = 1, 2, 3, ...), а каждая клетка, входящая в группу, должна иметь k соседних клеток.

Для получения минимальной ДНФ достаточно выполнить следующие условия:

каждая единичная клетка должна входить хотя бы в одну группу (при этом одна и та же клетка может входить в несколько групп);

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

количество групп должно быть минимальным.

Рекомендации по минимизации булевых функций с использованием диаграмм Вейча:

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

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

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

Группе, состоящей из 2k клеток, соответствует конъюнкция из nk букв, где n — число переменных в исходной булевой функции.

 

Пример 1. Найти минимальную ДНФ для булевой функции трех переменных, заданных следующей таблицей истинности(табл.1):

Таблица 1

№ набора х1 х2 х3 z
 
 
 
 

 

СДНФ для этой функции

.

Составим диаграмму Вейча (рис. 4)

 

Рис. 4

 

Здесь возможны два варианта склеивания:

1) склеивается с по переменной x1 – образуется импликанта ; склеивается с по переменной x1 – образуется импликанта ; склеивается с по переменной x3 – образуется импликанта . Отсюда получается первая минимальная ДНФ

;

2) склеивается с по переменной x1 – образуется импликанта ; склеивается с по переменной x1 – образуется импликанта ; склеивается с по переменной x2 – образуется импликанта . Отсюда получается вторая минимальная ДНФ

.

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

Пример 2. Найти минимальную ДНФ для булевой функции четырех переменных, заданных следующим выражением (в СДНФ):

Диаграмма Вейча для этого случая приведена на рис. 5.

Рис. 5.

Здесь возможно склеивание по четырем конституентам единицы:

; ; ; склеиваются по переменным х2 и х4 – образуется импликанта ;

; ; ; склеиваются по переменным х2 и х3 – образуется импликанта ;

 

 

; ; ; склеиваются по переменным х1 и х4 – образуется импликанта .

Таким образом, окончательное выражение для минимальной ДНФ:

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

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

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

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

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

 

Пример 3. Минимизировать булеву функцию четырех переменных, заданную диаграммой Вейча (рис. 6), только на 11-ти наборах двоичных аргументов. Неопределенные значения на диаграмме отмечены прочерком.

Рис. 6.

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


Метод Квайна

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

Метод Квайна основан на последовательном применении к парам дизъюнктивных членов операций склеивания и элементарного поглощения.

Операция склеивания основана на справедливости тождества . Операция элементарного поглощения — на справедливости тождеств х1Úх1х2 = х1 и х1(х1Úх2) = х1.

Вначале в СДНФ исходной булевой функции проводят все возможные операции склеивания дизъюнктивных членов — конъюнкций ранга n, где n — число аргументов функции. В результате склеивания получим конъюнкции n – 1 ранга. После выполнения операции поглощения с конъюнкциями n – 1 ранга осуществляют все возможные операции склеивания конъюнкций n – 1 ранга. Затем проводят операции поглощения с конъюнкциями n – 2 ранга и вновь выполняют операции склеивания и т.д.

Пример 4. Найти сокращенную ДНФ булевой функции

1) Используя операцию развертывания, представим исходную функцию в СДНФ. Для этого первуй член умножим на , второй член умножим на , третий член умножим на , а четвертый член умножим на . В результате получим СДНФ:

2) Пронумеруем все дизъюнктивные члены.

3) Выполним все возможные операции склеивания дизъюнктивных членов в такой последовательности:

первый член со всеми остальными,

второй член с остальными, кроме первого,

третий член с остальными, кроме первого и второго, и т.д.

В результате проведенных операций склеивания и поглощения получим ДНФ заданной функции в форме

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

.







©2015 arhivinfo.ru Все права принадлежат авторам размещенных материалов.