Логических устройств

Частной задачей, возникающей на первом этапе, является доопределение значений выходных сигналов (и функций) при не оговорённых условиях. Это - задача синтеза по неполностью заданным условиям. Произвольное доопределение условий работы устройства может привести к неоправданным затратам на его создание. Поэтому названную процедуру следует выполнить при минимизации логико-математической модели устройства.

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

Следует отметить, что задача построения устройства (его синтеза) ставится, когда его элементная база (по видам физических элементов) предопределена, либо предположительно выбрана. Например, известно, что надо построить релейно-контактное устройство, либо построить аналогичное устройство на микросхемах. Поэтому при поиске минимальных форм алгебраических выражений логических функций следует учитывать возможности элементной базы устройства. Тем не менее, на втором этапе возникают две частные задачи:

1) задача минимизации алгебраических форм функций;

2) поиск алгебраических форм неполностью определённых логических функций.

Обе задачи носят проблемный характер, так как не имеют однозначного решения. В частности, существующие методы минимизации логических функций ориентированы в основном на получение МДНФ либо МКНФ, поскольку разработаны для минимизации функций в базисе {И, ИЛИ, НЕ}. Методы же минимизации логических функций в других базисах разработаны недостаточно либо вообще отсутствуют.

В общем случае задача минимизации формулируется следующим образом: требуется отыскать такое алгебраическое выражение функции, в котором содержалось бы наименьшее число независимых переменных (букв) и наименьшее число логических символов. Так при минимизации функций в базисе {И, ИЛИ, НЕ} в алгебраическом (минимальном) выражении должно быть наименьшее число переменных и наименьшее число логических символов (конъюнкции, дизъюнкции и инверсии). А при минимизации функций в «смешанном» базисе, содержащем, например, кроме перечисленных символов, ещё и символ Å (суммы по mod2), также должно быть наименьшее число переменных и указанных символов.

Поиск алгебраических выражений неполностью определённых функций также многовариантная задача. В работе [5] изложен метод «неопределённых коэффициентов» для отыскания алгебраических выражений недоопределённых функций. Однако он практически непригоден для поиска выражений функций от 6 аргументов, громоздок и мало эффективен при неавтоматизированном применении («вручную»). Если же применять карты Карно для минимизации недоопределённых функций, то сложность получаемых выражений будет зависеть от степени недоопределённости и варианта доопределения. Этих же вариантов может быть очень много.

Достаточно просто указанные частные задачи решаются на основе визуально-матричного метода минимизации логических функций, основы которого изложены в работах [3, 6].

В настоящем разделе кратко излагаются некоторые используемые на практике методы минимизации булевых функций.