Минимизация ФАЛ

Рефераты, курсовые, дипломные, контрольные (предпросмотр)

Тип: Курсовая работа. Файл: Word (.doc) в архиве zip. Категория: Математика
Адрес этого реферата http://referat-kursovaya.repetitor.info/?essayId=20175 или
Загрузить
В режиме предпросмотра не отображаются таблицы, графики и иллюстрации. Для получения полной версии нажмите кнопку «Загрузить». Рефераты, контрольные, дипломные, курсовые работы предоставляются в ознакомительных целях, не для плагиата.
Страница 1 из 3 [Всего 3 записей]1 2 3 »

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

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

Существуют два направления минимизации:

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

2. Получение минимальной формы записи (цель - получение минимального числа символов для записи всей функции сразу).

При этом следует учесть, что ни один из способов минимизации не универсален!

Существуют различные методы минимизации:

1. Метод непосредственных преобразований логических функций. (1.1)

При применении данного метода:

а) Записываются ДСНФ логических функций

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

По отношению к соседним min-термам применяется закон склейки, значит ранг min-терма понижается на единицу.

Определение: Min-термы, образованные при склеивании называются импликантами.

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

Определение: Несклеивающиеся импликанты называются прослойками.

Определение: Формула, состоящая из простых импликант - тупиковая.

Пример:

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

Пример:

Мы получили минимальную СНФ.

Метод неопределенных коэффициентов. (1.2)

Суть метода состоит в преобразовании ДСНФ в МДНФ.

На основании теоремы Жигалкина любую ФАЛ можно представить в виде (рассмотрим на примере трех переменных):

Алгоритм определения коэффициентов:

1. Исходное уравнение разбить на систему уравнений, равных числу строк в таблице истинности.

2. Напротив каждого выражения поставить соответствующее значение функции.

3. Выбрать строку, в которой значение функции и приравнять все к нулю.

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

5. Проанализировать оставшиеся коэффициенты в единичных строках.

6. Используя правило, что дизъюнкция равна 1 если хотя бы один из , выбрать min-термы минимального ранга. Причем отдавать предпочтение коэффициентам, встречающимся в нескольких уравнениях одновременно.

7. Записать исходный вид функции.

Метод неопределенных коэффициентов применим для дизъюнктивной формы и непригоден для конъюнктивной.

Пример:

Итак, получим

Метод Квайна (1.3)

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

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

Определение: Непомеченные термы называются первичными импликантами.

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

Для этого:

1. Составляются таблицы, в строках которых пишутся найденные первичные импликанты, а в столбцах указываются термы первичной ФАЛ.

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

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

Алгоритм метода Квайна (шаги):

1. Нахождение первичных импликант.

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

2. Расстановка меток избыточности.

Составляем таблицу, в которой строки - первичные импликанты, столбцы - исходные термы. Если некоторый min-терм содержит первичный импликант, то на пересечении строки и столбца ставим метку.

3. Нахождение существенных импликант.

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

4. Строка, содержащая существенный импликант и соответствующие столбцы вычеркиваются.

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

5. Выбор минимального покрытия.

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

6. Далее результат записывается в виде функции.

Пример:

Недостаток метода Квайна - необходимость полного по парного сравнения всех min-термов на этапе нахождения первичных импликант.

Идея модификации метода Квайна - метод Квайна-Мак-Класки. (1.4)

1. Каждая конъюнкция в ДСНФ представляется своим двоичным набором.

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

3. Сравниваются две группы, отличающиеся на одну единицу.

4. В результате сравнения в номере набора, имеющего большее число единиц на позиции, где обнаружится разница на одну единицу ставится прочерк.

5. В процессе преобразования возникают новые сочетания (n-группы).

6. Процесс преобразования длится до тех пор, пока возможна операция склеивания.

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

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

Определение: n-группа - это такой набор аргументов функции, что число всех аргументов равных единице равно n, причем значении функции равно 1.

Пример:

Составим таблицу истинности:

Запишем n-группы:

0-Группа: 0000

1-Группа: 0001, 0010, 0100, 1000

2-Группа: 0011, 0101, 0110, 1001

3-Группа: 0111,1011

4-Группа: 1111

Теперь сравним группы с номерами n и n+1:

0-Группа: 000-, 00-0, 0-00, -000

1-Группа: 00-1, 0-01, -001, 001-, 0-10, 010-,01-0, 100-

2-Группа: 0-11, -011, 01-1, 011-, 10-1

3-Группа: -111, 1-11

Еще раз сравним (при этом прочерки должны быть на одинаковых позициях):

0-Группа: 00--, 0-0-, -00-

1-Группа: 0--1, -0-1, 0-1-, 01-

2-Группа: --11

И еще раз сравним:

0-Группа: 0---

Запишем таблицу исходных min-термов, где функция равна 1:

Выделим минимальное число групп, покрывающих

Для проверки составим таблицу истинности

Метод минимизирующих карт (для ДСНФ и КСНФ). (1.5)

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

RSSСтраница 1 из 3 [Всего 3 записей]1 2 3 »


При любом использовании материалов сайта обязательна гиперссылка на сайт «Репетитор».
Разработка и Дизайн компании Awelan
www.megastock.ru
Проверить аттестат