HW 4: Algorithmic State Machines with Datapath

Problem 1

We want to build a digital system that counts the number of people in a room. The one door through which people enter the room has a photocell that changes a signal x from 1 to 0 while the light is interrupted. People leave the room from a second door with a similar photocell that changes a signal y from 1 to 0 while the light is interrupted. The datapath circuit consists of an up-down counter with a display that shows how many people are in the room. Only one person can pass through each door at a time and each person should only be counted once.

• Construct a block diagram and an ASMD chart for this system.
  Hint: You should use 4 states corresponding with each combination of the sensors' outputs x and y.

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.

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.

1. The ROM is a purely combinational circuit. Draw out the partial ASMD chart using the ROM as-is. If N is found on the 4th searched address, how many clock cycles does the searching portion of the algorithm consume?
2. 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 4th searched address, how many clock cycles does the searching portion of the algorithm consume?

   

3. 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 4th searched address, how many clock cycles does the searching portion of the algorithm consume?

   

Problem 3

You are provided a buggy Verilog implementation of a divider circuit similar to the one discussed in lecture in the files: divider.v, downcount.v, muxdff.v, regne.v, and shiftlne.v (files).

• Create a test bench (divider_tb.sv) and use it to update the provided code to work as intended (note: all Verilog code works in SystemVerilog if you would like to update to .sv files). Make sure that your code fixes are documented in code comments for each file.
• Include screenshots of any warnings, errors, or simulation results of the original code and point out the parts that helped you identify the faulty behavior that you found.

Signal naming scheme: "E" is short for enable "L" is short for load "R" is short for register "C" is short for counter s is the start signal z is the zero signal (count==0).

Component naming scheme: Upper-left Left-shift register is "Register A" (A) Upper-right Register is "Register B" (B) Lower Left-shift register is the "Remainder Register" (R, confusing, I know) The output signals at the bottom are the quotient (Q) and remainder (R). The down-counter (C) is not shown but used to generate the z signal.