Efficient spectral method for disjoint bi-decompositions of Boolean functions

A method has been developed to find disjoint bi-decomposition of Boolean functions. From the knowledge of a subset of Walsh spectrum for a Boolean function and by checking some preliminary conditions, the new algorithm is applied to identify the type of bi-decomposition and its existence. All three types of bi-decomposition are considered including OR, AND and EXOR type. The new method is very efficient by using a filtering procedure that establishes quickly the lack of bi-decomposition from the knowledge of just a few Walsh spectral coefficients. The type of bi-decomposition and affirmation/negation of variables in its logic sub-functions are directly identified by manipulation on the reduced cubical representation of Boolean functions and their corresponding Walsh spectra