The spectral test of the Boolean function linearity

Piotr Porwik

International Journal of Applied Mathematics and Computer Science (2003)

  • Volume: 13, Issue: 4, page 567-575
  • ISSN: 1641-876X

Abstract

top
The paper discusses the problem of recognizing the Boolean function linearity. A spectral method of the analysis of Boolean functions using the Walsh transform is described. Linearity and nonlinearity play important roles in the design of digital circuits. The analysis of the distribution of spectral coefficients allows us to determine various combinatorial properties of Boolean functions, such as redundancy, monotonicity, self-duality, correcting capability, etc., which seems more difficult be performed by means of other methods. In particular, the basic synthesis method described in the paper allows us to compute the spectral coefficients in an iterative manner. The method can be easily used in investigations of large Boolean functions (of many variables), which seems very attractive for modern digital technologies. Experimental results demonstrate the efficiency of the approach.

How to cite

top

Porwik, Piotr. "The spectral test of the Boolean function linearity." International Journal of Applied Mathematics and Computer Science 13.4 (2003): 567-575. <http://eudml.org/doc/207668>.

@article{Porwik2003,
abstract = {The paper discusses the problem of recognizing the Boolean function linearity. A spectral method of the analysis of Boolean functions using the Walsh transform is described. Linearity and nonlinearity play important roles in the design of digital circuits. The analysis of the distribution of spectral coefficients allows us to determine various combinatorial properties of Boolean functions, such as redundancy, monotonicity, self-duality, correcting capability, etc., which seems more difficult be performed by means of other methods. In particular, the basic synthesis method described in the paper allows us to compute the spectral coefficients in an iterative manner. The method can be easily used in investigations of large Boolean functions (of many variables), which seems very attractive for modern digital technologies. Experimental results demonstrate the efficiency of the approach.},
author = {Porwik, Piotr},
journal = {International Journal of Applied Mathematics and Computer Science},
keywords = {bent functions; Boolean functions; linearity measure of a Boolean function; coefficients distribution; Walsh coefficients},
language = {eng},
number = {4},
pages = {567-575},
title = {The spectral test of the Boolean function linearity},
url = {http://eudml.org/doc/207668},
volume = {13},
year = {2003},
}

TY - JOUR
AU - Porwik, Piotr
TI - The spectral test of the Boolean function linearity
JO - International Journal of Applied Mathematics and Computer Science
PY - 2003
VL - 13
IS - 4
SP - 567
EP - 575
AB - The paper discusses the problem of recognizing the Boolean function linearity. A spectral method of the analysis of Boolean functions using the Walsh transform is described. Linearity and nonlinearity play important roles in the design of digital circuits. The analysis of the distribution of spectral coefficients allows us to determine various combinatorial properties of Boolean functions, such as redundancy, monotonicity, self-duality, correcting capability, etc., which seems more difficult be performed by means of other methods. In particular, the basic synthesis method described in the paper allows us to compute the spectral coefficients in an iterative manner. The method can be easily used in investigations of large Boolean functions (of many variables), which seems very attractive for modern digital technologies. Experimental results demonstrate the efficiency of the approach.
LA - eng
KW - bent functions; Boolean functions; linearity measure of a Boolean function; coefficients distribution; Walsh coefficients
UR - http://eudml.org/doc/207668
ER -

References

top
  1. Adams C.M. and Tavares S.E. (1990): Generating and counting binary bent sequences. - IEEE Trans. Inf. Th., Vol. IT-36, No. 5, pp. 1170-1173. Zbl0739.94012
  2. Ahmed N. and Rao K.R. (1975): Orthogonal Transforms for Digital Signal Processing. - Berlin: Springer. Zbl0335.94001
  3. Blahut R.E. (1983): Theory and Practice in Error Control Codes. - London: Addison-Wesley. Zbl0569.94012
  4. Clarke E.M., McMillan K.L., Zhao X. and Fujita M. (1993): Spectral transformation for extremely large Boolean functions.- Proc. IFIP WG 10.5 Workshop Applications of the Reed-Muller Expansion in Circuit Design, Hamburg, Germany, pp. 86-90. 
  5. Falkowski B.J. and Kannurao S. (2000): Spectral theory of disjunctive decomposition for balanced functions. - Proc. 13th Int.Conf. VLSI Design, Calcutta, India, pp. 100-105. 
  6. Harmuth H.F. (1977): Sequency Theory. Foundations and Applications. - New York: Academic Press. Zbl0521.94002
  7. Hurst S.L., Miller D.M. and Muzio J.C. (1985): Spectral Techniques in Digital Logic. - London: Academic Press. 
  8. Karpovsky M.G. (1976): Finite Orthogonal Series in the Design of Design of Digital Devices. - New York: Wiley. Zbl0336.94017
  9. Mister S. and Adams C. (1996): Practical S-box design. - Workshops Selected Areas in Cryptography, SAC'96, Queen's University Kingston, Ontario, Canada, pp. 61-76. 
  10. Porwik P. (2000a): Towards calculation of Boolean functions nonlinearity using Walsh transform. -Arch. Theoret. Appl. Comp. Sci.Polish Acad. Sci., Fasc. No. 1, Vol. 12, pp. 51-64. 
  11. Porwik P. (2000b): Spectral modelling of digital systems with specified features. - Sci. Works of the Silesian University No. 1898, Katowice (in Polish). 
  12. Porwik P. (2002): Efficient calculation of the Reed-Mullerforms by means of the Walsh spectrum. - Int. J. Appl. Math. Comp. Sci., Vol. 12, No. 4, pp. 571-579. Zbl1026.94556
  13. Porwik P. and Falkowski B.J. (1999): Informatics properties of the Walsh transform. - Proc. 2nd Int. Conf. Information Communications and Signal Processing, ICISC'99, Singapore, paper 2B2.4, pp .1-5. 
  14. Sasao T. (1993): Logic Synthesis and Optimization. -Dordrecht: Kluwer. 
  15. Sasao T. (1995): Representation of logic functions using EXOR operators. - Proc. Workshop Applications of the Reed-Muller Expansion in Circuit Design, Makuhari, Japan, pp. 308-313. 
  16. Seberry J. and Zhang X.M. (1994): Construction of bent function from two known bent functions. - Australasian J. Comb., Vol. 9, pp. 21-34. Zbl0802.05021

NotesEmbed ?

top

You must be logged in to post comments.