Related Concepts: 5.01 Arithmetic Circuits, Multipliers & Comparators | 5.03 Tree Networks (Cascading MUX, Decoders & DeMUX) | 5.04 Programmable Logic Devices (ROM & PLA)

5.02 Code Converters & Data Routing Implementations

MSI Component Architecture

Medium Scale Integration (MSI) components—such as Decoders, Multiplexers (MUX), and Demultiplexers (DeMUX)—drastically reduce hardware gate counts and wiring complexity by replacing custom SSI gate networks.

---

1. Core Data Routing Definitions

• Decoder: Converts binary information from $n$ input lines to a maximum of $2^n$ unique output lines {generates all minterms internally}.
• Multiplexer (MUX): Selects binary data from one of $2^n$ input lines and routes it to a single output controlled by $n$ select lines {Data Selector}.
• Demultiplexer (DeMUX): Takes data from a single input line and routes it to one of $2^n$ output lines controlled by $n$ select lines {Data Distributor}.

---

2. Master Code Converter: 2,4,2,1 to 8,4,-2,-1

The single most repeated design question in the course

Six appearances — 2017, 2019, 2020, 2023, 2024, 2025 — worth 8 to 13 marks, with word-for-word identical wording every time. If you prepare one design question for this exam, prepare this one.

Major PYQ Problem (PYQ 2017, 2019, 2020, 2023, 2024, 2025 — 8 to 13 marks)

Question (verbatim): Design a combinational circuit that converts a decimal digit from the 2, 4, 2, 1 code to the 8, 4, -2, -1 code.

Complete Conversion Truth Table:

Decimal	Inputs (2,4,2,1) $ABCD$	Outputs (8,4,-2,-1) $WXYZ$	Weight Check
0	0 0 0 0	0 0 0 0	$0=0$
1	0 0 0 1	0 1 1 1	$4-2-1=1$
2	0 0 1 0	0 1 1 0	$4-2-0=2$
3	0 0 1 1	0 1 0 1	$4-0-1=3$
4	0 1 0 0	0 1 0 0	$4-0-0=4$
5	1 0 1 1	1 0 1 1	$8-2-1=5$
6	1 1 0 0	1 0 1 0	$8-2-0=6$
7	1 1 0 1	1 0 0 1	$8-0-1=7$
8	1 1 1 0	1 0 0 0	$8-0-0=8$
9	1 1 1 1	1 1 1 1	$8+4-2-1=9$

• Don’t Care Conditions: the 2421 code never produces the binary patterns 0101–1010, so $d=\Sigma d(5,6,7,8,9,10)$ These six free cells are what make the equations collapse so dramatically — use them.

Minimised Output Equations

Plot one K-map per output over $\Sigma m$ (from the table) plus $\Sigma d(5,6,7,8,9,10)$:

Output	$\Sigma m$ (input binary values where output = 1)	Minimised equation
$W$	$11,12,13,14,15$	$\mathbf{W}=\mathbf{A}$
$X$	$1,2,3,4,15$	$\mathbf{X}={\mathbf{A}}^{\prime }(\mathbf{B}+\mathbf{C}+\mathbf{D})+\mathbf{BCD}$
$Y$	$1,2,11,12,15$	$\mathbf{Y}=\mathbf{A}\oplus \mathbf{C}\oplus \mathbf{D}$
$Z$	$1,3,11,13,15$	$\mathbf{Z}=\mathbf{D}$

How each one falls out:

• $W=A$ — the 1s occupy rows $AB=11$ and $AB=10$; with $m_8,m_9,m_{10}$ available as don’t cares, the whole $A=1$ half becomes a single octet.
• $Z=D$ — inspect the table: the output LSB is 1 in exactly the five rows where the input LSB is 1. No K-map needed.
• $Y=A\oplus C\oplus D$ — in the $A^{\prime }$ half the output follows $C\oplus D$; in the $A$ half it follows $(C\oplus D{)}^{\prime }$. That inversion-on-$A$ pattern is an XOR with $A$.
• $X$ — quads $A^{\prime }B$, $A^{\prime }C$ and $A^{\prime }D$ cover everything in the $A^{\prime }$ half except $m_0$; factoring gives $A^{\prime }(B+C+D)$. The lone remaining 1 at $m_{15}$ pairs only with the don’t care $m_7$, giving $BCD$.

Two traps in this question

• Do not use $ACD$ to cover $m_{15}$. It looks equivalent to $BCD$ but it also covers $m_{11}$ — which is decimal 5, where $X$ must be 0. Check every group against the real 0 cells, not just the 1s.
• Watch the row ordering. The 2421 input for decimal 5 is 1011, not 0101. The code jumps from 0100 (4) straight to 1011 (5) — that discontinuity is exactly what creates the six don’t cares. Writing the inputs as plain binary 0–9 produces a completely different (and wrong) circuit.

Marks strategy

The truth table alone is typically worth about half the marks, so write it out fully and correctly before touching a K-map. Add the weight-check column ($8W+4X-2Y-Z$) as shown above — it costs nothing and proves each row to the examiner. If time runs short, an accurate table plus $W=A$ and $Z=D$ still banks a solid score.

---

3. Shannon’s Expansion Theorem & MUX Logic Design

Shannon’s Expansion Theorem is the mathematical foundation behind multiplexer-based logic design. It states that any Boolean function can be decomposed into smaller sub-functions by expanding it about one or more select variables.

3.1 Theorem Statement

For any $n$-variable Boolean function $F(x_n,\dots ,x_1)$, it can be expanded about an individual variable $x_i$ as:

$\mathbf{F}={\mathbf{x}}_{\mathbf{i}}^{\prime }\cdot \mathbf{F}({\mathbf{x}}_{\mathbf{n}},\dots ,0,\dots ,{\mathbf{x}}_1)+{\mathbf{x}}_{\mathbf{i}}\cdot \mathbf{F}({\mathbf{x}}_{\mathbf{n}},\dots ,1,\dots ,{\mathbf{x}}_1)$

Using cofactor notation, we write: $F=x_i^{\prime }\cdot F_{x_i=0}+x_i\cdot F_{x_i=1}$

Where:

• $F_{x_i=0}$ is the cofactor of $F$ evaluated with variable $x_i=0$.
• $F_{x_i=1}$ is the cofactor of $F$ evaluated with variable $x_i=1$.

3.2 Direct Hardware Mapping to Multiplexers

A multiplexer is physically a hardware implementation of Shannon’s expansion equation:

• The Select Lines ($S$) act as the expansion variables ($x_i$).
• The Data Inputs ($I$) of the MUX are hardwired to the resulting cofactors.

The Select Line Rule

Since each select line represents one expansion variable, an $n$-variable Boolean function can always be implemented using a Multiplexer with:

• $n-1$ select lines (where the remaining $1$ variable feeds the data inputs as $0,1,V,\text{or }{V}^{\prime }$).
• $n$ select lines (where the data inputs are tied to static constants 0 or 1).

---

3.3 Implementing an Arbitrary Function with a Multiplexer

Five appearances — the second-most repeated question in this chapter

2016, 2019, 2022, 2023 and 2024 all ask you to implement a 4-variable function with a multiplexer, for 10 marks each. Only the function changes.

The Three-Step Recipe

For a 4-variable function $F(A,B,C,D)$ on an 8×1 MUX:

1. Connect $A,B,C$ to the three select lines ($S_2{S}_1{S}_0$). The remaining variable $D$ feeds the data inputs.

2. Pair the minterms: rows $2k$ and $2k+1$ share select combination $k$, differing only in $D$.

3. For each pair, read off the data input:

   $F$ at $D=0$	$F$ at $D=1$	Data input $I_k$
   0	0	$0$
   0	1	$D$
   1	0	$D^{\prime }$
   1	1	$1$

Worked Exam Problem (PYQ 2016 — 10 marks; 2024 — 10 marks, specified as $8\times 1$)

Question (verbatim, 2024): Implement the following function with a $8\times 1$ multiplexer: $F(A,B,C,D)=\sum (0,1,3,4,8,9,15)$.

$ABC$	$I_k$	Minterm at $D=0$	Minterm at $D=1$	$F(0)$	$F(1)$	Data input
000	$I_0$	$m_0$	$m_1$	1	1	$1$
001	$I_1$	$m_2$	$m_3$	0	1	$\mathbf{D}$
010	$I_2$	$m_4$	$m_5$	1	0	${\mathbf{D}}^{\prime }$
011	$I_3$	$m_6$	$m_7$	0	0	$0$
100	$I_4$	$m_8$	$m_9$	1	1	$1$
101	$I_5$	$m_{10}$	$m_{11}$	0	0	$0$
110	$I_6$	$m_{12}$	$m_{13}$	0	0	$0$
111	$I_7$	$m_{14}$	$m_{15}$	0	1	$\mathbf{D}$

Verification: $m_4$ has $ABC=010$, $D=0$, so the MUX selects $I_2=D^{\prime }=1$ ✓; $m_5$ selects the same input, $D^{\prime }=0$ ✓.

The Other Examined Function

Worked Exam Problem (PYQ 2019, 2023 — 10 marks)

Question (verbatim, 2023): Implement the following function with a multiplexer. $F(A,B,C,D)=\sum (0,2,3,4,8,10,14)$.

$I_0=D^{\prime }{I}_1=1I_2=D^{\prime }{I}_3=0I_4=D^{\prime }{I}_5=D^{\prime }{I}_6=0I_7=D^{\prime }$

(The 2019 paper prefixes this with “Define multiplexer and demultiplexer” — those definitions are in §1.)

When the question says "4×1 multiplexer and external gates"

The 2022 paper asks for $F(A,B,C,D)=\sum (1,3,4,11,12,13,14,15)$ using a $4\times 1$ MUX. With only two select lines ($A,B$), each data input must be a function of the remaining two variables $C$ and $D$ — so $I_k$ can be $0$, $1$, $C$, $D$, $C^{\prime }$, $CD$, $C+D$, and so on. Build a small four-row table of $F$ against $CD$ for each $AB$ combination and read off the sub-function. That sub-function is what the “external gates” implement.

---

4. Implementing Full-Adder using 4x1 Multiplexers

Major PYQ Problem (PYQ 2021 — 07 marks)

Question (verbatim): Implement a full-adder with two $4\times 1$ multiplexers.

Solution: A Full-Adder has three inputs: $X,Y$ (which we choose as our select lines $S_1=X,S_0=Y$) and $Z$ (the carry-in, which will feed the data inputs).

1. Sum Function ($S=\Sigma m(1,2,4,7)$): Apply Shannon’s expansion about variables $X,Y$: $S=X^{\prime }{Y}^{\prime }\cdot I_0+X^{\prime }Y\cdot I_1+X{Y}^{\prime }\cdot I_2+XY\cdot I_3$
   • For $XY=00$: $S=Z⟹I_0=Z$ (covers minterm 1)
   • For $XY=01$: $S=Z^{\prime }⟹I_1=Z^{\prime }$ (covers minterm 2)
   • For $XY=10$: $S=Z^{\prime }⟹I_2=Z^{\prime }$ (covers minterm 4)
   • For $XY=11$: $S=Z⟹I_3=Z$ (covers minterm 7)
2. Carry Function ($C_{out}=\Sigma m(3,5,6,7)$): Apply Shannon’s expansion about variables $X,Y$: $C_{out}=X^{\prime }{Y}^{\prime }\cdot I_0+X^{\prime }Y\cdot I_1+X{Y}^{\prime }\cdot I_2+XY\cdot I_3$
   • For $XY=00$: $C_{out}=0⟹I_0=0$
   • For $XY=01$: $C_{out}=Z⟹I_1=Z$ (covers minterm 3)
   • For $XY=10$: $C_{out}=Z⟹I_2=Z$ (covers minterm 5)
   • For $XY=11$: $C_{out}=1⟹I_3=1$ (covers minterms 6, 7)

graph TD
    subgraph 4x1 MUX Full-Adder Implementation
        S1[Select S1 = X] & S0[Select S0 = Y] --> MUX_Sum[MUX 1: Sum S]
        S1 & S0 --> MUX_Carry[MUX 2: Carry Out C]
        
        Z[Input Z] -->|I0=Z, I1=Z', I2=Z', I3=Z| MUX_Sum
        Z -->|I0=0, I1=Z, I2=Z, I3=1| MUX_Carry
    end

---

5. Implementing Full-Adder using 3-to-8 Decoder

Major PYQ Problem (PYQ 2019 — 11 marks)

Question (verbatim): Implement a full-adder circuit with a decoder and two OR gates.

Inputs: $x,y,z$ connected to 3-to-8 decoder select lines.

• Sum Output ($S$): Connect decoder output pins 1, 2, 4, 7 to a 4-input OR gate $⟹S=\Sigma m(1,2,4,7)$.
• Carry Output ($C_{out}$): Connect decoder output pins 3, 5, 6, 7 to a second 4-input OR gate $⟹C_{out}=\Sigma m(3,5,6,7)$. $■$

5.1 The General Decoder Method

Why a decoder makes this trivial

An $n$-to-$2^n$ decoder outputs every minterm of its inputs, one per pin. So implementing any SOP function is just “OR together the pins whose indices appear in the minterm list.” No K-map, no simplification — that is the entire technique.

Worked Exam Problem (PYQ 2018 — 08 marks)

Question (verbatim): What is a Decoder? Implement the following function using Decoder, $F(A,B,C,D)=\sum (0,1,3,4,8,9,10,11)$.

Use a 4-to-16 decoder with $A,B,C,D$ on the select lines, then OR together output pins 0, 1, 3, 4, 8, 9, 10, 11. An 8-input OR gate completes the circuit.

Answer the “What is a Decoder?” half too — the definition is in §1 and is worth easy marks.

Worked Exam Problem (PYQ 2016, 2017 — 12 marks; 2020 — 10 marks)

Question (verbatim): A combinational circuit is defined by the following three equations: $F_1=x^{\prime }{y}^{\prime }+xy{z}^{\prime }{F}_2=x^{\prime }+y{F}_3=xy+x^{\prime }{y}^{\prime }$ Design the circuit with a decoder and external gates.

Step 1 — expand each function to minterms over $x,y,z$:

Function	Working	Minterms
$F_1=x^{\prime }{y}^{\prime }+xy{z}^{\prime }$	$x^{\prime }{y}^{\prime }\to m_0,m_1$; $xy{z}^{\prime }\to m_6$	$\sum m(0,1,6)$
$F_2=x^{\prime }+y$	$x^{\prime }\to m_0,m_1,m_2,m_3$; $y\to m_2,m_3,m_6,m_7$	$\sum m(0,1,2,3,6,7)$
$F_3=xy+x^{\prime }{y}^{\prime }$	$xy\to m_6,m_7$; $x^{\prime }{y}^{\prime }\to m_0,m_1$	$\sum m(0,1,6,7)$

Step 2 — one 3-to-8 decoder feeds three OR gates:

• $F_1$: OR of pins $0,1,6$
• $F_2$: OR of pins $0,1,2,3,6,7$
• $F_3$: OR of pins $0,1,6,7$

Economy note: $F_2$ has six minterms out of eight. It is cheaper to build its complement — $F_2^{\prime }=\sum m(4,5)$ — with a 2-input NOR gate on pins 4 and 5. Mentioning this trade-off earns credit for design judgement.

---

6. BCD to Seven-Segment Decoder Design

Lab experiment, not a theory PYQ

This has not appeared in any theory paper from 2015 to 2025. It is ECE 2104 Lab Week 9 (“Design and Implementation of BCD to Seven Segment Decoder”), so learn it for the lab and the lab quiz. It also serves as the largest worked example of the multi-output K-map design flow used by the code converter in §2.

A BCD to Seven-Segment decoder takes a 4-bit binary coded decimal input ($A,B,C,D$, where $A$ is MSB) and converts it to active-high control outputs ($a,b,c,d,e,f,g$) to drive a standard 7-segment LED display to render decimal numbers 0 through 9.

6.1 Display Segment Layout

       a
     +---+
   f |   | b
     +---+  <- g
   e |   | c
     +---+
       d

6.2 Truth Table (Active-High Display)

States $10\dots 15$ (binary 1010 to 1111) are invalid BCD inputs and are treated as Don’t Care ($X$) states.

Decimal	Inputs ($ABCD$)	Segments ($abcdefg$)
0	0 0 0 0	1 1 1 1 1 1 0
1	0 0 0 1	0 1 1 0 0 0 0
2	0 0 1 0	1 1 0 1 1 0 1
3	0 0 1 1	1 1 1 1 0 0 1
4	0 1 0 0	0 1 1 0 0 1 1
5	0 1 0 1	1 0 1 1 0 1 1
6	0 1 1 0	1 0 1 1 1 1 1
7	0 1 1 1	1 1 1 0 0 0 0
8	1 0 0 0	1 1 1 1 1 1 1
9	1 0 0 1	1 1 1 1 0 1 1

6.3 Minimized Logic Equations (using K-Maps)

• Segment a: $a=A+C+BD+B^{\prime }{D}^{\prime }$
• Segment b: $b=B^{\prime }+C^{\prime }{D}^{\prime }+CD$
• Segment c: $c=B+C^{\prime }+D$
• Segment d: $d=A+B^{\prime }{D}^{\prime }+C{D}^{\prime }+B^{\prime }C+B{C}^{\prime }D$
• Segment e: $e=B^{\prime }{D}^{\prime }+C{D}^{\prime }$
• Segment f: $f=A+C^{\prime }{D}^{\prime }+B{C}^{\prime }+B{D}^{\prime }$
• Segment g: $g=A+B^{\prime }C+B{C}^{\prime }+C{D}^{\prime }$

---

7. Basic 1-to-4 Demultiplexer (DeMUX) Design

A Demultiplexer (DeMUX) is a logic circuit that takes a single input line $D$ and routes it to one of $2^n$ outputs, based on the select variables.

7.1 Truth Table

• Inputs: Data $D$, Selects $S_1,S_0$ (where $S_1$ is MSB).
• Outputs: $Y_3,Y_2,Y_1,Y_0$.

Selects ($S_1{S}_0$)	Outputs ($Y_3{Y}_2{Y}_1{Y}_0$)
0 0	0 0 0 D
0 1	0 0 D 0
1 0	0 D 0 0
1 1	D 0 0 0

7.2 Logic Equations & Schematic Implementation

${\mathbf{Y}}_0={\mathbf{S}}_1^{\prime }{\mathbf{S}}_0^{\prime }\mathbf{D}$ ${\mathbf{Y}}_1={\mathbf{S}}_1^{\prime }{\mathbf{S}}_0\mathbf{D}$ ${\mathbf{Y}}_2={\mathbf{S}}_1{\mathbf{S}}_0^{\prime }\mathbf{D}$ ${\mathbf{Y}}_3={\mathbf{S}}_1{\mathbf{S}}_0\mathbf{D}$

The hardware is implemented using four 3-input AND gates:

• The select lines $S_1,S_0$ are connected to the gate inputs through inverters to generate the addressing minterms.
• The data line $D$ is fed to one input of all four AND gates in parallel.

---

8. Past Year Questions (PYQs)

PYQ Index for this note

Question (as asked)	Years	Marks	Solved in
Design a combinational circuit that converts a decimal digit from 2,4,2,1 code to 8,4,-2,-1 code	2017, 2019, 2020, 2023, 2024, 2025	8–13	§2
Implement $F(A,B,C,D)=\sum (0,1,3,4,8,9,15)$ with a (8×1) multiplexer	2016, 2024	10	§3.3
Implement $F(A,B,C,D)=\sum (0,2,3,4,8,10,14)$ with a multiplexer	2019, 2023	10	§3.3
Implement $F(A,B,C,D)=\sum (1,3,4,11,12,13,14,15)$ with a 4×1 multiplexer and external gates	2022	10	§3.3 tip
Define multiplexer and demultiplexer (prefix to the 2019 MUX question)	2019	part of 10	§1
Implement a full-adder with two 4×1 multiplexers	2021	7	§4
Implement a full-adder circuit with a decoder and two OR gates	2019	11	§5
What is a Decoder? Implement $F(A,B,C,D)=\sum (0,1,3,4,8,9,10,11)$ using a Decoder	2018	8	§5.1
Design the circuit for $F_1=x^{\prime }{y}^{\prime }+xy{z}^{\prime }$, $F_2=x^{\prime }+y$, $F_3=xy+x^{\prime }{y}^{\prime }$ with a decoder and external gates	2016, 2017, 2020	10–12	§5.1

Pattern to notice: this note carries the two heaviest recurring questions in Chapter 5 — the code converter (six appearances) and MUX implementation (five) — plus the decoder implementations (four). Between them that is roughly 20 marks of every paper, and all three are mechanical once the technique is known.

The unifying insight: decoders and multiplexers both let you skip simplification entirely. A decoder hands you every minterm on a pin; a MUX lets you fold one variable into the data inputs. Neither needs a K-map. Reach for the truth table, not for grouping.

Not examined here: the BCD to seven-segment decoder (§6) is a lab experiment (ECE 2104 Week 9), not a theory question. The 1×16 demultiplexer built from 2-to-4 decoders (2023) is a tree-network question — see 5.03 Tree Networks (Cascading MUX, Decoders & DeMUX).