Читайте также:
|
Для конечного автомата U=<|A|=3,|B|=2,d,l>,автоматная таблица
| a\q | q1 | q2 | q3 | q4 | q5 | q6 | q7 | q8 | q9 |
| a1 | q2,b1 | q1,b2 | q1b2 | q8,b1 | q6,b2 | q8,b1 | q6,b2 | q4,b4 | q7,b1 |
| a2 | q4,b2 | q1,b1 | q6,b1 | q1,b2 | q4,b2 | q9,b2 | q1,b2 | q4,b1 | q9,b2 |
| a3 | q4,b4 | q5,b1 | q5,b1 | q1,b1 | q3,b1 | q6,b2 | q3,b1 | q7,b1 | q7,b2 |
Найти приведенный (минимальный) автомат Un.
Решение.
1. Классов разбиений 1-эквивалентных состояний(т.е. l1(qil,a)=l2(qjn,a)) три:С1,1={q1,q4,q6,q9}, С1,2={q2,q3,q8}, С1,3={q5,q7}.
2. Классов разбиений 2-х эквивалентных состояний (т.е. когда d(q||,a),d(q|,a)Î С1,j=1,3) четыре:
| C1,1 | C1,2 | C1,3 | |||||||
| a\q | q1 | q4 | q6 | q9 | q2 | q3 | q8 | q5 | q7 |
| a1 | c1,2 | c1,2 | c1,2 | c1,3 | c1,1 | c1,1 | c1,1 | c1,1 | c1,1 |
| a2 | c1,1 | c1,1 | c1,1 | c1,1 | c1,1 | c1,1 | c1,1 | c1,1 | c1,1 |
| a3 | c1,1 | c1,1 | c1,1 | c1,3 | c1,3 | c1,3 | c1,3 | c1,2 | c1,2 |
Т.е. имеем С2.1={q1,q4,q6},C2,2={q9}, C2,3={q2,q3,q8},C2,4={q5,q7}
3. Классов разбиений 3-х эквивалентных состояний пять:
Т.е. С3,1={q1,q4},C3,2={q6},C3,3={q9},C3,4={q2,q3,q8},C3,5={q5,q7}
| C2,1 | C2,2 | C2,3 | C2,4 | ||||||
| a\q | q1 | q4 | q6 | q9 | q2 | q3 | q8 | q5 | q7 |
| a1 | c2,3 | c2,3 | c2,3 | c2,4 | c2,1 | c2,1 | c2,1 | c2,1 | c2,1 |
| a2 | c2,1 | c2,1 | c2,2 | c2,2 | c2,1 | c2,1 | c2,1 | c2,1 | c2,1 |
| a3 | c2,1 | c2,1 | c2,2 | c2,4 | c2,4 | c2,4 | c2,4 | c2,3 | c2,3 |
4. Классов разбиений 4-х эквивалентных состояний шесть.
Т.ею имеем C4,1={q1,q4},C4,2={q6},C4,3={q9},C4,4={q2,q8},C4,5={q3},C4,6={q5,q7}
| C3,1 | C3,2 | C3,3 | C3,4 | C3,5 | |||||
| a\q | q1 | q4 | q6 | q9 | q2 | q3 | q8 | q5 | q7 |
| a1 | c3,4 | c3,4 | c3,4 | c3,5 | c3,1 | c3,1 | c3,1 | с3,2 | с3,2 |
| a2 | c3,1 | c3,1 | c3,3 | c3,3 | c3,1 | c3,1 | c3,1 | c3,1 | c3,1 |
| a3 | c3,1 | c3,1 | c3,2 | c3,5 | c3,5 | c3,5 | c3,5 | c3,4 | c3,4 |
5. Классов разбиений 5-х эквивалентных состояний шесть.
| C4,1 | C4,2 | C4,3 | C4,4 | C4,5 | C4,6 | ||||
| a\q | q1 | q4 | q6 | q9 | q2 | q3 | q8 | q5 | q7 |
| a1 | c4,4 | c4,4 | c4,4 | c4,6 | c4,1 | c4,1 | c4,1 | c4,2 | c4,2 |
| a2 | c4,1 | c4,1 | c4,3 | c4,3 | c4,1 | c4,1 | c4,1 | c4,1 | c4,1 |
| a3 | c4,1 | c4,1 | c4,2 | c4,6 | c4,6 | c4,6 | c4,6 | c4,5 | c4,5 |
6. Поскольку число разбиений шага 5 совпадает с числом разбиений в шаге 4,то приведенный автомат (минимальный по числу состояний) автомат Un имеет шесть состояний, т.е. U=<|A|=3,|B|=2,d,l> с автоматной таблицей!
| a\q | q1 | q2 | q3 | q5 | q6 | q9 |
| a1 | q2,b1 | q1,b2 | q1b2 | q6,b2 | q2,b1 | q5,b1 |
| a2 | q1,b2 | q1,b1 | q6,b1 | q1,b2 | q9,b2 | q9,b2 |
| a3 | q1,b2 | q5,b1 | q5,b1 | q3,b1 | q6,b2 | q5,b2 |
Пояснение Автоматная таблица приведенного автомата Un получена из исходной таблицы вычеркиванием её столбцов q4,q7,q8 и заменой в клетках других столбцов состояния q4 на эквивалентное состояние q1,q7 на q5,q8,на q2.
· Методы минимизации комбинационных схем в базисе булевых функций.
Комбинационная схема -правильная схема, построенная из элементов,являющихся автоматами без памяти. В правильной схеме нет обратных связей,а соединение элементов выполнено по правилам, соответствующим(функциональном отношении) операции суперпозиции функции. В соответствии с этим оператор, реализуемый комбинационной схемой, также является некоторой функции алгебры логики.
Задача минимизации комбинационных схем решается с привлечением методов минимизации вспомогательных функций в алгебре логики(булевой алгебре).
В этом случае имеют в виду представление булевых формул, описывающих комбинационный автомат, нормальными формами, простейшими относительно некоторой меры сложности. Обычно под сложностью нормальной формы понимается число букв в нем. Именно простейшую форму будем называть минимальной.
Итак, исходным заданием комбинационной схемы для её минимизации в базисе функциональных схем «и», «или», «не» будем считать комбинационную таблицу, С.Д.Н.Ф. или произвольную Д.Н.Ф.
Рассматриваемые ниже методы минимизации комбинационной схемы состоят из трех этапов:
На первом этапе осуществляется переход от исходного задания переключательной (логической) функции,к её сокращенной Д.Н.Ф.(такая сокращенная форма определяется для каждой функции однозначно). Сокращенная Д.Н.Ф. тем же свойством что любая минимальная Д.Н.Ф.(т.е. М.Д.Н.Ф) получается из нее удалением некоторых элементарных конъюнкций.
На втором этапе из сокращенной Д.Н.Ф. получают тупиковые Д.Н.Ф., среди которых содержатся все М.Д.Н.Ф.
На третьем этапе осуществляется выбор М.Д.Н.Ф. из всех тупиковых Д.Н.Ф.
Напоминание В синтезе и анализе комбинационных схем часто используют следующие термины:
=Конституента единицы (импликанта С.Д.Н.Ф.) – элементарная конъюнкция С.Д.Н.Ф. (т.е. конъюнкция всех входных переменных в прямом или инверсном виде);
=Сокращенная нормативная форма (С.Н.Ф.)булевой функции Д.Н.Ф.,представляющая собой дизъюнкцию всех простых импликант функции;
=Импликанта булевой функции –элементарная конъюнкция Д.Н.Ф.,такая,что <xi,…,xj>Þfº1;
=Тупиковая С.Д.Н.Ф. – С.Д.Н.Ф.,в которой нет ни одной лишней имплканты, т.е. такой импликанты,наличие которой не сказывается на значениях булевой ф-ии;
=Минимизация Д.Н.Ф. (М.Д.Н.Ф.)- Д.Н.Ф. состоящая из минимального возможного числа букв(символов).
Лекция №14.
ПРИМИНЕНИЕ МЕТОДОВ МИНИМИЗАЦИИ КОМБИНАЦИОННЫХ АВТОМАТОВ.
Продолжительность: 2 часа (90) минут
Ключевые (основные) вопросы (моменты)
метод Кванта-Мак-Класки.
Текст лекции
ПРИМИНЕНИЕ МЕТОДОВ МИНИМИЗАЦИИ КОМБИНАЦИОННЫХ АВТОМАТОВ.
Синтез минимальных одновыходных комбинационных автоматов по методу Кванта-Мак-Класки. (до 45 минут)
В этом случае выполняются следующие процедуры:
1. Записывают логическую функцию как С.Д.Н.Ф.;
2. Преобразовывают С. Д.Н.Ф. в С. Н.Ф. (сокращенную Д.Н.Ф.) на основе операций обобщенного склеивания и поглощения, а именно
xyUx --zUyzºxyUx—z, xUxy+x;
3. Получают nтупиковые С.Н.Ф. и выбирают среди них М.Д.Н.Ф.;
4. Записывают минимальную форму логической функции в заданном элементом базисом с учетом ограничений.
Следует отметить,что процедура поиска М. Д.Н.Ф. является переборной. Поэтому для сокращения перебираемых вариантов все конституэнты располагаются в порядке увеличения числа единиц в картежах входных переменных,а конституэнты с одинаковым числом единиц считаются относящимися к одному классу. При поиске склеиваемых конституэнт рассматривают не все возможные сочетания конституэнт из разных соседних классов. Результат склеивания конституэнт образуют список импликант, над которыми выполняют такие же операции упорядочивания и поиска склеиваемых импликант,как и над исходным списком конституэнт констант. Искомая С.Н.Ф. представляет собой совокупность n таких из исходного и всех образующегося списков, которые не участвовали в операциях склеивания.
Поясним сказанное на примере.
Пример.
Пусть задана функция f(x1,x2,x3,x4)U1F(2,6,12,13,14,15).Найдем С.Д.Н.Ф. для него:
1. Сгруппируем картежи (наборы) переменных x1,x2,x3,x4 в таблицу (здесь конституэнты сгруппированы как классы 1,2,3,4)
| Номер картежа | Номер картежа | x1 | x2 | x3 | x4 | Классы |
2. Результат склеивания списка конституэнт единицы сведем в таблицу
| Номера склеиваемой константы | x1 | x2 | x3 | x4 |
| 1,2 | -- | |||
| 2,5 | -- | |||
| 3,4 | -- | |||
| 3,5 | -- | |||
| 4,6 | -- | |||
| 5,6 | -- |
3. Склеивая импликанты (3,4) и (4,5),(3,5),(4,6), получаем сокращенную Д.Н.Ф. для исходной функции четырех аргументов f(x1,x2,x3,x4)=х1—х3х4—Ux2x3x4—Ux1x2.
Тупиковые Д.Н.Ф. получают с помощью таблицы простыми импликантами С.Н.Ф.,а строки – конституэнтами заданной функции. В этом случае,если простая импликанта покрывает(поглощает) конституэнту,то в соответствующей ячейке таблицы покрытий ставят 1(иначе 0). Для рассматриваемой функции f(x1,x2,x3,x4) имеем таблицу покрытий:
| Простые импликанты С.Н.Ф. | x1x2 | x2x3x4- | x1-x3x4- |
| Конституэнты единицы | |||
Тупиковую Д.Н.Ф импликанты тех столбцов,которые в совокупности имеют единицы во всех строках таблицы,причем исключение любой импликанты нарушает это условие.
Из полученной таблицы покрытий находим единственную тупиковую Д.Н.Ф x1x2Ux1—x3x4--. Эта тупиковая Д.Н.Ф есть М.Д.Н.Ф.
Замечание
1. Функциями с большим числом аргументов соответствуют большое число тупиковых Д.Н.Ф, такие,что их полный перебор с целью выделения М.Д.Н.Ф становится нереальным.
2. Для функций многих переменных целесообразно использование приближенных методов получения М. Д.Н.Ф.
Приближённые методы синтеза минимальных одновидных комбинационных автоматов. (до 45 минут)
К приближенным методам относится широко используемый на практике минимальный алгоритм, в соответствии с которым включение импликант в М.Д.Н.Ф выполняют в следующей последовательности:
1. Выбирается строка таблицы покрытой наименьшим числом единиц;
2. Среди столбцов, имеющих в этой строке единицы, выбирается столбец с наибольшим числом единиц;
3. Импликанта этого столбца включается в М. Д.Н.Ф,а все конституэнты,покрываемые указанной импликантой (и соответствующие им строки таблицы) вычеркивается;
4. Процедуру повторяют до тех пока остаются не вычеркнутые строки.
Применив рассмотренный минимальный алгоритм к полученной выше таблице покрытий, имеем:
1. Выбираем первую строку (очевидно логично выбирать 3,или 4,или 6);
2. Берем(выбора нет) третий столбец;
3. Включаем импликанту x1—x3x4-- в М.Д.Н.Ф,а первую и вторую строки вычеркиваем;
4. Выбираем третью строку(левую,можно брать 4 или 6);
5. Берем первый столбец;
6. Включаем импликанту x1x2 в М.Д.Н.Ф и вычеркиваем все оставшиеся не вычеркнутыми строки(т.е. 3-ю,4-ю,5-ю,6-ю);
Окончательный результат получается в виде f(x1,x2,x3,x4)= x1x2Ux1—x3x4----- М.Д.Н.Ф.
Лекция №15.
ПРИМИНЕНИЕ МЕТОДОВ МИНИМИЗАЦИИ КОМБИНАЦИОННЫХ АВТОМАТОВ (ПРОДОЛЖЕНИЕ)
Продолжительность: 2 часа (90) минут
Ключевые (основные) вопросы (моменты)
Текст лекции
Дата добавления: 2015-12-01; просмотров: 22 | Нарушение авторских прав