Digital Circuits: Boolean Algebra, Multiplexers, Encoders and Decoders, Flip-Flops and Counters
1. Boolean algebra and minimisation
- Identities: A + 0 = A, A · 1 = A, A + A = A, A + A′ = 1, A · A′ = 0, A + 1 = 1.
- Absorption: A + AB = A and A(A + B) = A; also A + A′B = A + B.
- De Morgan: (A + B)′ = A′B′ and (AB)′ = A′ + B′ — the reason NAND and NOR are each universal: either alone builds NOT, AND and OR.
- Consensus: AB + A′C + BC = AB + A′C — the BC term is redundant because it is covered whichever value A takes.
A function is written as a sum of minterms (SOP) or a product of maxterms (POS). A Karnaugh map arranges the minterms in Gray-code order so that adjacent cells differ in one variable; grouping 1s in rectangles of 1, 2, 4 or 8 cells, wrapping round the edges, removes the variables that change within the group. Don’t-care cells may be counted as 1 when they enlarge a group. For F(A, B, C, D) = Σm(0, 2, 5, 7, 8, 10, 13, 15): the four corners (0, 2, 8, 10) form B′D′ and the centre block (5, 7, 13, 15) forms BD, so F = B′D′ + BD, the XNOR of B and D.
2. Multiplexers, encoders and decoders
A multiplexer routes one of 2ⁿ data inputs to its output under n select lines: a 32-to-1 MUX needs 5. It is also a universal function generator — a 2ⁿ-to-1 MUX implements any function of n variables by tying its data inputs to 0 or 1, and any function of n + 1 variables if the extra variable (or its complement) is allowed on the data inputs. A decoder has n inputs and 2ⁿ outputs, exactly one active: a 3-to-8 decoder with ABC = 101 (A the most significant) activates output 5. Because each output is one minterm, a decoder with an OR gate implements any function.
An encoder is the reverse: 2ⁿ inputs, one active, to an n-bit code. A plain encoder gives nonsense when two inputs are active at once, so the practical form is the priority encoder, which reports the highest-numbered active input and a valid flag: with D₁ and D₂ both high on a 4-to-2 priority encoder, the output is 10, for D₂. Half and full adders, comparators and code converters are the other combinational blocks; a combinational circuit has no memory, its output a function of the present inputs alone.
3. Latches and flip-flops
A latch is level-sensitive: it follows its input while enabled. A flip-flop is edge-triggered: it samples at a clock edge and holds between edges, which is what makes synchronous design possible. The four types are defined by their characteristic equations.
| Type | Next state Q⁺ | Remark |
|---|---|---|
| SR | S + R′Q, with SR = 0 | S = R = 1 is not allowed. |
| JK | JQ′ + K′Q | J = K = 1 toggles. |
| D | D | Delay: the output copies D at the edge. |
| T | T ⊕ Q | T = 1 toggles, T = 0 holds. |
4. Counters
A counter of modulus N needs n flip-flops with 2ⁿ ≥ N: mod-10 (a decade counter) needs 4. In an asynchronous (ripple) counter each flip-flop is clocked by the previous one’s output, so the delays add: with n stages of delay t_pd, the output settles n·t_pd after the clock, and the maximum clock frequency is 1/(n·t_pd) — 10 MHz for four stages of 25 ns. Each stage halves the frequency, so an n-bit ripple counter divides by 2ⁿ: a 1 kHz clock gives 125 Hz at the third stage. A synchronous counter clocks every flip-flop together and uses gating to decide which toggle, so its speed is set by one flip-flop delay plus the gate delay, independent of length.
Shift-register counters trade flip-flops for simple decoding: an n-stage ring counter circulates a single 1 and has n states; a Johnson (twisted-ring) counter feeds back the complement of the last stage and has 2n states — 8 for four flip-flops. A mod-N counter from a binary counter is made by detecting state N and resetting, and up/down counters reverse the gating.
Key takeaways
- De Morgan makes NAND and NOR universal; the consensus term BC in AB + A′C + BC is redundant.
- K-map groups of 1, 2, 4, 8 wrap round the edges; the four corners of a 4-variable map are one group.
- A 2ⁿ-to-1 MUX has n select lines; a decoder output is a minterm; a priority encoder reports the highest active input.
- JK: Q⁺ = JQ′ + K′Q, toggling at J = K = 1; T: Q⁺ = T ⊕ Q; D: Q⁺ = D; master–slave removes race-around.
- Mod-N needs 2ⁿ ≥ N; a ripple counter runs at most 1/(n t_pd) and divides by 2ⁿ; ring has n states, Johnson 2n.
Practice questions (13)
Attempt each one before opening the answer. Every explanation names the tempting wrong option as well as the right one, because that is where marks are lost.
By De Morgan’s theorem, (A + B)′ equals:
Show answer
Answer: A — A′B′
The complement of a sum is the product of the complements: A + B is 0 only when both are 0, so (A + B)′ is 1 only when A′ and B′ are both 1. A′ + B′ is the complement of AB, the other half of the theorem.The expression AB + A′C + BC simplifies to:
Show answer
Answer: A — AB + A′C
BC = BC(A + A′) = ABC + A′BC, and ABC is absorbed by AB while A′BC is absorbed by A′C, so BC adds nothing: the consensus theorem. B + C is wrong at A = 1, B = 0, C = 1, where the original is 0.The number of select lines required by a 32-to-1 multiplexer is ____.
Numerical answer — type the value.
Show answer
Answer: 5
n select lines address 2ⁿ inputs, and 2⁵ = 32. The number of data inputs, 32, is not the number of select lines.The minimal sum-of-products form of F(A, B, C, D) = Σm(0, 2, 5, 7, 8, 10, 13, 15) is:
Show answer
Answer: A — B′D′ + BD
Minterms 0, 2, 8, 10 all have B = 0, D = 0 — the four corners of the map — giving B′D′; minterms 5, 7, 13, 15 all have B = 1, D = 1, giving BD. A and C take both values in each group and drop out. B′D + BD′ is the XOR, the complement of the answer.A 3-to-8 decoder with active-high outputs Y₀ to Y₇ receives inputs A = 1, B = 0, C = 1, with A the most significant bit. The output that goes high is Y____.
Numerical answer — type the value.
Show answer
Answer: 5
ABC = 101₂ = 4 + 0 + 1 = 5, so Y₅ is the one active output. Reading C as the most significant bit gives 101 again here, but 110 would then map to 3 instead of 6.A 4-to-2 priority encoder gives priority to the highest-numbered input. With D₁ = 1, D₂ = 1 and D₀ = D₃ = 0, its output Y₁Y₀ is:
Show answer
Answer: A — 10
D₂ outranks D₁, so the code for 2, binary 10, is output. A plain encoder would OR the codes 01 and 10 and give 11, which names D₃, an input that is not active — the failure priority encoding exists to prevent.An edge-triggered JK flip-flop with J = 1 and K = 1 receives a clock edge. Its output:
Show answer
Answer: A — toggles
Q⁺ = JQ′ + K′Q = Q′ + 0 = Q′: the state inverts. The indeterminate case belongs to the SR flip-flop with S = R = 1, which the JK design was made to replace.Which characteristic equations are correct?
Show answer
Answer: A — D flip-flop: Q⁺ = D; B — T flip-flop: Q⁺ = T ⊕ Q; C — JK flip-flop: Q⁺ = JQ′ + K′Q
(A)–(C) are the defining equations. (D) False: S = R = 1 is the forbidden input of the SR flip-flop — both outputs are driven to the same value and the state after it is released is unpredictable. The hold input is S = R = 0.The minimum number of flip-flops needed to build a mod-10 counter is ____.
Numerical answer — type the value.
Show answer
Answer: 4
n flip-flops give 2ⁿ states, and 2³ = 8 < 10 ≤ 16 = 2⁴, so four are needed, with six of the sixteen states unused. Ten would be the count for a ring counter, not a binary one.A 4-bit ripple counter is built from flip-flops each with a propagation delay of 25 ns. Allowing the counter to settle fully before the next clock edge, its maximum clock frequency is ____ MHz.
Numerical answer — type the value.
Show answer
Answer: 10
The worst-case settling time is 4 × 25 = 100 ns, since each stage waits for the one before it, so f_max = 1/100 ns = 10 MHz. Using a single delay gives 40 MHz, which is the synchronous counter’s figure (before gate delays).A Johnson (twisted-ring) counter built from four flip-flops has how many distinct states in its counting sequence?
Show answer
Answer: A — 8
Feeding back the complement of the last stage fills the register with 1s and then with 0s: 0000, 1000, 1100, 1110, 1111, 0111, 0011, 0001 — 2n = 8 states. A ring counter has n = 4; a binary counter 2ⁿ = 16.Which statements are true?
Show answer
Answer: A — NAND gates alone can implement any Boolean function; B — A 4-to-1 multiplexer can implement any function of three variables if one variable or its complement may be applied to the data inputs; D — A master–slave JK flip-flop avoids the race-around condition
(A) NAND builds NOT (tied inputs), AND (NAND then NOT) and OR (by De Morgan). (B) Two variables drive the select lines and each data input is 0, 1, C or C′. (C) False: that is a synchronous counter; in a ripple counter each stage clocks the next. (D) The master and slave are enabled on opposite clock levels, so the output changes once per cycle.A 1 kHz square wave clocks a 3-bit ripple counter. The frequency of the output of the most significant flip-flop is ____ Hz.
Numerical answer — type the value.
Show answer
Answer: 125
Each toggling stage halves the frequency: 1000 → 500 → 250 → 125 Hz at the third stage, a division by 2³ = 8. Dividing by 3 confuses the number of stages with the division ratio.