И обобщенных кодов

Минимизация логических функций на основе решетки соседних чисел

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

Для вхождения в решетку соседних чисел (РСЧ) необходимо задать функцию в символической форме.

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

Пусть, например, имеем СДНФ функции требуется ее минимизировать. Выбираем базу a, b, c, d и переходим к рабочим числам:

Входим в четырехразрядную решетку соседних чисел и находим эти рабочие числа. Видим, что числа 1 и 5, 5 и 13 соседние, а 8 – отдельное число. Записываем их по группам в виде дизъюнкции

Выписываем обобщенные коды (ОК) линий связи:

Так как число 8 не объединяется с другими рабочими числами, то его ОК имеет все четыре разряда, т.е. само двоичное число.

Далее поразрядно переходим к ДНФ и получаем:

Вынося переменные за скобки, получим:

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

Рассмотрим общую методику минимизации не полностью определенных логических функций по РСЧ.

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

Минимизация с использованием решетки состоит в следующем.

1. На решетке соседних чисел фиксируются рабочие и запрещенные весовые состояния.

2. Рабочие числа на решетке группируются в фигуры – линии, квадраты, полосы (кубы), позволяющие получить обобщенный код с максимальным числом тире, т.е. в максимальные правильные фигуры. Группы рабочих состояний дополняются при необходимости условными, при этом каждое число (рабочее и условное) можно использовать несколько раз в разных фигурах.

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

3. Из решетки выписываются обобщенные коды, которые получились в результате логического сложения всех рабочих и дополняющих условных весовых состояний, т.е. обобщенные коды полученных фигур.

4. На основании полученных обобщенных кодов записывается ДНФ функции при выбранной базе.

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

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

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

Рассмотрим примеры.

Пример 3.7 Минимизировать функцию

Для простоты уяснения методики возьмем скелет решетки соседних чисел – только вершины (Рисунок 3.15) – и на нем произведем построение фигур, причем стремимся охватить рабочие числа максимальными правильными фигурами, добавляя при необходимости условные числа. На решетке запрещенные числа зачеркнем, а рабочие – подчеркнем. Следует составить фигуры, чтобы в них вошли все рабочие числа и необходимые условные. Видим, что полоса не получается.

Берем квадрат и квадрат Эти два квадрата полностью охватывают все рабочие числа и не затрагивают запрещенных. Выписываем обобщенный код (из полной РСЧ – см. рисунок 3.14):

Переходим к ДНФ и упрощаем:

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

Пример 3.8 Минимизировать функцию

Получаем две полосы (два куба) (Рисунок 3.16):

Итак,

Отметим, что если логическая функция зависит только от трех переменных, то следует пользоваться только верхней полосой решетки соседних чисел, отбрасывая старший разряд, или 3-разрядной решеткой, так называемым кубом соседних чисел (Рисунок 3.17).

Рисунок 3.16

Рисунок 3.17

При пользовании верхней полосой 4-разрядной решетки следует отбрасывать старший разряд.

Пример 3.9 Минимизировать функцию

Пример 3.10 Дана ДНФ Найти СДНФ.

Выбираем базу a, b, c и получаем:

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

Пример 3.11 Определить сокращенную ДНФ функции

На скелете решетки соседних чисел (Рисунок 3.18) отметим рабочие (подчеркнем) и запрещенные (зачеркнем) числа (вершины) и определим все возможные максимальные правильные фигуры.

Получим всего 7 максимальных правильных фигур, которым соответствуют обобщенные коды (смотри полную РСЧ) 0 – 0 –; 0 – – 0; – – 01; 1 – – 1; 10 – –; – 00 –; – 0 – 0.