GATE CS - DIGITAL LOGIC:K-maps, Flip-Flops and Sequential Circuits — GATE Deep Dive

K-maps, Flip-Flops and Sequential Circuits

Karnaugh Maps (K-maps) — The GATE Staple

K-maps provide a systematic method to minimize Boolean functions. GATE regularly asks for SOP (Sum of Products) or POS (Product of Sums) minimization.

2-Variable K-map

        B=0   B=1
A=0  |  m₀  |  m₁  |
A=1  |  m₂  |  m₃  |

Adjacency: m₀-m₁, m₂-m₃ (horizontal); m₀-m₂, m₁-m₃ (vertical)

3-Variable K-map (Gray code ordering)

        BC=00  BC=01  BC=11  BC=10
A=0  |   m₀  |  m₁  |  m₃  |  m₂  |
A=1  |   m₄  |  m₅  |  m₇  |  m₆  |

Note: Columns follow Gray code (00→01→11→10), NOT binary order!

4-Variable K-map (most common in GATE)

          CD=00  CD=01  CD=11  CD=10
AB=00  |   0   |   1   |   3   |   2   |
AB=01  |   4   |   5   |   7   |   6   |
AB=11  |  12   |  13   |  15   |  14   |
AB=10  |   8   |   9   |  11   |  10   |

K-map wrapping: Corners and edges wrap around — the K-map is logically toroidal.

• Cells 0,2,8,10 form a valid group (corners of the 4×4 map)
• Cells 0,4,12,8 form a valid column group

Grouping Rules

• Groups must contain 1, 2, 4, 8, or 16 cells (powers of 2)
• Groups must be rectangular
• Each cell with 1 must be covered by at least one group
• Larger groups → fewer literals in the term
• Use don't cares (X) to form larger groups when beneficial

Example: F(A,B,C,D) = Σm(0,1,2,3,4,5,6,7,12,13)

          CD=00  CD=01  CD=11  CD=10
AB=00  |   1   |   1   |   1   |   1   |
AB=01  |   1   |   1   |   1   |   1   |
AB=11  |   1   |   1   |   0   |   0   |
AB=10  |   0   |   0   |   0   |   0   |

Groups:
- {0,1,2,3,4,5,6,7}: AB=0X → A'  (all top two rows)
- {0,4,12,8}: ... wait, 8=0 and 12=1, so check the map values
- Best grouping: {0-7} (A=0, any BCD) → term: A'
                {12,13} (AB=11, CD=0X) → term: ABC'D' ... 

Simplified: F = A' + A·B·C'  = A' + BC'  (after verification)

GATE tip: Always check K-map wrapping. Many marks are lost by missing wrapped groups.

Flip-Flops — Complete Reference

SR Flip-Flop

Excitation table (given current Q, desired Q+):

JK Flip-Flop

No forbidden state — the JK is the most general flip-flop.

Characteristic equation: Qₙ₊₁ = JQ̄ₙ + K̄Qₙ

D Flip-Flop

Characteristic equation: Qₙ₊₁ = D

Excitation: D = Qₙ₊₁ (whatever you want next, that's your input)

T Flip-Flop

Characteristic equation: Qₙ₊₁ = T ⊕ Qₙ

Excitation: T = Qₙ ⊕ Qₙ₊₁

Flip-Flop Conversions (GATE High Frequency)

Method: Use excitation table of the target flip-flop, then derive input equations using K-maps.

Example: JK → D conversion

To implement D flip-flop using JK:

Using K-map: J = D, K = D̄

Verify: With J=D, K=D̄:

• D=0: J=0, K=1 → Qₙ₊₁=0 ✓
• D=1: J=1, K=0 → Qₙ₊₁=1 ✓

Example: D → JK conversion

To implement JK flip-flop using D:

D (the input to D FF) = Qₙ₊₁ = JQ̄ₙ + K̄Qₙ

K-map minimization gives: D = JQ̄ + K̄Q (same as JK characteristic equation)

Counters

3-bit Synchronous Up Counter

All FFs triggered by same clock. Uses T FFs for simplicity.

T₀ = 1 (always toggles)

T₁ = Q₀ (toggles when Q₀=1)

T₂ = Q₁Q₀ (toggles when both Q₁=1 and Q₀=1)

GATE fact: Mod-n counter requires ⌈log₂n⌉ flip-flops. Maximum mod = 2^n.

Moore vs Mealy Machines

GATE question type: Convert between Moore and Mealy machines.

Conversion rule (Mealy → Moore): For each (state, output) pair in the Mealy machine, create a separate Moore state.

Practice Problems

1. Minimize F(A,B,C,D) = Σm(1,3,7,11,15) + d(0,2,5) using K-map
2. Design a 3-bit synchronous down counter using JK flip-flops
3. Convert SR to JK flip-flop (find input equations)
4. A Moore machine with 4 states produces output 1 when 3 consecutive 1s are detected. Draw the state diagram.
5. Identify the K-map group for minterms {0,2,8,10} in a 4-variable map