Past exam of the year 1 of the computer science course of the University of Oxford / 2003 / Functional programming, data structures and algorithms, procedural programming, and digital hardware / 9

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\ne 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 givesFor 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:Swapping the two numbers interchanges $L$ and $G$ and fixes equality. Decode the outputs byThus 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.

The finite-state machine retains its state on input 00 or 11, moves to Lt on 01, and moves to Gt on 10. Here each input label is the pair ab, not a pair of outputs. The following state-transition diagram shows every valid-state transition; a diagonal input is stronger than all previous comparison history because it arrives at a more significant position.

Equivalently the complete transition rule isThe state-transition diagram starts at Eq, representing the comparison of two empty, hence zero-valued, bit strings.

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:

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:

Arrange each four-variable Karnaugh map in Gray code order $LG=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\wedge b$. Group rows 11,10 with columns 00,01 to obtain $L\wedge \neg a$. Group those same rows with columns 01,11 to obtain $L\wedge 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 givesThese 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.