Electronic – What heuristics are there (if any) to know how close a circuit is to a function

boolean-algebra

I'm working on an AI project for circuit minimization.

I'm trying to think of a heuristic to tell me how close a certain circuit is to representing a certain function.

For example, if I need to implement a XOR function, than a circuit consisting of a single OR gate will be closer to representing the XOR in comparison to a circuit consisting of a single AND gate (because all is missing is a single NOT gate).

Are there any such heuristics in order to sense how "close" a circuit is to the final circuit?

We have tried scoring the circuits by counting the number of correct outputs according to the truth table, but this fails. For example, if we have a circuit that for every input outputs the negation of the correct output, then its "score" would be 0 according to this heuristic, but in fact it is very close to the final design, and all that is missing is to not the output.

Thanks

Best Answer

You could base your "cost function" on DNF fault classes. For a start, you could consider the following set

  • ENF: expression negation fault (a -> !a)
  • TOF: term omission fault (a -> a | b)
  • TIF: term insertion fault (a | b -> a)
  • TNF: term negation fault (a | b -> a | !b)
  • LOF: literal omission fault (a -> ab)
  • LIF: literal insertion fault (ab -> a)
  • LNF: literal negation fault (ab -> a!b)

For example, the distance from AND (a&b) to XOR (a&!b | !a&b) would be 1 LIF and 1 TOF, while a distance from AND to NAND would be 1 ENF. You'll have to experiment with weights you assign on different fault types in your cost function.

Another idea you may want to consider is to take the problem from the other end: instead of generating minimal functions and optimize for correctness, you could generate correct functions and optimize for minimalism. It's much easier to come up with a reasonable cost function in the latter case, and you don't have to actually reach the optimum in order to get an acceptable solution.

Related Topic