Комбинационные схемы
Для невычеркнутых строк и столбцов составляем формальное выражение Петрика, раскрываем в нем скобки:
(AмB)(CмD)ъACмADмBCмBD
Каждая полученная в результате конъюнкция соответствует ТДНФ, все они являются МДНФ. Записываем получившиеся МДНФ, не забывая добавлять выписанные ранее существенные импликанты. Для этого записываем соответствующие кубам импликанты, например, для конъюнкции AC:
г(й,ц,у,к)ъфыамцвмвамук
импликанта A 
импликанта С существенные импликанты
Остальные МДНФ:
Вариант AD: г(й,ц,у,к)ъфыамцкмвамук Вариант ВС: г(й,ц,у,к)ъфыумцвмвамук Вариант ВD: г(й,ц,у,к)ъфыумцкмвамук
Очевидно, что модернизация Мак-Класки позволила существенно упростить первый этап минимизации.
3.1.3. Модернизация Нельсона метода Квайна
Еще одна модернизация метода Квайна также направлена на упрощение первого этапа – нахождение всех простых импликант.
Идея данного метода состоит в том, что минимизируемая функция первоначально записывается не в ДСНФ, а в КСНФ. Естественно, что данный метод будет эффективнее рассмотренных выше лишь тогда, когда у минимизируемой функций наборов, на которых она равна 0 значительно меньше, чем наборов, на которых функция равна 1.
Алгоритм метода Квайна с модернизацией Нельсона:
1. Нахождение всех простых импликант функции.
1.1.Записываем СКНФ функции алгебры логики. Для этого необходимо выписать макстермы тех наборов, на которых функция принимает значение 0, и объединить их знаками конъюнкции.
1.2.Проводим возможные склеивания элементарных дизъюнкций.
1.3.Раскрываются скобки с учетом поглощения. В результате по-
лучаем СокрДНФ.
2. Нахождение МДНФ.
2.1.Составляем таблицу Квайна, в столбцах которой – минтермы функции (т.е. конъюнкции высшего ранга, соответствующие наборам, на которых функция равна 1), а в строках – все найденные простые импликанты.
2.2.Далее – по алгоритму Квайна.
35
Цифровая схемотехника
Пример:
В качестве примера применения модернизации Нельсона проделаем минимизацию функции алгебры логики, которая равна 0 всего на четырех наборах.
г(й,ц,у,к)ър(0,1,2,3,5,7,8,10,12,13,14,15)
или
г(й,ц,у,к)ъР(4,6,9,11)
Заносим функцию в таблицу истинности (табл. 3.7):
Табл. 3.7
N |
x1 |
x2 |
x3 |
x4 |
f |
0 |
0 |
0 |
0 |
0 |
1 |
|
|
|
|
|
|
1 |
0 |
0 |
0 |
1 |
1 |
|
|
|
|
|
|
2 |
0 |
0 |
1 |
0 |
1 |
|
|
|
|
|
|
3 |
0 |
0 |
1 |
1 |
1 |
|
|
|
|
|
|
4 |
0 |
1 |
0 |
0 |
0 |
|
|
|
|
|
|
5 |
0 |
1 |
0 |
1 |
1 |
|
|
|
|
|
|
6 |
0 |
1 |
1 |
0 |
0 |
|
|
|
|
|
|
7 |
0 |
1 |
1 |
1 |
1 |
|
|
|
|
|
|
8 |
1 |
0 |
0 |
0 |
1 |
|
|
|
|
|
|
9 |
1 |
0 |
0 |
1 |
0 |
|
|
|
|
|
|
10 |
1 |
0 |
1 |
0 |
1 |
|
|
|
|
|
|
11 |
1 |
0 |
1 |
1 |
0 |
|
|
|
|
|
|
12 |
1 |
1 |
0 |
0 |
1 |
|
|
|
|
|
|
13 |
1 |
1 |
0 |
1 |
1 |
|
|
|
|
|
|
14 |
1 |
1 |
1 |
0 |
1 |
|
|
|
|
|
|
15 |
1 |
1 |
1 |
1 |
1 |
|
|
|
|
|
|
Построим СКНФ функции:
г(й,ц,у,к)ъ(ймымумк)(ймымвмк)с с(фмцмума)(фмцмвма)ъ
Склеиваем:
ъ(ймымк)(фмцма)ъ
Раскрываем скобки:
ъйцмйамфымыамфкмцк
Получили СокрДНФ. Составляем таблицу Квайна (табл. 3.8). Ни в одном столбце нет по одной метке, следовательно, у функции нет простых импликант. Но зато есть несколько пар одинаковых столбцов. По одному столбцу из каждой совпадающей пары вычеркиваем.
36
Комбинационные схемы
|
|
|
|
|
|
|
|
|
|
|
|
Табл. 3.8 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
фыва |
фывк |
фыуа |
фыук |
фцвк |
фцук |
йыва |
йыуа |
йцва |
йцвк |
йцуа |
йцук |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
йц |
|
|
|
|
|
|
|
|
я |
я |
я |
я |
A |
йа |
|
|
|
|
|
|
я |
я |
я |
|
я |
|
B |
фы |
я |
я |
я |
я |
|
|
|
|
|
|
|
|
C |
ыа |
я |
|
я |
|
|
|
я |
я |
|
|
|
|
D |
фк |
|
я |
|
я |
я |
я |
|
|
|
|
|
|
E |
цк |
|
|
|
|
я |
я |
|
|
|
я |
|
я |
F |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Составляем формальное выражение Петрика:
(CмD)(CмE)(EмF)(BмD)(AмB)(AмF)ъ
Раскрываем попарно скобки с учетом поглощения:
ъ(CмDE)(BмAD)(FмAE)ъ ъ(BCмACDмBDEмADE)(FмAE)ъ ъBCFмABCEмACDFмACDEмBDEFм мABDEмADEFмADE
Каждая полученная в результате конъюнкция соответствует ТДНФ, две из них (BCF и ADE) являются МДНФ. Записываем получившиеся МДНФ:
BCF: г(й,ц,у,к)ъйамфымцк
ADE: г(й,ц,у,к)ъйцмыамфк
3.1.4. Минимизация частично заданных функций методом Квайна
Минимизация частично заданных функций имеет свои особенности. Если функция f имеет q запрещенных наборов, то ее можно доопределить 2q способами. У каждой такой полностью доопределенной относительно f функции есть МДНФ. Самая короткая по числу операций МДНФ из всех доопределенных функций и есть МДНФ частично заданной функции f.
Но чтобы воспользоваться методом Квайна, необходимо записать функцию аналитически, т.е. ее нужно предварительно доопределить. Оптимальное доопределение неизвестно, поэтому из всех 2q полностью доопределенных относительно f функций выделим две: функцию, которая на всех запрещенных наборах равна 0 (б0), и функцию, кото-
37
Цифровая схемотехника
рая на всех запрещенных наборах равна 1 (б1). С их помощью будем находить МДНФ частично заданной функции f.
Алгоритм метода:
1. Нахождение всех простых импликант функции.
1.1.Доопределяем функции б0 и б1.
1.2.Находим простые импликанты функции б1.
1.2.Находим минтермы функции б0.
2. Нахождение МДНФ.
2.1.Составляем таблицу Квайна, в столбцах которой – минтермы
функции б0, а в строках – все найденные простые импликанты функ-
ции б1.
2.2. Далее – по алгоритму Квайна.
Пример:
Дана частично заданная функция четырех аргументов:
г(й,ц,у,к)ър(0,1,2,5,6)ь(10,11,12,13,14,15)
У функции 6 запрещенных наборов. Заносим функцию в таблицу истинности и доопределяем функции б0 и б1. Эти функции на всех разрешенных наборах совпадают с заданной функцией и отличаются только на запрещенных наборах (табл. 3.9):
Табл. 3.9
N |
x1 |
x2 |
x3 |
x4 |
f |
б0 |
б1 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
|
|
|
|
|
|
|
|
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
|
|
|
|
|
|
|
|
2 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
|
|
|
|
|
|
|
|
3 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
|
|
|
|
|
|
|
|
4 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
|
|
|
|
|
|
|
|
5 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
|
|
|
|
|
|
|
|
6 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
|
|
|
|
|
|
|
|
7 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
|
|
|
|
|
|
|
|
8 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
|
|
|
|
|
|
9 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
|
|
|
|
|
|
|
|
10 |
1 |
0 |
1 |
0 |
* |
0 |
1 |
|
|
|
|
|
|
|
|
11 |
1 |
0 |
1 |
1 |
* |
0 |
1 |
|
|
|
|
|
|
|
|
12 |
1 |
1 |
0 |
0 |
* |
0 |
1 |
|
|
|
|
|
|
|
|
13 |
1 |
1 |
0 |
1 |
* |
0 |
1 |
|
|
|
|
|
|
|
|
14 |
1 |
1 |
1 |
0 |
* |
0 |
1 |
|
|
|
|
|
|
|
|
15 |
1 |
1 |
1 |
1 |
* |
0 |
1 |
|
|
|
|
|
|
|
|
38
Комбинационные схемы
Ищем простые импликанты функции б1. Функция равна 0 только на 5 наборах, поэтому проще всего использовать метод Нельсона. строим СКНФ функции б1:
г(й,ц,у,к)ъ(ймцмвма)(ймымумк)с с(ймымвма)(фмцмумк)(фмцмума)ъ
Склеиваем первую и третью скобки, а также четвертую и пятую::
ъ(ймвма)(фмцму)(ймымумк)ъ
Раскрываем скобки и проводим возможные поглощения:
ъ(йцмйумфвмцвмфамцамуа)с с(ймымумк)ъ ъйцмйцумйцкмйумйыумйукмфывм мфвкмйцвмцвкмфыамфуамйцам мцуамйуамыуамуаъ ъйцмйумфывмфвкмцвкмфыамуа
Получили СокрДНФ функции б1. Составляем таблицу Квайна, в строки которой записываем найденные простые импликанты функции б1, а в столбцы – минтермы функции б0.
Расставляем метки. В каждом столбце должна быть по крайней мере одна метка, но в строках меток может и не быть, т.к. в строках и столбцах стоят конъюнкции разных функций – б0 и б1.
У функции одна существенная импликанта, выписываем ее, вычеркиваем соответствующие столбцы и строку. В первых двух строках нет меток – они лишние, вычеркиваем их. Остальные строки обозначаем буквами и составляем формальное выражение Петрика (табл. 3.10).
б0
б1
йц
йу
фыв
фвк
цвк
фыа
сущ. 
уа
фыва
я
я
Табл. 3.10
фывк |
фыуа |
фцвк |
фцуа |
я |
|
A |
я |
я |
B |
|
я |
C |
|
я |
D |
|
я |
я |
39