23-06-2012, 12:55 PM
Radix–2 Multioperand and Multiformat Streaming On–line Addition
Radix–2 Multioperand and Multiformat Streaming.pdf (Size: 672.19 KB / Downloads: 25)
Abstract
In this paper we present multioperand radix–2 on–line addition
using different data representations (signed-digit, two’s complement,
and carry–save), in particular cases in which operands with
different representations are added. We use the previously defined on–
line full adder (olFA) as a component to build different multioperand
on–line architectures.
INTRODUCTION
On–line arithmetic defines algorithms for serial arithmetic
operators that receive the inputs and generate
the output starting from the most-significant digit (MSD
first). The serial approach is advantageous because of the
simplicity of the hardware and the reduction in number
and length of connections among modules. Moreover,
the MSD first alternative allows the implementation of
operations, such as division and square root, which are
difficult to implement least-significant digit first.
RADIX-2 ON-LINE ADDITION
In this section we give a brief description of the wellknown
implementation of radix–2 on-line addition. More
details can be found, for instance, in [3]. To allow for
the on-line operation, the representation of the output
should be redundant, while the inputs can be either
redundant or non-redundant. The first designs using
on-line arithmetic began to deal with SD since it was
just proposed [2], and the symmetry of SD seems more
adequate for high radix. Consequently, the most used
redundant representation is signed-digit, but other representations,
such as carry-save, can also be utilized.
ON–LINE ADDITION FOR THREE INPUTS
In this section we deal with on-line adders for three
inputs1. The conclusions obtained from the study of this
case are used to extend the result to multi-operand online
adders in the next section.
The following assumptions are made for the rest of the
paper: 1) there is no overflow in the additions of data and
2) one CS number is equivalent to two TC numbers in
such a way that, along the text, we only use the notation
of TC numbers (take into account that we can always
pairs two TC numbers as one CS when desired).
Before describing a systematic method to deal with
input and output data using different representations
(see section 3.3) let us describe the basic element for
all the architectures presented in this paper: the on–line
full adder (olFA). The cohabitation of data with different
representation is obtained by simple combination of this
element as well as insertion of some inverters.
MULTI-OPERAND ON–LINE ADDITION (FOUR
INPUTS AND BEYOND)
In this section we deal with multi-operand on-line addition
based on olFA elements. We extend the results
of the previous section to four operands and beyond.
The multi-operand case of having four inputs is specially
relevant since it permits to add two redundant data,
which is the most typical in on-line arithmetic based
designs. Thus, we present several examples for four
operands in detail when needed.
ADDITION OF VECTORS (STREAMS)
Consider the addition of vectors. We consider the case
in which one on-line adder tree is used, so that the
elements of the vectors are applied consecutively, forming
a stream. Following the description of the previous
section for operands of p digits3 each addition takes
p + δ cycles. Moreover, to avoid that an element of
the vector affects the previous one, separation cycles are
introduced between elements.
SUMMARY AND CONCLUSIONS
In this paper we have presented the on–line addition
operation using several representations and multiple
operands for streams of data. We have described the
olFA as the key element to build the different tree
architectures. We have performed an analysis of having
together different data representation at input (SD, CS
and/or TC) for the basic case (three inputs) and propose
a method for an inner conversion that eliminates the
need of a specific hardware stage, saving time and area.
As consequence, six simple practical rules are given to
deal with different data representations.