Главная    Почта    Новости    Каталог    Одноклассники    Погода    Работа    Игры     Рефераты     Карты
  
по Казнету new!
по каталогу
в рефератах

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



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

Минимизация ФАЛ
Совершенно нормальные формы хотя и дают однозначные  представления  функции,
но   являются   очень   громоздкими.   Реализация   СНФ    программно    или
схемотехнически является избыточной, что  ведет  к  увеличению  программного
кода, поэтому существуют методы упрощения логической записи – минимизации.
Определение:  Преобразование  логических  функций  с  целью   упрощения   их
аналитического представления называются минимизацией.
Существуют два направления минимизации:
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]
Сост
1234
скачать работу


 Другие рефераты
ҚАЗАҚСТАН РЕСЕЙ ИМПЕРИЯСЫНЫҢ ҚҰРАМЫНДА
Қазақстанның ғылымы және ғылыми мекемелері
Бір өзінің айбаты мың кісідей болады…
ЛЕПТІ СӨЙЛЕМДЕР


 

Отправка СМС бесплатно

На правах рекламы


ZERO.kz
 
Модератор сайта RESURS.KZ