While studying boolean function simplification I often find things about Karnaugh maps and the Quine–McCluskey algorithm, but I find little about the case of multiple output boolean functions.
In terms of digital circuits, I know that you can reuse the output of gates to get simpler circuits. But, is there a systematic way (algorithm) to get the optimal circuit according to some cost criterion (number of gates, size of gates, etc.)?
Answer
The optimization of such cost functions in strict mathematical sense will likely result in an NP-hard problem, meaning that you'll have to explore an exponentially growing set of combinations to find a true optimum. In real logic synthesis software, different heuristics are used to find a close-to-optimum solution in a realistic time.
One important thing you should keep in mind is that there are many constraints in real world circuits - simply implementing the right Boolean expression is not enough. There may be limits on propagation time. You are often limited to only a particular element (e.g. NAND) you can use in synthesis. In some circuits you may be required to eliminate race conditions. All these constraints will further complexify the optimization task.
No comments:
Post a Comment