Past exam of the year 1 of the computer science course of the University of Oxford / 2003 / Functional programming, data structures and algorithms, procedural programming, and digital hardware / 10

An $n$-bit two's complement word $b_{n-1}\cdots b_1{b}_0$ represents the integerThe leading bit has negative weight. Words beginning with zero encode the nonnegative values; words beginning with one encode the negative values. Equivalently, interpret the whole word as unsigned and subtract $2^n$ when its leading bit is one. For example, the four-bit words 0111, 1000, and 1111 encode $7$, $-8$, and $-1$ respectively. The range is asymmetric: the most negative value has no positive counterpart in the same number of bits.

For a nonzero representable magnitude, complementing all bits and adding one obtains its negative modulo $2^n$. Fixed-width addition can therefore use the same low-order binary numeral system addition circuitry for signed and unsigned operands; interpreting the result as signed requires detecting integer overflow.

Write $H=2^{n-1}$ and $U=H-1$. The operands occupy the integer points of the square $[-H,U{]}^2$. The exact sum is representable precisely whenThe upper boundary is $y=U-x$, and the lower boundary is $y=-H-x$. Within the operand square, the closed band between these lines is representable. The triangle below the lower line has negative overflow, and the triangle above the upper line has positive overflow. The boundary lines themselves are included.

Consequently overflow occurs exactly when $x+y<-H$ or $x+y>U$. Negative overflow requires two negative operands; positive overflow requires two nonnegative operands. Same-sign operands alone are not sufficient: their exact sum must cross a range endpoint. Opposite-sign operands never overflow on addition. In terms of the stored wrapped result, addition overflows exactly when the operands have equal sign bits and the result has the opposite sign bit.

The illustration uses $n=4$, so $H=8$ and $U=7$, and marks every permissible operand pair. The general region follows from the same two inequalities for arbitrary $n\ge 1$.

For the exact difference, the representability condition becomesWithin the same operand square $[-H,U{]}^2$, the closed diagonal band between $y=x-U$ and $y=x+H$ is representable. Above the upper line, $x-y<-H$ gives negative overflow; below the lower line, $x-y>U$ gives positive overflow. The right-hand panel of the figure shows these regions, including their representable boundary points.

Positive overflow can occur only when $x\ge 0$ and $y<0$; negative overflow can occur only when $x<0$ and $y\ge 0$. The corresponding exact inequalities are still required: operands with different signs do not always overflow. Same-sign subtraction is always representable. In sign-bit terms, subtraction overflows exactly when the operands have different signs and the wrapped result's sign differs from that of $x$.

One must test subtraction directly or use its correct overflow rule: forming -y in the same $n$ bits fails at $y=-H$, even though some differences with that operand are representable. For example $(-H)-(-H)=0$ is valid.

A D flip-flop stores one bit. On each active clock edge, it samples the input D and changes its stored output Q to that sampled value after the propagation delay. Between active edges, it holds the value. In the ideal discrete model,where $D_k$ is the input sampled at edge $k$ and $Q_{k+1}$ is the state just after that edge. This assumes D meets the required setup time and hold time; asynchronous set or reset inputs, if present, are inactive.

A fully synchronous sequential circuit has all its state stored in edge-triggered elements driven by a common clock signal, with combinational logic computing the next state from the current state and inputs. State updates occur together at the designated clock edges, rather than letting one register output serve as another register's ripple clock. Its ideal equations areFor a Moore machine the output function depends only on the state, $z_k=G(s_k)$. Physical design must leave enough time for register-to-register combinational paths and satisfy setup time and hold time at every receiving storage element.

Use a three-state Moore machine for a rearmable one-cycle pulse generator. Call the states Ready, Pulse, and Wait. Their outputs are respectively $z=0,1,0$, and initialize in Ready. Labels below are the sampled input pair ab; because simultaneous ones are unspecified, choose reset priority for 11.

The complete chosen state transition table is

A sampled trigger 10 causes a pulse only in Ready. Leaving Pulse unconditionally on the next edge keeps its output high for exactly one clock period, even if a remains high. In Wait, further triggers are ignored until a sampled reset rearms the finite-state machine.

The crucial transition is Pulse --01--> Ready. If reset occurs in the cycle immediately following a trigger, this transition both ends the current pulse and rearms the circuit. The next trigger then produces a pulse after just one intervening low-output cycle. Sending every exit from Pulse to Wait would lose that reset and fail the alternate-cycle requirement. This behavior is explicitly visible in the last three pulses of the original timing diagram.^[ref]

For the sixteen sampled pairs in that diagram, numbering the first edge as 1, z is high just after edges $2,10,13,15$ and low after every other edge. Equivalently,The two low-output states cannot be merged: the same future trigger must produce a pulse from Ready and be ignored from Wait. A separate high-output state is needed to hold the one-cycle pulse, explaining the three-state design.