Unit 3: Combinational Logic | Digital Logic

3Unit 3

Combinational Logic Circuits

10h

Class hours

Topics

0/39 done

Progress0/39 topics

Why This Unit Matters

Design circuits whose outputs depend only on current inputs — adders, subtractors, decoders, multiplexers, and more.

Why This Unit Matters

Unit 3 is where Boolean algebra becomes real hardware. Every circuit here — adders, decoders, multiplexers — is a building block used in every processor, memory chip, and digital system ever made. The Full Adder alone is replicated billions of times inside modern CPUs. TU BCA exams consistently require Full Adder design, 4:1 MUX function implementation, and decoder circuit diagrams every year.

Unit Overview in Simple Words

Arithmetic Circuits

Adders and subtractors — building binary math into gates.

Routing Circuits

Encoders, decoders, MUX, DEMUX — directing data flow.

Comparison & Codes

Comparators, Gray code, parity — comparing and protecting data.

Programmable Logic ✦

ROM, PAL, PLA — beyond official TU syllabus; enrichment reading only.

Learning Outcomes

1Design Half Adder and Full Adder; write Sum and Carry Boolean expressions

2Build Full Adder from two Half Adders; explain CLA vs ripple carry

3Perform BCD addition and apply the 6-correction rule when sum exceeds 9

4Design Half and Full Subtractor; write Difference and Borrow expressions

5Design 2:4 and 3:8 decoders; implement any Boolean function using a decoder

6Design 4:2 and 8:3 encoders; explain priority encoder operation

7Implement any 2-variable function with 4:1 MUX; 3-variable with 8:1 MUX

8Convert between Binary and Gray code using XOR circuit

9Design parity generator and checker; detect single-bit errors with XOR

10[Extra] Compare ROM, PAL, PLA — explain which arrays are programmable in each (beyond official syllabus)

⏱️

Teaching Hours

10 hours

📌

Topics

10 main topics

🎯

Exam Weight

~30% of paper

⚠️

Must Know

Full Adder + 4:1 MUX + 2:4 Decoder

Introduction to Combinational Logic

Definition & Characteristics

Combinational Logic Circuit — Core Definition

A digital circuit whose output at any instant depends only on the current input values — not on any past inputs or history. There are no memory elements, no feedback, and no clock required.

Output = f(current inputs only) — no stored state

🧠

No Memory

Outputs depend only on present inputs. Remove or change an input and the output changes immediately (after propagation delay). No flip-flops, no latches.

⚡

No Clock Required

Purely asynchronous. The output responds as soon as inputs change. No synchronisation signal needed — unlike sequential circuits.

🔗

No Feedback

Output signals are never routed back to any input. Any circuit with feedback (like a SR latch) becomes sequential, not combinational.

📋

Fully Defined by Truth Table

Every combinational circuit can be completely specified by a truth table. Given n inputs, there are exactly 2ⁿ rows — all cases are covered.

Combinational vs Sequential — At a Glance

Property	Combinational	Sequential
Memory	None — no storage elements	Uses flip-flops or latches
Clock	Not required	Usually required
Feedback	No feedback paths	Output fed back to input
Output depends on	Current inputs only	Current inputs + past state
Design tools	K-map, Boolean algebra	State diagrams, excitation tables
Response	Immediate (propagation delay only)	Synchronized to clock edges
Examples	Adder, MUX, decoder, encoder	Counter, register, flip-flop

Design Procedure

Any combinational logic circuit can be designed systematically in 5 steps. Mastering this procedure means you can design any circuit from a word problem.

Problem Statement

Clearly define the circuit's purpose. Identify and name each input and output signal. Decide how many bits each signal uses.

Design a circuit that adds two 1-bit numbers A and B, producing a Sum and a Carry output.

Truth Table

List all 2ⁿ input combinations. For each combination, determine what the outputs should be. This is the complete specification.

Two inputs → 4 rows (00, 01, 10, 11). Fill in Sum and Carry for each row based on binary addition.

Boolean Expression (SOP/POS)

Derive the Boolean expression for each output from the truth table. Write it as SOP (sum of minterms) initially.

Sum = Ā·B + A·B̄ (minterms 1 and 2), Carry = A·B (minterm 3)

Simplification

Simplify each expression using K-map or Boolean algebra to find the minimum gate implementation.

Sum simplifies to A⊕B (XOR) — recognise the XOR pattern from the K-map. Carry = A·B is already minimal.

Logic Diagram

Draw the circuit using standard gate symbols. Connect inputs to outputs as specified by the simplified expressions. Verify against the truth table.

Draw an XOR gate (A,B → Sum) and an AND gate (A,B → Carry). Both gates share the same inputs.

Adders & Subtractors

Half Adder (HA)

Adds two 1-bit numbers A and B. Produces a Sum and a Carry output. Called "half" because it cannot process a carry input from a previous stage.

Fig 3.1 — Two inputs (A, B), two outputs (Sum, Carry)

Fig 3.1b — XOR gate → Sum, AND gate → Carry

Boolean Expressions

Sum = A ⊕ B (XOR gate) Carry = A · B (AND gate)

Gate count: 2 gates

• 1 XOR gate → Sum output

• 1 AND gate → Carry output

Truth Table

A	B	Sum (A⊕B)	Carry (A·B)
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

Pattern to remember:

• Sum = 1 when inputs are different (this is exactly XOR)

• Carry = 1 only when both inputs are 1 (this is exactly AND)

Full Adder (FA)

Adds three 1-bit numbers: A, B, and a carry-in (Cin) from a previous stage. This allows Full Adders to be chained together to add multi-bit numbers.

🎛️

Interactive Circuit Simulator

Toggle inputs A, B, and C to observe the outputs.

Half Adder
Active

Sum

Carry

Fig 3.2 — Three inputs (A, B, Cin), two outputs (Sum, Cout)

Fig 3.2b — 2 XOR + 2 AND + 1 OR — P = A⊕B, G = A·B, Sum = P⊕Cin, Cout = G + Cin·P

Boolean Expressions

Sum = A ⊕ B ⊕ Cin Cout = A·B + Cin·(A⊕B)

Cout can also be written as: A·B + B·Cin + A·Cin

Truth Table (8 rows — 3 inputs)

A	B	Cin	Sum	Cout
0	0	0	0	0
0	0	1	1	0
0	1	0	1	0
0	1	1	0	1
1	0	0	1	0
1	0	1	0	1
1	1	0	0	1
1	1	1	1	1

A Full Adder can be constructed from two Half Adders and one OR gate:

HA₁

First Half Adder

Inputs: A, B
Sum₁ = A⊕B
C₁ = A·B

HA₂

Second Half Adder

Inputs: Sum₁, Cin
Sum₂ = Sum₁⊕Cin
C₂ = Sum₁·Cin

Final Carry

Cout = C₁ + C₂
(OR gate on both carries)

Final Sum = A⊕B⊕Cin | Final Cout = A·B + Cin·(A⊕B)

Gate count: 2 XOR + 2 AND + 1 OR = 5 gates total

4-bit Ripple Carry Adder

Four Full Adders chained together. The carry-out of each FA becomes the carry-in of the next. Carry "ripples" from FA₀ (LSB) to FA₃ (MSB), which is why it's called a ripple carry adder.

Fig 3.3 — Four Full Adders chained with carry rippling left to right

How it works

• FA₀ adds A₀ + B₀ + 0 (Cin always 0 for LSB)
• FA₁ adds A₁ + B₁ + C₁ (carry from FA₀)
• FA₂ adds A₂ + B₂ + C₂ (carry from FA₁)
• FA₃ adds A₃ + B₃ + C₃ (carry from FA₂)
• Final C₄ = overall carry-out (overflow indicator)

Disadvantage: Carry Propagation Delay

FA₃ cannot produce its output until FA₂ produces its carry, which waits for FA₁, which waits for FA₀. For 4-bit: delay = 4× (one FA carry delay). For 32-bit: delay = 32× — very slow!

Carry Lookahead Adder (CLA)

Solves the ripple carry delay problem by computing all carries simultaneously using two auxiliary signals: Generate (G) and Propagate (P).

Key Concepts

Generate: Gᵢ = Aᵢ · Bᵢ

A carry is "generated" when both Aᵢ and Bᵢ are 1, regardless of the incoming carry.

Propagate: Pᵢ = Aᵢ ⊕ Bᵢ

A carry is "propagated" when either Aᵢ or Bᵢ (but not both) is 1 — the incoming carry passes through.

C₁ = G₀ + P₀·C₀

C₂ = G₁ + P₁·G₀ + P₁·P₀·C₀

C₃ = G₂ + P₂·G₁ + P₂·P₁·G₀ + P₂·P₁·P₀·C₀

All carries computed in parallel — only 2 gate delays regardless of bit width

BCD Adder

Adds two BCD digits (0–9). BCD uses 4 bits per digit, so the raw binary sum can exceed 9 (the highest valid BCD value). The BCD adder detects and corrects invalid sums.

Correction Rule

• Step 1: Add the two 4-bit BCD digits using a normal 4-bit binary adder
• Step 2: If the result ≤ 9 (0000–1001), the result is already valid BCD — no correction
• Step 3: If the result > 9 (1010–1111) OR there is a carry-out, add 6 (0110) to correct it

Correction needed when: K + Z₈ + Z₄·Z₂ + Z₈·Z₂ = 1 (where K = carry, Z = sum bits)

Example: 7 + 5 = 12

0111 (7 in BCD)

+ 0101 (5 in BCD)

= 1100 (12 in binary — invalid BCD!)

+ 0110 (add 6 for correction)

= 0001 0010 (= 12 in BCD ✓)

Half Subtractor (HS)

Subtracts 1-bit B from 1-bit A. Produces a Difference and a Borrow output. Cannot accept a borrow input from a previous stage.

Fig 3.4 — Computes A - B with Difference and Borrow

Boolean Expressions

Diff = A ⊕ B (same as HA Sum) Borrow = Ā · B (NOT A, AND B)

Key insight:

Borrow occurs when A=0 and B=1 (can't subtract 1 from 0 without borrowing)

Truth Table

A	B	Diff (A⊕B)	Borrow (Ā·B)
0	0	0	0
0	1	1	1
1	0	1	0
1	1	0	0

Compare with Half Adder:

• Diff and Sum are identical (both = A⊕B)

• Borrow = Ā·B, Carry = A·B — differ only in the NOT on A

Full Subtractor (FS)

Subtracts B and a borrow-in (Bin) from A. Produces Difference and Borrow-out (Bout). Can be chained for multi-bit subtraction.

Fig 3.5 — Computes A - B - Bin with Difference and Borrow-out

Boolean Expressions

Diff = A ⊕ B ⊕ Bin Bout = Ā·B + Ā·Bin + B·Bin

Bout also written as: ĀB + Bin(A⊕B)̄ — compare with FA Cout

Truth Table

A	B	Bin	Diff	Bout
0	0	0	0	0
0	0	1	1	1
0	1	0	1	1
0	1	1	0	1
1	0	0	1	0
1	0	1	0	0
1	1	0	0	0
1	1	1	1	1

Worked Derivation: Full Adder Sum Expression

Step through the K-map derivation of FA Sum = A⊕B⊕Cin

Start with truth table minterms for Sum=1

Sum = Σm(1,2,4,7)

Rows where Sum output = 1

Encoders & Decoders

Encoders

An encoder converts a one-hot input (exactly one input active at a time) into its corresponding binary code. It performs the inverse operation of a decoder.

n-bit output ← 2ⁿ inputs (2ⁿ-to-n encoder)

🎛️

Interactive Encoder & Decoder

Toggle inputs to see the active lines change instantly.

Inputs (D₀-D₇)

Highest active input takes priority

8:3 Priority
Encoder

Outputs

VValid

4-to-2 Encoder

4 inputs (I₀–I₃), 2 outputs (A₁, A₀). Exactly one input is HIGH at a time.

I₃	I₂	I₁	I₀	A₁	A₀
0	0	0	1	0	0
0	0	1	0	0	1
0	1	0	0	1	0
1	0	0	0	1	1

Boolean Expressions

A₁ = I₂ + I₃ A₀ = I₁ + I₃

Derivation trick:

• A₁=1 for rows where A₁=1 → I₂=1 (row 3) and I₃=1 (row 4)

• A₀=1 for rows where A₀=1 → I₁=1 (row 2) and I₃=1 (row 4)

⚠ Limitation: doesn't handle simultaneous inputs or all-0 input (invalid)

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

8 inputs (I₀–I₇), 3 outputs (A₂, A₁, A₀). One input active at a time.

Active Input	A₂	A₁	A₀
I₀ (octal 0)	0	0	0
I₁ (octal 1)	0	0	1
I₂ (octal 2)	0	1	0
I₃ (octal 3)	0	1	1
I₄ (octal 4)	1	0	0
I₅ (octal 5)	1	0	1
I₆ (octal 6)	1	1	0
I₇ (octal 7)	1	1	1

Boolean Expressions

A₂ = I₄ + I₅ + I₆ + I₇ A₁ = I₂ + I₃ + I₆ + I₇ A₀ = I₁ + I₃ + I₅ + I₇

Pattern:

Aₙ = OR of all inputs where bit n = 1 in the binary code.

A₀ = all odd inputs (1,3,5,7 — LSB is 1)

A₁ = inputs 2,3,6,7 (2nd bit = 1)

A₂ = inputs 4,5,6,7 (MSB = 1)

Priority Encoder

Solves the limitation of basic encoders — handles multiple simultaneous active inputs by prioritising the highest-numbered active input.

4-input Priority Encoder Truth Table

I₃	I₂	I₁	I₀	A₁	A₀	V
0	0	0	0	X	X	0
0	0	0	1	0	0	1
0	0	1	X	0	1	1
0	1	X	X	1	0	1
1	X	X	X	1	1	1

V = valid output indicator (1 = at least one input active)

Priority order: I₃ > I₂ > I₁ > I₀

A₁ = I₃ + I₂ A₀ = I₃ + Ī₂·I₁ V = I₃ + I₂ + I₁ + I₀

Why X (don't care) in inputs?

If I₃=1, the outputs are always 11 regardless of I₂, I₁, I₀ — those inputs don't affect the output.

Decoders

A decoder converts a binary code input into a one-hot output — exactly one output line goes HIGH (or LOW for active-low) for each input combination. With n inputs, a decoder activates one of 2ⁿ outputs.

2ⁿ outputs ← n-bit binary input (n-to-2ⁿ decoder)

2-to-4 Decoder (with Enable)

2 inputs (A₁, A₀) + Enable (E). 4 outputs (Y₀–Y₃). When E=0, all outputs are 0. When E=1, exactly one output is 1.

E	A₁	A₀	Y₃	Y₂	Y₁	Y₀
0	X	X	0	0	0	0
1	0	0	0	0	0	1
1	0	1	0	0	1	0
1	1	0	0	1	0	0
1	1	1	1	0	0	0

Boolean Expressions

Y₀ = E · Ā₁ · Ā₀ (minterm 0) Y₁ = E · Ā₁ · A₀ (minterm 1) Y₂ = E · A₁ · Ā₀ (minterm 2) Y₃ = E · A₁ · A₀ (minterm 3)

Key insight: Decoder = Minterm Generator

Each output Yᵢ implements exactly minterm mᵢ. This makes decoders powerful — you can implement any Boolean function by ORing the appropriate outputs together.

Fig 3.6b — 2 NOT gates generate complements, 4 AND gates produce one-hot outputs Y₀–Y₃

3-to-8 Decoder (74138)

3 inputs (A₂, A₁, A₀), 8 outputs (Y̅₀–Y̅₇ — active LOW), 3 enable inputs.

Abbreviated Truth Table

A₂	A₁	A₀	Active output (LOW)
0	0	0	Y̅₀
0	0	1	Y̅₁
0	1	0	Y̅₂
0	1	1	Y̅₃
1	0	0	Y̅₄
1	0	1	Y̅₅
1	1	0	Y̅₆
1	1	1	Y̅₇

74138 Enable Inputs

• G1 (active HIGH) — must be 1 to enable

• G2A̅ (active LOW) — must be 0 to enable

• G2B̅ (active LOW) — must be 0 to enable

All three conditions must be met: G1=1 AND G2A=0 AND G2B=0

BCD to 7-Segment Decoder

Takes a 4-bit BCD input (0–9) and drives 7 segments (a–g) of a 7-segment display.

Digit 0 — Active segments

abcdefg

BCD input: 0 0 0 0

Segment pattern: abcdef

Fig 3.6 — Each BCD digit (0-9) maps to a unique combination of 7 segments (a-g)

Multiplexers & Demultiplexers

Multiplexers (MUX)

A multiplexer is a data selector — it routes one of 2ⁿ data inputs to a single output, controlled by n select lines. Think of it as a digital switch or rotary selector knob.

1 output ← 2ⁿ inputs, controlled by n select lines

2:1 MUX

Fig 3.7 — 1 select line, 2 data inputs, 1 output

S	Y (output)
0	I₀
1	I₁

Y = S̄·I₀ + S·I₁

Gate implementation

• 2 AND gates (one for each input)

• 1 NOT gate (for S̄)

• 1 OR gate (combine both AND outputs)

S=0 → passes I₀ S=1 → passes I₁

Fig 3.7b — Y = S̄·I₀ + S·I₁ — 1 NOT, 2 AND, 1 OR gate

4:1 MUX

4 data inputs (I₀–I₃), 2 select lines (S₁, S₀), 1 output (Y).

S₁	S₀	Output Y
0	0	I₀
0	1	I₁
1	0	I₂
1	1	I₃

Boolean Expression

Y = S̄₁·S̄₀·I₀ + S̄₁·S₀·I₁ + S₁·S̄₀·I₂ + S₁·S₀·I₃

Gate count:

• 4 AND gates (3-input each: Sᵢ, Sⱼ, Iₖ)

• 2 NOT gates (for S̄₁ and S̄₀)

• 1 OR gate (4-input)

Interactive 4:1 MUX Simulator

Data Inputs (I₀–I₃)

I₀← selected

I₁

I₂

I₃

Select Lines

S₁

S₀

S₁S₀ = 00 → selects I0

Output Y

Y = I0 = 0
(S₁=0, S₀=0)

8:1 MUX

8 data inputs (I₀–I₇), 3 select lines (S₂, S₁, S₀), 1 output.

Y = S̄₂·S̄₁·S̄₀·I₀ + S̄₂·S̄₁·S₀·I₁ + S̄₂·S₁·S̄₀·I₂ + S̄₂·S₁·S₀·I₃ + S₂·S̄₁·S̄₀·I₄ + S₂·S̄₁·S₀·I₅ + S₂·S₁·S̄₀·I₆ + S₂·S₁·S₀·I₇

Using 8:1 MUX as 3-variable function generator

Connect A, B, C to S₂, S₁, S₀. Set I₀–I₇ to the truth table output values of F(A,B,C).

Example: F(A,B,C) = Σm(0,2,5,7) Set I₀=1, I₂=1, I₅=1, I₇=1 All others = 0

Function Implementation with MUX

4:1 MUX as Function Generator (2-variable)

Connect A and B to S₁ and S₀. Set data inputs I₀–I₃ to the desired function values. Tap the truth table cells to change the function.

A (S₁)	B (S₀)	Data input
0	0	I0
0	1	I1
1	0	I2
1	1	I3

Detected function

A⊕B (XOR)

MUX Wiring:

• S₁ ← variable A

• S₀ ← variable B

• I0 ← 0 (GND)

• I1 ← 1 (VCC)

• I2 ← 1 (VCC)

• I3 ← 0 (GND)

A 4:1 MUX (2 select lines) can implement any 2-variable Boolean function — just set the data inputs to the truth table values.

Demultiplexers (DEMUX)

A demultiplexer is the inverse of a MUX — it routes a single input to one of 2ⁿ outputs, controlled by n select lines. Think of it as a distribution switch — one source, multiple destinations.

2ⁿ outputs ← 1 input, controlled by n select lines

1:4 DEMUX

1 data input (D), 2 select lines (S₁, S₀), 4 outputs (Y₀–Y₃).

Fig 3.8 — 2 select lines, 1 data input, 4 outputs

S₁	S₀	Y₀	Y₁	Y₂	Y₃
0	0	D	0	0	0
0	1	0	D	0	0
1	0	0	0	D	0
1	1	0	0	0	D

Boolean Expressions

Y₀ = D · S̄₁ · S̄₀ Y₁ = D · S̄₁ · S₀ Y₂ = D · S₁ · S̄₀ Y₃ = D · S₁ · S₀

DEMUX = Decoder + Enable

Notice: expressions are identical to a 2:4 decoder with E=D.

Set D=1 permanently → it becomes a 2-to-4 decoder!

MUX vs DEMUX — Summary Comparison

Property	Multiplexer (MUX)	Demultiplexer (DEMUX)
Function	Many-to-one (data selector)	One-to-many (data distributor)
Inputs	2ⁿ data + n select	1 data + n select
Outputs	1 output	2ⁿ outputs
Select lines	Chooses which INPUT to read	Chooses which OUTPUT to write
Dual of	DEMUX	MUX
Example	4:1 MUX — select 1 of 4 channels	1:4 DEMUX — route to 1 of 4 lines

Data Processing Circuits

Magnitude Comparator

Compares two binary numbers A and B and produces three outputs: A> B, A=B, and A<B. Exactly one output is HIGH at a time.

⚖️

4-Bit Magnitude Comparator

Toggle bits to compare two binary numbers instantly.

Input A

= 5₁₀

7485 ICComparator

Outputs

A > B

A = B

A < B

1-bit Comparator

A	B	A>B	A=B	A<B
0	0	0	1	0
0	1	0	0	1
1	0	1	0	0
1	1	0	1	0

Boolean Expressions

(A> B) = A · B̄ (A = B) = A ⊙ B (XNOR) (A < B) = Ā · B

Gate implementation:

• (A>B): AND gate with A and B̄ (NOT B)

• (A=B): XNOR gate

• (A<B): AND gate with Ā (NOT A) and B

4-bit Comparator (IC 7485)

Compares two 4-bit numbers A(A₃A₂A₁A₀) and B(B₃B₂B₁B₀) starting from the MSB.

Comparison Logic (MSB-first)

Compare bit 3 (MSB): if A₃≠B₃, the result is determined immediately
If A₃=B₃, compare bit 2: if A₂≠B₂, result determined
Continue down to bit 0
If all bits equal, use cascade inputs to determine final result

Cascade inputs (for chaining)

• I(A>B), I(A=B), I(A<B) — from lower-order chip

• Set I(A=B)=1, others=0 for standalone use

Cascading for larger comparators

Lower chip (A₃–A₀ vs B₃–B₀)

I(A=B)=1, others=0

Upper chip (A₇–A₄ vs B₇–B₄)

Connect outputs of lower chip to cascade inputs

8-bit compare: two 7485 chips MSB chip outputs = final result LSB chip outputs → MSB cascade inputs

Code Converters

Combinational circuits that convert from one binary code to another — no memory, just combinational logic (XOR gates for Gray, adder for Excess-3).

Binary ↔ Gray Code Converter

Binary → Gray

G[n] = B[n] (MSB same) G[i] = B[i+1] ⊕ B[i] (XOR adjacent)

The MSB of Gray equals the MSB of binary. Each subsequent Gray bit is XOR of adjacent binary bits.

Gray → Binary

B[n] = G[n] (MSB same) B[i] = B[i+1] ⊕ G[i] (XOR with prev)

The conversion cascades from MSB — each binary bit depends on the previous binary bit (not binary input bit).

4-bit Example Table

Binary	Gray Code
0000	0000
0001	0001
0010	0011
0011	0010
0100	0110
0101	0111
0110	0101
0111	0100

Adjacent Gray codes differ by exactly 1 bit (single-step property).

Interactive Code Converter

Binary (up to 8 bits)

Gray Code result

1110

Step-by-step (Binary→Gray):

Bit [0] (MSB): G[0] = B[0] = 1

Bit [1]: G[1] = B[0]⊕B[1] = 1⊕0 = 1

Bit [2]: G[2] = B[1]⊕B[2] = 0⊕1 = 1

Bit [3]: G[3] = B[2]⊕B[3] = 1⊕1 = 0

Gray code: 1110

BCD ↔ Excess-3 Converter

BCD → Excess-3

Add 3 (0011) to the BCD value using a 4-bit binary adder.

XS3 = BCD + 0011 Uses a 4-bit adder with B input = 0011

Excess-3 → BCD

Subtract 3 (add 2's complement of 0011 = 1101).

BCD = XS3 − 0011 = XS3 + 1101 (add 2's complement)

Decimal	BCD	Excess-3
0	0000	0011
1	0001	0100
2	0010	0101
3	0011	0110
4	0100	0111
5	0101	1000
6	0110	1001
7	0111	1010
8	1000	1011
9	1001	1100

Parity Generator & Checker

Parity is a simple error-detection method. A parity bit is appended to data so that the total number of 1-bits in the transmitted word is always even (even parity) or always odd (odd parity). A single bit error changes the parity, which can be detected.

Parity Generator

3-bit Even Parity Generator

Generates parity bit P for data bits A, B, C so that total 1s is even.

P (even) = A ⊕ B ⊕ C P (odd) = A ⊕ B ⊕ C ⊕ 1 = P̄(even)

Circuit: XOR chain

• XOR(A, B) → intermediate result

• XOR(intermediate, C) → parity bit P

• For n data bits: n−1 XOR gates

Truth Table (even parity bit P)

A	B	C	P (even)
0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	0
1	1	1	1

Parity Checker

At the receiver, XOR all received bits (data + parity). For even parity: result = 0 means no error, result = 1 means error detected.

Error = A ⊕ B ⊕ C ⊕ P (XOR of all received bits) Error=0 → OK | Error=1 → bit flip!

Limitation of single parity bit

• Detects single bit errors (odd number of flipped bits)

• Cannot detect 2-bit errors (two flips cancel out)

• Cannot correct errors (use Hamming code for correction)

Parity Check Example

Transmitted: 1011 | P=1 (even)

Count of 1s in 1011: three 1s → odd → P=1 ✓

Received: 1111 (bit flip!)

XOR(1⊕1⊕1⊕1) = 0... wait:

1⊕0⊕1⊕1⊕1 = 0 → no error detected!

2-bit flip: undetectable by single parity

Parity Bit Calculator

Data bits (up to 8)

Result

Count of 1s: 3

even parity bit: 1

Transmitted word: 10111(data + parity)

How it works:

XOR all data bits: 1 ⊕ 0 ⊕ 1 ⊕ 1 = 1

Even parity: append this XOR result as parity bit (makes total 1-count even)

Programmable Logic (ROM / PAL / PLA)

✦ Enrichment — Beyond Official TU Syllabus

Programmable Logic Devices (ROM, PAL, PLA) are not part of the official TU BCA CACS 103 Digital Logic syllabus. This section is included for enrichment only. Do not prioritise it over core syllabus topics for exam revision.

Programmable Logic Devices (PLDs)

Any combinational logic function in SOP form can be expressed as a set of AND operations (product terms) followed by OR operations (sum of products). PLDs implement this structure in hardware — some connections are programmable, letting you define the function after manufacture.

ROM

AND: Fixed

OR: Programmable

PAL

AND: Programmable

OR: Fixed

PLA

AND: Programmable

OR: Programmable

ROM — Read-Only Memory

ROM stores a fixed lookup table: given an n-bit address input, it outputs the pre-stored m-bit data word. As a combinational circuit, the address lines are inputs and the data lines are outputs — no clock, no state.

ROM Structure

AND Array ○ Fixed

Fixed connections — hardwired at manufacture. Implements full address decode.

Inputs: n address lines (A₀–Aₙ₋₁)

→

OR Array ✦ Programmable

Fuse-based connections — you choose which product terms sum into each output.

Outputs: m data lines (D₀–Dₘ₋₁)

Product terms available: 2ⁿ word lines (full address decode — all minterms)

ROM as Combinational Logic

A 2ⁿ × m ROM stores a complete truth table for m output functions of n variables. Each address is a minterm; the stored data is the output combination.

Example: 4-variable, 3-output function → 16×3 ROM (16 addresses, 3 data bits)

No simplification needed — just store the truth table values directly.

Types of ROM

Mask ROMOne-time

Fixed at manufacture — cheapest for high volume. Can never be changed.

PROMWrite-once

Programmable once by user with a "PROM programmer" — fuses blown by high current.

EPROMUV-erasable

Erasable with UV light (shine UV for ~20 min to reset). Then reprogram.

EEPROMElectrical erase

Electrically erasable byte-by-byte. The basis of modern Flash memory.

PAL — Programmable Array Logic

PAL has a programmable AND array (you define the product terms) connected to a fixed OR array (each output gets a fixed number of product terms OR-ed together). This is the most common PLD architecture.

PAL Structure

AND Array ✦ Programmable

Fuse-based connections — you choose which inputs reach which product terms.

Inputs: n input variables + their complements

→

OR Array ○ Fixed

Fixed connections — hardwired. Each output OR-sums a fixed set of product terms.

Outputs: m output functions

Product terms available: P product terms per output (fixed — e.g., 4 PTs each)

How to program a PAL

1. Express each output function in SOP form

2. Each SOP product term = one row of the AND array

3. Blow fuses to create the desired product terms

4. The OR array then sums them (fixed, you can't change which PTs sum into which output)

Key limitation

Product terms cannot be shared between output functions. If two outputs share the same product term, you must duplicate it — wasting capacity.

PAL Example

Implement: F₁(A,B,C) = AB + BC + ĀC F₂(A,B,C) = A̅B̅C̅ + ABC PAL AND array programs: PT₁: A·B → to F₁ OR gate PT₂: B·C → to F₁ OR gate PT₃: Ā·C → to F₁ OR gate PT₄: Ā·B̄·C̄ → to F₂ OR gate PT₅: A·B·C → to F₂ OR gate

PLA — Programmable Logic Array

PLA has both the AND and OR arrays programmable. This is the most flexible PLD — product terms can be shared between multiple outputs, reducing the total number of product terms needed.

PLA Structure

AND Array ✦ Programmable

Fuse-based connections — you choose which inputs reach which product terms.

Inputs: n input variables + their complements

→

OR Array ✦ Programmable

Fuse-based connections — you choose which product terms sum into each output.

Outputs: m output functions

Product terms available: k product terms — shared among all outputs

PLA Advantage: Shared product terms

If F₁ and F₂ both need product term A·B, PLA only needs one AND gate for it — the OR array routes it to both outputs. PAL would need two separate AND gates.

PLA Disadvantage

More programmable connections = more fuses = slower (higher propagation delay) and more expensive than PAL. Optimising PLA also requires special algorithms.

PLA Example — shared product term

Implement: F₁ = AB + ĀC F₂ = AB + B̄C PLA product terms: PT₁: A·B → to F₁ AND F₂ (shared!) PT₂: Ā·C → to F₁ only PT₃: B̄·C → to F₂ only Only 3 PTs needed (PAL would need 4)

ROM vs PAL vs PLA — Full Comparison

Feature	ROM	PAL	PLA
AND array	Fixed (full decoder)	Programmable	Programmable
OR array	Programmable (data stored)	Fixed	Programmable
Product terms	All 2ⁿ minterms (exhaustive)	Limited per output	Shared, limited total
Flexibility	Maximum (stores all minterms)	Medium	High (sharing allowed)
Speed	Slower (full decode)	Fastest	Slower (2 prog arrays)
Cost	Higher for many variables	Low	Medium
Reprogrammable?	EEPROM/Flash only	Usually one-time (SPLD)	Usually one-time
Best for	Lookup tables, code conversion	Simple SOP with few PTs	Complex logic, PT sharing

Practice & Self-Assessment

Active Recall Questions

Answer each question from memory before revealing the answer.

What are the two Boolean expressions for a Half Adder? Which gates implement them?

How is a Full Adder constructed from Half Adders? How many gates in total?

What is the key difference between an Encoder and a Decoder?

Write the output expression for a 4:1 MUX. Which inputs are selected for S₁=1, S₀=0?

What is the difference between PAL and PLA? Which is more flexible?

Exam-Style Questions

These are representative of TU BCA past paper questions for Unit 3.

Design a Full Adder circuit. Write the Boolean expressions for Sum and Carry-out, and show how it can be implemented using two Half Adders.

5 marks

Explain a 4:1 Multiplexer with truth table. Implement F(A,B) = AB + Ā using a 4:1 MUX.

5 marks

Design a 2-to-4 decoder with active-HIGH outputs. Write Boolean expressions for all outputs and draw the logic diagram.

4 marks

Explain the ripple carry adder with a diagram. What is its main disadvantage? How does carry lookahead address this?

5 marks

Compare ROM, PAL and PLA. Which is most flexible and why?

4 marks

Mini-Test

8 multiple-choice questions. Select one answer per question, then submit.

Q1. The Sum output of a Half Adder is implemented using which gate?

Q2. A 4-bit ripple carry adder requires how many Full Adder circuits?

Q3. Which gate is used for both the Sum of a Half Adder and the Difference of a Half Subtractor?

Q4. A 3:8 decoder has how many output lines?

Q5. A 4:1 MUX requires how many select lines?

Q6. The Borrow output of a Half Subtractor is:

Q7. In a PAL (Programmable Array Logic), which array is programmable?

Q8. Binary-to-Gray code conversion: which gate is used?

How to Remember Unit 3

Unit 3 has many circuits to memorise. These shortcuts and patterns tie everything together.

Adders & Subtractors — The Pattern

The Symmetric Relationship

Sum = A ⊕ B

Diff = A ⊕ B

IDENTICAL! Both use XOR.

Carry = A · B

Borrow = Ā · B

Carry uses A; Borrow uses Ā (NOT A).

Key insight: HA and HS differ ONLY in the Carry/Borrow output. The difference/sum is always XOR. The carry/borrow is AND — just with A complement for subtractor.

⊕

XOR = Sum/Difference, AND = Carry/Borrow

For any adder or subtractor, the output is XOR (for the bit result) and AND (for carry/borrow). For subtractor, the borrow's A input is complemented.

HA Sum = A⊕B, Carry = A·B HS Diff = A⊕B, Borrow = Ā·B

🔗

Full = Half + Half + OR

A Full Adder uses two Half Adders plus an OR gate. The first HA adds A+B, the second HA adds that sum with Cin, and OR combines both carries.

Cout = HA₁.C + HA₂.C (OR the two carries)

🌊

Ripple = chain of FAs

A 4-bit adder is just 4 FAs connected in a chain. The carry 'ripples' left to right. Disadvantage: slow (carry must propagate through all 4 FAs).

FA₀ → C₁ → FA₁ → C₂ → FA₂ → C₃ → FA₃ → Cout

⚡

CLA: G+P = look ahead

CLA computes all carries at once using Generate (G=AB) and Propagate (P=A⊕B). No ripple — all carries computed in 2 gate delays.

Gᵢ = Aᵢ·Bᵢ (generates carry) Pᵢ = Aᵢ⊕Bᵢ (propagates carry)

Encoder & Decoder — n and 2ⁿ

The "n and 2ⁿ" Rule

2ⁿ → nEncoder

2ⁿ inputs, n outputs. One-hot to binary.

8-to-3: 8 inputs → 3-bit code

n → 2ⁿDecoder

n inputs, 2ⁿ outputs. Binary to one-hot.

3-to-8: 3-bit code → 8 one-hot outputs

Decoder = minterm generator. Each output is exactly one minterm. Use a decoder + OR gate to implement any Boolean function.

MUX & DEMUX — Quick Patterns

🎛️

MUX: Select number = select binary

The select lines S₁,S₀ form a 2-bit binary number. That number tells you which input is selected. S₁=1, S₀=0 → binary 10 = 2 → I₂ selected.

S₁S₀=00→I₀, 01→I₁, 10→I₂, 11→I₃

🔌

n select lines → 2ⁿ channels

MUX: n select lines → 2ⁿ data inputs. DEMUX: n select lines → 2ⁿ outputs. Same rule, opposite direction.

2 select → 4 channels (4:1 MUX / 1:4 DEMUX) 3 select → 8 channels (8:1 / 1:8)

📊

MUX as function generator

4:1 MUX → any 2-variable function. Connect A,B to S₁,S₀. Set I₀–I₃ = truth table values. 8:1 MUX → any 3-variable function.

F = A⊕B: set I₀=0, I₁=1, I₂=1, I₃=0 (same as XOR truth table)

↔️

DEMUX = Decoder + Enable

Set data input D=1 on a DEMUX — it behaves exactly like a decoder. The select lines choose the active output. DEMUX is decoder with a data input.

1:4 DEMUX with D=1 → same as 2:4 decoder

Code Converters & Parity

🔀

Binary→Gray: XOR adjacent bits

MSB of Gray = MSB of binary. Each subsequent Gray bit = XOR of that binary bit and the previous one. Direction: left to right through the binary bits.

Binary 1011 → Gray:{" "}G[3]=1, G[2]=1⊕0=1, G[1]=0⊕1=1, G[0]=1⊕1=0{" "}Gray = 1110

🔄

Gray→Binary: XOR accumulates

MSB of Binary = MSB of Gray. Each subsequent binary bit = XOR of the previous BINARY bit with the current GRAY bit. Uses previously computed binary, not previous gray.

Gray 1110 → Binary:{" "}B[3]=1, B[2]=1⊕1=0, B[1]=0⊕1=1, B[0]=1⊕0=1{" "}Binary = 1011 ✓

✓

Even parity: XOR all data bits

Parity bit P = XOR of all data bits (for even parity). XOR of all bits including parity should equal 0 at receiver. If result = 1, an error occurred.

Data: 1011 → P = 1⊕0⊕1⊕1 = 1{" "}Transmitted: 10111 (data + parity)

3️⃣

Excess-3 = BCD + 3

To convert BCD to Excess-3, just add 0011 (3) using a 4-bit adder. Reverse: subtract 3 (add 1101 = two's complement of 3).

BCD 0101 (5) + 0011 = 1000 (XS3 for 5)

ROM / PAL / PLA — Memory Anchor

The "Fixed vs Programmable" Table

ROM

AND: ○ Fixed

OR: ✦ Prog

"Remember Output Mapping"

PAL

AND: ✦ Prog

OR: ○ Fixed

"Programmable AND, Locked OR"

PLA

AND: ✦ Prog

OR: ✦ Prog

"Programmable Logic Array — all Programmable"

Quick Revision Summary

Before the Exam: Unit 3 Checklist

✓Can write Boolean expressions for Half Adder (Sum + Carry)

✓Can write Boolean expressions for Full Adder (Sum + Cout)

✓Can construct Full Adder from two Half Adders (HA₁ + HA₂ + OR)

✓Know how carry ripples in a 4-bit ripple carry adder

✓Understand G (generate) and P (propagate) in CLA

✓Know the BCD adder correction rule (add 6 when sum > 9)

✓Can write Half Subtractor expressions (Diff and Borrow)

✓Can draw a 2:4 decoder with all Boolean expressions

✓Know 8:3 encoder expressions (A₂ = I₄+I₅+I₆+I₇, etc.)

✓Understand priority encoder: highest input wins

✓Can implement any 2-variable function using a 4:1 MUX

✓Know Binary→Gray conversion algorithm (XOR adjacent bits)

✓Know Gray→Binary conversion algorithm (XOR accumulates)

✓Know parity generator: P = XOR of all data bits (even parity)

✓Can compare ROM, PAL, and PLA (AND/OR programmable)