World's most popular travel blog for travel bloggers.

Determining whether a digital circuit is optimal

, , No Comments
Problem Detail: 

Are there any techniques that can be used to determine whether a digital logic circuit is optimal, or if it has extraneous operations that don't contribute to the output?

I'm especially curious in the case where the circuit is defined in terms of XOR and AND gates.

I know I could make a karnaugh map and create a circuit from that, but that doesn't really tell me about the circuit I had, it just gives me another circuit.

Thanks for any info!

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

Use one of the standard techniques for circuit minimization. As far as I know, verifying that a candidate circuit is minimal is as hard as finding the minimal circuit in the first place (I know of no faster algorithm for verifying minimality than finding a minimal circuit in the first place).

Circuit minimzation is NP-hard (in fact it's even harder than that, in some sense), so you shouldn't expect an efficient algorithm for it that handles all functions efficiently.

Best Answer from StackOverflow

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

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback