8
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ There is no even formal way to "map" to an arbitrary binary function. And not every binary function comprise a complete functional system. The same is true for ternary. \$\endgroup\$ – Eugene Sh. Dec 4 '17 at 15:03
  • 1
    \$\begingroup\$ I believe this is NP hard for binary functions. \$\endgroup\$ – user110971 Dec 4 '17 at 15:20
  • \$\begingroup\$ @user110971 I don't think so.. I think you confuse with the SAT problem. \$\endgroup\$ – Eugene Sh. Dec 4 '17 at 15:24
  • 1
    \$\begingroup\$ @EugeneSh. I think the problem reduces to Boolean minimization, which is NP hard, because otherwise you could solve the SAT problem. At least this is what I think the OP is asking. \$\endgroup\$ – user110971 Dec 4 '17 at 15:32
  • 2
    \$\begingroup\$ @user110971 The standard algorithms (that I'm aware of) do not reduce to arbitrary ternary logical functions (that is the question). They simplify to 3-in NANDs, and 3-in ANDs, but not all other 3-in logical functions which would allow a much more compact reduction. \$\endgroup\$ – HJLebbink Dec 4 '17 at 16:17
4
+50
\$\begingroup\$

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)

\$\endgroup\$
  • 1
    \$\begingroup\$ You say "conversions rules follow easily from boolean logic", thus I tried to build a Term Rewriting System (TRS) to do just that.<br/> The first 4-ary BF (of the most complex sort) BF[100010110,4] has truth table:<br/> 0000 => 1<br/> 0010 => 1<br/> 0100 => 1<br/> 1000 => 1<br/> 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)) Which is the smallest reduction I could find by brute force searching.<br/> My Question: How would you rewrite this (inefficiently), I don’t see how the conversion rules from Boolean logic are of any help here. \$\endgroup\$ – HJLebbink Dec 7 '17 at 10:37
  • 1
    \$\begingroup\$ And after 6 min reading this you cannot even remove the not-very-functional <br/> \$\endgroup\$ – HJLebbink Dec 7 '17 at 10:45
  • 1
    \$\begingroup\$ You don't need to rewrite it. Just do a brute-force evaluation for each combination of truth-values. \$\endgroup\$ – Pål-Kristian Engstad Dec 8 '17 at 20:50
  • \$\begingroup\$ @engstad: ah I finally understood your remark: you mean something like: BF[i,K](a_0, ..., a_K) = BF[0xCA, 3](a_0, BF[upperhalf(i), K-1](a_1, ..., a_K), BF[lowerhalf(i), K-1](a_1, ..., a_K)) \$\endgroup\$ – HJLebbink Dec 23 '17 at 14:25
2
\$\begingroup\$

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);
  1. 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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.