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\$
4
  • 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\$ Commented Nov 14, 2017 at 10:27
  • 1
    \$\begingroup\$ Put your formulas into DNF or CNF and permute the input order. \$\endgroup\$
    – PlasmaHH
    Commented Nov 14, 2017 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\$ Commented Nov 14, 2017 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
    Commented Nov 14, 2017 at 18:27

3 Answers 3

1
\$\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\$
1
\$\begingroup\$

I came across a very similar problem in educational settings. We want students to create logical circuits to a given problem and compare their result with the teachers answer. Hereby in the first step we are not interested if the two circuits are identical but if there is a isomorphism between the two truth tables. Then we can give feedback that the circuit suits the problem (but maybe can be optimized regarding gate number and speed).

I coded some Maxima code (we want to use it with Moodle and the STACK quiz question plugin). You can find it here: https://github.com/Famondir/Logic-Circuit-Simulator/blob/master/truthtabletester.wxm But be aware the code is quite messy right now. You will see all the process to come up with the final function. The final function is called truthtable_isequal.

I do the following steps:

  1. Check if the truth tables have same amount of in and outputs (if the matrix has same dimensins).
  2. Check if the sorted vectors of rowsums (full row and entries of the response submatrix) and columnsums of response submatrix are equal.
  3. Group the columnsums of response submatrix by equal columnsums and the rows by the tuple of fullrow- and responsecolumn-only-rowsums.
  4. Sort the matrix columns by their columnsum score and the rows by 1st their full-rowsum score and in case of a tie by their response-column-only-rowsum score.
  5. Permute the rows and columns that are member of the same group and check if matrices are equal.

To permutate only in subgroups reduces the amount of checks hugely most of the time. E.g. you can easily reduce the amount of checks necessary to identify nonisomorph truth tables by 10^4 for 3 inputs and 3 outputs.

In my code I picked up the idea to sort rows and columns by their sumscores I found here: https://math.stackexchange.com/questions/692605/how-to-tell-if-two-matrices-are-equal-up-to-a-permutation

\$\endgroup\$
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\$
4
  • 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\$ Commented Nov 14, 2017 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
    Commented Nov 14, 2017 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\$ Commented Nov 15, 2017 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
    Commented Nov 15, 2017 at 9:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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