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

Question

Por favor, sea amable. Tengo una pregunta espinosa e importante de otro campo de la ingeniería cuya respuesta puede ser bastante conocida en ingeniería eléctrica. Hice una pregunta similar en StackOverflow

---

Supongamos que tengo una tabla de verdad de 5 entradas y 1 salida. He utilizado el algoritmo Espresso (por ejemplo, Logic Friday) para minimizar la tabla y escribir un VHDL eficiente. Todo funciona bien.

En lugar de minimizar y mapear la tabla de verdad a puertas NAND, me gustaría mapear a una función lógica ternaria arbitraria. No me interesa la lógica multivaluada, sino las funciones lógicas que tienen 3 variables de entrada. Hay 256 de estas funciones, y 3-en NAND es sólo uno de ellos. No todas estas 256 funciones pueden ser interesantes: algunas se reducen a sus hermanas de 2 variables de entrada.

Pregunta Cómo se puede mapear una tabla de verdad (por ejemplo, con 7 entradas) a cualquiera de estas funciones 3-in. Una herramienta que haga algo similar sería genial, pero un método sobre cómo simplificar a funciones ternarias arbitrarias sería lo mejor.

---

Antecedentes: Las CPUs modernas pueden realizar operaciones lógicas ternarias arbitrarias en registros de 512 bits (por ejemplo, la instrucción vpternlog ), pero debido a la complejidad, los compiladores lo dejan en manos del programador, que no tiene ni idea de cómo optimizarlo.

Answer 1

Análisis

Observe que la instrucción codifica todo posibles funciones ternarias. Por lo tanto, dadas tres variables booleanas cualesquiera y cualquier operación a nivel de bits sobre ellas, siempre podemos encontrar el byte de codificación. Por ejemplo, si se da una función $$ f : \text{Bool} \times \text{Bool} \times \text{Bool} \rightarrow \text{Bool}, $$ entonces se puede encontrar el valor de verdad para cada combinación de valores de entrada, y almacenarlo 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

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

Optimizaciones

Dada una situación arbitraria n -de valores booleanos, lo único que tenemos que hacer es convertir las funciones binarias en funciones ternarias. Podemos hacerlo porque sabemos que podemos calcular cualquier combinación de funciones. Partiendo de un árbol sintáctico abstracto de nodos unarios y binarios, empezaríamos representando las funciones unarias y binarias de forma similar a la "codificación" anterior.

Así, para nuestro f :

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

Utilizando la 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 ser optimizado en (reglas de conversión 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 consulta (LUT) de la FPGA. Estoy seguro de que puedes encontrar muchos textos y algoritmos para mapear la lógica a las LUTs. Por ejemplo: Flow-map ( http://cadlab.cs.ucla.edu/~cong/papers/tcad94.pdf )

Answer 2

Extracto de mi propio respuesta .

1. Traduce la tabla de verdad en una fórmula lógica; utiliza, por ejemplo, Logic Friday.
2. Almacena 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: A System for Sequential Synthesis and Verification" del Berkeley Verification and Synthesis Research Center.

En el 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 tenga que ejecutar choice; if -K 3; ps varias veces para obtener mejores resultados.

El BF_Q6.bench resultante contiene los 3-LUTs para una 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.