Problem $3,(25$ points$)$

Draw a carry$-$save adder tree using $3$:$2$ counters $($i$.$e$.,$ full$-$adders$)$ as building blocks $($Wallace tree$)$ to accumulate

partial products in the multiplication of two operands in the 'fwo's complement format, where, each operand is $15-$bits

long. Assume that radix$-4$ Booth$-$recoding is used.

How many levels are there in the tree?

What is the length of the final CPA $($in terms of the number of digit positions across which the carry needs to propa$-$

gate$)?$

Let the delay of each$-$level be ${}_{3\text{:}2}.$ Then what is the total delay required by the tree to reduce the summation of partial

products down to two$-$operands, $($excluding the delay of booth$-$recoding$)?$

Now draw another tree based on the $(4,2)$ compressors.

How many levels are there in this free?

What is the length of the final carry$-$propagate adder?

Let the delay of each$-$level be ${}_{42}.$ Then what is the total delay of the tree?

Derive conditions relating ${}_{3\text{:}2}$ and ${}_{4\text{:}2}$ under which

$($a$)$ The Wallace Treefs faster and

$($b$)$ The $4$:$2$ compressor tree is faster.