VLSI Interview Questions by Rajesh Bawankule: June 2011

Monday, June 6, 2011

Interview Question 16: Fibonacci number generator

Design a hardware block to generate Fibonacci numbers.
You have freedom to decide the architecture of this block.

In mathematics, the Fibonacci numbers or Fibonacci series or Fibonacci sequence are the numbers in the following integer sequence:

$0,\;1,\;1,\;2,\;3,\;5,\;8,\;13,\;21,\;34,\;55,\;89,\;144,\; \ldots\;$

or, alternatively,

$1,\;1,\;2,\;3,\;5,\;8,\;13,\;21,\;34,\;55,\;89,\;144,\; \ldots.$

By definition, the first two numbers in the Fibonacci sequence are 0 and 1 (alternatively, 1 and 1), and each subsequent number is the sum of the previous two.
In mathematical terms, the sequence Fn of Fibonacci numbers is defined by the recurrence relation

$F_n = F_{n-1} + F_{n-2},\!\,$
with seed values

$F_0 = 0,\; F_1 = 1.$