Digital Logic Problem Vault
The last volume turns the course into revision. It gathers every rule and formula onto one sheet, works through 24 practice problems in the GATE style - written for this course, with every answer checked by its simulator - and answers the interview and viva questions that digital logic always brings.
- Every rule, formula and key number of the course, on one sheet
- How to solve GATE-style problems on numbers, K-maps, building blocks, adders, counters and memory
- Model answers to the interview and viva questions that come up most
- The rest of this course. Each problem names the volume that teaches its idea.
10.1 Formula and fact sheet
The whole course fits on one sheet: a handful of number rules, the gates and their algebra, the building blocks, and the timing of flip-flops. Know these by heart, and every exam question becomes a matter of applying them carefully.
The ideas, volume by volume
| Volume | The idea to keep |
|---|---|
| 00 | Digital means reading a voltage as 0 or 1 against thresholds, so small noise changes nothing |
| 01 | Binary places are powers of 2; hex is 4 bits per digit; two's complement makes the top place negative |
| 02 | Seven gates; NAND and NOR alone can build everything; gates take time |
| 03 | Boolean rules, De Morgan, sum of products and product of sums, minterms and maxterms |
| 04 | K-maps find the smallest sum of products; don't cares help; a bridging term removes a hazard |
| 05 | Multiplexers and decoders can build any function; priority encoders pick the highest input |
| 06 | Full adders chain into a ripple adder; subtraction adds the two's complement; V = C(n-1) ⊕ C(n) |
| 07 | Memory needs feedback; latches are level sensitive, flip-flops edge-triggered; setup and hold |
| 08 | Registers, shift registers, ripple and synchronous counters; check unused states for lock-up |
| 09 | Memory organisation, DACs and ADCs, noise margins and fan-out |
Formulas
| Topic | Formula |
|---|---|
| Patterns from n bits | 2 to the power n; unsigned values 0 to 2 to the power n, minus 1 |
| Two's complement range | -2 to the power n-1 up to 2 to the power n-1, minus 1 |
| Negating in two's complement | invert every bit, then add 1 |
| Gray code | G = B XOR (B shifted right one place) |
| De Morgan | (A·B)' = A' + B' and (A + B)' = A'·B' |
| Consensus | A·B + A'·C + B·C = A·B + A'·C |
| Functions of n inputs | 2 to the power 2 to the power n |
| Multiplexer | n select lines choose from 2 to the power n inputs; builds any function of n + 1 inputs |
| Full adder | S = A ⊕ B ⊕ Cin; Cout = A·B + Cin·(A ⊕ B) |
| Carry look-ahead | G = A·B, P = A ⊕ B, C(i+1) = G(i) + P(i)·C(i) |
| Signed overflow | V = C(n-1) ⊕ C(n): same-sign inputs gave a result of the other sign |
| JK flip-flop | Q next = J·Q' + K'·Q |
| T flip-flop | Q next = T ⊕ Q |
| Johnson counter | 2n states from n flip-flops; a ring counter has n |
| Memory | 2 to the power k words need k address lines |
| Chips for a bigger memory | (words needed / words per chip) x (width needed / chip width) |
| DAC | Vout = Vref x D / 2 to the power n; one step = Vref / 2 to the power n |
| Flash ADC | 2 to the power n, minus 1, comparators; successive approximation takes n steps |
| Noise margins | NMH = VOH - VIH; NML = VIL - VOL |
| Fan-out | the smaller of IOL / IIL and IOH / IIH |
| CMOS switching power | P = C x V squared x f |
| Fastest clock | period at least clock-to-Q + logic delay + setup time |
The rules of Boolean algebra
| Rule | AND form | OR form |
|---|---|---|
| Identity | A·1 = A | A + 0 = A |
| Null | A·0 = 0 | A + 1 = 1 |
| Idempotent | A·A = A | A + A = A |
| Complement | A·A' = 0 | A + A' = 1 |
| Double inversion | 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) |
| Absorption | A·(A + B) = A | A + A·B = A |
| Redundancy | A·(A' + B) = A·B | A + A'·B = A + B |
| De Morgan | (A·B)' = A' + B' | (A + B)' = A'·B' |
Every row was checked on every input by the simulator in Volume 03.
How many different Boolean functions of 4 inputs are there?
Show the answer
Answer: B. Four inputs make 24 = 16 rows, and each row can be 0 or 1, so there are 216 = 65536 truth tables.
10.2 GATE-style practice problems
These problems follow the style of GATE Digital Electronics questions. They were written for this course, not taken from any past paper, and every answer was worked out by the course's simulator.
Try each one on paper before opening the solution. The volume that teaches each idea is named, so you can go back when one does not click.
Numbers
1. Hex to decimal and octal
Convert 0x2BC to decimal and to octal.
Show the solution
Hex places are worth 256, 16 and 1 (Volume 01):
0x2BC = 2×256 + 11×16 + 12×1 = 700
0x2BC = 1 010 111 100 in binary = 1274 in octal
For octal, write the bits and regroup them in threes from the right.
2. A negative number in 8 bits
Write -37 as an 8-bit two's complement number.
Show the solution
+37 = 0010 0101; invert: 1101 1010; add 1: 1101 1011
3. The range of 6 bits
What range of values can a 6-bit number hold in two's complement, and in sign-magnitude?
Show the solution
6 bits, two's complement: -32 to 31; sign-magnitude: -31 to 31
Sign-magnitude loses one value because it has two zeros.
4. Gray code both ways
Write 45 in 6-bit binary and in Gray code.
Show the solution
Copy the first bit, then compare neighbouring bits: same gives 0, different gives 1 (Volume 01):
45 = 101101 in binary = 111011 in Gray code; Gray 111011 -> binary 101101
Boolean algebra and K-maps
5. A four-variable map
Find the minimal sum of products for F(A, B, C, D) = Σm(0, 2, 5, 7, 8, 10, 13, 15).
Show the solution
The four corners (0, 2, 8, 10) group as B'·D', and the middle square (5, 7, 13, 15) as B·D:
F = Σm(0, 2, 5, 7, 8, 10, 13, 15): F = B'·D' + B·D (4 literals)
That is B ⊙ D, an XNOR - worth spotting in an exam.
6. Don't cares with two answers
Minimise F(A, B, C, D) = Σm(1, 3, 7, 11, 15) + d(0, 2, 5).
Show the solution
C·D covers 3, 7, 11 and 15. Minterm 1 needs one more group, and two are equally good:
F = Σm(1, 3, 7, 11, 15) + d(0, 2, 5): F = A'·D + C·D (4 literals)
F = Σm(1, 3, 7, 11, 15) + d(0, 2, 5): F = A'·B' + C·D (4 literals)
2 cheapest answers
Either is a full-marks answer.
7. Counting prime implicants
How many prime implicants does F(A, B, C) = Σm(0, 1, 2, 5, 6, 7) have, and how many of them are essential?
Show the solution
6 prime implicants, 0 essential
Every 1 is covered by two groups of two, so no group is essential - the cyclic map of Volume 04, with two equally good answers of three terms each.
8. A hazard
F = A·B + A'·C has a static-1 hazard. Which term removes it, and does adding it change F?
Show the solution
the cover term is B·C: A·B + A'·C + B·C = A·B + A'·C on every row: True
B·C holds the output at 1 while A changes (Volume 04), and it is the consensus term, so F is unchanged.
9. Self-dual functions
A function is self-dual if it equals its own dual - swap every AND and OR, and every 0 and 1, and you get the same function back. How many of the 256 functions of three inputs are self-dual?
Show the solution
A self-dual function gives opposite outputs on opposite rows (000 and 111, 001 and 110, and so on), so only half the rows are free. Four free rows give 24 functions:
self-dual functions of 3 inputs: 16 of 256
The majority function from Volume 03 is one of them.
Combinational blocks
10. What does this multiplexer compute?
A 4-to-1 multiplexer has S1 = A, S0 = B, and data inputs D0 = C', D1 = 1, D2 = 0 and D3 = C. Find F as a minimal sum of products.
Show the solution
Each pair of rows with the same A and B takes one data input. Collect the rows where F = 1:
F = Σm(0, 2, 3, 7) = A'·C' + B·C
11. A big decoder from small ones
How many 2-to-4 decoders with enable inputs are needed to build a 4-to-16 decoder?
Show the solution
16 outputs / 4 per decoder = 4 decoders, plus 1 to drive their enables = 5
The top two address bits go into the fifth decoder, whose outputs enable one of the other four.
12. A function of five inputs
What is the smallest multiplexer that can build any function of five inputs A to E on its own, with 0, 1, E and E' available as data inputs?
Show the solution
with 4 select lines, a 16-to-1 multiplexer builds any 5-input function (data inputs 0, 1, E, E')
A, B, C and D drive the select lines, and each data input covers two rows that differ only in E.
Arithmetic
13. A 32-bit ripple-carry adder
In a 32-bit ripple-carry adder, each full adder takes 2 ns from carry in to carry out and 3 ns from carry in to sum. All inputs arrive at once. How long until the last sum bit is correct?
Show the solution
The carry ripples through 31 stages before it reaches the last one, then the last stage adds its sum delay:
(n - 1) x carry + sum = 31 x 2 + 3 = 65 ns
14. Overflow in 8 bits
Add 0x7F and 0x01 as 8-bit two's complement numbers. What is the result, and has it overflowed?
Show the solution
0111 1111 + 0000 0001 = 1000 0000 = -128 as signed: overflow, because two positives gave a negative
Sequential circuits
15. Flip-flops for a counter
How many flip-flops do mod-10, mod-12, mod-60 and mod-100 counters need?
Show the solution
The smallest n with 2n at least the count:
a mod-10 counter needs 4 flip-flops (2^4 = 16)
a mod-12 counter needs 4 flip-flops (2^4 = 16)
a mod-60 counter needs 6 flip-flops (2^6 = 64)
a mod-100 counter needs 7 flip-flops (2^7 = 128)
16. A toggling JK flip-flop
A JK flip-flop with J = K = 1 starts at Q = 0. What is Q after 5 clock edges?
Show the solution
J = K = 1 toggles at every edge: 1, 0, 1, 0, 1.
a JK flip-flop with J = K = 1, starting at 0, holds 1 after 5 clock edges
17. Johnson and ring counters
How many states does a 5-bit Johnson counter use, and how many of the 32 possible states are left unused? Compare a 5-bit ring counter.
Show the solution
Johnson: 2 x 5 = 10 states used, 22 of 32 unused
ring: 5 states used, 27 unused
All those unused states are why these counters can lock up (Volume 08).
18. Follow a counter
A 3-bit counter uses JK flip-flops with J2 = Q1, K2 = Q1', J1 = Q0, K1 = Q0', J0 = Q2' and K0 = Q2. Starting from 000, what sequence does it follow?
Show the solution
from 000: 000 -> 001 -> 011 -> 111 -> 110 -> 100 -> 000
It is a 3-bit Johnson counter - and, as Volume 08 found, its unused states 010 and 101 lock up.
19. A counter divides the clock
A 4-bit binary up-counter runs from a 16 MHz clock. At what frequency does each output toggle through a full cycle?
Show the solution
Each output completes a cycle at half the rate of the one before:
Q0 toggles at 1/2 of the clock frequency: 8.0 MHz from a 16 MHz clock
Q1 toggles at 1/4 of the clock frequency: 4.0 MHz from a 16 MHz clock
Q2 toggles at 1/8 of the clock frequency: 2.0 MHz from a 16 MHz clock
Q3 toggles at 1/16 of the clock frequency: 1.0 MHz from a 16 MHz clock
Memory, converters and families
20. A 2K x 8 memory
How many 256 x 4 chips build a 2K x 8 memory, and how are the address lines used?
Show the solution
chips: (2K / 256) x (8 / 4) = 8 x 2 = 16
address lines: 11 in all, 8 to each chip, 3 to a 3-to-8 decoder
21. A DAC's output
An 8-bit DAC has Vref = 10.24 V. What is one step, and what is the output for the input 1010 0000?
Show the solution
one step = 10.24 / 256 = 0.04 V; input 1010 0000 = 160 gives 6.40 V
22. ADC speed and size
How long does a 10-bit successive-approximation ADC take at one bit per clock of 1 MHz? How many comparators would a 10-bit flash ADC need?
Show the solution
a 10-bit SAR ADC at one bit per clock of 1 MHz takes 10 microseconds
a 10-bit flash ADC needs 2^10 - 1 = 1023 comparators
23. Noise margins and fan-out
A logic family has VOH = 3.3 V, VOL = 0.2 V, VIH = 2.0 V and VIL = 0.8 V. Its outputs sink 8 mA and source 0.4 mA; its inputs draw 0.4 mA when low and 20 microamps when high. Find its noise margin and its fan-out.
Show the solution
NMH = 3.3 - 2.0 = 1.3 V; NML = 0.8 - 0.2 = 0.6 V; the family's noise margin is the smaller: 0.6 V
low: 8 / 0.4 = 20; high: 0.4 / 0.02 = 20; fan-out = 20
24. The fastest clock
A path from one flip-flop to the next has clock-to-Q 3 ns, logic delay 12 ns and setup time 2 ns. What is the fastest clock it can run at?
Show the solution
period at least 3 + 12 + 2 = 17 ns; f_max = 1000 / 17 = 58.8 MHz
The course on static timing analysis builds this one sum into a complete method.
A counter must count from 0 to 99 and repeat. What is the fewest flip-flops it can use?
Show the answer
Answer: A. It needs 100 states. Six flip-flops give only 64; seven give 128, which is enough.
10.3 Interview and viva questions
A good interview answer has three parts: the idea, the reason, and one piece of evidence. The model answers below use the numbers this course measured and checked.
What is the difference between combinational and sequential logic?
"What is the difference between combinational and sequential logic?"
Show the solution
"A combinational circuit's outputs depend only on its present inputs - gates, adders, multiplexers. A sequential circuit also depends on what happened before, because it has memory: flip-flops fed back through logic. That memory needs a feedback loop; two NOT gates in a ring already hold a bit."
Why two's complement?
"Why do computers use two's complement for negative numbers?"
Show the solution
"Because one ordinary adder then handles signed and unsigned numbers alike, there is only one zero, and the sign shows in the top bit. 5 + (-5) in 8 bits gives 1 0000 0000, and dropping the carry leaves exactly zero. Sign-magnitude would need extra circuits and has two zeros."
Universal gates
"Why are NAND and NOR called universal, and what does it cost to build other gates from NAND?"
Show the solution
"Each alone can build every other gate. A search of every small network shows the minimum counts: NOT takes 1 NAND, AND takes 2, OR takes 3, XOR takes 4 and XNOR takes 5:
XNOR needs 5 NAND gates: g1 = NAND(A, A); g2 = NAND(A, B); g3 = NAND(B, B); g4 = NAND(g1, g3); g5 = NAND(g2, g4)
In CMOS, NAND is also the natural gate: 4 transistors against 6 for an AND."
What is a K-map for?
"Why use a Karnaugh map instead of Boolean algebra?"
Show the solution
"Algebra can simplify a formula but never proves the result is the smallest. A K-map lays out the truth table in Gray-code order, so neighbouring cells differ in one input. Circling the largest groups of 1s gives the minimal sum of products directly, and don't cares can be used to make the groups bigger. Beyond about five inputs, tools use algorithms like Quine-McCluskey instead."
What is a glitch, and why does it happen?
"What is a glitch, and how can a circuit with a correct truth table glitch?"
Show the solution
"A glitch is a short unwanted pulse. Every gate has a propagation delay, so signals that should change together arrive at different times. In A·A', the NOT gate's output changes a step later than A, so for one step both AND inputs are 1. A static hazard is the same thing in a real function, and adding the consensus term removes it."
Multiplexer as a universal block
"How would you implement a three-input function with a 4-to-1 multiplexer?"
Show the solution
"Put two inputs on the select lines. Each select value picks a pair of truth-table rows that differ only in the third input, and the data input is 0, 1, that input or its inverse. For the majority function, the data inputs are 0, C, C and 1."
Ripple versus look-ahead
"How does a carry look-ahead adder beat a ripple-carry adder?"
Show the solution
"A ripple adder's carry passes through every stage, two gate delays each, so its delay grows with the width. Look-ahead computes every carry directly from generate and propagate signals in two gate levels. In a gate-level simulation of the 4-bit worst case, ripple settled in 8 gate delays and look-ahead in 4."
Latch versus flip-flop
"What is the difference between a latch and a flip-flop?"
Show the solution
"A latch is level sensitive: while enabled it is transparent. A flip-flop is edge-triggered: it samples its input only at the clock edge. A D flip-flop is a master latch and a slave latch opened by opposite clock levels, so there is never a straight path through."
Setup and hold
"What are setup and hold times, and what happens if they are violated?"
Show the solution
"Setup is how long the input must be steady before the clock edge, hold how long after. They come from the gates inside the flip-flop. In a gate-level simulation of a master-slave flip-flop, D had to be steady 3 gate delays before the edge and 1 after. Violate them and the output can be wrong, late or glitchy - and in real silicon, metastable."
Why is a synchronous counter better?
"Why do designs use synchronous counters rather than ripple counters?"
Show the solution
"In a ripple counter each flip-flop waits for the one before, so the delay grows with the width. The outputs also pass through wrong values: 7 went through 6, 4 and 0 before reaching 8 in the course's simulation. A synchronous counter clocks every stage together, so all bits change on one edge within a single gate delay of each other."
What is lock-up?
"What is lock-up, and how do you design it out?"
Show the solution
"A counter locks up when its unused states lead only to each other, so if it ever lands in one it never returns to its sequence. Treating unused states as don't cares during design can cause it. Always follow every unused state, and give any that do not reach the sequence an explicit next state."
SRAM versus DRAM
"Compare SRAM and DRAM."
Show the solution
"SRAM stores each bit in a latch, usually six transistors, so it is fast and needs no refresh. DRAM stores each bit as charge on a capacitor with one transistor: far denser and cheaper, but it leaks and must be refreshed. Caches are SRAM; main memory is DRAM. Both are volatile."
How does a SAR ADC work?
"How does a successive-approximation ADC work?"
Show the solution
"It is a binary search with a DAC and one comparator. Set the top bit, compare the DAC's voltage with the input, keep the bit if the input is higher, then move down a bit. An n-bit result takes n steps. Measuring 3.30 V with 8 bits and a 5 V reference gave 168, which stands for 3.2813 V."
Noise margin
"What is noise margin?"
Show the solution
"How much noise a signal can pick up between one gate and the next and still be read correctly: VOH - VIH for a 1 and VIL - VOL for a 0. For standard TTL both are 0.4 V. It is why digital signals are so robust: noise that stays inside the margin changes nothing."
Flashcards
Test yourself: read the front, answer aloud, then turn the card.
01 Bits needed for N values
02 Negate in two's complement
03 8-bit two's complement range
04 De Morgan
05 Consensus term of A·B + A'·C
06 K-map group sizes
07 Essential prime implicant
08 Full adder
09 Signed overflow
10 JK characteristic equation
11 Latch or flip-flop?
12 Johnson counter states
13 R-2R DAC output
14 Flash ADC comparators
15 Noise margins
16 CMOS switching power
In an interview, which answer about latches and flip-flops is strongest?
Show the answer
Answer: C. It states the idea, gives the reason and names the mechanism. The others are wrong or say nothing.
What you learned in this course
- How to count, convert and store negative numbers with bits, and the codes computers use.
- The seven gates, why NAND and NOR are universal, and how propagation delay causes glitches.
- Boolean algebra, De Morgan, SOP and POS, minterms and maxterms - and simplifying with K-maps.
- The combinational building blocks: multiplexers, decoders, encoders, comparators and adders.
- How memory comes from feedback: latches, flip-flops, setup and hold.
- Registers, shift registers and counters, and how to design a counter for any sequence without lock-up.
- How memories, converters and logic families connect digital logic to real chips.
Where to go next
You now know what digital circuits are made of. Three courses on this site build directly on it:
- Verilog and SystemVerilog describes circuits like these in code, so a tool can build them for you.
- State Machines from Zero takes the counters of Volume 08 further, into machines that react to their inputs.
- Static Timing Analysis from Zero turns setup, hold and clock-to-Q into a complete method for checking a whole chip.
If you are preparing for GATE, the GATE ECE practice portal has more questions across every subject.