A Hybrid Method for Spectral Translation Equivalent Boolean Functions

The equivalence of Boolean functions with respect to five invariance (aka translation) operations has been well considered with respect to the Rademacher-Walsh spectral domain. In this paper, we introduce a hybrid approach that uses both the Reed-Muller and the Rademacher-Walsh spectra. A novel hybrid algorithm that maps a Boolean function to a representative function for the equivalence class containing the original function is presented. The algorithm can be used to determine a sequence of translations that maps one function to an equivalent function. We present experimental results that show the hybrid algorithm can determine the equivalence classes for 5 variables much more efficiently than before. We also show that for 6 variables where there are 150,357 equivalence classes, 8 are very difficult, a further 58 are difficult and the remainder are straightforward in terms of the CPU time required by the hybrid algorithm.


Published in:
[2019 IEEE Pacific Rim Conference on Communications, Computers and Signal Processing]
Presented at:
2019 IEEE Pacific Rim Conference on Communications, Computers and Signal Processing, Victoria, Canada, August 21-23, 2019
Year:
Aug 21 2019
Publisher:
IEEE
Laboratories:




 Record created 2019-09-30, last modified 2019-10-02

Fulltext:
Download fulltext
PDF

Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)