Simulating the classical log-depth, AND, OR, NOT circuits for threshold gates

Figure 1:A threshold gate

As Figure 1 shows, the input for the threshold gate is a 0-1 vector of A=(a₁, a₂,...,a_n) and a threshold value k, the output is a 0/1 value, which is:

   if  (a1+a2+...+an >= k)  then

      Output = 1

   else

      Output = 0

The value of the above threshold gate T^{a1, a2,..,an}_k can be evaluated in the following recursive way:

• T^{a1, a2,...,an}_k = T^{a1, a2,...,an/2}₀ AND T^{a(n/2+1), a(n/2+2),...,an}_k OR T^{a1, a2, ... ,an/2}₁ OR T^{a(n/2+1),a(n/2+2),...,an}_k-1 OR ... OR T^{a1, a2,...,an/2}_k AND T^{a(n/2+1), a(n/2+2),...,an}₀
• Tⁿ₀...= 1
• T^a1,a2,...,aj_i = 0    if j>i

Thus, we can construct a circuit with classical AND and OR gates to simulate a threshold gate. It is easy to see that the depth of this evaluation is log(n). We use the above algorithm to implement our program.

In this implementation, we use three classes. A CAND class is used for defining and operating a classical AND gate. Similarly, a COR class is created for OR gate. Finally, a CThreshold class is used for describing a threshold gate. We first construct a classical circuit consist of AND and OR gates for threshold gate. Then given input bits and a threshold value m, we evaluate the circuit and output the result.