1.1 Threshold Gates

The basic function of a linear threshold gate (LTG) is to discriminate between labeled points (vectors) belonging to two different classes. An LTG maps a vector of input data, x, into a single binary output, y. The transfer function of an LTG is given analytically by (1.1.1)

where x = [x1 x2 ... xn]T and w = [w1 w2 ... wn]T are the input and weight (column) vectors, respectively, and T is a threshold constant. Figure 1.1.1 (a) shows a symbolic representation of an LTG with n inputs. A graphical representation of Equation (1.1.1) is shown in Figure 1.1.1 (b).  (a) (b)

Figure 1.1.1. (a) Symbolic representation of a linear threshold gate and (b) its transfer function.

The vector x in Equation (1.1.1) is n dimensional with binary or real components (i.e., x  {0, 1}n or x  Rn) and . Thus, the LTG output y may assume either of the following mapping forms: or An LTG performs a linear weighted-sum operation followed by a nonlinear hard clipping/thresholding operation, as described in Equation (1.1.1). Figure 1.1.2 shows an example LTG which realizes the Boolean function y given by: (1.1.2)

where x1 and x2 belong to {0, 1}. Equation (1.1.2) reads y = [(NOT x1) AND x2] OR [x2 AND (NOT x3)]. Here, the weight vector w = [1  2  1]T and threshold T = lead to a correct realization of y. One way of arriving at the solution for w and T is to directly solve the following set of eight inequalities:

0 < T w1 + w2  T

w1 < T w1 + w3 < T

w2  T w2 + w3  T

w3 < T w1 + w2 + w3 < T

These inequalities are obtained by substituting all eight binary input combinations (x1, x2, x3) and their associated y values from Equation (1.1.2), in Equation (1.1.1). For example, for input (x1x2x3) = (0, 0, 0), the output y [using Equation (1.1.2)] is given by y = 0. Hence, for a proper operation of the LTG, we require: 0w1 + 0w2 + 0w3 < T, which gives the first of the above eight inequalities: 0 < T. The other seven inequalities are obtained similarly for each of the remaining cases: (x1x2x3) = (0, 0, 1) through (1, 1, 1). It should be noted that the solution given in Figure 1.1.2 is one of an infinite number of possible solutions for the above set of inequalities. Figure 1.1.2. Example of an LTG realization of the Boolean function .

There exists a total of unique Boolean functions (switching functions) of n variables, there are 2n combinations of n independent binary variables which lead to unique ways of labeling these 2n combinations into two distinct categories (i.e., 0 or 1). It can be shown (see Section 1.2) that a single n-input LTG is capable of realizing only a small subset of these Boolean functions (refer to Figure 1.1.3). A Boolean function which can be realized by a single LTG is known as a threshold function. A threshold function is a linearly separable function, that is, a function with inputs belonging to two distinct categories (classes) such that the inputs corresponding to one category may be perfectly, geometrically separated from the inputs corresponding to the other category by a hyperplane. Any function that is not linearly separable, such as the exclusive-OR (XOR) function , cannot be realized using a single LTG and is termed a non-threshold function. Linear and non-linear separability are illustrated in Figure 1.1.4 (a) and (b), respectively. Figure 1.1.3. Pictorial representation depicting the set of threshold functions as a small subset of the set of all Boolean functions. (a) (b)

Figure 1.1.4. Linear versus non-linear separability: (a) Linearly separable function, and (b) non-linearly separable function. Filled circles and open squares designate points in the first class and second class, respectively.

Threshold functions have been exhaustively enumerated for small n (Cameron, 1960 ; Muroga, 1971) as shown in Table 1.1.1. This table shows the limitation of a single LTG with regard to the realization of an arbitrary Boolean function. Here, as , the ratio of the number of LTG-realizable Boolean functions, Bn, to the total number of Boolean functions approaches zero; formally, (1.1.3)

This result is verified in Section 1.2.
 n NUMBER OF THRESHOLD FUNCTIONS Bn TOTAL NUMBER OF BOOLEAN FUNCTIONS 1 4 4 2 14 16 3 104 256 4 1,882 65,536 5 94,572 4.3x109 6 15,028,134 1.8x1019 7 8,378,070,864 3.4x1038 8 17,561,539,552,946 1.16x1077

Table 1.1.1. Comparison of the number of threshold functions versus the number of all possible Boolean functions for selected values of n.

Although a single LTG cannot represent all Boolean functions, it is capable of realizing the universal NAND (or NOR) logic operation ( and ). Hence, the LTG is a universal logic gate; any Boolean function is realizable using a network of LTG's (only two logic levels are needed). Besides the basic NAND and NOR functions, though, an LTG is capable of realizing many more Boolean functions. Therefore a single n-input LTG is a much more powerful gate than a single n-input NAND or NOR gate.

For n 5, a Karnaugh map (or K-map) may be employed to identify thresholding functions or to perform the decomposition of nonthreshold functions into two or more factors, each of which will be a threshold function. This decomposition allows for obtaining an LTG network realization for Boolean functions as illustrated later in Section 2.1.1 of Chapter 2. Figure 1.1.5 shows the admissible K-map threshold patterns for n = 3. The K-map for the threshold function in Equation (1.1.2) is shown in Figure 1.1.6 along with its corresponding threshold pattern. Each admissible pattern may be in any position on the map, provided that its basic topological structure is preserved. Note that the complements of such patterns also represent admissible threshold patterns (refer to Example 1.2.1 in Section 1.2 for an example). Admissible patterns of Boolean functions of n variables are also admissible for functions of + 1 or more variables (Kohavi, 1978). Figure 1.1.5. Admissible Karnaugh map threshold patterns for n = 3. Figure 1.1.6. A Karnaugh map representation for the threshold function . The 1's of this function can be grouped as shown to form one of the threshold patterns depicted in Figure 1.1.5.

Given that for large n the number of threshold functions is very small in comparison to the total number of available Boolean functions, one might try to design a yet more powerful "logic" gate which can realize non-threshold functions. This can be accomplished by expanding the number of inputs to an LTG. For example, one can do this by feeding the products or ANDings of inputs as new inputs to the LTG. In this case, we require a fixed preprocessing layer of AND gates which artificially increases the dimensionality of the input space. We expect that the resulting Boolean function (which is now only partially specified) becomes a threshold function and hence realizable using a single LTG. This phenomenon is illustrated through an example (Example 1.2.1) given in the next section.

The realization of a Boolean function by the above process leads to a quadratic threshold gate (QTG). The general transfer characteristics for an n-input QTG are given by (1.1.4)

for , and (1.1.5)

for . Note that the only difference between Equations (1.1.4) and (1.1.5) is the range of the index j of the second summation in the double summation term. The bounds on the double summations in Equations (1.1.4) and (1.1.5) eliminate the wijxixj and wjixjxi duplications. QTG's greatly increase the number of realizable Boolean functions as compared to LTG's. By comparing the number of degrees of freedom (number of weights plus threshold) listed in Table 1.1.2, we find an increased flexibility of a QTG over an LTG.
 Threshold gate Number of degrees of freedom/parameters (including threshold) LTG QTG    Table 1.1.2. Comparison of the number of degrees of freedom in an LTG versus a QTG.

Although the QTG greatly increases the number of functions that can be realized, a single QTG still cannot realize all Boolean functions of n variables. Knowing that a second order polynomial expansion of inputs offers some improvements, it makes sense to extend this concept to r-order polynomials. This results in a polynomial threshold gate denoted PTG(r). Note that the LTG and QTG are special cases, where LTG PTG(1) and QTG PTG(2). The general transfer equation for a PTG(r) is given by (1.1.6)

In this case, the number of degrees of freedom is given by (1.1.7)

for , and (1.1.8)

for . Here, the term gives the number of different combinations of m different things, k at a time, without repetitions. The PTG appears to be a powerful gate. It is worthwhile to investigate its capabilities.

Goto [1.0] [1.2] [1.3] [1.4] [1.5] [1.6] [1.7] Back to the Table of Contents Back to Main Menu