Минимизация функций алгебры логики методом ненаправленного графа

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

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

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

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

• 1.    Выявить минтермы (наборы переменных), при которых функция обращается в логическую единицу.

• 2.    Определить уровни графа (индексы) по количеству единиц в наборе.

• 3.    Построить фрагмент графа с определением дуг, соединяющих вершины графа.

Построение графа является общим для всех графических структур.

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

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

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

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

Рассмотрим пример. Пусть задана функция в виде:

f = abcd v abcd v abcd v abcd v abcd V abcd v abcd .

Функция зависит от четырех переменных, полный граф для нее представлен на рисунке 1. Выполним построение интересующего нас фрагмента данного графа. Так как ФАЛ принимает значения логической единицы в записанных минтермах, то во фрагменте оставляем соответствующие вершины с номерами 0000, 0001, 0010, 0011, 0101, 0111, 1010 (для упрощения запишем их номера в десятичной системе счисления: 0, 1, 2, 3, 5, 7, 10 (рисунок 3)).

Рисунок 1 - Полный граф для функции четырех переменных

Рисунок 2 - Фрагмент графа для исследуемой ФАЛ

На рисунке 2 видно, что из полученного графа можно выделить два четырехугольника (0-1-3-2 и 1-3-7-5) и отрезок 2-10.

Из четырехугольника 0-1-3-2 видно, что общей частью всех вершин являются два первых нуля «00__». Также выделим общую часть вершин второго четырехугольника 1-3-7-5: «0__1»; общую часть вершин отрезка 2-10: «_010». Записав полученное выражение в буквенном виде, получим результат минимизации заданной ФАЛ:

f = ab v ad v bcd .

Выполним проверку аналитическим методом, используя законы и тождества алгебры логики.

f = abcd v abcd v abcd v abcd v abcd v abcd v abcd = abc ( d v d ) v bcd ( a v v a ) v abd ( c v c ) v abc ( d v d ) v abd ( c v c ) = abc v bcd v abd v abc v abd =

= ab ( c v c ) v bcd v ad(b v b ) = ab v bcd v ad.

Сравнивая результаты решения, можно сделать вывод об их совпадении.

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