Problem $2$

In this problem, we will investigate the implied timing of ASMD charts. Recall that any datapath effects from the active path take effect when you EXIT the state.

Our goal is implement a rudimentary search algorithm on a ROM, whose datapath is shown below. We want to cycle through the addresses $($adding $1$ each time$)$ until a

specified number $N$ is found. We output a status indicator found as well as the first encountered address $A$ in which it was found. For this purposes of this problem,

you should ignore the situation where $N$ is not in the ROM.

Figure $1$: Datapath for rudimentary search algorithm. A is the output of a register$/$counter and represents the address we're currently checking. D is the output of the ROM that is compared

against a specified number $N.$

In the questions below, when asked, draw a partial ASMD chart for just the searching part of the algorithm $($i$.$e$.,$ you don't need to show the idling, initialization, or done

states and you can leave paths the go to or come from these states "hanging"$).$ Use incr$\_$A as a control signal and found as a status signal. Your goal is to complete

the task in as few clock cycles as possible.

a$.$ The ROM is a purely combinational circuit. Draw out the partial ASMD chart using the ROM as$-$is$.$ If $N$ is found on the $4$th searched address, how many clock cycles

does the searching portion of the algorithm consume?

b$.$ We now synchronize the output of the ROM by registering it$.$ Draw out the partial ASMD chart using the registered ROM output. If $N$ is found on the $4$th searched

address, how many clock cycles does the searc'

c$.$ Harry the Husky claims that we can save clock cycles with the registered ROM output if we also register the A output. Draw out the partial ASMD chart using the

synchronized A output, remembering that we want the A output to reflect the correct address when the searching is done. You may use an additional control

signal decr$\_$A for this ASMD. If $N$ is found on the $4$ th cearrhed addresc hnw manv rlnck svelec dnec the cearrhino portion of the algorithm consume?