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

Постановка и методы решения задачи минимизации функции алгебры логики (ФАЛ)

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

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

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

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

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

Метод Квайна основан на последовательном применении к ДСНФ функции АЛ операций неполного склеивания и элементарного поглощения. Метод применим в основном для ФАЛ от небольшого количества аргументов.

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

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

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

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

При выполнении минимизации осуществляется накрытие с помощью правильных конфигураций полей карты, содержащих единицы или нули. Правильными конфигурациями ранга i на карте Карно для ФАЛ от n-переменных являются все прямоугольники (вертикальные, горизонтальные и квадратные), имеющие площадь 2^n–i (i = 1, 2, ..., n). Следовательно, правильными конфигурациями на карте Карно для ФАЛ от двух переменных являются все прямоугольники, имеющие площадь 2^2–i (рис. 10.1), от трёх переменных – прямоугольники, имеющие площадь 2^3–i (рис. 10.2), от четырёх переменных – прямоугольники, имеющие площадь 2^4–i (рис. 10.3). Рангом накрытия называется сумма рангов всех правильных конфигураций, образующих накрытие.

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

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

Рисунок 10.1 Использование карт Карно при минимизации ФАЛ от двух переменных

Рисунок 10.2 Использование карт Карно при минимизации ФАЛ от трёх переменных

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

Как видно из рис. 10.1–10.3, при объединении двух полей исключается одна переменная, при объединении четырех полей – две переменные, при объединении восьми полей – три переменные.

В поля карты, соответствующие наборам аргументов, при которых значение функции нас не интересует, вместо нулей или единиц проставляется символ «×» (рис. 10.3). Поля, отмеченные символом «×», включаются в конфигурации накрытия, если это способствует получению более простого выражения для записи функции.

Рисунок 10.3 Использование карт Карно при минимизации ФАЛ от четырёх переменных

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

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

Для удобства записи значений, принимаемых функцией на каждом наборе аргументов, вместо куба рассматриваются четыре располагаемые рядом карты Карно по 16 полей (рис. 10.5).

Рисунок 10.4 Использование карт Карно при минимизации ФАЛ от пяти переменных

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

Рисунок 10.5 Использование карт Карно при минимизации ФАЛ от пяти переменных