I have a circuit that is represented as a netlist (specifically, an and-inverter graph). The desired outputs of this circuit are known. We can assume that some combination of the primary inputs will result in the desired outputs. If it makes it easier, you can assume that there's only one combination of inputs that will give me the desired output. How do I find those inputs?

Each output for the netlist can be represented as a combinatorial boolean equation, so I was tempted to convert each output, triangularise, and solve to obtain the suitable primary inputs. However, converting the netlist to equation-form (i.e. a similar operation to unfolding it) incurs a prohibitive space cost. Is there a way to "triangularise" the circuit so that I can find suitable primary inputs? Or, alternatively, can anyone recommend a way to achieve the goal of finding suitable primary inputs?

  • $\begingroup$ Looks like a generalization of SAT and SAT itself is NP-complete. So I'll suggest looking at heuristics used by SAT solvers. $\endgroup$ – AProgrammer Nov 5 '14 at 13:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.