Linear Optimization Models for Maj-3 and Maj-5 Exact Synthesis

Due to the physical restriction of current CMOS technology, the study of majority based nanotechnologies has been progressing steadily. In this paper, we present a new exact synthesis algorithm for majority-of-three and majority-of-five boolean functions. Key in our approach is the formulation of constraints that encodes majority logic problems into linear optimization models. The proposed algorithm is able to generate optimal results for both depth and size minimization, while also minimizing the number of inverters and literals in the output function. With this new approach, we can decrease the total production cost of a circuit in technologies where inverters and literals are expensive to build, without losing optimal results for depth and size minimization. To evaluate our method, a comparison was made with two exact synthesis algorithms that can generate optimal results when considering depth and size as cost criteria, for majority-of-three and majority-of-five boolean functions. Since our method considers two additional cost criteria, the goal is to generate functions that are also optimal in relation to depth and size, but with less inverters and literals. The obtained results have shown that the proposed algorithm was able to further optimize 64% of all 220,376 compared functions, while also achieving equal cost results for the remaining 36%.

Automated summary

This paper presents a new exact synthesis algorithm for majority-of-three and majority-of-five boolean functions, which encodes majority logic problems into linear optimization models and generates optimal results for both depth and size minimization. The proposed algorithm further optimizes 64% of compared functions while achieving equal cost results for the remaining 36%.