Читайте также:
|
В этом случае имеют в виду представления булевых функций, описывающих комбинационные автоматы нормальными формами (простейшими относительно некоторой меры сложности).
Обычно под сложностью нормальной формы понимают число букв в ней – минимальная простейшая форма.
Исходным заданием для минимизации комбинационных схем в базисе функциональных схем ("и", "или", "не") считают комбинационную таблицу СДНФ или производную ДНФ. В силу двойственности ДНФ и КНФ в дальнейшем достаточно применение только ДНФ.
Обобщенный алгоритм.
На первом этапе минимизации заданной логической функции осуществляется переход к ее сокращенной ДНФ, которая определена для каждой функции однозначно. Существует большое число методов реализации этого перехода. Наиболее универсальный – выполнение над ДНФ преобразований с использованием операций поглощения и обобщенного склеивания.
xy ∨ X = X _
XY ∨ XY = XY ∨ XZ ∨ YZ
При этом сокращенная ДНФ обладает таким свойством, что любая минимальная ДНФ получается из нее удалением некоторых элементарных коньюнкций.
Второй этап: получение из сокращенной ДНФ всех тупиковых ДНФ, среди которых содержатся все минимальные.
Третий этап: выбор минимальной ДНФ из всех тупиковых.
В синтезе комбинационных автоматов часто используют следующие понятия: коституента единицы, импликанта СДНФ, minterm.
Сокращенная нормальная форма (СНФ) булевой функции – это ДНФ, представляющая собой дизъюнкцию всех простых импликант данной функции.
Импликант булевой функции – это элементарная конъюнкция ДНФ, такая что ее значение для логической функции равно единице.
x ∨ yz ∨ x y z
Простая импликанта – это импликанта, вычеркивание простой буквы из которой делает ее неимпликантой.
y ∨ xy
Тупиковая СДНФ – СДНФ, в которой нет ни одной лишней импликанты, т.е. такой импликанты, наличие которой не сказывается на значении булевой функции.
Минимальная ДНФ – ДНФ, состоящая из минимально возможного числа букв алфавита.
Пример минимизации комбинационного автомата.
Синтез одновыходных комбинационных автоматов по методу Квайна-Мак-Класки:
· запись логической функции в СДНФ,
· преобразование СДНФ в СНФ на основании операции склеивания,
· получение тупиковых СНФ и выбор из них минимальной ДНФ (МДНФ),
· получение минимальной формы функции в заданном элементарном базисе с учетом ограничений выбранной системы элементов.
Замечание. Процедура поиска МДНФ является переборной. Для сокращения перебора все конституенты располагаются в порядке увеличения числа единиц входных переменных. Конституенты с одинаковым числом единиц считаются относящимися к одному классу. При поиске склеиваемых конституент рассматриваются на все возможные пересечения конституент, а только сочетания из разных соседних классов. Результат склеивания конституент образует список импликант, над которым выполняются такие же операции упорядочивания, поиска, склеивания, как над исходным списком конституент. Процедура продолжается пока не останется склеиваимых импликант. Исходная СНФ представляет собой совокупность таких импликант из всех образующихся списков, которые не участвовали в операциях склеивания.
Пример. Пусть задана функция F(x1,x2,x3,x4)=V F(2,6,12,13,14,15)
Сгруппируем наборы (кортежи) входных переменных автомата согласно таблице
| № конституенты 1 | x1 | x2 | x3 | x4 | Примечание (№ логической пары) |
Эти конституенты сгруппированы как 1, 2-3, 4-5, 6. Результаты склеивания конституент сведены в таблице.
| №№ склеиваемых конституент | x1 | x2 | x3 | x4 | ||
 1,2
| - | |||||
| 1,3 | - | |||||
| - | |||||
| 3,4 | - | |||||
| 3,5 | - | |||||
| 5,6 | - |
|
Склеивая импликанты (1,2) и (3,4),(1,3) и (2,4) имеем сокращенную ДНФ
F(x1,x2,x3,x4) = x1x2 ∨ x2x3x4 ∨ x1x3x4
Тупиковые ДНФ получим из таблицы покрытий, в которой для каждой коституенты из сокращенной ДНФ отводится одна строка, а для каждой простой импликанты из сокращенной ДНФ – один столбец. Значения в позициях таблицы записывают единицу, если j-я импликанта покрывает (поглощает) i-ю конституенту. Иначе – записывают нуль.
| Констит.1
| x1x2 | x2x3x4 | x1x3x4 |
x1 x2 x3 x4 ∨ x1 x2 = x1 x2 (x3 x4 ∨ 1) = x1 x2 - склеиваются
x1 x2 x3 x4 ∨ x2 x3 x4 = x2 x4 (x1 x3 ∨ x3) - не склеиваются
x1 x2 x3 x4 ∨ x1 x3 x4 = x4 (x1 x2 x3 ∨ x1 x3) - не склеиваются
Тупиковые ДНФ образуют импликанты тех столбцов, которые в совокупности имеют единицы во всех строках таблицы покрытия, причем исключение любой импликанты не нарушает это условие.
Замечание.
1. Функции с большим числом аргументов соответствует большое число тупиковых ДНФ, такое что полный их перебор с целью выделения минимальной ДНФ становится не реальным.
2. Для функции многих переменных часто используют приближенные алгоритмы получения минимальной ДНФ.
3. К приближенным алгоритмам относят, так называемый минимальный алгоритм, в соответствии с которым включение импликант в минимальную ДНФ выполняют в следующей последовательности:
· выбирается строка таблицы покрытий с наименьшим (минимальным) числом единиц. Среди столбцов, имеющих в этой строке единицу, выбирают столбец с наибольшим (максимальным) числом единиц.
· импликанты этого столбца включаются в МДНФ, а все конституенты, покрываемые этой импликантой, и соответствующие им строки таблицы исключаются.
· процедура повторяется до тех пор, пока остаются навычекнутые строки.
Таким образом получаем x1 x2 ∨ x1 x3 x4
Дата добавления: 2015-07-10; просмотров: 449 | Нарушение авторских прав