Multipliers:Multiplier Based on Wallace Tree.

By -
Multiplier Based on Wallace Tree

In the multiplier based on Wallace tree [13], the multiplicand-multiples are summed up in parallel by means of a tree of carry save adders. A carry save adder sums up three binary numbers and produces two binary numbers (i.e., a partial sum and a partial carry). Therefore, using n/3 carry save adders in parallel, we can reduce the number of multiplicand-multiples from n to about 2n/3. Then, using about

Multipliers-0498

2n/9 carry save adders, we can further reduce it to 4n/9. Applying this principle about log3/2 n times, the number of multiplicand-multiples can be reduced to only two. Finally, we sum up these two multiplicand- multiples by means of a fast carry propagate adder.

Figure 42.4 illustrates a block diagram of a multiplier based on Wallace tree. This consists of full adders, just like the array multiplier described previously. (Recall that a carry save adder consists of full adders.) The delay is small. It is proportional to log n when a fast carry propagate adder with O(log n) delay is used for the final addition. The number of logic gates is about the same as that of an array multiplier and is proportional to n2. However, its circuit structure is not suited for VLSI realization because of the complexity.

The 2-bit Booth’s method can be also applied to this type of multiplier. However, it is not as effective as in the array multiplier, because the height of the Wallace tree decreases by only one or two, even though the number of the multiplicand-multiples is reduced to about half.

A full adder, which is used as the basic cell in a multiplier based on Wallace tree, can be regarded as a counter which counts up 1’s in the three-input bits and outputs the result as a 2-bit binary number. Namely, a full adder can be regarded as a 3-2 counter. We can also use larger counters, such as 7-3 counters and 15-4 counters, as the basic cells, instead of full adders.

We can increase the regularity in the circuit structure by replacing Wallace tree with a 4-2 adder tree [12], where a 4-2 adder is formed by connecting two carry save adders, shown in the dot-lined rectangles, in series, as shown in Figure 42.5. A 4-2 adder is an adder that sums up four binary numbers, A = [an–1 …a0], B = [bn–1 …b0], C = [cn–1 …c0], and D = [dn–1 …d0], and produces two binary numbers, E = [en …e0] and

Multipliers-0499

F = [fn …f0], where f0 = 0. We can form a 4-2 adder tree by connecting 4-2 adders in a binary tree form. The delay of a multiplier based on a 4-2 adder tree is slightly larger than that of a multiplier with Wallace tree but is still proportional to log n. The number of logic gates is about the same as a multiplier based on Wallace tree, and is proportional to n2. It is more suited for VLSI realization than the Wallace tree.

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

Adders:Carry Look-Ahead Adder.

By -
Image
Carry Look-Ahead Adder As previously stated, the carry, c i +1, produced at the i -th position is calculated as c i +1 = x i · y i ∨ c i ·( x i ⊕ y i ). This means that a carry is generated if both x i and y i are 1, or an incoming carry is propagated if one of x i and y i is 1 and the other is 0. Therefore, letting g i denote x i y i , we have c i +1 = g i ∨ c i p i , where p i = x i ⊕ y i . Here, g i is the formula for the carry generation condition at the i -th position, i.e., when g i is 1, a carry is generated at this position. Substituting g i –1 ∨ p i –1 c i –1 for c i , we get 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, c i +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
Read more