1
$\begingroup$

Let's say that I want to map some string of binary digits to a single binary digit of output, like the below:

$ \begin{array}{l|l} \text{Input}&\text{Output}\\ \hline 0001&0\\ 0011&1\\ 0111&0\\ 1111&1 \end{array} $

If inputs besides those listed are given, I don't care what the output is. I only care about the inputs listed.

I can eyeball the truth table and come up with the below:

$Output = \lnot (Input_0 \oplus Input_1 \oplus Input_2 \oplus Input_3)$

However, that isn't the only solution, and might not be the solution using the fewest number of operations.

Are there any algorithms to figure this out for arbitrary length inputs mapping to a single binary digit of output?

Ultimately I'm trying to solve for mapping $M$ bits of input to $N$ bits of output. I figure an ok way to do this might be to break it into $N$ problems of mapping $M$ bits of input to a single bit of output so am starting with that.

I'm actually going to be implementing something using a standard modern computer (aka desktop CPU), so I know that there is some extra complexity if I want better efficiency, due to the fact that operations happen not on single binary digits, but on eg. words. Not only will efficiency depend on minimizing the number of operations done on each bit, there will also be efficiency to be gained by letting "bit programs" share operations where they can, if that makes sense.

One step at a time, but I bring this up in case there is an answer which encompasses my future needs as well.

Edit: I've found these pages which talk about minterms and karnaugh maps and understand what they are talking about, however I also know that they aren't guaranteed to be the minimal circuit, and they also mention that some other algorithms are used in more complex circuit design (but they don't say what they are)
https://www.facstaff.bucknell.edu/mastascu/eLessonsHTML/Logic/Logic2.html
https://www.facstaff.bucknell.edu/mastascu/eLessonsHTML/Logic/Logic3.html

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

This is an instance of logic synthesis. A standard approach is to use Karnaugh maps or the Quine-McCluskey algorithm. Finding the minimal circuit is hard (see circuit minimization), but there are tools and techniques that often work reasonably well in practice. For instance, you can use the Espresso tool to help with this; there are other tools for this task as well.

See also Creating a logical circuit and Working out the connectives (And, Or, Not) in a Truth Table that has the outputs.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks so much. For the record, this applies to another question you gave an answer to (cs.stackexchange.com/questions/50824/…). I'm going to try using logic synthesis (thanks for the term!) to come up with a simpler program to find the minimal perfect hash of a set of inputs. Unfortunately if I want minimal, I would have to try all orderings of the input, besides the "non minimality" of karnaugh and the algorithm you linked. seems like some decent results could come out of it yet though. Thanks again! $\endgroup$
    – Alan Wolfe
    Dec 19, 2015 at 6:31

Your Answer

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

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