200
D. M. Miller and M. Soeken
Table 9.1 Function
classification schemes
Classification Translations
NPN
1, 2, 3
Linear
1, 4
Affine
1, 2, 4
Spectral
1, 2, 3, 4, 5
Table 9.2 Equivalence class sizes
n
Functions
NPN [5]
Linear [10]
Affine [10]
Spectral [8, 12]
1
4
2
4
3
1
2
16
4
8
5
2
3
256
14
20
10
3
4
65,536
222
92
32
8
5
4.3 × 10 9
616,126
2,744
382
48
6
1.8 × 10 19
2.0 × 10 14
9.5 × 10 8
1.5 × 10 7
150,357
The problem addressed in this paper can be stated as follows:
Problem Statement: Given a Boolean function f (with spectrum S) find a low
cost sequence of spectral translations that transforms f to the representative
function f R (with spectrum S R ) of the equivalence class that contains f for
linear, affine or spectral classification.
The cost of a sequence of translations depends on the cost model used. If
all translations are assumed to have unit cost, the cost is simply the number of
translations. Assigning 0 cost to each translation means that any sequence leading
to f R is equally acceptable. In this paper we use the following costs:
– Translation 1 interchanges 2 variables and requires a swap gate which can be
implemented using 3 XOR gates. We thus assume a cost of 3.
– Translations 2 and 3 each require a single NOT gate to implement an inversion
and we use a cost of 1.
– Translations 4 and 5 each require a single XOR gate and again we use a cost of
1.
Note that alternative cost models including a model where the cost of a
translation varies by context can be used. For reversible or quantum circuits the
XOR gates mentioned above are implemented as controlled-NOT (CNOT) gates
[13].
Given an algorithm to transform f to f R , it is possible to find the equivalence
classes for n variables, at least for small n, by applying it to all 2 2 n functions and
keeping track of the unique f R encountered. Such a transformation algorithm can
also be applied to map an n variable function to its canonical form for subsequent
synthesis.
D. M. Miller and M. Soeken
Table 9.1 Function
classification schemes
Classification Translations
NPN
1, 2, 3
Linear
1, 4
Affine
1, 2, 4
Spectral
1, 2, 3, 4, 5
Table 9.2 Equivalence class sizes
n
Functions
NPN [5]
Linear [10]
Affine [10]
Spectral [8, 12]
1
4
2
4
3
1
2
16
4
8
5
2
3
256
14
20
10
3
4
65,536
222
92
32
8
5
4.3 × 10 9
616,126
2,744
382
48
6
1.8 × 10 19
2.0 × 10 14
9.5 × 10 8
1.5 × 10 7
150,357
The problem addressed in this paper can be stated as follows:
Problem Statement: Given a Boolean function f (with spectrum S) find a low
cost sequence of spectral translations that transforms f to the representative
function f R (with spectrum S R ) of the equivalence class that contains f for
linear, affine or spectral classification.
The cost of a sequence of translations depends on the cost model used. If
all translations are assumed to have unit cost, the cost is simply the number of
translations. Assigning 0 cost to each translation means that any sequence leading
to f R is equally acceptable. In this paper we use the following costs:
– Translation 1 interchanges 2 variables and requires a swap gate which can be
implemented using 3 XOR gates. We thus assume a cost of 3.
– Translations 2 and 3 each require a single NOT gate to implement an inversion
and we use a cost of 1.
– Translations 4 and 5 each require a single XOR gate and again we use a cost of
1.
Note that alternative cost models including a model where the cost of a
translation varies by context can be used. For reversible or quantum circuits the
XOR gates mentioned above are implemented as controlled-NOT (CNOT) gates
[13].
Given an algorithm to transform f to f R , it is possible to find the equivalence
classes for n variables, at least for small n, by applying it to all 2 2 n functions and
keeping track of the unique f R encountered. Such a transformation algorithm can
also be applied to map an n variable function to its canonical form for subsequent
synthesis.