Sum of digits processor

Assumption: n is an unsigned 16-bit integer (0 to 65535). The decimal digits are extracted with "mod 10" and "div 10", implemented by repeated subtraction (there is no hardware divider).

Step 1: Function

 SumDigits(n):
   sum = 0
   while (n > 0):
       q = 0; r = n
       while (r >= 10): r = r - 10; q = q + 1    // q = n div 10, r = n mod 10
       sum = sum + r
       n = q
   output sum

Step 2: FSMD

 S0 -> S1 -(N>0)-> S2 -> S3 -(R>=10, loop)-> S3
        |                 |(R<10)
       (N=0)              v
        v               S4 -> S1
       S5 -> S0

Step 3: Datapath

 n -> [N] <- mux(n, Q) ;  [N > 0] comparator -> gtz
 [R] <- mux(N, R-10) <- subtractor(R, const 10) ; [R >= 10] -> ge10
 [Q] <- mux(0, Q+1) <- incrementer
 [SUM] <- mux(0, SUM+R) <- adder
 SUM -> out

Components: registers N, R, Q, SUM; a subtractor (R - 10), an incrementer, an adder, comparators (N > 0, R >= 10), and muxes for N, R, Q and SUM.

Controller

Six-state FSM, 3-bit state register. Inputs: start, gtz, ge10. Outputs: N_ld, R_ld/R_sel, Q_clr/Q_inc, SUM_clr/SUM_ld, done.

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

Trace n = 345: (Q, R) = (34, 5): sum 5; n = 34 -> (3, 4): sum 9; n = 3 -> (0, 3): sum 12; n = 0 -> output 12.