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

Use four request bits $r_0,r_1,r_2,r_3$ and four grant bits $g_0,g_1,g_2,g_3$. A high $r_i$ requests service for the coming allocation period, and a high $g_i$ identifies the requester granted the resource during the current period. At most one grant may be high. An all-zero grant vector means idle. The synchronous sequential circuit also has a clock and an initialization signal.

Requests are sampled at a clock edge; the resulting allocation appears during the following cycle. This fixes the Moore machine timing convention: current grants depend on the stored state, rather than combinationally on requests that can change within the cycle.

Store three state bits: a two-bit index $L\in \{0,1,2,3\}$ identifying the most recent recipient, and a valid bit $V$ indicating whether that recipient is receiving service in the current cycle. ThenWhen no requests are present at a decision edge, clear $V$ but preserve $L$. Preserving $L$ implements round-robin arbitration with idle memory. Four possible last recipients each have an active and an idle state, giving eight states. The four idle states have equal outputs but different future priorities, so they cannot all be merged. One valid reset is $L=3,V=0$, which gives requester zero first priority at startup.

All requester indices in the following expressions are interpreted modulo four. Let $h_{\ell ,j}$ mean that requester $j$ is the first asserted request after last recipient $\ell$:An empty logical conjunction is true. Decode the remembered index and combine the four priority orders:Exactly one $w_j$ is high when any request is high. Write $L$ as bits $L_1{L}_0$. The next-state function and Moore machine outputs areThus an idle step preserves the priority memory. The $w_j$ are combinational selection signals, not the current-cycle grants: exposing them directly as outputs would change the design into a Mealy machine. If a requester remains continuously asserted, each intervening successful grant advances the circular order, so it receives service after at most four grant decisions.

For a single read-only memory implementing both the next-state and output equations, the address has four request bits plus three present-state bits. Each word contains three next-state bits and four grant bits. HenceThree D flip-flops store the state outside this combinational ROM. This is the direct truth-table implementation for the encoding above. A smaller factored implementation exploits the independence of the next-state equations from $V$: a $64\times 3$ next-state ROM and an $8\times 4$ output ROM use $224$ stored bits in total, or the output decoder can be ordinary logic. These are different implementation organizations, not different state counts.