Алгоритм Куайна – Маккласки

Диаграмма Хассе графа поиска алгоритма для 3 переменных. Учитывая, например, подмножество $S=\{abc,a{\overline {b}}c,{\overline {a}}bc,{\overline {a}}b{\overline {c}},{\overline {a}}{\overline {b}}c\}$ из узлов нижнего уровня (светло-зеленый) алгоритм вычисляет минимальный набор узлов (здесь: $\{{\overline {a}}b,c\}$, темно-зеленый), который покрывает ровно $S$.

Алгоритм Куайна-МакКласки ( QMC ), также известный как метод простых импликант , представляет собой метод, используемый для минимизации булевых функций , который был разработан Уиллардом В. Куайном в 1952 году. и расширен Эдвардом Дж. Маккласки в 1956 году. В качестве общего принципа этот подход уже был продемонстрирован логиком Хью Макколлом в 1878 году: было доказано Арчи Блейком в 1937 году. и был заново открыт Эдвардом В. Самсоном и Бертоном Э. Миллсом в 1954 году. и Раймонд Дж. Нельсон в 1955 году. Также в 1955 году Пол В. Абрахамс и Джон Г. Нордаль а также Альберт А. Маллин и Уэйн Г. Келлнер предложил десятичный вариант метода.

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

Алгоритм Куайна-МакКласки работает следующим образом:

1. Нахождение всех простых импликант функции.
2. Используйте эти основные импликанты в таблице простых импликантов, чтобы найти основные основные импликанты функции, а также другие основные импликанты, необходимые для покрытия функции.

Сложность

Хотя алгоритм Куайна – МакКласки более практичен, чем отображение Карно , при работе с более чем четырьмя переменными, он также имеет ограниченный диапазон использования, поскольку проблема, которую он решает, является NP-полной . Время работы алгоритма Куайна – МакКласки растет экспоненциально с увеличением количества переменных. Для функции n переменных число простых импликант может достигать $3^{n}/{\sqrt {n}}$ , например, для 32 переменных может быть более 534 × 10 ¹² основные импликанты. Функции с большим количеством переменных приходится минимизировать с помощью потенциально неоптимальных эвристических методов, из которых эвристический логический минимайзер Espresso был фактическим стандартом в 1995 году. Для одного естественного класса функций $f$, то точная сложность поиска всех простых импликантов стала лучше понятна: Милан Моссе, Гарри Ша и Ли-Янг Тан открыли почти оптимальный алгоритм для поиска всех простых импликантов формулы в конъюнктивной нормальной форме .

Второй шаг алгоритма сводится к решению задачи покрытия множества ; На этом этапе алгоритма могут возникнуть NP-сложные случаи этой проблемы.

Пример

Вход

В этом примере входными данными является булева функция с четырьмя переменными: $f:\{0,1\}^{4}\to \{0,1\}$ который оценивается как $1$ о ценностях $4,8,10,11,12$ и $15$, оценивается как неизвестное значение на $9$ и $14$, и чтобы $0$ везде (где эти целые числа интерпретируются в двоичной форме для ввода в $f$ для краткости обозначений). Входные данные, которые оцениваются как $1$ называются минтермсами. Мы кодируем всю эту информацию, записывая

$f(A,B,C,D)=\sum m(4,8,10,11,12,15)+d(9,14).\,$

Это выражение говорит, что выходная функция f будет равна 1 для минтермов. $4,8,10,11,12$ и $15$ (обозначается термином «m») и что нас не волнует результат $9$ и $14$ комбинации (обозначаются термином «d»). Символ суммирования $\sum$ обозначает логическую сумму (логическое ИЛИ или дизъюнкция) всех суммируемых членов.

Шаг 1: поиск основных импликантов

Сначала мы запишем функцию в виде таблицы (где «x» означает «неважно»):

	А	Б	С	Д	ж
м0	0	0	0	0	0
м1	0	0	0	1	0
м2	0	0	1	0	0
m3	0	0	1	1	0
м4	0	1	0	0	1
м5	0	1	0	1	0
м6	0	1	1	0	0
м7	0	1	1	1	0
м8	1	0	0	0	1
м9	1	0	0	1	х
м10	1	0	1	0	1
м11	1	0	1	1	1
м12	1	1	0	0	1
м13	1	1	0	1	0
м14	1	1	1	0	х
м15	1	1	1	1	1

Из этой таблицы можно легко сформировать выражение канонической суммы произведений , просто суммируя минтермы (опуская ненужные термины ), где функция оценивается как единица:

f _A,B,C,D = A'BC'D' + AB'C'D' + AB'CD' + AB'CD + ABC'D' + ABCD.

что не является минимальным. Поэтому в целях оптимизации все минтермы, имеющие единицу, сначала помещаются в таблицу минтермов. В эту таблицу также добавлены ненужные термины (имена в скобках), поэтому их можно комбинировать с минтермами:

Число из 1 с	Минтерм	Двоичный Представительство
1	м4	0100
	м8	1000
2	(м9)	1001
	м10	1010
	м12	1100
3	м11	1011
	(м14)	1110
4	м15	1111

На этом этапе можно начинать комбинировать минтермы с другими минтермами в соседних группах. Если два термина отличаются только одной цифрой, эту цифру можно заменить тире, указывающим, что цифра не имеет значения. Термины, которые больше нельзя комбинировать, отмечены звездочкой ( * ). Например 1000 и 1001 можно объединить, чтобы дать 100-, что указывает на то, что оба минтерма подразумевают, что первая цифра равна 1 и следующие два 0.

Число из 1 с	Минтерм	0-куб	Импликанты размера 2
1	м4	0100	м(4,12)	-100 *
	м8	1000	м(8,9)	100-
	—		м(8,10)	10-0
	—		м(8,12)	1-00
2	м9	1001	м(9,11)	10-1
	м10	1010	м(10,11)	101-
	—		м(10,14)	1-10
	м12	1100	м(12,14)	11-0
3	м11	1011	м(11,15)	1-11
	м14	1110	м(14,15)	111-
4	м15	1111	—

При переходе от размера 2 к размеру 4 обработайте - в качестве значения третьего бита. Сопоставьте -это первое. Термины представляют продукты, и для объединения двух терминов продукта они должны иметь одинаковые переменные. Одна из переменных должна быть дополнена в одном члене и не дополнена в другом. Остальные присутствующие переменные должны совпадать. Итак, чтобы сопоставить два термина, -должны совпадать, и все остальные цифры, кроме одной, должны быть одинаковыми. Например, -110 и -100 можно объединить, чтобы дать -1-0, как может -110 и -010 дать --10, но -110 и 011- не может, поскольку -не совпадают. -110 соответствует BCD', а 011- соответствует A'BC, а BCD' + A'BC не эквивалентно термину продукта.

Число из 1 с	Минтерм	0-куб	Импликанты размера 2		Импликанты размера 4
1	м4	0100	м(4,12)	-100 *	—
	м8	1000	м(8,9)	100-	м(8,9,10,11)	10-- *
	—		м(8,10)	10-0	м(8,10,12,14)	1--0 *
	—		м(8,12)	1-00	—
2	м9	1001	м(9,11)	10-1	—
	м10	1010	м(10,11)	101-	м(10,11,14,15)	1-1- *
	—		м(10,14)	1-10	—
	м12	1100	м(12,14)	11-0	—
3	м11	1011	м(11,15)	1-11	—
	м14	1110	м(14,15)	111-	—
4	м15	1111	—		—

Примечание. В этом примере ни один из терминов в таблице импликантов размера 4 не может быть объединен в дальнейшем. В общем, этот процесс следует продолжать (размеры 8, 16 и т. д.) до тех пор, пока не перестанут комбинироваться термины.

Шаг 2: основная импликантная диаграмма

Ни один из терминов не может быть объединен дальше этого, поэтому на этом этапе мы создаем необходимую таблицу простых импликант. Сбоку идут только что сгенерированные основные импликанты (это те, которые отмечены знаком «). * " на предыдущем шаге), а сверху идут минтермы, указанные ранее. Неважные термины не размещаются сверху — они опущены в этом разделе, поскольку не являются обязательными входными данными.

	4	8	10	11	12	15	⇒	А	Б	С	Д
м(4,12) #							⇒	—	1	0	0
м(8,9,10,11)							⇒	1	0	—	—
м(8,10,12,14)							⇒	1	—	—	0
м(10,11,14,15) #							⇒	1	—	1	—

Чтобы найти основные основные импликанты, мы ищем столбцы только с одним «✓». Если в столбце есть только один символ «✓», это означает, что минтерм может быть покрыт только одним основным импликантом. Этот главный импликант очень важен .

Например: в первом столбце с минтермом 4 стоит только один «✓». Это означает, что m(4,12) существенно (поэтому отмечено ^# ). В Minterm 15 также есть только один «✓», поэтому m(10,11,14,15) тоже важно. Теперь все столбцы с одним "✓" закрыты. Строки с минтермами m(4,12) и m(10,11,14,15) теперь можно удалить вместе со всеми столбцами, которые они покрывают.

Вторая основная импликанта может быть «покрыта» третьей и четвертой, а третья основная импликанта может быть «покрыта» второй и первой, и, таким образом, ни одна из них не является существенной. Если основная импликанта существенна, то, как и следовало ожидать, ее необходимо включить в минимизированное логическое уравнение. В некоторых случаях основные основные импликанты не охватывают все минтермы, и в этом случае могут быть использованы дополнительные процедуры сокращения диаграммы. Самая простая «дополнительная процедура» — метод проб и ошибок, но более систематический способ — метод Петрика . В текущем примере существенные основные импликанты не обрабатывают все минтермы, поэтому в этом случае существенные импликанты можно объединить с одним из двух несущественных, чтобы получить одно уравнение:

f _A,B,C,D = BC'D' + AB' + AC

или

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.

Алгоритм

Шаг 1: Нахождение главных импликантов

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

// Computes the prime implicants from a list of minterms. 
// each minterm is of the form "1001", "1010", etc. 
function getPrimeImplicants(list minterms) is 
    primeImplicants ← empty list
    merges ← new boolean array of length equal to the number of minterms, each set to false
    numberOfmerges ← 0 
    mergedMinterm, minterm1, minterm2 ← empty strings 

    for i = 0 to length(minterms) do
        for c = i + 1 to length(minterms) do
            minterm1 ← minterms[i]
            minterm2 ← minterms[c]
            // Checking that two minterms can be merged
            if CheckDashesAlign(minterm1, minterm2) && CheckMintermDifference(minterm1, minterm2) then
                mergedMinterm ← MergeMinterms(minterm1, minterm2) 
                primeImplicants.Add(mergedMinterm) 
                numberOfMerges ← numberOfMerges + 1
                merges[i] ← true
                merges[c] ← true

    // Filtering all minterms that have not been merged as they are prime implicants. Also removing duplicates
    for j = 0 to length(minterms) do
        if merges[j] == false && primeImplicants Contains minterms[j] then
            add minterms[j] to primeImplicants

    // if no merges have taken place then all of the prime implicants have been found so return, otherwise 
    // keep merging the minterms. 
    if numberOfmerges == 0 then
        return primeImplicants
    else 
        return getPrimeImplicants(primeImplicants)

В этом примере CheckDashesAlign и CheckMintermDifference Функции выполняют необходимые проверки для определения возможности объединения двух минтермов. Функция MergeMinterms объединяет минтермы и добавляет тире там, где это необходимо.

function MergeMinterms(minterm1, minterm2) is
    mergedMinterm ← empty string
    for i = 0 to length(minterm1) do 
        //If the bits vary then replace it with a dash, otherwise the bit remains in the merged minterm.
        if minterm[i] != minterm2[i] then
            mergedMinterm ← mergedMinterm + '-'
        else
            mergedMinterm ← mergedMinter + minterm1[i] 
    return mergedMinterm

function CheckDashesAlign(minterm1, minterm2) is
    for i = 0 to length(minterm1) do 
        // If one minterm has dashes and the other does not then the minterms cannot be merged. 
        if minterm1[i] != '-' && minterm2[i] == '-' then
            return false 
    return true

function CheckMintermDifference(minterm1, minterm2) is 
    // minterm1 and minterm2 are strings representing all of the currently found prime implicants and merged 
    // minterms. Examples include '01--' and '10-0'
    m1, m2 ← integer representation of minterm1 and minterm2 with the dashes removed, these are replaced with 0
    res ← m1 ^ m2
    return res != 0 && (res & res - 1) == 0

Шаг 2: Основная импликантная диаграмма

Приведенный ниже псевдокод можно разделить на две части:

1. Создание диаграммы основных импликант с использованием основных импликант
2. Чтение таблицы основных импликантов, чтобы найти основные основные импликанты.

Создание основной импликантной карты

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

1. Переберите каждый ключ (основной импликант словаря).
2. Замените каждое тире в главном импликанте на \d код символа. При этом создается регулярное выражение, которое можно проверять по каждому минтерму в поисках совпадений.
3. Перебрать каждый минтерм, сравнивая регулярное выражение с двоичным представлением минтерма. Если есть совпадение, добавьте "1" к соответствующей строке в словаре. В противном случае добавьте "0".
4. Повторите эти действия для всех основных импликантов, чтобы создать завершенную диаграмму основных импликантов.

При написании в псевдокоде описанный выше алгоритм выглядит следующим образом:

function CreatePrimeImplicantChart(list primeImplicants, list minterms) 
    primeImplicantChart ← new dictionary with key of type string and value of type string
    // Creating the empty chart with the prime implicants as the key and empty strings as the value. 
    for i = 0 to length(primeImplicants) do
        // Adding a new prime implicant to the chart. 
        primeImplicantChart.Add(primeImplicants[i], "")
    
    for i = 0 to length(primeImplicantChart.Keys) do
        primeImplicant ← primeImplicantChart.Keys[i]
        // Convert the "-" to "\d" which can be used to find the row of ticks above.
        regularExpression ← ConvertToRegularExpression(primeImplicant)
        for j = 0 to length(minterms) do
            // If there is a match between the regular expression and the minterm than append a 1 otherwise 0. 
            if regularExpression.matches(primeImplicant) then
                primeImplicantChart[primeImplicant] += "1"
            else 
                primeImplicantChart[primeImplicant] += "0"

    // The prime implicant chart is complete so return the completed chart. 
    return primeImplicantChart

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

function ConvertToRegularExpression(string primeImplicant)
    regularExpression ← new string 
    for i = 0 to length(primeImplicant) do
        if primeImplicant[i] == "-" then
            // Add the literal character "\d". 
            regularExpression += @"\d"; 
    return regularExpression

Нахождение основных основных импликантов

Используя функцию, CreatePrimeImplicantChart, определенный выше, мы можем найти основные простые импликанты, просто перебирая столбец за столбцом значений в словаре, и где один "1" найдено, то найдена существенная основная импликанта.

См. также

• Каноническая форма Блейка
• Алгоритм Бухбергера - аналог алгоритма алгебраической геометрии.
• метод Петрика
• Качественный сравнительный анализ (QCA)

Дальнейшее чтение

• Кертис, Герберт Аллен (1962). «Глава 2.3. Метод МакКласки». Новый подход к проектированию коммутационных схем . Серия Bell Laboratories (1-е изд.). Принстон, Нью-Джерси, США: D. van Nostand Company, Inc., стр. 90–160. ISBN  0-44201794-4 . OCLC   1036797958 . S2CID   57068910 . ISBN   978-0-44201794-1 . ковчег:/13960/t56d6st0q. (viii+635 страниц) (Примечание: эта книга была переиздана Чин Джи в 1969 году.)
• Кудер, Оливье (октябрь 1994 г.). «Двухуровневая логическая минимизация: обзор» (PDF) . Интеграция, Журнал СБИС . 17–2 (2): 97–140. дои : 10.1016/0167-9260(94)00007-7 . ISSN   0167-9260 . Архивировано (PDF) из оригинала 10 мая 2020 г. Проверено 10 мая 2020 г. (47 страниц)
• Джадхав, Виттал; Бучаде, Амар (8 марта 2012 г.). «Модифицированный метод Куайна-Маккласки». arXiv : 1203.2289 [ cs.OH ]. (4 страницы)
• Креншоу, Джек (19 августа 2004 г.). «Все о Куайне-Маккласки» . Embedded.com . Архивировано из оригинала 10 мая 2020 г. Проверено 10 мая 2020 г.
• Томашевский, Себастьян П.; Челик, Ильгаз У.; Антониу, Джордж Э. (декабрь 2003 г.) [05 марта 2003 г., 9 апреля 2002 г.]. «Минимизация логических функций на основе WWW» (PDF) . Международный журнал прикладной математики и информатики . 13 (4): 577–584. Архивировано (PDF) из оригинала 10 мая 2020 г. Проверено 10 мая 2020 г. [7] [8] (7 страниц)
• Душа, Адриан (01 октября 2008 г.) [сентябрь 2007 г.]. «Математический подход к задаче булевой минимизации». Качество и количество . 44 : 99–113. дои : 10.1007/s11135-008-9183-x . S2CID   123042755 . Номер статьи: 99 (2010). [9] (22 страницы)
• Душа, Адриан (2007). «Усиление Куайна-Маккласки» (PDF) . Университет Бухареста . Архивировано (PDF) из оригинала 12 мая 2020 г. Проверено 12 мая 2020 г. (16 страниц) (Примечание.

Внешние ссылки

• Учебное пособие по методу Куайна-Маккласки и Петрика.
• Полностью проработанный пример можно найти по адресу: http://www.cs.ualberta.ca/~amaral/courses/329/webslides/Topic5-QuineMcCluskey/sld024.htm.