09-11-2012, 06:07 PM
On the Design and Analysis of Quaternary Serial and Parallel Adders
On the Design and Analysis of Quaternary.pdf (Size: 754.77 KB / Downloads: 79)
INTRODUCTION
Among the various building blocks used in a
microprocessor, adder is undoubtedly the most important one.
Therefore performance enhancement of a microprocessor
depends largely on the development of adder circuits. Since
1973, researchers [1]-[3] have been working relentlessly to
optimize time delay, wiring complexity, fan-in, fan-out and
chip area of the adder circuit. They used various mathematical
techniques [2] and VLSI design optimizations like dynamic
programming to minimize latency and area of the adder [3].
The most common technique of reducing the time delay is
expressing carry of each bit as a function of propagate and
generate terms of corresponding bit and its earlier bits. Almost
all of these works are based on binary logic, so with the advent
of multi-valued logic systems like ternary or quaternary logic,
improved and efficient adders for these systems have become a
prime necessity.
Multi-valued logic is an apparent extension of binary logic
where any proposition can have more than 2 values. Boolean
algebra in binary logic system is established by defining some
fundamental operators which are fully analogous to union,
intersection and compliment operations in set theory, but it is
not readily expandable for multi-valued logic. In fact, a system
with radix 2k (k ≥ 2) must have a lot of similarities with binary
system [4], so a logic scheme having fundamental blocks that
function similarly to their binary counterparts is surely
advantageous for such logic systems.
QUATERNARY ALGEBRA
In this section we have reviewed a novel quaternary logic
that was proposed in [5], [6]. Quaternary states (0, 1, 2, 3) can
be imagined as 2-bit binary equivalents 00, 01, 10, 11. If the
bits of the binary equivalent interchange their positions and still
the quaternary state remains unchanged, then it is said to have
binary symmetry; otherwise it is asymmetrical. Thus 0, 3 are
symmetrical and 1, 2 are asymmetrical. A single quaternary
digit is called a qudit when it is expressed as a number.
QUATERNARY ADDERS
Since the performance of adders play dominant role in the
overall performance of many digital systems, special care has
to be taken for proper optimization of adders. Speed, physical
limitations in VLSI technology and the purpose of adders in a
system are some key points that must be considered at the time
of designing. A complete description of quaternary adders
requires all possible situations to be considered and different
adders are needed to be designed to handle different
contingencies. For that reason we start our discussion with
single qudit full adder and ripple carry adder. Then in
subsection A we propose the design of single-stage parallel
adder, and in subsection B the design of logarithmic stage
carry-tree adder is introduced.
PERFORMANCE ANALYSIS:
The serial and parallel adders described so far differ widely
from one another in performance and complexity. Usually
efficient adders are more complex in nature, so there is always
some trade off in speed, cost-efficiency or complexity.
Some important parameters in performance evaluation are
gate delay, wiring and gate cost, largest fan-in in a circuit, etc.
Here we develop the expressions for these quantities for each
of the adders described in the preceding sections. Since the
expression of sum is same for all the adders we are considering
here, we only take the carry generation circuit into account.
Gate delay affects the performance of an adder very
severely so it is of maximum priority to reduce the delay as
much as possible. In our analysis we have assumed all gates to
have same amount of delay. From Fig. 6, we can see that
single-stage parallel adder has a fixed number of gate stages
regardless of the number of qudits. The delay for this adder is 6
and it is constant for any qudit.
DESIGN OPTIMIZATION OF LARGE ADDERS:
In this section we propose some schemes to optimize the
design of large adders. For example, we can achieve such
optimization by modifying the carry tree of logarithmic stage
carry-tree adder. Optimization of adder includes the increase of
the radix and sparsity of the carry tree. Radix of the tree is
defined as the maximum number of children of any node.
Increment of the radix of the carry tree results in decrement of
the number of stages but increase of fan-in and delay in each
stage. So we fix the radix as 2.
Sparsity of an adder is defined as the number of every n-th
carry generated by the carry tree. We can efficiently reduce
root congestion and area by increasing the sparsity of the adder.
We propose here a sparsity-4 adder which can be constructed
as follows (Fig. 11, 12).