Fibonacci Circuit

Thread Starter

scendic

Joined Dec 2, 2022
9
Hello
I have to make the logisim circuit of the Fibonacci sequence on 8 bits. My knowledge is limited on the components I can use. I was thinking of using a clock, registers, a 7 segments display, an adder and a reset. I understand the principle of the Fibonacci sequence but I can't translate it into a logic circuit....
Some indications ?

I have done this in Bsim :

LD(a,R1)
LD(b,R2)
LD(n,R4)
loop:
ADD(R1,R2,R3)
MOVE(R2,R1)
MOVE(R3,R2)
SUBC(R4,1,R4)
test:
CMPLT(R31,R4,R5) // If (R31 < R4) Then R5 <- 1 Else R5 <- 0
BT(R5,loop) // If R5 != 0 Then GoTo loop

ST(R3,c)
HALT()

a: LONG(0)
b: LONG(1)
c: LONG(0)
n: LONG(5)

Thanks
 
Last edited:

WBahn

Joined Mar 31, 2012
27,880
Don't assume that everyone knows whatever particular assembly language you are using.

Don't start with throwing code at a problem. Design an algorithm (a set of steps) intended to solve the problem. Then convert the steps into code.
 

Thread Starter

scendic

Joined Dec 2, 2022
9
I don't see all the steps to do... Especially the components. I was thinking of using 3 registers, each connected to a clock. Use an adder between 2 registers to add their output value but I don't see how to give back the value of the second register to the first one after having done the addition for example. In general I think I have understood but it's when I build the circuit that I understand that it's more complicated than expected


Don't assume that everyone knows whatever particular assembly language you are using.

Don't start with throwing code at a problem. Design an algorithm (a set of steps) intended to solve the problem. Then convert the steps into code.
 

WBahn

Joined Mar 31, 2012
27,880
Say you have two registers. I'll call them Reg0 and Reg1.

After several clocks, Reg0 has a value of 8 and Reg1 has a value of 5.

You should recognize these as two values in the Fibonacci sequence.

If the output of the circuit right now is 8, what would you think the next value in Reg0 should be? What should the next value in Reg1 be?
 

Thread Starter

scendic

Joined Dec 2, 2022
9
For me, Reg0 would be worth 8 and Reg1 would be worth 5+8=13?
The clock strokes would be in fact the modeling of the incrementation of n in the circuit ? (For F(0) : 1st clock stroke, F(1) : 2nd clock stroke...?)
But how can the value which is 8 at the end of your example, be stored in the Reg0 ? Don't we need a 3rd register that stores the result of the addition of Reg0 and Reg1?

Say you have two registers. I'll call them Reg0 and Reg1.

After several clocks, Reg0 has a value of 8 and Reg1 has a value of 5.

You should recognize these as two values in the Fibonacci sequence.

If the output of the circuit right now is 8, what would you think the next value in Reg0 should be? What should the next value in Reg1 be?
 

WBahn

Joined Mar 31, 2012
27,880
For me, Reg0 would be worth 8 and Reg1 would be worth 5+8=13?
Why? What would they become on the next clock cycle? The way you are going about it, the register that contains the current Fibonacci number would be ping-ponging back and forth between the two. That means that the output of your logic has to ping-pong back and forth. You can do it that way, but why?

Instead, decide up front how your circuit is going to decide what the current Fibonacci number is. The easiest way it to pick one of the registers and say that, at any given time, that register always has the current element in the Fibonacci sequence. Then ask yourself what information do you need to determine what that value becomes next?

The clock strokes would be in fact the modeling of the incrementation of n in the circuit ? (For F(0) : 1st clock stroke, F(1) : 2nd clock stroke...?)
But how can the value which is 8 at the end of your example, be stored in the Reg0 ? Don't we need a 3rd register that stores the result of the addition of Reg0 and Reg1?
Why would you need a register to store the sum of Reg0 and Reg1?

What would you do with that?

You want a register that, after every clock cycle, contains the next value in the sequence.

You can do it with a third register (or a fourth or a fifth), but it's not necessary.
 

WBahn

Joined Mar 31, 2012
27,880
I'm going to have give a bit of a mea culpa -- I had in mind hardware registers that can all be updated on the same clock edge. In that case you only need two registers.

The solution is simple: Reg0 stores the current number in the sequence and Reg1 stores the prior number.

On each clock edge, Reg0 gets the sum of Reg0 and Reg1 while Reg1 gets what was in Reg0.

You need a way to initiate things, which would involve one of two approaches. The first would load a 1 in Reg0 and a 0 in Reg1. This sequence then starts 1,1,2,3....

If, instead, you need to start the sequence out with 0,1,1,2,3,..., then you load a 0 in Reg0 and a 1 in Reg1. This is a bit of a trick and is not obvious.

However...

You are not implementing this in hardware, but rather software, and you can only change one register at a time. While it can still be done with just two registers, the easiest way is with three.

There are a couple of ways of thinking about this.

The first is to think of that third register as just a scratchpad/temporary varaible.

Another is to envision that at the beginning of each cycle, R0 has the current Fibonacci number, R1 as the prior value, and R2 has the value prior to that.

What has to happen to the value of each register during the next cycle of the code loop? The big thing you need to do is make sure that you don't overwrite a register's value until you don't need that value every again.

I'd recommend getting a three-register solution going. Then we can talk about a two-register solution (which will be much faster).
 

Thread Starter

scendic

Joined Dec 2, 2022
9
I made a circuit with 3 registers Reg0, Reg1 and Reg2. I added an adder with Reg0 and Reg1 as inputs and Reg2 as output. My sequence must start with 0,1,1,2,3... so I initialized Reg0 by 1 and Reg1 by 0. I also added a clock on each register. Everything is in 8 bits.

But here is my problem : how to put the following values in the registers ? When I create a wire from the adder and connect it to Reg0, I get an error. Similarly when I create a thread at the output of Reg0 to Reg1.

I would have done it this way but it doesn't work...

I'm going to have give a bit of a mea culpa -- I had in mind hardware registers that can all be updated on the same clock edge. In that case you only need two registers.

The solution is simple: Reg0 stores the current number in the sequence and Reg1 stores the prior number.

On each clock edge, Reg0 gets the sum of Reg0 and Reg1 while Reg1 gets what was in Reg0.

You need a way to initiate things, which would involve one of two approaches. The first would load a 1 in Reg0 and a 0 in Reg1. This sequence then starts 1,1,2,3....

If, instead, you need to start the sequence out with 0,1,1,2,3,..., then you load a 0 in Reg0 and a 1 in Reg1. This is a bit of a trick and is not obvious.

However...

You are not implementing this in hardware, but rather software, and you can only change one register at a time. While it can still be done with just two registers, the easiest way is with three.

There are a couple of ways of thinking about this.

The first is to think of that third register as just a scratchpad/temporary varaible.

Another is to envision that at the beginning of each cycle, R0 has the current Fibonacci number, R1 as the prior value, and R2 has the value prior to that.

What has to happen to the value of each register during the next cycle of the code loop? The big thing you need to do is make sure that you don't overwrite a register's value until you don't need that value every again.

I'd recommend getting a three-register solution going. Then we can talk about a two-register solution (which will be much faster).
 

WBahn

Joined Mar 31, 2012
27,880
At this point I'm confused as to what the end game is here. How are you trying to implement the solution? Are you trying to design a logic circuit, or write an assembly language program? The constraints on each are different.

What tool are you using to simulate your hardware solution? Can you show a picture of the schematic you are trying to implement?
 

Thread Starter

scendic

Joined Dec 2, 2022
9
I use Logisim to make my circuit of the Fibonnaci sequence on 8 bits. I have to display the result of each operation (F(0), F(1), F(2)...) with a 7 segments display.
So I have to display a result for each clock stroke. As components, I have only seen registers, multiplexers, demultiplexers, adder, splitter, logic gates (AND, OR, NOR...), comparators, RAM and ROM.

What I explained in my previous message, here it is schematized on Logisim. fibo.png


At this point I'm confused as to what the end game is here. How are you trying to implement the solution? Are you trying to design a logic circuit, or write an assembly language program? The constraints on each are different.

What tool are you using to simulate your hardware solution? Can you show a picture of the schematic you are trying to implement?
 

WBahn

Joined Mar 31, 2012
27,880
You are loading both of the left-hand registers with zero on every clock cycle and then loading the right-hand register with the sum of the two left-hand registers.

If the value in Reg2 is the current Fibonacci number, what register does that value need to appear in on the next cycle, when it is the prior Fibonacci number? What value needs to be in the other register next? Where is that number currently stored?

You need to be able to reset the sequence, which means you need to be able to choose whether to load the initial values into the registers, or the next values. What component can be used to do that?
 

Thread Starter

scendic

Joined Dec 2, 2022
9
The value in Reg2 must be in one of the two registers Reg0 or Reg1. I will choose Reg0, so the value in Reg2 must appear in Reg0 at the end of the circuit before the next clock stroke? So Reg1 will have the value of Reg0.

Can we use a Reset ? That we connect to a multiplexer ?
 

WBahn

Joined Mar 31, 2012
27,880
The value in Reg2 must be in one of the two registers Reg0 or Reg1. I will choose Reg0, so the value in Reg2 must appear in Reg0 at the end of the circuit before the next clock stroke? So Reg1 will have the value of Reg0.

Can we use a Reset ? That we connect to a multiplexer ?
It looks like you are on the right track. Put these thoughts into your schematic and post it so that we can be sure we are on the same page.
 

Thread Starter

scendic

Joined Dec 2, 2022
9
I don't really understand why I have an error after putting the multiplexers? Did I connect the components wrong? I should not have put a constant=0 in an input of the MUX?

fibo2.png
 

WBahn

Joined Mar 31, 2012
27,880
Yes. You are connecting the OUTPUT of the MUX to the CONSTANTs, so what value is on that bus, the output of the MUX or the value of the constant?
 

WBahn

Joined Mar 31, 2012
27,880
No. The two red wires each are being driven by TWO signal sources -- a constant and the output of a mux. This results in contention (fighting). It's like if one parent tells a child to clean their room and the other parent tells them to mow the lawn. What should the child do when they are being told to do two different things but can only do one thing at a time?

What is the purpose of that constant 00000101? It's to preload the register with a value WHEN the reset is issued (I'm assuming that you are using 5 and 3 as test values).

Go back and review what a MUX is and what it does and what it's inputs and outputs are.
 
Top