Complexity of Boolean Functions Satisfying the Propagation Criterion

Shouichi HIROSE  Katsuo IKEDA  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E78-A   No.4   pp.470-478
Publication Date: 1995/04/25
Online ISSN: 
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>>
Buy this Article

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.