Synthesis of combinational logic using three-input majority gates

This paper examines the problem of synthesizing a switching function using only majority gates. It is assumed that the switching function is given in truth-table form where any "don\´t care" input combinations have simply been omitted from the table. First, a theorem is derived which indicates those complemented variables and constants which must be added as additional columns of the truth-table in order that the function be realizable with only majority gates. Likewise, the same theorem permits unnecessary input variables to be eliminated. Next, the table is "unitized" by complementing those rows where F is to be O. Finally, a reduction theorem often permits many of the rows of this "unitized" table to be eliminated. Various synthesis procedures are described based on this reduced table. Two "canonical" realizations are shown which follow immediately from the table. A more comprehensive procedure for three-input gates is then described. Extensions of the methods to majority gates with more than three inputs and to multiple-output functions are discussed briefly. Examples are included.