Combinational circuit design notes — Unit 3

Digital circuits are divided into two categories: Combinational and Sequential.

⇒1.1 Characteristics of Combinational Circuits

A Combinational Circuit consists of logic gates whose outputs at any instant of time are determined entirely by the current combination of inputs.

• No Memory: They have no ability to store past data or states.
• No Feedback: The output is never fed back into the inputs.
• Functionality is completely defined by a set of Boolean expressions or a Truth Table.

⇒1.2 General Design Procedure

• 1. State the problem and determine the number of available inputs and required outputs.
• 2. Assign letter symbols to inputs and outputs.
• 3. Derive the Truth Table defining the required relationships.
• 4. Obtain the simplified Boolean expressions using K-Maps for each output.
• 5. Draw the logic diagram.

⇒2.1 Half Adder

A combinational circuit that performs the addition of two 1-bit numbers ($A$ and $B$). It produces a Sum ($S$) and a Carry ($C$).

• Sum ($S$): $A \oplus B$ (XOR gate)
• Carry ($C$): $A \cdot B$ (AND gate)

Limitation: It cannot accept a carry coming from a previous lower significant bit. This makes it useless for adding multi-bit numbers.

⇒2.2 Full Adder

A circuit that adds three bits: $A$, $B$, and a Carry-in ($C_{in}$) from a previous stage.

• Sum ($S$): $A \oplus B \oplus C_{in}$
• Carry-out ($C_{out}$): $AB + C_{in}(A \oplus B)$

A Full Adder can be constructed using two Half Adders and an OR gate.

⇒3.1 Half Subtractor

Subtracts a 1-bit subtrahend ($B$) from a 1-bit minuend ($A$), producing a Difference ($D$) and a Borrow ($B_{out}$).

• Difference ($D$): $A \oplus B$ (Same as Half Adder Sum!)
• Borrow ($B_{out}$): $A' \cdot B$ (A is inverted before the AND gate)

⇒3.2 Full Subtractor

Subtracts $B$ and a Borrow-in ($B_{in}$) from $A$.

• Difference ($D$): $A \oplus B \oplus B_{in}$
• Borrow-out ($B_{out}$): $A'B + B_{in}(A \oplus B)'$ (or $A'B + A'B_{in} + BB_{in}$)

⇒4.1 Ripple Carry Adder (Parallel Adder)

To add $n$-bit numbers, we cascade $n$ Full Adders. The Carry-out of the $i^{th}$ adder is connected to the Carry-in of the $(i+1)^{th}$ adder.

Propagation Delay: The major flaw of the Ripple Carry Adder. The Most Significant Bit (MSB) adder cannot compute its final sum until the carry ripples through every single previous stage.

⇒4.2 Carry Look-Ahead Adder (CLA)

A fast adder that solves the ripple delay. It uses complex logic to calculate all carries simultaneously based on the inputs, rather than waiting for them to ripple.
Define: Generate $G_i = A_i \cdot B_i$ and Propagate $P_i = A_i \oplus B_i$.
Carry equations are derived independently of previous carry outputs.

⇒4.3 4-Bit Adder/Subtractor Circuit

By using XOR gates at the $B$ inputs and a control signal $M$, a single Ripple Carry Adder can do both.
If $M=0$, it adds.
If $M=1$, the XOR gates invert $B$ (1's complement), and $M$ acts as the initial Carry-in (adding 1). This creates 2's complement subtraction: $A + B' + 1 = A - B$.

A combinational circuit that compares two numbers $A$ and $B$, and determines their relative magnitudes.

It produces three outputs:

• $A > B$
• $A = B$
• $A < B$

⇒5.1 1-Bit Comparator Logic

• $A = B$: True when inputs are identical. Equation: $A \odot B$ (XNOR)
• $A > B$: True when $A=1$ and $B=0$. Equation: $A \cdot B'$
• $A < B$: True when $A=0$ and $B=1$. Equation: $A' \cdot B$

⇒5.2 Multi-Bit Comparator

For multi-bit numbers, equality requires all corresponding bits to be equal: $x_i = A_i \odot B_i$. Total equality is $x_3 \cdot x_2 \cdot x_1 \cdot x_0$.
For $A>B$, check from MSB downwards. E.g., $A>B$ if $A_3>B_3$, OR if ($A_3=B_3$ AND $A_2>B_2$), etc.

A Multiplexer (or Data Selector) is a circuit with many data inputs and one single output. It selects one of the inputs and routes it to the output based on a set of Select Lines.

⇒6.1 $2^n$-to-1 MUX

A MUX has $2^n$ data inputs, $n$ select lines, and 1 output.

Example: 4-to-1 MUX. Inputs $I_0, I_1, I_2, I_3$. Select lines $S_1, S_0$.

• If $S_1S_0 = 00$, Output $Y = I_0$
• If $S_1S_0 = 01$, Output $Y = I_1$
• If $S_1S_0 = 10$, Output $Y = I_2$
• If $S_1S_0 = 11$, Output $Y = I_3$

Boolean Equation: $Y = S_1'S_0'I_0 + S_1'S_0I_1 + S_1S_0'I_2 + S_1S_0I_3$.

A Multiplexer is highly versatile. Any $n$-variable Boolean function can be implemented using a $2^{n-1}$-to-1 MUX.

⇒7.1 Procedure

Example: Implement $F(A,B,C) = \Sigma m(1, 3, 5, 6)$ using a 4-to-1 MUX. (3 variables means we need a $2^{3-1} = 4$-to-1 MUX).

• Connect the two most significant variables (A, B) to the select lines $S_1, S_0$.
• Create an Implementation Table. Columns represent the 4 data inputs $I_0, I_1, I_2, I_3$. Rows represent $C'$ and $C$.
• Fill the table with minterm numbers (0 to 7).
• Circle the minterms given in the function $(1, 3, 5, 6)$.
• Determine the input for each column:
  - If neither circled: Input is 0
  - If both circled: Input is 1
  - If only $C'$ circled: Input is $C'$
  - If only $C$ circled: Input is $C$

Result: Connect $C$ to $I_0$, $C$ to $I_1$, $C'$ to $I_2$, and $0$ to $I_3$.

A Demultiplexer performs the exact opposite function of a multiplexer. It takes one single input data line and routes it to one of $2^n$ possible output lines based on $n$ select lines.

⇒8.1 1-to-4 DEMUX

Input $D$. Select lines $S_1, S_0$. Outputs $Y_0, Y_1, Y_2, Y_3$.

• If $S_1S_0 = 00$, $Y_0 = D$, all other outputs are 0.
• If $S_1S_0 = 01$, $Y_1 = D$, all other outputs are 0.

Equations:
$Y_0 = S_1'S_0' \cdot D$
$Y_1 = S_1'S_0 \cdot D$
$Y_2 = S_1S_0' \cdot D$
$Y_3 = S_1S_0 \cdot D$

A Decoder is a combinational circuit that converts binary information from $n$ input lines to a maximum of $2^n$ unique output lines.

Interestingly, a Decoder is identical in logic to a Demultiplexer where the data input $D$ is permanently tied to Logic 1 (or treated as an Enable pin).

⇒9.1 3-to-8 Line Decoder

Inputs: $x, y, z$. Outputs: $D_0$ to $D_7$.

Each output represents a unique minterm. For input $011$ ($x=0, y=1, z=1$), only output $D_3$ goes HIGH. All other outputs remain LOW.

⇒9.2 Implementing Boolean Functions

Since a decoder generates all possible minterms of the input variables, any Boolean function can be implemented using an $n$-to-$2^n$ decoder and a single OR gate. You just connect the decoder outputs corresponding to the function's minterms into the OR gate.

An Encoder performs the inverse operation of a decoder. It has $2^n$ input lines and $n$ output lines. It outputs the binary code corresponding to the single input line that is active (HIGH).

⇒10.1 Octal to Binary Encoder (8-to-3)

Inputs $D_0$ to $D_7$. Outputs $x, y, z$.

If $D_5$ is HIGH, output is $101$ ($x=1, y=0, z=1$).

⇒10.2 Flaws of a Basic Encoder

• What if two inputs are HIGH simultaneously (e.g., $D_3$ and $D_6$)? The basic encoder fails and outputs garbage (an OR mix of 3 and 6).
• What if NO input is HIGH? The output is 000. But 000 is also the valid output when $D_0$ is HIGH. This causes ambiguity.

To solve these issues, we use a Priority Encoder.

A Priority Encoder assigns a priority to each input. If multiple inputs are active simultaneously, the output code corresponds to the input with the highest priority.

⇒11.1 4-to-2 Priority Encoder

Inputs $D_0, D_1, D_2, D_3$. Let higher subscript denote higher priority. Outputs $x, y$, and a valid bit $V$.

• If $D_3=1$, output is 11, regardless of $D_2, D_1, D_0$ (Don't Cares).
• If $D_3=0$ and $D_2=1$, output is 10, regardless of $D_1, D_0$.
• Valid bit $V$ is set to 1 if any input is active. If all inputs are 0, $V=0$, distinguishing it from $D_0$ being active.

Heavily used in CPU interrupt controllers, where multiple hardware devices might interrupt the CPU at the exact same time.

A standard combinational circuit design application is translating data from one digital code to another.

⇒12.1 Binary to Gray Code Converter

Let Binary inputs be $B_3, B_2, B_1, B_0$ and Gray Code outputs be $G_3, G_2, G_1, G_0$.

• $G_3 = B_3$ (MSB remains unchanged)
• $G_2 = B_3 \oplus B_2$
• $G_1 = B_2 \oplus B_1$
• $G_0 = B_1 \oplus B_0$

The circuit requires only three XOR gates.

⇒12.2 BCD to 7-Segment Decoder

Takes a 4-bit BCD input and outputs 7 lines (a, b, c, d, e, f, g) to light up the appropriate LEDs on a 7-segment display. Requires drawing a K-Map for each of the 7 output lines (treating inputs 1010 to 1111 as Don't Cares).

In theory, logic gates act instantly. In reality, physical gates have a propagation delay. Unequal delays along different paths can cause temporary false outputs, known as Hazards or Glitches.

⇒13.1 Static Hazards

• Static-1 Hazard: The output is supposed to remain steady at 1, but temporarily dips to 0.
• Static-0 Hazard: The output is supposed to remain steady at 0, but temporarily spikes to 1.

⇒13.2 Detecting and Eliminating Static Hazards

Static-1 hazards occur in SOP implementations when moving between two adjacent groups in a K-Map. During the input transition, one AND gate turns off slightly before the other turns on, causing the OR gate output to glitch.

Solution: Add a redundant prime implicant to the circuit! Group the two adjacent 1s that span the gap between the two groups. This extra AND gate keeps the output high during the transition.

Combinational circuits are the stateless math engines of the CPU.

⇒14.1 University Exam Checklist

• Design a Full Adder using two Half Adders and an OR gate. Draw the logic diagram.
• Explain the drawback of a Ripple Carry Adder and how a Carry Look-Ahead Adder solves it.
• Implement the Boolean function $F(A,B,C,D) = \Sigma m(0,1,3,4,8,9,15)$ using an 8-to-1 MUX.
• Explain the difference between a Decoder and a Demultiplexer.
• Design a 4-to-2 Priority Encoder. Provide the truth table and K-Map derivations.
• Explain Static Hazards and how redundant logic can eliminate them.

⇒14.2 Hardware/VLSI Interview Focus

• Why is the Carry Look-Ahead logic not used for 64-bit adders directly? (Answer: The fan-in requirement for the AND/OR gates grows astronomically. Large adders use hierarchical block look-aheads).
• How does a multiplexer act as a universal logic module in modern FPGA architectures (Lookup Tables)?