Dedicated spectral method of Boolean function decomposition

Piotr Porwik; Radomir Stankovic

International Journal of Applied Mathematics and Computer Science (2006)

  • Volume: 16, Issue: 2, page 271-278
  • ISSN: 1641-876X

Abstract

top
Spectral methods constitute a useful tool in the analysis and synthesis of Boolean functions, especially in cases when other methods reduce to brute-force search procedures. There is renewed interest in the application of spectral methods in this area, which extends also to the closely connected concept of the autocorrelation function, for which spectral methods provide fast calculation algorithms. This paper discusses the problem of spectral decomposition of Boolean functions using the Walsh transform and autocorrelation characteristics.

How to cite

top

Porwik, Piotr, and Stankovic, Radomir. "Dedicated spectral method of Boolean function decomposition." International Journal of Applied Mathematics and Computer Science 16.2 (2006): 271-278. <http://eudml.org/doc/207792>.

@article{Porwik2006,
abstract = {Spectral methods constitute a useful tool in the analysis and synthesis of Boolean functions, especially in cases when other methods reduce to brute-force search procedures. There is renewed interest in the application of spectral methods in this area, which extends also to the closely connected concept of the autocorrelation function, for which spectral methods provide fast calculation algorithms. This paper discusses the problem of spectral decomposition of Boolean functions using the Walsh transform and autocorrelation characteristics.},
author = {Porwik, Piotr, Stankovic, Radomir},
journal = {International Journal of Applied Mathematics and Computer Science},
keywords = {Boolean function; Walsh spectrum; autocorrelationcoefficients; disjoint decomposition},
language = {eng},
number = {2},
pages = {271-278},
title = {Dedicated spectral method of Boolean function decomposition},
url = {http://eudml.org/doc/207792},
volume = {16},
year = {2006},
}

TY - JOUR
AU - Porwik, Piotr
AU - Stankovic, Radomir
TI - Dedicated spectral method of Boolean function decomposition
JO - International Journal of Applied Mathematics and Computer Science
PY - 2006
VL - 16
IS - 2
SP - 271
EP - 278
AB - Spectral methods constitute a useful tool in the analysis and synthesis of Boolean functions, especially in cases when other methods reduce to brute-force search procedures. There is renewed interest in the application of spectral methods in this area, which extends also to the closely connected concept of the autocorrelation function, for which spectral methods provide fast calculation algorithms. This paper discusses the problem of spectral decomposition of Boolean functions using the Walsh transform and autocorrelation characteristics.
LA - eng
KW - Boolean function; Walsh spectrum; autocorrelationcoefficients; disjoint decomposition
UR - http://eudml.org/doc/207792
ER -

References

top
  1. Ahmed N. and Rao K.R. (1975): Orthogonal Transforms for Digital Signal Processing. - Berlin: Springer. Zbl0335.94001
  2. Ashenhurst R. (1957): The decomposition of switching functions. - Proc. Int. Symp.Theory of Switching, Annual Computation Laboratory, Harvard University, Vol. 29, pp. 74-116. 
  3. Dubrova E. (1999): AOXMIN-MV: A heuristic algorithm for AND-OR-XOR minimization. - Proc. Int. Workshop Applications of Reed-Muller Expansion in Circuit Design, RM'99, Victoria, Canada, pp. 37-53. 
  4. Curtis H.A. (1962): A New Approach to the Design of Switching Circuits. - Princeton: Van Nostrand. 
  5. Bertacco V. and Damiani M. (1997): The disjunctive decompositionof logic functions. - Proc. Computer-Aided Design, ICCAD'97, San Jose, CA, pp. 78-82. 
  6. Falkowski B.J. and Kannurao S. (2001): Analysis of disjunctive decomposition of balanced Boolean functions through Walsh spectrum. - IEE Proc. Comput. Digit. Techn., Vol. 148, No. 2, pp. 71-78. 
  7. Falkowski B.J. and Porwik P. (1999): Evaluation of nonlinearity in Boolean functions by extended Walsh-Hadamard transform. - Proc. 2nd Int. Conf. Information Communications and Signal Processing, ICISC'99, Singapore, paper 2B2.2, pp. 1-4. 
  8. Hurst S.L., Miller D.M. and Muzio J.C. (1985): Spectral Techniquesin Digital Logic. - London: Academic Press. 
  9. Karpovsky M.G. (1976): Finite Orthogonal Series in the Designof Design of Digital Devices. - New York: Wiley. Zbl0336.94017
  10. Karpovsky M.G., Stankovic R.S. and Astola J.T. (2003): Reduction of size decision diagrams by autocorrelation functions. - IEEE Trans. Comput., Vol. 52, No. 5, pp. 592-606. 
  11. Lai Y., Pedram M. and Vrudhula S. (1993): BDD based decompositionof logic function with application to FPGA synthesis. - Proc. 30-th Conf.Design Automation, DAC'93, Dallas, Texas, pp. 642-647. 
  12. MacWilliams F.J. and Sloane N.J. (1977): The Theory of Error-Correctiong Codes. - Amsterdam: Nord-Holland Publishing Company. Zbl0369.94008
  13. Mishchenko A., Steinbach B. and Perkowski M. (2001): Analgorithm for bi-decomposition of logic functions. - Proc. 38-th Conf. Design Automation, DAC'01, Las Vegas, NV, pp. 103-108. 
  14. Nowicka M., Rawski M. and Łuba T. (1999): DEMAIN - An interactive tool for FPGA-based logic decomposition. - Proc. 6-thInt. Conf. Mixed Design of Integrated Circuits and Systems, Cracow, Poland, pp. 115-120. 
  15. Porwik P. (2003): The spectral test of the Boolean function linearity. - Int. J. Appl. Math. Comput. Sci., Vol. 13, No. 4, pp. 567-575. Zbl1039.94017
  16. Porwik P. (2004a): Efficient spectral method of identification of linear Boolean function. - Int. J. Contr. Cybern., Vol. 33, No. 4, pp. 663-678. Zbl1167.94344
  17. Porwik P. (2004b): Walsh coefficients distribution for some types of Boolean function. - Arch. Theoret. Appl. Informat., Vol. 16, No. 2, pp. 109-120. 
  18. Rawski M., Jozwiak L. and L uba T. (2001): Functional decomposition with an efficient input support selection for sub-functions based on information relationship measures. - J. Syst. Archit., Vol. 47, Elsevier Science, pp. 137-155. 
  19. Rice J. and Muzio J.C. (2003): On the use of autocorrelation coefficients in the identification of three-level decompositions. - Proc. Int. Workshop Logic Synthesis, IWLS'03, Laguna Beach, CA, pp. 187-191. 
  20. Stanković R.S. and Astola J.T., (2003): Spectral Interpretation of Decision Diagram. - New York: Springer. Zbl1038.94002
  21. Stankovic R.S. and Falkowski B. (2002): Spectral transforms calculation trough decision diagrams. - VLSI Design.,Vol. 14, No. 1, pp. 5-12. 
  22. Sasao T. and Butler J.T. (1997): On bi-decomposition of logic functions. - Proc. Int. Workshop Logic Synthesis, Lake Tahoe, CA, Vol. 2, pp. 1-6. Zbl0883.11006
  23. Sasao T. and Matsuura M. (2004): A method to decompose multiple-output logic functions. - Proc. 41-th Conf. Design Automation, DAC'04, San Diego, CA, pp. 428-433. 
  24. Tokmen V.H. (1980): Disjoint decomposability of multi-valued functions by spectral means. - Proc. IEEE 10-th Int. Symp. Multiple-Valued Logic, New York, USA, pp. 88-93. 
  25. Tomczuk R. (1996): Autocorrelation and decomposition methods in combinational logic design. - Ph.D. thesis, University of Victoria, Victoria, Cadada. 
  26. Yanushkevich S. (1998): Logic Differential Calculus in Multi-Valued Logic Design. - Szczecin: Techn. University of Szczecin Academic Publishers, Poland. 
  27. Yaroslavsky L. (2003): Digital Image Processing. - Boston, MA: Kluwer Academic Publisher. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.