Past exam of the year 1 of the computer science course of the University of Oxford / 2018

Source release: Oxford examination archive, member a10101w1.pdf. The held cover identifies the regular 14 June 2018 examination. Every printed option is treated below.

Use a Moore machine whose state records the longest suffix of the received stream that is also a prefix of the target word. The transitions areThe last row preserves overlap: after recognition, one more one leaves suffix $11$, giving $S_2$. Initialize to $S_0$ and update the state on each active clock edge; the output after that edge reports whether the word has just ended. This is a prefix-suffix sequence recognizer.

Five distinct states require three D flip-flops, since $2^2<5\le 2^3$. Choose the state encoding $S_i$ equal to the three-bit binary expansion of $i$. Write the present bits as $A,B,C$, in decreasing significance. The state transition table isThe dashes are don't-care conditions for minimizing the logic. They do not prescribe what the actual circuit will do in those unused states; part (e) determines that from the chosen equations.

With the encoding in part (b), $y=A$ is a valid Moore machine output equation. Among reachable states, $A=1$ exactly at $S_4$. This uses unused output-table entries as don't-care conditions. If one instead wants the output to be zero in every unused state, use $y=A\bar{B}\bar{C}$; that extra requirement does not change any output from a valid state.

Use four-variable Karnaugh maps with rows $AB=00,01,11,10$ and columns $Cx=00,01,11,10$, both in Gray code order. A dash denotes an unused present state. The maps for the three next-state bits areFor $A^{+}$, join its sole one with the dash directly below it. For $B^{+}$, use the four-cell groups $Ax$ and $B\bar{C}$, and the two-cell group $\bar{B}Cx$; the last group wraps between the top and bottom rows. For $C^{+}$, join the one at row $01$, column $00$ to the dash below it; the one at row $00$, column $01$ is isolated. These prime implicants giveHere products mean Boolean conjunction and sums mean Boolean disjunction. The $D$ inputs are the desired next-state bits of the three D flip-flops. The equations are independent of the unused values except for the explicitly chosen Karnaugh map groups.

Evaluate the implemented equations from part (d), rather than the don't-care entries of the original table:States $101$ and $110$ enter a valid state after one edge. State $111$ does so after one edge for zero, or moves to $110$ and enters a valid state on the following edge for either next input. Thus every unused state recovers within at most two clock edges, independently of the incoming bits. The machine cannot become trapped there. This self-starting finite-state machine property does not guarantee meaningful recognizer output during recovery; initialization to $S_0$ still establishes the intended stream history.

The internal Boolean functions are $x=\bar{a}\bar{c}$, $y=bc$, $z=\bar{c}d$, $w=y+z$ and $q=x+w$. Put the falling edge of $c$ at $t=0$. Since $a=1$ throughout, $x=0$ throughout. The remaining transitions, including every stated propagation delay, areThe inverter delays the rise of $\bar{c}$ by ten nanoseconds, and the $z$ AND gate adds another ten. Consequently $y$ and $z$ are simultaneously zero for ten nanoseconds. This gap propagates through the two OR gates. The output has a static-one logic hazard: a low glitch on $30\le t<40$ ns, despite its equal initial and final logical values.

The steady-state output is $q=\bar{a}\bar{c}+bc+\bar{c}d$. Its Karnaugh map, with rows $ab$ and columns $cd$ in Gray code order, isThe existing prime implicants cover adjacent ones except for some transitions in $c$. The consensus theorem supplies the two missing bridging implicants $\bar{a}b$ and $bd$, givingBoth are needed in a hazard-free sum of products retaining the original terms. At $a=0,b=1,d=0$, the two values of $c$ require a common implicant, necessarily covered by $\bar{a}b$; at $a=1,b=1,d=1$, the corresponding transition requires $bd$. Neither bridge covers the other's critical edge. All other adjacent-one pairs already share a term. Thus two is the least number of additional prime implicants. This addresses single-input static hazards; simultaneous input changes require separate analysis.

To implement the two additional prime implicants explicitly, add two 2-input AND gates and two 2-input OR gates. Reuse $\bar{a}$ from the existing inverter. An OR-tree arrangement that keeps the maximum propagation delay at 40 ns isThe five product gates feed four OR gates; the original circuit already supplied three of the product gates and two OR gates. From the primary inputs, $bc$ and $bd$ settle by 10 ns, so $u$ settles by 20 ns. The two products in $v$ and the product $\bar{c}d$ settle by 20 ns, so $v$ and $w$ settle by 30 ns, and $q$ by 40 ns. In particular, no increase in worst-case delay is necessary. Merely appending two OR gates to the old output would unnecessarily lengthen some paths.

If arbitrary rewiring and factoring are allowed, an even smaller added-hardware implementation isExpanding this expression gives all five terms from part (b). It needs three OR gates, two AND gates and the existing two inverters: add one OR gate, reuse two existing AND gates and leave the third unused. Both $u$ and $v$ settle by 20 ns, $t$ by 30 ns and $q$ by 40 ns. During a potentially hazardous change of $c$, the bridging condition $b=u=1$ holds $v=t=1$ regardless of $c$; zero-to-zero cases keep either both $b,u$ zero or all relevant products steadily zero. The factored circuit therefore retains single-input hazard protection. The four-gate count above is the minimum when the two extra product implicants are required as separate AND outputs; factoring changes that implementation constraint.

Removing logic hazards prevents transient false control pulses, incorrect triggering of asynchronous state changes and avoidable switching activity. It also makes behavior less sensitive to unequal propagation delays. These benefits matter especially when an output directly controls another circuit rather than being sampled only after settling.

The usual costs are redundant logic gates, larger area and capacitance, more wiring and possibly a longer critical path. Power can rise from extra hardware even when glitch power falls. A synchronous design may instead sample after a sufficiently long clock period, trading settling time against additional hazard-correction logic. A circuit proved free of single-input static hazards need not be safe under arbitrary simultaneous input changes; metastability at an asynchronous input is a different problem.

Fetch the MIPS instruction at the program counter, and compute $pc+4$. The opcode selects an MIPS R-type instruction; register-file read addresses $rs$ and $rt$ select the two operands. The function field selects ALU addition. The result returns through write-back multiplexer input zero to destination $rd$, and the next program counter is $pc+4$.

Using the diagram's actual selector encodings, the control signals areHere $\mathrm{ALUOp}=10$ means decode the function field; $00$ means add and $01$ means subtract. The source's $\mathrm{Branch}=(B{r}_1,B{r}_0)$ is a two-bit control: the branch-taken output is $B{r}_1\wedge (B{r}_0\oplus \mathrm{Zero})$. With $B{r}_1=0$, $B{r}_0$ is immaterial; zero is a convenient concrete setting. No data-memory access occurs.

Fetch and decode the MIPS I-type instruction, read $rs$ and $rt$, and subtract their values in the arithmetic logic unit. The zero flag is one exactly when they are equal. The branch target isThe branch selector chooses that target when $B{r}_1=1$ and $B{r}_0=0$ make the diagram's condition equal to $\mathrm{Zero}$. Otherwise it chooses $pc+4$. Neither registers nor data memory are written. The control signals areDashes are don't-care conditions because register write enable is zero. The immediate goes to the branch-target adder, while the main ALU's second input remains the value in $rt$.

For the semantics stipulated by the question, write $pc+4$ to register 31 and load the next $pc$ from register $rs$. Read $rs$ through register-file output $r{d}_0$. Select input two of the next-PC multiplexer, which is already wired from $r{d}_0$. Select destination input two, already the constant register number 31, and write-back input two, already $pc+4$.

Thus the printed diagram already contains the necessary three-way multiplexers and wires. Extend the controller's opcode/function decoding to generateThe displayed $\mathrm{ALUOp}$ and $\mathrm{ALUSrc}$ settings are arbitrary safe choices for an unused result. No additional datapath hardware or control field is required beyond decoding this instruction into the existing values. This uses the question's explicitly specified $pc+4$ link convention.

Use the stipulated MIPS I-type instruction encoding, whose unused $rt$ field is zero, so register-file output $r{d}_1$ supplies the hardwired zero register. With $\mathrm{ALUSrc}=0$ and subtraction selected, the arithmetic logic unit computes $R[rs]-0$. Its zero flag detects $R[rs]=0$, while bit 31 of $r{d}_0$ is the sign in two's complement. Therefore the required signed test isIntroduce one new control bit $GT$, and replace the zero-flag input to the existing branch XOR byThis needs an AND gate, an OR gate and a tap of the sign bit. With $GT=0$, existing branch behavior is unchanged. With $GT=1$ and $\mathrm{Branch}=11$, the existing branch-taken circuit gives $\neg Z^{\ast }$, exactly the positive test. Its output still selects between $pc+4$ and the usual sign-extended branch target. The complete control row isSet $GT=0$ for each instruction in parts (a)–(c). Registers and data memory remain unchanged. The available signed slt operation could support a different design; the sign-and-zero design above avoids adding an ALU-input swap and explicitly distinguishes zero from positive values.

Over the underlying field $F$, the row space is the linear span of the row vectors of $A$, a vector subspace of $F^n$. The column space is the linear span of its column vectors, a vector subspace of $F^m$. The null space isa vector subspace of the domain. The column space is the image of a linear map represented by $A$; the null space is its kernel.

Gaussian elimination givesElementary row operations preserve the row space, so $\{(1,0,1),(0,1,2)\}$ is a basis. The two rows are linearly independent because their first two coordinates form the standard basis of ${\mathbb{R}}^2$.

The pivot columns of the reduced matrix in part (i) are columns one and two. Select those columns of the original matrix, giving the column-space basisThey are independent, for example their first two entries have determinant $-2\ne 0$. The remaining original column is the first plus twice the second. Taking the reduced matrix's columns instead would generally give the wrong column space.

The reduced equations are $x+z=0$ and $y+2z=0$. Thus the null space is the lineThe nonzero spanning vector gives a one-element basis, so the nullity is one.

Reducing the augmented matrix givesThere is no contradictory row. Hence the system is consistent, with affine solution spaceThe three planes intersect in this common line. Their normals span a two-dimensional row space, leaving a one-dimensional common direction, the null space. More explicitly, five times the first equation minus eleven times the second plus twice the third is the zero equation, including the right-hand side; the third plane therefore contains the intersection of the first two.

The rank of $A$ is the dimension of its column space, equivalently the dimension of its row space or the number of pivot columns in a row-echelon form. For an $n\times n$ matrix it lies between zero and $n$.

Each elementary matrix is obtained by applying one invertible elementary row operation to the identity matrix. Its inverse is the elementary matrix for the reverse operation. A product of elementary matrices is therefore invertible and has full rank $n$.

Conversely, if $\mathrm{rank}A=n$, Gaussian elimination has a pivot in every column and reduces $A$ to the identity. Writing the successive row operations as left multiplication gives $E_r\cdots E_{1}A=I$. Hence $A=E_1^{-1}\cdots E_r^{-1}$, a product of elementary matrices. This proves both directions of the elementary-matrix factorization theorem.

False. In the real vector space $\mathbb{R}$, both $\{1\}$ and $\{2\}$ are bases: each is linearly independent and spans the whole space. A basis need not be a unique set. What is fixed for a finite-dimensional vector space is the number of basis elements, its dimension.

True. Existence follows because the basis spans $V$. If $v={\sum }_i{a}_i{s}_i={\sum }_i{b}_i{s}_i$, subtract to get ${\sum }_i(a_i-b_i)s_i=0$. The basis vectors' linear independence forces every $a_i-b_i=0$, proving uniqueness. For an infinite basis, both representations have finite support, so the same argument applies to their finite union. These coefficients are the coordinates relative to a basis.

Transpose both inverse identities, using reversal of multiplication under matrix transposition:Thus $(A^T{)}^{-1}=(A^{-1}{)}^T$, by uniqueness of the matrix inverse.

Let column $j$ of $A^{-1}$ be $x$, so $Ax=e_j$. Every diagonal entry of the invertible lower triangular matrix $A$ is nonzero, since its determinant is the product of those entries. In row one through row $j-1$, the right-hand side is zero. Forward substitution first gives $x_1=0$, then $x_2=0$, and successively $x_i=0$ for all $i<j$. These are precisely the entries above the diagonal in column $j$ of $A^{-1}$. Every column satisfies this, proving that $A^{-1}$ is lower triangular. This is triangularity of an inverse matrix.

If $B$ is an invertible upper triangular matrix, $B^T$ is invertible and lower triangular. Part (ii) makes $(B^T{)}^{-1}$ lower triangular, while part (i) identifies it with $(B^{-1}{)}^T$. Transposing gives that $B^{-1}$ is upper triangular. This deduction uses both the inverse-transpose identity and the lower-triangular result.

Gaussian elimination givesThe first two original columns form an image basis:Their independence follows already from their third and first coordinates. The third column is twice the first plus the second, and the fourth is the first plus twice the second, so they span every output of $T$.

The rank-nullity theorem states $\dim V=\dim \ker T+\dim \mathrm{im}T$ for a linear map from a finite-dimensional vector space $V$. Here the domain has dimension four and the image has dimension two. Thus $\dim \ker T=4-2=2$. For example, a kernel basis is $\{(-2,-1,1,0),(-1,-2,0,1)\}$, as follows from the reduced equations.

A linear map $T:V\to W$ is onto, or surjective, when every $w\in W$ equals $T(v)$ for some $v\in V$; equivalently its image is all of $W$. Here $T$ is not onto, because its image has dimension two while its declared codomain ${\mathbb{R}}^3$ has dimension three. Indeed every image vector satisfies $x+y-3z=0$, so, for example, $(0,0,1)$ is not attained.

A linear map is one-to-one, or injective, when equal outputs imply equal inputs. Equivalently its kernel is $\{0\}$: subtracting inputs converts equality of outputs to a zero output. Here $T$ is not one-to-one, since its kernel has dimension two. Concretely, $T(-2,-1,1,0)=T(0)=0$ for distinct inputs.