Signed Digit Addition and Related Operations with Threshold Logic.
AbstractAssuming signed digit number representations, we investigate the implementation of some addition related operations assuming linear threshold networks. We measure the depth and size of the networks in terms of linear threshold gates. We show first that a depth-$2$ network with $O(n)$ size, weight, and fan-in complexities can perform signed digit symmetric functions. Consequently, assuming radix-$2$ signed digit representation, we show that the two operand addition can be performed by a threshold network of depth-$2$ having $O(n)$ size complexity and $O(1)$ weight and fan-in complexities. Furthermore, we show that, assuming radix-$(2n-1)$ signed digit representations, the multioperand addition can be computed by a depth-$2$ network with $O(n^3)$ size with the weight and fan-in complexities being polynomially bounded. Finally, we show that multiplication can be performed by a linear threshold network of depth-$3$ with the size of $O(n^3)$ requiring $O(n^3)$ weights and $O(n^2 \log n)$ fan-in.
Introduction
High performance addition and addition related operations, such as multiplication, play
an important role in the computer based computational paradigm. A major impediment
to improve the speed of arithmetic execution units incorporating addition and addition
related operations is the presence of carry and borrow chains. One solution for the elimination
of carry chains is the use of redundant representation of operands, proposed by
Avizienis in [1]. The Signed Digit (SD) number representation method allows, under certain
assumptions, the so called "totally parallel addition" [1], which limits the propagation
of the carries at the expense of some overhead in data storage space and in processing time
for the conversion of the results and potentially of the operands.
The redundant representation operates as follows. For any radix r - 2, a sign-digit
integer number represented with n digits has the algebraic
Each digit x i of the X number can assume its value in the digit
set \Sigma ffg. The cardinality of the set \Sigma r is 2ff
and the maximum digit magnitude ff must satisfies the relations stated in Equation (1) 1 .
In order to have minimum redundancy and as consequence minimum storage overhead
one can assume that
ri
but in order to break the carry chain, i.e., to have "totally
parallel addition", the value of ff should satisfy the relations stated in Equation (2).
Based on sign-digit representation, a number of high-speed architectures 2 have been re-
ported, see for example [2], [3], [4], [5], [6]. Thus far all the investigations in SD arithmetic
architectures assumed logic implementation with technologies that directly implement
Boolean gates. Currently other possibilities exist in VLSI for the implementation
of Boolean functions using threshold devices in CMOS technology [7], [8], [9], [10]. In
assuming Threshold Logic (TL) the basic processing element can be a Linear Threshold
1 Note that for a given radix r it might be that ff is not unique, therefore there can be more than one possible
digit set.
On-Line, and parallel.
Gate 3 (LTG) computing the Boolean function F (X) such that:
where the set of input variables and weights are defined by
and
Such a LTG contains a threshold value,
/, a summation device, \Sigma, computing F(X) and a threshold element, T , computing
Given that may be promising, it is of interest to investigate new schemes applicable
to such a new technology. To this end, assuming binary non-redundant representations, a
number of recent proposals regarding addition and multiplications, see for example [13],
[14], [15], [16], [17], [18], [19], [20], have been developed that assume threshold rather than
Boolean logic.
Thus far there are no studies assuming redundant representations and TL. In this paper
we assume SD number representation and we investigate linear threshold networks for
addition, multi-operand addition, and multiplication. We assume that the operands are
n-SD numbers and we are mainly concerned in establishing the limits of the circuit designs
using threshold based networks. We measure the depth and the size of the networks we
propose in terms of LTGs.
The main contributions of our proposal can be summarized as:
ffl Any SD symmetric function can be implemented by a depth-2 feed-forward Linear
Threshold Network (LTN) with O(n) size, weight and fan-in values.
ffl Assuming radix-2 redundant operand representation, the addition of two n-SD numbers
can be computed by a depth-2 LTN with O(n) size and O(1) weight and fan-in values.
Assuming operand representation the multi-operand addition
of n n-SD numbers can be computed by an explicit depth-2 LTN with the size in the order
of O(n 3 ), with the maximum weight value in the order of O(n 3 ), and the maximum fan-in
value in the order of O(n 2 ).
3 Such a threshold gate corresponds to the Boolean output neuron introduced in the McCulloch-Pitts neural
model [11], [12] with no learning features.
Assuming representation the multiplication of two n-SD numbers
can be computed by an explicit depth-3 LTN with the size in the order of O(n 3 ). The
maximum weight value is in the order of O(n 3 ) and the maximum fan-in value is in the
order of O(n 2 log n).
We also note here that while our results are primarily theoretical, there exist technology
proposals, see for example [10], which may implement at least some of the proposed
schemes, e.g., two operand addition.
The presentation is organized as follows: In Section 2 we discuss background information
on Boolean symmetric functions and their implementation with
preliminary results; In Section 3 we present schemes for the addition of radix-2
SD numbers; In Section 4 we study the multiplication of radix-2 SD numbers and we
present schemes for the multi-operand addition and the multiplication of
SD numbers; We conclude the presentation with some final remarks.
II. Background and Preliminaries
In order to make this presentation self consistent we introduce in this section the definition
of Boolean symmetric functions and some based implementation techniques that
we will use in our investigation.
Definition 1: A Boolean function of n variables F s is symmetric if and only if for any
permutation oe of !
For any n input variable symmetric Boolean function F s the sum
ranges from
(all input variables are 0) to n (all input variables are 1). Inside this definition domain
[0; n] there are r intervals [q
to 1 and outside these intervals the function is 0. This is graphically depicted in Figure 1
and formally described by Equation (4).
elsewhere
The number of intervals depends on the function definition and we proved elsewhere [21]
that for any Boolean symmetric function the maximum number of intervals r is upper
June 23, 1999
c
c
s
Fig. 1. Interval Based Representation of F s
bounded by d n+1e.
Definition 2: A Boolean function of n variables F gs is generalized symmetric 4 if it
entirely depends on
the weighted sum of its input variables, with w i ,
In essence a generalized symmetric Boolean function F gs is either a symmetric Boolean
function or a non symmetric Boolean function that can be transformed into a symmetric
Boolean function by trivial transformations, e.g., assignation of different weight values
to the inputs or input replication. F gs can be described as a function of
and the definition domain extends from [0; n] to [0; - max ], where -
. All the
results that stand true for symmetric Boolean functions can be applied also to generalized
symmetric Boolean functions.
To clarify the generalized symmetric Boolean function concept let consider the 4 2-
bit multi-operand addition producing a 4-bit result. The truth table and the schematic
diagram for such a function are depicted in Figure 2. First it can be observed that in order
to produce the sum at bit position 0 we need to consider only the bits in the first column
(LSB position). It can be easily verified that the Boolean function computing the sum's
because it can be clearly determined by the integer
value of
4 This definition and also Definition 1 are not specific to functions with Boolean input variables. The symmetry
is an intrinsic property of the function and do not depend on the input variable type. Therefore they apply also
to functions of other type of input variables, e.g., integer, real.
5 The weights w i can be also real numbers but we have assumed here integer values because of practical considerations
related to the LTG fabrication technology [7], [10].
Decimal
Sum
Binary Sum1y1 y0
2Fig. 2. 4 2-bit Multi-operand Addition
Fig. 3. Interval Based Representation of s 1
This property however does not hold
for the other sum bits. For example the Boolean function s 1
not a symmetric Boolean function as its value depends on the positioning of the inputs
and can not be always correctly determined from the x
value.
The s 1 function is however a generalized symmetric Boolean function as it can be made
to be a symmetric Boolean function if a weight of 2 is associated to the input bits in
the column 1. Consequently, the s 1 sum bit can be computed by a symmetric Boolean
function s 1 (-), where based
representation is graphically depicted in Figure 3.
Given that symmetric (generalized or not) functions constitute a frequently used class
of Boolean functions and because they are expensive to implement in hardware, in terms
of area and delay, their implementation with feed-forward LTNs have been the subject of
numerous theoretical and practical scientific investigations see for example [22], [23], [24],
[25], [16], [21].
The most network size efficient approach known so far for the depth-2 implementation of
symmetric Boolean function with TL is the telescopic sum method and it was introduced by
Minick in [23]. The method can be used for the implementation of any Boolean symmetric
function and produces depth-2 feed-forward LTNs with the size in the order of O(n),
measured in terms of LTGs, and with linear weight and fan-in values. We shortly describe
this method by introducing the following lemma.
Lemma 1: [Minick 0 61] Any Boolean symmetric function F s described
as in Equation (4), can be implemented by a two-layer feed-forward LTN with a size
complexity measured in terms of LTGs in the order of O(n) as follows:
r
where:
A formal proof of Lemma 1 and implementation examples can be found in [26].
Given that we assume SD operands (that is we consider functions with no Boolean input
variables) we need to map them into general Boolean functions. In order to achieve this
mapping we have first to choose a representation for the SDs. One possible representation
is the 2's complement [27] 6 .
Given a fixed radix r a SD number is represented as (s
presentation we will consider that any digit s i can assume a value in the symmetric 7 digit
set with the maximum digit magnitude ff satisfying
the Equation (1) or (2). The cardinality of the digit set is 2ff consequently any
6 There are also other possibilities but the 2's complement notation seems to be the natural choice. Later on
we will suggest that in some particular cases other codification schemes are more convenient as they lead to the
reduction of the network depth.
7 The symmetry of the digit set is not a restriction. We make this assumption for simplicity of notations. Digit
sets which are not symmetric can be also considered without changing the results we report in the next chapters.
can be binary represented by a k-tuple
and x l 2 f0; 1g, for
For the particular case of the 2's complement codification of the SDs the dimension of the
k-tuple can be computed also as 1)e. For each s i ,
values of x l , are to be computed such as s
Assuming 2's complement representation codification of the SDs we will prove (in the
following lemma) that any generalized symmetric SD function can be implemented by a
depth-2 LTN with polynomially bounded size.
Lemma 2: Let F(s an arbitrary generalized symmetric function of
and ff satisfying Equation
(1) or (2) for a fixed radix r. F can be implemented by a LTN with the cost in the
order of O(n).
Proof: Given that F is generalized symmetric it can be expressed as in Equation (6),
are arbitrary integer constant weights.
Under 2's complement representation of the SDs s i Equation (6) is equivalent to:
\Gamma2
dlog
As a consequence of Equation (7) F is expressed as a generalized Boolean symmetric function
of n(1+dlog (ff then it can be computed with the scheme in Lemma 1.
The size of the LTN implementing F depends, on the number of intervals on the definition
domain. Given that in our case the maximum absolute value any digit can assume
is the argument of F as described in Equation (7), in the worst case scenario,
can take any value inside the definition domain [\Gamma
Consequently the
maximum number of intervals is upper bounded by
. Because we assumed
that the weights w i and the radix r are arbitrary integer constants the LTN cost is in the
order of O(n). Obviously the weight and fan-in values are in the order of O(n).


I
Totally Parallel Addition at Digit Position i
III. Signed Digit
In this section we addition schemes using a "totally parallel" [1] addition
approach. We use a fixed radix of 2 and the corresponding digit set f1; 0; 1g,
where 1 denotes \Gamma1. We consider two n-SD integers
and
and propose two schemes to compute the sum
represented as
Traditionally, in the context of Boolean logic, the 2\Gamma1 addition of radix-2 SD represented
operands has been achieved with two step approaches [2], [27], [3]: First an intermediate
carry c i and an intermediate sum s i satisfying the equation x i +y are computed
for each digit position i. Second the sum digit z i , computed as
In our approach we will use the "totally parallel" addition described in Table I [3].
We also assume that any digit x in the set f1; 0; 1g is represented in the 2's complement
notation by two bits, as is shown in Table II. Note that in this codification the combination
not allowed and can not appear during the computations.
It can be observed in the Table I that the digits in position contribute into the
June 23, 1999


II
Digit Codification for x 2 f1; 0; 1g
computation of s i and c i only by their sign. Therefore what we have to compute in order
to implement the scheme presented in the Table are the functions s
These two functions, as they directly implied from the Table, are
not symmetric in their input variables. They can be made symmetric by computing the
weighted sum of the inputs - s stated by Equation (8), such that the Equations (9, 10) with
proper determined weights w i and w hold true for all the possible input combinations.
We compute the weights w i and w i\Gamma1 by taking into consideration the specific structure
of the functions s i and c i . The choice for w straightforward. Given that for
the digits in position account only the x \Gamma bits the minimum value of
should be equal 8 to 3. Consequently the weighted sum - s in the Equation (8) can be
computed as \Gamma6(x \Gamma
and the description of the symmetric
functions computing s i and c i is described in Table III.
From the Table we derive the interval description (similar to the description of Equation
(4)) for the required Boolean functions:
has to be greater than the maximum value that can be assumed by w
which in this case is
2.


III
c i and s i as Symmetric Functions of x
Assume that [ff]
are computed as in Equations (15,16).
We introduce next an implicit depth-1 implementation technique based on the fact that
any symmetric Boolean function F s defined as in Equation (4) can be expressed as:
r Q
r (17)
where: q
concatenation
represent logical OR, and AND respectively.
Lemma 3: Any Boolean symmetric function F s described in Equation (17),
can be implemented by an implicit depth-1 feed-forward LTN with the size in the order
of O(n) as follows:
Proof: To verify Equation (18) it will be shown that F s is indeed 1 when the sum
lies inside an interval [q for a specific j and that F s is 0 when there is no
j such that - 2 [q
In this case Q
as needed.
ffl Case 2: There is no r such that - 2 [q
In this case there are three possibilities:
We will prove that in all of them F s is 0 as needed. In the first sub-case
i.e., is 0. In the second
sub-case
Consequently F
i.e., is 0. In the last sub-case
Consequently F i.e., is 0.
Given that any q
j can be obtained with a LTG computing sgnf- \Gamma q j g and any Q
with a LTG computing -g the entire network is built with 2r LTGs, i.e., the
implementation cost is in the order of O(n). All the input weights are 1 and the fan-in for
all the gates is n.
The method presented in Lemma 3 can be also applied for the implementation of generalized
symmetric functions. Given that in this case the number of intervals is upper
bounded by
, the implementation cost will be upper bounded by 2
i.e., is still in the order of O(n).
Remark 1: The scheme in Lemma 3 can be changed into an explicit one by connecting
all the outputs of the gates computing q
j to a gate with the threshold value of
1. The output of this extra gate will provide explicitly the value of F s after the delay
of 2 TGs.
Remark 2: If q
1 is always 1 and Equation (18) becomes:
r is always 1 and Equation (18) becomes:
If
are always 1 and Equation (18) becomes:
It should be noted that if used in cascaded computation the method described in Lemma 3
increases the fan-in of the next stage because the value of the function F s is carried by 2r
signals.
From the Table III and using the Equation (17) the four Boolean symmetric functions
describing the computations of the intermediate sum s i and carry c i can be expressed by
the following:
By applying the Lemma 3 we derive from the Equations (22,23,24,25) an implicit depth-1
implementation of the first step of the "totally parallel" addition scheme. Because [\Gamma6]
and
are always 1 and Remark 2 we have that:
In order to make more intuitive the way this implicit scheme is working we depicted in

Figure

4 the regions in which the threshold signals [ff]
are active for each of the
four signals s
The second step of the "totally parallel" addition is the computation of z
Following the reasoning used for the computation of s
Fig. 4. Description of Threshold Signals for s
where:
d
c
Theorem 1: Assuming radix-2 SD operand representation and the SD codification in

Table

II the addition of two n-SD numbers can be computed by an implicit depth-2 LTN
with weight value of 6 and a maximum fan-in of 12.
Proof: The quantities d
i in Equation (33,34) can be computed, by doing
the proper substitutions, using Equations (26,27,28,29), as:
d
ni
c
\Gamma2
\Gamma[\Gamma3]
\Gamma[\Gamma4]
June 23, 1999
Consequently, the Equations (30,31) provide an implicit depth-2 implementation scheme
for the computation of the sum digit z i . On the first level of the network we compute
for each digit position i,
use 9 TGs per digit. On the second level we need
2 TGs for each digit position i, in order to compute d
i as
stated by Equations (35,36). Therefore the network producing all the sum digits can be
constructed with 11n TGs. For the digit position we have to produce the carry-out.
This can be explicitly generated in depth-2 at the expanse of two TGs computing:
Therefore the cost of the entire addition network is 11n 2, i.e., of O(n) complexity.
Obviously the weight values and fan-in values do not depend on n. The maximum fan-in
is 12 and the maximum weight value is 6, i.e., having O(1) complexity.
Note that for this scheme the value of z
i is carried by two signals and one threshold value
and z \Gamma
i is actually depth-2 explicitly computed. If used in cascaded computation this
method will increase with 1 the fan-in of the next stage and will contribute with 1 to the
threshold value of some of the gates in the next stage.
If we compare the scheme introduced in Theorem 1 with the depth-2 scheme presented
in [28] which has a network size of 25n + 5, a maximum fan-in of 26, and a maximum
weight value of 123, one can observe that we achieved a substantial reduction in network
size, weight, and fan-in values for the same network depth. However the new depth-2
scheme is implicit and this fact increases the fan-in of the stage requiring as inputs the
digits z i . In the remainder of this section we show that it is possible to explicitly compute
the sum while maintaining the network depth and complexity.
The method described by Equations (30,31) is implicit because of the way we compute
the final sum bit z
. All the other signals, i.e., z \Gamma
are explicitly computed
with two levels of TGs. Consequently, Equation (30) has to be modified to appear as
inducing fundamental changes to the Equations (31,37,38).
To this end we assume that in order to represent a SD x in the set f1; 0; 1g we use the
codification described in Table IV instead of the 2's complement codification in Table II.


IV
New Digit Codification for x 2 f1; 0; 1g


c i and s i as Functions of - s
Note that with this new codification the combination x allowed
and can not appear during the computations.
Under this assumption the quantity - s can be expressed as in Equation (39) and it can
take values in the definition interval [\Gamma12; 8].
Thus the first step of the "totally parallel" addition scheme is described in Table V.
From the Table it can be deduced that the Boolean symmetric functions describing the
June 23, 1999
computations of the intermediate sum s i and carry c i are as follows:
As is was proved in the Lemma 3 from these equations we can derive an implicit depth-1
implementation of the first step of the "totally parallel" addition scheme. Because [\Gamma12]
are always 1 the results of Remark 2 can also be included in the derivation. Thus,
The second step of the "totally parallel" addition is the computation of z
In this case - z
and the second step can be described by
the

Table

VI. Following the same reasoning applied previously for the computation of
this step can be implemented by:
Theorem 2: Assuming radix-2 SD operand representation and the SD codification in

Table

IV the addition of two n-SD numbers can be computed by an explicit depth-2 LTN
with weight value of 10 and a maximum fan-in of 14.
Proof: By proper substitutions, using the Equations (44,45,46,47), the Equations (48,49)
provide an explicit depth-2 implementation scheme of the addition as follow:
ni
June 23, 1999


VI
z i as Functions of - z
\Gamma2
\Gamma2[\Gamma6]
\Gamma2[\Gamma10]
On the first level we compute for each digit position i, the values
digit. On the second level we need 2 TGs for each digit position i,
order to compute d
i as stated by the Equations (50,51). For the digit position
we have to produce the carry-out. This can be also explicitly generated in depth-2
at the expanse of two TGs computing:
Therefore the cost of the entire addition network is 12n 2. The maximum fan-in is 14
and the maximum weight value is 10.
One can observe that all the quantities involved in Theorem 2 are in the same order of
magnitude as in Theorem 1. Even though the scheme in Theorem 1 requires slightly larger
maximum fan-in (14 instead of 12) and weight values (10 instead of 6) it has the advantage
of explicitly computing the sum digits after the delay of 2 TGs.
IV. Signed Digit Multi-Operand Addition and Multiplication
Threshold networks for multi-operand addition and multiplication of n-bit binary operands
have been reported [14], [15], [26], [29]. Generally speaking multi-operand addition and
multiplication can be achieved in two steps, namely: First reduce a multi-operand addition
(in multiplication such addition is required for the reduction of the partial product
into two rows; Second add the two rows to produce the final result. In addition to
these two steps the multiplication also requires a third step, the production of the partial
product matrix. In this section we investigate these processes. For such a scheme and
non-redundant representations the following has been suggested:
ffl The reduction of the multi-operand addition (or the reduction of multiplication partial
product matrix) into two rows can be achieved by depth-2 networks with the cost of the
network, in terms of LTGs, in the order of O(n 2 ) and a maximum fan-in in the order of
O(n log n), see for example [15], [29].
ffl The entire multiplication can be implemented by a depth-4 network [14].
It was also suggested in [30], based on a result in [31], that multi-operand addition
can be computed in depth 2 and multiplication in depth 3 but no explicit construction
for the networks and no complexity bounds are provided. A constructive approach
can be derived if the result in [32] suggesting that a single threshold gate computing
with arbitrary weights can be simulated by an explicit
polynomial-size depth-2 network is used. Such a LOGSPACE-uniform construction
as stated in [32] produces a network with O(log 12 W (n)) wires and the weights of those
wires in order of O(log 8 W (n)), for a total size of O(n 20 log 20 n). The total size for such a
construction was further reduced to O(n 12 log 12 n) in [33]. LOGSPACE-uniform constructions
for depth 2 multi-operand addition and depth 3 multiplication has been suggested
in [32] but the discussion about depth-2 multi-operand addition or depth-3 multiplication
schemes is marginal and no complexity bounds are explicitly given. In an attempt to asses
the complexity of such scheme for multi-operand addition which operates on an n 2 -input
function instead of an n-input function we can use the least expensive scheme in [32] and
estimate that such a depth-2 multi-operand addition or depth-3 multiplication network
may require a total size of O(n 24 log 24 n).
(b) One Step Reduction
(a) Two Step Reduction
Fig. 5. Addition of 8 8-Bit Numbers
In this section we investigate the potential benefit that can be expected by using SD
represented operands in multiplication schemes. First we prove that multi-operand
addition can be achieved by a depth-2 network with O(n 3 ) size, O(n 3 ) weights and O(n 2 )
fan-in complexities. It must be noted that the proposed network performs an n operand to
one result reduction in depth-2 not an n operand to two reduction in depth-2 as previously
proposed schemes [15], [29] do. Subsequently we show that the multiplication (that is the
generation of the partial products and the matrix reduction into one row representing
the product) can be achieved with a depth-3 network with O(n 3 ) size, O(n 3 ) weights and
O(n 2 log n) fan-in complexities.
A. Depth-2 Multi-Operand Addition
It is well known that in order to perform n-bit multi-operand addition first the n rows
(representing the n numbers) are reduced to two then the two rows are added to produce
the final result. This two step process is depicted, for the particular case of 8 8-bit numbers,
in the

Figure

5(a). As indicated in the introduction of the section the first step of multi-
operand addition using not redundant digit representations requires a depth-2 network and
additional depth is required to perform the second step. In the following we will prove
that if we assume SD operands in an appropriate representation radix the multi-operand
addition of n n-SD numbers, and consequently the reduction of the partial product matrix
of the multiplication operation, into one row, can be achieved in one computation step as
June 23, 1999
in

Figure

5(b), requiring a depth-2 network. This is achieved by determining a radix which
allows an n-digit "totally parallel" addition. Avizienis investigated this issue in [1] but
from the dual point of view, by assuming a given radix-r SD representation and determine
the maximum number of digits that can be added in "totally parallel" mode within that
radix-r SD representation. In our investigation the number of digits n is given and a
minimum value for the radix-r must be found to compute n SD addition into a "totally
parallel" mode. We answer to this question in the following lemma.
Lemma 4: The simultaneous addition of n SDs can be done in a "totally parallel" mode
by assuming a representation radix greater or equal with 2n \Gamma 1.
Proof: The simultaneous addition of n SDs can be done in a way similar to the
addition of two digits. That is in order to add the n digits x 1
i in a "totally
parallel" mode we have first to produce an intermediate sum digit u i and a transport digit
t i that satisfy the Equation (54) and also we have to satisfy the constraint indicating that
the subsequent addition in the Equation (55), that gives the value of the sum digit z i in
the position i, can be performed without generating a carry-out. That is:
We have to find the value of the radix r for which the computation in the Equations (54,55)
can be achieved and also the maximum absolute values that we can allow for the intermediate
sum digit u i and the transport digit t i . In order to have consistency we have
to assume that jx j
Therefore, if
mapped in absolute maximal values, the Equations (54,55) become:
From the Equations (56,57) we can derive the following inequalities:
In order to obtain the greatest range for jtj max we have to assume the maximum redundancy
digit set, i.e., jxj for the intermediate sum an absolute maximum value
June 23, 1999
of juj
ri
. This together with the Equation (58) and depending if we assume an
or an even one r e , lead to r e - 2n or r Therefore in order to
perform simultaneous addition of n SDs in a "totally parallel" mode we have to use a
representation radix greater or equal with 2n \Gamma 1.
Assuming a representation radix of 2n \Gamma 1 we introduce the depth-2 multi-operand addition
scheme for n n-SD numbers.
Theorem 3: Assuming representation the multi-operand addition of
(that is the reduction via addition of an n-digit n row matrix to one
row) can be computed by an explicit depth-2 LTN with the size of O(n 3 ). The maximum
weight value is the order of O(n 3 ) and the maximum fan-in value is in the order of O(n 2 ).
Proof: Assume that the n SD numbers we have to add are x
and all the digits x j
can take value within the symmetric
digit set
Given that the radix-(2n \Gamma 1) allows for "totally parallel" addition of n SDs, we can
compute the sum of the n numbers as follows: for each position i produce an intermediate
sum digit u i and a transport digit t i that satisfy
the
sum digit z i in the position i is computed as z generating a carry-out.
If we assume that the greatest absolute values for the input digits, transport digits and
intermediate sum digits are jxj
the sum digit z i will depend only on the values of the digits in the columns i and of the
multi-operand addition matrix and can be computed with the two step approach. With
this scheme the network implementing the multi-operand addition contains one sub-circuit
performing this computation for each digit position i, Obviously the cost
of the entire network is n times the cost of the circuit performing the "totally parallel"
addition of n digits. The delay of the multi-operand addition, the maximum weight and
fan-in values are imposed by their similar values in the circuit performing the "totally
parallel" addition of n digits.
The direct implementation of this two steps computation procedure with the scheme in
the Lemma 1 is not convenient because it will lead to a depth-4 LTN. However, given that
June 23, 1999
any generalized symmetric Boolean function can be implemented with a depth-2 network
we can reduce the depth of the network to 2 if we are able to compute the value of z i with
a symmetric function of 2n input variables, i.e., all the digits in the columns i and
of the multi-operand addition matrix. This can be done by observing the direct link that
exists between the value of z i and the value assumed by the weighted sum - of all the
2n digits x 1
in the columns i and computed as in the
Equation (59).
This link exists as a consequence of the fact that under the maximum value assumptions
we made for the input digits, transport digits and intermediate product digits the radix-
representation of the sum - is the values of t i , z i and t
follow from Equations (54,55). The maximum absolute value that can be assumed by -
can be derived from the Equation (59) under the assumption that all the x j
digits
are 2. This will lead to j-j and to a variation domain for - equal to
Because the digits involved into the computation in the Equation (59) belong to the set D
we need [log bits for their 2's complement codification. Under this codification
each digit x j
i is represented by a
Each of this bits will take part into the computation of - with a weight that
correspond to its position inside the digit and following the 2's complement codification
convention. With this assumption the Equation (59) becomes:
iA
Assuming all of these the product digit z i can be expressed by a function F(-). Obviously,
because of the weighted manner we did the computation of the sum -, the function F is
symmetric in all of the input variables 9 and consequently it can be implemented using the
9 The number of input Boolean variables is given by the product of the number of digits involved into the
computation of z i and the number of bits we need in order to represent a digit in D, i.e.,
method described in the Lemma 1 with a depth-2 LTN.
Because z i can assume any digit value in the set D we need again
its codification. Therefore in order to compute F(-) we have to compute [log (2n \Gamma 1)] +1
symmetric Boolean functions F 1)]. For the implementation of
each symmetric Boolean function F i (-) we need r i LTGs in the first layer of the network,
being the number of intervals in the definition domain where F i assume the value of 1,
and 1 LTG in the second layer. Consequently the computation of the function F(-) can
be done
LTGs. The definition domain for F(-) is given by [\Gamma4n
it F(-) can change its value at most I = 2\Theta4n 2 (n\Gamma1)+1
times. As consequence for each
Boolean function F i (-) the number of intervals r i can not be greater than I. Given that
the changes of the values of F i (-) can appear only in certain fixed positions common for
all of them, we can use the gate sharing concept we introduced in [29]. In this way the
gates associated to the upper limit of the intervals can be shared between the networks implementing
the Boolean functions F i (-). This fact leads to an upper bound of
l 8n 2 (n\Gamma1)+1
for the maximum number of TGs in the first level of the network. The second level of the
network has to contain one gate for each F i (-), i.e., bit position in the 2's complement
representation of z i , then it can be build with gates.
Therefore the network computing the sum digit z i as F(-) can be built with at most
l 8n 2 (n\Gamma1)+1
LTGs. Because we need one such network for each digit
position i and the multi-operand addition matrix has n columns 10 the cost of the entire
multi-operand addition is upper bounded by n
Asymptotically speaking this leads to an implementation of the multi-operand addition
of n n-SD numbers with a depth-2 network having the number of LTGs in the order of
O(n 3 ).
The maximum weight value is upper bounded by the dimension of the definition domain,
consequently it is in the order of O(n 3 ).
If the multi-operand addition matrix is the partial product matrix corresponding to the multiplication of two
n-SD numbers the number of columns is 2n and the cost change as consequence. However this do not change the
asymptotic cost.
The maximum fan-in value is imposed by the gates in the second level of the network
which take as inputs all the bits participating into the computation, i.e., 2n([log(2n \Gamma
some outputs of the gates on the first level. The total number of gates in the
first level of the network is upper bounded by
l 8n 2 (n\Gamma1)+1
and consequently the maximum
fan-in value is in the order of O(n 2 ).
We conclude our investigation on networks for the multiplication of SD operands
by introducing a depth-3 LTN for multiplication which uses the multi-operand addition
scheme we presented in Theorem 3.
B. Depth-3 Multiplication
Multiplication is achieved with the generation and reduction of a partial product ma-
trix. In the previous subsection we have shown that the multi-operand addition (and by
extension the reduction of the multiplication partial product matrix) can be performed in
depth-2 using threshold networks and SD representations. In this section we investigate
the entire multiplication operation including the generation of the partial product matrix.
In the case of non redundant operand representation the generation of the partial product
matrix can be performed at the expanse of n 2 TGs in depth-1 because we need one
AND gate to produce each partial product z This may
not be true for sign digit operands where each partial product z i;j is a SD which has to be
computed as the product of two SDs x i and y j . In essence, even though using
representation the partial product reduction can be achieved by a depth-2 it is not said
that multiplication can be achieved by a depth-3 network.
To achieve a depth-3 multiplication we use Theorem 3 for the reduction of the partial
product matrix and use implicit computations in the network connecting the partial
product production and the first stage of partial product reduction. Given that in order
to use the scheme in Theorem 3 all the partial products z i;j ,
to assume values inside the digit set
we have to restrict the maximum absolute values for the SDs x i and y j to
In the following lemma we assume that the operand digits are represented with the 2's
complement codification discussed in Section II and prove that the entire partial product
matrix can be produced by a depth-2 LTN with polynomially bounded size, weight and
June 23, 1999
fan-in values.
Lemma 5: Assuming two n-SD operands
and jy
the partial product matrix
can be produced by a depth-2 LTN with the size measured
in terms of LTGs in the order of O(n 3 ). The maximum weight value is in the order of
O(n) and the maximum fan-in value is in the order of O(n).
Proof: We assume that all the SDs are represented in the 2's complement notation
by x
). The value of d is imposed
by the maximum absolute value of
we have assumed for the operand digits
and is equal with
log
ii
1. With these assumptions the partial product z i;j
can be expressed as in the following equation:
z
\Gamma2
!/
\Gamma2
On the other hand z i;j is a SD in the set
and can be represented by the ([log(2n\Gamma1)]+1)-tuple (z [log(2n\Gamma1)]
Consequently each bit z r
can be expressed by a symmetric
Boolean function F r (- m ) with the weighted sum -m computed as in Equation (63).
This function can be implemented with a depth-2 network as shown in Lemma 1. By its
construction -m can assume values in the definition domain Consequently
the definition domain for all the F r (- m ) describing the partial product z i;j is given
by definition domain any F r (- m ) can change its value
at most 4(n\Gamma1)+1times. Using the same way of reasoning as in the Theorem 3 an upper
bound of
l 4(n\Gamma1)+1m
can be obtained for the maximum number of TGs in the first level of
the network. The second level of the network has to contain one gate for each F r (- m ),
i.e., bit position in the 2's complement representation of the partial product z i;j , then it
can be build with gates.
Therefore the network computing the partial product z i;j can be built with at most
l 4(n\Gamma1)+1m
Because one such network for each digit pair (i; j),
required the cost of the network producing the entire partial
product matrix is upper bounded by n 2
. This leads to
an implementation cost of the depth-2 network producing the partial product matrix in
the order of O(n 3 ). The maximum weight value is upper bounded by the dimension of
the definition domain for the F r (- m ) functions, i.e., consequently it is
in the order of O(n). The maximum fan-in value is imposed by the gates in the second
level of the network which take as inputs all the bits participating into the computation,
log
ii
2, and some outputs of the gates on the first level. Because we
proved that the total number of gates in the first level of the network is upper bounded
by
l 4(n\Gamma1)+1m
the maximum fan-in value is also in the order of O(n).
By connecting the results for the multi-operand addition and the generation of the partial
product matrix for SD operands we obtain a depth-4 scheme for the multiplication of SD
numbers as stated in the following corollary.
Corollary 1: Assuming representation the multiplication of two n-SD
numbers can be computed by an explicit depth-4 LTN with the size measured in terms of
LTGs in the order of O(n 3 ). The maximum weight value is the order of O(n 3 ) and the
maximum fan-in value is in the order of O(n 2 ).
Proof: Trivial from Lemma 5 and Theorem 3.
The delay of the multiplication network can be still reduced by producing the partial
product matrix using an implicit computation scheme presented in Lemma 3.
Theorem 4: Assuming representation the multiplication of two n-SD
numbers can be computed by an explicit depth-3 LTN with the size in the order of O(n 3 ).
The maximum weight value is the order of O(n 3 ) and the maximum fan-in value is in the
order of O(n 2 log n).
Proof: Trivial. First use the implicit implementation (Lemma 3) in order to produce
the partial products z i;j with the delay of one TG. This derivation will not change the
asymptotic costs we derived in the Lemma 5. Second use the depth-2 multi-operand addition
in Theorem 3 to produce the product. The implicit computation of the partial products
will only increase the fan-in of the gates in the first level of the network performing the
multi-operand addition from 2n([log(2n 1) to at most 2n(4n \Gamma 3)([log(2n
This will change the asymptotic bound for the fan-in from O(n 2 ) to O(n 2 log n). The
asymptotic size of the network and the maximum weight value will remain unchanged.
Consequently this depth-3 scheme has a network size in the order of O(n 3 ) and the maximum
weight value is the order of O(n 3 ).
V. Conclusions
We investigated LTNs for symmetric Boolean functions
addition, and multiplication. We assumed SD number representation and we were mainly
concerned in establishing the limits of the circuit designs using threshold based networks.
We have shown that assuming radix-2 representation the addition of two n-SD numbers
can be computed by an explicit depth-2 LTN with O(n) size and O(1) weight and fan-in
values. If a higher radix of (2n \Gamma 1) is assumed we proved that the multi-operand addition
of n n-SD numbers can be computed by an explicit depth-2 LTN with the size in the order
of O(n 3 ), with the maximum weight value is the order of O(n 3 ) and the maximum fan-in
value is in the order of O(n 2 ). Finally we have shown that the multiplication of two n-SD
numbers can be computed by an explicit depth-3 LTN with the size in the order of O(n 3 ).
The maximum weight value is the order of O(n 3 ) and the maximum fan-in value is in the
order of O(n 2 log n).



--R

"Signed-Digit Number Representations for Fast Parallel Arithmetic,"
"Logic Design of a Redundant Binary Adder,"
"High-Speed VLSI Multiplication Algorithm with a Redundant Binary Addition Tree,"
"Fast Radix-2 Division with Quotient-Digit Prediction,"
"Simple Radix-4 Division with Operands Scaling,"
"High Radix Square Rooting,"
"A Functional MOS Transistor Featuring Gate-Level Weighted Sum and Threshold Operations,"

"Neuron MOS Binary-Logic Integrated Circuits- Part II: Simplifying Techniques of Circuit Configuration and their Practical Applications,"
"A Capacitive Threshold-Logic Gate,"
"A Logical Calculus of the Ideas Immanent in Nervous Activity,"
"How we Know Universals: The Perception of Auditory and Visual Forms,"
"Neural Computation of Arithmetic Functions,"
"Some Notes on Threshold Circuits and Multiplication in Depth 4,"
"Efficient Implementation of a Neural Multiplier,"
"Depth-Size Tradeoffs for Neural Computation,"
Addition and Related Arithmetic Operations with Threshold Logic,"
"ffi-bit Serial Addition with Linear Threshold Gates,"
"A Compact High-Speed (31; 5) Parallel Counter Circuit Based on Capacitive Threshold-Logic Gates,"
"On the Application of the Neuron MOS Transistor Principle for Modern VLSI Design,"
"Periodic Symmetric Functions with Feed-Forward Neural Networks,"
"The Principle of Majority Decision Elements and the Complexity of their Circuits,"
"Linear Input Logic,"
"The Realization of Symmetric Switching Functions with Linear-Input Logical Elements,"
"On Threshold Circuits for Parity,"
"Block Save Addition with Telescopic Sums,"
Computer Arithmetic: Principles
"2j1 Redundant Binary Addition with Threshold Logic,"
"Block Save Addition with Threshold Logic,"
"On optimal depth threshold circuits for multiplication and related problems,"
"Majority gates vs. general weighted threshold gates,"
"Simulating threshold circuits by majority circuits,"
"A note on the simulation of exponential threshold weights,"
--TR
redundant adders;carry-free addition;computer arithmetic;redundant multipliers;neural networks;threshold logic;signed-digit arithmetic;signed-digit number representation