Electronic – How to map a truth table to ternary logical functions

boolean-algebradigital-logiclogic-gates

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.

Best Answer

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)

Related Topic