1
\$\begingroup\$

I'm working on some project which is not really related to digital circuits but rather boolean algebra analysis.

In some point I stucked at algorithmic or maybe data structure problem: How to effectively determine if given truth table is equal to another one (when we take into account that they can differ at order of inputs).

For now I hold truth tables in bitvectors for example nand truth table will be stored as: 1110 because:

A | B | R
0 | 0 | *1*
0 | 1 | *1*
1 | 0 | *1*
1 | 1 | *0*

However for some circuits thruth table in my representation might look tottaly different for the same circuit when inputs order is changed. For example:

schematic

simulate this circuit – Schematic created using CircuitLab

Truth table:

A | B | C | R
0 | 0 | 0 | 0
0 | 0 | 1 | 1
0 | 1 | 0 | 0
0 | 1 | 1 | 1
1 | 0 | 0 | 0
1 | 0 | 1 | 1
1 | 1 | 0 | 1
1 | 1 | 1 | 1

but when we change A <-> C inputs like:

schematic

simulate this circuit

truth table become:

A | B | C | R
0 | 0 | 0 | 0
0 | 0 | 1 | 0
0 | 1 | 0 | 0
0 | 1 | 1 | 1
1 | 0 | 0 | 1
1 | 0 | 1 | 1
1 | 1 | 0 | 1
1 | 1 | 1 | 1

So at it is visible I cannot just compare my "raw" form of truth tables for this case because 01010111 != 00011111 while from my perspective these truth tables represent exactly the same circuits with only inputs order difference.

Is there any smart representation of truth tables which will allow me to check this kind of equality and tell me which inputs from first thruth table maps to which inputs from second one?

For now I only have idea to generate all "raw" thruth tables based on inputs order permutations for given "start" truth table and during comparation check if any of these permutations is equal, but this is very memory consuming and slow method.

Do you have any idea how to solve this problem? Maybe there are existing scientific papers about this?

\$\endgroup\$
  • 1
    \$\begingroup\$ Turn the truth tables into gates and compare the gate setup. That is the only thing that is exactly identical in both of your cases. Or turn it into boolean algebra "A&B+C" vs "B&C+A" and compare two text strings where you swap the signals around until your text matches. \$\endgroup\$ – Harry Svensson Nov 14 '17 at 10:27
  • 1
    \$\begingroup\$ Put your formulas into DNF or CNF and permute the input order. \$\endgroup\$ – PlasmaHH Nov 14 '17 at 10:28
  • \$\begingroup\$ @PlasmaHH: thank you for idea that DNF or CNF can help. I figured out that after conversion of both truth tables to CNF or DNF it's fairly easy to find if variable in one expression can be variable in second expression and recursively check if after choosen variable substitution next one can be substituted by ellimination. Suppose CPU complexity of this algorithm is not so big, while memory complexity is negligible. When I finish my implementation, I will try to show it here bacause I couldn't find any materials about this for a long time. \$\endgroup\$ – Tomasz Frydrych Nov 14 '17 at 12:46
  • \$\begingroup\$ @TomaszFrydrych I'm guessing that this topic you've brought up is probably a fairly hot topic in the area of cryptography. This is exactly the kind of question they'd be asking themselves to solve. I'd be looking at publications related to "mod 2", Galois fields, Walsh, spectral analysis, and probably also anything related to algebraic normal forms (there are several sub areas here.) \$\endgroup\$ – jonk Nov 14 '17 at 18:27
0
\$\begingroup\$

They do not represent the same circuit because swapping the inputs may not yield the same result. The inputs are not equal otherwise swapping them would have no meaning.

Consider the case where ABC = 100: in the first circuit it yields 0, in the second it yields 1. So the logic is different even though the gates are the same. If the order of the inputs did not matter, how would you differentiate between ABC = 100 and ABC = 001 since they produce different output in your case?

\$\endgroup\$
  • 1
    \$\begingroup\$ In case when you not allow "aliasing" inputs you are right but when you are interesting about that if Circut A can be used insead of circut B that what you are saing is not true. Imagine that inputs from first example we will name A1, B1 C1 while in second A2, B2 and C2. If we assume that A1=C2, B1=B2 and C1=A2 or B1=C2, A1=B2 and C1 =A2 these circuits are equal. \$\endgroup\$ – Tomasz Frydrych Nov 14 '17 at 12:36
  • \$\begingroup\$ @TomaszFrydrych I get what you are saying, but the order of inputs is as relevant to the circuit as is the topology of the gates. Otherwise you have a single gate with a number of inputs, then it doesn't matter. I don't see any practical relevance to this problem \$\endgroup\$ – clabacchio Nov 14 '17 at 13:15
  • \$\begingroup\$ Practical usage can be for example digital circuit synthesis - you have in this scenario "library" of logically complex gates and big nand graph as input for agorithm. So task for synthesis algorithm is to replace parts of big nand graph using gates from library and/or optimize it by removal of not needed subgaphs using for example maximal munch aproach. As it's visible there is needed method to detect if subgraph can be replaced by something from library(about that is this topic). Simmilar things are done for example during FPGA synthesis by Xilinx ISE(or other simmilar software) \$\endgroup\$ – Tomasz Frydrych Nov 15 '17 at 9:32
  • \$\begingroup\$ @TomaszFrydrych I believe in that case the order of the inputs matters, contrarily to the assumption in the question. Do you know the eggs and milk joke? \$\endgroup\$ – clabacchio Nov 15 '17 at 9:40
0
\$\begingroup\$

After some research I figured out algorithm which somehow resolve my problem(thanks for @PlasmaHH suggestion) - maybe not as fast as possible but anyway good enaught for me. I implemented it in C++: https://gitlab.com/snippets/1684702

It change truth table(stored as bitvector) into some kind of normalized form. On normalized form it tries to eliminate contradictory aliasings between variables to find that combinations of variables aliasings under which conditions given truth tables are equal.

\$\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.