¿Cómo asignar una tabla de verdad a funciones lógicas ternarias?

Extracto de mi propia respuesta .

1. Convierta la tabla de verdad en una fórmula lógica; utilizar, por ejemplo, Viernes Lógico.
2. Almacene la fórmula lógica en formato de ecuación de Synopsys (.eqn).

Contenido de 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);

3. Utilice "ABC: Un sistema para la síntesis y verificación secuencial" del Centro de investigación de verificación y síntesis de Berkeley.

En ABC corro:

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

Es posible que necesites ejecutar choice; if -K 3; ps varias veces para obtener mejores resultados.

El BF_Q6.bench resultante contiene las 3-LUT para un 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 )

Esto se puede reescribir (mecánicamente) al C ++ que estaba buscando.

Análisis

Observe que la instrucción codifica todas las posibles funciones ternarias. Por lo tanto, dadas tres variables booleanas y cualquier operación de bits en ellas, siempre podemos encontrar el byte de codificación. Por ejemplo, si se le da una función $$ f: \ text {Bool} \ times \ text {Bool} \ times \ text {Bool} \ rightarrow \ text {Bool}, $$ luego, el valor de verdad se puede encontrar para cada combinación de valores de entrada y se puede almacenar en una tabla. Por ejemplo, si $$ f (a, b, c) = a \ & (! b | c), $$ entonces $$ f (a, b, c) = \ text {TERN} _ {{10110000} _2} (a, b, c), $$ Como se puede ver en una tabla de verdad.

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

Dado que solo hay 8 entradas para la codificación y solo 2 resultados binarios, esto se puede codificar como un número de 8 bits, en este caso 0b10110000 = 0xB0.

Optimizaciones

Dada una función n arbitraria de valores booleanos, todo lo que tenemos que hacer es convertir las funciones binarias en funciones ternarias. Podemos hacer esto, porque sabemos que podemos calcular cualquier combinación de funciones. Partiendo de un árbol de sintaxis abstracta de nodos unarios y binarios, comenzaríamos representando funciones unarias y binarias de manera similar a la "codificación" anterior.

Por lo tanto, para nuestro f :

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

Usando lógica recursiva, podemos combinar BIN y UNARY en:

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

Que luego puede optimizarse en (las reglas de conversión se siguen fácilmente de la lógica booleana):

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

Observación

Esto es muy similar a cómo se calculan las tablas de búsqueda de FPGA (LUT). Estoy bastante seguro de que puede encontrar muchos textos y algoritmos para mapear la lógica a las LUT. Por ejemplo: Flow-map ( enlace )