CSC 211

Digital Logic & Circuit Design

Comprehensive Study Guide

■ Lecture Notes — Organized, Refined & Enhanced

Chapter 1 Logic Gates: NOT, AND, OR, NAND, NOR, EX-OR, EX-NOR

Chapter 2 Boolean Algebra, Minimisation, Karnaugh Maps

Chapter 3 Combinational Circuits: Adders, Comparators, Encoders

Chapter 4 Flip-Flops: SR, Gated SR, D-type, JK, Edge-Triggered

Chapter 5 Sequential Circuits: Registers, Shift Registers, Counters

Chapter 6 Finite State Machines: Moore & Mealy Models, Design

 CSC 211 — Digital Logic & Circuit Design

Table of Contents

Logic Gates
Ch 1
NOT · AND · OR · NAND · NOR · EX-OR · EX-NOR

Boolean Algebra & Minimisation

Ch 2
Laws · Theorems · Karnaugh Maps · Don't-Care States

Combinational Circuits
Ch 3
Half/Full Adders · Parallel/Serial · Comparators · Encoders

Flip-Flops (Memory Elements)

Ch 4
SR Latch · Gated SR · D-type · JK · Master-Slave · Edge-Triggered

Registers & Counters

Ch 5
Registers · Shift Registers · Ring · Binary · Ripple · IC Counters

Sequential Circuit Design

Ch 6
FSM · Moore & Mealy · State Tables · Excitation Equations

Study Guide — Organized & Enhanced Page 2

 CSC 211 — Digital Logic & Circuit Design

Chapter 1
Logic Gates
The Building Blocks of Digital Circuits

1.1 What are Logic Gates?

Gates are the means by which logic signals are switched in or out of digital circuits. A gate is either closed or open according
to the voltage level applied at its input. Since a gate performs a binary operation, there are two corresponding voltage levels
— typically 5 V (HIGH = Logic 1) and 0 V (LOW = Logic 0). This is known as Positive Logic. The reverse (0 V = HIGH) is
Negative Logic.

★ Logic 1 = HIGH = 5 V | Logic 0 = LOW = 0 V (Positive Logic convention)

★ Gates perform: NOT, AND, OR, NAND, NOR, EX-OR, EX-NOR

★ The output of any gate depends solely on its current inputs (combinational logic).

1.11 NOT Gate (Inverter)

Boolean Function: Y = ■

Produces the complement of its input. A logic 0 becomes 1 and vice versa.

Key Uses: Invert logic signals; used as building block in all other gates.

A Y

0 1

1 0

Study Guide — Organized & Enhanced Page 3

 CSC 211 — Digital Logic & Circuit Design

1.12 AND Gate

Boolean Function: Y = AB

Output is 1 ONLY when ALL inputs are 1. With one input held at 0 the output is inhibited; held at 1 the other input passes
through.

Key Uses: Enable/inhibit a signal; combine conditions that must ALL be true.

A B Y

0 0 0

0 1 0

1 0 0

1 1 1

1.13 OR Gate
Boolean Function: Y = A + B

Output is 1 if ANY input is 1. Output is 0 only when ALL inputs are 0.

Key Uses: Combine conditions where at least one must be true; switch ON data.

A B Y

0 0 0

0 1 1

1 0 1

1 1 1

1.14 NAND Gate

Boolean Function: Y = ■■B■ (= NOT AND)

Output is 0 ONLY when all inputs are 1; otherwise output is 1. Universal gate — any function can be built from NAND gates
alone.

Key Uses: Universal building block; inverter (tie all inputs together); AND followed by NOT.

A B Y

0 0 1

0 1 1

1 0 1

1 1 0

Study Guide — Organized & Enhanced Page 4

 CSC 211 — Digital Logic & Circuit Design

1.15 NOR Gate

Boolean Function: Y = ■+B■ (= NOT OR)

Output is 1 ONLY when ALL inputs are 0. Also a universal gate.

Key Uses: Universal building block; inverter (tie all inputs together); OR followed by NOT.

A B Y

0 0 1

0 1 0

1 0 0

1 1 0

1.16 EX-OR Gate (Exclusive OR)

Boolean Function: Y = ■B + AB■ = A ⊕ B

Output is 1 only when inputs are DIFFERENT. Output is 0 when inputs are equal.

Key Uses: Comparator (output 1 when inputs differ); arithmetic sum bit; programmable inverter.

A B Y

0 0 0

0 1 1

1 0 1

1 1 0

1.17 EX-NOR Gate (Exclusive NOR)

Boolean Function: Y = AB + ■B■ = A ■ B

Output is 1 only when inputs are EQUAL. The invert of EX-OR.

Key Uses: Equality detector (output 1 when inputs match); programmable inverter (opposite polarity to EX-OR).

A B Y

0 0 1

0 1 0

1 0 0

1 1 1

Study Guide — Organized & Enhanced Page 5

 CSC 211 — Digital Logic & Circuit Design

1.2 Gate Summary Comparison

Gate Function Output = 1 when… Universal?

NOT Y=■ Input = 0 No

AND Y = AB ALL inputs = 1 No

OR Y = A+B ANY input = 1 No

NAND Y = ■B NOT all inputs = 1 Yes

NOR Y = ■+B■ ALL inputs = 0 Yes

EX-OR Y = A⊕B Inputs are DIFFERENT No

EX-NOR Y = A■B Inputs are EQUAL No

Study Guide — Organized & Enhanced Page 6

 CSC 211 — Digital Logic & Circuit Design

Chapter 2
Boolean Algebra & Minimisation
Laws · Theorems · Karnaugh Maps · Don't-Care Conditions

2.1 Basic Laws of Boolean Algebra

Boolean algebra provides the mathematical framework for designing and simplifying logic circuits. The following rules allow us
to manipulate Boolean expressions to find a minimum implementation — i.e. one that uses the fewest gates.

Law AND form OR form

Identity x·1=x x+0=x

Null/Annul x·0=0 x+1=1

Idempotent x·x=x x+x=x

Complement x · x■ = 0 x + x■ = 1

Involution x■■ = x (double complement)

Commutative xy = yx x+y = y+x

Associative (xy)z = x(yz) (x+y)+z = x+(y+z)

Distributive x(y+z) = xy+xz x+(yz) = (x+y)(x+z)

Absorption x(x+y) = x x + xy = x

De Morgan's x■■ = x■+■ x■+■ = x■·■

2.2 Minterms & Maxterms

For n variables there are 2n possible input combinations. Each combination gives a minterm (AND product, = 1 for one row)
or a maxterm (OR sum, = 0 for one row). A Boolean function expressed as a sum of minterms is written Σ(m) and as a
product of maxterms Π(M). A maxterm is the dual of the corresponding minterm: Mi = m■i.

Sum of Minterms (SOP): F = Σ(minterm numbers) → function is 1 at those rows

Product of Maxterms (POS): F = Π(maxterm numbers) → function is 0 at those rows

Example: F = ABC + ■BC■ + AB■C = Σ(1,5,6) = Π(0,2,3,4,7)

2.3 Karnaugh Map Minimisation

Study Guide — Organized & Enhanced Page 7

 CSC 211 — Digital Logic & Circuit Design

The Karnaugh map (K-map) is a graphical tool that facilitates Boolean minimisation by visually identifying groups of 1s (for
SOP) or 0s (for POS) that differ by only one variable at a time (adjacent cells). The map is arranged so that adjacent cells
differ by exactly one literal (Gray code ordering).

Grouping Rules
• Group size: Must be a power of 2: 1, 2, 4, 8, 16 … The larger the group, the simpler the resulting term.
• Adjacency: Cells are adjacent if they differ by one bit. The map wraps around (edges and corners are adjacent).
• Overlap: A cell may belong to more than one group — use this to form the largest possible groups.
• Coverage: Every 1 (for SOP) must be covered by at least one group.
• Redundancy: A group that is entirely covered by other groups is redundant and can be omitted.
• Don't-Cares (X): Treat as 1 or 0 to maximise group sizes, but they need not be covered themselves.

Reading Off the Minimised Expression

Each group of 2k cells eliminates k variables from the term. Variables that appear in both complemented and
uncomplemented form within a group cancel out. The minimised SOP expression is the OR of all group terms.

★ Largest groups → fewest literals → simplest circuit.

★ Use the Consensus Theorem to eliminate redundant terms: if ABD is covered by ABC and BCD, then ABD is redundant.

★ For POS minimisation group the 0s — the complement of each group gives a sum factor.

Study Guide — Organized & Enhanced Page 8

 CSC 211 — Digital Logic & Circuit Design

Chapter 3
Combinational Circuits
Adders · Comparators · Encoders

3.1 Half Adder

The half adder adds two single bits (A and B) and produces a Sum (S) and a Carry (C). It has no carry input, so it can only be
used for the least significant bit position.

A B S (Sum) C (Carry)

0 0 0 0

0 1 1 0

1 0 1 0

1 1 0 1

Equations: S = A ⊕ B (EX-OR) C = AB (AND)

3.2 Full Adder

The full adder adds three bits: A, B and a carry-in Ci, producing Sum S and carry-out Co. Multiple full adders are cascaded to
add multi-bit numbers.

A B C■ S C■

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

S = A ⊕ B ⊕ Ci Co = Ci(A⊕B) + AB = Ci(AB■ + ■B) + AB

A full adder = two half adders + an OR gate.

Study Guide — Organized & Enhanced Page 9

 CSC 211 — Digital Logic & Circuit Design

3.3 Parallel Adder (Ripple-Through)

n full adders are connected in series so that the carry-out of each stage feeds the carry-in of the next more-significant stage.
The carry ripples through from LSB to MSB, so the final result is valid only after all propagation delays have settled. A 4-bit
parallel adder uses four full adders with Ci = 0 at the LSB stage.

★ Speed is limited by carry propagation delay — O(n) for n bits.

★ Look-Ahead Carry Adders pre-compute carries to run in O(log n) time.

★ A 4-bit parallel adder produces a 5-bit result: C■ S■ S■ S■ S■.

3.4 Serial Adder

Both operands are stored in shift registers and fed one bit at a time — from LSB to MSB — into a single full adder. A D-type
latch holds the carry between clock pulses. After n clock pulses the n-bit sum is assembled in the sum shift register.

3.5 Comparators
A comparator checks the relative magnitude of two binary numbers A and B, producing three outputs: A > B, A = B, A < B. For
a single bit, the EX-OR gate detects inequality (A ≠ B) and EX-NOR detects equality (A = B). Multi-bit comparators check from
the most significant bit downward.

1-bit: A=B → A ■ B (EX-NOR = 1 when equal)

A>B: AB■ = 1 (A is 1 and B is 0)

A<B: ■B = 1 (A is 0 and B is 1)

Multi-bit: Compare MSBs first; if equal move to next bit.

3.6 Encoders & Decoders

An encoder converts 2n input lines to an n-bit binary code (e.g. a 10-key keyboard encoder). A decoder performs the
reverse, activating one of 2n outputs. These are purely combinational circuits built from OR/AND gates.

Study Guide — Organized & Enhanced Page 10

 CSC 211 — Digital Logic & Circuit Design

Chapter 4
Flip-Flops
Memory Elements for Sequential Circuits

4.1 Introduction to Flip-Flops

Flip-flops are sequential logic elements that store one bit of information. Unlike combinational logic, the output depends on
both current inputs and the current stored state. They are built from feedback connections of logic gates and form the
memory elements of digital systems.

★ Flip-flops are bistable: they remain in one of two stable states (Q=0 or Q=1) until triggered.

★ They are used as: memory cells, registers, counters, and state machines.

★ The complementary output Q■ is always the inverse of Q.

4.2 SR Flip-Flop (SR Latch)

Built from two cross-coupled NOR (or NAND) gates. S = Set forces Q=1; R = Reset forces Q=0. When both S=R=0 the latch
holds its previous state. The condition S=R=1 is forbidden (NOR implementation) or unused (NAND) as it causes both
outputs to be 0 (or 1), which is indeterminate when inputs return to 0.

S R Q+ Q■+

0 0 Q Q■ (hold)

0 1 0 1 (reset)

1 0 1 0 (set)

1 1 — — (forbidden/unused)

Excitation Equation: Q+ = S + R■Q (excitation equation)

Note: Q+ means the next state. The forbidden condition S=R=1 must never occur in NOR implementation.

Study Guide — Organized & Enhanced Page 11

 CSC 211 — Digital Logic & Circuit Design

4.3 Gated SR Flip-Flop (Clocked SR)

A clock (gate) input G controls when the SR inputs take effect. When G=0 the latch ignores S and R and holds its state. When
G=1 the latch follows the normal SR truth table. This introduces synchronism — the latch only changes at clock-determined
instants.

G S R Q+

0 X X Q (hold regardless)

1 0 0 Q (hold)

1 0 1 0 (reset)

1 1 0 1 (set)

1 1 1 — (unused)

Note: X = don't care. The latch responds only when G=1.

4.4 D-Type Flip-Flop (Data Latch)

Eliminates the forbidden state by connecting D directly to S and D■ to R. When clocked (C=1) the output Q follows the D
input. When C=0 the output holds its previous value. Also called a data latch — it captures ("latches") the data present when
clocked.

C D Q+

0 X Q (hold)

1 0 0

1 1 1

Excitation Equation: Q+ = D (when clock = 1)

Note: Q+ = D when clocked. The D flip-flop is the most commonly used in registers.

Study Guide — Organized & Enhanced Page 12

 CSC 211 — Digital Logic & Circuit Design

4.5 JK Flip-Flop
Solves the SR forbidden state: when J=K=1 the flip-flop toggles (Q → Q■). J behaves like S (set) and K like R (reset). The
toggle condition makes the JK the most versatile flip-flop. It is implemented as a master-slave arrangement to prevent racing
(the "ones-catching" problem).

J K Q+

0 0 Q (hold)

0 1 0 (reset)

1 0 1 (set)

1 1 Q■ (toggle)

Excitation Equation: Q+ = JQ■ + K■Q

Note: With J=K=1 permanently the JK acts as a T (toggle) flip-flop, toggling on every clock edge.

4.6 Master-Slave JK & Edge-Triggered Flip-Flop

The master-slave configuration uses two gated SR stages in series. The master latches data on the HIGH clock phase; the
slave transfers it to the output on the LOW phase. This eliminates racing but has a "ones-catching" defect corrected by the
edge-triggered flip-flop, which responds only to the rising or falling edge of the clock.

Clock Edge Action

Rising ↑ Data captured (positive edge-triggered)

Falling ↓ Data captured (negative edge-triggered)

High/Low level No change (edge-triggered only)

Note: Edge-triggered flip-flops are the most common in modern synchronous design.

Flip-Flop Excitation Table Summary

The excitation table shows what inputs are required to achieve a desired state transition (Q → Q+). This is the reverse of the
truth table and is essential for sequential circuit design.

Q → Q+ SR: S / R JK: J / K D T

0→0 0/X 0/X 0 0

0→1 1/0 1/X 1 1

1→0 0/1 X/1 0 1

1→1 X/0 X/0 1 0

X = don't care (either 0 or 1 gives the required transition).

Study Guide — Organized & Enhanced Page 13

 CSC 211 — Digital Logic & Circuit Design

Chapter 5
Registers & Counters
Storage, Shift Registers, Ring & Binary Counters

5.1 Registers
A register is an array of flip-flops used to store a binary word. Each flip-flop holds one bit. SR, D-type and JK flip-flops can all
be used. A 4-bit register stores a 4-bit word. Data is loaded in parallel (all bits simultaneously) and held until the next clock
pulse.

★ Transfer A→B: enable AND gates so data on A's Q outputs appears at B's D inputs; clock B.

★ A parallel-load register uses one D flip-flop per bit, all clocked simultaneously.

5.2 Shift Registers

A shift register moves data one bit position per clock pulse. Flip-flops are chained serially: each Q output feeds the D (or J/K)
input of the next stage.

Right Shift: Data enters at the MSB (D3) and propagates right toward LSB on each clock. Used to serially receive data MSB first
or to divide by 2 (binary right shift = ÷2).
Left Shift: Data enters at the LSB (D0) and propagates left toward MSB on each clock. Used to multiply by 2 or to serially receive
data LSB first.

5.3 Universal Shift Register

Controlled by mode-select lines S1 and S2 to operate in four modes:

S■S■ = 00 Hold — data retained, no change.

S■S■ = 01 Right Shift — serial data shifts right.

S■S■ = 10 Left Shift — serial data shifts left.

S■S■ = 11 Parallel Load — all bits loaded simultaneously from D inputs.

5.4 Ring Counter

A ring counter is a shift register with the output of the last flip-flop fed back to the input of the first. With n flip-flops it has n
distinct states (a "1" circulates). An initiate signal sets one flip-flop to 1 and all others to 0. The ring counter is a modulo-n
counter using n flip-flops, but it wastes states compared to a binary counter (which needs only log■n flip-flops).

Clock Pulse Q■ Q■ Q■ Q■

Initiate 0 0 0 1

Study Guide — Organized & Enhanced Page 14

 CSC 211 — Digital Logic & Circuit Design

1 0 0 1 0

2 0 1 0 0

3 1 0 0 0

4 0 0 0 1

5.5 Counters
A counter counts clock pulses. It can count up, down, or both, and is characterised by its modulus (the number of states it
passes through before repeating).

• Binary (Synchronous):
All flip-flops clocked simultaneously. JK or D flip-flops. n flip-flops → modulo 2■. The binary counter counts 0000 to 1111
(mod-16 for n=4).

• Ripple (Asynchronous):
Clock applied only to LSB flip-flop. Each subsequent flip-flop is clocked by the Q output of the previous stage (a 1→0 transition
toggles the next). Simpler but slower due to cumulative delays.

• Modulo-4 (Divide-by-4):
Counts 00 → 01 → 10 → 11 → 00. Requires 2 flip-flops. Excitation equations: D■ = Q■⊕Q■, D■ = Q■■.

• Ring Counter:
n flip-flops, one hot encoding, modulo-n with n states. Easy decoding but inefficient use of flip-flops.

• IC Counter '93:
4-stage ripple counter with isolated first stage (÷2) + 3-stage (÷8) = ÷16. Can be cascaded for divide-by-12 (type '92) or
divide-by-10 (LS90).

★ An N-state machine needs ■log■N■ flip-flops.

★ Synchronous counters are faster and glitch-free; ripple counters are simpler.

★ Binary counter with n stages divides the clock by 2■.

Study Guide — Organized & Enhanced Page 15

 CSC 211 — Digital Logic & Circuit Design

Chapter 6
Sequential Circuit Design
Finite State Machines · Moore & Mealy · Excitation Equations

6.1 Finite State Machines (FSMs)

A finite state machine is a mathematical model of a sequential circuit comprising: a finite set of states, a set of inputs, a set
of outputs, a next-state function (transition function), and an output function. The machine changes state synchronously
at each clock pulse.

State: A condition that remembers the past history relevant to future outputs.

State Diagram: Graphical representation — circles = states, arrows = transitions labelled with input/output.

State Table: Tabular form listing Present State, Input, Next State, Output.

Excitation Table: Extends state table with required flip-flop inputs for each transition.

6.2 Moore Model

In the Moore model, the output depends only on the present state (not on the input). Each state has a fixed output. The
output is associated with the state itself (shown inside the circle).

Z = f(Sk+1) where Sk+1 = f(Sk, M)

So: Z = f(f(Sk, M)) — output lags one clock behind the input change.

6.3 Mealy Model

In the Mealy model, the output depends on both the present state and the current input. The output can change
immediately when the input changes (no extra clock needed). Outputs are labelled on the transition arrows (input/output).

Z = f■(Sk, M) Sk+1 = f■(Sk, M)

Feature Moore Model Mealy Model

Output depends on State only State AND input

On transition arrow
Output location Inside state circle (input/output)

Output changes With state (next clock) Immediately with input

Typical state count More states needed Fewer states (more efficient)

Study Guide — Organized & Enhanced Page 16

 CSC 211 — Digital Logic & Circuit Design

Stability More stable (no glitches) Can have transient glitches

6.4 Design Procedure for Synchronous Sequential Circuits

1 Step 1 — Problem Statement
Describe the circuit behaviour: what sequence must it detect/generate? What outputs are required?

2 Step 2 — State Diagram

Draw a state diagram with circles for states and labelled arrows for transitions (Moore or Mealy).

3 Step 3 — State Table

Convert the diagram to a table: Present State | Input | Next State | Output.

4 Step 4 — State Assignment

Assign binary codes to states. n states → ■log■n■ flip-flops with 2■ possible codes.

5 Step 5 — Transition/Excitation Table

Add columns for required flip-flop inputs using the flip-flop excitation table.

6 Step 6 — Excitation Equations

Use Karnaugh maps on each flip-flop input column to derive minimised Boolean expressions.

7 Step 7 — Output Equation

Derive the output Boolean expression from the output column using K-maps.

8 Step 8 — Circuit Implementation

Draw the combinational circuit implementing the excitation and output equations, plus the flip-flop memory.

6.5 Synchronous vs Asynchronous Sequential Circuits

Asynchronous (Fundamental
Feature Synchronous (Clocked) Mode)

State changes Only at clock edges Immediately when input changes

Memory elements Edge-triggered flip-flops Unclocked latches / gate delays

Harder — races and hazards

Design complexity Easier — race-free possible

Potentially faster (no clock

Speed Limited by clock period overhead)

Level Mode (fundamental) · Pulse

Sub-types — Mode

Study Guide — Organized & Enhanced Page 17

 CSC 211 — Digital Logic & Circuit Design

6.6 Sequence Detector Example (Mealy)

Design a Mealy machine that detects the sequence 011 in a serial bit stream. The machine uses JK flip-flops. With 4 states
(A–D) two flip-flops are required.

Present State Input M Next State Output Z

A (00) 0 A (00) 0

A (00) 1 B (01) 0

B (01) 0 C (10) 0

B (01) 1 D (11) 0

C (10) 0 A (00) 0

C (10) 1 D (01) 0

D (11) 0 C (10) 0

D (11) 1 D (11) 0

Excitation equations (from K-maps):

J■ = Q■ K■ = M■Q■■

J■ = M· K■ = M■ Z = Q■■Q■■M

Quick Revision — Key Formulae & Facts

★ Number of flip-flops needed = ■log■ N■ where N = number of states.

★ Moore output: Z = f(state only). Mealy output: Z = f(state, input).

★ Full adder: S = A⊕B⊕C■ Co = C■(A⊕B) + AB.

★ De Morgan's: x■■ = x■+■ and x■+■ = x■·■.

★ JK flip-flop: Q+ = JQ■ + K■Q. D flip-flop: Q+ = D. T flip-flop: Q+ = T⊕Q.

★ Karnaugh groupings must be powers of 2; wrap-around adjacency applies.

★ Ripple counter: n stages ÷ 2■. Binary synchronous counter uses toggle conditions.

★ SR forbidden: S=R=1 (NOR); SR unused: S=R=1 (NAND implementation).

Study Guide — Organized & Enhanced Page 18