3.P — Worked Problems: Digital Electronics

Problem 1 — Noise margins and level compatibility

A 3.3 V LVC device (V_{OH}=2.4 V, V_{OL}=0.4 V) drives a 5 V HC input (V_{IH}=3.5 V, V_{IL}=1.5 V). Will it work? What if the receiver is a 5 V HCT input (V_{IH}=2.0 V, V_{IL}=0.8 V)?

Solution

HC receiver:

NM_H = V_{OH}-V_{IH} = 2.4-3.5 = -1.1\ \text{V}

Negative, so it fails. The driver's highest guaranteed output is more than a volt below what the receiver needs to read a 1. It may appear to work on the bench with a particular chip at room temperature, and it will fail in production.

NM_L = 1.5-0.4 = 1.1\ \text{V} \ ✓

Only the high level is broken.

HCT receiver:

NM_H = 2.4-2.0 = 0.4\ \text{V} \ ✓, \qquad NM_L = 0.8-0.4 = 0.4\ \text{V} \ ✓

Works, with 0.4 V of margin each way. HCT exists precisely for this: it is CMOS internally with TTL-compatible input thresholds, so it can be driven by anything that manages 2 V.

The other direction, 5 V driving 3.3 V, is a different problem entirely — not a margin problem but an absolute maximum problem. A 5 V high forward-biases the 3.3 V part's input protection diode into its supply rail, injecting current that can latch up or destroy the chip. Never mix the two directions up: low-to-high is a logic level question, high-to-low is a damage question.

Problem 2 — Fan-out limited by capacitance

A CMOS output with R_{on} = 25\ \Omega drives n inputs of 4 pF each on a track contributing 25 pF. The clock is 40 MHz and the rise time must stay under 20% of the period. Find the maximum n, and the power at that load with a 3.3 V supply.

Solution

Period is 1/(40\times10^6) = 25 ns, so the rise time budget is 5 ns.

t_r = 2.2R_{on}C \;\Rightarrow\; C_{max} = \frac{5\times10^{-9}}{2.2\times25} = 9.09\times10^{-11} = 90.9\ \text{pF}

n = \frac{90.9-25}{4} = 16.5 \;\Rightarrow\; \textbf{16 inputs}

Power at that load. Each output transition charges or discharges C; a full cycle costs CV^2:

P = CV^2f = 90.9\times10^{-12}\times3.3^2\times40\times10^6 = 90.9\times10^{-12}\times10.89\times4\times10^7

= 39.6\ \text{mW}

From one output pin. A bus of 32 such signals would dissipate 1.3 W just moving capacitance around, which is why bus widths, clock rates and voltages are all fought over so hard in chip design.

If 32 inputs were needed: split into two branches through a buffer. Each branch then sees 8 inputs plus its own track, and the buffer's own delay is added — a straight trade of latency for edge rate.

Problem 3 — Boolean simplification, two ways

Simplify F = \bar A\bar B\bar C+\bar A\bar BC+\bar AB\bar C+AB\bar C, algebraically and with a Karnaugh map.

Solution

Algebraically. Take the first two terms:

\bar A\bar B\bar C+\bar A\bar BC = \bar A\bar B(\bar C+C) = \bar A\bar B

Take the last two:

\bar AB\bar C+AB\bar C = B\bar C(\bar A+A) = B\bar C

F = \bar A\bar B + B\bar C

By Karnaugh map. With A as the row variable and BC as the columns in Gray order 00, 01, 11, 10:

A \ BC	00	01	11	10
0	1	1	0	1
1	0	0	0	1

Cells with 1: 000, 001, 010, 110.

Group 000 and 001 (top row, first two columns): A=0, B=0, C varies → \bar A\bar B.

Group 010 and 110 (column 10, both rows): B=1, C=0, A varies → B\bar C.

F = \bar A\bar B+B\bar C \ ✓

Gate count: the original needed four 3-input ANDs and one 4-input OR — 16 gate inputs. The simplified version needs two 2-input ANDs and one 2-input OR — 6 gate inputs, plus the inverters. Roughly a third of the hardware for the same function.

Problem 4 — Karnaugh map with don't-cares

A BCD input (0–9) drives a circuit that must output 1 when the digit is greater than 6. Minimise using don't-cares for 10–15.

Solution

Output is 1 for 7 (0111), 8 (1000), 9 (1001). Don't-care for 1010 through 1111. Output 0 for 0 through 6.

Map with AB as rows, CD as columns, Gray order:

AB \ CD	00	01	11	10
00	0	0	0	0
01	0	0	1	0
11	X	X	X	X
10	1	1	X	X

Group 1: the bottom row's 1000 and 1001, extended into the don't-cares at 1011 and 1010 — the whole AB=10 row. Then extend upward into the AB=11 row, which is all don't-cares. That gives the entire right half of the map where A=1:

\text{term} = A

Group 2: the 1 at 0111, extended into the don't-care at 1111 (adjacent in A), giving BCD with A eliminated:

\text{term} = BCD

F = A + BCD

Check against the requirement. A=1 covers 8 and 9 ✓. BCD covers 0111 = 7 ✓. Nothing from 0 to 6 is covered: 6 is 0110, which fails BCD because D=0 ✓.

Without don't-cares the answer would have been A\bar B\bar C+\bar ABCD, needing seven gate inputs against three. Don't-cares halved the circuit for free.

Problem 5 — Hazard detection and removal

F = AB+\bar AC. Find the hazard and remove it.

Solution

Locate it. Set B=C=1. Then F = A + \bar A = 1 always.

But when A falls from 1 to 0:

• AB goes from 1 to 0 immediately (one AND delay).
• \bar AC goes from 0 to 1 after the inverter delay plus the AND delay.

Between those two moments both terms are 0 and the output glitches low. With a 3 ns inverter, the glitch is about 3 ns wide.

On the Karnaugh map, the two 1s at ABC = 110 and ABC = 011 are adjacent (they differ only in A when B=C=1)... more precisely, the cells 111 and 011 are covered by different groups with no group spanning them. That is the visual signature of a static-1 hazard: two adjacent 1s not covered by a common group.

The fix — add the consensus term:

F = AB+\bar AC+BC

Now when B=C=1, the BC term is 1 regardless of what A is doing, and holds the output up through the transition.

Verify it changes nothing logically. BC is only 1 when both B and C are 1; in that case either A is 1 (so AB is already 1) or A is 0 (so \bar AC is already 1). The term is always redundant and never wrong.

Cost: one extra AND gate and one more OR input, to remove a fault that would otherwise appear as an intermittent, unreproducible bug in whatever the output clocks.

Problem 6 — Adder delay and the frequency it allows

Compare a 16-bit ripple-carry adder with a 16-bit carry-lookahead adder built as four 4-bit groups with group-level lookahead. Gate delay is 1.5 ns; a full adder's carry path is two gate delays.

Solution

Ripple-carry.

t = 16\times2\times1.5 = 48\ \text{ns}

Plus the final sum XOR, 1.5 ns: 49.5 ns, so f_{max} = 20.2 MHz.

Carry-lookahead. Within a group: one delay to compute G and P, then two more for the two-level carry expression = 3 delays. Across groups, the same again for the group-level lookahead = 3 delays. Then the final sum: 1 delay.

t = (3+3+1)\times1.5 = 10.5\ \text{ns} \;\Rightarrow\; f_{max}=95\ \text{MHz}

Nearly five times faster.

Gate count. A ripple adder is 16 full adders, roughly 5 gates each = 80. The lookahead version adds, per 4-bit group, about 14 gates for the carry expressions, plus the group-level block: roughly 80 + 4(14) + 14 = 150 gates, nearly double.

The trade in one line: 88% more gates for 370% more speed. In an arithmetic unit that decides the processor's clock rate, that is an easy decision — which is why every processor's adder is lookahead or one of its faster descendants.

Problem 7 — Setup, hold and maximum clock

A design has t_{co}=2.5 ns, t_{su}=1.2 ns, t_h=0.4 ns, clock skew ±0.6 ns, longest logic path 9 ns, shortest logic path 0.3 ns. Find f_{max} and check for hold violations.

Solution

Setup, taking the worst-case skew as adding delay to the receiving clock's arrival — actually the worst case is skew that makes the period effectively shorter:

T \ge t_{co}+t_{logic(max)}+t_{su}+t_{skew} = 2.5+9+1.2+0.6 = 13.3\ \text{ns}

f_{max} = \frac{1}{13.3\times10^{-9}} = 75.2\ \text{MHz}

Hold:

t_{co}+t_{logic(min)} \ge t_h+t_{skew}

2.5+0.3 = 2.8 \ \text{ns} \qquad\text{versus}\qquad 0.4+0.6 = 1.0\ \text{ns}

2.8 \ge 1.0 \ ✓

Passes, with 1.8 ns of margin.

Now suppose the shortest path were a direct wire, 0 ns, and the skew were 2.5 ns (a badly distributed clock):

2.5+0 = 2.5 \qquad\text{versus}\qquad 0.4+2.5 = 2.9

Fails by 0.4 ns, at every clock frequency including 1 Hz. The only fixes are inserting buffers into the data path or fixing the clock tree. This is why hold violations are treated as more serious than setup violations — you cannot test your way around them by running slower.

Problem 8 — Metastability calculation

An asynchronous button, debounced to change at most 20 times per second, is sampled by a 50 MHz clock. \tau=250 ps, T_0=1.5 ns. Compare one, two and three synchroniser flip-flops, assuming each gives a full clock period minus 2 ns of settling time.

Solution

Clock period is 20 ns, so settling time per stage is 18 ns.

\text{MTBF} = \frac{e^{t/\tau}}{T_0f_{clk}f_{data}}

Denominator: 1.5\times10^{-9}\times5\times10^7\times20 = 1.5.

One flip-flop (no synchroniser — the receiving logic must settle within the same period, say 2 ns available):

\text{MTBF} = \frac{e^{2/0.25}}{1.5} = \frac{e^{8}}{1.5} = \frac{2981}{1.5} = 1988\ \text{s} = 33\ \text{minutes}

Unacceptable.

Two flip-flops (18 ns of settling):

\text{MTBF} = \frac{e^{18/0.25}}{1.5} = \frac{e^{72}}{1.5} = \frac{1.86\times10^{31}}{1.5} = 1.2\times10^{31}\ \text{s}

That is 4\times10^{23} years — longer than the universe has existed by fourteen orders of magnitude.

Three flip-flops would give e^{144}, a number with no physical meaning.

The conclusion. Two flip-flops is the standard answer and it is standard because the exponential makes it overwhelmingly sufficient. A third is used only at very high clock rates where the per-stage settling time is small — at 1 GHz the period is 1 ns and the sums come out very differently.

And note what one flip-flop costs: a button that glitches the system every half hour, which in a product is a fault report every day from every user, and which will never reproduce on a test bench.

Problem 9 — Sequence detector state machine

Design a Moore machine detecting 1101 with overlap allowed. Give the state table, the state assignment, and the next-state equations.

Solution

States, named by how much of the pattern has matched:

• S0: nothing
• S1: 1
• S2: 11
• S3: 110
• S4: 1101 — output 1

Transitions. Work out each failure carefully.

State	in=0	in=1	Output
S0	S0	S1	0
S1	S0	S2	0
S2	S3	S2	0
S3	S0	S4	0
S4	S0	S2	1

The reasoning on the tricky rows. From S2 (11) on a 1: you now have 111, whose last two bits are 11, still a valid two-character prefix, so stay in S2. From S4 (1101) on a 1: the last bit 1 plus the new 1 gives 11, a valid prefix — so go to S2, not S1. From S3 (110) on a 0: 1100 has no useful suffix, so back to S0.

Assignment. Five states need three bits: S0=000, S1=001, S2=010, S3=011, S4=100.

Next-state equations, reading down the columns:

Next state is S1 (001) only from S0 with in=1: \bar Q_2\bar Q_1\bar Q_0\cdot x.

Next state is S2 (010) from S1 with in=1, S2 with in=1, or S4 with in=1:

D_1 = x(\bar Q_2\bar Q_1Q_0 + \bar Q_2Q_1\bar Q_0 + Q_2\bar Q_1\bar Q_0)

Next state is S3 (011) from S2 with in=0: D_1D_0 set by \bar x\bar Q_2Q_1\bar Q_0.

Next state is S4 (100) from S3 with in=1: D_2 = x\bar Q_2Q_1Q_0.

Output: Y = Q_2 — the single simplest possible output logic, which is the reward for choosing 100 as the accepting state's code.

Safety. Three bits give eight codes and only five are used. Add a default transition sending 101, 110 and 111 to S0, so a glitch or a power-up transient cannot strand the machine in an unreachable loop.

One-hot alternative: five flip-flops, one per state, with next-state logic like D_{S2} = x(S_1+S_2+S_4) — an OR of three signals rather than a decode of three bits. More registers, much shallower logic, which is the right trade inside an FPGA.

Problem 10 — Counter design

Design a synchronous modulo-12 counter (0 to 11) using D flip-flops, and explain why the synchronous version is preferable.

Solution

Four bits, counting 0000 to 1011, then back to 0000.

Toggle conditions for a normal binary counter:

T_0=1, \quad T_1=Q_0, \quad T_2=Q_0Q_1, \quad T_3=Q_0Q_1Q_2

Terminal count detection. The last valid count is 11 = 1011. Detect it with Q_3\bar Q_2Q_1Q_0 — but since no count above 11 ever occurs, Q_3Q_1Q_0 is sufficient and cheaper (the only codes with those three bits set are 1011 and 1111, and 1111 never occurs).

\text{TC} = Q_3Q_1Q_0

Synchronous reset. On the edge after TC, load 0000 instead of counting:

D_i = \overline{\text{TC}}\cdot(\text{normal next value})_i

Why synchronous is preferable. The asynchronous alternative detects 1100 and pulls the clear line. That means:

1. The counter genuinely reaches 1100 for a few nanoseconds. Anything decoding the count sees a spurious "12".
2. The clear propagates to the four flip-flops with slightly different delays, so some clear before others — and if Q_2 clears first, the detection term collapses and the clear pulse is cut short before the others have responded. The counter can end up in a partially cleared state. This failure is well known and is called a "runt pulse" problem.

The synchronous version never reaches an invalid state at all, because the decision is made before the edge and applied at it. It costs one extra AND gate.

Maximum frequency: T \ge t_{co}+t_{AND\ chain}+t_{su}. With 2 ns, 3 ns and 1 ns: 6 ns, so 167 MHz. The AND chain grows with counter width, so a 32-bit counter needs lookahead in the enable terms exactly as an adder does.

Problem 11 — Memory system design

Build a 256 KB memory system from 64 KB × 8 chips, mapped at address 0x40000 to 0x7FFFF. Specify the address decoding.

Solution

Chips needed: 256/64 = 4 chips, each 8 bits wide, giving an 8-bit word. Four chips in a row for depth, not width.

Address bits. 256 KB needs \log_2(262144) = 18 bits, A_0 through A_{17}. Each 64 KB chip needs 16 bits, A_0 through A_{15}.

• A_0–A_{15} go to all four chips in parallel.
• A_{16} and A_{17} go to a 2-to-4 decoder producing the four chip selects.

Base address decoding. The system's range starts at 0x40000 and ends at 0x7FFFF. In a larger address space of, say, 20 bits, that range is exactly the values where A_{19}=0 and A_{18}=1:

\text{block enable} = \bar A_{19}A_{18}

Feed that into the decoder's enable input.

The map:

Chip	Range	A_{17}A_{16}
0	0x40000–0x4FFFF	00
1	0x50000–0x5FFFF	01
2	0x60000–0x6FFFF	10
3	0x70000–0x7FFFF	11

Verify one address. 0x6A3F1 in binary is 0110 1010 0011 1111 0001. A_{19}=0 ✓, A_{18}=1 ✓ so the block is enabled. A_{17}A_{16}=10, selecting chip 2 ✓. The remaining 1010 0011 1111 0001 = 0xA3F1 is the offset within that chip ✓.

Why this is safe by construction. The decoder activates exactly one output, so two chips can never drive the bus simultaneously. No arbitration logic is needed because the topology makes conflict impossible — which is the general lesson of address decoding.

Problem 12 — ADC resolution and range

A temperature sensor gives 10 mV/°C over 0 to 150 °C, read by a 12-bit ADC with a 3.3 V reference. Find the resolution in degrees, and design an amplifier to use the full range.

Solution

Sensor output range: 0 to 1.5 V.

ADC LSB:

\text{LSB} = \frac{3.3}{4096} = 0.806\ \text{mV}

Resolution in degrees, unamplified:

\frac{0.806\ \text{mV}}{10\ \text{mV/°C}} = 0.081\ \text{°C}

But only 1.5 V of the 3.3 V range is used, so 45% of the codes — you are effectively getting 11.1 bits.

Amplify to fill the range. Gain needed:

A = \frac{3.3}{1.5} = 2.2

Use a non-inverting amplifier (Chapter 2.5) with 1+R_f/R_1 = 2.2, so R_f = 1.2R_1. Take R_1 = 10 kΩ, R_f = 12 kΩ.

New resolution:

\frac{0.806\ \text{mV}}{2.2\times10\ \text{mV/°C}} = 0.037\ \text{°C}

Doubled, for the cost of one op-amp and two resistors.

But check the noise floor before celebrating. The op-amp's noise, the sensor's noise and the ADC's own noise all get amplified too. If the total input-referred noise is 1 mV rms, that is 0.1 °C — nearly three times the quantisation step, so the extra resolution is measuring noise, not temperature.

The honest fix is averaging. Averaging N samples reduces random noise by \sqrt N, so 16 samples improve it by 4× to 0.025 °C. This is oversampling used as a measurement technique, and it costs nothing but time. It only works for noise that is genuinely random; it does nothing for offset or gain error, which need calibration.

Problem 13 — Aliasing

A system samples at 10 kHz with no anti-alias filter. What frequencies appear at the output for inputs of 3 kHz, 7 kHz, 12 kHz and 23 kHz?

Solution

Nyquist frequency is 5 kHz. Anything above it folds.

f_{alias} = |f - k f_s| \ \text{brought into } 0\text{–}5\ \text{kHz}

3 kHz: below Nyquist, appears as 3 kHz ✓ correct.

7 kHz: |7-10| = 3 kHz. Appears as 3 kHz — indistinguishable from the genuine one.

12 kHz: |12-10| = 2 kHz. Appears as 2 kHz.

23 kHz: |23-20| = 3 kHz. Appears as 3 kHz again.

Three different input frequencies all become 3 kHz, and once sampled there is no way to tell them apart. This is not a processing limitation that a better algorithm could fix — the information is genuinely absent from the samples.

The filter required. To pass 4.5 kHz and stop 5.5 kHz with 60 dB of attenuation is a transition ratio of 1.22 across 60 dB, which needs roughly

n = \frac{60}{20\log_{10}(1.22)} = \frac{60}{1.73} = 35\ \text{poles}

Utterly impractical as an analog filter.

With 8× oversampling at 80 kHz, Nyquist becomes 40 kHz. Now the filter must pass 4.5 kHz and stop 40 kHz — a ratio of 8.9:

n = \frac{60}{20\log_{10}(8.9)} = \frac{60}{18.98} = 3.2\ \text{poles}

A four-pole analog filter, entirely ordinary. Then filter digitally down to 5 kHz and decimate by 8. This is why every modern converter oversamples, and the calculation above is the whole argument in numbers.

Problem 14 — Sigma-delta resolution

A second-order sigma-delta modulator with a 1-bit quantiser oversamples by 64. Estimate the effective resolution.

Solution

\text{SNR} \approx 6.02n+1.76+(2L+1)10\log_{10}(\text{OSR})-10\log_{10}\frac{\pi^{2L}}{2L+1}

With n=1, L=2, OSR = 64:

6.02(1)+1.76 = 7.78\ \text{dB}

(2\times2+1)\times10\log_{10}64 = 5\times18.06 = 90.3\ \text{dB}

10\log_{10}\frac{\pi^4}{5} = 10\log_{10}\frac{97.41}{5}=10\log_{10}19.48 = 12.9\ \text{dB}

\text{SNR} = 7.78+90.3-12.9 = 85.2\ \text{dB}

\text{ENOB} = \frac{85.2-1.76}{6.02} = 13.9\ \text{bits}

Fourteen bits from a one-bit converter.

Compare oversampling alone with no noise shaping (L=0):

7.78 + 1\times18.06 - 0 = 25.8\ \text{dB} = 4\ \text{bits}

Noise shaping supplied ten of the fourteen bits. That is the whole point of the architecture, and it is why the loop order and the oversampling ratio are the two numbers on any sigma-delta converter's front page.

Doubling OSR to 128 adds 5\times3.01 = 15 dB, which is 2.5 more bits. Going to third order with OSR 64 adds 2\times18.06 = 36 dB minus a larger penalty term, giving roughly 4 more bits. Both routes work; third-order loops need careful design because they can become unstable, which is why fourth order and above is rare.

Problem 15 — Microcontroller battery life

A device wakes every 5 minutes, spends 200 ms sampling at 4 mA, then 50 ms transmitting at 25 mA, and sleeps at 1.8 µA. Battery is a 1200 mAh lithium cell. Find the life, and the effect of halving the transmit time.

Solution

Charge per wake-up:

Q_{sample} = 4\ \text{mA}\times0.2\ \text{s} = 0.8\ \text{mA·s}

Q_{tx} = 25\ \text{mA}\times0.05\ \text{s} = 1.25\ \text{mA·s}

Q_{total} = 2.05\ \text{mA·s per cycle}

Average from the active periods:

I_{active,avg} = \frac{2.05}{300\ \text{s}} = 6.83\ \mu\text{A}

Plus sleep, which occupies essentially the whole period:

I_{avg} = 6.83+1.8 = 8.63\ \mu\text{A}

\text{Life} = \frac{1200\ \text{mAh}}{0.00863\ \text{mA}} = 139{,}000\ \text{hours} = 15.9\ \text{years}

In practice, self-discharge would kill the cell first — a lithium primary cell loses 1 to 2% per year, so about 10 years is the honest figure. When the calculated life exceeds the battery's shelf life, the design is done and further optimisation is pointless.

Halving the transmit time to 25 ms:

Q = 0.8+0.625 = 1.425, \quad I_{active} = 4.75\ \mu\text{A}, \quad I_{avg}=6.55\ \mu\text{A}

Life becomes 20.9 years — a 31% improvement, but irrelevant given the shelf life.

Where the real opportunity is: the sampling period costs 0.8 mA·s against transmission's 1.25. If the 200 ms of sampling is mostly the sensor settling while the processor spins in a delay loop, putting the processor to sleep during that wait cuts sampling to near zero. That single change is worth more than any radio optimisation, and it is the most common finding when a real design is measured rather than estimated.

Problem 16 — Choosing between microcontroller and FPGA

You must capture eight channels of 12-bit data at 5 MSPS each, apply a 64-tap FIR filter to each, and stream the result over Ethernet. Assess both options.

Solution

The computational load. A 64-tap FIR needs 64 multiply-accumulate operations per output sample:

8\ \text{channels}\times5\times10^6\ \text{samples/s}\times64 = 2.56\times10^9\ \text{MACs per second}

Microcontroller. A Cortex-M7 at 500 MHz with a single-cycle MAC delivers 5\times10^8 MACs per second — five times short, before any interrupt handling, Ethernet stack or ADC servicing. Even a high-end DSP with eight parallel MAC units at 1 GHz gives 8\times10^9, which is enough on paper but leaves little margin and requires the data to be perfectly organised.

And the input rate alone is a problem: 8\times5\times10^6\times2 bytes = 80 MB/s arriving continuously, which needs DMA and a memory system that can sustain it while the processor also reads it.

FPGA. A 64-tap FIR maps to 64 DSP slices in a systolic chain, one multiply per clock, producing one output per clock. Eight channels need 512 slices — well within a mid-range part with 700 to 2000 slices.

At 200 MHz the chain produces 200 million outputs per second per channel, against the 5 million required. The design is 40 times over-provisioned, so you would instead time-share: run one filter chain at 200 MHz serving all eight channels at 5 MSPS each, using 8\times5 = 40 MSPS of its 200 MSPS capacity. 64 DSP slices total instead of 512.

Verdict: FPGA, decisively. The load is regular, parallel and fixed-rate — exactly what an FPGA is for.

The realistic architecture is both. FPGA for the capture and filtering; a soft or hard processor core inside the same FPGA, or a separate microcontroller, for the Ethernet stack, configuration and control. Regular high-rate work in hardware, irregular decision-making in software. That division is the standard shape of every signal-processing product, and it recurs in Chapter 5.6 and Chapter 10.1.

---

Part 4 steps back from circuits entirely and asks what a signal is, what a system does to it, and why sines are the natural language for both.