Problem 3.9 Ann-bit AND-circuit has 0-1 valued inputs a 0,a1,...,an1 and one output c whose value will be

c = a0 AND a1 AND AND an 1

There are various ways to design an n-bit AND-circuit. A serial design is simply a series of AND-gates, each with one input being a circuit input ai and the other input being the output of the previous gate as shown in Figure 1.

We can also use a tree design. A 1-bit tree design is just a wire, that is c = a1. Assuming for simplicity that n is a power of two, an n-input tree circuit for n > 1 simply consists of two n/2-input tree circuits whose outputs are ANDd to produce output c, as in Figure 2. For example, a 4-bit tree design circuit is shown in Figure 3.

(a) How manyAND-gates are in the n-input series circuit?

(b)The speed or latency of a circuit is the largest number of gates on any path from an input to an output. Briefly explain why the tree circuit is exponentially faster than the series circuit.

(c) Assumenis a power of two. Prove that the then-input tree circuit has n1 AND-gates.

Please help me with parts a, b, and c!!!

a a AND AND AND Figure 1. A serial AND-circuit. 4 IES ++ H- %-input AND-tree "%- input AND-tree AND Figure 2. An n-bit AND-tree circuit. . a AND AND AND Figure 3. A 4-bit AND-tree circuit