Цели минимизации ПФ

При технической реализации переключательных функций, широко используемых в вычислительной технике, системах автоматического (автоматизированного) управления и контроля, возникает задача нахождения наиболее экономичного представления соответствующих переключательных функций. По существу решается задача оптимизации, причем минимизируется стоимость реализации. Понятие стоимости устройства, реализующего переключательную функцию – дискретного устройства – относительно. Для переключательных схем, реализуемых в виде релейно-контактных схем, для схем из корпусных транзисторов и резисторов, из микросхем логических элементов малой степени интеграции, минимизация числа реле, контактов, транзисторов, числа микросхем и означает снижение стоимости [28]. Это было особенно актуально на ранних этапах развития дискретной, цифровой техники. Для современных цифровых автоматов на больших и сверхбольших интегральных схемах (БИС и СБИС) стоимость определяется площадью схемы на кристалле кремния и непосредственно не связана с числом микротранзисторов и других элементов. Нередко схема с большим числом элементов, но обладающая высокой регулярностью, занимает небольшую площадь, кроме того, она выгодна с точки зрения проектирования, ведь стоимость проектирования, как и стоимость изготовления, входит в суммарную стоимость устройства [28].

При построении устройства из дискретных компонентов в целях повышения надежности наряду с уменьшением их числа (что увеличивает вероятность безотказной работы) большое значение придается уменьшению числа соединений между компонентами (это также увеличивает вероятность безотказной работы). Кстати, эта задача решается на соответствующем графе – он разбивается на подграфы, минимально связанные между собой. Однако, для БИС надежность соединений внутри кристалла достаточно высока по сравнению с надежностью соединений между кристаллами. В связи с этим большое значение приобретает деление системы на БИС таким образом, чтобы уменьшить число точек соединений между ними.

Ограничимся в дальнейшем целью нахождения наиболее простого представления переключательной функции в смысле наименьшего числа входящих в нее символов (букв). Процесс получения такого представления будем называть минимизацией. Под различными символами (буквами) будем понимать вхождения одной и той же переменной в различные дизъюнктивные (конъюнктивные) члены функции. Так, функция z₁(аbс)=аb Ú `aс Ú bс содержит шесть букв, а функция z<sub>2</sub>(аbс)=аb Ú `aс – четыре буквы, хотя обе функции зависят от трех переменных а, b, с (закон обобщенного склеивания z₁=z₂).

Методы минимизации разрабатываются применительно к каждой отдельной функциональной полной системе элементных переключательных функций. Наиболее детально такие методы разработаны для систем из дизъюнкции, конъюнкции и инверсии.

При этом задача минимизации переключательной функции сводится к нахождению такой ее формы, которая содержит наименьшее число дизъюнкций, конъюнкций и инверсий.

Нахождение минимального представления функции в виде ДНФ или КНФ связано с решением двух основных задач [17]. Во-первых, это определение конъюнкций (дизъюнкций) входящих в ДНФ (КНФ), каждая из которых содержит минимальное число букв. Во-вторых, это определение ДНФ (КНФ), содержащей минимальное число различных элементарных конъюнкций (дизъюнкций).

Будем рассматривать в основном минимизацию переключательных функций в классе ДНФ, не требуя минимизации числа инверсий.

Основные понятия минимизации ПФ

При минимизации переключательных функций существенную роль играют понятия импликанты, простой импликанты, имплиценты и простой имплиценты [14]. Пусть f(x), g(x), p(x) – полностью определенные функции, причем под х понимается некоторый набор из n переменных (х₁х₂...х_n). Функция f(х) определена на рабочих (единичных) наборах М₁[f(х)] и множестве запрещенных (нулевых) наборов М₀[f(х)]. Функция g(x) определена на множестве рабочих (единичных) наборов М₁[g(x)], а функция р(х) – на множестве запрещенных (нулевых) наборов М₀[р(х)].

Переключательная функция g(х) называется импликантой переключательной функции f(х), если множество рабочих (единичных) наборов функции g(х) совпадает или является подмножеством множества рабочих наборов функции f(х), т.е. М₁[g(x)]Í М₁[f(x)], где Í – знак включения в множество, означающий, что всякий элемент левого множества является элементом правого множества. При этом говорят, что М₁[f(x)] содержит М₁[g(x)], т.е. в соответствии с определением импликации g(x)®f(x).

Переключательная функция р(х) является имплицентой переключательной функции f(х), если множество запрещенных (нулевых) наборов функции р(х) совпадает или является подмножеством множества запрещенных (нулевых) наборов функции f(х), т.е. М₀[р(x)]Í М₀[f(x)].

Пусть функция в СДНФ имеет вид:

f(x₁x₂x₃)=`x<sub>1</sub> x<sub>2</sub> x<sub>3</sub> Ú x<sub>1</sub> x<sub>2</sub>`x₃ Ú x₁x₂x₃;

g₁(x)=`x₁ x₂ x₃ (конституента СДНФ);

g₂(x)= х₁ х₂`x₃ (конституента СДНФ);

g₃(x)= х₁ х₂ х₃ (конституента СДНФ);

g₄(x)= f(х), т.е. сама функция в СДНФ.

Из СДНФ можно получить другие импликанты путем всевозможных группировок ее членов и многократного использования (по возможности) закона склеивания, пока не останется конъюнкций, отличающихся значениями одной переменной ( в одной, в другой, если остальные члены конъюнкции одинаковы).

Так:

Группировка первой и второй конституенты не позволяет применить закон склеивания:

Других вариантов комбинаций и склеиваний для f(х) нет.

Простой импликантой функции f(х) называется любая элементарная конъюнкция в g(х), являющаяся импликантой функции и обладающая тем свойством, что никакая ее собственная часть уже не является импликантой. В примере импликанты g₅=х₁х₂, g₆=х₂х₃ являются простыми импликантами функции f. Импликанты g₁, g₂, g₃, g₇ и, естественно, g₄ – не являются простыми, т.к. их части являются импликантами функции f: например, g₅ является частью g₂ (g₃). Говорят, что простые импликанты покрывают или поглощают соответствующие конституенты.

В булевой алгебре переключательных функций утверждается и доказывается: 1) дизъюнкция любого числа импликант переключательной функции также является импликантой этой функции; 2) любая переключательная функция равносильна дизъюнкции всех своих простых импликант, и такая форма ее представления называется сокращенной ДНФ (СкДНФ). Рассмотренный перебор всех возможных импликант переключательной функции f дает возможность убедиться, что простых импликант всего две: g₅, g₆. Тогда сокращенная ДНФ функции f имеет вид:

f=g₅Ú g₆=х₁х₂Ú х₂х₃.

Рабочими наборами функции f(х₁х₂х₃) являются 011, 110, 111 (табл. 34). Из таблицы видно, что импликанты g₅, g₆ в совокупности покрывают своими единицами все единицы функции f, т.е. рабочие наборы сокращенной ДНФ = 110, 111, 011, 111, последний повторяется дважды. Получение сокращенной ДНФ – первый этап минимизации.

Иногда из сокращенной ДНФ можно убрать одну или несколько простых импликант, не нарушая количества необходимых рабочих наборов. Такие простые импликанты назовем лишними. В нашем случае их нет. Исключение лишних простых импликант из сокращенной ДНФ – второй этап минимизации.

Таблица 34

Таблица истинности импликант

Сокращенная ДНФ переключательной функции называется тупиковой, если в ней отсутствуют лишние простые импликанты.

Устранение лишних простых импликант из сокращенной ДНФ переключательной функции не является однозначным процессом, т.е. переключательная функция может иметь несколько тупиковых ДНФ.

Тупиковые ДНФ, содержащие минимальное число букв, являются минимальными.

Минимальных ДНФ тоже может быть несколько. Минимальная ДНФ функции, найденная путем построения и перебора всех тупиковых ДНФ и выбора из них самой минимальной, называется общей (абсолютной) тупиковой ДНФ.

Поиск минимальной ДНФ всегда связан с перебором решений. Существуют методы уменьшения перебора, но он всегда имеется. Как правило, ограничиваются нахождением одной или нескольких тупиковых ДНФ, из которых выбирают минимальную, – её называют частной минимальной ДНФ и считают близкой к общей (абсолютной).

При минимизации не полностью определенных переключательных функций особенностью является то, что необходимо найти такое ее доопределение за счет условных наборов, которое соответствует минимальной ДНФ, содержащей наименьшее число букв.