Efficient spectral method of identification of linear Boolean function

• Autorzy: Porwik P.
• Języki publikacji: EN

Abstrakty

EN

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 important role in design of digital circuits. The analysis of the spectral coefficients' 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 Boolean function 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. Experimental results demonstrate the efficiency of the approach.

Słowa kluczowe

EN

Walsh coefficients; coefficients distribution; incompletely defined Boolean functions; linear Boolean function

PL

współczynnik Walsha; rozkład współczynników; niekompletnie zdefiniowana funkcja Boole'a; liniowa funkcja Boole'a

• Wydawca: Systems Research Institute, Polish Academy of Sciences
• Czasopismo: Control and Cybernetics
• Rocznik: 2004
• Tom: Vol. 33, no 4
• Strony: 663--678
• Opis fizyczny: Bibliogr. 23 poz., wykr,

Twórcy

autor

Porwik P.

• Institute of Informatics, Silesian University, Będzińska 39, 41-200 Sosnowiec, Poland,

Bibliografia

• Ahmed, N.and Rao, K.R. (1975) Orthogonal Transforms for Digital Signal Processing. Springer-Verlag. Berlin.
• Blahut, R.E. (1983) Theory and Practice in Error Control Codes. Addison-Wesley Publishing Company, London.
• Falkowski, B.J. and Porwik, P. (1999) Evaluation of Nonlinearity in Boolean Functions by Extended Walsh-Hadamard Transform. 2nd Int. Conf. on Information Communications and Signal Processing ICISC’99, Singapore paper 2B2.2, 1-4.
• Falkowski, B.J., Schafer, I. and Perkowski, M.A. (1992) Effective Computer Methods for the Calculation of Rademacher-Walsh Spectrum for Completely and Incompletely Specified Boolean Functions. IEE Tran. on Computer-Aided Design 11 (10), 1207-1226.
• Fujita, M. and Yang, J. (1995) Fast Spectrum Computation for Logic Functions using Binary Decision Diagrams. Int’l Symp. Circ. and Systems, 275-278.
• Harmuth, H.F. (1977) Sequency Theory. Foundations and Applications. Academic Press, New York.
• Hurst, S.L., Miller, D.M. and Muzio, J.C. (1985) Spectral Techniques in Digital Logic. Academic Press, London.
• Karpovsky, M.G. (1976) Finite Orthogonal Series in the Design of Design of Digital Devices. John Wiley, New York.
• Karpovsky, M.G., Stankovic, R.S. and Astola, J.T. (2003) Reduction of Size Decision Diagrams by Autocorrelation Functions. IEEE Trans. on Comp. 52 (5), 592-606.
• Maitra, S. and Sarkar, P. (2002) Cryptographically significant Bolean functions with five valued spectra. Theoretical Computer Science, 276, 133-146.
• Mister, S. and Adams, C. (1996) Practical S-Box Design. Workshop on selected areas in cryptography (SAC’96). Queen’s University Kingston, Ontario, Canada, 61-76.
• Porwik, P. and Falkowski, B.J. (1999) Informatics Properties of the Walsh Transform. 2nd Int. Conf. on Information Communications and Signal Processing ICISC’99, Singapore, paper 2B2.4, 1-5.
• Porwik, P. (2000) Towards Calculation of Boolean Functions Nonlinearity Using Walsh Transform. Arch. Theoret. Appl. Comp. Sci. Polish Acad. Sci.12 (1), 51-64.
• Porwik, P. (2002) Efficient calculation of the Reed-Muller forms by means of the Walsh spectrum. Int. Journal of Applied Mathematics and Computer Science 12 (4), 571-579.
• Porwik, P. (2000) Spectral modelling of digital systems with specified features. Prace Naukowe Uniwersytetu Śląskiego 1898, Katowice (in Polish).
• Porwik, P. (2003) The Spectral Test of the Boolean Function Linearity. Journal of Applied Mathematics and Computer Science 13 (4), 567-575.
• Sasao, T. (1993) Logic Synthesis and Optimalization. Kluwer Academic Publishers, Dordrecht, Holland.
• Seberry, J. and Zhang, X.M. (1994) Construction of Bent Function from Two Known Bent Functions. Australasian Journal of Combinatorics 9, 21-34.
• Somenzi, F. (2004) BDD Package. CUDD v.2.3.0. http://vlsi.colorado.edu/ ̃fabio/CUDD/cuddIntro.html
• Stankovic, R. and Falkowski, B. (2002) Spectral Transform Calculation through Decision Diagrams.VLSI Design 14 (1), 5-12.
• Thornton, M. and Drechsler, R. (2001) Spectral Decision Diagrams Using Graph Transformations. Int. Conf. Design, Automation and Test in Europe, Munich, Germany, 713-719.
• Wegener, I. (2000) Branching Programs and Dinary Decision Diagrams. SIAM Monographs on Discrete Mathematics and Applications, Philadelphia.
• Yang, C. and Ciesielski, M. (2002) BDS: A BDD-based logic optimization system. IEEE Trans. CAD 21 (7), 866-876.