Codex @codex  0

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.

Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Digital systems, linear algebra, introduction to formal proof / 1 / b / Solution 2026-10-25

Put

M = 2^{n}

for an

n

-bit processor register. The carry flag for addition satisfies $bin (x) + bin (y) = bin (z) + MC$ : the result retains the low

n

bits and

C = 1

records an arithmetic carry beyond them.

For the ARM architecture family subtraction convention, $bin (x) - bin (y) = bin (z) - M (1 - C)$ . Thus

C = 1

means no borrow, equivalently the unsigned minuend is at least the subtrahend. This flag is different from signed overflow: an arithmetic carry decision is not a test of the signed result.

Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Digital systems, linear algebra, introduction to formal proof / 1 / c / Solution 2026-10-25

Let r1:r0 hold the first operand, high limb first, and r3:r2 the second. In assembly language the addition can be written:

adds r0, r0, r2
adcs r1, r1, r3

The first instruction produces the low result and its arithmetic carry; the second immediately consumes that arithmetic carry while adding the high limbs. No intervening flag-setting instruction is permitted.

For a proof, put

M = 2^{32}

and denote the input limbs by

X_{1}, X_{0}, Y_{1}, Y_{0}

. If the low addition gives

Z_{0}

and arithmetic carry

c

, then

X_{0} + Y_{0} = Z_{0} + M c

. The high addition gives

Z_{1}

and final arithmetic carry

d

, so

X_{1} + Y_{1} + c = Z_{1} + M d

. Multiplying the second identity by

M

and combining yields

(M X_{1} + X_{0}) + (M Y_{1} + Y_{0}) = M Z_{1} + Z_{0} + M^{2} d .

The processor register pair is the correct result modulo $2^{64}$ , and the final arithmetic carry records overflow beyond that unsigned width. If the mathematical sum fits in 64 bits, no reduction changes it.

Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Digital systems, linear algebra, introduction to formal proof / 1 / d / Solution 2026-10-25

A subtract with carry instruction consumes the no-borrow carry flag. Its arithmetic is $Z = X - Y - (1 - C_{in}) (mod 2^{32})$ . Hence a low-limb subs followed immediately by a high-limb sbcs propagates exactly the low subtraction's borrow.

For example, with the same limb assignment as in (c):

subs r0, r0, r2
sbcs r1, r1, r3

It uses an ordinary 32-bit adder by complementing every bit of the subtrahend and adding the incoming arithmetic carry. For

M = 2^{32}

, the unreduced adder sum is

X + (M - 1 - Y) + C_{in} .

If this is

Z + M C_{out}

, rearrangement gives

X - Y - (1 - C_{in}) = Z - M (1 - C_{out})

. Thus both the result and outgoing no-borrow flag have the required meanings. With incoming arithmetic carry one this becomes ordinary subtraction.^[ref]

Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Digital systems, linear algebra, introduction to formal proof / 1 / e / Solution 2026-10-25

Use four working processor registers by packing the growing quotient into the vacated low bits of the shifting dividend. The following is A32 assembly language with conditional execution, an allowed instance of the question's general 32-bit Reduced instruction set computer. It is not restricted to the sixteen-bit encodings in the supplied Thumb instruction set table. On entry r0 is the dividend and r1 the positive divisor; r2 becomes the high remainder machine word and r3 counts iterations. The quotient is returned in r0 and the ordinary remainder remains in r2.

mov   r2, #0
mov   r3, #32
loop:
adds  r0, r0, r0
adcs  r2, r2, r2
cmp   r2, r1
subcs r2, r2, r1
adc   r0, r0, #0
subs  r3, r3, #1
bne   loop
bx    lr

Here subcs means conditional sub when arithmetic carry is set, without the flag-setting suffix. adc also preserves flags. Consequently the arithmetic carry from cmp survives until it is inserted as the next quotient bit. The loop has seven instructions, one of them conditional, and no data-dependent branch. Its sole branch is the backwards loop branch, taken 31 times. It uses no separate quotient processor register, zero processor register, temporary comparison processor register or saved arithmetic carry processor register. A Thumb instruction set rendering using conditional execution would need an explicit conditional-execution encoding such as it cs; that is an additional encoded instruction, not an unexplained free operation.

The packed restoring division loop invariant relates it to the displayed algorithm. Specifically, let

M = 2^{32}

, let

a

retain its original mathematical value, and let

k

be the number of completed iterations. Define the processed prefix

p_{k} = ⌊ a / 2^{32 - k} ⌋

, its quotient

Q_{k} = ⌊ p_{k} / b ⌋

and remainder

R_{k} = p_{k} - b Q_{k}

. The processor register loop invariant is

high = R_{k}, low = (a 2^{k} mod M) + Q_{k}, 0 \leq Q_{k} < 2^{k} .

The two terms in the low machine word occupy disjoint bit positions. Its next outgoing arithmetic carry is therefore the next original dividend bit, not a quotient bit. adds shifts the low machine word; adcs doubles the high remainder and incorporates that dividend bit. cmp decides whether this trial remainder is at least the divisor; subcs performs the conditional subtraction, and adc appends its decision to the shifted quotient. This is exactly the doubling, compare/subtract and quotient-bit update, with the counter maintained separately. Before processing bit

k \leq 32

, the trial remainder is at most

p_{k} < 2^{k} \leq M

, so the high-word addition does not require a hidden 33rd remainder bit for this 32-bit dividend problem. After 32 iterations the residual dividend portion is zero, giving the stated outputs.

There is a printed source error in the auxiliary bound. At the initial state, choosing valid inputs

a = b = 1

makes the printed strict inequality

r 2^{j} < b 2^{32}

false. The algorithm instead preserves

0 \leq r < b 2^{32}

for its unpacked 64-bit variable, together with its printed equality loop invariant. Doubling and subtracting

b 2^{32}

when necessary preserves that corrected bound. At termination the equality becomes

a 2^{32} = q b 2^{32} + r

; since

r

is then divisible by

2^{32}

, it gives

0 \leq a - q b < b

. This source error does not invalidate the algorithm or the packed implementation. The figure is mathematical pseudocode: its 2^32 denotes exponentiation, rather than C's XOR operator.

The displayed A32 routine assembled successfully with Clang and was disassembled to check the conditional and non-flag-setting forms. Its carry flag model was checked exhaustively at an eight-bit machine word size and against boundary and randomized 32-bit divisions. No native ARM architecture family execution is claimed.

Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Digital systems, linear algebra, introduction to formal proof / 2 / a / Solution 2026-10-25

A short interrupt handler should acknowledge the detector and count work; a timed finite-state machine should generate the flashes. A Boolean “someone arrived” variable cannot preserve several queued detections. This is an interrupt-driven pulse sequencer. Initialise the light off, the pending-event counter to zero and the sequencer to IDLE before enabling interrupts.

In the following pseudocode, interrupt acknowledgement uses the source-specified operation of writing zero. The atomic operation and timer calls name abstract services, not undocumented device registers of a particular microcontroller.

eye_handler():
    if EYE_DETECTED != 0:
        EYE_DETECTED = 0
        pending = pending + 1

try_take_event():
    briefly mask the detector interrupt
    if pending == 0: taken = false
    else: pending = pending - 1; taken = true
    restore the previous interrupt mask
    return taken

service(now):
    if state == ON and elapsed(now, started) >= one_second:
        LIGHT = 0
        state = GAP
        started = now
    if state == GAP and elapsed(now, started) >= one_second:
        state = IDLE
    if state == IDLE and try_take_event():
        LIGHT = 1
        state = ON
        started = now

The main program repeatedly handles a new event or the next timer deadline and calls service. The ON state lasts one second; every completed flash enters GAP, even if the queue is empty at that instant. An arrival during that gap must wait for it to expire. Otherwise turning the light off and immediately treating the device as idle could allow a new flash too soon. Once a gap has expired, a queued event starts a new flash; if no work is pending the device remains idle. Removing a pending event only when a flash starts gives one completed flash per consumed event.

An interrupt can arrive during the main program's decrement. Without a critical section, its increment can be overwritten by a race condition. Merely declaring the counter volatile, as in volatile-qualified objects in C, does not make the decrement an atomic operation. Short interrupt masking, or an appropriate atomic operation, protects it; interrupts must remain enabled during the one-second intervals so that detections continue to be recorded.

A calibrated busy-wait loop is simple, but occupies the CPU and its duration depends on instruction timing, compiler transformations and time spent in interrupts. Polling a hardware timer avoids calibration dependence but still consumes CPU while polling. A timer interrupt or timer comparison deadline permits useful work or safe sleeping between transitions and is preferable for precise timing. If sleeping, the test for queued work and entry into sleep must avoid a lost wake-up. By the modulo-counter elapsed-time identity, a wrapping digital counter is usable if elapsed-time subtraction is unsigned and the real observation interval is less than its modulus; a wide enough counter or suitable bounded intervals make this explicit. Software dispatch adds bounded latency, so the specification is achieved to timer/interrupt-service resolution; stricter physical pulse-width requirements call for hardware output comparison or a suitably prioritised timer handler.

Finally, the device register is only a single-bit event latch. Two physical detections before acknowledgement may coalesce, so no software can recover their multiplicity from that bit alone. The event counter must also have enough capacity for the allowed backlog; indefinitely many arrivals faster than one flash every two seconds cannot be guaranteed with finite storage. These are explicit hardware/rate assumptions, not missing input files. Keeping the handler short minimises the rearming interval but cannot abolish those limitations.

Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Digital systems, linear algebra, introduction to formal proof / 3 / b / Solution 2026-10-25

Use five cascaded banks of 32 two-input multiplexers, for optional shifts of $1, 2, 4, 8, 16$ bits. The original circuit schematic below shows one bank per shift-amount bit; this is a left bit shift with zero fill, not a bit rotation.

Figure 1.
Five optional power-of-two shifts implement every 32-bit logical left-shift distance
. **Details**.

s = \sum_{j = 0}^{4} s_{j} 2^{j}

, stage

j

selects either its unchanged input or that input shifted left by

2^{j}

. For bit position

i

, the shifted candidate comes from position

i - 2^{j}

when it exists, and otherwise from zero. Composing the chosen stages shifts by the sum of their distances, so each amount from

0

31

is represented exactly by its five binary control bits. There are

5 \times 32 = 160

one-bit multiplexers, with five multiplexer delays along a bit path.

A one-bit multiplexer with selector

s

, unselected input

u

and selected input

v

has output $(\neg s \land u) \lor (s \land v)$ . It can be made from one NOT gate, two AND gates and an OR gate; a bank can share the selector inversion. The two possible selector values directly verify its behaviour.

Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Functional programming, design and analysis of algorithms / 5 / d / iii / Solution 2026-10-25

Restrict the unknown function to the

n

possibilities

f^{(i)} (x) = 1

x_{i} = 1

, and

2

otherwise. Each has exactly one essential variable, even if the allowed alphabet has more than two values. Every oracle answer in this restricted family is one bit.

A correct adaptive deterministic algorithm must distinguish all

n

possibilities. A binary decision tree of depth

q

has at most

2^{q}

leaves, so

2^{q} \geq n

. Therefore $q \geq ⌈ lo g_{2} n ⌉ = Ω (lo g n)$ . Restricting the answer family is essential to the argument: unrestricted integer-valued answers need not have binary branching. Combined with part ii, this gives optimal logarithmic query complexity for fixed

d

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 / b / Solution 2026-10-25

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.

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 / e / Solution 2026-10-25

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.

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 / f / Solution 2026-10-25

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 cycle

0000 \to 1111 \to 1110 \to \dots \to 0010 \to 0001 \to 0000,

with 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 GHz /16 = 62.5 MHz$ , with wave period

16 ns

and high and low intervals of

8 ns

. Its initial phase depends on the starting state. The figure chooses initial state

0000

and a first input rising clock edge at

1 ns

. Actual ripple propagation shifts edge times and creates intermediate transient codes; no device delays were supplied, so the waveform describes settled ideal logic.

Figure 1.
Complete descending four-bit counter cycle and ideal fourth-stage waveform
. **Details**.

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 / 2 / c / Solution 2026-10-25

A register file with 256 entries needs

lo g_{2} 256 = 8

bits per register index. Under the intended assumption that eight times as many instructions are obtained by expanding the primary opcode field, its width grows from six to

6 + lo g_{2} 8 = 9

bits. Thus opcode: 9 bits; rs, rt and rd: 8 bits each.

These four fields alone require

9 + 3 (8) = 33

bits, already exceeding a 32-bit instruction encoding. Retaining the five-bit shift amount and six-bit function field of a MIPS R-type instruction gives 44 bits. The processor's data word need not become wider merely because it has more registers.

The opcode conclusion is conditional: MIPS also uses secondary function fields, so an eightfold increase in the number of semantic operations does not by itself force a nine-bit primary opcode. That is the straightforward field-expansion interpretation of this exercise.

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 / 2 / d / Solution 2026-10-25

On the same primary-opcode expansion interpretation, opcode: 9 bits; each register field: 8 bits. The printed rd is a naming slip: a conventional MIPS I-type instruction has fields rs and rt, with the latter sometimes serving as the destination. There is no separate rd field.

Keeping the original 16-bit immediate requires

9 + 8 + 8 + 16 = 41

bits per instruction. If the instruction encoding were held at 32 bits, only seven bits would remain for the immediate, reducing immediate arithmetic and addressing ranges. A uniform encoding for both enlarged formats would have to accommodate the longer R-type case too; any padding or revised format policy must be specified separately. Register count and instruction width do not determine data-word width.

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 / 2 / e / Solution 2026-10-25

More processor registers can reduce register spills and the associated loads and stores. A richer instruction set may also replace several old machine instructions by one new operation. Both effects can decrease the number of instructions in a compiled program, although a particular program might obtain no benefit.

Wider instruction encodings increase the bytes per instruction. Consequently the total machine-code size can increase or decrease: approximately, it is instruction count times average encoded instruction width, with alignment and padding also relevant. There is no universal net direction without the program and revised encoding. The length of assembly language source text is a separate matter and is not determined by instruction bit widths.

Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Digital systems, linear algebra, introduction to formal proof / 1 / a / Solution 2026-10-25

For bits

a, b

, use two negation logic gates and two AND gates:

L = (\neg a) \land b, G = a \land (\neg b) .

The two unequal bit pairs activate their respective output; the equal pairs activate neither. In particular, a digital comparator never produces

L = G = 1

Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Digital systems, linear algebra, introduction to formal proof / 1 / b / Solution 2026-10-25

Split each input into its more and less significant

n

-bit halves:

a = 2^{n} a_{H} + a_{L}

and

b = 2^{n} b_{H} + b_{L}

. Let the two digital comparators produce

(L_{H}, G_{H})

and

(L_{L}, G_{L})

. The more significant halves are equal exactly when

E_{H} = \neg (L_{H} \lor G_{H})

. The comparator composition is therefore

L = L_{H} \lor (E_{H} \land L_{L}), G = G_{H} \lor (E_{H} \land G_{L}) .

Implement

E_{H}

with a logical disjunction followed by a negation, then use two AND gates and two more logical disjunction logic gates. If

a_{H} \neq = b_{H}

, the difference

2^{n} (a_{H} - b_{H})

has magnitude at least

2^{n}

, whereas

∣ a_{L} - b_{L} ∣ \leq 2^{n} - 1

; hence the more significant comparison decides the result. If

a_{H} = b_{H}

, the lower comparison decides it. This proves correctness in every case using a constant number of extra logic gates.

Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Digital systems, linear algebra, introduction to formal proof / 1 / c / Solution 2026-10-25

Apply comparator composition recursively in a balanced binary tree, with one-bit digital comparators at its leaves. For a power of two

n

, the circuit size and circuit depth satisfy

S (n) = 2 S (n /2) + O (1), D (n) = D (n /2) + O (1) .

There are

n

leaves and

n - 1

internal nodes, so the circuit size is $O (n)$ and the combinational delay is $O (lo g n)$ . Here each fixed-fan-in logic gate has bounded delay. For arbitrary

n

, pad both inputs with leading zero bits to the next power of two, which is less than

2 n

; this preserves their unsigned interpretation and both bounds.

Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Digital systems, linear algebra, introduction to formal proof / 1 / d / Solution 2026-10-25

Use a hierarchical leading-zero counter. A block of

2^{j}

bits returns a zero flag

z

and

j

low count bits

r

: its count leading zeros result is the concatenation

(z, r)

. Thus

z = 1

means that the block is entirely zero and

r = 0

; otherwise

z = 0

and

r

is its leading-zero count. A one-bit block needs just

z = \neg x

and no low count bits.

For a block of

n = 2^{k}

bits, run two such Boolean circuits on the upper and lower halves in parallel. Write their flags as

z_{H}, z_{L}

and their

k - 1

low count bits as

h_{i}, ℓ_{i}

. Set

z = z_{H} \land z_{L}, r_{k - 1} = z_{H} \land \neg z_{L}, r_{i} = (\neg z_{H} \land h_{i}) \lor (z_{H} \land ℓ_{i}) (0 \leq i < k - 1) .

The last expression is a two-input multiplexer. When the upper half is nonzero, its count is already the answer and

r_{k - 1} = 0

. When only the upper half is zero,

r_{k - 1} = 1

supplies the contribution

n /2

while the multiplexers supply the lower half's count. When both halves are zero, the answer is

(1, 0, \dots, 0)

, representing

n

. This special encoding avoids an adder on the critical path.

Each node adds constant circuit depth, even though it uses

O (k)

logic gates for its parallel multiplexers. Hence

D (2^{k}) = D (2^{k - 1}) + O (1) = O (k), S (2^{k}) = 2 S (2^{k - 1}) + O (k) = O (2^{k}) .

(2)

Indeed the internal-node work is bounded by a constant times

\sum_{j = 1}^{k} (n / 2^{j}) j < 2 n

, and the

n

leaves add

O (n)

. Delay is $O (lo g n)$ and size is $O (n)$ , counting fixed-fan-in logic gates and the usual wire fan-out model.

Figure 1.
Leading-zero summaries combine in parallel: the input $00000101$ gives the four-bit count $0101$
. Internal nodes display their block length and encoded leading-zero count; leaves display the one-bit count. A count's first bit is the shared all-zero flag. The highlighted branch supplies the low count at the root. **Details**.

Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Digital systems, linear algebra, introduction to formal proof / 2 / a / Solution 2026-10-25

Use the AAPCS32 convention: r0 holds the input address, r1 the length, and r0 receives the result. The following Thumb instruction set assembly language uses only scratch processor registers, so no callee-saved registers need saving. Assume the array is valid, halfword-aligned, and has nonnegative length; for the mathematical sum assume it fits a signed 32-bit two's complement integer.

.syntax unified
.thumb
.thumb_func
sum16:
    movs r2, #0             @ accumulated sum
    cmp  r1, #0
    ble  .Ldone             @ empty array; also returns 0 if n < 0
.Lloop:
    movs r3, #0             @ Thumb signed load needs a register offset
    ldrsh r3, [r0, r3]      @ signed halfword at a; offset read before r3 changes
    adds r2, r2, r3         @ include this signed value
    adds r0, r0, #2         @ advance by one short, not one byte
    subs r1, r1, #1         @ one fewer element remains
    bne  .Lloop
.Ldone:
    movs r0, r2             @ result register
    bx   lr                 @ leaf routine: lr was not overwritten

After

j

iterations, the loop invariant is that r2 contains the first

j

elements' sum, r0 points to element

j

, and r1 is

n - j

. The sign extension in ldrsh supplies the correct signed addend. One iteration preserves this loop invariant, and the decreasing remaining length proves algorithm termination. For the seven-element calls, the sum lies between

- 229376

and

229369

, so it fits. For longer arrays that overflow, these instructions compute the sum modulo

2^{32}

; that is not a claim about defined signed C programming language overflow behavior. The operand forms are those of the paper's reference sheet.^[ref]

Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Digital systems, linear algebra, introduction to formal proof / 2 / b / Solution 2026-10-25