13-05-2014, 04:31 PM
Design and Implementation of High-Performance High-Valency Ling Adders
Design and Implementation.pdf (Size: 414.84 KB / Downloads: 23)
Abstract
Parallel prefix adders are used for efficient VLSI
implementation of binary number additions. Ling architecture
offers a faster carry computation stage compared to the con-
ventional parallel prefix adders. Recently, Jackson and Talwar
proposed a new method to factorize Ling adders, which helps
to reduce the complexity as well as the delay of the adder
further. This paper discusses the design and implementation
details for such lower complexity, fast parallel prefix adders
based on Ling theory of factorization. In particular, valency or
radix, the number of inputs to a single node, is explored as
a design parameter. Several low and high valency adders are
implemented in 65 nm CMOS technology. Experimental results
show that the high-valency Ling adders have superior area×delay
characteristics over previously reported Ling-based or non-Ling
adders for the same input size. Moreover, our 20-bit high valency
adder has a better area×delay measurement than the previously-
published 16-bit adders.
INTRODUCTION
Binary addition is one of the fundamental operations in
electronic circuits. Many modern circuits contain several adder
units for applications such as arithmetic logic unit, memory
addresssing and program counter update. Thus, there is a
considerable interest to design higher speed and less complex
adder architectures. For the last few decades, several adder
architectures have been proposed to optimize the adder delay,
examples include, carry-look ahead [1], [2], [3], ripple carry
[4], [5], and parallel prefix adder [6], [7], [8]. The parallel
prefix adder is one of the most popular architectures and offers
good compromise among area, speed and power. This type
of adder implements a logic function to determine whether
each bit position generates the carry, propagates it or kills
it. Then these generate and propagate/not kill functions are
hierarchically combined to compute the carry into each bit
position forming a carry tree. The final stage computes sum
at every bit position using exclusive or (XOR) gates.
Ling Adders
In [9], Ling introduced the pseudo carry notion and showed
that the delay in the carry path could be reduced by forming
the pseudo-carry term (Hn:0 = gn + Gn−1:0 ). Ling’s pseudo
carry is less complex than the Gn:0 as the fan-in of each AND
gate to compute Ling pseudo carry gets reduced by one. Thus,
Hn:0 is easier to implement than Gn:0 .
CONCLUSIONS
Ling factorization can be recursively applied to all stages
in a carry computation tree of an adder. This factorization
reduces the complexity of the carry path which is generally
the critical path of the adder, making it faster. This makes
some other paths more complex, but if the complexity is
properly balanced the resulting adder can work faster. Idea
of combining more simplified logic in a group without buffers
in between and then drives another stage of logic, which is
high valency implementation of carry equations proved not
slower but of similar or better delay. Using valency-4, 16-bit
adders resulted in similar speed as that of the conventional
adders, implemented using Ling factorization at the first level,
but area improvement is considerable. Using valency-5, 20-bit
and 32-bit adders are better in terms of both speed and area
than the conventional adders. Hence, it is shown that high-
valency Ling adders have superior area×delay characteristics
over existing Ling or non-Ling adders for the same input size.
As a future direction, one can design adders by making the
carry tree sparse, i.e. instead of generating every carry some
of the carries are generated which form the sum of more than
one bit position.