Dual-purpose processor: median and variance

Assumptions: five 8-bit unsigned integers are entered one at a time (each accompanied by an enter pulse). Median = middle value of the sorted list. Variance = Σ(xi - mean)² / 5 with integer arithmetic (mean and variance truncated). The processor sorts with bubble sort and divides by 5 using repeated subtraction.

Algorithm

 sum = 0
 for i = 0..4: wait(enter); M[i] = din; sum += din
 sort M[0..4] ascending (bubble sort)
 median = M[2]
 mean = sum / 5
 acc = 0
 for i = 0..4: d = M[i] - mean; acc += d*d
 variance = acc / 5
 output median, variance

FSMD

FSM (control view, grouped)

 Input phase : S0 -> S1 -> S2 -> S3 -> S1 ... (5 numbers)
 Sort phase  : S4 -> S5 -> S6 -> S7 -> S8 -> (S9) -> S7 ... S5
 Mean phase  : S10 -> S11 (loop)
 Var. phase  : S12 -> S13 -> S14 -> S12 ... -> S15 (loop) -> S16 -> S0

17 states need a 5-bit state register (binary) or 17 flip-flops (one-hot).

Datapath

 din -> [ Register file M0..M4 (5x8) ] <- address mux (I, J, J+1, 2)
              | read A         | read B
              v                v
        [ comparator > ]   [ subtractor M[I]-MEAN ] -> [D]
              |                         |
          (gt to FSM)                [ multiplier D x D ] -> [ adder ] -> [ACC]
 [SUM] <- adder (SUM+din)
 [Q],[R] <- subtractor R-5, incrementer Q+1 ; comparator R>=5
 [I],[J],[P] counters/comparators (I<5, P<4, J<4-P)
 outputs: MED, VAR registers

Components: a 5x8 register file with two read ports and two write ports (so the swap in S9 fits in one state; with one write port, split S9 into two states); registers sized for the worst case:

• SUM: 11 bits are enough (5 × 255 = 1275); 16 bits used.
• D: 9-bit signed, since M[I] - MEAN ranges from -255 to +255.
• ACC and R: 17 bits, since the sum of squared deviations can reach 78030 (e.g. inputs 0, 0, 0, 255, 255: 3 × 102² + 2 × 153² = 78030 > 65535).
• Q and VAR: 16 bits, since ACC / 5 can reach 15606 (Q also gives the mean, which fits in 8 bits).
• MEAN, T, MED: 8 bits; I, J, P: 3-bit counters.

Functional units: one adder, one subtractor, one 9x9 signed multiplier (product up to 65025), comparators and an incrementer.

Controller

FSM with inputs start, enter, gt, (I<5), (P<4), (J<4-P), (R>=5); outputs: register-file write/read selects, loads of all registers, ALU function selects and done. Block diagram:

 start, status flags --> +-------------+   +-----------+
 (from datapath)         | Next-state  |-->| State     |
                         | logic       |   | register  |
                         +------^------+   +-----+-----+
                                |   current state |
                                +-----------------+
                                                  v
                                           +-------------+
                                           | Output logic|--> control
                                           +-------------+    signals

Example: inputs 3, 1, 4, 1, 5 -> sum 14, sorted 1, 1, 3, 4, 5, median 3, mean 14/5 = 2 (integer), deviations of the sorted values -1, -1, 1, 2, 3, sum of squares 16, variance 16/5 = 3 (integer).