Перейти к содержанию

Метод Куайна — Мак-Класки

Карта Карно наглядна, но на пяти-шести переменных становится неудобной. Метод Куайна — Мак-Класки решает ту же задачу таблицами двоичных кодов: он систематичен, не зависит от числа переменных и легко переносится в программу.

Обновлено Редакция GAW

Содержание

Метод Куайна — Мак-Класки (Quine–McCluskey method) — табличный алгоритм минимизации логической функции в форме суммы произведений. Идею последовательной склейки предложил У. В. Куайн, а Э. Дж. Мак-Класки в статье 1956 года в Bell System Technical Journal упростил запись, сделал процедуру систематической и добавил учёт безразличных наборов. В отличие от методов Карно, Айкена и Куайна, которые, по его словам, отказывают на достаточно сложных функциях, новый метод легко программируется.

Шаги

  1. Минтермы в двоичной записи. Каждую единицу функции записывают двоичным кодом; удобно сгруппировать коды по числу единиц.
  2. Склейка. Два кода, совпадающие во всех позициях, кроме одной, где ни у одного нет прочерка, заменяются кодом с прочерком в этой позиции: 1000 и 1001 дают 100-. Процедуру повторяют для полученных кодов, пока склеивать нечего. Все участвовавшие в склейке коды помечают.
  3. Простые импликанты. Непомеченные коды — простые импликанты.
  4. Таблица покрытия. Столбцы — минтермы функции, строки — простые импликанты, крестик — импликанта покрывает минтерм. Строки с единственным крестиком в каком-либо столбце обязательны. Остальные столбцы закрывают наименьшим числом строк, предпочитая строки с бо́льшим числом крестиков — у них меньше литералов.

Пример

Для T = Σ(3, 7, 8, 9, 12, 13) из статьи Мак-Класки склейка даёт 0-11 и, через промежуточные 100-, 110-, 1-00 и 1-01, член 1-0-. Это две простые импликанты, обе обязательны, и минимальная сумма — x₁'x₃x₄ + x₁x₃'. Мак-Класки разбирает и функции, где выбор неоднозначен: если два варианта дают одинаковое число членов, минимальной считается сумма с меньшим числом литералов, например 11 против 12.

Безразличные наборы

Безразличные наборы участвуют в склейке наравне с минтермами — это даёт более короткие импликанты, — но в таблицу покрытия как столбцы не входят. Так метод использует свободу, которую дают «невозможные» входы, не обязывая её покрывать.

Где встречается

Методом простых импликант и таблицы покрытия минимальные формы находят симулятор логических схем и карта Карно онлайн на этом сайте. Для ручной работы с тремя-четырьмя переменными удобнее карта Карно, а табличный метод показывает, что происходит «под капотом».

Частые вопросы

Чем метод Куайна — Мак-Класки лучше карты Карно?

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

Что делать, если после обязательных импликант остаётся выбор?

Закрыть оставшиеся минтермы наименьшим числом строк таблицы покрытия. Мак-Класки советует располагать строки по числу крестиков и при равном выборе брать строку с бо́льшим их числом: у такой импликанты меньше литералов. Если и это не решает, минимальной считается сумма с меньшим общим числом литералов.

Как метод учитывает безразличные наборы?

На этапе склейки безразличные наборы добавляют к минтермам, чтобы получить более короткие импликанты. На этапе покрытия их в столбцы таблицы не включают: покрывать нужно только настоящие единицы функции. Мак-Класки описывает эти члены как включаемые в функцию «только для удобства проектировщика».

Источники

  1. E. J. McCluskey. Minimization of Boolean functions. The Bell System Technical Journal, 1956, vol. 35, no. 6, p. 1417 (поступила 26 июня 1956 г.) — аннотация: систематическая процедура записи функции как минимальной суммы произведений, упрощение и расширение метода У. В. Куайна, с учётом членов, включаемых для удобства проектировщика; разд. 1: методы Карно, Айкена и Куайна отказывают на достаточно сложных функциях, новый метод систематичен и легко программируется; разд. 3: склейка в двоичных символах — два символа, совпадающие во всех позициях, кроме одной, без прочерка в ней, заменяются символом с прочерком; разд. 4: таблица простых импликант, строки с единственным крестиком в столбце обязательны
  2. Kuphaldt T. R. Lessons In Electric Circuits, Vol. IV — Digital, ch. 8 «Karnaugh Mapping» (CC BY) — минимизация картой Карно для 2–6 переменных, группы размером в степень двойки; безразличные клетки можно использовать для увеличения групп

Нашли ошибку?

Смотрите также