GATE CS 2016 Set 2 Q07 — Computer Arithmetic

In an $n$-bit ripple-carry adder, the latency (propagation delay) is maximized when a carry is generated at the least significant bit (LSB) and must propagate through all subsequent stages to the most significant bit (MSB).

For any stage $i$ (where $0 \le i \le 7$):

• Carry Generation ($G_i$): A carry is generated if $A_i \cdot B_i = 1$.
• Carry Propagation ($P_i$): An incoming carry is propagated to the next stage if $A_i \oplus B_i = 1$.

To achieve the longest latency:

1. A carry must be generated at stage $0$: $$G_0 = A_0 \cdot B_0 = 1$$
2. The carry must propagate through all remaining stages $1$ to $7$: $$P_i = A_i \oplus B_i = 1 \quad \text{for } i \in \{1, 2, \dots, 7\}$$

Given that the decimal value of $A$ is $1$, its $8$-bit binary representation is: $$A = 00000001_2$$ This gives $A_0 = 1$ and $A_i = 0$ for $1 \le i \le 7$.

Applying our conditions to find the bits of $B$:

• For stage $0$: We need $A_0 \cdot B_0 = 1 \implies 1 \cdot B_0 = 1 \implies B_0 = 1$.
• For stages $1 \le i \le 7$: We need $A_i \oplus B_i = 1 \implies 0 \oplus B_i = 1 \implies B_i = 1$.

Thus, all bits of $B$ must be $1$: $$B = 11111111_2$$ In $8$-bit $2$'s complement representation, the binary value $11111111_2$ represents the decimal integer $-1$.