|
Complexity of implementation of parity functions in the implication–negation basis
Yu. A. Kombarov Lomonosov Moscow State University
Abstract:
The paper is concerned with circuits in the basis $\{x \to y, \overline{x}\}$. The exact value of the complexity of implementation of an even parity function is obtained and the minimal circuits implementing an odd parity function are described.
Keywords:
circuit, parity function, minimal circuit, complexity circuits.
Received: 17.09.2014
Citation:
Yu. A. Kombarov, “Complexity of implementation of parity functions in the implication–negation basis”, Diskr. Mat., 27:1 (2015), 73–97; Discrete Math. Appl., 25:4 (2015), 211–231
Linking options:
https://www.mathnet.ru/eng/dm1316https://doi.org/10.4213/dm1316 https://www.mathnet.ru/eng/dm/v27/i1/p73
|
Statistics & downloads: |
Abstract page: | 409 | Full-text PDF : | 168 | References: | 32 | First page: | 36 |
|