Efficient spectral method of identification of linear Boolean function
Piotr Porwik · Control and Cybernetics · 2004
This paper discusses a problem of recognition of the Boolean function's linearity. The article describes the spectral method of analysis of incompletely specified Boolean functions using the Walsh Transform. The linearity and nonlinearity play an impor- tant role in design of digital circuits. The analysis of the spectral co- efficients' distribution allows to determine the various combinatorial properties of the Boolean functions: redundancy, monotonicity, self- duality, correcting capability, etc. which seems to be more difficult to obtain by means of other methods. In particular, the distribution of spectral coefficients allows us to determine whether Booleanfunction is linear. The method described in the paper can be easily used in investigations of large Boolean functions (of many variables), what seems to be very attractive for modern digital technologies. Exper- imental results demonstrate the efficiency of the approach.