Алгоритмы минимизации булевых функций

Размещено на http://www.allbest.ru/

Введение

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

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

Если произвести минимизацию булевых функций, входящих в систему независимо друг от друга, то общая схема будет состоять из изолированных подсхем. Её можно иногда упростить за счет объединения участков подсхем, реализующих одинаковые члены, входящие в несколько булевых функций системы. Задача минимизации систем булевых функций хорошо исследована в классе функционально полных систем: «дизъюнкция», «конъюнкция», «отрицание».

Целью данной работы является рассмотрение алгоритмов минимизации булевых функций: Метод Квайна, Метод карт Карно, Метод Квайна и Мак-Класки, Метод диаграмм Вейча, Метод неопределенных коэффициентов.

1. Представление булевых функций

Используя законы булевой алгебры, можно получить для одной и той же логической функции множество эквивалентных представлений. Чем проще выражение функции, тем экономичнее ее практическая реализация на интегральных микросхемах. Сложность булевой функции определяется ее рангом, т.е. количеством переменных в ее конъюнктивных или дизъюнктивных членах. Пусть I = {0, 1} - множество, состоящее из двух элементов: 0 (ложь) и 1 (истина). Булевой функцией f : In I называется произвольная функция f(x1, x2, …, xn) от n аргументов, принимающая значения в I. Будем предполагать, что функции от n переменных определены для всех натуральных чисел n  0, причем функциями от 0 переменных являются константы 0 и 1.

Представление булевой функции в СовДНФ (совершено дизъюнктивной нормальной форме) в большинстве случаев не является минимальным.

Используя операции поглощения и склеивания, её можно существенно упростить. Часто используется неполное склеивание, при котором оба члена, участвовавших в склеивании (или один из них), могут повторно склеиваться с другими оставшимися членами Сов ДНФ.

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

Конституентой единицы (коньюнктивным термом) называется функция f(x1,x2,...,xn), принимающая значение 1 только на единственном наборе.

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

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

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

(1)

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

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

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

Найдем для примера тупиковую форму СокрДНФ (2)

Испытаем член AC. AC = 1, если A = 1 и C = 1. Подставим в оставшееся выражение  A = 1 и C = 1, получим

При B = 0 F(A, B, C) = 1·1 B 0·0 = 1, но при B=1 F(A, B, C) = 0·1 B 0·0 = 0. Следовательно, член AC не лишний.

Испытаем член BC, равный 1 при B = 0, C = 1. При этом выражение (3)

(3)

Последнее выражение равно 1 как при A = 1, так и при A = 0. Поэтому член - лишний.

Испытание члена по этой же методике показывает, что он не является лишним, в итоге тупиковая форма исходной функции имеет вид (4):

(4)

Способы представления булевых функций

Результат выполнения логических операций над двоичными переменными А, В, С, ... также представляет собой двоичную переменную F, которую называют булевой функцией. Наиболее распространены следующие способы представления булевых функций[5].

Табличный способ. При этом способе функция представляется в виде таблицы истинности, в которую вписываются все возможные наборы аргументов (А, В) и для каждого набора устанавливается значение функции F = 0 или F =1.

Таблица 1.1 - Таблица истинности

A	B	F
0	0	0
0	1	1
1	0	1
1	1	0

Алгебраический способ. Существует две формы представления функций в алгебраическом виде:

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

F(A, B, C) = AB + AC + BC (5)

СДНФ - совершенно ДНФ (каждое слагаемое содержит все переменные или их отрицания). Например выражение (6):

F(A, B, C) = ABC + AC + AB. (6)

КНФ - конъюнктивная нормальная форма, представляет собой логическое произведение элементарных логических сумм. Например выражение(7):

F(A, B, C) = (A + B)(A + + C) (7)

СКНФ - совершенная конъюнктивная нормальная форма (каждая сумма содержит все переменные или их отрицания). Например выражение (8):

F(A, B, C) = (A +  +)( + B +). (8)

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

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

2. Минимизация булевых функций

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

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

При небольшом числе переменных для минимизации булевых функций применяют диаграммы или карты Карно-Вейча. Карта Карно-Вейча - прямоугольник, разбитый на квадраты, число которых равно общему числу наборов для данной функции. На рисунке 2.1 показана карта Карно-Вейча для четырех переменных. Квадраты против черты с буквой соответствуют восьми наборам, на которых данная переменная равна 1. В квадратах также могут быть проставлены номера наборов[15].

Рисунок 2.1 - Карта Карно-Вейча для четырех переменных

Правила минимизации:

Соседними являются ячейки по горизонтали и по вертикали. Соседние ячейки с "1" значениями объединяются в группы. Группа может состоять только из 2i ячеек. Каждая группа "1" записывается как произведение аргументов с неизменными значениями на всех ячейках группы. Число групп должно быть минимальным, а их размер максимально возможным. Ячейка может входить в состав нескольких групп.

Покажем на примере применение карт Карно. Функция задана номерами единичных наборов, представленных в выражении (9): F(A, B, C, D) = ? (0, 3, 4, 5, 7, 8, 10, 11, 14, 15). (9)

Нанесем эту функцию на карту Карно. На карте Карно при нанесении на нее функции F, заполненными нулями остаются ячейки, относящиеся к наборам, на которых функция равна 0.

Произведя минимизацию, получим функцию (10) F = AC + CD +  + C. (10)

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

Рисунок 2.2 - Функция карт Карно Для оценки алгоритмов существует много критериев

Чаще всего нас будет интересовать порядок роста необходимых для решения задачи времени и емкости памяти при увеличении входных данных. Нам хотелось бы связать с каждой конкретной задачей некоторое число, называемое ее размером, которое выражало бы меру количества входных данных. Например, размером задачи умножения матриц может быть наибольший размер матриц - сомножителей[11].

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

Именно асимптотическая сложность алгоритма определяет в итоге размер задач, которые можно решить этим алгоритмом. Если алгоритм обрабатывает входы размера n за время c*n2, где c - некоторая постоянная, то говорят, что временная сложность этого алгоритма есть O(n2) (читается "порядка n - квадрат").

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

Допустим, у нас есть пять алгоритмов A1,A2,…,A5 со следующими временными сложностями:

Таблица 2.1 - Алгоритмы

Алгоритм	Временная сложность
A1	n
A2	n*log(n)
A3	n2
A4	n3
A5	2n

Здесь временная сложность - это число единиц времени, требуемого для обработки входа размера n. Пусть единицей времени будет одна миллисекунда (1сек=1000 миллисекунд). Тогда алгоритм A1 может обработать за одну секунду вход размера 1000, в то время как A5 - вход размера не более 9. В следующей таблице 2.1 приведены размеры задач, которые можно решить за одну секунду, одну минуту и один час каждым из этих пяти алгоритмов.

Таблица 2.2 - Размеры задач, решаемые за 1 секунду

Алгоритм	Временная сложность	Максимальный размер задачи
		1 сек	1 мин	1 час
A1	n	1000	6*104	3,6*106
A2	n*log(n)	140	4893	2*104
A3	n2	31	244	1897
A4	n3	10	39	153
A5	2n	9	15	21

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

Таблица 2.3 - Размеры задач, решаемые с большей скоростью

Алгоритм	Временная сложность	Максимальный размер задачи
		до ускорения	после ускорения
A1	n	S1	10 S1
A2	n*log(n)	S2	Примерно 10 S2 для больших S2
A3	n2	S3	3,165 S3
A4	n3	S4	2,155 S4
A5	2n	S5	S5+3,3

Вместо эффекта увеличения скорости рассмотрим теперь эффект применения более действенного алгоритма. Если в качестве основы для сравнения взять 1 мин, то, заменяя алгоритм A4 алгоритмом A3, можно решить задачу, в 6 раз большую, а заменяя A4 на A2, можно решить задачу, большую в 125 раз. Эти результаты производят гораздо большее впечатление, чем двукратное улучшение, достигаемое за счет десятикратного увеличения скорости. Если в качестве основы для сравнения взять 1 ч, то различие оказывается еще значительнее. Отсюда мы заключаем, что асимптотическая сложность алгоритма служит важной мерой качественности алгоритма, причем такой мерой, которая обещает стать еще важнее при последующем увеличении скорости вычислений.

Несмотря на то что основное внимание здесь уделяется порядку роста величин, надо понимать, что большой порядок роста сложности алгоритма может иметь меньшую мультипликативную постоянную (постоянная c в определении О(f(x))), чем малый порядок роста сложности другого алгоритма. В таком случае алгоритм с быстро растущей сложностью может оказаться предпочтительнее для задач с малым размером - возможно, даже для всех задач, которые нас интересуют. Например, предположим, что временные сложности алгоритмов A1, A2, A3, A4, A5 в действительности равны соответственно 1000n, 100n*log(n), 10n2, n3 и 2n. Тогда A5 будет наилучшим для задач размера 2?n?9, A2 - для задач размера 10?n?58, A1 - при 59?n?1024, а A1 - при n>1024[7].

2.1 Метод Квайна

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

При минимизации по методу Квайна предполагается, что минимизируемая логическая функция задана в виде ДСНФ. Здесь используется закон неполного склеивания. Минимизация проводится в два этапа: нахождение простых импликант, расстановка меток и определение существенных импликант (Q - матрица).

Метод Квайна основывается на применении двух основных соотношений.

Соотношение склеивания(11)

 (11)

где А - любое элементарное произведение.

Соотношение поглощения(12) (12)

Справедливость обоих соотношений легко проверяется.

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

Метод применим к совершенной ДНФ. Из соотношения поглощения следует, что произвольное элементарное произведение поглощается любой его частью.

Для доказательства достаточно показать, что произвольная простая импликанта р =  может быть получена. В самом деле, применяя к р операцию развертывания (обратную операции склеивания): по всем недостающим переменным исходной функции f, получаем совокупность S конституент единицы. При склеивании всех конституент из S получим импликанту р. Последнее очевидно, поскольку операция склеивания обратна операции развертывания. Множество S конституент обязательно присутствует в совершенной ДНФ функции f поскольку р - ее импликанта[4].

Минимизация по методу Квайна выполняется по следующему алгоитму:

1. Выполняются все склеивания в СДНФ.

2. Выполняются все поглощения.

3. Результирующая функция проверяется на возможность дальнейшего склеивания и поглощения.

4. После получения сокращенной ДНФ строится импликантная матрица, по которой находятся “лишние” импликанты.

Пример. Пусть имеется булева функция, заданная таблицей истинности. Ее СДНФ имеет вид(13):

(13)

Для удобства изложения пометим каждую конституенту единицы из СДНФ функции f каким-либо десятичным номером (произвольно). Выполняем склеивания. Конституента 1 склеивается только с конституентой 2 (по переменной х3) и с конституентой 3 (по переменной х2) конституента 2 с конституентой 4 и т. д. В результате получаем:

1-2:

1-3: 

2-4: 

3-4:

4-6: 

5-6: 

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

Далее производим склеивания получаемых элементарных произведений. Склеиваются только те произведения, которые содержат одинаковые переменные. Имеет место два случая склеивания:

=

(14)

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

(15)

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

Таблица 2.4 - Импликантная матрица

Простые	Конституенты единицы
импликанты
	Х	Х	Х	Х
				Х		Х
					Х	Х

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

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

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

Пример (продолжение). Ядром нашей функции являются импликанты  и . Импликанта  - лишняя, так как ядро накрывает все столбцы импликантной матрицы. Поэтому функция имеет единственную тупиковую и минимальную ДНФ: fmin= (16)

Следует отметить, что число N крестиков в одной строке всегда является степенью 2. Более того, читатель может легко убедиться в том, что N = 2n-k, где k - число букв, содержащихся в простой импликанте.

Заметим также, что используя различные соотношения, можно расширить область применения метода Квайна за пределы совершенной ДНФ.

Алгоритм Квайна позволяет получать минимальные дизъюнктивные нормальные формы заданных функций. Однако, в ряде случаев минимальные конъюнктивные нормальные выражения оказываются "меньше" дизъюнктивных, поэтому при решении задач минимизации желательно получить не только дизъюнктивные, но и конъюнктивные нормальные формулы и выбрать из них наименьшее. Методы получения минимальных конъюнктивных выражений двойственны рассмотренным выше методам и мы не будем на них останавливаться[6].

2.2 Минимизация булевых функций методом Карно

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

Рисунок 2.3 - Карта Карно в форме ДСНФ

Пусть задана функция 3-х переменных (17) Заданную функцию представим с помощью карты Карно:

Рисунок 2.4 - Карта Карно

Затем производится объединение 2-х, 4-х или 8-ми единиц. В данном случае объединение двух единиц по горизонтали соответствует операции склеивания над конституентами и, в результате которой исключается переменная B и получена импликанта . Объединение двух единиц по вертикали соответствует операции склеивания над конституентами и , в результате которой исключена переменная Си будет получена импликанта . Следовательно, минимальная форма заданной функции примет следующий вид: . (18)

Ниже приведен пример, поясняющий процесс минимизации функции 3-х переменных методом Карно.



Рисунок 2.5 -Процесс минимизации функции 3-х переменных методом Карно.

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

Рассмотрим минимизацию функции 4-х переменных. Пусть задана функция .

Представим в виде карты Карно.

Рисунок 2.6 -Процесс минимизации функции в виде карты Карно.

В данном случае возможно объединение 4-х единиц, в результате получим минимальную форму y=BD.

Ниже приведены примеры минимизации функции 4-х переменных(рисунок 2.8).



Рисунок 2.7 - Процесс минимизации функции 3-х переменных методом Карно.

Методом Карно возможна минимизация функций 5 переменных. Карта в этом случае имеет 32 поля. Рассмотрим минимизацию следующей функции 5 переменных y=f(A,B,C,D,E), которая задана в виде карты Карно (рисунок 2.9).

В результате минимизации, получим следующую форму(19):

. (19)

Таким образом, при объединении 2-х полей исключается одна переменная, при объединении 4-х полей - две переменные, при объединении 8-ми полей - три переменные.

Метод Карно целесообразно применять для функций, имеющих не более 5 переменных. При большом количестве переменных используют формальные методы Квайна или Квайна-Мак-Класки[12].



Рисунок 2.8 - Минимизация функций 5 переменных

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

Минимизация методом диаграмм Вейча и карт Карно в силу своей наглядности широко используется при ручном процессе минимизации логических функций от небольшого количества переменных, обычно не превышающего пяти. В случае, когда количество переменных больше, необходимо использовать методы, характеризующиеся однозначностью алгоритма, что позволяет автоматизировать процесс минимизации на ЭВМ. Одним из таких методов является метод Квайна и Мак-Класки. Суть метода состоит в следующем:

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

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

3. все склеенные конституенты, образующие импликанты, отмечают каким-либо признаком, например звездочкой;

4. не отмеченные при склеивании импликанты являются простыми и заносятся в импликантную матрицу, в первой строке которой записываются все конституенты единицы функции f, а в первом столбце - все простые импликанты;

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

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

7. соответствующие этим звездочкам простые импликанты называются базисными и образуют ядро функции f и обязательно входят в МДНФ;

8. рассматриваются столбцы импликантной матрицы и выделяются те, которые содержат более одной звездочки;

9. если среди выделенных столбцов существуют такие, которые покрываются базисными импликантами из ядра функции, то они считаются уже учтенными в записи МДНФ, если же выделенные столбцы базисными импликантами не покрываются, то в МДНФ записываются импликанты соответствующих столбцов с минимальным переменных [10].

Рассмотрим пример минимизации функции f методом Квайна и Мак-Класски. Функция принимает единичные значения при следующих значениях переменных А, В и С - 000, 010, 011, 111, которые и образуют конституенты единицы. Эти конституенты можно записать в четыре группы по количеству в них единиц:

группа 0: 000 *; группа 1: 010 *;

группа 2: 011 *;

группа 3: 111 *.

Таблица 2.5 - Минимизация методом Квайна и Мак-Класки

Простые импликанты	Конституенты единицы
	000	010	011	111
0-0	*	*
01-		*	*
-11			*	*

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

группа 1: 0-0;

группа 2: 01-;

группа 3: -11.

Дальнейшее склеивание соседних импликант возможно только при наличии прочерка в одинаковых позициях. В нашем примере это условие не выполняется и, поэтому, образованные импликанты являются простыми. Из полученных простых импликант составляется импликантная матрица, в первой строке которой записываются все конституенты единицы, а в первом столбце - все простые импликанты. Звездочкой отмечаются все пересечения строк и столбцов, в которых импликанты покрывают конституенты единицы.

В матрице находим столбцы, содержащие по одной звездочке. Это столбцы с конституентами 000 и 111. Одиночным звездочкам в них соответствуют импликанты 0-0 и -11. Эти импликанты являются базисными, образуют ядро логической функции и обязательно входят в состав МДНФ. Далее выделяются столбцы, содержащие более одной звездочки. Такими столбцами являются столбцы с конституентами 010 и 011. Поскольку эти конституенты покрываются импликантами 0-0 и -11 из ядра функции, то импликанта 01- является лишней и в МДНФ не входит. В результате имеем в составе МДНФ импликанты 0-0 и-11. Заменив двоичные коды полученных импликант на обозначения переменных в прямом и инверсном виде, получим окончательную запись МДНФ функции: , что соответствует результату минимизации методом диаграмм Вейча.

Рассмотрим пример минимизации ФАЛ четырех переменных методом Квайна и Мак-Класски. Пусть задана функция в виде последовательности десятичных чисел(20):

f(A,B,C,D)=v(1,2,3,5,6,7,10,11,14,15) (20)

Запишем конституенты единицы функции f в виде двоичных кодов(21):

. (21)

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

группа 0: ;

группа 1: 0001 **, 0010 ***;

группа 2: 0011 ****, 0101 **, 0110 **, 1010 ***;

группа 3: 0111 ****, 1011 ***, 1110 **;

группа 4: 1111 ***.

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

группа 1: 00-1 *, 0-01 *, 001- **, 0-10 **, -010*;

группа 2: 0-11 ***, -011 **, 01-1 *, 011- **, 101- *, 1-10 **;

группа 3: -111 *, 1-11 **, 111- *.

Продолжим дальнейшее склеивание импликликант из соседних групп, причем склеивание возможно, только между импликантами с прочерками в одинаковых позициях:

группа 1: 0--1, 0--1, 0-1-, -01-, 0-1-, --10, -01-;

группа 2: --11, --11, -11-, 1-1-, 1-1-. 

Перепишем, оставив только неповторяющиеся импликанты:

группа 1: 0--1, 0-1- *, -01- *, --10 *;

группа 2: --11 *, -11- *, 1-1- *.

Продолжим склеивание:

Группа 1: --1-, --1-, --1-.

Не отмеченные звездочками импликанты являются простыми: 0--1 и --1-. Построим импликантную матрицу:

Из матрицы видно, что столбцы, содержащие по одной звездочке соответствуют обеим простым импликантам и, следовательно, обе эти импликанты являются базисными, образуют ядро ФАЛ и входят в МДНФ. Заменяя двоичные коды импликант соответствующими переменными, запишем вид МДНФ: . В истинности полученного выражения можно убедиться подстановкой всех возможных значений входных переменных A, B, C, и D.

При минимизации частично определенной функции недостающие наборы выбираются произвольно исходя из соображения получения наименьшего количества простых импликант, по возможности содержащих минимальное количество переменных. На диаграмме Вейча такие импликанты будут определяться максимально большими прямоугольниками. Поэтому при минимизации частично определенной ФАЛ в диаграмму Вейча заносят все определенные значения функции в виде соответствующих нулей и единиц. В неопределенных ячейках дописываются нули и единицы до образования максимально склеиваемых областей, соответствующих простым импликантам с наименьшим количеством переменных. Например, если для заданной функции трех переменных заполненная диаграмма Вейча имеет вид (прочерками указываются неопределенные значения), представленный на рисунке 2.10а, то после дополнения единиц в позициях и, диаграмма Вейча примет вид, представленный на рисунке 2.10,б. В результате склеивания МДНФ запишется f=C[14].

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

Рассмотрим один из алгоритмов минимизации, предложенный американский ученым Вейчем. Вейч предложил специальные диаграммы-карты, в которые можно записать все конституенты единицы, входящие в СДНФ (конституенты нуля, входящие в СКНФ) той или иной булевой функции. На рисунке 2.11 в качестве примера приведены диаграммы для минимизаций функций двух, трех и четырех переменных соответственно.

Рис. 2.11 - Диаграммы Вейча для функций 2-х, 3-х и 4-х переменных.

Каждой клетке диаграммы в случае минимизации СДНФ соответствует определенная конституента единицы. Метод минимизации с помощью диаграмм Вейча заключается в следующем. Конституенты единицы, входящие в СДНФ булевой функции, заносятся в соответствующие клетки диаграммы. Удобно наличие соответствующей конституенты единицы изображать в клетке диаграммы цифрой 1, а отсутствие - 0. Все диаграммы построены таким образом, что рядом расположенные единицы по горизонтали или вертикали склеиваются между собой в соответствии с законом склеивания алгебры логики. Одну и ту же конституенту единицы можно использовать для склеивания с несколькими другими конституентами единицы с целью получения наиболее простого окончательного выражения. Цель всех операций - получить как можно меньшее число прямоугольников (в том числе квадратов), чтобы число членов СДНФ уменьшилось, получив в итоге МДНФ. булевая функция минимизация карно

Формировать прямоугольники можно только при включении в них хотя бы одного нового осуществлять и путем замыкания крайних ребер в «бочку». Таким образом, полученная диаграмма Вейча геометрически образует цилиндр. На рисунке 2.12 приведены некоторые правила склеивания конституент единицы для функций 2-х и 3-х переменных.



Рисунок 2.12 - Примеры для иллюстрации правил склеивания.

Метод минимизации СДНФ с помощью диаграмм Вейча включает в себя следующие шаги:

1. производится занесение в соответствующую диаграмму конституент единицы, входящих в СДНФ минимизируемой функции;

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

3. находится искомая минимальная дизъюнктивная нормальная форма (МДНФ) ФАЛ выбором минимальной совокупности простых импликант, покрывающей все конституенты единицы диаграммы.

В качестве примера найдем МДНФ функции. Диаграмма Вейча этой функции представлена на рисeyrt 2.13. Из рисунка видно, что в результате склеивания образовались две простые импликанты: BC и . Импликанта участвует в склеивании с конъюнкциями: BC и  и поэтому не является простой. Таким образом, полученная вид f=BC. В истинности полученного выражения можно убедиться путем подстановки всех наборов переменных А, В и С.



Рисунок 2.13 - Пример минимизации функции

Аналогом диаграмм Вейча являются карты Карно. Они позволяют изображать на плоскости прямоугольника конституенты единицы (нуля) более четырех переменных. В отличие от диаграмм Вейча, в которых отдельным строкам и столбцам соответствуют отдельные переменные, в картах Карно им можно присваивать значения нескольких переменных. При этом должны быть представлены все возможные комбинации этих переменных, например: AB, ,  и . Таким образом, общее количество переменных минимизируемой с помощью карты Карно может быть больше, чем в случае использования диаграмм Вейча. Сам процесс минимизации аналогичен описанному на примере диаграмм Вейча [8].

2.5 Метод неопределенных коэффициентов

Этот метод может быть использован для любого числа аргументов. Но так как этот метод достаточно громоздок, то применяется только в тех случаях, когда число аргументов не более 5-6.

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

Построим матрицу неопределенных коэффициентов для четырех аргументов. В этом случае мы будем иметь систему из 16-ти уравнений.

Система приведена на странице.

Приравняем все коэффициенты 0 в тех строках, которым соответствует 0 в векторе столбце. Затем приравняем 0 соответствующие коэффициенты в других строках. После этих преобразований система примет следующий вид(22):

V = 1

V V V V VV = 1

V V V V VV = 1

V = 1 (22)

V V V = 1

V V V V VV = 1

V V V = 1

V V V VV = 1

V VV = 1

Теперь в каждой строке необходимо выбрать коэффициент минимального ранга и приравнять его единице, а остальные коэффициенты - 0. После этого вычеркиваем одинаковые строки, оставляя при этом одну из них (те строки, у которых все коэффициенты равны 0, также вычеркиваются)[1].

= 1

= 1 = 1 (23)

= 1

= 1

Запишем теперь конъюнкции, соответствующие коэффициентам, равным единицам. Мы получим минимальную ДНФ.

F(X1X2X3X4) = X1X3 V X2X3 V X3X4 V X1X2X4 V X1X2X4. (24)

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

3. Синтез схемы логического устройства

3.1 Схема алгоритма для метода Квайна

1. Начало.

2. Ввести матрицу ДСНФ исходной функции.

3. Проверить на склеиваемость i-ю (i=1,m-1: где m - количество строк в ДСНФ) и j-ую (j=i+1, m) строки. Если строки склеиваются, то перейти к пункту 6, в противном случае перейти к пункту 5.

4. Формировать массив простых импликант, предварительно пометив символом `*' ту переменную, по которой данные строки склеиваются.

5. Перейти к пункту 2.

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

7. Перейти к пункту 2.

8. Вывод полученной матрицы.

9. Конец.

10.

Логическая схема алгоритма в нотации Ляпунова 1 1

VHV1Z1V2V3V4VK (25)

VH - начало.

V1 - ввести матрицу ДСНФ исходной функции.

V2 - формировать массив простых импликант, предварительно пометив символом `*' ту переменную, по которой данные строки склеиваются.

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

V4 - вывод полученной матрицы.

Z1 - если строки склеиваются, то перейти к пункту 3, в противном случае перейти к пункту 5.

VK - конец.

3.2 Граф-схема алгоритма

Составим структуру работы логической схемы. Ниже приведена блок-схема

Рисунок 3.1 - Блок-схема логического устройства

Опание машинных процедур

Procedure Stuck(S1, S2: Diz; IndexS1, IndexS2 : byte);

Данная процедура склеивает два, передаваемых ей дизъюнкта. Дизъюнкты задаются в параметрах S1, S2. Индексы IndexS1, IndexS2 определяют индексы этих дизъюнктов в главном рабочем массиве . Алгоритм работы процедуры следующий: сначала ищется количество склеивающихся символов. Если их 0, то они одинаковые, и в конечный массив записывается только один из них. Если 1, то определяется местоположение символа, по которому данные две дизъюнкции склеиваются, и заменяем этот символ на `*'. Все полученные результаты заносятся в массив REZ.

Все остальные функции и процедуры программы связаны с действиями над массивами, то есть не имеют непосредственного отношения к данному методу нахождения МДНФ. Поэтому нет смысла их описывать [13].

Заключение

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

Иначе выглядит метод неопределенных коэффициентов. Для машинной реализации он подходит больше других, так как в нем мы имеем дело с массивами, для работы с которыми не надо особо сложной логики. И конечно ручное исполнение этого метода крайне нерационально, так как приходиться решать систему из 16-ти уравнений. Это для четырех переменных, а для пяти это будет 32 уравнения. Такой метод для ручного исполнения не подходит.

В задаче курсовой работы также входил синтез логической схемы. Полученная схема МДНФ была реализована в трех базисах: Буля, Пирса, Шеффера. Анализ и оценка аппаратурных затрат также приведена в данной записке.

Список использованных источников

1. Влах, Кишор, Сингхал “Машинные методы анализа и проектирования электронных схем.” Москва, изд. “Радио и связь”, 1988г.

2.“Измерения параметров цифровых интегральных микросхем.” (под ред. Эйдукаса Д.Ю., Орлова Б.В.) Москва, “Радио и связь”, 1982г.

3. Кузнецов О. П., Адельсон-Вельский Г. М. Дискретная математика для инженера. - М.: «Энергия», 1980. -- 344 с.

4. Лазер И.М., Шубарев В.А. “Устойчивость цифровых микроэлектронных устройств.” Москва, “Радио и связь”, 1983г.

5. Марченков С. С. Замкнутые классы булевых функций. -- М.: Физматлит, 2000.

6. Нефедов А.В., Савченко А.М., Феоктистов Ю.Ф.“Зарубежные интегральные микросхемы для электронной аппаратуры.” Москва, Энергоатомиздат, 1989г.

7.Ногов Ю.Р.“Математические модели элементов интегральной электроники.” Москва, “Современное радио”, 1976г.

8. Пухальский Г.И., Новосельцева Т.Я. “Цифровые устройства.” Санкт-Петербург, изд. “Политехника”1996г.

9. Самофалов К.Г, Романкевич А.М. Прикладная теория цифровых автоматов. - Киев “Вища школа”,1987

10. Схрейвер А. Теория линейного и целочисленного программирования. - М.: Мир, 1991 

11.Сысоев В.В.“Структурные и алгоритмические модели автоматизированного проектирования производства изделий электронной техники. ”Воронеж, Воронежский технологический институт, 1993г.

12. Токхейм Р.“Основы цифровой электроники” Москва, изд. “Мир”, 1988г.

13.Чахмахсазян Е.А., Мозговой Г.П., “Математическое моделирование и макромоделирование биполярных элементов электронных схем.”Москва, “Радио и связь”, 1985г.

14. Шило В.Л. “Популярные цифровые микросхемы.”Москва, Металлургия, 1988г.

15. Яблонский С. В. Введение в дискретную математику. -- М.: Наука, 1986.

Размещено на Allbest.ru