Related Concepts: 5.02 Code Converters & Data Routing Implementations | 5.03 Tree Networks (Cascading MUX, Decoders & DeMUX) | 5.04 Programmable Logic Devices (ROM & PLA)

5.01 Arithmetic Circuits, Multipliers & Comparators

Combinational Arithmetic Building Blocks

Combinational Arithmetic Circuits form the core of a CPU’s Arithmetic Logic Unit (ALU). Because combinational circuits have no memory elements, their outputs are functions solely of their present inputs.

graph TD
    subgraph 3 Half-Adder Functional Generator
        InA[Inputs A, B] --> HA1[Half-Adder 1: S1 = A ⊕ B, C1 = AB]
        HA1 & InC[Input C] --> HA2[Half-Adder 2: S2 = A ⊕ B ⊕ C = D, C2 = S1 • C = E]
        HA1 & InC --> HA3[Half-Adder 3: S3 = C1 ⊕ C = F, C3 = C1 • C = G]
    end

---

1. The Combinational Circuit Design Blueprint

To design any combinational circuit from scratch (especially when resolving 14-mark word problems), engineers follow a structured 5-step blueprint:

+-----------------------------------+
|  1. Analyze Word Problem & Rules   |
+-----------------------------------+
                  |
                  v
+-----------------------------------+
|  2. Draw Truth Table (I/O Mapping)|
+-----------------------------------+
                  |
                  v
+-----------------------------------+
|  3. Simplify Outputs via K-Maps   |
+-----------------------------------+
                  |
                  v
+-----------------------------------+
|  4. Write Minimized Equations      |
+-----------------------------------+
                  |
                  v
+-----------------------------------+
|  5. Draw Schematic Gate Diagram   |
+-----------------------------------+

Step 1: Variable Identification

Determine the number of input variables and output variables from the problem specification. Assign distinct letter symbols (e.g., inputs $A,B,C$, outputs $X,Y,Z$) to each.

Step 2: Truth Table Construction

List all $2^n$ possible binary combinations for the $n$ input variables. Determine the required output value (1 or 0) for each row based on the system rules. If certain input states are physically impossible or will never occur, mark those output states as Don’t Cares (X).

Step 3: K-map Optimization

Plot a separate K-map for each output variable. Place 1s, 0s, and Xs in their corresponding cells, and group them to obtain the simplest expressions.

Step 4: Logic Equation Extraction

Write down the minimized Sum-of-Products (SOP) or Product-of-Sums (POS) algebraic equations for each output.

Step 5: Schematic Drafting

Draw the physical logic gate circuit. Ensure inputs flow from left to right, gates are drawn cleanly, and all lines and connections are clearly labeled.

---

2. The 4-Function Half-Adder Cascading Puzzle

Major Exam Problem (PYQ 2015 — 12 marks; 2018 — 10 marks; 2019 — 12 marks)

Question (verbatim): Implement the four Boolean functions listed below using three half-adder circuits:

• $D=A\oplus B\oplus C$
• $E=A^{\prime }BC+A{B}^{\prime }C$
• $F=AB{C}^{\prime }+(A^{\prime }+B^{\prime })C$
• $G=ABC$

Word-for-word identical in all three papers. The trick is recognising that each function is already the sum or carry output of a half-adder — do not build them from scratch with gates.

Solution Step-by-Step:

1. Half-Adder 1 (HA1): Inputs $A$ and $B$.

   • Sum Output: $S_1=A\oplus B$
   • Carry Output: $C_1=AB$

2. Half-Adder 2 (HA2): Inputs $S_1$ and $C$.

   • Sum Output: $S_2=S_1\oplus C=(A\oplus B)\oplus C=\mathbf{A}\oplus \mathbf{B}\oplus \mathbf{C}=\mathbf{D}$
   • Carry Output: $C_2=S_1\cdot C=(A\oplus B)\cdot C=(A^{\prime }B+A{B}^{\prime })C={\mathbf{A}}^{\prime }\mathbf{BC}+\mathbf{A}{\mathbf{B}}^{\prime }\mathbf{C}=\mathbf{E}$

3. Half-Adder 3 (HA3): Inputs $C_1$ and $C$.

   • Sum Output: $S_3=C_1\oplus C=(AB)\oplus C=AB\cdot C^{\prime }+(AB{)}^{\prime }\cdot C=\mathbf{AB}{\mathbf{C}}^{\prime }+({\mathbf{A}}^{\prime }+{\mathbf{B}}^{\prime })\mathbf{C}=\mathbf{F}$
   • Carry Output: $C_3=C_1\cdot C=(AB)\cdot C=\mathbf{ABC}=\mathbf{G}■$

---

3. Full-Adder to Full-Subtractor Conversion

The Single Inverter Trick (PYQ 2020 — 10 marks)

Question (verbatim): Show that a full adder can be converted full subtractor with the addition of one inverter gate.

• Standard Full-Adder (FA): $Sum=X\oplus Y\oplus Z$, $C_{out}=XY+XZ+YZ$
• Standard Full-Subtractor (FS): $Diff=X\oplus Y\oplus Z$, $B_{out}=X^{\prime }Y+X^{\prime }Z+YZ$

Solution:

Connect an inverter to the Minuend input ($X$) before it enters the Full-Adder.

1. Input to FA becomes $X^{\prime }$.
2. Carry Out becomes: $C_{out\_new}=X^{\prime }Y+X^{\prime }Z+YZ={\mathbf{B}}_{\mathbf{out}}$ (matches Full-Subtractor Borrow Out).
3. Note: The Sum output becomes $Su{m}_{new}=X^{\prime }\oplus Y\oplus Z=(X\oplus Y\oplus Z{)}^{\prime }=\mathbf{Dif}{\mathbf{f}}^{\prime }$ (complement of Difference). $■$

---

4. Carry Look-Ahead Mathematical Proof & Parallelism

In a standard Ripple Carry Adder, the propagation delay accumulates as carries ripple sequentially through each stage. A Carry Look-Ahead (CLA) Adder eliminates this sequential bottleneck by calculating all carry signals in parallel.

4.1 Derivation of the Carry Equation

Carry Equation Proof (PYQ 2018 — 10 marks)

Question (verbatim): Show that the output carry in a full-adder circuit can be expressed as $C_{i+1}=G_i+P_i{C}_i$ for the full adder circuit shown in Fig. 3(c).

1. Standard Full-Adder carry-out logic equation: $C_{i+1}=A_i{B}_i+A_i{C}_i+B_i{C}_i$
2. Factor out the carry-in $C_i$: $C_{i+1}=A_i{B}_i+C_i(A_i+B_i)$
3. Define Carry Generate ($G_i$): A carry is generated internally if both inputs are 1, regardless of carry-in: $G_i=A_i{B}_i$
4. Define Carry Propagate ($P_i$): An input carry is propagated to the output if either input is 1 (commonly implemented using XOR for sum generation): $P_i=A_i\oplus B_i$
5. Substituting $G_i$ and $P_i$ back into the carry equation: ${\mathbf{C}}_{\mathbf{i}+1}={\mathbf{G}}_{\mathbf{i}}+{\mathbf{P}}_{\mathbf{i}}{\mathbf{C}}_{\mathbf{i}}■$

The second half of the 2018 question

The printed paper continues: "$=G_i^{\prime }{P}_i^{\prime }+G_i^{\prime }{C}_i^{\prime }$". As printed this second expression is not equal to $G_i+P_i{C}_i$ — it is a garbled transcription of the complement form. If you meet it, prove the first equality cleanly (steps 1–5 above), then add one line noting that the second expression as printed does not follow, and give the correct complement instead: $C_{i+1}^{\prime }=(G_i+P_i{C}_i{)}^{\prime }=G_i^{\prime }(P_i^{\prime }+C_i^{\prime })=G_i^{\prime }{P}_i^{\prime }+G_i^{\prime }{C}_i^{\prime }$ That final form matches the printed characters exactly — so the paper almost certainly meant $C_{i+1}^{\prime }$, not $C_{i+1}$. Stating this explicitly is safer than either ignoring it or trying to force a false equality.

---

4.2 Parallel Carry Generation (Look-Ahead Formulas)

By expanding the recurrence relation, we express every carry signal solely in terms of the initial carry-in $C_0$ and the primary input variables ($A$ and $B$, which generate $G_i$ and $P_i$ instantly at the first gate level):

• $C_1$ (Stage 1 Carry): $C_1=G_0+P_0{C}_0$
• $C_2$ (Stage 2 Carry): $C_2=G_1+P_1{C}_1={\mathbf{G}}_1+{\mathbf{P}}_1{\mathbf{G}}_0+{\mathbf{P}}_1{\mathbf{P}}_0{\mathbf{C}}_0$
• $C_3$ (Stage 3 Carry): $C_3=G_2+P_2{C}_2={\mathbf{G}}_2+{\mathbf{P}}_2{\mathbf{G}}_1+{\mathbf{P}}_2{\mathbf{P}}_1{\mathbf{G}}_0+{\mathbf{P}}_2{\mathbf{P}}_1{\mathbf{P}}_0{\mathbf{C}}_0$
• $C_4$ (Stage 4 Carry): $C_4=G_3+P_3{C}_3={\mathbf{G}}_3+{\mathbf{P}}_3{\mathbf{G}}_2+{\mathbf{P}}_3{\mathbf{P}}_2{\mathbf{G}}_1+{\mathbf{P}}_3{\mathbf{P}}_2{\mathbf{P}}_1{\mathbf{G}}_0+{\mathbf{P}}_3{\mathbf{P}}_2{\mathbf{P}}_1{\mathbf{P}}_0{\mathbf{C}}_0$

Propagation Delay Analysis

Since all $G_i$ and $P_i$ terms are computed simultaneously at the first gate level, all carry signals ($C_1$ to $C_4$) are generated in parallel with a flat delay of only two gate levels (one level of ANDs, one level of ORs). This eliminates the $O(n)$ ripple carry delay, keeping the addition speed independent of the word size.

---

5. 2-Bit Binary Multiplier Circuit Design

Not examined 2015–2025 — foundational only

No past paper has asked for a binary multiplier design. It is included because it is the natural application of the half-adder cascade in §2 and appears in the Week 2 syllabus. Read it once; do not prioritise it over the code-converter and ROM/PLA questions that recur every year.

Method Demonstration: $A_1{A}_0\times B_1{B}_0$

Inputs: $A_1{A}_0$ and $B_1{B}_0$. Outputs: $P_3{P}_2{P}_1{P}_0$.

graph TD
    subgraph Multiplier Architecture
        P0[P0 = A0 • B0]
        AND1[A1 • B0] & AND2[A0 • B1] --> HA1[Half-Adder 1: Sum = P1, Carry = C1]
        AND3[A1 • B1] & HA1 --> HA2[Half-Adder 2: Sum = P2, Carry = P3]
    end

• Hardware Required: 4 AND gates and 2 Half-Adders.

---

6. Magnitude Comparator Design & Mathematics

Not examined 2015–2025 — foundational only

Despite appearing in some checklists as a 2023/2024/2025 question, no magnitude comparator question exists in any paper from 2015 to 2025. The equality logic below is still worth knowing — the XNOR-equality trick reappears inside code converters and in the divisibility word problem (2022) — but treat this section as background, not as a predicted question.

A magnitude comparator is a combinational circuit that compares two multi-bit binary numbers ($A$ and $B$) to determine their relative magnitude ($A=B$, $A>B$, or $A<B$).

6.1 Bit Equivalence Coefficient ($x_i$)

To compare two numbers, we first define an equivalence coefficient $x_i$ for each individual bit position $i$ using the XNOR gate:

$x_i=A_i\odot B_i=A_i{B}_i+A_i^{\prime }{B}_i^{\prime }$

• $x_i=1$ if bit $A_i$ is equal to bit $B_i$.
• $x_i=0$ if bit $A_i$ is not equal to bit $B_i$.

6.2 Equality Condition ($A=B$)

For the entire 4-bit numbers $A$ and $B$ to be equal, every single bit position must be equal simultaneously:

$(\mathbf{A}=\mathbf{B})={\mathbf{x}}_3\cdot {\mathbf{x}}_2\cdot {\mathbf{x}}_1\cdot {\mathbf{x}}_0$

Hardware Implementation: Four 2-input XNOR gates feeding into a single 4-input AND gate.

---

6.3 Inequality Conditions ($A>B$ and $A<B$)

To determine if $A$ is greater than or less than $B$, we compare bits starting from the Most Significant Bit (MSB, position 3) down to the Least Significant Bit (LSB, position 0).

1. The $A>B$ Logic Equation

$A>B$ if the MSB of $A$ is $1$ and $B$ is $0$. If they are equal, we check the next bit down, and so on:

$(\mathbf{A}>\mathbf{B})={\mathbf{A}}_3{\mathbf{B}}_3^{\prime }+{\mathbf{x}}_3{\mathbf{A}}_2{\mathbf{B}}_2^{\prime }+{\mathbf{x}}_3{\mathbf{x}}_2{\mathbf{A}}_1{\mathbf{B}}_1^{\prime }+{\mathbf{x}}_3{\mathbf{x}}_2{\mathbf{x}}_1{\mathbf{A}}_0{\mathbf{B}}_0^{\prime }$

2. The $A<B$ Logic Equation

Similarly, $A<B$ if the MSB of $A$ is $0$ and $B$ is $1$. If they are equal, we check the next bit down:

$(\mathbf{A}<\mathbf{B})={\mathbf{A}}_3^{\prime }{\mathbf{B}}_3+{\mathbf{x}}_3{\mathbf{A}}_2^{\prime }{\mathbf{B}}_2+{\mathbf{x}}_3{\mathbf{x}}_2{\mathbf{A}}_1^{\prime }{\mathbf{B}}_1+{\mathbf{x}}_3{\mathbf{x}}_2{\mathbf{x}}_1{\mathbf{A}}_0^{\prime }{\mathbf{B}}_0$

Hardware Implementation: Utilizes the existing XNOR equivalence outputs $x_i$ along with AND gates and a final multi-input OR gate to evaluate the conditions.

---

7. BCD Adder Design & Operation

Not examined 2015–2025 — foundational only

The BCD adder has not appeared as a question in any paper. It is retained because the ”$+6$ correction” rule is the same one used in BCD addition in 2.01 BCD & Weighted Digital Codes, and because it demonstrates the adder-plus-correction-logic pattern that the code-converter questions rely on.

A BCD Adder is a digital circuit that adds two BCD digits in parallel and produces a BCD sum digit.

The Correction Logic

The sum of two BCD digits ($A,B\le 9$) plus a carry-in ($C_{in}\le 1$) can range from $0$ to $19$.

• Standard 4-bit binary addition handles sums up to 15 without a carry-out.

• To convert a binary sum ($S_3{S}_2{S}_1{S}_0$ with carry $K$) into a valid BCD digit (where values $>9$ must generate a decimal carry and be offset by $+6$), we define a correction detection logic function $F$.

• Detection Rule: An overflow (sum $>9$) occurs if:

  1. $K=1$ (the binary sum is $\ge 16$).
  2. $S_3\cdot S_2=1$ (the binary sum is $12,13,14,$ or $15$).
  3. $S_3\cdot S_1=1$ (the binary sum is $10$ or $11$).

  $\mathbf{F}=\mathbf{K}+{\mathbf{S}}_3{\mathbf{S}}_2+{\mathbf{S}}_3{\mathbf{S}}_1$

• If $F=1$, we add binary $6_{10}=0110_2$ to the sum. The output carry for the next decimal stage is $F$.

Hardware Block Diagram:

graph TD
    subgraph BCD Adder Architecture
        InA[BCD Input A] & InB[BCD Input B] --> Adder1[4-Bit Binary Adder 1]
        Cin[Carry In] --> Adder1
        Adder1 --> BinSum[Binary Sum: S3 S2 S1 S0]
        Adder1 --> CarryK[Carry K]
        
        BinSum & CarryK --> Detect[Detection Logic: F = K + S3•S2 + S3•S1]
        
        Detect -->|F| CorrectionBit[Correction Value: 0 F F 0]
        
        BinSum & CorrectionBit --> Adder2[4-Bit Binary Adder 2]
        Adder2 --> BCDOut[Final BCD Sum Output]
        Detect --> CarryOut[Final BCD Carry Out Cout = F]
    end

---

Past Year Questions (PYQs)

Question (as asked)	Years	Marks	Solved in
Implement the four Boolean functions $D,E,F,G$ using three half-adder circuits	2015, 2018, 2019	10–12	§2
Show that the output carry in a full-adder can be expressed as $C_{i+1}=G_i+P_i{C}_i$	2018	10	§4.1
Show that a full adder can be converted to a full subtractor with the addition of one inverter gate	2020	10	§3
Implement a full-adder circuit with a decoder and two OR gates	2019	11	5.02 Code Converters & Data Routing Implementations
Implement a full-adder with two $4\times 1$ multiplexers	2021	7	5.02 Code Converters & Data Routing Implementations

Pattern to notice: the three-half-adder question is the reliable one here — three appearances, identical wording, 10–12 marks. It looks like a design problem but is really a recognition problem: each of $D,E,F,G$ is already a half-adder sum or carry, so the answer is a wiring diagram, not a K-map exercise.

Two adder questions live in the next note because they are really data-routing problems: the 2019 decoder implementation and the 2021 MUX implementation both use the full-adder truth table as input to a MUX/decoder technique.

Sections not examined (2015–2025): the 2-bit multiplier (§5), the magnitude comparator (§6), and the BCD adder (§7) have never been asked. They are foundational background — some checklists tag them with years, but those tags do not survive a check against the question bank. Spend the time on the code converter (six appearances) and ROM/PLA (five and four) instead.