# Python电路代写 | CPSC 359 Assignment 2: A Sequential Circuit to Generate the Fibonacci

本次加拿大代写是Python电路的一个assignment

In this assignment, you will program a sequential circuit to that computes 32-bit unsigned integers in the Fibonacci

sequence. While the circuit is very speciﬁc to this task, it is a simpliﬁcation of many of the elements of a CPU. Your

program will be equivalent to the microcode in a CPU that establishes the machine code/assembly language for the

device.

Design and implement a sequential logic circuit that computes 32-bit unsigned integers in the Fibonacci series modulo

2 ³².

Algorithm 1 shows how to compute the Fibonacci sequence in order. I have provided you with a logisim template to

implement this algorithm (Figure 1). Insert you solution into the template where indicates – otherwise do not alter the

template.

Algorithm 1 Algorithm to computer the Fibonacci sequence.

1: f0 0

2: f1 1

3: for n = 2 : : : do

4: fn fn 1 + fn 2

5: end for

Note the use of tunnels in the template. These are in the wiring menu of Logisim. You can think of them as a

named wire. Anywhere the name of the tunnels match, Logisim treats it as if you had connected a wire between the

two points. They are a nice way to keep your circuits organized (especially if you choose meaningful names) and

reduce the clutter in the rat’s nest of connections that you get without them.

The template gives you three 32-bit registers to work with. The idea is that after your circuit executes line 4 of the

algorithm, the three registers will contain fn, fn 1, and fn 2. In my solution I put fn in r2, so as the circuit runs you

see the Fibonacci numbers (modulo 2³²) in hexadecimal.

Each register has the following features.

• There is a data output attached to a tunnel with the register name (r0, r1, and r2).

• Each registers load/clock is connected to the master clock through an AND gate. The registers perform a load

on a falling edge. A load signal (load0, load1, and load2) determines when the clock passes through to the

register so that a load occurs.

• The data input to a register is a 4-to-1 multiplexer, so that a register load can come from one of 4 sources. These

sources are: 0, 1, the adder output, or one of the other registers (r[n] can load from r[(n + 1) mod 3] ). The

source is selected with the 2-bit signals rSrc0, rSrc1, and rSrc2.

There is one 32-bit adder. Each of the operands comes from a 4-to-1 multiplexer that selects from: 1, r0, r1, or r2.

The 2-bit signals aSrc0 and aSrc1 select the two operands. The adder output goes to the tunnel named Adder.

At the top of the template you will ﬁnd a set of signals that are useful for the circuit.

• There are two 32-bit constants for the values 0 and 1 (with tunnels named Zero and One). These are useful for

initializing registers or the 1 can be used to increment a value with the adder.

• There is a master clock . Use this to drive state transitions in your sequential circuit. State transitions should

occur on the rising edge of the clock. Note that this is out of phase with the falling-edge loads of the registers.

• There is a start pin (tunnel named Start. You circuit should have and idle state. Setting the start pin should start

the algorithm.

• The algorithm runs in an inﬁnite loop. The halt pin (tunnel named Halt) provides a way to break out of the loop.

• The reset pin (tunnel named Reset) should move the circuit from the halt state back to the idle state so you can

run the algorithm again.

Note that Logisim (and a real-world circuit) will do unpredictable things when a register is both a source and a

destination in a load. You need to account for this in your microcode.

The template circuit is sufﬁcient to implement the algorithm by providing a sequential circuit to use/provide the

signals in the tunnels. Once you are comfortable that you understand the template, create a state diagram for the

algorithm.

Finally, implement the your state diagram in a sequential circuit using a read-only memory (ROM), as discussed in

class. Your sequential controller will need a clock signal to drive it. If you then click Ticks Enabled under the Simulate

menu in Logisim, the lock should operate as speciﬁed.