Nonlinearity of incomplete Boolean functions: prioritizing spectra calculation

• Autorzy: Porwik Piotr

Identyfikatory

DOI

10.24425/acs.2022.143666

• Języki publikacji: EN

Abstrakty

EN

In this paper, a class of linear Boolean functions is analyzed. The Boolean function can be represented as disjoint cubes or in the form of a truth vector. The primary purpose of this analysis is to decide whether an incompletely defined function can be extended to a complete linear form. A simple algorithm for generating all states of this function has been proposed if the Boolean function can have a full representation. The algorithm is beneficial for large functions. The proposed approach can be applied to completely and incompletely defined Boolean functions.

Słowa kluczowe

EN

Boolean function; numerical methods; Walsh transform

• Wydawca: Polish Academy of Sciences, Committee of Automatic Control and Robotics
• Czasopismo: Archives of Control Sciences
• Rocznik: 2022
• Tom: Vol. 32, No. 4
• Strony: 663--676
• Opis fizyczny: Bibliogr. 17 poz., rys., tab., wzory

Twórcy

autor

Porwik Piotr

• Faculty of Science and Technology, University of Silesia, Będzińska 39, 41-200 Sosnowiec, Poland

Bibliografia

• [1] N.U. Ahmed and K.R. Rao: Orthogonal Transforms for Digital Signal Processing. Springer-Verlag, Berlin, Heidelberg, 1975. DOI: 10.1007/978-3-642-45450-9.
• [2] M. Andrecut: On the inherent competition between valid and spurious inductive inferences in boolean data. International Journal of Modern Physics C, 28(12), (2017), 1750146. DOI: 10.1142/S0129183117501467.
• [3] T. Ayav: Prioritizing MCDC test cases by spectral analysis of boolean functions. Software Testing, Verification and Reliability, 27:e1641, 08 (2017). DOI: 10.1002/stvr.1641.
• [4] E. Bellini: Yet another algorithm to compute the nonlinearity of a boolean function. arXiv.org, 2014. DOI: 10.48550/arXiv.1404.2471.
• [5] E. Bellini, M. Sala, and I. Simonetti: Nonlinearity of boolean functions: An algorithmic approach based on multivariate polynomials. Symmetry, 14(2(213)) (2022). DOI: 10.3390/sym14020213.
• [6] L. Budaghyan, C. Carlet, T. Helleseth, and A. Kholosha: Generalized bent functions and their relation to Maiorana-McFarland class. In Proceedings of the 2012 IEEE International Symposium on Information Theory, ISIT 2012, Cambridge, MA, USA, July 1-6, 2012, pages 1212-1215. IEEE, 2012. DOI: 10.1109/ISIT.2012.6283049.
• [7] R. de Wolf: A Brief Introduction to Fourier Analysis on the Boolean Cube. Number 1 in Graduate Surveys. Theory of Computing Library, 2008. DOI: 10.4086/toc.gs.2008.001.
• [8] B. Falkowski, I. Shefer, and M. Perkowski: Fast computer algorithm for the generation of disjoint cubes for completely and incompletely specified boolean functions. Proc. 33rd Midwest Symp. on Circuits and Systems, pages 1119-1122, 1990. DOI: 10.1109/MWSCAS.1990.140922.
• [9] B.J. Falkowski, I. Schafer, and C.-H. Chang: An effective computer algorithm for the calculation of disjoint cube representation of boolean functions. Proceedings of 36th Midwest Symposium on Circuits and Systems, pages 1308-1311 vol. 2, 1993. DOI: 10.1109/MWSCAS.1993.343341.
• [10] M. Karpovski: Finite Orthogonal Series in the Design of Digital Devices: Analysis, Synthesis, and Optimization. A Halsted Press book. Wiley, 1976.
• [11] D.M. Miller and M. Soeken: An algorithm for linear, affine and spectra classification of boolean functions. In Advanced Boolean Techniques, pages 195-215. Springer, 2020. DOI: 10.1007/978-3-030-20323-8_9.
• [12] P. Porwik: Efficient spectral method of identification of linear boolean function. Int. Journal Control and Cybernetics, 33(4), (2004), 663-678.
• [13] B. Steinbach and C. Posthoff: Logic Functions and Equations. Springer Netherlands, 2009. DOI: 10.1007/978-1-4020-9595-5.
• [14] E. Uyan, Çaǧdaş Çalik, and A. Doǧanaksoy: Counting boolean functions with specified values in their walsh spectrum. Journal of Computational and Applied Mathematics, 259 (2014), 522-528. DOI: 10.1016/j.cam.2013.06.035.
• [15] R. Wang: Introduction to Orthogonal Transforms: With Applications in Data Processing and Analysis. Cambridge University Press, 2012. DOI: 10.1017/CBO9781139015158.
• [16] A. Younes: A fast quantum algorithm for finding the coefficients of the affine linear boolean function. arXiv.org, July 2014. DOI: 10.48550/arXiv.1407.6402.
• [17] A. Younes: A fast quantum algorithm for the affine boolean function identification. Eur. Phys. J. Plus, 130(2), (2015), 34. DOI: 10.1140/epjp/i2015-15034-4.

Uwagi

Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2022-2023)