Алгоритм Куайна-Маккласка ( ККА ), также известный как метод простого импликанта , является методом , используемым для минимизации из функций булевых , который был разработан Willard В. Куайным в 1952 году [1] [2] и расширен Edward J. Маккласка в 1956. [3] В качестве общего принципа этот подход уже был продемонстрирован логиком Хью МакКоллом в 1878 году, [4] [5] [6] был доказан Арчи Блейком в 1937 году, [7] [8] [9] [6]и был вновь открыт Эдвардом В. Самсоном и Бертоном Э. Миллсом в 1954 году [10] [6] и Раймондом Дж. Нельсоном в 1955 году. [11] [6] Также в 1955 году Пол В. Абрахамс и Джон Г. Нордал [12], а также Альберт А. Маллин и Уэйн Г. Келлнер [13] [14] [15] [16] предложили десятичный вариант метода. [17] [14] [15] [16] [18] [19] [20] [21]
Алгоритм Куайна – Маккласки функционально идентичен отображению Карно , но табличная форма делает его более эффективным для использования в компьютерных алгоритмах, а также дает детерминированный способ проверки достижения минимальной формы логической функции. Иногда его называют методом табуляции.
Метод состоит из двух этапов:
- Нахождение всех простых импликантов функции.
- Используйте эти простые импликанты в диаграмме простых импликантов, чтобы найти основные простые импликанты функции, а также другие простые импликанты, которые необходимы для покрытия функции.
Сложность
Хотя алгоритм Куайна – Маккласки более практичен, чем отображение Карно при работе с более чем четырьмя переменными, он также имеет ограниченный диапазон применения, поскольку решаемая им проблема является NP-полной . [22] [23] [24] Время работы алгоритма Куайна – Маккласки растет экспоненциально с увеличением числа переменных. Для функции n переменных количество простых импликант может достигать 3 n / ln ( n ), [ необходима ссылка ], например, для 32 переменных может быть более 534 × 10 12 простых импликант. Функции с большим количеством переменных должны быть минимизированы потенциально неоптимальными эвристическими методами, из которых эвристический логический минимизатор Espresso был стандартом де-факто в 1995 году. [ Нуждается в обновлении ] [25]
Второй шаг алгоритма сводится к решению задачи заданного покрытия ; [26] На этом шаге алгоритма могут возникнуть NP-трудные экземпляры этой проблемы. [27] [28]
Пример
Вход
В этом примере входом является логическая функция с четырьмя переменными, что оценивается как о ценностях а также , принимает неизвестное значение на а также , и чтобы везде (где эти целые числа интерпретируются в их двоичной форме для ввода в для краткости обозначений). Входы, которые оцениваются какназываются «минтермами». Мы кодируем всю эту информацию, записывая
Это выражение говорит, что функция вывода f будет равна 1 для minterms а также (обозначается термином 'm') и что нам не важен вывод для а также комбинации (обозначаются термином "d").
Шаг 1: поиск основных импликантов
Сначала мы записываем функцию в виде таблицы (где x означает безразлично):
А B C D ж m0 0 0 0 0 0 m1 0 0 0 1 0 m2 0 0 1 0 0 м3 0 0 1 1 0 м4 0 1 0 0 1 m5 0 1 0 1 0 m6 0 1 1 0 0 m7 0 1 1 1 0 m8 1 0 0 0 1 m9 1 0 0 1 Икс m10 1 0 1 0 1 m11 1 0 1 1 1 m12 1 1 0 0 1 m13 1 1 0 1 0 m14 1 1 1 0 Икс m15 1 1 1 1 1
Можно легко сформировать каноническую сумму выражений продуктов из этой таблицы, просто суммируя minterms (без учета безразличных терминов ), где функция оценивает единицу:
- f A, B, C, D = A'BC'D '+ AB'C'D' + AB'CD '+ AB'CD + ABC'D' + ABCD.
что не является минимальным. Таким образом, для оптимизации все minterms, которые оценивают один, сначала помещаются в таблицу minterm. В эту таблицу также добавляются безразличные термины (имена в скобках), поэтому их можно комбинировать с minterms:
Количество
единицМинтерм Двоичное
представление1 м4 0100 m8 1000 2 (m9) 1001 m10 1010 m12 1100 3 m11 1011 (m14) 1110 4 m15 1111
На этом этапе можно начинать комбинировать минтермы с другими минтермами. Если два термина отличаются только одной цифрой, эту цифру можно заменить дефисом, указывающим, что цифра не имеет значения. Термины, которые больше не могут быть объединены, отмечены звездочкой (*). Например, 1000
и 1001
можно объединить, чтобы получить 100-
, указывая, что оба термина подразумевают, что первая цифра есть, 1
а следующие две - 0
.
Количество
единицМинтерм 0-куб Импликант размера 2 1 м4 0100 м (4,12) -100 * m8 1000 м (8,9) 100- - - м (8,10) 10-0 - - м (8,12) 1-00 2 m9 1001 м (9,11) 10-1 m10 1010 м (10,11) 101- - - м (10,14) 1-10 m12 1100 м (12,14) 11-0 3 m11 1011 м (11,15) 1-11 m14 1110 м (14,15) 111- 4 m15 1111 -
При переходе от размера 2 к размеру 4 рассматривать -
как третье битовое значение. Например, -110
и -100
можно комбинировать, чтобы давать -1-0
, как можно -110
и -11-
отдавать -11-
, но -110
и 011-
нельзя, потому что -110
подразумевается, 1110
пока 011-
не является. (Уловка: сопоставьте -
первое.)
Количество
единицМинтерм 0-куб Импликант размера 2 Импликант размера 4 1 м4 0100 м (4,12) -100 * м (8,9,10,11) 10 - * m8 1000 м (8,9) 100- м (8,10,12,14) 1–0 * - - м (8,10) 10-0 - - - м (8,12) 1-00 - 2 m9 1001 м (9,11) 10-1 м (10,11,14,15) 1-1- * m10 1010 м (10,11) 101- - - - м (10,14) 1-10 - m12 1100 м (12,14) 11-0 - 3 m11 1011 м (11,15) 1-11 - m14 1110 м (14,15) 111- - 4 m15 1111 - -
Примечание. В этом примере ни один из терминов в таблице импликантов размера 4 нельзя комбинировать дальше. Как правило, этот процесс следует продолжать (размеры 8, 16 и т. Д.) До тех пор, пока не перестанут быть объединены термины.
Шаг 2: простая импликантная диаграмма
Ни один из терминов не может быть скомбинирован дальше этого, поэтому на этом этапе мы строим существенную таблицу импликантов простых чисел. Вдоль стороны идут первичные импликанты, которые только что были сгенерированы, а вверху идут минтермы, указанные ранее. Термины безразличия не помещаются сверху - они опускаются в этом разделе, потому что они не являются необходимыми входными данными.
4 8 10 11 12 15 ⇒ А B C D м (4,12) * ⇒ - 1 0 0 м (8,9,10,11) ⇒ 1 0 - - м (8,10,12,14) ⇒ 1 - - 0 м (10,11,14,15) * ⇒ 1 - 1 -
Чтобы найти основные простые импликанты, мы пробегаемся по верхнему ряду. Мы должны искать столбцы только с одним «✓». Если в столбце есть только один «✓», это означает, что минтерм может быть покрыт только одним простым импликантом. Этот главный импликант очень важен .
Например: в первом столбце с minterm 4 только одно «✓». Это означает, что m (4,12) существенно. Так что ставим рядом звезду. Minterm 15 также имеет только одно «✓», поэтому m (10,11,14,15) также имеет важное значение. Теперь закрыты все столбцы с одним «✓».
Импликанты второго простого числа могут быть «покрыты» третьим и четвертым импликантами, а импликанты третьего простого числа могут быть «покрыты» вторым и первым, и поэтому ни один из них не является существенным. Если простая импликанта важна, то, как и следовало ожидать, необходимо включить ее в минимизированное логическое уравнение. В некоторых случаях существенные простые импликанты не охватывают все минтермы, и в этом случае могут быть использованы дополнительные процедуры сокращения диаграммы. Простейшая «дополнительная процедура» - это метод проб и ошибок, но более систематический - метод Петрика . В текущем примере существенные простые импликанты не обрабатывают все минтермы, поэтому в этом случае существенные импликанты могут быть объединены с одной из двух несущественных импликант, чтобы получить одно уравнение:
- f A, B, C, D = BC'D '+ AB' + AC [29]
или же
- f A, B, C, D = BC'D '+ AD' + AC
Оба этих окончательных уравнения функционально эквивалентны исходному подробному уравнению:
- f A, B, C, D = A'BC'D '+ AB'C'D' + AB'C'D + AB'CD '+ AB'CD + ABC'D' + ABCD '+ ABCD.
Смотрите также
- Каноническая форма Блейка [7] [6]
- Алгоритм Бухбергера - аналогичный алгоритм для алгебраической геометрии
- Метод Петрика
- Качественный сравнительный анализ (QCA)
Рекомендации
- ↑ Куайн, Уиллард Ван Орман (октябрь 1952 г.). «Проблема упрощения функций истины». Американский математический ежемесячник . 59 (8): 521–531. DOI : 10.2307 / 2308219 . JSTOR 2308219 .
- ^ Куайн, Уиллард Ван Орман (ноябрь 1955 г.). «Способ упростить функции истины». Американский математический ежемесячник . 62 (9): 627–631. DOI : 10.2307 / 2307285 . hdl : 10338.dmlcz / 142789 . JSTOR 2307285 .
- ^ Маккласки-младший, Эдвард Джозеф (ноябрь 1956 г.). «Минимизация булевых функций» . Технический журнал Bell System . 35 (6): 1417–1444. DOI : 10.1002 / j.1538-7305.1956.tb03835.x . hdl : 10338.dmlcz / 102933 . Проверено 24 августа 2014 .
- ^ Макколл, Хью (1878-11-14). "Исчисление эквивалентных утверждений (Третья статья)" . Труды Лондонского математического общества . s1-10 (1): 16–28. DOI : 10.1112 / ПНИЛИ / s1-10.1.16 .
- ^ Лэдд, Кристина (1883). «Об алгебре логики». В Пирсе, Чарльз Сандерс (ред.). Исследования по логике . Бостон, США: Little, Brown & Company . С. 17–71. п. 23:
[...] Если приведение [выражения к простейшей форме] неочевидно, это можно облегчить, взяв отрицательное значение выражения, уменьшив его, а затем вернув его в положительную форму. [...]
- ^ а б в г д Браун, Фрэнк Маркхэм (ноябрь 2010 г.) [2010-10-27]. «Макколл и минимизация» . История и философия логики . Тейлор и Фрэнсис . 31 (4): 337–348. DOI : 10.1080 / 01445340.2010.517387 . ISSN 1464-5149 . Архивировано 15 апреля 2020 года . Проверено 15 апреля 2020 .
- ^ а б Блейк, Арчи (1938) [1937]. Канонические выражения в булевой алгебре (Диссертация) (Lithographed ed.). Чикаго, Иллинойс, США: Библиотеки Чикагского университета . п. 36. с. 36:
[...] этот метод был известен Пирсу и его ученикам [...] Он упоминается в нескольких местах в «Исследованиях по логике» членами Университета Джона Хопкинса , 1883 г. [...]
(ii + 60 страниц) - ^ Блейк, Арчи (ноябрь 1932 г.). «Канонические выражения в булевой алгебре». Бюллетень Американского математического общества . Тезисов докладов: 805.
- ^ Блейк, Арчи (июнь 1938). «Поправки к каноническим выражениям в булевой алгебре » . Журнал символической логики . Ассоциация символической логики . 3 (2): 112–113. DOI : 10.2307 / 2267595 . ISSN 0022-4812 . JSTOR 2267595 .
- ^ Самсон, Эдвард Уолтер; Миллс, Бертон Э. (апрель 1954 г.). Минимизация схем: алгебра и алгоритмы для новых булевых канонических выражений . Бедфорд, Массачусетс, США: Кембриджский исследовательский центр ВВС США . Технический отчет AFCRC TR 54-21.
- ^ Нельсон, Раймонд Дж. (Июнь 1955 г.). «Простейшие функции нормальной истины». Журнал символической логики . Ассоциация символической логики . 20 (2): 105–108. DOI : 10.2307 / 2266893 . JSTOR 2266893 . (4 страницы)
- ^ «Добро пожаловать на страницу памяти Джона« Джека »Дж. Нордала, 14 июня 1933 г. ~ 20 ноября 2017 г. (возраст 84 года)» . Похоронное бюро Джеллисона и услуги кремации. Архивировано 05 мая 2020 года . Проверено 5 мая 2020 .
- ^ Маллин, Альберт Алкинс ; Келлнер, Уэйн Г. (1958). Написано в Университете Иллинойса, Урбана, США, и на факультете электротехники Массачусетского технологического института , Массачусетс, США. «Проверка остатка для булевых функций» (PDF) . Труды Академии наук штата Иллинойс (Учебный меморандум). Спрингфилд, Иллинойс, США. 51 (3–4): 14–19. S2CID 125171479 . Архивировано (PDF) из оригинала 05.05.2020 . Проверено 5 мая 2020 . [1] (6 страниц) (NB. В своей книге Колдуэлл датирует это ноябрем 1955 года как учебный меморандум. Поскольку Маллин датирует их работу 1958 годом в другой работе, а меморандум Абрахамса / Нордала также датирован ноябрем 1955 года, это могло ошибка копирования.)
- ^ а б Колдуэлл, Сэмюэл Хоукс (1958-12-01) [февраль 1958]. «5.8. Операции с использованием десятичных символов». Написано в Уотертауне, Массачусетс, США. Коммутационные схемы и логическая конструкция . 5 сентября 1963 г. (1-е изд.). Нью-Йорк, США: John Wiley & Sons Inc., стр. 162–169. ISBN 0-47112969-0. LCCN 58-7896 . п. 166:
[...] Приятно отметить, что это лечение основано на работе двух студентов, которые изучали схемы переключения в Массачусетском технологическом институте. Они обсудили метод независимо, а затем вместе подготовили меморандум класса: П. У. Абрахам и Дж. Г. Нордаль [...]
(xviii + 686 страниц) (NB. Что касается первого основного трактата о десятичном методе в этой книге, его иногда ошибочно называют «десятичной таблицей Колдвелла».) - ^ а б Маллин, Альберт Алкинс (1960-03-15) [1959-09-19]. Написано в Университете Иллинойса, Урбана, США. Фишер, Харви I .; Экбло, Джордж Э .; Зеленый, ФО; Джонс, Рис; Круиденье, Фрэнсис; МакГрегор, Джон; Сильва, Пол; Томпсон, Милтон (ред.). "Два приложения элементарной теории чисел" (PDF) . Труды Академии наук штата Иллинойс . Спрингфилд, Иллинойс, США. 52 (3–4): 102–103. Архивировано (PDF) из оригинала 05.05.2020 . Проверено 5 мая 2020 . [2] [3] [4] (2 страницы)
- ^ а б Маккласки-младший, Эдвард Джозеф (июнь 1960 г.). «Альберт А. Муллин и Уэйн Г. Келлнер. Проверка вычетов для булевых функций. Труды Академии наук штата Иллинойс, том 51, номера 3 и 4, (1958), стр. 14–19». Журнал символической логики (Обзор). 25 (2): 185. DOI : 10,2307 / 2964263 . JSTOR 2964263 . п. 185:
[...] Результаты этой статьи представлены в более доступной книге С.Х. Колдуэлла [...]. В этой книге автор отдает должное Маллину и Келлнеру за разработку манипуляций с десятичными числами.
(1 стр.) - ^ Абрахамс, Пол Уильям; Нордаль, Джон «Джек» Г. (ноябрь 1955 г.). Модифицированная процедура редукции Куайна – Маккласки (меморандум класса). Отдел электротехники, Массачусетский технологический институт , Массачусетс, США.(4 страницы) (NB. В некоторых источниках авторы называют « PW Abraham » и « IG Nordahl », название также цитируется как « Модифицированная процедура сокращения Маккласки – Куайна ».)
- ^ Филдер, Дэниел К. (декабрь 1966 г.). "Классная редукция булевых функций". IEEE Transactions по образованию . IEEE . 9 (4): 202–205. Bibcode : 1966ITEdu ... 9..202F . DOI : 10.1109 / TE.1966.4321989 . eISSN 1557-9638 . ISSN 0018-9359 .
- ^ Каммерер, Вильгельм (май 1969). "I.12. Теория: минимальные логические функции". Написано в Йене, Германия. Во Фрюхафе, Ганс ; Каммерер, Вильгельм; Шредер, Курц; Винклер, Гельмут (ред.). Digitale Automaten - Theorie, Struktur, Technik, Programmieren . Elektronisches Rechnen und Regeln (на немецком языке). 5 (1-е изд.). Берлин, Германия: Akademie-Verlag GmbH . С. 98, 103–104. Номер лицензии. 202-100 / 416/69. № заказа. 4666 ES 20 K 3. с. 98:
[...] 1955 wurde das Verfahren auf die bequemere dezimale Schreibweise umgestellt ( PW Abraham und IG Nordahl в [ Caldwell ]). [...]
(NB. Существует также второе издание 1973 г.) - ^ Холдсворт, Брайан; Вудс, Клайв (2002). «3.17 Десятичный подход к упрощению Куайна – Маккласки булевой алгебры» . Цифровой логический дизайн (4-е изд.). Newnes Books / Elsevier Science . С. 65–67. ISBN 0-7506-4588-2. Проверено 19 апреля 2020 .CS1 maint: игнорируются ошибки ISBN ( ссылка )(519 страниц) [5]
- ^ Маджумдер, Алак; Чоудхури, Барнали; Мондал, Абир Дж .; Джайн, Кундж (30.01.2015) [09.01.2015]. Исследование метода Куайна МакКласки: новый подход, основанный на десятичной манипуляции, для минимизации булевой функции . Международная конференция по электронному проектированию, компьютерным сетям и автоматизированной проверке (EDCAV), 2015 г., Шиллонг, Индия (доклад конференции). Департамент электроники и связи, Технический национальный технологический институт, Аруначал-Прадеш, Юпия, Индия. С. 18–22. DOI : 10.1109 / EDCAV.2015.7060531 . Архивировано 08 мая 2020 года . Проверено 8 мая 2020 . [6] (NB. Эта работа не ссылается на предшествующий уровень техники по десятичным методам.) (5 страниц)
- ^ Масек, Уильям Дж. (1979). Некоторая NP-комплектация, покрывающая проблемы . не опубликовано.
- ^ Чорт, Себастьян Лукас Арне (1999). Сложность минимизации дизъюнктивных нормальных формул (магистерская диссертация). Орхусский университет.
- ^ Уманс, Кристофер ; Вилла, Тициано; Санжиованни-Винчентелли, Альберто Луиджи (05.06.2006). «Сложность минимизации двухуровневой логики». IEEE Transactions по автоматизированному проектированию интегральных схем и систем . 25 (7): 1230–1246. DOI : 10,1109 / TCAD.2005.855944 . S2CID 10187481 .
- ^ Нельсон, Виктор П .; Нэгл, Х. Трой; Кэрролл, Билл Д .; Ирвин, Дж. Дэвид (1995). Анализ и проектирование цифровых логических схем (2-е изд.). Прентис Холл . п. 234. ISBN 978-0-13463894-2. Проверено 26 августа 2014 .
- ^ Фельдман, Виталий (2009). «Трудность приближенной двухуровневой минимизации логики и обучения PAC с запросами членства». Журнал компьютерных и системных наук . 75 : 13–25 [13–14]. DOI : 10.1016 / j.jcss.2008.07.007 .
- ^ Гимпель, Джеймс Ф. (1965). «Метод создания булевой функции, имеющей произвольно заданную простую импликантную таблицу». Транзакции IEEE на компьютерах . 14 : 485–488. DOI : 10,1109 / PGEC.1965.264175 .
- ^ Пол, Вольфганг Якоб (1974). "Boolesche Minimalpolynome und Überdeckungsprobleme". Acta Informatica (на немецком языке). 4 (4): 321–336. DOI : 10.1007 / BF00289615 . S2CID 35973949 .
- ^ Программа Logic Friday
дальнейшее чтение
- Кертис, Герберт Аллен (1962). «Глава 2.3. Метод Маккласки». Новый подход к проектированию коммутационных схем . Серия Bell Laboratories (1 - е изд.). Принстон, Нью-Джерси, США: D. van Nostrand Company, Inc., стр. 90–160. ISBN 0-44201794-4. OCLC 1036797958 . S2CID 57068910 . ISBN 978-0-44201794-1 . ковчег: / 13960 / t56d6st0q. (viii + 635 страниц) (NB. Эта книга была перепечатана Чин Джи в 1969 году.)
- Кудерт, Оливье (октябрь 1994). «Минимизация двухуровневой логики: обзор» (PDF) . Интеграция, Журнал СБИС . 17–2 (2): 97–140. DOI : 10.1016 / 0167-9260 (94) 00007-7 . ISSN 0167-9260 . Архивировано (PDF) из оригинала на 2020-05-10 . Проверено 10 мая 2020 . (47 страниц)
- Джадхав, Виттал; Бухад, Амар (2012-03-08). «Модифицированный метод Куайна-Маккласки». arXiv : 1203,2289 [ cs.OH ]. (4 страницы)
- Креншоу, Джек (2004-08-19). «Все о Куайне-МакКласки» . embedded.com . Архивировано 10 мая 2020 года . Проверено 10 мая 2020 .
- Томашевский, Себастьян П .; Челик, Ильгаз У .; Антониу, Джордж Э. (декабрь 2003 г.) [2003-03-05, 2002-04-09]. «Минимизация логических функций на основе WWW» (PDF) . Международный журнал прикладной математики и информатики . 13 (4): 577–584. Архивировано (PDF) из оригинала на 2020-05-10 . Проверено 10 мая 2020 . [7] [8] (7 страниц)
- Душа, Адриан (2008-10-01) [сентябрь 2007]. «Математический подход к задаче логической минимизации». Качество и количество . 44 : 99–113. DOI : 10.1007 / s11135-008-9183-х . S2CID 123042755 . Номер статьи: 99 (2010). [9] (22 страницы)
- Душа, Адриан (2007). «Улучшение Куайна-МакКласки» (PDF) . Бухарестский университет . Архивации (PDF) с оригинала на 2020-05-12 . Проверено 12 мая 2020 .(16 страниц) (NB. QCA , реализация на основе R с открытым исходным кодом, используемая в социальных науках.)
Внешние ссылки
- Реализация алгоритма Куайна-Маккласки с поиском всех решений , автор Фредерик Карпон.
- Karċma 3 , набор инструментов логического синтеза, включая карты Карно, минимизацию Куайна-Маккласки, BDD, вероятности, обучающий модуль и многое другое. Лаборатория синтеза логических схем (LogiCS) - UFRGS , Бразилия.
- BFunc , упрощители логической логики на основе QMC, поддерживающие до 64 входов / 64 выходов (независимо) или 32 выхода (одновременно), Антонио Коста
- Реализация Python Робертом Диком с оптимизированной версией .
- Реализация Python для символического сокращения логических выражений.
- Quinessence , реализация с открытым исходным кодом, написанная на Free Pascal Марко Каминати.
- minBool - реализация Андрея Попова.
- QMC applet , апплет для пошагового анализа алгоритма QMC от Кристиана Рота.
- Реализация на C ++ SourceForge.net Программа на C ++, реализующая алгоритм.
- Модуль Perl от Даррена М. Кулпа.
- Учебное пособие Учебное пособие по методу Куайна-МакКласки и Петрика.
- Реализация Petrick C ++ (включая Petrick) на основе приведенного выше руководства.
- Программа C Консоль Public Domain на основе C программы на SourceForge.net.
- Чтобы увидеть полностью проработанный пример, посетите: http://www.cs.ualberta.ca/~amaral/courses/329/webslides/Topic5-QuineMcCluskey/sld024.htm
- Логический бот: реализация JavaScript для Интернета: http://booleanbot.com/
- графический интерфейс с открытым исходным кодом QMC Minimizer
- Коды компьютерного моделирования для метода Куайна-Маккласки , автор Sourangsu Banerji.