---
title: "Fibonacci single-purpose processor"
subject: "Embedded System"
chapter: 2
key: "semester_6/embedded_system:spp-fibonacci"
source: https://www.bctengineer.com/q/semester_6/embedded_system/spp-fibonacci
site: BCT Engineering
---

# Fibonacci single-purpose processor

Embedded System · Chapter 2: Hardware Design Issues

- Asked in: 2072 Asoj, 8 marks; 2075 Baisakh, 8 marks (asked 2 times)
- Video: [Designing Single Purpose Processor To Calculate GCD (HCF).](https://www.youtube.com/watch?v=Wy344fMRnOo) — AFlick
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_6/embedded_system/spp-fibonacci
- Whole chapter: https://www.bctengineer.com/md/semester_6/embedded_system/chapter-2

## Question

Design a single-purpose processor that outputs Fibonacci numbers up to 'n' places. Start with a function computing the desired result, translate it into a state diagram and sketch a probable datapath.

## Short answer

The processor initializes a=0, b=1, then loops outputting a, computing next = a+b, updating a=b, b=next until count=n. The FSMD has states wait, test, output, update. Datapath includes registers A, B, T, I, an adder for next, incrementer for count, and comparator; controller sequences loads and outputs.

## Answer

**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)
```text
 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)
```text
   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:

| State | Condition | Actions | Next |
|---|---|---|---|
| S0 (wait) | start = 0 | done = 0 | S0 |
| S0 | start = 1 | a = 0, b = 1, i = 0 | S1 |
| S1 (test) | i < n | none | S2 |
| S1 | i >= n | done = 1 | S4 |
| S2 (output) | always | out = a, valid = 1, t = a + b | S3 |
| S3 (update) | always | a = b, b = t, i = i + 1 | S1 |
| S4 (finish) | always | done = 1 | S0 |

#### Step 3: Probable datapath
```text
        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.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. In the Fibonacci algorithm, what is the update inside the loop?
   A. output a; t = a + b; a = b; b = t; i = i + 1
   B. a = a + a
   C. b = b - a
   D. i = i - 1 only
   Answer: A. Output a, compute t = a + b, shift a and b, increment i. (Key point: Algorithm)

2. What are the initial values?
   A. a = 1, b = 1, i = 1
   B. a = 0, b = 1, i = 0
   C. a = 0, b = 0, i = 0
   D. a = 1, b = 0, i = n
   Answer: B. Starting with a = 0, b = 1 produces 0, 1, 1, 2, 3, 5... (Key point: Initial values)

3. In state S1 (test), what decides the next state?
   A. The value of a
   B. start
   C. i < n goes to S2; i >= n goes to S4 (done)
   D. The value of t
   Answer: C. The status i < n from the datapath determines whether to output another number or finish. (Key point: State diagram)

4. Which components form the datapath?
   A. Only the FSM
   B. Only a multiplier
   C. Only a ROM
   D. Registers A, B, T, I, adder, incrementer, comparator and muxes
   Answer: D. Registers hold values; the adder computes a + b, the incrementer i + 1, the comparator i < n. (Key point: Datapath)

5. For n = 5 the outputs are:
   A. 0, 1, 1, 2, 3
   B. 1, 1, 2, 3, 5
   C. 0, 1, 2, 3, 4
   D. 1, 2, 3, 4, 5
   Answer: A. The first five Fibonacci numbers starting from 0 are 0, 1, 1, 2, 3. (Key point: Output for n=5)

## Related in Embedded System

- [Factorial single-purpose processor](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Aspp-factorial) — 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×
- [Design LCM single-purpose processor](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Aspp-lcm-datapath-controller) — Embedded System, chapter 2
- [Sum of digits processor](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Aspp-sum-of-digits) — Embedded System, chapter 2
- [Dual-purpose processor: median and variance](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Adual-purpose-median-variance) — Embedded System, chapter 2
- [LCM processor with state table](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Aspp-lcm-state-table-2digit) — Embedded System, chapter 2