Еще раз о минимизации булевых функций

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



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

    Итак, в примере из предыдущей статьи, можно найти ядро функции для следующей симметричной карты:

    image

    Оно равно:

    !X1*X5 V X2*X3*X4 V X1*!X2*!X5

    Можно найти, что единица в строке с индексом 0 и столбце с индексом 4 может быть покрыта двумя способами:

    !X1*X3*!X4 (1)
    X3*!X4*!X5 (2)

    Аналогично, единица в строке с индексом 10 и столбце с индексом 4 может быть покрыта четыремя способами:

    !X1*X3*!X4 (1)
    X3*!X4*!X5 (2)
    !X1*X2*X3 (3)
    X2*X3*!X5 (4)

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

    Далее, единица в строке с индексом 30 и столбце с индексом 4 может быть покрыта тремя способами:

    X3*!X4*!X5 (2)
    X1*X3*!X5 (5)
    X2*X3*!X5 (4)

    И единица в строке с индексом 20 и столбце с индексом 1 может быть покрыта двумя способами:

    X1*!X2*!X3*!X4 (6)
    !X2*!X3*!X4*X5 (7)

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

    (1 V 2)(1 V 2 V 3 V 4)(2 V 5 V 4)(6 V 7)

    Раскроем первые две скобки:

    (1*1 V 1*2 V 1*3 V 1*4 V 2*1 V 2*2 V 2*3 V 2*4)(2 V 5 V 4)(6 V 7)

    Поскольку импликанта, будучи умноженная сама на себя дает ту же импликанту, первую скобку можно переписать в следующем виде:

    (1 V 1*2 V 1*3 V 1*4 V 2*1 V 2 V 2*3 V 2*4)(2 V 5 V 4)(6 V 7)

    Далее, поскольку вариант с одной импликантой дает лучшее решение, чем с двумя, можно переписать решение в виде:

    (1 V 2)(2 V 5 V 4)(6 V 7)

    Раскрывая скобки далее и используя подобные сокращения, получаем окончательное решение, которое уже нельзя сократить:

    2(6 V 7)

    Первый множитель 2 — единственная импликанта в группе и должна быть довавлена в ядро функции (так называемое расширенное ядро функции):

    X3*!X4*!X5

    А скобка дает два варианта:

    X1*!X2*!X3*!X4

    и

    !X2*!X3*!X4*X5

    Можно выбрать любой из них.

    Естественно, возникает вопрос про автоматизацию данного алгоритма. Для этого мной была написана программа apssymmap, которую можно найти на моем сайте:

    http://andyplekhanov.narod.ru/soft/soft.htm

    Представляет интерес сравнить результаты применения данного метода с другими известными методами. Сравним результаты работы программы apssymmap с известной программой espresso на примере, представленном ниже:

    image

    Результат работы программы espresso:

    espresso -Dexact -oeqntott test.txt

    image

    Результат работы программа apssymmap:

    image

    Видно, что программа apssymmap выдает 8 различных вариантов вместо одного у espresso. Однако, более интересным фактом является то, что результат espresso не является оптимальным. Если отбросить все общие части в этих решениях, можно увидеть, что у espresso останется две импликанты:

    !X7*!X5*!X4*X2*X1
    и
    X7*!X6*X5*X4*X3*X1

    содержащие соответственно 5 и 6 переменных, а в решении apssymmap будут импликанты

    !X5*X3*X2*X1
    и
    X7*!X6*X3*X2*X1

    содержащие 4 и 5 переменных, то есть на две меньше. В качестве вывода можно сделать заключение, что симметричные карты являются не только более удобным методом при ручной минимизации булевых функций, но и превосходят другие методы при решении этой задачи на компьютере.
    Поделиться публикацией
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама
    Комментарии 14
    • 0
      Может иметь смысл расширение матрицы с 2D на 3D. Или до размерности соответствующей количеству переменных.
      • 0
        Хм… А как тогда вручную минимизировать в 7-мерном пространстве?
        • 0
          С помощью срезов. Как крестики-нолики 3д на бумаге. Но такую задачу больше не нужно решать руками, у нас же есть специальные роботы!
          • 0
            А нужно ли её минимизировать вручную? В 2016м-то году?
            • 0
              Вопрос из серии — надо ли знать таблицу умножения, если полно калькуляторов?
        • 0
          Давно уже ищу способы решения такой задачки, может кто с хабра подскажет?
          Есть кейс: пару сотен булевых функций от примерно 5 сотен переменных. Задача: для заданного вектора результатов найти значения переменных или хотя бы упростить исходную систему для возможности полного перебора. Этакие булевые СЛАУ.
          • 0
            Это же типичная задача SAT, разве нет? Перегоняете все свои функции в КНФ форму, добавляете вспомогательные переменные, соответствующие выходам функций, задаете им соответствующие значения, затем запускаете SAT солвер, он вам и найдет какое-то решение, из которого можно будет достать входные значения.
            • 0
              Как сказал CaptainTrunky, Ваша задача легко укладывается в SAT. Но решение SAT вам позволит найти значения переменных. Что касается минимизации, то тут или аналитически или генерируя все возможные решения SAT задачи (ALL-SAT). Размер результата очень сильно зависит от КНФ, вплоть до невообразимых величин, тут важна информация о самой КНФ: встречаемость литералов в конъюнктах, отношение колиества переменных к количеству конъюнктов и т.п. Касательно ALL-SAT, могу дать пару соображений.
              • 0
                Спасибо, теперь хоть буду знать в какую сторону копать.
                До этого начал уже придумывать способы ухода в базис Жегалкина и дальше аналогично методу Гаусса в СЛАУ решать их (хотя проверял только на 3 переменных и трех уравнениях, так что на возможность такого решения для 100+ переменных не ручаюсь). Собственно размеры уравнений в базисе пугает (в пределе 2^n коньюнкций по (1;n) переменных), хоть и очень разряженная матрица получается, а ощущение неправильности способа решения не покидает и почти уже бросил затею, т.к. играюсь для себя.
                • 0
                  Можно еще попробовать навести оптимизацию при помощи булевых счетчиков. Задаем дополнительные ограничения на кол-во определенных литералов, после чего инкрементально увеличиваем счетчик от нуля до тех пор, пока не придем к SAT решению. Счетчики тоже могут получиться невообразимо большими, но что поделать. Как и tvi, могу помочь более детально.
                  • 0
                    Не понятен Ваш способ. Я правильно понимаю что Вы задаете ограничение на количество конъюнктов, в которых будет распространяться приписывание литерала? Но тогда где гарантия, что мы найдем все решения (ведь без них мы не получим минимизации)?
                    • 0
                      Прошу прощения, я изначально неправильно прочитал постановку задачи. Согласен, AllSAT выглядит самым разумным решением для данной задачи, вопрос только в форме КНФ и кол-ве возможных решений. Я сейчас занимаюсь чем-то похожим. :)
              • 0
                На практике в FPGA все равно булевы функции записываются в LUT (Look-Up Table), это такая ПЗУ-шка на N входов и в ней хранится битовая таблица 2^N.

                Минимизировать надо, если из К155ЛА3 собирать логику :)
                • 0
                  Но ведь логика не только в FPGA нужна. :)
                  Мы вот ее в вычислительную геометрию пихаем и нам ох как нужна минимизация.

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