DIGITAL LOGIC & COMPUTER

DESIGN
Comprehensive Study Notes
Covering All Units | M-23, M-24, M-25 PYQs | Mano DLCD & CSA, R.P. Jain, Stallings, Murdocca
UNIT 1: Boolean Algebra & Logic Gates
Reference: Mano DLCD Chapter 2 | R.P. Jain Chapter 3

1.1 What is Boolean Algebra?

Boolean Algebra is a mathematical system dealing with binary variables (0 and 1) and logical
operations. Introduced by George Boole in 1854, it forms the foundation of digital circuit design. Unlike
conventional algebra, variables can only take two values: TRUE (1) and FALSE (0).

PYQ: What is Boolean algebra, and how is it applied in digital logic? M-25 | 7 marks

Applications in Digital Logic:

• Designing combinational and sequential circuits
• Simplifying complex logic expressions to reduce gate count
• Implementing truth tables via logic gates (AND, OR, NOT, NAND, NOR, XOR)
• Verification of circuit equivalence
• Building ALUs, adders, multiplexers, encoders, decoders

1.2 Basic Postulates (Huntington Postulates)

Boolean Algebra is defined by the following postulates for binary variables A, B, C:
Postulate OR Form (+) AND Form (.)
Identity A+0=A A.1=A
Null/Dominance A+1=1 A.0=0
Idempotent A+A=A A.A=A
Complement A + A' = 1 A . A' = 0
Involution A'' = A A'' = A
Commutative A+B=B+A A.B=B.A
Associative A+(B+C) = (A+B)+C A.(B.C) = (A.B).C
Distributive A.(B+C) = A.B+A.C A+B.C = (A+B).(A+C)

1.3 Important Theorems

Absorption Laws:
A + AB = A
A(A + B) = A
Consensus Theorem:
AB + A'C + BC = AB + A'C (BC is redundant)

1.4 De Morgan's Theorem

PYQ: Discuss De Morgan's theorem with Boolean expressions and truth M-25 | 7 marks
tables.

De Morgan's Theorem provides a way to transform AND/OR expressions using complement. It has two
forms:

Theorem 1:
(A + B)' = A' . B'
The complement of a sum equals the product of the complements.

Theorem 2:
(A . B)' = A' + B'
The complement of a product equals the sum of the complements.

Proof via Truth Table (De Morgan's First Theorem):

A B A+B (A+B)' A' B' A'.B'
0 0 0 1 1 1 1
0 1 1 0 1 0 0
1 0 1 0 0 1 0
1 1 1 0 0 0 0

Columns (A+B)' and A'.B' are identical → Theorem 1 proved.

Proof via Truth Table (De Morgan's Second Theorem):

A B A.B (A.B)' A' B' A'+B'
0 0 0 1 1 1 1
0 1 0 1 1 0 1
1 0 0 1 0 1 1
1 1 1 0 0 0 0

Columns (A.B)' and A'+B' are identical → Theorem 2 proved.

Gate-Level Representation:
De Morgan's Theorem allows replacing NAND gates with OR gates with inverted inputs, and NOR
gates with AND gates with inverted inputs. This is crucial for implementing circuits using only NAND or
only NOR gates (universal gates).
• NAND gate implements: (A.B)' = A'+B' — equivalent to OR with inverted inputs
• NOR gate implements: (A+B)' = A'.B' — equivalent to AND with inverted inputs

1.5 Boolean Functions: SOP and POS Forms

A Boolean function can be expressed in two canonical forms:

Sum of Products (SOP) / Minterm Expansion:

Each product term (minterm) has all variables appearing exactly once. Denoted as Sigma (m).
F(A,B,C) = A'B'C + A'BC + AB'C' = Sum of minterms

Product of Sums (POS) / Maxterm Expansion:

Each sum term (maxterm) has all variables appearing exactly once. Denoted as Pi (M).
F(A,B,C) = (A+B+C)(A'+B+C')(A+B'+C) = Product of maxterms

1.6 Minterms and Maxterms

Minterm (m):
A minterm of n variables is a product term in which each variable appears exactly once (either
complemented or uncomplemented). For n variables, there are 2^n minterms.

PYQ: Prove that the logical sum of all minterms of a Boolean function of 2 M-24 | 2 marks
variables is 1.

Proof: Sum of All Minterms = 1 (2 variables)

For 2 variables A and B, the minterms are:
Row A B Minterm Symbol
0 0 0 A'.B' m0
1 0 1 A'.B m1
2 1 0 A.B' m2
3 1 1 A.B m3

Logical sum of all minterms:

m0 + m1 + m2 + m3 = A'B' + A'B + AB' + AB
= A'(B' + B) + A(B' + B)
= A'(1) + A(1) [since B + B' = 1]
 = A' + A
= 1 [since A + A' = 1]
Therefore, the logical sum of all minterms for 2 variables = 1. (Proved)

1.7 Proof: x'y + xy' = x + y

PYQ: Using Boolean algebra prove: x'y + xy' = x + y M-24 | 2 marks

Proof using Boolean algebra:

LHS = x'y + xy'
= x'y + xy' + 0 [adding 0]
= x'y + xy' + xx' + yy' [A.A' = 0]
= x'y + yy' + xy' + xx' [rearranging]
= y(x' + y') + x(y' + x') [factoring]
= y(xy)' + x(xy)' [De Morgan]
Alternatively, a simpler proof:
LHS = x'y + xy'
RHS = x + y

x + y = x.1 + y.1 [identity]

= x(y + y') + y(x + x') [complement]
= xy + xy' + xy + x'y [distribute]
= xy + xy' + x'y [idempotent]
Also: x'y + xy' + xy = x'y + x(y'+y) = x'y + x = x + y (absorption). And x'y + xy' is a subset. Let's verify by
truth table:
x y x'y + xy' x+y
0 0 0 0
0 1 1 1
1 0 1 1
1 1 0 1

⚠ Note: Note: x'y + xy' = x XOR y, which is NOT equal to x + y in general (row 4 differs). The PYQ
question as stated has an error in it OR implies specific conditions. Always verify both LHS and RHS
with truth tables in your exam answer, then state the discrepancy or the examiner's intended
equivalence.

1.8 Logic Gates – Complete Overview

Gate Symbol Function Boolean Expression Truth Values (A,B->Y)
AND A.B Y = A.B 00->0, 01->0, 10->0, 11->1
OR A+B Y = A+B 00->0, 01->1, 10->1, 11->1
NOT A' Y = A' 0->1, 1->0
NAND (Universal) (A.B)' Y = (A.B)' 00->1, 01->1, 10->1, 11->0
NOR (Universal) (A+B)' Y = (A+B)' 00->1, 01->0, 10->0, 11->0
XOR A⊕B Y = A'B + AB' 00->0, 01->1, 10->1, 11->0
XNOR (A⊕B)' Y = AB + A'B' 00->1, 01->0, 10->0, 11->1

⚠ Note: NAND and NOR are called Universal Gates because any Boolean function can be
implemented using only NAND gates or only NOR gates. This has practical advantage as it reduces
IC chip variety needed.
UNIT 2: Number Representations & Computer Arithmetic
Reference: Mano DLCD Chapter 1 | Mano CSA Chapter 10 | Stallings Chapter 9

2.1 Number Systems Overview

System Base Digits Used Example
Binary 2 0, 1 (1011)₂ = 11₁₀
Octal 8 0-7 (13)₈ = 11₁₀
Decimal 10 0-9 (11)₁₀
Hexadecimal 16 0-9, A-F (B)₁₆ = 11₁₀

2.2 Binary to Gray Code Conversion

PYQ: Explain binary to gray and gray to binary conversion with circuit M-23 | 6 marks
diagram and truth table.

What is Gray Code?

Gray code (also called reflected binary code) is a binary numeral system where two successive values
differ in only ONE bit. This property makes it invaluable in reducing errors during transitions in digital
systems (e.g., encoders, A/D converters).

Binary to Gray Code Conversion Rules:

1. The Most Significant Bit (MSB) of the Gray code is the same as the MSB of the binary code.
2. Each subsequent Gray bit = XOR of current binary bit and previous binary bit.
G[n] = B[n] (for MSB)
G[i] = B[i+1] XOR B[i] (for all other bits, moving right)

Gray Code to Binary Conversion Rules:

3. The MSB of binary is same as MSB of Gray code.
4. Each binary bit = XOR of all Gray code bits from MSB to current position.
B[n] = G[n]
B[i] = B[i+1] XOR G[i]

4-bit Binary to Gray Code Truth Table:

Decimal Binary (B3B2B1B0) Gray (G3G2G1G0)
0 0000 0000
 1 0001 0001
2 0010 0011
3 0011 0010
4 0100 0110
5 0101 0111
6 0110 0101
7 0111 0100
8 1000 1100
9 1001 1101
10 1010 1111
11 1011 1110
12 1100 1010
13 1101 1011
14 1110 1001
15 1111 1000

Circuit Implementation:
Binary to Gray: Use XOR gates between adjacent binary bits.
G3 = B3
G2 = B3 XOR B2
G1 = B2 XOR B1
G0 = B1 XOR B0

Gray to Binary: Cascade XOR gates from MSB to LSB.

B3 = G3
B2 = B3 XOR G2
B1 = B2 XOR G1
B0 = B1 XOR G0

2.3 BCD (Binary Coded Decimal)

BCD represents each decimal digit by its 4-bit binary equivalent. Only codes 0000 to 1001 (0-9) are
valid; codes 1010-1111 are invalid.
Decimal BCD Code
0 0000
1 0001
2 0010
3 0011
4 0100
 5 0101
6 0110
7 0111
8 1000
9 1001

Example: 394₁₀ in BCD = 0011 1001 0100

2.4 Fixed-Point Representation

PYQ: What is fixed-point representation? M-25 | 2 marks

Fixed-point representation stores a number with the binary point at a FIXED, predefined position. The
position of the binary point is implied and not stored explicitly.
• Integer representation: binary point is assumed to be to the right of all bits
• Fractional representation: binary point is assumed at a fixed position within the word
• The range and precision are fixed; cannot handle very large or very small numbers
simultaneously

Example:
For an 8-bit word with binary point after bit 4:
Bits: b7 b6 b5 b4 . b3 b2 b1 b0
Integer part: 4 bits | Fractional part: 4 bits
10110110 => 1011.0110 = 11.375 in decimal

Sign Representation in Fixed-Point:

• Sign-Magnitude: MSB = 0 for positive, 1 for negative; rest = magnitude
• 1's Complement: Invert all bits for negative
• 2's Complement: Invert all bits and add 1; most widely used

2's Complement Representation:

For an n-bit number:
Positive numbers: same as sign-magnitude (MSB = 0)
Negative numbers: 2^n - |magnitude|
Example (8-bit): -46 in 2's complement
+46 = 00101110
1's complement = 11010001
2's complement = 11010010
Arithmetic with 2's Complement:
Addition: Add normally; ignore final carry out of MSB for the operation.
Example: 5 + (-3) = 00000101 + 11111101 = 00000010 = 2 (correct)
Subtraction: A - B = A + 2's complement of B

2.5 Floating-Point Representation

PYQ: Why is floating-point number more difficult to represent and process M-23 | 2 marks
than integer?

Why Floating-Point is More Complex than Integer:

5. Variable Precision: Unlike integers, floating-point involves sign, exponent, AND mantissa fields,
requiring complex parsing and operations.
6. Normalization: The mantissa must be normalized (kept within a specific range), adding extra
steps after every operation.
7. Special Cases: Must handle +∞, -∞, NaN (Not a Number), denormalized numbers, and +0/-0 —
integers have none of these.
8. Rounding Errors: Real numbers often cannot be represented exactly in binary floating-point,
causing rounding errors (e.g., 0.1 has no exact binary representation).
9. Complex ALU: Floating-point arithmetic units are much more complex than integer ALUs,
requiring separate exponent and mantissa handling with alignment shifts before add/subtract.
10. Alignment: Before adding two floating-point numbers, their exponents must be made equal by
shifting the mantissa — not needed for integers.

PYQ: Represent (+46.5)₁₀ as a floating-point binary number with 24 bits. M-24 | 6 marks
Mantissa 16 bits, exponent 8 bits.

IEEE-Style Floating-Point Format (24-bit):

The 24-bit format: 1 sign bit + 8 exponent bits + (implied 1 +) 15 mantissa bits, or as given: 1 bit sign +
8 bits exponent + 15 bits mantissa (totaling 24 bits). But the problem states 16-bit mantissa + 8-bit
exponent = 24 bits (sign embedded in sign bit = 1 bit + 15-bit mantissa + 8-bit exponent).
Following the standard approach with sign bit included in 16-bit mantissa field:
Step 1: Convert 46.5₁₀ to binary
46 / 2 = 23 R 0
23 / 2 = 11 R 1
11 / 2 = 5 R 1
5 / 2 = 2 R 1
2 / 2 = 1 R 0
1 / 2 = 0 R 1
46₁₀ = 101110₂
0.5 = .1₂
So 46.5₁₀ = 101110.1₂
 Step 2: Normalize
101110.1 = 0.1011101 × 2^6
(Normalized: mantissa is 0.1011101, exponent = 6)

Step 3: Encode into 24-bit format

Sign bit (positive) = 0
Exponent = 6 = 00000110 in 8 bits
Mantissa = .1011101 stored in 15 bits:
101110100000000 (fraction bits after decimal point)

Final 24-bit representation:

Sign (1) | Exponent (8) | Mantissa (15)
0 | 00000110 | 101110100000000
= 0 00000110 101110100000000

Floating-Point Format Structure (General):

Component Bits Description
Sign (S) 1 0 = positive, 1 = negative
Exponent (E) 8 Biased exponent (bias = 127 for IEEE 754 single)
Mantissa (M) 15/23 Fractional part of normalized number

⚠ Note: IEEE 754 uses biased exponents (excess-127 for single precision). The implicit leading 1 in
the mantissa saves one bit. Always normalize so the leading bit is 1 (or 0 for denormalized numbers).
UNIT 3: Combinational Logic – Adders, Subtractors, MUX,
DEMUX
Reference: Mano DLCD Chapter 4 | R.P. Jain Chapter 7 | Murdocca Chapter 3

3.1 Introduction to Combinational Circuits

A combinational circuit is one where the output at any instant depends ONLY on the current inputs —
there is no memory or feedback. The output is a purely combinational (Boolean) function of the inputs.

Design Procedure:
11. State the problem clearly
12. Determine the number of inputs and outputs
13. Assign letter symbols to each I/O
14. Derive the truth table
15. Obtain simplified Boolean expressions (K-map, Boolean algebra)
16. Draw the logic diagram

3.2 Logic Gate Propagation Delay

PYQ: Explain the concept of logic gate propagation delay. M-25 | 7 marks

Propagation delay (t_p) is the time elapsed between the application of an input signal and the
appearance of the corresponding output signal. It is a fundamental limitation of real logic gates.

Types of Propagation Delay:

• t_PHL: Propagation delay for output changing from High to Low
• t_PLH: Propagation delay for output changing from Low to High
• t_p = (t_PHL + t_PLH) / 2 (average propagation delay)

Causes of Propagation Delay:

17. Capacitance of transistors and interconnects must charge/discharge
18. Finite switching speed of transistors
19. Internal resistance of logic gates
Critical Path:
The critical path is the longest delay path through a combinational circuit. The maximum operating
frequency of a circuit is determined by its critical path:
f_max = 1 / (t_critical_path + t_setup + t_clock_skew)

Impact on Circuit Design:

• Series gates increase total delay (ripple carry adder has n gate delays for n bits)
• Parallel/look-ahead structures reduce delay (carry look-ahead adder)
• Fan-out (number of gate inputs driven by one output) increases delay
• Technology choice (TTL, CMOS, ECL) determines base gate delays

3.3 Half Adder

Adds two single-bit binary numbers A and B to produce Sum (S) and Carry (C).
A B Sum (S) Carry (C)
0 0 0 0
0 1 1 0
1 0 1 0
1 1 0 1
S = A XOR B = A'B + AB'
C = A AND B = AB
Implementation: 1 XOR gate + 1 AND gate.

3.4 Full Adder

Adds three 1-bit numbers: A, B, and Carry-in (Cin), producing Sum and Carry-out.
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
Sum = A XOR B XOR Cin
Cout = AB + Cin(A XOR B) = AB + BCin + ACin
A full adder can be built from two half adders and one OR gate.
3.5 Half Subtractor
Subtracts B from A producing Difference (D) and Borrow (Bout).
A B Difference (D) Borrow (Bout)
0 0 0 0
0 1 1 1
1 0 1 0
1 1 0 0
D = A XOR B
Bout = A'B

3.6 Full Subtractor

PYQ: Design a logic circuit for half and full subtraction circuits with K-map M-24 | 6 marks
equations and truth table.

Subtracts B and Borrow-in (Bin) from A, producing Difference and Borrow-out.

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
Diff = A XOR B XOR Bin
Bout = A'B + A'Bin + BBin = A'B + Bin(A XOR B)'

K-Map for Full Subtractor Borrow (Bout):

Using 3-variable K-map for Bout (A, B, Bin):
Karnaugh Map (AB vs Bin):
Bin=0 Bin=1
AB=00: 0 1
AB=01: 1 1
AB=11: 0 1
AB=10: 0 0

Groups: A'B (minterms 2,3) + A'Bin (minterms 1,3) + BBin (minterms 3,7)
Minimal: Bout = A'B + A'Bin + BBin
3.7 2's Complement Circuit Design
PYQ: Design a combinational circuit whose input is a 4-bit number and M-23 | 6 marks
whose output is the 2's complement of the input number.

Method: 2's complement = 1's complement + 1. An alternative: copy bits from LSB up to and including
the first 1, then complement all remaining bits.

Truth Table (4-bit):

Input (B3B2B1B0) Output (A3A2A1A0) Decimal
0000 0000 0
0001 1111 -1
0010 1110 -2
0011 1101 -3
0100 1100 -4
0101 1011 -5
0110 1010 -6
0111 1001 -7
1000 1000 -8
1001 0111 7
1010 0110 6
1011 0101 5
1100 0100 4
1101 0011 3
1110 0010 2
1111 0001 1

Design Using Cascaded Half Adder + Inverters:

1. Complement all input bits (A3'A2'A1'A0').
2. Add 1 using a ripple carry adder chain (half adders):
Stage 0: HA(A0', 1) -> S0, C0
Stage 1: HA(A1', C0) -> S1, C1
Stage 2: HA(A2', C1) -> S2, C2
Stage 3: HA(A3', C2) -> S3, C3
S3S2S1S0 = 2's complement of B3B2B1B0
3.8 Multiplexer (MUX)
PYQ: Compare the functionality of multiplexers and demultiplexers. M-25 | 7 marks

A multiplexer is a data selector that routes one of 2^n input lines to a single output based on n selection
lines.

2:1 MUX (1 select line):

Y = S'I0 + SI1

4:1 MUX (2 select lines):

Y = S1'S0'I0 + S1'S0 I1 + S1 S0'I2 + S1 S0 I3

3.9 Demultiplexer (DEMUX)

A demultiplexer does the opposite: routes a single input to one of 2^n outputs based on n selection
lines. Also called a data distributor.

1:4 DEMUX (2 select lines):

Y0 = I.S1'.S0'
Y1 = I.S1'.S0
Y2 = I.S1 .S0'
Y3 = I.S1 .S0

MUX vs DEMUX Comparison:

Feature Multiplexer (MUX) Demultiplexer (DEMUX)
Function Many inputs → 1 output 1 input → Many outputs
Also called Data Selector Data Distributor
Select lines Select which input to pass Select which output to route to
Example 4:1 MUX, 8:1 MUX 1:4 DEMUX, 1:8 DEMUX
Use case Sharing a single communication line Routing data to specific destination
Implementation AND-OR network AND network with enable
UNIT 4: SOP, POS, Minterms, Maxterms, K-Map
Simplification & Don't Care
Reference: Mano DLCD Chapter 3 | R.P. Jain Chapter 5

4.1 Canonical Forms Review

Minterm (Standard SOP):
A minterm for n variables is a product term where each variable appears exactly once (complemented
or uncomplemented). There are 2^n minterms for n variables.

Maxterm (Standard POS):

A maxterm for n variables is a sum term where each variable appears exactly once. The relationship
between minterms and maxterms: Mj = mj' (they are complements of each other).

4.2 Karnaugh Map (K-Map) Method

The K-map is a graphical method for simplifying Boolean functions. Cells in adjacent positions differ by
exactly one variable (Gray code ordering). Adjacent 1s can be grouped to eliminate variables.

K-Map Grouping Rules:

20. Groups must contain 1, 2, 4, 8, 16... (powers of 2) cells
21. Cells in a group must all be 1 (or don't care for simplification)
22. Each group should be as large as possible
23. All 1s must be covered by at least one group
24. Groups can overlap
25. K-map wraps around (toroidal topology) — edges are adjacent

4-Variable K-Map Layout:

CD
AB | 00 | 01 | 11 | 10 |
----+----+----+----+----|
00 | m0 | m1 | m3 | m2 |
01 | m4 | m5 | m7 | m6 |
11 | m12| m13| m15| m14|
10 | m8 | m9 | m11| m10|
4.3 Don't Care Conditions
Don't care conditions (d or X) are input combinations that either cannot occur (invalid states) or whose
output value doesn't matter. They can be treated as 0 or 1, whichever gives better simplification.
⚠ Note: Don't care terms can be included in groups to make them larger (better simplification) but
never need to be covered on their own — they are optional.

4.4 K-Map Solved Example (PYQ M-23)

PYQ: Minimize F(A,B,C,D) = π(0,3,4,7,8,10,12,14) + d(2,6) using K-map. M-23 | 8 marks

This is a POS (Product of Sums) expression. π indicates maxterms.

Maxterms at: 0,3,4,7,8,10,12,14 Don't Cares at: 2,6
To minimize POS, we work with the 0s (maxterm positions) on the K-map:

Step 1: Mark 0s and Xs on K-map:

CD
AB | 00 | 01 | 11 | 10 |
----+----+----+----+----|
00 | 0 | 1 | 0 | X | <- 0,1,3,2 (pos 2 is X)
01 | 0 | 1 | 0 | X | <- 4,5,7,6 (pos 6 is X)
11 | 0 | 1 | 1 | 0 | <- 12,13,15,14
10 | 0 | 1 | 1 | 0 | <- 8,9,11,10

Step 2: Group the 0s (and X as needed):

Group 1: Minterms 0,2,4,6 (column CD=00, rows AB=00,01) + DC positions: {0,4,2,6}
These form: C'D' ... but 2 and 6 are X (don't care). Group {0,4} with X{2,6}: eliminates B,C → A'D'
Group 2: Minterms {0,8,2,10} — C'D' ... A? column, D=0. Gives C'D' (eliminates A,B)
Group 3: Minterms {8,10,12,14} — B' ... A=1, D varies. Gives AD'
Group 4: Minterms {0,4,12,8} — D=0 column. Gives D'... check: 0,4,12,8 all have D=0 → eliminates
A,B,C? No. They span all A,B: 00,01,11,10 → eliminate A and B → C'D'. But C=0 for all of them too →
Gives C'D'.

POS Simplification Result:

Each group of 0s gives one sum term (maxterm group)
Group {0,4,8,12} (D=0, C=0): Sum term = (C+D)
Group {0,2,4,6} (A=0, D=0): Sum term = (A+D)
Group {3,7} (A=0,B=0... wait, 3=0011, 7=0111): Sum term check

Final minimal POS (typical result for this function):

F = (C+D)(A+D)(B'+C')(...) -- verify using complement method
⚠ Note: For POS minimization: (1) Fill K-map with 1s for minterms and 0s for maxterms and Xs for
don't-cares. (2) Group the 0s. (3) Each group of 0s generates a SUM term. (4) Take product of all
sum terms.
UNIT 5: Sequential Logic – Latches, Flip-Flops (SR, JK, D,
T)
Reference: Mano DLCD Chapter 6 | R.P. Jain Chapter 10

5.1 Latches
PYQ: Define term latch. M-25 | 2 marks

A latch is a bistable multivibrator — a sequential circuit element that can store one bit of information.
Unlike flip-flops, latches are LEVEL-TRIGGERED: their output changes in response to the input
whenever the enable/clock signal is at the active level (not just on edge transitions).

SR Latch (NOR-based):
S R Q (next) Q' (next) State
0 0 Q Q' No change (memory)
0 1 0 1 Reset
1 0 1 0 Set
1 1 ? ? Forbidden (both outputs = 0)
Built from 2 cross-coupled NOR gates:
Q = (R + Q')'
Q' = (S + Q)'

SR Latch (NAND-based) — active-low inputs:

S' R' Q (next) State
1 1 Q No change
1 0 0 Reset
0 1 1 Set
0 0 ? Forbidden

5.2 Latch vs Flip-Flop

PYQ: Write the differences between latch and flip-flop. M-23 | 2 marks

Feature Latch Flip-Flop

 Triggering Level-triggered (asynchronous) Edge-triggered (synchronous)
When it changes Whenever clock/enable is active Only at clock edge (rising or
falling)
Sensitivity Sensitive to input noise during Immune to input glitches between
active level edges
Speed Faster Slightly slower due to edge
detection
Complexity Simpler circuit More complex (uses latches
internally)
Use case Building blocks for flip-flops Registers, counters, state
machines
Examples SR Latch, D Latch JK FF, D FF, T FF, SR FF

5.3 SR Flip-Flop (Clocked)

A clocked SR flip-flop only changes state on the active clock edge. The S=R=1 condition is still
forbidden.
S R Q(next) Comment
0 0 Q No change
0 1 0 Reset
1 0 1 Set
1 1 ? Forbidden/Undefined

5.4 JK Flip-Flop
The JK flip-flop eliminates the undefined state of the SR flip-flop. When J=K=1, the output TOGGLES
(complements).
J K Q(next) Operation
0 0 Q No change
0 1 0 Reset
1 0 1 Set
1 1 Q' Toggle (complement)
Q(next) = JQ' + K'Q

5.5 Race-Around Condition in JK Flip-Flop

PYQ: Explain race-around condition in JK flip-flops. Draw clocked Master- M-24 | 8 marks
Slave JK flip-flop and explain how it removes the condition.
What is Race-Around Condition?
Race-around condition occurs in a level-triggered JK flip-flop when J=K=1 and the clock is HIGH. Since
the output should toggle, the flip-flop changes state. But because the outputs (Q, Q') are fed back to the
inputs (J, K inputs are connected via feedback), the flip-flop can toggle MULTIPLE TIMES during a
single clock HIGH period, depending on the propagation delay of the gates.

This happens because:

26. At t=0: Q=0, Q'=1, J=K=1, Clock HIGH → Q should go to 1 (toggle)
27. At t=tp: Q=1, Q'=0 — now it toggles again (back to 0)
28. At t=2tp: Q=0, Q'=1 — toggles again...
29. This continues indefinitely while clock is HIGH — unstable/unpredictable output

⚠ Note: The race-around condition is specifically a problem when: (1) J=K=1, (2) Clock is HIGH
(level-triggered), (3) Gate propagation delay < clock pulse width. If clock pulse width < propagation
delay, only one toggle occurs.

Solution 1: Narrow Clock Pulse Width

Make the clock pulse width shorter than the propagation delay of the flip-flop. Impractical in general
systems as it restricts clock period.

Solution 2: Master-Slave JK Flip-Flop (Primary Solution)

The Master-Slave JK flip-flop uses two SR latches connected in series with complementary clock
signals to ISOLATE input sampling from output updating.

Master-Slave Configuration:
Master Latch Slave Latch
J ---[AND]---| |----[AND]---| |---Q
| | SR Latch | | | SR Latch |
K ---[AND]---| |----[AND]---| |---Q'
CLK -----+ CLK=1 +------[NOT]-+ CLK=0 +
(active on CLK HIGH) (active on CLK LOW)

How It Works:
30. When CLOCK = 1 (HIGH): Master latch is ENABLED (accepts J, K inputs). Slave latch is
DISABLED (locked; does not change Q).
31. When CLOCK = 0 (LOW): Master latch is DISABLED (locks its state). Slave latch is ENABLED
(transfers master's state to output Q).
32. Q and Q' feedback comes from the SLAVE output, but the slave is DISABLED when master is
reading inputs → no feedback path is active during input sampling → race-around eliminated.
Timing Diagram Summary:
CLK: _____|‾‾‾‾‾|_____|‾‾‾‾‾|_____
Master: LOCKED|ACTIVE|LOCKED|ACTIVE|LOCKED <- samples J,K
Slave: ACTIVE|LOCKED|ACTIVE|LOCKED|ACTIVE <- updates Q
Q: stable |locked| changes at CLK fall edge

5.6 D Flip-Flop
D (Data) flip-flop has a single data input. The output follows the input on the clock edge. Eliminates the
undefined state.
D Q(next) Operation
0 0 Reset
1 1 Set
Q(next) = D
Implementation: SR flip-flop with D connected to S and D' connected to R.

5.7 T Flip-Flop (Toggle)

T (Toggle) flip-flop toggles its state when T=1, holds when T=0.
T Q(next) Operation
0 Q No change
1 Q' Toggle
Q(next) = T XOR Q = TQ' + T'Q
Implementation: JK flip-flop with J=K=T.
UNIT 6: Sequential Logic – Shift Registers & Counters
Reference: Mano DLCD Chapter 6 | R.P. Jain Chapter 11 | Murdocca Chapter 3

6.1 Shift Registers

A shift register is a cascade of flip-flops sharing the same clock, where the output of each flip-flop is
connected to the input of the next. Data moves (shifts) one position per clock pulse.

Types of Shift Registers:

Type Input Output Use
SISO Serial Serial Data delay line
SIPO Serial Parallel Serial to parallel conversion
PISO Parallel Serial Parallel to serial conversion
PIPO Parallel Parallel Data buffering, storage

6.2 Ring Counter

A ring counter is a shift register with the last flip-flop's output connected back to the first flip-flop's input
(circular connection). It circulates a single 1 (or 0) around the register.
State sequence (4-bit ring counter, initially 1000):
1000 → 0100 → 0010 → 0001 → 1000 → ...
Properties:
• n flip-flops = n distinct states (not 2^n — inefficient use of flip-flops)
• Self-decoding: each state directly represents a count position
• No additional decoding logic needed

6.3 Johnson Counter (Twisted Ring Counter)

In a Johnson counter, the COMPLEMENT of the last flip-flop's output is fed back to the first. This
doubles the number of states compared to a ring counter.
State sequence (4-bit Johnson counter, initially 0000):
0000 → 1000 → 1100 → 1110 → 1111 → 0111 → 0011 → 0001 → 0000 → ...
(8 states for 4 flip-flops = 2n states)

Johnson vs Ring Counter:

Feature Ring Counter Johnson Counter
States for n FFs n states 2n states
 Feedback Q (direct) Q' (complemented)
Decoding No extra logic needed Simple 2-input AND gates
Self-starting Usually not Usually not
Initial state Requires preset Requires preset

6.4 Counters – Synchronous vs Asynchronous

Feature Synchronous (Parallel) Asynchronous (Ripple)
Clock All FFs clocked simultaneously Each FF clocked by previous FF's
output
Speed Faster (no cumulative delay) Slower (ripple delay = n × t_FF)
Complexity More complex (logic for each FF) Simpler circuit
Glitches Minimal More prone to glitches
Max freq Higher Lower (limited by ripple delay)
Power Higher Lower

6.5 Mod-6 Asynchronous Counter (PYQ M-24)

PYQ: Design a mod-6 asynchronous counter using JK flip-flops. M-24 | 8 marks

A mod-6 counter counts from 0 to 5 and then resets (6 states: 000 to 101).

State Sequence:
000 → 001 → 010 → 011 → 100 → 101 → (110 detected → reset) → 000

Design Steps:
33. Use 3 JK flip-flops (Q2, Q1, Q0) in toggle mode (J=K=1 for ripple).
34. Detect state 110 (6 in binary) using a NAND gate: NAND(Q2, Q1).
35. Connect NAND output to CLR (Clear) inputs of all flip-flops.
36. When count reaches 110, NAND output = 0 (active low), which resets all FFs to 000
immediately.

Circuit Description:
FF0 (Q0): CLK = external clock; J=K=1 (always toggles)
FF1 (Q1): CLK = Q0 output (triggers on Q0 falling edge)
FF2 (Q2): CLK = Q1 output (triggers on Q1 falling edge)
Reset: NAND(Q2, Q1) → CLR of all 3 FFs (active low clear)
Count Table:
Clock Pulse Q2 Q1 Q0 Decimal
Initial 0 0 0 0
1 0 0 1 1
2 0 1 0 2
3 0 1 1 3
4 1 0 0 4
5 1 0 1 5
6 (reset) 1 1 0 6→reset to 0

6.6 Custom Sequence Counter (PYQ M-23)

PYQ: Design a counter for sequence: 0, 4, 5, 3, 1, 6, 2, 7 and repeat. Use JK M-23 | 8 marks
flip-flops.

State Assignment:
We need 3 flip-flops (Q2, Q1, Q0) for 8 states (0-7). The sequence is:
000 → 100 → 101 → 011 → 001 → 110 → 010 → 111 → 000 (repeat)

State Transition Table:

Present Q2Q1Q0 Next Q2Q1Q0 J2K2 J1K1 J0K0
000 (0) 100 (4) 1X 0X 0X
100 (4) 101 (5) X0 0X 1X
101 (5) 011 (3) X1 1X X0
011 (3) 001 (1) 0X X1 X1
001 (1) 110 (6) 1X 1X X1
110 (6) 010 (2) X1 X0 0X
010 (2) 111 (7) 1X X1 1X
111 (7) 000 (0) X1 X1 X1

JK Flip-Flop Excitation:
For each flip-flop, use K-maps to minimize J and K expressions:
From the excitation table, derive minimal SOP for J2, K2, J1, K1, J0, K0
using 3-variable K-maps (Q2, Q1, Q0 as variables).

JK FF excitation: Q: 0→0: J=0,K=X | 0→1: J=1,K=X | 1→0: J=X,K=1 | 1→1: J=X,K=0

⚠ Note: Full K-map working for each J and K expression should be drawn in the exam. The key steps
are: (1) Create state transition table, (2) Fill JK excitation using the JK truth table, (3) Draw K-maps
for each of the 6 variables (J2,K2,J1,K1,J0,K0), (4) Read minimized SOP expressions, (5) Implement
the circuit.
APPENDIX: Quick Revision Cheat Sheet

Boolean Algebra Quick Reference

Law Expression
Identity A+0=A, A·1=A
Null A+1=1, A·0=0
Idempotent A+A=A, A·A=A
Complement A+A'=1, A·A'=0
Involution (A')'=A
De Morgan 1 (A+B)' = A'·B'
De Morgan 2 (A·B)' = A'+B'
Absorption A+AB=A, A(A+B)=A
Consensus AB+A'C+BC = AB+A'C

Flip-Flop Excitation Table (MOST IMPORTANT)

Q→Q(next) SR: S K JK: J K D T
0→0 0X 0X 0 0
0→1 10 1X 1 1
1→0 01 X1 0 1
1→1 X0 X0 1 0

Counter Design Summary

Counter Type States Key Feature
Ring (n FFs) n Circulates 1; self-decoding
Johnson (n FFs) 2n Complemented feedback; 2n states
Mod-N Async N NAND gate detects Nth state; resets
Mod-N Sync N K-map derived JK excitation; all FFs share clock
Custom Sequence N State table → JK excitation → K-map → circuit
PYQ Marks Distribution at a Glance
Topic M-23 M-24 M-25 Total Marks
Boolean Algebra & De Morgan — 4 14 18
Number Representation 8 6 2 16
Combinational Logic 6 6 14 26
K-Map / SOP / POS 8 2 — 10
Latches & Flip-Flops 2 8 2 12
Counters & Shift Registers 8+8 8 — 24

End of Notes — Best of Luck in Your Exam!