Synthesis of majority and minority networks and its applications to QCA, TPL and SET based nanotechnologies

In this paper, we present a methodology for efficient majority/minority network synthesis of arbitrary multioutput Boolean functions. Many emerging nanoscale technologies, such as quantum cellular automata (QCA), tunneling phase logic (TPL), and single electron tunneling (SET), are capable of implementing majority or minority logic very efficiently. However, there exists no comprehensive methodology or design automation tool for general multilevel majority/minority network synthesis. We have built the first such tool, majority logic synthesizer (MALS), on top of an existing Boolean logic synthesis tool. We have performed experiments with 40 MCNC benchmarks. They indicate that up to 68.0% reduction in gate count is possible when utilizing majority logic, with the average reduction being 21.9%, compared to traditional logic synthesis, in which two-input AND/OR gates in the circuit are converted to majority gates.