Глава вторая МИНИМИЗАЦИЯ ЛОГИЧЕСКИХ ФУНКЦИЙ МЕТОДОМ ОБОБЩЁННЫХ КОДОВ.
В СДНФ функции от n переменных каждый набор &xi можно заменить последовательностью нулей и единиц. Такая последовательность носит название обобщённого кода.
Метод обобщённых кодов был разработан в конце 60-х годов на 21-й кафедре Академии им. Дзержинского д. т. н. Мавренковым Леонидом Трофимовичем. Дальнейшее развитие метода и доведение его до инженерных методик было выполнено сотрудниками этой кафедры к.т.н. Кустенко А.С., к.т.н. Кузнецовым Н.В. и к.т.н. Салтыковым Ю.А.(см. "Вопросы оборонной техники", 1972 г.). Этот метод до сих пор является самым эффективным методом минимизации логических функций.
Я понимаю, что доходчиво изложить метод Мавренкова очень непросто. Вполне допускаю, что не все читатели освоят этот метод. Для решения подавляющего большинства задач вполне достаточно знания карт Карно. Метод Мавренкова должен быть реализован на ЭВМ.
Например, набору x4x3’x2x1’ соответствует обобщённый код 1010. Для ДНФ обобщённый код (ОК) имеет прочерки на местах отсутствующих переменных. Например, для функции от 5 переменных набору x5x2’ соответствует ОК = 1--0-.
Методом обобщённых кодов удобно работать с функциями, заданными таблицами истинности. Причём рабочим наборам соответствуют рабочие обобщённые коды (РОК), запрещённым наборам - запрещённые обобщённые коды (ЗОК).
Введём понятие оценочной функции. Оценочная функция F0p(F1p) определяет количество нулей (единиц) для одного разряда всех РОК. Оценочная функция F0з(F1з) определяет количество нулей (единиц) для одного разряда всех ЗОК.
Функция вида F0 = F0р + F1з называется нулевой оценочной функцией.
Функция вида F1 = F1р + F0з называется единичной оценочной функцией.
В результате минимизации булевой функции получается минимальная ДНФ (МДНФ), состоящая из простых импликант, т.е. таких импликант, дальнейшая минимизация которых не возможна. В методе обобщённых кодов простой импликанте соответствует минимальный обобщённый код (МОК). Будем говорить, что данный МОК покрывает определённый РОК, если нули и единицы в этом РОК стоят в тех же разрядах, что и в данном МОК.
Сущность метода ОК заключается в том, чтобы по максимуму оценочных функций выбрать такие переменные, которые чаще всего встречаются в РОК и реже всего в ЗОК, и на их основе построить такую совокупность минимальных обобщённых кодов, которая покрывала бы все РОК и не покрывала бы ни одного ЗОК.
2.1. Общий алгоритм определения МОК.
Алгоритм 1.
1. Присвоить индексу МОК значение 1, т.е. i :=1.
2. Подсчитать по таблице истинности F0 и F1 для всех разрядов РОК и ЗОК.
3. В качестве базы МОКi (БМОКi) или дополнение к БМОКi выбрать переменную с максимальной F0 или F1 . Если F0 = max, то переменная входит в БМОКi нулём. Если F1=max , то переменная входит в БМОКi единицей. Если несколько переменных имеют максимальные оценочные функции, то выбрать в качестве БМОК ту переменную, у которой соответствующая запрещённая оценочная функция (F0з, F1з) имеет минимальное значение; в противном случае в качестве БМОК взять любую переменную с максимальной оценочной функцией.
4. Выписать все РОК и ЗОК, покрываемые базой МОКi. Если БМОКi не покрывает ни одного РОК или покрывает все ЗОК, то приравнять нулю оценочные функции F0 и F1 для данного разряда и перейти к п.3. Если покрываемых ЗОК нет, то перейти к п.6.
5. Подсчитать F0 и F1 для всех разрядов РОК и ЗОК, покрытых данной базой, кроме тех разрядов, которые образуют БМОКi . Присоединить к БМОКi переменную (дополнение к БМОКi) с максимальной оценочной функцией в соответствии с требованиями п.3. Считать этот ОК новой базой МОКi . Если новая БМОКi покрывает столько же ЗОК, сколько и на предыдущем шаге, то приравнять нулю оценочные функции для дополнения к БМОКi , отбросить присоединённую переменную и добавить к БМОКi переменную с максимальной оценочной функцией в соответствии с требованиями п.3, считать полученный ОК новой БМОКi . Если БМОКi покрывает хотя бы один ЗОК, перейти к п.4.
6. Принять в качестве МОКi базу МОКi.
7. Если все РОК из исходной таблицы истинности покрыты минимальными обобщёнными кодами, перейти к п.9.
8. Выписать из исходной таблицы истинности все ЗОК и те РОК, которые не покрыты минимальными обобщёнными кодами. Считать вновь полученную таблицу исходной таблицей истинности . Увеличить индекс МОК на единицу, т.е. i :=i+1. Перейти к п.2.
9. Конец.
Поясним положение пп.4 и 5 алгоритма 1. Пусть таблица истинности состоит из одного РОК 1110 и трёх ЗОК: 1010, 0110 и 1111.
После подсчёта оценочных функций оказалось, что для второго разряда F0 = 3 = max. Если в соответствии с максимумом оценочной функции взять в качестве БМОК код --0- , то этот код не покроет ни одного РОК, что недопустимо, т.к. БМОК обязательно должна покрыть хотя бы один РОК.
Несколько иная ситуация складывается в том случае, когда БМОК, найденная по максимуму оценочной функции, покрывает часть РОК и все ЗОК. Пусть функция задана пятью РОК и одним ЗОК.
Если в соответствии с максимумом взять в качестве БМОК код --1-, то мы покроем ЗОК, что недопустимо. Поэтому в качестве БМОК можно,например, взять ---1.
Проиллюстрируем выполнение алгоритма 1 примерами.
Задача 7.
Построить МДНФ булевой функции y, заданной таблицей, по методу ОК.
Решение .
1. Выбираем в качестве БМОК1 переменную x3 , т.е. БМОК1 = -1--. Эта БМОК1 покрывает все РОК и один ЗОК .
2. Выписываем эти РОК и ЗОК (см. след. таблицу).
3. По максимальному F0 = 5 определяем вторую переменную базы МОК1. Это переменная x1. Она входит в БМОК инверсным значением, т.е. БМОК1 = -1-0.
4. Так как БМОК1 = -1-0 не покрывает ни одного ЗОК и покрывает все РОК, то минимизацию считаем законченной и принимаем МОК1 = БМОК1 = -1-0 , т.е.
y = x3x1’ .
Такой же результат получается и по карте Карно.
Задача 8.
Построить МДНФ функции, заданной таблицей.
Решение.
1. Принимаем БМОК1 по F1 = 10 (можно по F0 =10).
БМОК1 = --1-----
БМОК1 покрывает один ЗОК и все РОК.
2. Выписываем все РОК и ЗОК, покрываемые БМОК1. После подсчёта оценочных функций оказывается, что максимум F0 приходится на x1, поэтому
БМОК1 = --1----0
МОК1 = БМОК1 = --1----0
3.Непокрытым оказался только один РОК. Выписываем этот РОК и все ЗОК в таблицу.
4. Находим БМОК2 = -----1--
МОК2 = БМОК2 = -----1--
Результат минимизации выглядит так:
y = x6x1’ + x3
Такой же результат получен и по карте Карно.
Задание 3.
Найти минимальную форму функций, указанных в задании 1, методом обобщённых кодов.
2.2. Алгоритм соседнего определения базы МОК (алгоритм Мавренкова).
Алгоритм 1 требует раздельного размещения РОК и ЗОК. Приведение таблицы истинности к такому виду усложняет метод ОК.
Процесс минимизации методом ОК может быть существенно упрощен, если определение БМОК производить с использованием приводимого ниже алгоритма.
Алгоритм 2.
1. Присвоить индексу МОК значение 1, т.е. i := 1 .
2. Присвоить индексу РОК значение 1 , т.е. j := 1.
3. Взять РОК из исходной таблицы истинности и, сравнивая его со всеми ЗОК, определить переменные, по которым РОК может быть склеен с ЗОК. Эта совокупность переменных и будет базой МОКi . Перейти к п.7.
4. Если РОКj не имеет соседних ЗОК, то j := j + 1 и перейти к п.3. Если в таблице истинности нет ни одного РОК, соседнего хотя бы с одним ЗОК, то перейти к п.5.
5. Подсчитать по таблице истинности F0 и F1 для всех разрядов.
6. В качестве базы МОКi (БМОКi) или дополнения к БМОКi выбрать переменную с максимальной F0 или F1. Если F0 = max, то переменная входит в БМОКi нулём. Если F1 = max, то переменная входит в БМОКi единицей. Если несколько переменных имеют одинаковые оценочные (максимальные) функции , то выбрать в качестве БМОКi ту переменную , у которой соответствующая запрещённая оценочная функция ( F0з или F1з ) имеет минимальное значение, в противном случае в качестве БМОКi взять любую переменную с максимальной оценочной функцией F0 или F1 .
7. Выписать РОК и ЗОК, покрываемые базой МОКi. Если БМОКi не покрывает ни одного РОК или покрывает все ЗОК, то приравнять нулю оценочные функции F0 и F1 для данного разряда и перейти к п.6. Если покрываемых ЗОК нет, то перейти к п.9.
8. Подсчитать F0 и F1 для всех разрядов РОК и ЗОК, покрываемых данной базой, кроме разрядов (переменных), образующих БМОКi. Присоединить к БМОКi переменную (дополнение к БМОКi) с максимальной оценочной функцией в соответствии с требованиями п.6. Считать полученный ОК новой базой МОКi . Если новая БМОКi покрывает столько же ЗОК, сколько и на предыдущем шаге, то приравнять нулю оценочные функции или дополнения к БМОКi , отбросить присоединённую переменную и добавить к БМОКi переменную с максимальной оценочной функцией в соответствии с положениями п.6, считать полученный ОК новой БМОКi. Если БМОКi покрывает хотя бы один ЗОК, перейти к п.7.
9. Принять в качестве МОКi базу МОКi .
10. Если все РОК из исходной таблицы истинности покрыты минимальными обобщёнными кодами, перейти к п.12.
11. Выписать из исходной таблицы истинности все ЗОК и те РОК, которые не покрыты минимальными обобщёнными кодами. Считать вновь полученную таблицу исходной таблицей истинности. Увеличить индекс МОК на единицу, т.е. i := i+1. Перейти к п.2.
12. Конец.
Задача 9.
Произвести минимизацию булевой функции, заданной таблицей.
Решение.
1. По алгоритму 2 пп. 1-3 для РОК2 находим соседний ЗОК, т.е. находим БМОК1 = ---0----.
2. По алгоритму 2 пп. 7-9 находим
МОК1 = ---0--0-
Так как МОК1 покрывает все РОК, то в соответствии с п.10 алгоритма 2 получаем
y = x5’x2’
Сущность алгоритма 2 заключается в том, что отыскиваются в первую очередь « необходимые « МОК, т.е. МОК для тех РОК, развязывание которых с ЗОК максимально затруднено, так как они развязываются только по тем переменным, по которым возможно склеивание данного РОК со всеми ЗОК. Под развязыванием понимается процесс выявления тех переменных в РОК, которые не встречаются в ЗОК.
Задача 10.
Произвести минимизацию булевой функции, заданной таблицей.
Решение .
1. По алгоритму 2 пп.1-3 для РОК1 находим
БМОК1 = ----0-
2. По алгоритму 2 пп.7, 8 строим таблицу.
3. По алгоритму 2 п.8 из таблицы находим БМОК1 = ---00-
4. По алгоритму 2 п.9
МОК1 = БМОК1 = ---00-
5. По алгоритму 2 для непокрытых РОК (для РОК3) находим
БМОК2 = -1----.
6. По алгоритму 2 пп.7, 8 , 11 строим таблицу.
7. По алгоритму 2 п.9 находим МОК2
МОК2 = 01----
8. По алгоритму 2 пп.7, 8, 11 строим следующую таблицу .
9. По алгоритму 2 п.3 находим БМОК3
БМОК3 = ----1-
10. По алгоритму 2 пп. 7, 8, 11 строим таблицу.
11. Из таблицы по алгоритму 2 п.8 находим
БМОК3 = ----11
12. По алгоритму 2 пп. 7, 8 строим следующую таблицу.
13. По таблице 17 определяем
МОК3 = -1--11
Таким образом ,
y = x3’x2’ + x5x2x1 + x6’x5
На рисунке представлено решение задачи 10 с помощью карты Карно . Функция y представлена в виде МДНФ.
Из рисунка видно, что результаты минимизации по карте Карно и по методу обобщённых кодов совпадают.
Задача 10а.
Произвести минимизацию логической функции, заданной таблицей истинности.
Т.к. РОК3 и ЗОК1 являются соседними по x7,то в качестве БМОК1 выбираем х7’,не обращая внимания на абсолютный максимум F0 для х8.БМОК1 покрывает РОК1 - РОК5 и ЗОК3,ЗОК5.Подсчитаем оценочные функции для выбора дополнения к БМОК1 и получения МОК1.
Дополнение х4’ могло бы привести нас к МДНФ, поэтому мы выберем эквивалентное по оценочной функции дополнение х1,чтобы убедиться в некоторых недостатках метода. В результате получим МОК1 = x7’x1. Поскольку МОК1 покрывает РОК с номерами 1,3 - 5,то стартовая таблица для синтеза БМОК2 выглядит так:
Исходя из этой таблицы, получаем БМОК2 = x8’. Для нахождения МОК2 строим следующую таблицу.
Отсюда получаем МОК2 = х8’x5’, который дополнительно покрывает РОК2 и РОК6. Найдём БМОК3.
F0 для х3 имеет максимальное значение, но использовать x3’ в качестве БМОК3 нельзя, поскольку единственный РОК не имеет нуля в данном разряде. Принимаем БМОК3 = x8’. Строим очередную таблицу для синтеза последнего МОК.
Из последней таблицы получаем МОК3 = x8’x7x4.Таким образом, мы получили тупиковую ДНФ
y = x8’x7x4 + х8’x5’ + x7’x1.
По карте Карно получена минимальная ДНФ
y =х8’x5’ + x7x1’ + x7’x4’.
Т.е. высокая эффективность метода обобщённых кодов не всегда гарантирует получение МДНФ. Кроме того, если рассмотреть недоопределённую логическую функцию, заданную 8-ичными наборами: РОК – 67,73,63 и ЗОК – 37,65,66, то окажется, что по первому алгоритму получим избыточное решение. В этом случае y = x3’ + x6x2x1. При минимизации по второму алгоритму y = x6x2x1.Таким образом, алгоритм 2 не только менее трудоёмок, но и более эффективен.
Проверка результата минимизации булевых функций.
Результат минимизации булевой функции является корректным, если выполняются следующие условия:
1. Совокупность МОК покрывает все РОК .
2. Совокупность МОК не покрывает ни одного ЗОК.
2.3. Выводы.
Далеко не всегда по методу ОК может быть получена МДНФ. Чаще всего в результате минимизации удаётся получить одну из тупиковых ДНФ. В этом недостаток метода. Алгоритм 2 по сравнению с алгоритмом 1 даёт более компактный результат, т.е. вероятность получения МДНФ по алгоритму 2 выше, чем по алгоритму 1.
Достоинствами метода являются простота и высокая скорость получения результата. Особенно этот метод эффективен для минимизации булевых функций от большого числа переменных (n8). Вполне приемлемым даже без применения ЦВМ является число наборов, на которых задана функция , в пределах 1000. Например , 6 булевых функций от 12 переменных, определённые на 320 наборах были отминимизированы вручную в течение 30 минут. Разумеется, задача такой сложности может быть решена на ЭВМ. Однако даже только на ввод с последующей проверкой 320 наборов для 6 функций потребуется значительно больше времени, чем на ручное решение. Эффективность данного алгоритма выше всех других, известных автору.
В соответствии с алгоритмом 2 в 1974г. была написана программа, которая позволяла минимизировать булевы функции от 36 переменных, определённые на 2000 наборах. Программа осуществляла контроль правильности ввода исходных массивов. Если функция введена неверно, то выводились на печать неправильно введённые РОК или ЗОК, а программа переходила к минимизации следующей функции. Время, затраченное ЦВМ М-220 на минимизацию булевой функции от 36 переменных, определённой на 1000 наборах, составило 6 минут. В 1985г. на языке Паскаль эта программа была переписана для ПЭВМ ДВК-2М. Она обрабатывала 16 функций от 32 переменных. Количество наборов достигало 2000.
Вопрос о минимизации булевых функций вручную или с использованием ПЭВМ решается в зависимости от количества наборов, на которых задана функция, количества соседних РОК и ЗОК, а также от частоты чередования РОК и ЗОК в исходной таблице истинности. Чем больше количество наборов, задающих функцию, чем меньше соседних РОК и ЗОК, чем выше частота чередования РОК и ЗОК, тем предпочтительнее использование ЭВМ. Например, систему из 7 булевых функций от 18 переменных, заданную на 80 наборах, оказалось рациональнее решать с помощью ЭВМ, так как в этой системе не нашлось ни одной соседней пары РОК и ЗОК, а частота чередования РОК и ЗОК для отдельных функций достигала 40. Однако за 40 лет инженерной практики разработки цифровых устройств и систем автор лишь трижды обращался к услугам ЭВМ при решении задач минимизации булевых функций.
Задание 4.
Методом обобщённых кодов найти минимальное представление функций, заданных на рабочих и запрещённых наборах.
4-1) РН(4): 0, 4, 6, 10; ЗН(4): 7, 13. Ответ: Кс = 1
4-2) РН(5): 4, 2, 29, 23; ЗН(5): 3, 21. Ответ: Кс = 7 = (1+1+2)+3
4-3) РН(6): 0, 9, 10, 13, 57, 63, 36; ЗН(6): 27, 29, 18, 44, 33.
Ответ: Кс = 9 = (2+2+2)+3
4-4) РН(6): 1, 4, 14, 21, 35, 62; ЗН(6): 3, 7, 30, 9.
Ответ: Кс = 8 = (2+2+1)+3
4-5) РН(8): 16, 49, 35, 41, 253, 167, 158; ЗН(8): 99, 125, 90, 249, 1
Ответ: Кс = 9 = (2+2+2)+3
Примечание: Кс - коэффициент сложности булевой функции.
«Читай и слушай для собственного развлечения рассказы о хитроумных системах, вникай в интересные вопросы, поставленные там со всей изощрённостью, какой только может наделить их пылкая фантазия, но смотри на всё это только как на упражнения для ума и возвращайся каждый раз к согласию со здравым смыслом...»
(Честерфилд «Письма к сыну»)
|
