How to map a truth table to ternary logical functions?

Question

Please be kind. I have a thorny and important question from a different field of engineering whose answer may be fairly well-known in electrical engineering. I asked a similar question on StackOverflow

---

Suppose I have a truth table of 5 inputs and 1 output. I used the Espresso algorithm (e.g., Logic Friday) to minimize the table and write some efficient VHDL. Everything works fine.

Instead of minimizing and mapping the truth-table to NAND gates, I would like to map to arbitrary ternary logical function. I'm not interested in multi-valued logic, but in logical functions that have 3 input variables. There are 256 of these functions, and 3-in NAND is just one of them. Not all of these 256 functions may be interesting: some reduce to their 2 input variable siblings.

Question: how can you map a truth-table (e.g., with 7 inputs) to any of these 3-in functions. A tool that does something similar would be great, but a method on how to simplify to arbitrary ternary functions would be best.

---

Background: modern CPUs can do arbitrary ternary logic operations on 512-bit registers (e.g., instruction vpternlog), but due to complexity, compilers leave it to the programmer, who is somewhat clueless on how to optimize this.

Answer 1

Analysis

Notice that the instruction encodes all possible ternary functions. So, given any three boolean variables and any bit-wise operations on them, we can always find the encoding byte. For instance, if given a function $$ f : \text{Bool} \times \text{Bool} \times \text{Bool} \rightarrow \text{Bool}, $$ then the truth value can be found for each combination of input values, and stored in a table. For instance, if $$f(a,b,c) = a \& (!b | c),$$ then $$ f(a,b,c) = \text{TERN}_{{10110000}_2}(a, b, c),$$ as can be seen from a truth table.

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

Since there are only 8 inputs to encoding and only 2 binary results, this can be coded as an 8-bit number, in this case 0b10110000 = 0xB0.

Optimizations

Given an arbitrary n-ary function of boolean values, all we need to do is to convert binary functions into ternary functions. We can do this, because we know that we can calculate any combination of functions. Starting from an abstract syntax tree of unary and binary nodes, we would start by representing unary and binary functions in a similar fashion as "encoding" above.

So, for our f:

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

Using recursive logic, we can combine BIN and UNARY into:

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

Which can then be optimized into (conversions rules follow easily from boolean logic):

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

Observation

This is very similar to how FPGA lookup tables (LUTs) are calculated. I'm pretty sure you can find many texts and algorithms for mapping logic to LUTs. For instance: Flow-map (http://cadlab.cs.ucla.edu/~cong/papers/tcad94.pdf)

Answer 2

Excerpt from my own answer.

1. Translate the truth table into a logical formula; use e.g., Logic Friday.
2. Store the logical formula in Synopsys equation format (.eqn).

Content of 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. Use "ABC: A System for Sequential Synthesis and Verification" from the Berkeley Verification and Synthesis Research Center.

In ABC I run:

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

You may need to run choice; if -K 3; ps multiple time to get better results.

The resulting BF_Q6.bench contains the 3-LUTs for an 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 )

This is can be rewritten (mechanically) to the C++ that I was looking for.