2
\$\begingroup\$

I searched quite a bit about this but it seems not many people have a similar interest as mine regarding don't cares. Most don't care topics I found revolve around simplifying the function at hand. I am, however, not interested in changing the function, but interested to understand which inputs are inconsequential at any particular state.

Problem:

I have a circuit with an known arbitrary function, for example:

z = a|(b&c)

which will yield a truth table as follows:

a b c | z
______|__
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

I would like to further reduce this table with don't cares, as in the following table:

a b c | z
______|__
0 0 x | 0
0 x 0 | 0
x 1 1 | 1
1 x x | 1

I would like to be able to generate a reduced truth table from a full truth table (or from the original function) programmatically for many logic functions with mostly 2-6 inputs. I am at a loss of how to come up with an algorithm myself. I am wondering if there are known algorithms out there that I can leverage. Planning to implement in Python if that is of any help.

I am particularly interested in knowing which inputs are inconsequential given the value of other inputs. i.e if I know that "a" is 1 for a particular time window, I would like to know what "b" and "c" values don't matter within that time window (ignoring glitches and delays).

I feel I may not be using the right keywords in my research (truth table, don't care, reduce). Any pointers will be helpful.

Thank you.

\$\endgroup\$
0

3 Answers 3

3
\$\begingroup\$

I'm assuming you already can produce the k-maps just fine. But you are looking for iterative (and they are iterative) algorithms dealing with cover on the hypercubes up to 6 dimensions, or so. You will want to study ancient materials (decades back) on MINI, PRESTO, ESPRESSO, and ESPRESSO II. Then you will want to find newer papers referencing these that suggest newer algorithms.

Let's just use MINI (S. J. Hong, R. G. Cain, and D. L. Ostapco, "MINI: A Heuristic Approach for Logic Minimization," IBM J. of Res. and Dev., Sep. 1974.)

Take your table as you show it. Find the first row with 1 (true) as its result. This would be 011. Start there.

Try 011    --> That table entry is 1. This is OK. So keep it.
Try *11    --> All such table entries are 1. This is OK. So keep it.
Try **1    --> Failure. Some entries are 0. Restore to prior state.
Try *1*    --> Failure. Some entries are 0. Restore to prior state.
Rmv *11    --> Remove all rows matching this from further consideration.
Try 100    --> That table entry is 1. This is OK. So keep it.
Try *00    --> Failure. Some entries are 0. Restore to prior state.
Try 1*0    --> All such table entries are 1. This is OK. So keep it.
Try 1**    --> All such table entries are 1. This is OK. So keep it.
Rmv 1**    --> Remove all rows matching this from further consideration
Nothing more to try, so stop.

The result is:

ABC Z
*11 1
1** 1

Let's pick another table:

VWXYZ F
00000 1
00001 1
00010 1
00011 0
00100 0
00101 0
00110 1
00111 1
01000 0
01001 1
01010 0
01011 1
01100 0
01101 1
01110 0
01111 1
10000 1
10001 0
10010 1
10011 1
10100 1
10101 1
10110 1
10111 1
11000 0
11001 0
11010 0
11011 1
11100 0
11101 0
11110 0
11111 1

Try 00000  --> That table entry is 1. This is OK. So keep it.
Try *0000  --> All such table entries are 1. This is OK. So keep it.
Try **000  --> Failure. Some entries are 0. Restore to prior state.
Try *0*00  --> Failure. Some entries are 0. Restore to prior state.
Try *00*0  --> All such table entries are 1. This is OK. So keep it.
Try *00**  --> Failure. Some entries are 0. Restore to prior state.
Rmv *00*0  --> Remove all rows matching this from further consideration
Try 00001  --> That table entry is 1. This is OK. So keep it.
Try *0001  --> Failure. Some entries are 0. Restore to prior state.
Try 0*001  --> All such table entries are 1. This is OK. So keep it.
Try 0**01  --> Failure. Some entries are 0. Restore to prior state.
Try 0*0*1  --> Failure. Some entries are 0. Restore to prior state.
Try 0*00*  --> Failure. Some entries are 0. Restore to prior state.
Rmv 0*001  --> Remove all rows matching this from further consideration
Try 00110  --> That table entry is 1. This is OK. So keep it.
Try *0110  --> All such table entries are 1. This is OK. So keep it.
Try **110  --> Failure. Some entries are 0. Restore to prior state.
Try *0*10  --> All such table entries are 1. This is OK. So keep it.
Try *0**0  --> Failure. Some entries are 0. Restore to prior state.
Try *0*1*  --> Failure. Some entries are 0. Restore to prior state. 
Rmv *0*10  --> Remove all rows matching this from further consideration
...
etc

There are many other methods and they won't all come up with the exact same set, since there may be several ways to get to similar places. Also, you many not be always guaranteed the minimum such sets from the process. In fact, this last case I presented may cause you to find a set that isn't the least number possible as it is a little 'greedy' about what it does and will often find smaller hypercubes before finding the larger ones. This is where ESPRESSO II starts to shine, more. But this should give you a start about how you might further pursue your question.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Thank you. This is very helpful! \$\endgroup\$
    – SamZay
    Commented Mar 12 at 19:34
0
\$\begingroup\$

Consider what you're looking for: a subset P of the inputs to f, which, when set to particular values, has the same result for all values of the complementary subset Q of the inputs.

For f(a, b, c) = a or (b and c), there are three inputs, and a length-2 subset of them would be P={a, c}, which would make the complementary subset Q be {b}. There are obviously 2^2 possible values Pi for a and c; and 2^1 possible values Qi for Q.

If "test f(0, X, X)" means "evaluate all the permutations for the Xs and see if they are all the same", then we need to try:

Subsets of length 0:

  • P={}, Q={a, b, c}
    • f(X, X, X)

Subsets of length 1

  • P={a}, B={b, c}
    • f(0, X, X)
    • f(1, X, X)
  • P={b}, B={a, c}
    • f(X, 0, X)
    • f(X, 1, X)
  • P={c}, B={a, b}
    • f(X, X, 0)
    • f(X, X, 1)

Subsets of length 2:

  • P={a, b}, Q={c}
    • f(0, 0, X)
    • f(0, 1, X)
    • f(1, 0, X)
    • f(1, 1, X)
  • P={a, c}, Q={b}
    • f(0, X, 0)
    • f(0, X, 1)
    • f(1, X, 0)
    • f(1, X, 1)
  • P={b, c}, Q={a}
    • f(X, 0, 0)
    • f(X, 0, 1)
    • f(X, 1, 0)
    • f(X, 1, 1)

Which is approximately

With a given number of inputs n
for i from 0 to n-1
   for each subset P of size i of the inputs
      calculate Q, the set of possible don't-care inputs
      for each 2^i possible values Pi of the P inputs
          for each 2^(n-i) possible values Qj of the Q inputs
              if all same, then P=Pi has Q=don't care

It can be fiddly to code, but it's a straightforward algorithm. Of course it's not a machine efficient algorithm, but usually coding is what's most expensive. It will work fine for your 6-input functions.

\$\endgroup\$
0
\$\begingroup\$

In the interest of not reinventing the wheel, thanks to @periblepsis I was able to find the following python module which does kind of what I am interested in. Here it is for anyone who goes down the same path:

package is called pyeda. Searching this function should give you info you need to run. If you still have questions let me know I can possibly help.

>>> from pyeda.boolalg.espresso import espresso
>>> espresso(ninputs, noutputs, cover, intype)
{((2, 3, 3), (1,)), ((3, 2, 2), (1,))}

in my case the values are:

ninputs = 3
noutputs = 1
# format is ((input), (output))
# input has 1 added for god knows what reason. 0 = 1 and 1 = 2
cover = {((1, 1, 1), (0,)), 
         ((1, 1, 2), (0,)), 
         ((1, 2, 1), (0,)), 
         ((1, 2, 2), (1,)), 
         ((2, 1, 1), (1,)), 
         ((2, 1, 2), (1,)), 
         ((2, 2, 1), (1,)), 
         ((2, 2, 2), (1,))}
intype = 5

This will only return the inputs which result in output = 1. 3 means don't care.

To get the inputs that result in 0 I can invert the output values in cover and rerun.

Cheers

\$\endgroup\$

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.