Minimal number of D flip-flops

Question

I have encountered the following question and can't be sure on the answer. Do you have any suggestions, any help would be much appreciated.

The Fibonacci sequence F(n) is defined by F(1)=1, F(2)=1, and Fn=F(n-2) + F(n-1) for all integers n>= 3. What is the minimal number of D flip-flops required (along with combinational logic) to design a counter circuit that outputs the first seven Fibonacci numbers (i.e., F1 through F7 ) and then wraps around?

(A) 3 (B) 4 (C) 5 (D) 6 (E) 7

Thanks in advance

Answer 1

First, you need to be able to count to 7. This is where the flip-flops come in, because they have the memory that you need to be able to remember the count. A simple approach would be to construct a ring buffer, but since you're allowed infinite combinatorial logic you can improve on this by constructing a binary counter.

Now that you have a circuit that provides 7 unique outputs, you can then augment that with further combinatorial logic to decode those outputs into the 7 values of your choice.

Answer 2

You can use a linear feedback shift register:

-- .--------/---------------------.
-- |        4             +----+  |
-- |          .-----------| __ |  |
-- |          |           | \  |--*-/-- F(n)
-- |  +--+    |  +--+     | /_ |    4
-- '--|  |--/-*--|  |--/--|    |
--    |> |  4    |> |  3  +----+
--    +--+       +--+
--   F(n-1)     F(n-2)

You need 7 flops in total (4+3).

Because your range is small the biggest numbers you will add are 8 and 5 to get F(7)=13

A real world design would register the F(n) output too (for timing reasons).

There is no need to count to 7 itself - this system could free-run and with increased stage widths count as high as you like. It would need a trigger value to reset itself if you wanted a fixed length sequence.

Answer 3

The minimum number of flipflops required would be only 3 for getting seven different outputs. But then it involves a lot of combinatorial circuitary for decoding the seven unique outputs into the required fibonacci sequence.One of those decoding circuit is using four 4:1 mux where, each mux output represents one bit of the fibonacci sequence.

But using 4 flipflops we can get a synchronous counter which goes through only these states 1,1,2,3,5,8,13 and wraping around. I think that this process involves a bit less circuitary.Here care should be taken only to differentiate the occurence of 1 twice, which, can be done through the use of an extra nand gate.