--- title: "Dual-purpose processor: median and variance" subject: "Embedded System" chapter: 2 key: "semester_6/embedded_system:dual-purpose-median-variance" source: https://www.bctengineer.com/q/semester_6/embedded_system/dual-purpose-median-variance site: BCT Engineering --- # Dual-purpose processor: median and variance Embedded System · Chapter 2: Hardware Design Issues - Asked in: 2070 Magh, 8 marks - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_6/embedded_system/dual-purpose-median-variance - Whole chapter: https://www.bctengineer.com/md/semester_6/embedded_system/chapter-2 ## Question Design a dual-purpose processor that calculates the median and variance of 5 numbers entered by the user, by showing the algorithm, FSMD, FSM, data-path and controller design. ## Short answer The processor inputs five numbers, sorts them with bubble sort, median is M[2]; mean = sum/5 by repeated subtraction; variance = Σ(xi-mean)²/5. Datapath includes register file, adder, subtractor, multiplier, counters; controller is a 17-state FSM. ## Answer **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 ```text 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 | State | Condition | Actions (RTL) | Next | |---|---|---|---| | S0 | start = 0 | wait | S0 | | S0 | start = 1 | SUM = 0, I = 0 | S1 | | S1 | I < 5 | none | S2 | | S1 | I >= 5 | P = 0 | S4 | | S2 | enter = 0 | wait | S2 | | S2 | enter = 1 | none | S3 | | S3 | always | M[I] = din, SUM = SUM + din, I = I + 1 | S1 | | S4 | always | P = 0 (pass count) | S5 | | S5 | P < 4 | none | S6 | | S5 | P >= 4 | none | S10 | | S6 | always | J = 0 | S7 | | S7 | J < 4 - P | none | S8 | | S7 | J >= 4 - P | P = P + 1 | S5 | | S8 | M[J] > M[J+1] | none | S9 | | S8 | else | J = J + 1 | S7 | | S9 | always | swap M[J], M[J+1] (via T); J = J + 1 | S7 | | S10 | always | MED = M[2]; Q = 0; R = SUM | S11 | | S11 | R >= 5 | R = R - 5; Q = Q + 1 | S11 | | S11 | R < 5 | MEAN = Q; I = 0; ACC = 0 | S12 | | S12 | I < 5 | none | S13 | | S12 | I >= 5 | Q = 0; R = ACC | S15 | | S13 | always | D = M[I] - MEAN (signed) | S14 | | S14 | always | ACC = ACC + D x D; I = I + 1 | S12 | | S15 | R >= 5 | R = R - 5; Q = Q + 1 | S15 | | S15 | R < 5 | VAR = Q | S16 | | S16 | always | output MED, VAR; done = 1 | S0 | #### FSM (control view, grouped) ```text 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 ```text 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: ```text 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). ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. How is the median obtained? A. Add all five and divide by 5 B. Take the largest number C. Sort the five numbers and take M[2] D. Take M[0] after sorting Answer: C. The middle value of the sorted list of five is the third element, M[2]. (Key point: Median) 2. What is the variance computed as? A. Sum of xi divided by 5 B. Square of the median C. Largest minus smallest D. Sum of (xi - mean)^2 divided by 5 Answer: D. Squared deviations from the mean are accumulated, then divided by 5. (Key point: Variance formula) 3. How does the processor divide by 5? A. Repeated subtraction of 5 while counting quotient Q B. A hardware divider C. Right-shift by 5 D. Table lookup Answer: A. It subtracts 5 while R >= 5 and increments Q; Q is the result. (Key point: Division by 5) 4. For inputs 3, 1, 4, 1, 5, what are median and variance (integer)? A. 4 and 3 B. 3 and 3 C. 3 and 16 D. 1 and 3 Answer: B. Sorted 1,1,3,4,5 gives median 3; mean 2; squares sum 16; 16/5 = 3. (Key point: Example) ## Related in Embedded System - [Dual-purpose processor: factorial and prime](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Adual-purpose-factorial-prime) — Embedded System, chapter 2 - [Design LCM single-purpose processor](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Aspp-lcm-datapath-controller) — Embedded System, chapter 2 - [Single-purpose processor for power](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Aspp-power) — Embedded System, chapter 2, asked 2× - [Factorial single-purpose processor](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Aspp-factorial) — Embedded System, chapter 2 - [GCD processor algorithm and VHDL](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Avhdl-gcd-processor) — Embedded System, chapter 9, asked 3× - [LCM processor algorithm and VHDL](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Avhdl-lcm-processor) — Embedded System, chapter 9, asked 2× ## Related in other subjects - [Dual processor modes in centralized SPC](https://www.bctengineer.com/question.md?key=semester_8%2Ftelecommunications%3Adual-processor-modes-spc) — Telecommunications, chapter 4, asked 4× - [SPC and dual processor architecture](https://www.bctengineer.com/question.md?key=semester_8%2Ftelecommunications%3Aspc-dual-processor) — Telecommunications, chapter 4 - [Numerical: Okumura median path loss (unity gain)](https://www.bctengineer.com/question.md?key=semester_7%2Fwireless_communication%3Aokumura-median-loss-unity-gain) — Wireless Communication, chapter 3, asked 3× - [Okumura model and median path loss numerical](https://www.bctengineer.com/question.md?key=semester_7%2Fwireless_communication%3Aokumura-model-median-path-loss) — Wireless Communication, chapter 3