9 An Algorithm for Linear, Affine and Spectral Classification of Boolean Functions
213
A key component in Fuller’s algorithm is the equivalence check. We use the
TRANSFORM algorithm proposed in this work for the linear, affine and spectral
cases in the manner described in the previous section.
For this experiment, we used an implementation of the TRANSFORM algorithm
inside the C++ truth table package kitty. 1 The experimental results were generated
using the example application spectral_enumeration_fuller on a laptop with an Intel
i5 2 Core processor running at 2.7 GHz and 8.0 GB RAM. The results are shown in
Table 9.9. The expected number of classes are produced in all cases—they are in
fact the same classes as reported in the previous section except for the linear case
for n = 5 where this time all 2744 classes were found.
The efficiency of this alternate approach is clear from the execution times shown
in Table 9.9 compared to those reported above in Tables 9.3 and 9.7. For example,
generating the affine classes for n = 5 takes 254.9 CPU sec. for the alternate
approach as compared to 11,036.6 CPU sec. for the NPN search approach, i.e. a
speedup of 43.3 times (Table 9.10).
9.7 Conclusion
In this work, we presented a single algorithm that can be used to identify the linear,
affine or spectral equivalence class of a Boolean function. For n ≤ 4, we showed that
the algorithm can be used to find the expected number of linear, affine and spectral
equivalence classes. For n = 5, we showed that starting from the NPN classes, the
algorithm can be used to find all affine and spectral classes, but because of not being
able to check all Boolean functions only 98.6% of the linear classes are found. We
also outlined an alternate approach that does efficiently find all linear, affine and
spectral classes for n ≤ 5 but without class size information.
We provided the representative functions for the classes for many cases and all
results, including those too extensive to include in this paper, are available on the
web. 2
A key facet of our approach is that the TRANSFORM algorithm identifies the
sequence of translations required to map a function to the representative function for
the equivalence class containing that function. Since the translations are self-inverse,
the algorithm can be used to find a sequence of translations to map a function to any
other function in the same equivalence class.
Our future work will concentrate on improving the efficiency of our implementation and on considering how to extend the function classification work to n > 5.
We also plan, now that we have a procedure for linear and affine classification to
consider those techniques in the synthesis of reversible and quantum circuits. We
1 https://github.com/msoeken/kitty.
2 www.cs.uvic.ca/~mmiller/fclasses.
213
A key component in Fuller’s algorithm is the equivalence check. We use the
TRANSFORM algorithm proposed in this work for the linear, affine and spectral
cases in the manner described in the previous section.
For this experiment, we used an implementation of the TRANSFORM algorithm
inside the C++ truth table package kitty. 1 The experimental results were generated
using the example application spectral_enumeration_fuller on a laptop with an Intel
i5 2 Core processor running at 2.7 GHz and 8.0 GB RAM. The results are shown in
Table 9.9. The expected number of classes are produced in all cases—they are in
fact the same classes as reported in the previous section except for the linear case
for n = 5 where this time all 2744 classes were found.
The efficiency of this alternate approach is clear from the execution times shown
in Table 9.9 compared to those reported above in Tables 9.3 and 9.7. For example,
generating the affine classes for n = 5 takes 254.9 CPU sec. for the alternate
approach as compared to 11,036.6 CPU sec. for the NPN search approach, i.e. a
speedup of 43.3 times (Table 9.10).
9.7 Conclusion
In this work, we presented a single algorithm that can be used to identify the linear,
affine or spectral equivalence class of a Boolean function. For n ≤ 4, we showed that
the algorithm can be used to find the expected number of linear, affine and spectral
equivalence classes. For n = 5, we showed that starting from the NPN classes, the
algorithm can be used to find all affine and spectral classes, but because of not being
able to check all Boolean functions only 98.6% of the linear classes are found. We
also outlined an alternate approach that does efficiently find all linear, affine and
spectral classes for n ≤ 5 but without class size information.
We provided the representative functions for the classes for many cases and all
results, including those too extensive to include in this paper, are available on the
web. 2
A key facet of our approach is that the TRANSFORM algorithm identifies the
sequence of translations required to map a function to the representative function for
the equivalence class containing that function. Since the translations are self-inverse,
the algorithm can be used to find a sequence of translations to map a function to any
other function in the same equivalence class.
Our future work will concentrate on improving the efficiency of our implementation and on considering how to extend the function classification work to n > 5.
We also plan, now that we have a procedure for linear and affine classification to
consider those techniques in the synthesis of reversible and quantum circuits. We
1 https://github.com/msoeken/kitty.
2 www.cs.uvic.ca/~mmiller/fclasses.