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

В то время как Карты Карно (K-maps) отлично справляются с ручной оптимизацией функций от 3 до 5 переменных, для функций с 6 и более переменными визуальный метод ломается: человек не способен эффективно группировать кубы в многомерном гиперпространстве. Метод Куайна-Маккласки, разработанный в 1950-х годах, решает эту проблему путем строгого табличного алгоритма, который идеально подходит для компьютерной реализации (EDA-систем).

Алгоритм состоит из двух основных фаз:

Фаза 1: Нахождение всех простых импликант.

• Все минтермы (строки таблицы истинности, где функция равна 1) выписываются в двоичном виде и группируются по количеству единиц в их двоичном коде (весу).
• Алгоритм сравнивает каждый терм из одной группы с каждым термом из соседней группы. Согласно закону склеивания булевой алгебры (A·B + A·¬B = A), если два терма отличаются ровно в одном бите, они сливаются в один более короткий терм, а отличающийся бит заменяется на прочерк ("-").
• Этот процесс склеивания повторяется рекурсивно до тех пор, пока не останется ни одной пары, которую можно было бы объединить. Термы, которые не смогли ни с кем склеиться на любом этапе, называются простыми импликантами.

Фаза 2: Построение минимального покрытия (Таблица импликант).

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

Результатом работы метода является Абсолютная Минимальная ДНФ. В современной микроэлектронике метод Куайна-Маккласки был заменен более быстрыми эвристическими алгоритмами (такими как Espresso от IBM), но его математический аппарат до сих пор остается эталоном для точного логического синтеза цифровых автоматов.