PROBLEM $3(25$ PTS$)$

$$ Fibonacci numbers Computation: We want to design a circuit that reads an unsigned number $(>1)$ and generates $$ :

$$ To compute $$ in an iterative fashion, we can use: $$

$=+,=,=11201$

$$

n: unsigned integer F$0=0,$ F$1=1$

if n $>1$

for i $=2$ to n

Fi $=$ Fi$-1+$ Fi$-2$

end end

return Fn

$$ Operation: The circuit reads n when the s signal $($usually a one$-$clock cycle$)$ is asserted. When the result $()$ is ready, the

signal done is asserted.

$$ Input: s $($start signal$),$ n $($input data$)$

$$ Outputs: Fn $($result$),$ done.

$$ Clock frequency: $100$ MHz$.$

$$ We restrict the bitwidth of Fn to $16$ bits. As a result, the largest n would be $24(24=46368).$

$$ Sketch the circuit: FSM $($in ASM form$)+$ Datapath components. Specify all the I$/$Os of the FSM$,$ as well as the signals

connecting the FSM and the Datapath components $($as in Problem $2).$

$$ Suggestion: Use two registers $($for $$ and $),$ initialized with $=1$ and $=($iterations start at $=2).$ At every $1210$

iteration $(=2,...,),$ is computed, and then the registers $($parametric register with enable: my$\_$rege$)$ are updated:

$$ Register $1$: It captures the computed $.$

$$ Register $2$: It captures $1.$

$$ Feel free to use any other standard component $($e$.$g$.$: register, counter, comparator, adder, busmux$).$

$$ The iteration index $$ can be implemented with a standard counter $($my$\_$genpulse$\_$sclr$).$ Here, you can only initialize the

count to $0.$ To ensure that iterations start at $=2,$ you can include more states $($to increase the count$).$

$$ To simplify the design, you can assume that $>1.$