Минимизация ФАЛ - (реферат)
Минимизация ФАЛ - (реферат)
Дата добавления: март 2006г.
Минимизация ФАЛ
Совершенно нормальные формы хотя и дают однозначные представления функции, но являются очень громоздкими. Реализация СНФ программно или схемотехнически является избыточной, что ведет к увеличению программного кода, поэтому существуют методы упрощения логической записи– минимизации. Определение: Преобразование логических функций с целью упрощения их аналитического представления называются минимизацией.
Существуют два направления минимизации:
1. Кратчайшая форма записи (цель –минимизировать ранг каждого терма). При этом получаются кратчайшие формы КДНФ, ККНФ, КПНФ.
2. Получение минимальной формы записи (цель – получение минимального числа символов для записи всей функции сразу). При этом следует учесть, что ни один из способов минимизации не универсален! Существуют различные методы минимизации:
1. Метод непосредственных преобразований логических функций. (1. 1) При применении данного метода:
а) Записываются ДСНФ логических функций
б) Форма преобразуется и упрощается с использованием аксиом алгебры логики. При этом, в частности, выявляются в исходном ДСНФ так называемые соседние min-термы, в которых есть по одной не совпадающей переменной.
По отношению к соседним min-термам применяется закон склейки, значит ранг min-терма понижается на единицу.
Определение: Min-термы, образованные при склеивании называются импликантами. Полученные после склейки импликанты по возможности склеивают до тех пор, пока склеивание становится невозможным.
Определение: Несклеивающиеся импликанты называются прослойками. Определение: Формула, состоящая из простых импликант – тупиковая. Пример:
0
0
0
1
0
0
1
1
0
1
0
1
0
1
1
1
1
0
0
0
1
0
1
0
1
1
0
0
1
1
1
0
Если в процессе склейки образуется форма R, содержащая члены вида и то для нее справедливо выражение , что позволяет добавить к исходной форме R несколько членов вида пар и и после этого продолжить минимизацию. Пример:
Мы получили минимальную СНФ.
Метод неопределенных коэффициентов. (1. 2)
Суть метода состоит в преобразовании ДСНФ в МДНФ.
На основании теоремы Жигалкина любую ФАЛ можно представить в виде (рассмотрим на примере трех переменных):
Алгоритм определения коэффициентов:
1. Исходное уравнение разбить на систему уравнений, равных числу строк в таблице истинности.
2. Напротив каждого выражения поставить соответствующее значение функции. 3. Выбрать строку, в которой значение функции и приравнять все к нулю. 4. Просмотреть строки, где функция имеет единичное значение, и вычеркнуть все коэффициенты, встречающиеся в нулевых строках.
5. Проанализировать оставшиеся коэффициенты в единичных строках. 6. Используя правило, что дизъюнкция равна 1 если хотя бы один из , выбрать min-термы минимального ранга. Причем отдавать предпочтение коэффициентам, встречающимся в нескольких уравнениях одновременно. 7. Записать исходный вид функции.
Метод неопределенных коэффициентов применим для дизъюнктивной формы и непригоден для конъюнктивной.
Пример:
0
0
0
0
00
00
00
000
1
1
0
0
1
00
01
01
001
0
2
0
1
0
01
00
10
010
1
3
0
1
1
01
01
11
011
0
4
1
0
0
10
10
00
100
1
5
1
0
1
10
11
01
101
0
6
1
1
0
11
10
10
110
0
7
1
1
1
11
11
11
111
1
Итак, получим
Метод Квайна (1. 3)
Суть метода сводится к тому, чтобы преобразовать ДСНФ в МДНФ. Задачи минимизации по методу Квайна состоит в попарном сравнении импликант, входящих в ДСНФ с целью выявления возможности склеивания по какой-то пременной так:
Таким образом, можно понизить ранг термов. Процедура производится до тех пор, пока не остается ни одного терма, допускающего склейки с другим. Причем склеивающиеся термы помечаются *.
Определение: Непомеченные термы называются первичными импликантами. Полученное логическое выражение не всегда оказывается минимальным, поэтому исследуется возможность дальнейшего упрощения.
Для этого:
1. Составляются таблицы, в строках которых пишутся найденные первичные импликанты, а в столбцах указываются термы первичной ФАЛ.
2. Клетки этой таблицы отмечаются в том случае, если первичная импликанта входит в состав какого-нибудь первичного терма.
3. Задача упрощения сводится к нахождению такого минимального количества импликант, которые покрывают все столбцы.
Алгоритм метода Квайна (шаги):
1. Нахождение первичных импликант.
Исходные термы из ДНФ записывают в столбик и склеиваю сверху вниз. Непомеченные импликанты переходят в функции на этом шаге.
2. Расстановка меток избыточности.
Составляем таблицу, в которой строки – первичные импликанты, столбцы –исходные термы. Если некоторый min-терм содержит первичный импликант, то на пересечении строки и столбца ставим метку.
3. Нахождение существенных импликант.
Если в каком-либо столбце есть только одна метка, то первичный импликант соответствующей строки является существенным.
4. Строка, содержащая существенный импликант и соответствующие столбцы вычеркиваются.
Если в результате вычеркивания столбцов появятся строки первичных импликант, которые не содержат метки или содержат одинаковые метки в строках, то такие первичные импликанты вычеркиваются. В последнем случае оставляем одну меньшего ранга.
5. Выбор минимального покрытия.
Из таблицы, полученной на шаге 3 выбирают такую совокупность первичных импликант, которая включает метки во всех столбцах по крайней мере по одной метке в каждом. При нескольких возможных вариантах отдается предпочтение покрытию с минимальным суммарным числом элементов в импликантах, образующих покрытие.
6. Далее результат записывается в виде функции.
Пример:
Шаг 1.
Термы 4го ранга
Термы 3го ранга
Термы 2го ранга
* 1
* 3
* 4
* 1
* 2
* 2
* 3
* 4
* 1
* 2
* 2
* 1
Шаг 2.
V
V
V
V
V
V
V
V
V
V
V
V
V
V
Шаг 4 пропускаем.
Шаг 5.
