Past exam of the year 1 of the computer science course of the University of Oxford / 2021 / Digital systems, linear algebra, introduction to formal proof / 1

After asserting and releasing the active-low Start pulse, a valid sequence is $X_0\uparrow$, then $X_1\uparrow$, then $X_2\uparrow$, with each input held high through the relevant sampling interval. The first JK flip-flop has $J=X_0,K=0$ and is clocked by $X_1$, so the rising clock edge of $X_1$ samples $X_0=1$ and sets $Y_0=1$. Once that output has settled, a rising clock edge of $X_2$ clocks the second JK flip-flop with $J=Y_0=1,K=0$, setting $Y_1=1$.

The essential conditions concern sampled levels: $X_0$ must be high at a rising clock edge of $X_1$, and $Y_0$ must then be high at a rising clock edge of $X_2$. Separate edges with adequate setup and hold time avoid an ambiguous simultaneous transition.

The initial input levels do not initialize the stored bits. The negative Start pulse asynchronously clears both outputs to zero, making the experiment start from a known state even without any clock edge. Once Start is released, the circuit can recognize a fresh sequence. It also clears the history retained by the JK flip-flops between trials; merely lowering the data inputs would not do so.

With $K=0$, a JK flip-flop obeys $Q^{+}=J\vee Q$ at its positive clock edge: $J=0$ holds its old state and $J=1$ sets it. Thus each original stage is a sticky record of a previously sampled high input until Start clears it. A D flip-flop instead obeys $Q^{+}=D$, so a later sample of zero can clear the output.

Connect each replacement D input where the corresponding J input was connected, preserving the clocks and asynchronous clear. The first valid sequence after Start still sets both outputs. Afterwards, let $X_0$ fall and apply another rising clock edge to $X_1$. The D version clears $Y_0$; the JK version retains $Y_0=1$. A subsequent rising clock edge of $X_2$ can therefore clear $Y_1$ only in the D version. Neither circuit continuously tracks its data input between clock edges.

Each stage has $J=K=1$ and therefore toggles. The printed clock symbols have no inversion bubble, so they are positive-edge triggered; each later clock is driven by the previous uncomplemented $Q$ output. Consequently the circuit is a ripple counter that counts down modulo eight. A zero least significant bit rises to one and propagates the transition; a one falls to zero and stops it. For example, the settled transition from $001$ is $000$, whereas $000$ is followed by $111$.

After $N$ input pulses the settled value is $(1-N)\mathrm{mod}8$, givingThe answers are $101$, $100$, and $000$, respectively, in most-significant-first order. Treating these as falling-edge stages would reverse the counting direction and would not follow the drawn clock symbols.

The inclusive range contains $2147483648=2^{31}$ distinct states. An $n$-bit binary counter has $2^n$ states, so 31 JK flip-flops in total are necessary and sufficient for the required capacity: add 28 to the three shown.

This is a capacity calculation. The printed positive-edge, uncomplemented-output cascade visits these codes in descending order. To obtain increasing numerical order one must change the cascade clock polarity, for example clocking each positive-edge stage from the preceding complemented output.

Connect the fourth JK flip-flop with $J_3=K_3=1$ and clock it from $Q_2$, retaining the source's positive-edge convention. Read the four-bit state as $Q_3{Q}_2{Q}_1{Q}_0$. Its state-transition diagram is a single cyclewith one input rising clock edge per arrow; the figure displays every state explicitly.

Each stage halves the preceding triggering frequency. $Q_3$ is an ideal square wave with a 50-percent duty cycle at $1\mathrm{GHz}/16=62.5\mathrm{MHz}$, with wave period $16\mathrm{ns}$ and high and low intervals of $8\mathrm{ns}$. Its initial phase depends on the starting state. The figure chooses initial state $0000$ and a first input rising clock edge at $1\mathrm{ns}$. Actual ripple propagation shifts edge times and creates intermediate transient codes; no device delays were supplied, so the waveform describes settled ideal logic.