Adders:Carry Look-Ahead Adder.

By -
Carry Look-Ahead Adder

As previously stated, the carry, ci+1, produced at the i-th position is calculated as ci+1 = xi ·yi ∨ ci ·(xi ⊕ yi). This means that a carry is generated if both xi and yi are 1, or an incoming carry is propagated if one of xi and yi is 1 and the other is 0. Therefore, letting gi denote xi yi, we have ci+1 = gi ∨ ci pi, where pi = xi ⊕ yi.

Here, gi is the formula for the carry generation condition at the i-th position, i.e., when gi is 1, a carry is generated at this position. Substituting gi–1 ∨ pi–1ci–1 for ci, we get

Adders-0489

A carry look-ahead adder can be realized according to this expression, as illustrated in Figure 41.10 for the case of four bits [21]. According to this expression, ci+1’s are calculated at all positions in parallel. It is hard to realize an n-bit carry look-ahead adder precisely according to this expression, unless n is small, because maximum fan-in and fan-out restriction is violated at higher positions. Large fan-out causes large delay, so the maximum fan-out is restricted. Also, the maximum fan-in is usually limited to 5 or less. There are some ways to alleviate this difficulty, as follows.

One way is the partition of carry look-ahead adders into several blocks such that each block consists of k positions, starting from the j-th one. In a block h, the carry at each position, ci+1, where j ≤ i ≤ j + k – 1, is calculated as

Adders-0490

where Ch, i.e., cj is the carry from the next lower block. The carry from the next lower block, Ch, goes to only the positions of the block h, so the fan-outs and fan-ins do not increase beyond a certain value. Therefore, we can form an n-bit adder by cascading n/k k-bit carry look-ahead adders, where k is a small constant independent of n, often 4. The worst delay of this type of adder and also the hardware amount are proportional to n.

Another way of alleviating the difficulty is recursively applying the principle of carry look-ahead to groups of blocks. The carry output of block h, Ch+1 (= cj+k ), is calculated as

Adders-0491

is 1, and an incoming carry is propagated if Ph = pj+k–1 pj +k–2 … pj +1 pj is 1. Gh is the formula for the carry generation condition of the block and Ph is the formula for the carry propagation condition of the block. (They are shown as P and G in Figure 41.10) Let us consider a super-block, that is, a group of several consecutive blocks. The carry generation and the carry propagation condition of a super-block are detected from those of the blocks, in the same way that Gh and Ph are detected from gi’s and pi’s. Once the carry input to a super-block is given, carry outputs from the blocks in the super-block are calculated immediately. Consequently, we obtain a fast adder in which small carry look-ahead circuits which include carry calculation circuits are connected in a tree form. Figure 41.11 shows a 4-bit carry look-ahead circuit and Figure 41.12 shows a 16-bit carry look-ahead adder using the 4-bit carry look-ahead circuits, where carry look-ahead circuits are shown as CLA in Figure 41.12. The worst delay of this type of adder is proportional to log n. The number of logic gates is proportional to n.

Adders-0492

Adders-0493

Comments

Post a Comment

Popular posts from this blog

Square wave oscillators and Op-amp square wave oscillator.

By -
Image
Square wave oscillators If Fourier analysis is performed on a square wave it is found that the waveform is composed of many harmonics of the fundamental frequency. This rich harmonic content makes the square wave particularly useful as a quick test of amplifier performance. Examples of possible results are shown. The simplest way to produce a square wave is to make a sine wave oscillator in one of the ways described earlier, then feed the output to some form of squaring circuit such as a Schmitt trigger. This is the method adopted in most commercial sine/square wave generators. There are, however, several circuits for square wave oscillators and a description of the most common follows. Multivibrator Technically the multivibrator is a relaxation oscillator, working on the charging of a capacitor through a resistor. If a negative edge is applied to the circuit in (a), transistor TR 1 turns off the for time taken for the base voltage to return to 0 V. If the voltage step is
Read more

Timing Description Languages:SDF

By -
Image
SDF Standard Delay Format (SDF) is an ASCII format used to convey timing information between EDA tools. SDF was first developed by Cadence in 1990. Open Verilog International (OVI) approved SDF version 2 in 1993 and SDF version 2.1 and 3 in the following years. Improving SDF version 3 features, resulted in IEEE Standard 1497 [1]. Role of SDF in Design Process SDF can be used in different levels of a design process to annotate timing specifications, including timing data and constraints. Timing constraints are used during the forward-annotation process while timing data are applied during the back-annotation process. Forward-annotation process deals with porting timing constraints to synthesis, floorplanner, layout, and routing tools to meet the required constraints. During the design process, timing data can be back-annotated to analysis tools (including simulators, static timing analysis tools, etc.) to provide more accurate timing representations. SDF Structure An SDF f
Read more