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
Aug 21 2019

Note: The status of this file is: Anyone

 Record created 2019-09-30, last modified 2020-04-20

Download fulltext

Rate this document:

Rate this document:
(Not yet reviewed)