Efficient Algorithm of Affine Form Searching forWeakly Specified Boolean Function

Article type: Research Article

Authors: Porwik, Piotr

Affiliations: Institute of Informatics University of Silesia Bedzinska 39, 41-200 Sosnowiec, Poland. E-mail: porwik@us.edu.pl

Abstract: This paper presents the spectralmethod of recognition of an incompletely defined Boolean function. The main goal of analysis is fast estimation whether a given single output function can be extended to affine form. Furthermore, a simple extension algorithm is proposed for functions, for which the affine form is reachable. The algorithm is compared with other methods. Theoretical and experimental results demonstrate the efficiency of the presented approach.

Keywords: Walsh coefficients, coefficients distribution, incompletely defined Boolean function, affine function

Journal: Fundamenta Informaticae, vol. 77, no. 3, pp. 277-291, 2007