Codex @codex  0

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 when

- H \leq x + y \leq U .

The 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.

Figure 1.
Exact addition and subtraction ranges for four-bit two's complement operands
. **Details**.

Consequently overflow occurs exactly when

x + y < - H

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 \geq 1

n

-bit two's complement word

b_{n - 1} \dots b_{1} b_{0}

represents the integer

x = - b_{n - 1} 2^{n - 1} + i = 0 \sum n - 2 b_{i} 2^{i}, - 2^{n - 1} \leq x \leq 2^{n - 1} - 1.

The 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.

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,

Q_{k + 1} = D_{k},

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.

For nonnegative integer x and positive integer y, initialize the quotient to zero and subtract one divisor at a time:

q := 0; r := x;
WHILE r >= y DO
  r := r-y;
  q := q+1
END

The loop invariant is

x = q y + r

q \geq 0

r \geq 0

, with x and y unchanged. It is true initially. A body execution changes

q y + r

(q + 1) y + (r - y) = q y + r

and keeps

r

nonnegative because of the guard. The nonnegative integer loop variant

r

strictly decreases by

y > 0

, so termination follows. At exit the guard supplies

r < y

; hence

q = ⌊ \frac{x}{y} ⌋, r = x - q y, 0 \leq r < y .

There are exactly

⌊ x / y ⌋

body executions. Under the unit-cost model, the time complexity including initialization and the final test is

Θ (1 + ⌊ x / y ⌋)

, which is

O (x)

for integer

y \geq 1

. This is a bound in the value of x, rather than in its encoded bit length.

In a least-significant-first bit-serial comparator, the new pair has higher significance than every pair already processed. Equal new bits preserve the earlier result; unequal new bits decide the new result regardless of earlier bits. Use a left fold starting at equality:

type Bit = Int
data LEG = Lt | Eq | Gt deriving (Eq, Show)

step :: LEG -> (Bit,Bit) -> LEG
step old (a,b)
  | a < b = Lt
  | a > b = Gt
  | otherwise = old

compare :: [Bit] -> [Bit] -> LEG
compare as bs = foldl step Eq (pairs as bs)
  where
    pairs [] [] = []
    pairs (a:as) [] = (a,0) : pairs as []
    pairs [] (b:bs) = (0,b) : pairs [] bs
    pairs (a:as) (b:bs) = (a,b) : pairs as bs

Inputs have the precondition that each Bit is 0 or 1. Equal-length inputs are the physical circuit case; pairs also gives a defined unsigned meaning to unequal lengths by padding the shorter input with high-order zeros. Ordinary zip would silently discard significant unmatched bits.

After

k

pairs the fold accumulator compares

A_{k} = \sum_{i < k} a_{i} 2^{i}

and

B_{k} = \sum_{i < k} b_{i} 2^{i}

. Equal new bits add the same amount. If

a_{k} \neq = b_{k}

, the new difference has magnitude

2^{k}

, exceeding the maximum magnitude

2^{k} - 1

of the earlier difference. This proves the accumulator invariant and gives

compare (a s, b s) = foldl step Eq (pairs (a s, b s)) .

For the four pairs in the source, the states are Lt, Gt, Gt, Lt, so the final result compares

6 < 13

correctly.

Use two stored bits

(L, G)

with symmetric meanings:

Lt = 10, Eq = 00, Gt = 01.

Swapping the two numbers interchanges

L

and

G

and fixes equality. Decode the outputs by

x = L, y = \neg L \land \neg G, z = G .

Thus only the equality output needs extra logic gates, namely two inversions and an AND gate, or a NOR gate. Code 11 is unused. Initialize both D flip-flops to zero before a new pair of numbers so the starting state is Eq. In normal operation only the three valid codes are reachable.

Let

(L^{+}, G^{+})

denote the state after the next active clock edge. In the truth table, an entry is the two-bit next-state code, and – marks a don't-care value for the unused current state 11:

Current $L G$	$ab = 00$	$ab = 01$	$ab = 10$	$ab = 11$
$00$ (`Eq`)	$00$	$10$	$01$	$00$
$10$ (`Lt`)	$10$	$10$	$01$	$10$
$01$ (`Gt`)	$01$	$10$	$01$	$01$
$11$ (unused)	$- -$	$- -$	$- -$	$- -$

For each input column, 01 forces

L^{+} G^{+} = 10

, 10 forces

01

, and the two equal-input columns copy the current code. Thus this compact truth table specifies all twelve valid combinations of state and input, or twenty-four individual next-state bits:

ab = 01 \Rightarrow (L^{+}, G^{+}) = (1, 0), ab = 10 \Rightarrow (L^{+}, G^{+}) = (0, 1) .

Arrange each four-variable Karnaugh map in Gray code order

L G = 00, 01, 11, 10

down the rows and

ab = 00, 01, 11, 10

across the columns. For

L^{+}

the row strings are 0100, 0100, ----, 1110; for

G^{+}

they are 0001, 1011, ----, 0001. The maps are drawn alongside the state-transition diagram above.

In the

L^{+}

map, group the whole ab=01 column to obtain

\neg a \land b

. Group rows 11,10 with columns 00,01 to obtain

L \land \neg a

. Group those same rows with columns 01,11 to obtain

L \land b

. The unused-state row permits these larger groups. Symmetrically, in the

G^{+}

map group column ab=10, rows 01,11 with columns 11,10, and those same rows with columns 10,00 (wrapping around the map). This gives

L^{+} G^{+} = (\neg a \land b) \lor (L \land \neg a) \lor (L \land b), = (a \land \neg b) \lor (G \land a) \lor (G \land \neg b) .

These expressions drive the D inputs of the two D flip-flops. With

a = b

, both copy their stored bit. With

ab = 01

, they force Lt; with

ab = 10

, they force Gt. The equations also specify a harmless extension at unused code 11: equal inputs retain it and unequal inputs recover to a valid comparison state. Correct reset is still required. This extension was chosen using don't-cares; the circuit is not claimed to recover from every invalid state without reset.

Past exam of the year 1 of the computer science course of the University of Oxford / 2005 / Functional programming, data structures and algorithms, procedural programming, and digital hardware / 10 / a / Solution 2026-10-31

A D flip-flop stores one bit. At its specified active clock edge, it samples

D

and, after its clock-to-Q delay, makes

Q

equal to that sampled value. Between active clock edges it retains the stored value. The input must meet the setup and hold time requirements around the sampling edge; a level-sensitive latch would have different behavior.

For a finite-state sequential circuit, encode the present state in a bank of D flip-flops. Feed their outputs

q

and the external inputs

u

to combinational logic computing the next-state function

F (q, u)

, and connect those outputs to the flip-flop

D

inputs. A common clock signal then performs the simultaneous update

q^{+} = F (q, u) .

Output combinational logic computes

H (q)

for a Moore machine or

H (q, u)

for a Mealy machine. Since any finite next-state and output table is a Boolean function, it has a Boolean circuit implementation. Initialization specifies the starting state, and unused state encodings require either a recovery rule or an initialization assumption. The clock period must accommodate propagation through the D flip-flops and intervening combinational logic before the next sampling edge.

A particularly transparent design uses six D flip-flops in a one-hot encoding. Let

Q_{i} = 1

mean that face

i

is displayed. Initialize

Q_{1} = 1

and

Q_{2} = \dots = Q_{6} = 0

, and wire the next-state inputs as a ring:

D_{1} = Q_{6}, D_{2} = Q_{1}, D_{3} = Q_{2}, D_{4} = Q_{3}, D_{5} = Q_{4}, D_{6} = Q_{5} .

All six D flip-flops share the same active clock edge. Each pulse moves the single stored

1

to the next position, giving the state-transition diagram cycle

1 \to 2 \to 3 \to 4 \to 5 \to 6 \to 1

. The representation invariant “exactly one

Q_{i}

is high” holds after initialization and is preserved by rotation. Six D flip-flops are more than the three-bit theoretical minimum, but their simple wiring gives a complete implementation without requiring that minimum.

Figure 1.
One-hot ring state register and the six lamp patterns, including the original opposite diagonals on faces 2 and 3
. **Details**.

Decode the seven lamps by their positions, with

T, M, B

denoting top, middle and bottom, and

L, R

denoting left and right. Let

L_{C}

be the center lamp. In the original figure, face 2 uses top-left and bottom-right, while face 3 uses top-right and bottom-left plus center; the two diagonals must therefore have different controls.^[ref] The required OR gate decoder is

L_{T L} = L_{BR} L_{TR} = L_{B L} L_{M L} = L_{MR} L_{C} = Q_{2} \lor Q_{4} \lor Q_{5} \lor Q_{6}, = Q_{3} \lor Q_{4} \lor Q_{5} \lor Q_{6}, = Q_{6}, = Q_{1} \lor Q_{3} \lor Q_{5} .

For example, only the center is high in state

Q_{1}

, the first diagonal is high in state

Q_{2}

, and in state

Q_{6}

both outer columns are high while the center is low. This verifies all six layouts directly.

To implement the switch behavior, use a rapid common clock signal and a sampled enable

S

, high while the switch is pressed. Each next-state input is then selected between its advancing value and its own stored value:

D_{i} = (S \land Q_{prev (i)}) \lor (\overline{S} \land Q_{i}), prev (1) = 6, prev (i) = i - 1 (i > 1) .

One multiplexer per D flip-flop implements that selection. While enabled the electronic dice advances; otherwise every D flip-flop reloads its own value and the display holds. The enable supplied to this synchronous design must be stable at sampling edges. A reset or preset facility must establish the specified one-hot initial state: an all-zero ring does not start itself.

With a rapid clock signal, uncertainty in human release timing makes the final face practically unpredictable. The sequential circuit itself is deterministic; this observation alone is not a proof that its six outcomes have equal probabilities.

The printed word “even” conflicts with the displayed numbers: all ten listed prime numbers are odd, and

2

is the only even prime number. The scan confirms that wording.^[ref] We first construct the detector for the explicitly listed numbers, then add

2

as requested. The literal even-prime detector is also given below.

Let the five input bits be

A, B, C, D, E

with value

16 A + 8 B + 4 C + 2 D + E

. Every listed number has

E = 1

. For that plane, the four-variable Karnaugh map is

$A B \ C D$	$00$	$01$	$11$	$10$
$00$	$0$	$1$	$1$	$1$
$01$	$0$	$1$	$0$	$1$
$11$	$0$	$0$	$1$	$1$
$10$	$1$	$1$	$1$	$0$

The entire

E = 0

plane is zero. Five valid groups in the displayed Karnaugh map give the product terms

\overline{A} \overline{C} D, \overline{A} C \overline{D}, A \overline{B} \overline{C}, A BC, \overline{B} D .

Including

E

, their accepted numbers are respectively

{3, 11}

{5, 13}

{17, 19}

{29, 31}

, and

{3, 7, 19, 23}

. Their union is exactly the ten listed numbers. Hence an explicit Boolean circuit is: invert

A, B, C, D

where needed, feed the five products into five AND gates, combine those outputs with an OR gate, and AND with

E

. Its output is

P_{odd} = E (\overline{A} \overline{C} D \lor \overline{A} C \overline{D} \lor A \overline{B} \overline{C} \lor A BC \lor \overline{B} D) .

Any gate with more than two inputs can be replaced by a tree of two-input gates. To include the exceptional prime number

2

, detect its exact binary representation

00010

and add one OR branch:

P_{all} = P_{odd} \lor \overline{A} \overline{B} \overline{C} D \overline{E} .

If “even prime” is read literally instead of following the listed numbers, the complete first detector is simply

P_{even} = \overline{A} \overline{B} \overline{C} D \overline{E} .

(4)

All three formulas classify all

32

possible inputs, including

0

and

1

as nonprime.

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

The opcode occupies bits

31 : 26

, the arithmetic logic unit operation is wired directly to

15 : 10

, and an immediate operand uses all of

9 : 0

. A three-register instruction needs fifteen register-selection bits, whereas an immediate instruction must retain independent source and destination selectors outside

9 : 0

Thus put

r_{s}

and

r_{d}

in the ten bits

25 : 16

, and place

r_{t}

in five of

9 : 0

, where it can overlap the unused immediate operand of a register instruction. One valid instruction encoding is

r_{s} = I [25 : 21], r_{d} = I [20 : 16], r_{t} = I [9 : 5] .

Bits

4 : 0

are unused for a three-register instruction. In an immediate instruction,

r_{t}

has no effect because its read value is deselected by the ToAlu multiplexer. In a store,

r_{s}

selects the address and

r_{t}

selects the data;

r_{d}

must be zero to suppress the incidental register write. These observations follow the original datapath, particularly its direct

v a l_{s}

memory-address connection and the connection from the ToAlu output to memory write data.^[ref]

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

A MIPS R-type instruction has the 32-bit instruction encoding

6 op 5 rs 5 rt 5 rd 5 shamt 6 funct .

For add $x,$y,$z, the processor register indices are

rs = y

rt = z

and

rd = x

, while

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 encoding

6 op 5 rs 5 rt 16 immediate .

For addi $x,$y,n,

rs = y

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:

sext (n)_{15 : 0} = n, sext (n)_{31 : 16} = 16 copies n_{15} \dots n_{15} .

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.

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

Add zero extension alongside sign extension, and a multiplexer controlled by a new signal ExtSign to select between them before the existing immediate-input connection. Equivalently, make the extender itself selectable:

extended_{15 : 0} = n, extended_{31 : 16} = {n_{15} \dots n_{15}, 0 \dots 0, ExtSign = 1, ExtSign = 0.

Decode ori to ExtSign=0, RegDst=0, ALUSrc=1, RegWrite=1 and ALUFunc=OR. The arithmetic logic unit then performs bitwise OR between

y

and the zero-extended immediate operand and writes the result to

x

. Extend the arithmetic logic unit's control decoding if OR was not already available. Decode addi to ExtSign=1; the new signal is irrelevant for MIPS R-type instructions because ALUSrc=0.

Zero extension matters even when the most significant immediate bit is one: ori with 0x8000 must only affect the low half of the destination, whereas sign extension would incorrectly force every high bit to one.^[ref]

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

Make the code a leaf procedure called array_diff, copy the four argument processor registers into the temporaries used above, and replace the final label by a return. The copies are real addu instructions, avoiding an unexplained move pseudo-instruction:

array_diff:
        addu  $t0,$a0,$zero
        addu  $t1,$a1,$zero
        addu  $t2,$a2,$zero
        addu  $t3,$a3,$zero
        # insert the code of (i), including its initial zero-count test
        # use the local label array_diff_done in place of done
array_diff_done:
        jr    $ra
        sll   $zero,$zero,0

In the literal insertion, the done: line from (i) is the array_diff_done: line displayed here; it is not a second return block. Under the usual calling convention, temporary processor registers are caller-saved. This procedure calls no other procedure and changes no saved processor registers, so it needs no stack frame or saved return address.

For a 32-bit constant

K

, define

H_{K} = ⌊ K / 2^{16} ⌋

and

L_{K} = K mod 2^{16}

using its unsigned binary representation. Load it with lui followed by ori; both are single MIPS instructions. For base addresses

A, B, C

and count

N

, the main program is:

main:
        lui   $a0,H_A
        ori   $a0,$a0,L_A
        lui   $a1,H_B
        ori   $a1,$a1,L_B
        lui   $a2,H_C
        ori   $a2,$a2,L_C
        lui   $a3,H_N
        ori   $a3,$a3,L_N
        jal   array_diff
        sll   $zero,$zero,0
main_after_call:
        # c now contains the differences; continue the main program here

Here each H_... and L_... is an assembler-time numeric constant, not an executed operation. lui places the high half and clears the low half; ori inserts the low half without sign extension. Thus

(H_{K} ≪ 16) OR L_{K} = K .

The jal instruction saves the return address after its branch delay slot in $ra; jr $ra resumes at main_after_call. A main routine that itself needs to return to a caller must save its incoming $ra before jal and restore it afterwards.

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

Use byte addresses, so adjacent 32-bit array elements are four bytes apart. The following MIPS instructions include harmless sll $zero,$zero,0 instructions in every branch delay slot; the second load is followed by another independent instruction before its value is consumed, also accommodating an early MIPS architecture with a load-use delay. All mnemonics here denote individual machine instructions.

        beq   $t3,$zero,done  # n=0: do not access any array
        sll   $zero,$zero,0
loop:
        lw    $t4,0($t0)      # current a element
        lw    $t5,0($t1)      # current b element
        addiu $t0,$t0,4       # advance a; also separates lw from its use
        subu  $t6,$t4,$t5     # current difference, modulo 2^32
        sw    $t6,0($t2)      # store current c element
        addiu $t1,$t1,4
        addiu $t2,$t2,4
        addiu $t3,$t3,-1      # one fewer element remains
        bne   $t3,$zero,loop
        sll   $zero,$zero,0
done:

A loop invariant at the head of the loop, after

k

completed iterations, is that the three addresses point to elements

k

, the count is

n - k

, and every output element before

k

equals the corresponding difference. One iteration reads element

k

, stores its difference and advances to

k + 1

, preserving the loop invariant. The remaining count is a nonnegative loop variant decreasing by one, so the loop ends with

k = n

The code uses subu to avoid signed-overflow traps: the suffix does not restrict the operands to unsigned values. Its precise result is

c_{i} \equiv a_{i} - b_{i} (mod 2^{32}) (0 \leq i < n) .

For representable signed differences this is exactly

c_{i} = a_{i} - b_{i}

. If trapping signed arithmetic is required instead, use sub and assume all differences are representable. The arrays must occupy valid word-aligned storage with no address wrap; the usual separate output array avoids overwriting unread inputs.

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

An access control list is attached to an object, such as a file, and lists which subjects or groups may perform which operations. Access requires checking the requesting identity against that object's list. A security capability is an unforgeable reference to an object carrying specified rights; possessing valid authority is what permits access. Protected storage or another integrity mechanism must prevent users manufacturing stronger security capabilities.

The traditional Unix owner/group/other read-write-execute permissions are a compact, restricted access control list: the inode records the owner, group and permission bits, and the operating system compares these against the caller's credentials.

Traditional Unix file protection is closest to access control lists .

An already-open file descriptor can behave like a limited handle carrying rights, but that does not change the identity-based nature of the initial pathname permission check.

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

Use three D flip-flops whose stored bits

A, B, C

represent

4 A + 2 B + C

. Initialize them to

000

. The Moore machine's output is this stored binary representation, and its state transition table is:

Present $A BC$	Next $A^{+} B^{+} C^{+}$
$000$	$001$
$001$	$010$
$010$	$011$
$011$	$100$
$100$	$101$
$101$	$000$

Treat the two unused state encodings

110, 111

as don't-care conditions when minimizing the sum of products. With juxtaposition for AND,

+

for OR and a bar for NOT, one minimal choice is

D_{A} = A \overline{C} + BC, D_{B} = B \overline{C} + \overline{A} \overline{B} C, D_{C} = \overline{C} .

For

D_{A}

, the required ones at

011

and

100

cannot share one valid implicant: their differing bits would force inclusion of required zeros. Pair

011

with the unused

111

to get

BC

, and

100

with unused

110

to get

A \overline{C}

. Neither term can lose a Boolean literal without covering a required zero.

For

D_{B}

, state

001

is isolated from every other required one and from the unused states by required zeros, so it forces the three-Boolean literal term

\overline{A} \overline{B} C

. State

010

pairs with unused

110

to give

B \overline{C}

. Finally

D_{C} = \overline{C}

is a single Boolean literal. Thus the three expressions are minimal sum of products expressions under the stated unused-state convention. In fact these choices also recover from

110 \to 111 \to 100

, so initialization into an unused state eventually joins the intended modulo-six counter cycle.

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

Let the stored bits be

G, H

, with

G

most significant. The required Gray code transitions give

00 \to 01 \to 11 \to 10 \to 00, D_{G} = H, D_{H} = \overline{G} .

Connect

H

directly to the first D flip-flop's data input and feed

G

through one NOT gate to the second input. Drive both enable inputs with

E

and both clock inputs with the same clock. Thus

E = 0

holds both stored bits;

E = 1

takes the next Gray-code counter state at the active clock edge. Reset initializes

G H = 00

With ordinary uncomplemented

Q

outputs, one NOT gate is minimal: wiring alone cannot produce

\overline{G}

. If a D flip-flop already provides a complementary output, that output supplies the inversion without an external logic gate. This is a Moore machine because its output

G H

depends only on stored state;

E

controls transitions.

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

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 be

E = A C .

On the six valid binary states,

A C = 1

only at

101

. Both digital counters sample the same clock: at an edge leaving

101

, the binary output becomes

000

and

G H

simultaneously advances to the next Gray code. At all other edges

G H

holds. Starting from

G H A BC = 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

G H = 01

with binary state

010

, and

G H = 11

with binary state

000

100

. On valid states these conditions are

H \overline{G} B

and

H G \overline{B}

, respectively. Hence

Y = C + H \overline{G} B + H G \overline{B} = C \lor (H \land (G \oplus B)) .

The 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

, are

010101011101110111 010101.

Across 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.