Симметричные карты как средство минимизации булевых функций

    Памяти моего папы, Плеханова Станислава Петровича, посвящается.

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



    Метод минимизации булевых функций, существенно более эффективный, чем другие существующие методы, основан на использовании так называемых «симметричных карт» [1,2]. Почему карты называют симметричными, будет ясно из дальнейшего рассказа. Проиллюстрирую этот метод на примере.

    Пусть дана таблица истинности с пятью входными переменными, показанная на рис. 1.

    image

    Напомню, что значение "-" функции F означает «безразличное» состояние, которое говорит, что подобного набора входных переменных не возникает и значение функции может быть назначено нами произвольно нулем или единицей в процессе минимизации. Первое, что необходимо сделать, это пронумеровать входные наборы в восьмеричной системе (последний столбец на рисунке 1). После этого проводят заполнение самой симметричной карты. Симметричная карта для пяти переменных показана на рисунке 2.



    Как ее нарисовать будет показано далее, а сейчас я хочу обратить внимание на индексы столбцов, которые образуют последовательность 0, 1, 3, 2, 6, 7, 5, 4 и последовательность строк («десятков» в восьмеричной системе) — 0, 10, 30, 20.
    Заполнение такой таблицы происходит значительно проще, чем карты Карно. Для этого берут восемь значений из таблицы истинности и заносят их в соответствующую строку (индексы столбцов соответстуют номеру в восьмерке входного набора). После этого приступают собственно к минимизации булевой функции. Здесь используется свойство симметрии, которое и дает название этой карте.

    Минимизируем карту по единицам. Возьмем единицу в строке 0 и столбце с индексом «1». Проверяем все клетки «симметричные» данной единице. Сначала в «паре», то есть относительно вертикальной оси, проходящей между столбцами «0» и «1». Это будет клетка в строке 0 и индексом 0. Там находится значение «0», поэтому «склеивание» этих двух значений произвести нельзя. Проверяем симметрию в «четверке», то есть относительно вертикальной оси, проходящей между столбцами 1 и 3. Это клетка в строке 0 и индексом 3. Там стоит значение "-", значит, если принять его за «1», можно объединить («склеить») его с нашей единицей. Далее проверяется клетка 5 строки 0, соответствующая оси симметрии между столбцами 2 и 6 (она тоже может быть слеена с нашей единицей). Следующая симметрия в «шестнадцать» — это клетка в строке 10 и столбце 1 относительно горизонтальной оси между строками 0 и 10. И, наконец, симметрия в «тридцать два» — клетка в строке 20 и столбце 1 — с горизонтальной осью симметрии, проходящей между строками 10 и 30.
    Наша задача — найти максимально возможную фигуру, склеивая нашу единичку с другими, симметричными ей. Имеется единственная такая фигура, которая покрывает клетки (строка-столбец): 0-1, 0-3, 0-7, 0-5, 10-1, 10-3, 10-7, 10-5. Чтобы получить импликанту, соответствующую этому набору, необходимо просто найти переменные, которые описывают данную группу либо в прямом либо в инверсном виде. Возьмем переменную X1 (на рисунке 2 она обозначена вертикальной прямой справа, причем строки 0 и 10 — это толстая линия, соответствующая инверсному значению, а строки 30 и 20 — тонкая линия, соответствующая прямому значению). Вся наша группа единичек попадает в строки 0 и 10, следовательно, X1 входит в нашу импликанту в инверсном виде. Переменная X2, показанная также справа, не войдет в нашу импликанту, поскольку группа попадает как в инверсное (строка 0), так и в прямое значение этой переменной (строка 10). Аналогчно, в нашу импликанту не попадут переменные X3 и X4, показанные горизонтальными линиями внизу симметричной карты, а переменная X5 войдет, поскольку вся группа единиц описывается прямым значением переменной X5. Окончательно, наша группа единиц будет представлена как (not X1)*X5.
    Разобравшись с единицей в строке 0 и столбце 1, ищем оставшиеся единицы, не входящие в уже сформированные группы. Берем единицу в строке 0 и индексом 4 (последний столбец). Из нее можно получить две равновеликие группы, первая из которых содержит клетки в строках 0 и 10, индексы столбцов 5 и 4, а вторая — все клетки в последнем столбце. Группы будут соответствовать импликантам (not X1)*X3*(not X4) и X3*(not X4)*(not X5). Заметим, что если существует более одной возможности покрытия, то вариантов минимальной булевой функции также может быть более одного. Действуем так аналогично, до тех пор, пока все единицы не будут покрыты хотя-бы одной группой.

    Окончательно имеем минимальную дизъюнктивно нормальную форму в виде двух вариантов:



    Симметричные карты для другого количества переменных имеют аналогичный вид, который приведен на следующих рисунках.













    Отметим, что симметричные карты позволяют:

    1. Существенно ускорить и упростить заполнение по таблице истинности.
    2. В несколько раз увеличить число аргументов минимизируемой функции.
    3. Существенно упростить процесс минимизации благодаря свойству симметрии.

    1. Медведев С.С. Восьмеричные карты для минимизации булевых функций. Теория автоматов. Сб. статей, Институт кибернетики АН СССР, 1966, с. 45-49.
    2. Плеханов С.П. Симметричные карты — мощное средство минимизации булевых функций при проектировании цифровых устройств больших размерностей. — Электронная техника, Сер. 10, Микроэлектронные устройства. — 1991. Вып. 4(88), с. 27-29.
    Метки:
    Поделиться публикацией
    Похожие публикации
    Реклама помогает поддерживать и развивать наши сервисы

    Подробнее
    Реклама
    Комментарии 17
    • 0
      Я правильно понимаю, что это частное решение общей NP-сложной задачи построения минимальной комбинации булевых функций по таблице состояния?
      • 0
        Да, правильно. Только лучше сказать из таблицы истинности.
        • 0
          Это не совсем частное решение. Скорее, минимизация исходных данных для такой задачи.

          Вот когда оказывается, что по такой карте каждая из единиц может быть "покрыта" несколькими способами — и из них всех надо выбрать оптимальное покрытие — тогда-то NP-полная задача и вылезает.
        • +3
          Картинки в экселе можно сделать и скриншоты в статью добавить. Смотрелось бы симпатичнее.

          • +1
            Описанный метод интересен только с исторической точки зрения. Сначала использовали метод Куайна и его модификации, сейчас производные от опенсорсного Espresso. Позволяет искать как точное решение так и близкое к точному. Запросто работает с количеством входов от 16 и выше.
            • +1
              Ошибаетесь. Симметричные карты были созданы исторически после метода Куайна—Мак-Класки и превосходят его по эффективности. Чтобы в этом убедиться, необходимо просто решить приведенный пример вручную двумя этими методами. Что касается автоматизации, то симметричные карты легко алгоритмизуются в силу формальности правил и могут точно решать задачи на 16 и более переменных.
              • +1
                А можно вас попросить написать прототип для автоматизации предложенного решения и прогнать его через бенчмарк/другой? Было бы любопытно посмотреть, как конкретно влияет такая минимизация на конечный результат. Ну и да, если сегодня говорить о проблемах минимизации функций, то тут интерес представляют функции куда большей размерности, чем 16 (мое сообщение чуть ниже).

                PS
                Эх, доделать бы свою версию espresso, оптимизированную под совсем большие задачи...
              • 0
                Вопрос дилетанта: нужно минимизировать функцию 64 переменных, Espresso с такой задачей справится? Раньше такими задачами не занимался, а сейчас как раз возникла необходимость.
                • +1
                  Да, легко. Espresso сносно работает с функциями до 200 переменных, потом как повезет. Есть опыт использования на функциях как раз с 180+ переменными и несколькими десятками тысяч строк. В мои требования по рантайму (20-30 минут — это норма) вполне укладывается.
                  • 0
                    Спасибо! Есть еще вопрос по Espresso.
                    Имеется нетлист схемы (реализация функции в виде базисных элементов логики). Из этого нетлиста хотелось бы восстановить функцию. Можно написать скрипт, который выпишет в виде отдельных формул функции всех элементов, составляющих нетлист. В результате, искомая функция окажется суперпозицией функций элементов.
                    Вопрос: умеет ли Espresso работать с функцией, заданной в виде суперпозиции частичных функций? Т.е. если я загружу список из функций элементов, сможет ли Espresso эти частичные функции склеить в единую функцию, и затем минимизировать? Или же, Espresso работает по принципу — одна формула — одна функция?
                    • +1
                      Я не использовал espresso очень уж активно, исключительно как минимизатор и cnf-2-dnf, dnf-2-cnf транслятор. Если в нем и есть умный алгоритм работать с частичными функциями под опциями, то я не знаю. С другой стороны, ведь написать скрипт, который бы склеил набор нетлистов в один — это дело пары часов, разве нет? Пусть у нас есть большой нетлист, составленный из частичных функций. Каждому входу/выходу соответствует некая переменная в PLA (или BLIF, что там у вас). Теперь начинаем перечилсять известные нам "решения" для этого большого нетлиста (строки в PLA, они же конъюнкты). Неизвестные или несущественные значения переменных заполняем don't care (например, мы точно знаем, что вход одного нетлиста никак не влияет на вход другого). Все, получившийся большой файл можно запихивать в espresso. Если я что-то не так понял или криво объяснил, предлагаю перехать в личные сообщения. )
                  • +1
                    Справится в режиме эвристики точно (то есть найдет не 100% оптимальный результат, но крайне близкий к нему). Режим -exact как повезет.
                • +1
                  Мы это изучали на первом курсе под видом карт Карно.
                  • 0
                    Это не карты Карно ни под каким видом.
                  • +1
                    Мы тоже такое изучали, и я тоже запомнил это как карты Карно. Хотя я не могу гарантировать что нам так и сказали, потому как теоретическую выкладку, из-за манеры преподавателя вводить для упрощения какие-то примеры и анекдоты для разрядки, я плохо помню, запомнил больше по практике. Пожалуй надо почитать о обоих методах, того гляди и вспомню.

                    Но данный метод мне показался весьма удобным.
                    • 0
                      Вам надо было эту статью на Хабре разместить. Она идеально для него подходит.
                      • 0
                        ТМ конечно, изверги. Столько лет не могут прикрутить отображение LaTeXa. Читать формулы булевой алгебры в виде (not X1)*X3*(not X4), X3*(not X4)*(not X5) во втором часу ночи выше моих сил. Статья на редкость интересная, но честно, пока не осиливаю. Завтра попробую на свежую голову еще раз перечитать.

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