For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Complexity of Boolean Functions Satisfying the Propagation Criterion
Shouichi HIROSE Katsuo IKEDA
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1995/04/25
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Boolean function, propagation criterion, unateness, inversion complexity, formula size, VLSI complexity, OBDD size,
Full Text: PDF>>
Complexity of Boolean functions satisfying the propagation criterion (PC), an extended notion of the perfect nonlinearity, is discussed on several computation models. The following topics are investigated: (i) relationships between the unateness and the degree of the PC, (ii) the inversion complexity of perfectly nonlinear Boolean functions, (iii) the formula size of Boolean functions that satisfy the PC of degree 1, (iv) the area-time-square complexity of VLSI circuits computing perfectly nonlinear Boolean functions, (v) the OBDD size perfectly nonlinear Boolean functions.