Как отобразить таблицу истинности на троичные логические функции?

Пожалуйста, будь добр. У меня острый и важный вопрос из другой области техники, ответ на который может быть довольно хорошо известен в электротехнике. Я задал похожий вопрос на StackOverflow

Предположим, у меня есть таблица истинности 5 входов и 1 выход. Я использовал алгоритм Espresso (например, Logic Friday), чтобы свернуть таблицу и написать эффективный VHDL. Все отлично работает

Вместо того, чтобы свести к минимуму и отобразить таблицу истинности для вентилей NAND, я хотел бы отобразить на произвольную троичную логическую функцию. Меня не интересует многозначная логика, а логические функции с 3 входными переменными. Есть 256 из этих функций, и 3-в NAND является лишь одной из них. Не все из этих 256 функций могут быть интересны: некоторые сводят к своим 2 братьям и сестрам входных переменных.

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

Предыстория: современные процессоры могут выполнять произвольные троичные логические операции над 512-битными регистрами (например, инструкция vpternlog ), но из-за сложности компиляторы оставляют это на усмотрение программиста, который в некоторой степени не знает, как это оптимизировать.

digital-logic logic-gates boolean-algebra HJLebbink
источник

Не существует даже формального способа «отобразить» произвольную двоичную функцию. И не каждая бинарная функция представляет собой законченную функциональную систему. То же самое верно для троичного.

Евгений Ш.

Я считаю, что это сложно для двоичных функций.

user110971

@ user110971 Я так не думаю .. Я думаю, что вы путаете с проблемой SAT.

Евгений Ш.

@EugeneSh. Я думаю, что проблема сводится к булевой минимизации, которая является NP трудной, потому что в противном случае вы могли бы решить проблему SAT. По крайней мере, это то, о чем я думаю, ФП спрашивает.

user110971

@ user110971 стандартные алгоритмы (которые я знаю) не сводится к произвольному тройной логические функциям (то есть вопрос). Они упрощаются до 3-дюймовых NAND и 3-дюймовых AND, но не всех других 3-дюймовых логических функций, которые позволили бы значительно более компактное сокращение.

HJLebbink

Ответы:

Анализ

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

е : Bool \times Bool \times Bool \to Bool,

$f : \text{Bool} \times \text{Bool} \times \text{Bool} \rightarrow \text{Bool},$ затем значение истинности может быть найдено для каждой комбинации входных значений и сохранено в таблице. Например, если

е (a, б, с) знак равно a & (! б | с),

$f(a,b,c) = a \& (!b | c),$ тогда

е (a, б, с) знак равно {КРАЧКА}_{10110000_{2}} (a, б, с),

$f(a,b,c) = \text{TERN}_{{10110000}_2}(a, b, c),$ как видно из таблицы истинности.

a b c | f
------+--
0 0 0 | 0
0 0 1 | 0
0 1 0 | 0
0 1 1 | 0
1 0 0 | 1
1 0 1 | 1
1 1 0 | 0
1 1 1 | 1

Поскольку для кодирования имеется только 8 входов и только 2 двоичных результата, это можно кодировать как 8-битное число, в данном случае 0b10110000 = 0xB0.

Оптимизации

Учитывая произвольную n -ную функцию булевых значений, все, что нам нужно сделать, - это преобразовать двоичные функции в троичные функции. Мы можем сделать это, потому что мы знаем, что мы можем вычислить любую комбинацию функций. Начиная с абстрактного синтаксического дерева унарных и двоичных узлов, мы начнем с представления унарных и двоичных функций способом, аналогичным описанному выше «кодирование».

Итак, для нашего ф :

f = AND(a, OR(NOT(b), c)) = BIN[1000](a, BIN[1110](UNARY[10](b), c))

Используя рекурсивную логику, мы можем объединить BIN и UNARY в:

f = AND(a, OR(NOT(b), c)) = BIN[1000](a, BIN[1011](b, c))

Который затем можно оптимизировать (правила преобразования легко следуют из логической логики):

f = AND(a, OR(NOT(b), c)) = TERN[10110000](a, b, c)

наблюдение

Это очень похоже на то, как рассчитываются таблицы поиска FPGA (LUT). Я уверен, что вы можете найти много текстов и алгоритмов для отображения логики в LUT. Например: Flow-map ( http://cadlab.cs.ucla.edu/~cong/papers/tcad94.pdf )

Пол-Кристиан Энгстад
источник

Вы говорите: «Правила преобразования легко следуют из булевой логики», поэтому я попытался создать систему перезаписи терминов (TRS), чтобы сделать именно это. Первая 4-арная БФ (самого сложного вида) БФ [100010110, 4] имеет таблицу истинности: 0000 => 1 0010 => 1 0100 => 1 1000 => 1 A'B'C'D + A'B'CD '+ A'BC'D' + AB'C'D '= BF [0xd1,3] (A, BF [0x16,3] (D, C, B), BF [0x02,3] (C, B, A)) Какое наименьшее сокращение я могу найти при поиске методом грубой силы. Мой вопрос: Как бы вы переписали это (неэффективно), я не вижу, как правила преобразования из булевой логики любой помощи здесь.

HJLebbink

И после того, как 6 мин чтение этого вы не можете даже удалить не-очень-функциональный

HJLebbink

Вам не нужно переписывать это. Просто проведите оценку грубой силы для каждой комбинации истинных ценностей.

Пол-Кристиан Энгстад

@engstad: ах я наконец понял ваше замечание: вы имеете в виду что-то вроде: BF [i, K] (a_0, ..., a_K) = BF [0xCA, 3] (a_0, BF [upperhalf (i), K-1 ] (a_1, ..., a_K), BF [младший (i), K-1] (a_1, ..., a_K))

HJLebbink

Выдержка из моего собственного ответа .

Переведите таблицу истинности в логическую формулу; используйте, например, Logic Friday.
Сохраните логическую формулу в формате уравнения Synopsys (.eqn).

Содержание BF_Q6.eqn:

INORDER = A B C D E F; 
OUTORDER = F0 F1;
F0 = (!A*!B*!C*!D*!E*F) + (!A*!B*!C*!D*E*!F) + (!A*!B*!C*D*!E*!F) + (!A*!B*C*!D*!E*!F) + (!A*B*!C*!D*!E*!F) + (A*!B*!C*!D*!E*!F);
F1 = (!A*!B*!C*!D*E) + (!A*!B*!C*D*!E) + (!A*!B*C*!D*!E) + (!A*B*!C*!D*!E) + (A*!B*!C*!D*!E);

Используйте «ABC: Система для последовательного синтеза и верификации» из Исследовательского центра верификации и синтеза Беркли.

В ABC я бегу:

abc 01> read_eqn BF_Q6.eqn
abc 02> choice; if -K 3; ps
abc 03> lutpack -N 3 -S 3; ps
abc 04> show
abc 05> write_bench BF_Q6.bench

Возможно, вам придется запустить choice; if -K 3; psнесколько раз, чтобы получить лучшие результаты.

Результирующий BF_Q6.bench содержит 3-LUT для FPGA:

INPUT(A)
INPUT(B)
INPUT(C)
INPUT(D)
INPUT(E)
INPUT(F)
OUTPUT(F0)
OUTPUT(F1)
n11         = LUT 0x01 ( B, C, D )
n12         = LUT 0x1 ( A, E )
n14         = LUT 0x9 ( A, E )
n16         = LUT 0xe9 ( B, C, D )
n18         = LUT 0x2 ( n11, n14 )
F1          = LUT 0xae ( n18, n12, n16 )
n21         = LUT 0xd9 ( F, n11, n14 )
n22         = LUT 0xd9 ( F, n12, n16 )
F0          = LUT 0x95 ( F, n21, n22 )

Это можно переписать (механически) в C ++, который я искал.

HJLebbink
источник

Хорошее использование ABC!

Пол-Кристиан Энгстад