Combinational Circuit Design and Analysis

1. The Building Blocks: Half and Full Adders

At the heart of all binary addition is the process of adding single bits. A circuit that performs this task is called an adder.

Half Adder

A Half Adder is the simplest form of adder. It adds two single binary digits, $A$ and $B$, producing a Sum bit, $S$, and a Carry-out bit, $C_{out}$.

Its operation is defined by the following truth table:

From the truth table, we can directly derive the Boolean expressions for the outputs:

• The Sum $S$ is 1 when exactly one of the inputs is 1. This is the exclusive OR (XOR) operation: $S=A\oplus B$.
• The Carry-out $C_{out}$ is 1 only when both inputs are 1. This is the AND operation: $C_{out}=A\cdot B$.

The resulting circuit is straightforward, consisting of a single XOR gate and a single AND gate. However, the Half Adder has a significant limitation: it cannot accept a carry-in from a previous, less-significant bit addition, making it insufficient for multi-bit arithmetic.

Full Adder

To build practical multi-bit adders, we need a circuit that can add three bits: two input bits $A$ and $B$, plus a Carry-in bit, $C_{in}$, from the previous stage. This is the Full Adder. It produces a Sum $S$ and a Carry-out $C_{out}$.

The truth table for a Full Adder is:

Using the K-map skills from our last lesson, we can find the minimal expressions:

• Sum (S): The minterms are $m(1,2,4,7)$. On a K-map, these form a "checkerboard" pattern, which is characteristic of the XOR function. The simplified expression is $S=A\oplus B\oplus C_{in}$.
• Carry-out ($C_{out}$): The minterms are $m(3,5,6,7)$. Grouping these on a K-map gives the expression $C_{out}=A\cdot B+B\cdot C_{in}+A\cdot C_{in}$.

A clever and efficient way to implement a Full Adder is by combining two Half Adders and an OR gate. This structure directly relates to another valid expression for the carry-out: $C_{out}=A\cdot B+C_{in}(A\oplus B)$.

2. The Ripple-Carry Adder

With the Full Adder as our building block, we can construct an adder for multi-bit numbers, such as 4-bit or 8-bit numbers. The most direct approach is the Ripple-Carry Adder (RCA), also known as a parallel adder.

In an RCA, Full Adders are cascaded in a chain. The carry-out from one stage becomes the carry-in for the next, more significant stage. This structure mimics how we perform addition by hand, where a carry from one column "ripples" over to the next.

Analysis: The Problem of Propagation Delay

While simple, the RCA has a major performance drawback: propagation delay. The final sum and carry bits are not valid until the carry has propagated or "rippled" all the way from the least significant bit (LSB) to the most significant bit (MSB).

Let's formalize this. If a single Full Adder has a propagation delay of $t_{sum}$ to produce its sum and $t_{carry}$ to produce its carry, then for an n-bit RCA:

• The carry-out of the $i$-th stage, $C_{i+1}$, is valid only after the carry $C_i$ is valid.
• The total time to get the final carry, $C_n$, is $n\times t_{carry}$.
• The final sum bit, $S_{n-1}$, depends on the carry $C_{n-1}$, which takes $(n-1)\times t_{carry}$ to become stable. Thus, the total delay for the final sum bit is $(n-1)\times t_{carry}+t_{sum}$.

The delay is linearly proportional to the number of bits, $n$, making RCAs slow for large bit-widths (e.g., 32 or 64 bits).

For GATE, you will often be asked to calculate this worst-case delay given the delays of individual gates inside the Full Adder.

3. The Carry-Lookahead Adder (CLA)

To overcome the RCA's speed limitation, we need to eliminate the ripple effect. The Carry-Lookahead Adder (CLA) achieves this by computing all the carry bits in parallel, directly from the input bits ($A_i$, $B_i$) and the initial carry-in ($C_0$).

The core idea relies on two functions for each bit position $i$:

• Carry Generate ($G_i$): $G_i=A_i\cdot B_i$. This function is 1 if stage $i$ generates a carry-out on its own, regardless of the carry-in.
• Carry Propagate ($P_i$): $P_i=A_i\oplus B_i$. This function is 1 if stage $i$ will propagate its carry-in ($C_i$) to its carry-out ($C_{i+1}$).

Using these G and P terms, we can write equations for each carry bit that depend only on the initial carry $C_0$ and the G and P terms of the preceding stages.

CLA Structure and Delay Analysis

A CLA is built in three logical layers:

1. P and G Generation: Compute all $P_i$ and $G_i$ terms in parallel. This takes 1 gate delay.
2. Carry Lookahead Logic: A dedicated block of two-level logic (AND-OR) computes all carry bits ($C_1$ to $C_n$) in parallel from the P and G terms. This takes 2 gate delays.
3. Final Sum Generation: Compute all sum bits in parallel using $S_i=P_i\oplus C_i$. This takes 1 gate delay.

The total delay is constant, typically 4 gate delays, regardless of the number of bits n (within a single CLA block). This is a massive improvement over the RCA's $O(n)$ delay.

4. Subtractors and Adder/Subtractor Units

How do we build a circuit for subtraction? Instead of designing a new circuit from scratch, we can leverage our adder. The key is 2's complement arithmetic: $A-B$ is equivalent to $A+(-B)$.

To find $-B$ in 2's complement representation, you invert all bits of B (which is the 1's complement) and add 1.
So, $A-B=A+(B^{\prime }+1)$.

We can implement this with a standard adder:

1. The inputs for B are inverted.
2. The +1 is achieved by setting the initial carry-in to the adder, $C_0$, to 1.

This leads to a versatile Adder/Subtractor circuit. By using a control signal, say M, we can make the circuit perform either addition or subtraction:

• Input B: Each bit $B_i$ is fed into an XOR gate along with the control signal M.
  • If $M=0$ (Add): $B_i\oplus 0=B_i$. The B input passes through unchanged.
  • If $M=1$ (Subtract): $B_i\oplus 1=B_i^{\prime }$. The B input is inverted.
• Carry-in $C_0$: The control signal M is connected directly to $C_0$.
  • If $M=0$ (Add): $C_0=0$.
  • If $M=1$ (Subtract): $C_0=1$, providing the +1 for the 2's complement.

The result is a single circuit that performs both operations based on a single control line.

5. Comparators

A magnitude comparator is a combinational circuit that compares two binary numbers, A and B, and determines their relative magnitude (A > B, A = B, or A < B).

Equality Comparison

The simplest case is checking for equality. Two numbers A and B are equal if and only if all their corresponding bits are equal: $A_i=B_i$ for all $i$. The logic function for $A_i=B_i$ is the XNOR gate, $(A_i\oplus B_i{)}^{\prime }$.
The output for A = B is therefore:
$O_{A=B}=(A_{n-1}\text{ XNOR }{B}_{n-1})\cdot (A_{n-2}\text{ XNOR }{B}_{n-2})\cdot \cdots \cdot (A_0\text{ XNOR }{B}_0)$

Magnitude Comparison

To determine 'greater than' or 'less than', we must check the bits from MSB to LSB. For example, for two 4-bit numbers A($A_3{A}_2{A}_1{A}_0$) and B($B_3{B}_2{B}_1{B}_0$):

• A > B if:
  • $A_3>B_3$ (which means $A_3=1$ and $B_3=0$), OR
  • $A_3=B_3$ AND $A_2>B_2$, OR
  • $A_3=B_3$ AND $A_2=B_2$ AND $A_1>B_1$, OR
  • ...and so on.

Let's define $E_i=(A_i\text{ XNOR }{B}_i)$ as the equality for bit $i$. The logic for the "A > B" output becomes:
$O_{A>B}=(A_3\cdot B_3^{\prime })+E_3\cdot (A_2\cdot B_2^{\prime })+E_3\cdot E_2\cdot (A_1\cdot B_1^{\prime })+E_3\cdot E_2\cdot E_1\cdot (A_0\cdot B_0^{\prime })$
The logic for "A < B" is symmetrical. This iterative structure allows comparators to be built for any number of bits, and they are often available as standard integrated circuits (ICs).

Conclusion

In this lesson, we have moved from abstract Boolean expressions to concrete, functional hardware. We designed the essential arithmetic circuits that form the core of every computer.

Key Takeaways:

• Adders: We constructed Half and Full Adders, the fundamental units of addition.
• Ripple-Carry vs. Carry-Lookahead: You learned the critical trade-off between the simple, but slow, Ripple-Carry Adder (with $O(n)$ delay) and the complex, but fast, Carry-Lookahead Adder (with $O(1)$ delay). For GATE, analyzing propagation delay is a key skill.
• Subtractors: We saw that subtraction is not a separate problem but can be elegantly implemented using an adder and the 2's complement method.
• Comparators: These circuits use an iterative MSB-first logic to determine the relative magnitude of two numbers.

You now have a solid understanding of combinational arithmetic circuits. In our next lesson, we will explore another crucial class of combinational circuits: those used for data selection and routing. We will cover multiplexers, demultiplexers, encoders, and decoders, and see how they can be used to implement any arbitrary Boolean function.