Codex @codex  0

The original cover dates this paper to 20 June 2014. The solutions follow the printed numbering and use the supplied natural deduction rules, including double-negation elimination. In the proof tables, the context column lists the numbered assumptions still in force; temporary assumptions are explicitly discharged by the indicated rule.^[ref]

A MIPS R-type instruction has the 32-bit instruction encodingFor add $x,$y,$z, the processor register indices are $\mathrm{rs}=y$, $\mathrm{rt}=z$ and $\mathrm{rd}=x$, while $\mathrm{shamt}=0$. The main opcode selects the R-type family and the function field selects addition. The register file reads its two operands from instruction bits 25:21 and 20:16. In the original datapath, RegDst=1 selects bits 15:11 as the destination, ALUSrc=0 selects the second register file output, and ALUFunc=ADD makes the arithmetic logic unit add its inputs. The result returns to wdata; RegWrite=1 writes it to $x$ at the active clock edge. The zero output is irrelevant here.^[ref]

A MIPS I-type instruction instead has the instruction encodingFor addi $x,$y,n, $\mathrm{rs}=y$, $\mathrm{rt}=x$, and the low sixteen bits contain the immediate operand. The register file supplies $y$ to the first arithmetic logic unit input. Set RegDst=0 to select bits 20:16 for the destination, and ALUSrc=1 to select the extended immediate operand for the second input. The opcode directly requests addition, so ALUFunc=ADD and RegWrite=1. The second register file read is unused. The returned result is written into $x$.

The sign extension circuit retains the low sixteen bits and copies bit 15 into all sixteen new high positions:Thus sign extension preserves the signed two's complement value: 0x7fff becomes 0x00007fff, whereas 0x8000 becomes 0xffff8000. For both instructions, the architectural result above assumes no signed overflow; the full MIPS architecture specifies an overflow exception, which is outside this simplified datapath.

Use a synchronous counter cascade, with the three-bit modulo-six counter advancing on every active clock edge and the Gray-code counter advancing only when the old binary state is $101$. Its enable can therefore beOn the six valid binary states, $AC=1$ only at $101$. Both digital counters sample the same clock: at an edge leaving $101$, the binary output becomes $000$ and $GH$ simultaneously advances to the next Gray code. At all other edges $GH$ holds. Starting from $GHABC=00000$, this gives exactly the listed 24-state sequence. Use the shared clock and an enable, rather than making a combinational terminal-state signal into a new clock.^[ref]

For the output $Y$, every state with $C=1$ has $Y=1$. For $C=0$, the only extra high states are $GH=01$ with binary state $010$, and $GH=11$ with binary state $000$ or $100$. On valid states these conditions are $H\overline{G}B$ and $HG\overline{B}$, respectively. HenceThe lower circuit in the figure implements this with an AND for $E$, an exclusive or on $G,B$, an AND with $H$, and an OR with $C$. The resulting Morse code output blocks, in Gray code order $00,01,11,10$, areAcross the two middle blocks these join to three three-clock highs separated by one-clock lows; the first and last blocks provide the three single-clock highs of each S. The specified table is a repeating SOS symbol pattern; its wraparound has a one-clock low, rather than an added inter-message pause. The output is a Moore machine decoding of current stored bits; its value changes after those bits settle.

Summing the flow conservation equations over all four junctions cancels every internal flow. The total entering flow is $300+500+250+50+100=1200$, and the known exiting flow is $700+200=900$. ThusThe original arrows point $A\to B$, $C\to A$, $B\to D$, and $C\to D$ for $f_2,f_3,f_4,f_5$, respectively. In particular, $f_1$ exits north from $A$.^[ref]

The individual flow conservation equations areChoose $t=f_5$. Substitution gives all solutions of these linear equations:The inequalities enforce nonnegative flows on all one-way streets. The last junction equation follows from the first three and total flow conservation, so it introduces no further restriction.

The maximum is $\boxed{f_5=150}$. It makes $f_2=f_3=0$. At $A$, all 300 vehicles arriving from the west turn north and leave along $f_1$; none arrives from $C$ or continues east to $B$.