Быстрый алгоритм инвертирования логической суммы произведений

Я пытаюсь реализовать очень-очень быстрый механизм логических выражений. Я использую его для представления состояний в очень больших пространствах состояний, поэтому мне нужно, чтобы он обрабатывал как можно больше операций в секунду. В основе этой машины лежит сумма произведений. Однако я столкнулся с проблемой оптимизации оператора NOT. Например, если у меня есть сумма продуктов с N minterms, где каждый minterm имеет около M переменных, то попытка инвертировать это создаст M^N minterms, которые затем будут упрощены с помощью алгоритма эспрессо. Я могу немного ускорить его и сэкономить немного памяти, если буду периодически запускать алгоритм эспрессо во время обратной операции, но этого недостаточно. Сомневаюсь, что я первый, кто столкнулся с этой проблемой, и я пытался провести исследование, но не могу найти эффективный способ сделать это.

Может ли кто-нибудь указать мне в правильном направлении?


algorithm inverse boolean-logic
person Ned Bingham    schedule 06.07.2014    source источник
comment
В общем, вы не можете избежать экспоненциального взрыва.   -  person n. 1.8e9-where's-my-share m.    schedule 06.07.2014
comment
Нет, булевы выражения по своей природе экспоненциальны, но вы можете уменьшить их, чтобы минимизировать экспоненциальное увеличение. Из того, что я могу сказать, оператор not имеет много шаблонов, что наводит меня на мысль, что использование эспрессо было бы похоже на использование 2-тонного вольфрамового стержня, ускоренного из космоса, чтобы забить гвоздь.   -  person Ned Bingham    schedule 06.07.2014
comment
Нет, вы не можете всегда уменьшать его. Попробуйте (x1&y1)|(x2&y2)|...|(xn&yn). После отрицания это имеет длину 2^n.   -  person n. 1.8e9-where's-my-share m.    schedule 06.07.2014
comment
Если у вас есть n переменных, то есть 2^n записей в таблице истинности любой функции, которую вы пишете с этими n переменными. Я почти уверен, что если вы ограничите себя только выражением функции в форме суммы произведений, то всегда будет какое-то присвоение, которое форма суммы произведений обязательно должна иметь 2^n minterms. Однако что, если вы не ограничитесь формой суммы произведений? Возможно, это приведет к лучшей альтернативе.   -  person Apiwat Chantawibul    schedule 06.07.2014
comment
Да, это худший сценарий. Но как насчет среднего случая? В среднем, если у вас есть M переменных и N minterms, в конечном результате не будет M^N minterms, потому что многие minterms будут иметь общие переменные. Если вы можете эффективно использовать это во время операции, а не ждать до конца, ваш средний случай может не быть экспоненциальным.   -  person Ned Bingham    schedule 06.07.2014
comment
Я просмотрел несколько различных представлений, и представление суммы продуктов кажется наиболее эффективным представлением, которое я могу реализовать. Я могу втиснуть минтерм с 16 переменными в одно 32-битное целое число, и с небольшими битами большинство желаемых операций выполняются довольно быстро. BDD проблематичны, потому что они по своей сути рекурсивны, что медленно, и потому что их порядок имеет значение. Я мог бы каким-то образом использовать как сумму произведений, так и произведение сумм, но взаимодействие между ними становится очень сложным.   -  person Ned Bingham    schedule 06.07.2014
comment
Существует также возможность использования полностью иерархического представления (разрешить круглые скобки), и это смягчит экспоненциальный характер оператора not, а также добавит небольшое количество рекурсии, и неясно, насколько эффективным будет упрощение, но это скорее всего, в minterms будет только несколько переменных, что приводит к потере большого количества места впустую, учитывая мое текущее представление minterm.   -  person Ned Bingham    schedule 06.07.2014
comment
@Ned Если мы говорим о среднем случае случайного присвоения таблице истинности n переменных, то мы можем провести тщательный анализ этого. Но если говорить о среднем случае булевой функции на практике, то я не знаю. Итак, какое дело вы хотите исследовать?   -  person Apiwat Chantawibul    schedule 06.07.2014
comment
@Billiska Давайте просто выберем случайное задание. Его легче анализировать.   -  person Ned Bingham    schedule 06.07.2014
comment
Я думал о выполнении шага факторинга, прежде чем пытаться сделать обратное. Шаг факторизации не обязательно должен быть идеальным, он просто должен быть достаточно хорошим, чтобы уменьшить наибольшую экспоненту. есть идеи? embedded.eecs.berkeley.edu/eecsx44/fall2011/lectures/   -  person Ned Bingham    schedule 06.07.2014

Ответы (2)


arrow_upward
2
arrow_downward

Итак, прошло 5 лет с тех пор, как я опубликовал этот вопрос. Недавно заново открыв его, я понял, что совершил смертный грех. В какой-то момент между тем и сейчас я нашел довольно быстрый алгоритм, чтобы сделать это, и больше не возвращался, чтобы ответить на вопрос. Проблема в том, что я потерял всю связанную документацию. Блин... вот. Я обновлю этот ответ, если заново открою источник.

https://github.com/nbingham1/boolean/blob/a0f21eb1808dbcf86a3360ea85ab4eae15f5bf49/boolean/cover.cpp#L1055

РЕДАКТИРОВАТЬ: нашел источник

Минимизация многозначной логики для синтеза PLA, Ричард Л. Руделл, стр. 58.

https://apps.dtic.mil/dtic/tr/fulltext/u2/a606736.pdf

При этом используется обобщенное расширение Шеннона, рекурсивно дополняющее две стороны расширения и объединяющее дополнения с помощью упрощающей эвристики.

person Ned Bingham    schedule 20.05.2019

arrow_upward
0
arrow_downward

Вы можете сделать это в O(n+m), где

answer = ( x1 OR x2 OR .. xn ) AND ( y1 OR y2 OR .. ym )

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

answer = ( x1 OR x2 OR .. xn ) LOGICAL-AND ( y1 OR y2 OR .. ym )

Где LOGICAL-AND проверит, является ли текущее значение 0, вернет 0 в O(n+1).

Вы также можете изменить этот процесс на операцию установки

DEFINE X = { X1, X2, .. Xn }
DEFINE Y = { Y1, Y2, .. Ym }

ANSWER =  X ∈ 1  AND  Y ∈ 1

И оптимизируй так

IF X ∈ 1
THEN RETURN Y ∈ 1
ELSE RETURN 0

В среднем вы получаете Time = i + j где

i = position of left-most 1 in X
j = position of left-most 1 in Y

Худшие случаи, которые потребовали бы O(n+m)

000..001, 000..000

000..001, 000..001
person Khaled.K    schedule 19.01.2015
comment
Прошло четыре года с тех пор, как вы опубликовали это, но я только недавно вернулся к этому. Похоже, вы предлагаете мне сохранить перевернутый результат в конъюнктивной нормальной форме (CNF)? Предполагая, что этот оператор является частью некоторого более крупного алгоритма, сохранение результата в CNF просто переносит сложность на логические операторы, которые должны были бы связывать CNF и DNF. - person Ned Bingham; 20.05.2019