Majority Logic Formulations for Parallel Adder Designs at Reduced Delay and Circuit Complexity.

The design of high-performance adders has experienced a renewed interest in the last few years; among high performance schemes, parallel prefix adders constitute an important class. They require a logarithmic number of stages and are typically realized using AND-OR logic; moreover with the emergence of new device technologies based on majority logic, new and improved adder designs are possible. However, the best existing majority gate-based prefix adder incurs a delay of 2\mathbflo\mathbfg_2(\boldsymboln) - 1<alternatives><inline-graphic xlink:href="lombardi-ieq1-2696524.gif"/></alternatives> (due to the \boldsymboln<alternatives> <inline-graphic xlink:href="lombardi-ieq2-2696524.gif"/></alternatives>th carry); this is only marginally better than a design using only AND-OR gates (the latter design has a 2\mathbflo\mathbfg_2(\boldsymboln) + 1<alternatives> <inline-graphic xlink:href="lombardi-ieq3-2696524.gif"/></alternatives> gate delay). This paper initially shows that this delay is caused by the output carry equation in majority gate-based adders that is still largely defined in terms of AND-OR gates. In this paper, two new majority gate-based recursive techniques are proposed. The first technique relies on a novel formulation of the majority gate-based equations in the used group generate and group propagate hardware; this results in a new definition for the output carry, thus reducing the delay. The second contribution of this manuscript utilizes recursive properties of majority gates (through a novel operator) to reduce the circuit complexity of prefix adder designs. Overall, the proposed techniques result in the calculation of the output carry of an \boldsymboln<alternatives><inline-graphic xlink:href="lombardi-ieq4-2696524.gif"/></alternatives> -bit adder with only a majority gate delay of \mathbflo\mathbfg_2(\boldsymboln) + 1<alternatives> <inline-graphic xlink:href="lombardi-ieq5-2696524.gif"/></alternatives>. This leads to a reduction of 40percent in delay and 30percent in circuit complexity (in terms of the number of majority gates) for multi-bit addition in comparison to the best existing designs found in the technical literature. [ABSTRACT FROM AUTHOR]