1.2 Computational Capabilities of Polynomial Threshold Gates

Next, we consider the capabilities of PTG's in realizing arbitrary Boolean functions. Let us start with a theorem which establishes the universality of a single n-input PTG(r) in the realization of arbitrary Boolean functions.

Theorem 1.2.1 (Nilsson, 1965; Krishnan, 1966): Any Boolean function of n-variables can be realized using a PTG of order r n.

The proof of this theorem follows from the discussion in Section 1.4. Theorem 1.2.1 indicates that r = n is an upper bound on the order of the PTG for realizing arbitrary Boolean functions. It implies that the most difficult n-variable Boolean function to implement by a PTG(r) requires r = n, and this may require parameters. So, in the worst case, the number of required parameters increases exponentially in n.

Winder (1963) gave the following upper bound on the number of realizable Boolean functions, Bn(r), of n variables by a PTG(r), r n (see Section 1.3.4 for details):

(1.2.1)

Where d is given by Equation (1.1.7) and

(1.2.2)

A couple of special cases are interesting to examine. The first is when r = n. From Theorem 1.2.1, any n-variable Boolean function is realizable using a single PTG(n). This means that the right hand side of Equation (1.2.1) should not exceed the number of n-variable Boolean functions, , if it is to be a tight upper bound. Indeed, this can be shown to be the case by first starting with Equation (1.2.1) and then finding the limit of C(2nd  1) as r approaches n. Since , we have

(1.2.3)

or

(1.2.4)

which is the desired result.

The other interesting case is for r = 1, which leads to the case of an LTG. Employing Equation (1.2.1) with d = + 1, n  2, gives the following upper bound on the number of n-input threshold functions:

(1.2.5)

It can be shown (Winder, 1963; see Problem 1.3.3) that a yet tighter upper bound on Bn(1) is . Equation (1.2.5) allows us to validate Equation (1.1.3) by taking the following limit:

(1.2.6)

Table 1.2.1 extends Table 1.1.1 by evaluating the above upper bounds on the number of threshold functions. Note that, despite the pessimistic fact implied by Equation (1.2.6), a single LTG remains a powerful logic gate by being able to realize a very large number of Boolean functions. This can be seen from the enumerated results in Table 1.2.1 (see the column labeled Bn(1)). In fact, Bn(1) scales exponentially in n as can be deduced from the following lower bound (Muroga, 1965)

(1.2.7)
Number of Threshold functions
Total number of Boolean functions
Upper bounds for

n



1
4
4
4
4
2
2
14
16
14
16
16
3
104
256
128
 170
512
4
1,882
65,536
3,882
 5461
65,536
5
94,572
4.3 x 109
412,736
 559,240
33,554,432
6
15,028,134
1.8 x 1019
1.5 x 108
1.9 x 108
6.9 x 1010
7
8,378,070,864
3.4 x 1038
1.9 x 1011
2.2 x 1011
5.6 x 1014
8
17,561,539,552,946
1.16 x 1077
8.2 x 1014
9.2 x 1014
1.8 x 1019

Table 1.2.1. Enumeration of threshold functions and evaluations of various upper bounds for n 8.

By its very definition, a PTG may be thought of as a two layer network with a fixed preprocessing layer followed by a high fan-in LTG. Kaszerman (1963) showed that a PTG(r) with binary inputs can be realized as the cascade of a layer of AND gates, each having a fan-in between two to r input lines, and a single LTG with inputs (representing the inputs received from the AND gates plus the original n inputs). The resulting architecture is shown in Figure 1.2.1.


Figure 1.2.1. PTG realization as a cascade of one layer of AND gates and a single LTG.

Example 1.2.1: Consider the XNOR function (also known as the equivalence function):


Using a Karnaugh map (shown in Figure 1.2.2), it can be verified that this function is not a threshold function; therefore, it cannot be realized using a single 2-input LTG (a diagonal pattern of 1's in the K-map is a non-threshold pattern and indicates a non-threshold/non-linearly separable function).


Figure 1.2.2. Karnaugh map of XNOR function

Since n = 2, Theorem 1.2.1 implies that a PTG(2) is sufficient; i.e., the QTG with three weights, shown in Figure 1.2.3, should be sufficient to realize the XNOR function.


Figure 1.2.3. A PTG(2) (or QTG) with binary inputs.

By defining , we can treat the PTG as a 3-input LTG and generate the K-map shown in Figure 1.2.4.


Figure 1.2.4. Karnaugh map for XNOR in expanded input space.

Since is defined as , there are some undefined states which we will refer to as "don't care" states; these states can be assigned either a 1 or 0, to our liking, and give us the flexibility to identify the threshold pattern shown in Figure 1.2.5 (this pattern is the complement of one of the threshold patterns shown in Figure 1.1.5, and therefore it is an admissible threshold pattern).


Figure 1.2.5. Karnaugh map after an appropriate assignment of 1's and 0's to the "don't care" states of the map in Figure 1.2.4.

The above K-map verifies that is realizable using a single LTG. The QTG in Figure 1.2.3 will realize the desired XNOR function with weight assignments as shown in Figure 1.2.6. Dertouzos (1965) describes a tabular method for determining weights for LTG's with small n. This method works well here, but will not be discussed. The topic of adaptive weight computation for LTG's is treated in Chapter Three.

Figure 1.2.6. Weight assignment for a QTG for realizing the XNOR function.

A geometric interpretation of the synthesized QTG may be obtained by first employing Equation (1.1.5), which gives

(1.2.8)

In arriving at this result, we took the liberty of interpreting the AND operation as multiplication. Note that this interpretation does not affect the QTG in Figure 1.2.6 when the inputs are in {0, 1}. Next, Equation (1.2.8) may be used to define a separating surface g that discriminates between the 1 and 0 vertices, according to

(1.2.9)

(here '' is the symbol for "defined as"). A plot of this function is shown in Figure 1.2.7, which illustrates how the QTG employs a nonlinear separating surface in order to correctly classify all vertices of the XNOR problem.








Figure 1.2.7. Separating surface realized by the QTG of Equation (1.2.9).

Another way of geometrically interpreting the operation of the QTG described by Equation (1.2.8) is possible if we define the product x1x2 as a new input x3. Now, we can visualize the surface of Equation (1.2.9) in 3-dimensions as a plane which properly separates the four vertices (patterns) of the XNOR function (see Problem 1.2.4 for an exploration of this idea).

Goto [1.0][1.1] [1.3] [1.4] [1.5] [1.6] [1.7]

Back to the Table of Contents

Back to Main Menu