Restoring & Non-Restoring Division and Carry Lookahead Adders

Problem: In a 4-bit Carry Lookahead Adder, each 2-input AND, OR, and XOR gate has a propagation delay of 10 ns, 10 ns, and 15 ns respectively. Assume gates have unlimited fan-in.

Calculate:

1. Time to generate all P_i and G_i signals.

2. Time to compute the final carry C_4.

3. Time to generate all sum bits S_i.

Step 1: Generate and Propagate terms:

G_i = A_i \cdot B_i (computed via 2-input AND gate \implies 10 ns).

P_i = A_i \oplus B_i (computed via 2-input XOR gate \implies 15 ns).

Both are computed in parallel: T_{PG} = \max(10, 15) = 15 ns.

Step 2: Carry equation expansions:

C_1 = G_0 + P_0 C_0

C_2 = G_1 + P_1 G_0 + P_1 P_0 C_0

C_3 = G_2 + P_2 G_1 + P_2 P_1 G_0 + P_2 P_1 P_0 C_0

C_4 = G_3 + P_3 G_2 + P_3 P_2 G_1 + P_3 P_2 P_1 G_0 + P_3 P_2 P_1 P_0 C_0

Each carry is a two-level AND-OR circuit: 1 AND gate delay + 1 OR gate delay.

T_{carry} = T_{PG} + T_{AND} + T_{OR} = 15 ns + 10 ns + 10 ns = 35 ns.

Step 3: Sum bit generation:

S_i = P_i \oplus C_i.

Since C_i is available at 35 ns, the final sum is computed by passing through one XOR gate:

T_{sum} = T_{carry} + T_{XOR} = 35 ns + 15 ns = 50 ns.