Sequential Circuits, Timing, Data Converters, Memories and Computer Organisation

Four delays describe a clocked stage, and mixing them up is the single most expensive habit in this section. Propagation delay t_pcq is the longest time from the clock edge until the flip-flop's output has settled. Contamination delay t_ccq is the shortest time from that edge until the output begins to change. Setup time t_su is how long the data must already be stable before the edge, and hold time t_h is how long it must remain stable after it. The combinational logic between two flip-flops has its own longest and shortest paths, t_pd and t_cd. The critical path is the longest register-to-register route through the whole design, and the clock period must exceed it; the shortest such route matters too, but for a completely different reason.

Work one stage all the way through. Take t_pcq = 0.9 ns, t_ccq = 0.5 ns, t_su = 0.4 ns, t_h = 0.25 ns, a combinational block whose longest path is t_pd = 3.2 ns and whose shortest is t_cd = 0.15 ns, and clock skew of 0.2 ns between the two flip-flops. The setup constraint says data launched at one edge must arrive and settle before the next: T_c ≥ t_pcq + t_pd + t_su + t_skew = 0.9 + 3.2 + 0.4 + 0.2 = 4.7 ns, so f_max = 1/4.7 ns ≈ 212.8 MHz. The hold constraint is a different inequality with no T_c in it at all: t_ccq + t_cd ≥ t_h + t_skew, that is 0.5 + 0.15 = 0.65 ns against 0.25 + 0.2 = 0.45 ns, satisfied with 0.2 ns of margin. Now push the skew to 0.45 ns and the hold requirement becomes 0.70 ns, which 0.65 ns fails — and no clock frequency fixes it, because the clock period does not appear in the inequality.

A mod-N counter needs ⌈log₂ N⌉ flip-flops, so a mod-12 counter takes four and a mod-100 counter takes seven, with the unused states either unreachable by design or steered back by decoding logic. The examinable divide is not the count but the clocking. In a ripple (asynchronous) counter each flip-flop's output clocks the next, so the delays add: four flip-flops of 7 ns propagation delay leave the outputs unsettled for up to 4 × 7 = 28 ns after an edge, which caps the usable clock at about 1/28 ns ≈ 35.7 MHz and, worse, means the output bus passes through counts the sequence never really visits. Decode those transient patterns and you get glitches — the reason a ripple counter's outputs should never drive a decoder directly.

A synchronous counter clocks every flip-flop from the same edge, so the outputs change together and the delays do not accumulate. What limits it instead is one stage of the loop: T_c = t_pcq + t_comb + t_su. With the same 7 ns flip-flops, 4 ns of enable-chain logic between stages and a 2 ns setup requirement, T_c = 13 ns and f_max ≈ 76.9 MHz — more than twice the ripple counter's ceiling. Look at what has vanished from that expression: the number of bits. Adding a fifth stage to a synchronous counter does not slow it down unless it lengthens the enable chain, whereas adding one to a ripple counter always does. That asymmetry, and not gate count, is why synchronous counters dominate despite costing more logic.

A shift register is n flip-flops in a chain, each feeding the next, so a serial bit stream is delayed by exactly n clocks — the standard serial-to-parallel and parallel-to-serial converter, and the delay line inside every digital filter. Feed the output back and the sequence closes: a ring counter of n stages has n states with one hot bit circulating, while a Johnson or twisted-ring counter feeds back the complement and gets 2n states from the same n flip-flops. Feed back an XOR of two tapped stages and you have a linear feedback shift register, which is what generates pseudo-random bit sequences in communication test equipment. A 4-bit LFSR with taps on the third and fourth stages cycles through 15 states — every pattern except all zeros, which is a fixed point the register can never leave. In general an n-bit maximal LFSR has 2^n − 1 states, and the missing one is always the all-zero word.

A synchronous FSM is a state register plus two blocks of combinational logic: next-state logic reading the present state and the inputs, and output logic. In a Moore machine the output is a function of the state alone; in a Mealy machine it is a function of the state and the current input. That single difference has three consequences worth carrying into the exam. A Mealy machine usually needs fewer states, because the input can do some of the discriminating. Its output appears one clock earlier, because it does not wait for the transition to be registered. And its output can glitch, since it follows an input directly through combinational logic, whereas a Moore output changes only just after a clock edge and is therefore clean enough to drive other logic without qualification.

Design the standard detector both ways to see it. The task is to raise an output whenever the serial input has just completed the pattern 101, with overlaps allowed. As a Moore machine four states are needed: S0 has no useful prefix, S1 has seen a 1, S2 has seen 10, and S3 has seen 101 and is the only state whose output is 1. The transitions worth checking are the ones out of S3: on a 0 it goes to S2, because the sequence now ends in 10, and on a 1 it goes to S1, because the sequence now ends in a single useful 1. Get those two wrong and the machine stops detecting overlaps. As a Mealy machine three states suffice — A, B after a 1, C after 10 — and the output is asserted on the transition from C on input 1, which returns to B rather than to A for exactly the same overlap reason.

Trace the input 1101011 through the Moore table, starting in S0, and the states visited are S1, S1, S2, S3, S2, S3, S1. The output is high in the two visits to S3, so the machine reports two detections — which is right, because 1101011 contains 101 starting at its second bit and again starting at its fourth, the two occurrences sharing a 1. A machine that reported one detection was built without the overlap transitions; a machine that reported three has invented one. Notice that both designs need ⌈log₂ 4⌉ = 2 flip-flops for Moore and ⌈log₂ 3⌉ = 2 for Mealy, so on this example the Mealy saving in states buys no hardware at all — a useful corrective to the idea that fewer states always means a smaller circuit.

An ADC needs its input to stand still while it decides, so almost every converter is preceded by a sample and hold: a switch that connects the input to a hold capacitor C_H through a buffer, and a high-impedance amplifier that reads the capacitor once the switch opens. Four numbers characterise it. Acquisition time is how long the switch must stay closed for the capacitor to settle to within the required error — set by the source resistance and C_H. Aperture time and its jitter are the uncertainty in when the switch actually opened, which converts input slew into amplitude error. Droop is the slow decay of the held voltage caused by leakage into the switch and the amplifier's input. And pedestal error is the step injected by charge from the switch as it opens.

Droop is where a clean numerical question lives, because it ties the analog part to the resolution. Take a 12-bit converter with a 5 V reference. One least significant bit is 5/4096 = 1.2207 mV, and a sensible error budget for the hold stage is half of that, 0.6104 mV. Now let the hold capacitor be C_H = 100 pF with a total leakage of 10 nA. The droop rate is dV/dt = I/C = 10 × 10^(−9) / 100 × 10^(−12) = 100 V/s, which is 0.1 mV/µs. Divide the budget by the rate: the voltage may be held for 0.6104 / 0.1 = 6.1 µs before the droop alone costs half a bit. That single division decides whether a given converter can be driven by a given sample-and-hold, and it explains the design pull in both directions — a larger C_H droops more slowly but takes longer to acquire, and the two requirements meet somewhere in the middle.

The same 12-bit, 5 V converter fixes the other standard figures. Quantisation error is bounded by ± half an LSB = ±0.61 mV, and the signal-to-quantisation-noise ratio of an ideal converter on a full-scale sine is 6.02n + 1.76 = 6.02 × 12 + 1.76 = 74.0 dB — the reason resolution is quoted in bits and dynamic range in decibels, one bit being worth about 6 dB. On the ADC side the architectures trade speed against hardware in a way worth knowing as a table rather than as prose. On the DAC side, a weighted-resistor DAC needs resistances spanning R to 2^(n−1)R, which is unbuildable at 12 bits, while an R-2R ladder needs only two resistor values and is therefore what real parts use. For an 8-bit R-2R DAC with V_ref = 8 V, the output is V_ref × D/256; the code 10100000 is D = 160, so the output is 8 × 160/256 = 5.000 V, and one LSB is 8/256 = 31.25 mV.

All three memories are the same architecture — an address decoder driving one row of an array, and a column circuit reading or writing the selected cells — and they differ almost entirely in the cell. A ROM cell is the presence or absence of a transistor at a crossing, so a ROM is literally a printed truth table: address lines are the inputs, the addressed word is the outputs. That makes a ROM a general combinational logic block, and the sizing question follows directly: to implement three arbitrary functions of four variables you need 2^4 words of 3 bits, which is 16 × 3 = 48 bits, and no minimisation is required or possible. An SRAM cell is two cross-coupled inverters plus two access transistors, six transistors, which holds its value as long as power is present and can be read without disturbing it. A DRAM cell is one transistor and one capacitor, which is why DRAM is several times denser and cheaper per bit than SRAM, and it pays for that density twice over.

The first payment is that a DRAM read is destructive. Sharing the tiny cell capacitor's charge onto the much larger bit-line capacitance leaves only a few tens of millivolts of signal, which a sense amplifier must resolve and then write back — so every read is a read-modify-write, and the row must be precharged before the next access. The second payment is refresh. Leakage discharges the cell, so every row must be rewritten within a retention time, typically 64 ms. A part with 4096 rows must therefore refresh one row every 64 ms / 4096 = 15.625 µs, and if a refresh cycle occupies 100 ns the overhead is 100 ns / 15.625 µs = 0.64 % of the available bandwidth — small, but never zero, and it is why DRAM has a controller and SRAM does not.

The other examinable habit is address arithmetic, which is pure counting. A 1K × 8 chip has 2^10 words, so it needs 10 address lines and 8 data lines. Build a 4K × 8 memory from four of them and the address bus is 12 bits wide: A9 down to A0 go to every chip in parallel, and A11 and A10 drive a 2-to-4 decoder whose four outputs are the chip selects, so exactly one device answers any address. The general rule is worth stating once: the low-order address bits select within a chip and the high-order bits select between chips, and a question that asks which lines go where is answered by counting log₂ of the chip depth. Word-width expansion is the other direction — two 1K × 4 chips side by side make 1K × 8, with the same address on both and the data buses concatenated rather than decoded.

Machine instructions and addressing modes come first, and the fastest way in is field arithmetic. A 32-bit instruction with a 6-bit opcode and three 5-bit register fields has 32 − 6 − 15 = 11 bits left for an immediate, which as a two's complement value spans −1024 to +1023; change the opcode to 7 bits and the immediate range halves. An addressing mode is just a rule for turning instruction fields into an effective address. With R1 = 0x2000 as a base, R2 = 0x40 as an index and a displacement of 0x8, base-plus-index-plus-displacement gives EA = 0x2000 + 0x40 + 0x8 = 0x2048. Counting memory accesses is the other standard question, and the ordering is what matters: immediate and register modes touch memory not at all beyond the fetch, direct and register-indirect take one access, and memory-indirect takes two because the address itself must be fetched first.

The ALU is the arithmetic core of the last chapter wrapped in a function select: one adder-subtractor built as described earlier, a logic unit, a shifter, and a multiplexer choosing which result reaches the output, with the status flags — zero, carry, sign and overflow — generated as a side effect. The data path is the registers, the ALU, the buses and the memory interface; the control unit is what asserts the enable, select and write lines in the right sequence. Control comes in two flavours, and the trade is the same one that runs through this whole section. Hardwired control is a finite state machine of exactly the kind designed earlier in this chapter: fast, and fixed at fabrication. Microprogrammed control keeps a small memory whose words are the control signals themselves, so the instruction set can be changed by rewriting a table: flexible, and slower by the access time of that memory.

Instruction pipelining is the last item, and it is arithmetic on the same critical-path idea that governed the flip-flop stage. Split execution into stages with latches between them; the clock period is then the slowest stage plus the latch overhead, never the average. Take a four-stage pipeline whose stages need 1.8, 2.4, 2.0 and 1.6 ns with 0.2 ns of latch delay. The unpipelined machine takes 1.8 + 2.4 + 2.0 + 1.6 = 7.8 ns per instruction; the pipelined one clocks at 2.4 + 0.2 = 2.6 ns, so the ideal speedup is 7.8/2.6 = 3.0 — against four stages, because the imbalance wastes the difference. For a finite run of 100 instructions the pipeline needs (k + n − 1) cycles, that is (4 + 99) × 2.6 = 267.8 ns against 100 × 7.8 = 780 ns, a speedup of 2.91. Both numbers are below k, for two separate reasons, and a question usually applies exactly one of them.