Recursive Approach to the Design of a Parallel Self Timed Adder

Existing System:

Binary addition is the single most important operation that a processor performs. Most of the adders have been designed for synchronous circuits even though there is a strong interest in clockless / asynchronous processors/circuits. Asynchronous circuits do not assume any quantization of time. Therefore, they hold great potential for logic design as they are free from several problems of clocked (synchronous) circuits. In principle, logic flow in asynchronous
circuits is controlled by a request-acknowledgment handshaking protocol to establish a pipeline in the absence of clocks. Explicit handshaking blocks for small elements, such as bit adders, are
expensive. Therefore, it is implicitly and efficiently managed using dual-rail carry propagation in adders.

1. Pipelined Adders Using Single-Rail Data Encoding The asynchronous Req/Ack handshake can be used to enable the adder block as well as to establish the flow of carry signals. In most
   of the cases, a dual-rail carry convention is used for internal bitwise flow of carry outputs. These dual-rail signals can represent more than two logic values (invalid, 0, 1), and therefore can be used to generate bit-level acknowledgment when a bit operation is completed. Final
   completion is sensed when all bit Ack signals are received (high). The carry-completion sensing adder is an example of a pipelined adder, which uses full adder (FA) functional blocks adapted for dual-rail carry. On the other hand, a speculative completion adder is
   proposed. It uses so-called abort logic and early completion to select the proper completion response from a number of fixed delay lines. However, the abort logic implementation is expensive due to high fan-in requirements.
2. Delay Insensitive Adders Using Dual-Rail Encoding Delay insensitive (DI) adders are asynchronous adders that assert bundling constraints or DI operations. Therefore, they can correctly operate in presence of bounded but unknown gate and wire delays.
   There are many variants of DI adders, such as DI ripple carry adder (DIRCA) and DI carry look-ahead adder (DICLA). DI adders use dual-rail encoding and are assumed to increase complexity.
   Though dual-rail encoding doubles the wire complexity, they can still be used to produce circuits nearly as efficient as that of the single-rail variants using dynamic logic or nMOS only designs. An example 40 transistors per bit DIRCA adder is presented while the conventional CMOS RCA uses 28 transistors. Similar to CLA, the DICLA defines carry propagate, generate, and kill equations in terms of dual-rail encoding [8]. They do not connect the carry signals in a chain but rather organize them in a hierarchical tree. Thus, they can potentially operate faster when there is long carry chain.

Disadvantages:

• Power consumption is high

Proposed System:

In the proposed system we are discussed about a 64bit self timed adder with recursive formulation. This adder is consists of 2:1 mux, sum module and carry module for half adder and completion detection circuit. The general block diagram for the proposed system is shown in fig 4 the circuits are detailed below.
Multiplexer:
We are use 2:1 multiplexer for select the input of the half adder. If SEL = 0 then the inputs of ai, bi is select to the half adder inputs, else SEL = 1 then the ci-1 and si is select to the input of the half adder. Fig 5 shows the 2:1 multiplexer using transistor.
Figure 5: 2:1 mux
Half adder:
The half adder is used to addition of 2 single bit input data and we get the 2 output of sum and carry. The adder is consists of 2 module

• Sum module
• Carry module

Sum module is the XOR operations of 2 inputs and the carry module is AND operations of 2 inputs. The circuit diagram for sum module and carry module is shown in the fig 6
 
Figure 6: single bit sum and carry module
Completion detection circuit:
This circuit is used to determine the iteration is terminated or not. This circuit is also depend on the select bit if the select bit SEL = 1 then it’s not functioning for determination of output else SEL=0 then work properly.
The carries of each half adder is input of the completion detection unit. The output of this circuit is high then the iteration is not finish, else the iteration is finish.

State diagram:
The state diagram for the self timed adder is separated to 2 parts

• Initial phase
• Iterative phase

An initial phase is the initialize the adder circuit. The output of adder is depending on the inputs of the adder. An iterative phase is the next stage of the adder. In this phase the output is depends on the output of previous sum and previous stage carry.
Recursive formula for binary addition:
Let Sji and Cji+1 are the sum and carry respectively. The i represent the bit and j represent the iteration. An initial phase the j = 0, so the addition is
S0i =ai XOR bi
C0i+1 =aibi
For the j th iteration the addition is
Sji = Sji XOR Cj-1i, 0≤i≤n
Cji+1 = Sj-1i Cj-1i, 0≤i≤n
The recursion is terminating at the kth iteration for the completion detection unit output is low. Based on, sum of the carry bit for each half adder to be 0.
Ckn + Ckn-1 +……. + Ck1 = 0, 0≤k≤n

Advantages:

• Reduce the power level

Software implementation:

• Modelsim
• Xilinx ISE