Минимизация функций алгебры логики – это процедура нахождения наиболее простого их представления в виде суперпозиции функций, составляющих функционально полную систему, при одновременной оптимизации ее технической реализации по некоторым критериям в условиях ряда ограничений. Критериями оптимизации могут быть объем оборудования (количество вентилей, корпусов), габариты, вес, энергопотребление, стоимость, быстродействие, надежность. Существует достаточно много методов упрощения, здесь будут рассмотрены три основных метода: с использованием карт Карно, избыточных комбинаций и для системы нескольких функций.
Для упрощения можно использовать как непосредственно аксиомы алгебры логики, так и специальные приемы. Произведем упрощение выражения для F на основе аксиом:
Однако такой метод не имеет достаточной наглядности, а также требует опыта и интуиции. Поэтому чаще используют более формализованные методы упрощения.
Метод карт Карно. Карта Карно является специальной формой таблицы истинности функции, позволяющей не только её задать, но и выполнить минимизацию. Карта содержит 2n клеток для всех возможных сочетаний переменных и их инверсий, причём каждой клетке соответствует строго определённый минтерм. Так, для трёх переменных А, В и С карта содержит 23 = 8 клеток, а для четырех переменных – 24 = 16, и имеет вид, показанный на рис. 3.3.
Рис. 3.3 Карта Карно для четырёх переменных
Обычно в клетки карты заносят не сами минтермы, а метят единицами клетки, соответствующие этим минтермам. Правила минимизации с использованием карт Карно заключаются в следующем:
1) В карту Карно заносится исходная функция. Для этого метятся единицами клетки, соответствующие присутствующим в этой функции минтермам. Если на одну и ту же клетку приходится несколько единиц, то она метится лишь один раз.
2) Соседние, помеченные единицами клетки обводятся контурами («склеива-ются»). Контур склейки должен иметь форму квадрата или прямоугольника и содержать число клеток 2i (i = 0, 1, 2,…n).
3) Одни и те же клетки можно обводить сколько угодно раз.
4) При проведении контуров крайние строки карты (верхние и нижние, левые и правые), а также угловые клетки считаются соседними (для карт до четырех переменных).
5) Каждый контур должен включать максимально возможное количество клеток, а число контуров должно быть минимальным.
6) Функция выписывается из контуров карты. Переменная, входящая в контур как в прямом, так и в переменном виде, поглощается (см. закон поглощения).
7) Все единицы в карте (даже одиночные) должны быть охвачены контурами.
Принцип минимизации заключается в объединении соседних полей карты в пределах правильных конфигураций. При нахождении минимальной формы ФАЛ, выписываются переменные, не изменяющие своего значения в пределах склейки
Рис. 3.4 Диаграмма минимизации функции F
Пример минимизации приведённой выше функции F методом Карт Карно представлен на рис. 3.4. Значения 0 либо 1 над клетками карты указывают, в каких полях карты ложны либо истинны значения Х1 либо Х2.
Запись функции F заключается в занесении единиц в клетки карты, соответствующие минтермам этой функции. Для данного случая можно построить три контура, содержащих по две клетки. Искомое минимизированное выражение есть логическая сумма укороченных произведений переменных, имеющих одно значение в пределах контура, без переменных, имеющих оба возможных значения (0 и 1) в пределах контура. Таким образом, согласно рис. 3.4, будем иметь
где первый член дает вертикальный контур, второй член – правый горизонтальный контур, и третий член определяется левым горизонтальным контуром.
После этого можно уже составлять функциональную схему, выполняющую операцию F (рис. 3.5).
Рис. 3.5 Схема реализации упрощённой функции F
Использование избыточных комбинаций. При проектировании
