8

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.

Rodrigo de Azevedo
  • 202
  • 1
  • 10
HJLebbink
  • 151
  • 1
  • 12
  • 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. – Eugene Sh. Dec 04 '17 at 15:03
  • 1
    I believe this is NP hard for binary functions. – user110971 Dec 04 '17 at 15:20
  • @user110971 I don't think so.. I think you confuse with the SAT problem. – Eugene Sh. Dec 04 '17 at 15:24
  • 1
    @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. – user110971 Dec 04 '17 at 15:32
  • I read the original question at SO and I am still not sure what you are trying to achieve exactly. Do you need faster simulation times? I have simulated very large systems, e.g. FPUs, memory controllers, and a communication stack on top, without much trouble. The limiting factor seems to be RAM access speeds, not CPU processing. – user110971 Dec 04 '17 at 15:39
  • @user110971 When I reorder my data structure such that the first bit of 512 integers are stored consequently in memory, same for the second bit, third, etc., I can reduce the number of memory access (gathers) considerably. My software program now contains a large truth table that that I like to simplify. I do not simulate hardware, I write HPC software. – HJLebbink Dec 04 '17 at 16:02
  • @HJLebbink So, why not use one of the standard algorithms? How big is your table? What proportion of the entries require a high output? – user110971 Dec 04 '17 at 16:12
  • 2
    @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. – HJLebbink Dec 04 '17 at 16:17
  • Normally EE's might use a brute force programmable logic chip to reduce 256 functions and create a connection map with sets of 3 input OR,AND,XOR gates , 2 inputs and inverters for inputs or outputs to produce a 1 bit logical output from a 1 byte hex function.. I probably still dont understand – Tony Stewart EE75 Dec 04 '17 at 18:51
  • For 4 inputs you need a maximum of two 3-input tables selected by the 4th input to generate any possible function. The selector can be done by a third 3-input table, so the worst case for 4 inputs is 3. Not sure how to either generalize that or to reduce it, though. – stark Dec 04 '17 at 18:53
  • actually 2 sets of tables with combinations of 2 of 3 functions(or,and,xor) not counting their input/output complements and 0/1 – Tony Stewart EE75 Dec 04 '17 at 19:15

2 Answers2

4

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)

Pål-Kristian Engstad
  • 1,305
  • 6
  • 12
  • 1
    You say "conversions rules follow easily from boolean logic", thus I tried to build a Term Rewriting System (TRS) to do just that.
    The first 4-ary BF (of the most complex sort) BF[100010110,4] has truth table:
    0000 => 1
    0010 => 1
    0100 => 1
    1000 => 1
    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.
    **My Question:** How would you rewrite this (inefficiently), I don’t see how the conversion rules from Boolean logic are of any help here.     – HJLebbink Dec 07 '17 at 10:37
  • 1
    And after 6 min reading [this](https://meta.stackexchange.com/questions/165268/line-breaks-not-working-in-comments) you cannot even remove the not-very-functional
    – HJLebbink Dec 07 '17 at 10:45
  • 1
    You don't need to rewrite it. Just do a brute-force evaluation for each combination of truth-values. – Pål-Kristian Engstad Dec 08 '17 at 20:50
  • @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)) – HJLebbink Dec 23 '17 at 14:25
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);
  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.

HJLebbink
  • 151
  • 1
  • 12