Del2: Simulating log-depth
threshold circuits for multiplication
1 Program description
This program simulates threshold circuits for multiplication
on two 5-bit numbers. Given two numbers in 5-bit binary form, the program
constructs a circuit consisting of only threshold gates. This circuit
calculates the multiple of these two numbers. It has depth of O(log
n),
and size of O(n), where n is the number of bits for each
input.
2 Background
We will use the following problem definition.
- Problem: ADD
Input: two n bit numbers a =
an-1 ...a0 and b = bn-1...
b0
Output: s
= sn...s0, s =def a + b
- Problem: ITADD
Input: n numbers in binary
with n bits each
Output: the sum of the input
numbers in binary
- Problem: LOGITADD
Input: log n numbers with n
bits each
Output: the sum of the input
numbers in binary
- Problem: BCOUNT
Input: n
bits an-1,...,a0
Output:
the sum of ai, where i from 0 to n
- Problem: MULT
Input: two
n bit numbers
Output:
the product of the input numbers in binary
- Problem: Tnm
Input: two n
bits numbers an-1,..., a0, wn-1,...,
w0, and
a threshold m (m
is an integer and 0<m<n)
Output:
1 if an-1*wn-1 +...+a0*w0 >= m;
|
0 otherwise
|
3 Algorithm
Given two n bit numbers a = an-1 ...a0
and b = bn-1 ...b0, first, we can
reduce
MULT to ITADD by using the school method for multiplication.
Define
- ci = 0n-i-1an-1...
a1a00i,
if bi = 1; 02n-1otherwise.
Then the product of a, b is the sum of ci, where
0<=i<n. Now our problem turns
out
to solve ITADD.
Given the above ci we define for every position k,
0<=k<2n-1, the sum
sk =
Σ i=0n-1ci,k. Every
sk
can be written in binary using no more than log(n) bits, so we have
Σi=0n-1ci,k
= Σj=0log(n)-1sk,j *
2j
Therefore,
Σi=0n-1 ci=
Σj=0n-1
Σj=0n-1 sk,j*2j
= Σ
j=0log(n)-1 Σj=0n-1
sk,j*2j*2k.
Notice that the problem of counting each sk is a
BCOUNT problem. Thus we can reduce the problem of adding n numbers to that
of
adding log(n) numbers
Σk=0n-1sk,j *2j+k,
where 0<=k<log(n).
Each of these numbers has no more than n+log(n) bits. We can
iterate
this procedure, that is, continue to add the above log(n) numbers
using
the same method, next time we get log(log(n)) numbers with
n+log(n
)+log(log(n)) bits, and so on. After x iterations, where
x is
the smallest number such that logx+1n<=2,
we have 2 numbers at the end, we
can add them using a constant depth circuit described in [Vol00].
Next, we reduce BCOUNT to Tnm.
Let l = log(n),
Σi=0n-1si
= sl-1 ... s0 in binary.
Let 0<=j<log(n).
Let Rj be the set of those numbers r ∈{0, ...,
n}
whose j-th bit is on (where the 0th bit is the
rightmost bit, and the (l-1)th bit is the leftmost bit). We have,
Sj = ∪r ∈Rj
(Σi=0n-1si = r).
Obviously,
(x = r) = (x >= r) AND NOT( x >= r+1)
thus,
Sj = ∪r ∈ Rj
(Tnr (a1, ...,
an)
Tnr+1 (a1, ..., an)).
Observe that the set
Rj
do not depend on the input value but only on the input length n and
thus
can be hardwired into the circuit. Now we have a circuit for BCOUNT which
uses
(Tnr) n ∈
N and (Tnr+1) n ∈N
gates.
To construct a multiplication
circuit we also need to use the NOT, AND, OR gates. It is easy to see
that:
AND = Tnn
(wi = 1, where 0<=i<n)
OR = Tn1
(wi= 1, where 0<=i<n)
NOT = T10 (w = -1)
Based on the above reductions, we can construct a circuit for MULT
with only threshold gates.
4 Design and Implementation
Overall circuit design
Given two 5-bit numbers, to calculate the product, our
program first generates a circuit, the inputs for this circuit are two
5-bit numbers.
The evaluation is the process of calculation, and the evaluation result is
the
multiple of two numbers. The program generates the circuit only once,
after
each evaluation (calculation), it can reset the circuit for next
evaluation.
Figure 1 shows this multiplication circuit.
|
Figure 1. Circuit for
calculating the product of two five bits binary numbers
|
The depth of the circuit is seven. In first five levels we
prepare ci,k (where 0<=i<n, 0<=k<2n-1), then we send
ci,k
to the sixth level, that is, five numbers with nine bits each need to be
added.
Level six contains nine BCOUNT gates, where each gate has five input and
three
output bits. After applying level six, we have three numbers with nine
bits
each. We now send them to the seventh layer, which consists of 11 BCOUNT
gates
with three inputs and two outputs each. After this level, we get two
13-bit
numbers. Adding two binary numbers can be done by a constant depth circuit
that
is described in [Vol00].
In Figure 1, the constructed circuit for MULT is made up of
BCOUNT gates with five or three input bits. Each BCOUNT gate can be
construct
by a constant depth circuit including threshold, AND, OR, and NOT gates.
Figure
2 illustrates the construction of a five inputs and three outputs BCOUNT
gate
using threshold, AND, OR gated. Figure 3 illustrates the construction of a
three inputs and two outputs BCOUNT gate using threshold, AND, OR gated.
We can
further replace each AND, OR, NOT gate with threshold gates as described
in section 3.
|
Figure 2 BCOUNT circuit with five inputs and three outputs
|
|
Figure 3 BCOUNT circuit with three inputs and two outputs
|
Given two n bit numbers, according to
our circuit construction, we need log*(n) layers of BCOUNT gates.
Each
layer can be implemented by a constant depth threshold circuit. Thus the
total
depth of the threshold circuit for multiplication is O(log*(n)).
Program organization
Basically, three structures are designed: pin, threshold and
blkbox structure.
- In pin structure, we record input and output
information using link-lists respectively. Each element of a
link-list is
a pointer that points to a pin.
- A threshold gate has input and output pins,
and its k of threshold value.
- A blkbox is a structure made of input pins,
output pins, and internal threshold gates. We can set
different
blkbox structures to implement AND, OR, NOT, or BCOUNT gates.
Having all these elements, we can finally construct our
circuit for multiplication. Figure 4 shows our program organization
|
Figure 4 Program organization diagram |
5 Test result
A test program is written, which
takes the circuit as its input and evaluate step-by-step the status and
value
of the threshold gates. Because this circuit is only calculating the
multiple
of two 5-bit binary numbers, it is possible to verify each possible input
and the evaluation result. My evaluations show that my circuit correctly
computed the product of two 5-bit numbers in constant time.
6 References:
[Vol00] Introduction to Circuit
Complexity. H.Vollmer. Springer-Verlag. 1999.
7 Code
Here is a link to a directory containing my code
|