Fibonacci single-purpose processor

Assumption: the processor takes an input n and outputs the first n Fibonacci numbers (0, 1, 1, 2, 3, 5, ...), one per output, with a start input and a done output.

Step 1: Function (algorithm)

 Fibonacci(n):
   a = 0; b = 1; i = 0
   while (i < n) {
       output a
       t = a + b
       a = b
       b = t
       i = i + 1
   }

Step 2: State diagram (FSMD)

   start=0 (loop)
      +---+
      v   |    start=1
    +----------+ a=0,b=1,i=0  +---------+
    | S0 wait  |------------->| S1 test |
    +----------+              +---------+
      ^                     i<n |   | i>=n
      |                         v   v
      |  done=1  +--------+  +----+ +------+
      +----------| S4 done|  | S2 |  (to S4)
                 +--------+  |out=a, t=a+b|
                             +-----+------+
                                   v
                             +-----------+
                             | S3 a=b    |
                             | b=t,i=i+1 |--> S1
                             +-----------+

Simplified state table:

Step 3: Probable datapath

        n --------------------+
                              v
  +---+   +---+   +---+    +------+  i<n (status)
  | A |   | B |   | T |    |  <   |-----------> to controller
  +-+-+   +-+-+   +-+-+    +--^---+
    |  \    |  /    ^         |
    |   +-->[ + ]----+       +-+-+
    |       adder           | I |<-[+1]
    v                       +---+
  out (a)

Components: registers A, B, T (data) and I (counter), an adder (a + b), an incrementer (i + 1), a comparator (i < n), muxes in front of A (0 or B) and B (1 or T) and output register. Control signals from the controller: load/clear A, B, T, I; mux selects; output enable. Status to controller: i < n.

Controller

A 5-state FSM (3 flip-flops, binary encoded) that generates the loads shown in the table and receives start and i<n. Example n = 5 outputs 0, 1, 1, 2, 3.