Majority Logic: Prime Implicants and n-Input Majority Term Equivalence

摘要

Recent advances in nanotechnology have led to the emergence of energy efficient circuit technologies like spintronics and domain wall magnets that use Majority gates as their primary logic elements. Logic synthesis that exploits these technologies demand an understanding of the mathematics of n-input Majority terms. One of the problems that turn up in such a study is the checking of equivalence of two n-input Majority terms on the same set of variables. We provide an algorithm based on prime implicants as a solution to this problem. In this quest, we extend the concept of implicants to two cases - 1-implicants and prime 1-implicants that imply a function evaluates to '1', and 0-implicants and prime 0-implicants that imply that it evaluates to '1'. We exploit the properties of Majority to create an efficient algorithm to generate the sums of all prime 1-implicants and all prime 0-implicants of an n-input Majority term, both being canonical representations of Boolean functions. As Majority and Threshold functions have been shown to be logically equivalent, our algorithms are applicable to Threshold functions as well. Also, being based on prime implicants, our algorithms improve on the known algorithm for equivalence checking for threshold logic terms.