ON THE NUMBER OF NEGATIONS NEEDED TO COMPUTE PARITY FUNCTIONS

Authors
NISHINO T RADHAKRISHNAN J
Citation
T. Nishino et J. Radhakrishnan, ON THE NUMBER OF NEGATIONS NEEDED TO COMPUTE PARITY FUNCTIONS, IEICE transactions on information and systems, E78D(1), 1995, pp. 90-91
Citations number
NO
Categorie Soggetti
Computer Science Information Systems
Journal title
IEICE transactions on information and systems → ACNP
ISSN journal
09168532
Volume
E78D
Issue
1
Year of publication
1995
Pages
90 - 91
Database
ISI
SICI code
0916-8532(1995)E78D:1<90:OTNONN>2.0.ZU;2-3
Abstract
We exactly determine the number of negations needed to compute the par ity functions and the complement of the parity functions. We show that with k NOT gates, parity can be computed on at most 2k+1 - 1 variable s, and parity complement on at most 2k+1 - 2 variables. The two bounds are shown to be tight.