Abstract

This paper presents methods for realizing simple threshold functions of n arguments by networks of k-input majority gates, where k≪n. An optimal network realization of the 5-argument majority function using 3-input majority gates is given, and it is then generalized by steps with realizations for the (2n-l)-argument majority function (where n = 3, 4, ...) using (2n-3)-input majority gates, and then for the (2n-1)-argument majority function using (2k-l)-input majority gates (where k≪n). In a final generalization an array network using (2k-l)-input majority gates introduced for the realization of an (m/n), ``simple,'' threshold function (where m = 1, 2, ...,n). The array network is then applied to the synthesis of arbitrary symmetric functions; in the latter synthesis a realization of ``adjustable logic'' is given where, by simple control of network connections, the same network can be made to compute any symmetric function. The specific networks for ``5 by 3's'' (5-argument majority function realized by a 3-input majority gate), ``7 by 5's'', and ``7 by 3's'' are the best known.

Keywords

Realization (probability)Simple (philosophy)Function (biology)GeneralizationArgument (complex analysis)MathematicsLogic gateBoolean functionTopology (electrical circuits)Discrete mathematicsComputer scienceArithmeticAlgorithmCombinatoricsMathematical analysis

Affiliated Institutions

Related Publications

Network In Network

Abstract: We propose a novel deep network structure called In Network (NIN) to enhance model discriminability for local patches within the receptive field. The conventional con...

2014 arXiv (Cornell University) 1037 citations

Publication Info

Year
1964
Type
article
Volume
EC-13
Issue
1
Pages
4-13
Citations
85
Access
Closed

External Links

Social Impact

Altmetric
PlumX Metrics

Social media, news, blog, policy document mentions

Citation Metrics

85
OpenAlex

Cite This

Saul Amarel, G. Cooke, R. O. Winder (1964). Majority Gate Networks. IEEE Transactions on Electronic Computers , EC-13 (1) , 4-13. https://doi.org/10.1109/pgec.1964.263829

Identifiers

DOI
10.1109/pgec.1964.263829