Chapter 6
Synthesis of Majority Expressions
Through Primitive Function
Manipulation
Evandro C. Ferraz, Jeferson de Lima Muniz, Alexandre C. R. da Silva,
and Gerhard W. Dueck
6.1 Introduction
Majority logic allows the creation of nanoelectronic circuits for several different
technologies, which justifies the search for majority based algorithms that generates
optimized circuits. Among the first works that deal with majority logic are Lindaman [11], Cohn [8], and Akers [1]. Lindaman [11] proposed the first theorem
for applying majority logic in binary decision problems, introducing the majority
operator to classical Boolean algebra. The theorem, shown in Eq. (6.1), proposes a
Boolean function equivalent to a majority operation.
M(A, B, C) = A · B + A · C + B · C
(6.1)
Subsequently, a set of axioms that defines the majority algebra independently of
the classical Boolean algebra was presented in [8], creating the basis for current
majority algebra axiomatization (Ω).
Moreover, the authors in [21] presented a method that performs the mapping
of all 3-input Boolean functions into a 3-dimensional cube, generating 13 possible
patterns, where each pattern has a different formula to convert a classical Boolean
function into a majority equivalent.
Similarly, the authors in [19] presented a method that uses a 4-dimensional cube
to map 4-input functions, generating a total of 143 representation patterns. All 143
patterns also have a specific formula to find their equivalent majority functions.
E. C. Ferraz () · J. de Lima Muniz · A. C. R. da Silva
Department of Electrical Engineering, FEIS - S˜ ao Paulo State University, Ilha Solteira, SP, Brazil
G. W. Dueck
Faculty of Computer Science, University of New Brunswick, Fredericton, NB, Canada
© Springer Nature Switzerland AG 2020
R. Drechsler, M. Soeken (eds.), Advanced Boolean Techniques,
https://doi.org/10.1007/978-3-030-20323-8_6
135
Synthesis of Majority Expressions
Through Primitive Function
Manipulation
Evandro C. Ferraz, Jeferson de Lima Muniz, Alexandre C. R. da Silva,
and Gerhard W. Dueck
6.1 Introduction
Majority logic allows the creation of nanoelectronic circuits for several different
technologies, which justifies the search for majority based algorithms that generates
optimized circuits. Among the first works that deal with majority logic are Lindaman [11], Cohn [8], and Akers [1]. Lindaman [11] proposed the first theorem
for applying majority logic in binary decision problems, introducing the majority
operator to classical Boolean algebra. The theorem, shown in Eq. (6.1), proposes a
Boolean function equivalent to a majority operation.
M(A, B, C) = A · B + A · C + B · C
(6.1)
Subsequently, a set of axioms that defines the majority algebra independently of
the classical Boolean algebra was presented in [8], creating the basis for current
majority algebra axiomatization (Ω).
Moreover, the authors in [21] presented a method that performs the mapping
of all 3-input Boolean functions into a 3-dimensional cube, generating 13 possible
patterns, where each pattern has a different formula to convert a classical Boolean
function into a majority equivalent.
Similarly, the authors in [19] presented a method that uses a 4-dimensional cube
to map 4-input functions, generating a total of 143 representation patterns. All 143
patterns also have a specific formula to find their equivalent majority functions.
E. C. Ferraz () · J. de Lima Muniz · A. C. R. da Silva
Department of Electrical Engineering, FEIS - S˜ ao Paulo State University, Ilha Solteira, SP, Brazil
G. W. Dueck
Faculty of Computer Science, University of New Brunswick, Fredericton, NB, Canada
© Springer Nature Switzerland AG 2020
R. Drechsler, M. Soeken (eds.), Advanced Boolean Techniques,
https://doi.org/10.1007/978-3-030-20323-8_6
135