Минимизация ФАЛ
Другие рефераты
Минимизация ФАЛ
Совершенно нормальные формы хотя и дают однозначные представления функции,
но являются очень громоздкими. Реализация СНФ программно или
схемотехнически является избыточной, что ведет к увеличению программного
кода, поэтому существуют методы упрощения логической записи – минимизации.
Определение: Преобразование логических функций с целью упрощения их
аналитического представления называются минимизацией.
Существуют два направления минимизации:
1. Кратчайшая форма записи (цель – минимизировать ранг каждого терма). При
этом получаются кратчайшие формы КДНФ, ККНФ, КПНФ.
2. Получение минимальной формы записи (цель – получение минимального числа
символов для записи всей функции сразу).
При этом следует учесть, что ни один из способов минимизации не
универсален!
Существуют различные методы минимизации:
1. Метод непосредственных преобразований логических функций. (1.1)
При применении данного метода:
а) Записываются ДСНФ логических функций
б) Форма преобразуется и упрощается с использованием аксиом алгебры логики.
При этом, в частности, выявляются в исходном ДСНФ так называемые соседние
min-термы, в которых есть по одной не совпадающей переменной.
[pic]
По отношению к соседним min-термам применяется закон склейки, значит ранг
min-терма понижается на единицу.
Определение: Min-термы, образованные при склеивании называются
импликантами.
Полученные после склейки импликанты по возможности склеивают до тех пор,
пока склеивание становится невозможным.
Определение: Несклеивающиеся импликанты называются прослойками.
Определение: Формула, состоящая из простых импликант – тупиковая.
Пример:
|[pic] |[pic] |[pic] |[pic] |[pic] |
|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, содержащая члены вида [pic] и
[pic]то для нее справедливо выражение [pic], что позволяет добавить к
исходной форме R несколько членов вида пар [pic] и [pic]и после этого
продолжить минимизацию.
Пример:
[pic][pic]
[pic]
Мы получили минимальную СНФ.
Метод неопределенных коэффициентов. (1.2)
Суть метода состоит в преобразовании ДСНФ в МДНФ.
На основании теоремы Жигалкина любую ФАЛ можно представить в виде
(рассмотрим на примере трех переменных):
[pic]
Алгоритм определения коэффициентов:
1. Исходное уравнение разбить на систему уравнений, равных числу строк в
таблице истинности.
2. Напротив каждого выражения поставить соответствующее значение функции.
3. Выбрать строку, в которой значение функции [pic]и приравнять все [pic] к
нулю.
4. Просмотреть строки, где функция имеет единичное значение, и вычеркнуть
все коэффициенты, встречающиеся в нулевых строках.
5. Проанализировать оставшиеся коэффициенты в единичных строках.
6. Используя правило, что дизъюнкция равна 1 если хотя бы один из [pic],
выбрать min-термы минимального ранга. Причем отдавать предпочтение
коэффициентам, встречающимся в нескольких уравнениях одновременно.
7. Записать исходный вид функции.
Метод неопределенных коэффициентов применим для дизъюнктивной формы и
непригоден для конъюнктивной.
Пример:
[pic]
| |[pic] |[pic] |[pic] |[pic] |[pic] |[pic] |[pic] |[pic] |
|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 |
[pic]
Итак, получим [pic]
Метод Квайна (1.3)
Суть метода сводится к тому, чтобы преобразовать ДСНФ в МДНФ. Задачи
минимизации по методу Квайна состоит в попарном сравнении импликант,
входящих в ДСНФ с целью выявления возможности склеивания по какой-то
пременной так:
[pic]
Таким образом, можно понизить ранг термов. Процедура производится до тех
пор, пока не остается ни одного терма, допускающего склейки с другим.
Причем склеивающиеся термы помечаются *.
Определение: Непомеченные термы называются первичными импликантами.
Полученное логическое выражение не всегда оказывается минимальным, поэтому
исследуется возможность дальнейшего упрощения.
Для этого:
1. Составляются таблицы, в строках которых пишутся найденные первичные
импликанты, а в столбцах указываются термы первичной ФАЛ.
2. Клетки этой таблицы отмечаются в том случае, если первичная импликанта
входит в состав какого-нибудь первичного терма.
3. Задача упрощения сводится к нахождению такого минимального количества
импликант, которые покрывают все столбцы.
Алгоритм метода Квайна (шаги):
1. Нахождение первичных импликант.
Исходные термы из ДНФ записывают в столбик и склеиваю сверху вниз.
Непомеченные импликанты переходят в функции на этом шаге.
2. Расстановка меток избыточности.
Составляем таблицу, в которой строки – первичные импликанты, столбцы –
исходные термы. Если некоторый min-терм содержит первичный импликант, то на
пересечении строки и столбца ставим метку.
3. Нахождение существенных импликант.
Если в каком-либо столбце есть только одна метка, то первичный импликант
соответствующей строки является существенным.
4. Строка, содержащая существенный импликант и соответствующие столбцы
вычеркиваются.
Если в результате вычеркивания столбцов появятся строки первичных
импликант, которые не содержат метки или содержат одинаковые метки в
строках, то такие первичные импликанты вычеркиваются. В последнем случае
оставляем одну меньшего ранга.
5. Выбор минимального покрытия.
Из таблицы, полученной на шаге 3 выбирают такую совокупность первичных
импликант, которая включает метки во всех столбцах по крайней мере по одной
метке в каждом. При нескольких возможных вариантах отдается предпочтение
покрытию с минимальным суммарным числом элементов в импликантах, образующих
покрытие.
6. Далее результат записывается в виде функции.
Пример:
[pic]
Шаг 1.
|Термы 4го ранга |Термы 3го ранга |Термы 2го ранга |
|[pic] * 1 |[pic] |[pic] |
|[pic] * 3 |[pic] |[pic] |
|[pic] * 4 |[pic] * 1 | |
|[pic] * 1 |[pic] * 2 | |
|[pic] * 2 |[pic] | |
|[pic] * 2 |[pic] * 2 | |
|[pic] * 3 | | |
|[pic] * 4 |[pic] | |
| |[pic] | |
| |[pic] * 1 | |
Шаг 2.
| |[pic] |[pic] |[pic] |[pic] |[pic] |[pic] |[pic] |[pic] |
|[pic] |V | | |V | | | | |
|[pic] |V | | | | |V | | |
|[pic] | | |V |V | | | | |
|[pic] | | | | |V |V | | |
|[pic] | | | | |V | | |V |
|[pic] | |V |V | | | |V |V |
Шаг 4 пропускаем.
Шаг 5.
Выбираем те min-термы, при записи которых, МДНФ функции минимальна.
Шаг 6.
[pic]
Недостаток метода Квайна – необходимость полного по парного сравнения всех
min-термов на этапе нахождения первичных импликант.
Идея модификации метода Квайна – метод Квайна-Мак-Класки. (1.4)
1. Каждая конъюнкция в ДСНФ представляется своим двоичным набором.
2. Вся совокупность номеров наборов разбивается на группы в зависимости от
числа единиц, имеющихся в номерах наборов (0-группа, 1-группа, 2-группа
и.т.д.).
3. Сравниваются две группы, отличающиеся на одну единицу.
4. В результате сравнения в номере набора, имеющего большее число единиц на
позиции, где обнаружится разница на одну единицу ставится прочерк.
5. В процессе преобразования возникают новые сочетания (n-группы).
6. Процесс преобразования длится до тех пор, пока возможна операция
склеивания.
7. Элементы преобразованных групп являются первичными импликантами, которые
вместе с номерами исходных наборов образуют таблицы разметок.
8. В остальном эти методы совпадают с единственным уточнением – если в
результате таблицы разметок ни одна из строк не покрывает единицу столбца,
то надо выбрать номер столбца набора из предыдущей группы преобразований.
Определение: n-группа – это такой набор аргументов функции, что число всех
аргументов равных единице равно n, причем значении функции равно 1.
Пример:
[pic]
Сост
| |  скачать работу |
Другие рефераты
| 
