Efficient calculation of the Reed-Muller form by means of the Walsh transform

Piotr Porwik

International Journal of Applied Mathematics and Computer Science (2002)

  • Volume: 12, Issue: 4, page 571-579
  • ISSN: 1641-876X

Abstract

top
The paper describes a spectral method for combinational logic synthesis using the Walsh transform and the Reed-Muller form. A new algorithm is presented that allows us to obtain the mixed polarity Reed-Muller expansion of Boolean functions. The most popular minimisation (sub-minimisation) criterion of the Reed-Muller form is obtained by the exhaustive search of all the polarity vectors. This paper presents a non-exhaustive method for Reed-Muller expansions. The new method allows us to build the Reed-Muller form based on the analysis of Walsh-Hadamard coefficients. The presented method has much less complexity than the procedures which have been applied until now. Both the transforms and the presented Walsh-Hadamard spectral characterization of the Reed-Muller expansion are compared. An analysis of the properties of the spectra obtained from these transforms is made.

How to cite

top

Porwik, Piotr. "Efficient calculation of the Reed-Muller form by means of the Walsh transform." International Journal of Applied Mathematics and Computer Science 12.4 (2002): 571-579. <http://eudml.org/doc/207613>.

@article{Porwik2002,
abstract = {The paper describes a spectral method for combinational logic synthesis using the Walsh transform and the Reed-Muller form. A new algorithm is presented that allows us to obtain the mixed polarity Reed-Muller expansion of Boolean functions. The most popular minimisation (sub-minimisation) criterion of the Reed-Muller form is obtained by the exhaustive search of all the polarity vectors. This paper presents a non-exhaustive method for Reed-Muller expansions. The new method allows us to build the Reed-Muller form based on the analysis of Walsh-Hadamard coefficients. The presented method has much less complexity than the procedures which have been applied until now. Both the transforms and the presented Walsh-Hadamard spectral characterization of the Reed-Muller expansion are compared. An analysis of the properties of the spectra obtained from these transforms is made.},
author = {Porwik, Piotr},
journal = {International Journal of Applied Mathematics and Computer Science},
keywords = {Boolean function; coefficient distribution; Walsh coefficients; synthesis of Boolean functions; Reed-Muller coefficients; logic synthesis; Walsh transform; Boolean functions},
language = {eng},
number = {4},
pages = {571-579},
title = {Efficient calculation of the Reed-Muller form by means of the Walsh transform},
url = {http://eudml.org/doc/207613},
volume = {12},
year = {2002},
}

TY - JOUR
AU - Porwik, Piotr
TI - Efficient calculation of the Reed-Muller form by means of the Walsh transform
JO - International Journal of Applied Mathematics and Computer Science
PY - 2002
VL - 12
IS - 4
SP - 571
EP - 579
AB - The paper describes a spectral method for combinational logic synthesis using the Walsh transform and the Reed-Muller form. A new algorithm is presented that allows us to obtain the mixed polarity Reed-Muller expansion of Boolean functions. The most popular minimisation (sub-minimisation) criterion of the Reed-Muller form is obtained by the exhaustive search of all the polarity vectors. This paper presents a non-exhaustive method for Reed-Muller expansions. The new method allows us to build the Reed-Muller form based on the analysis of Walsh-Hadamard coefficients. The presented method has much less complexity than the procedures which have been applied until now. Both the transforms and the presented Walsh-Hadamard spectral characterization of the Reed-Muller expansion are compared. An analysis of the properties of the spectra obtained from these transforms is made.
LA - eng
KW - Boolean function; coefficient distribution; Walsh coefficients; synthesis of Boolean functions; Reed-Muller coefficients; logic synthesis; Walsh transform; Boolean functions
UR - http://eudml.org/doc/207613
ER -

References

top
  1. Breuer M.A. and Friedman A.D. (1976): Diagnosis and Reliable Design of Digital Systems. - Potomac, Maryland: Computer Science Press. Zbl0378.94028
  2. Damarla T.R. and Karpovsky M. (1989): Fault detection in combinational networks by Reed-Muller transforms. - IEEE Trans. Comp., Vol. 38, No. 6, pp. 788-797. 
  3. Falkowski B.J. and Chang C.H. (2000): Minimisation of k-variable mixed-polarity Reed-Muller expansions. - VLSI Design, Vol. 11, No. 4, pp. 311-320. 
  4. Falkowski B.J. and Chang C.H. (1995): An exact minimizer of fixed polarity Reed-Muller expansion. - Int. J. Electron., Vol. 79, No. 3, pp. 389-409. 
  5. Falkowski B.J. and Chang C.H. (1999): Hadamard-Walsh spectral characterization of Reed-Muller expansions. - Comp. Electr.Eng., No. 25, pp. 111-134. 
  6. 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. 
  7. Giani A., Sheng S., Hsiao M.S. and Agraval V.D. (2001): Efficient spectral techniques for sequential ATPG. - Proc. Int. Conf. IEEEs Design Automation Test in Europe, Munich, Germany, pp. 204-208. 
  8. Hurst S.L., Miller D.M. and Muzio J.C. (1985): Spectral Techniques in Digital Logic. - London: Academic Press. 
  9. Karpovsky M.G. (1976): Finite Orthogonal Series in the Design of Digital Devices. - New York: Wiley. Zbl0336.94017
  10. Karpovsky M.G. (1985): Spectral Techniques and Fault Detection. - London: Academic Press. Zbl0625.00027
  11. Micheli De G. (1994): Synthesis and Optimization of Digital Circuits. - Boston: McGraw-Hill. 
  12. Perkowski M. (1996): A unified approach to exor-based representation of Boolean functions. - Proc. XIX Nat. Conf. Circuit Theory and Electronics Circuits, Krynica, Poland, Vol. 1, pp. 27-41. 
  13. Porwik P. (1996): Fault path detection using a spectral method. - Proc. Int. Baltic Electronic Conference, BEC'96, Tallin, Estonia, pp. 315-318. 
  14. Porwik P. and Falkowski B.J. (1999): Informatics properties of the Walsh transform. - Proc. 2-nd Int. Conf. Information Communications and Signal Processing, ICISC'99, Singapore, paper 2B2.4, pp. 1-5. 
  15. Sasao T. (1993): Logic Synthesis and Optimalization. - Dordrecht: Kluwer. 
  16. Sasao T. (1995): Representation of logic functions using EXOR operators. - Proc. Workshop Applications of the Read-Muller Expansion in Circuit Design, Makuhari, Japan, pp. 308-313. 
  17. Yanushkevich S. (1998): Logic Differential Calculus in Multi-Valued Logic Design. - Szczecin, Poland: Technical University Press. 

NotesEmbed ?

top

You must be logged in to post comments.