Cheap and Secure Web Hosting Provider : See Now

Algorithms for logical synthesis

, , No Comments
Problem Detail: 

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

Asked By : Alan Wolfe
Answered By : D.W.

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/50925

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback