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

• ALL

## Background

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.

## Objective

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

## Details

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. E-mail: vipdue@outlook.com  微信号:vipnxx 