CS 2204 Final Exam
Q1 [30 Points]. ASM Based Pattern Matching.
Carla wants to design a pattern matching circuit to detect
the pattern ‘1001’ in input ‘x’; output ‘y’ is ‘1’ whenever the
pattern is detected, ‘0’ otherwise. Overlapping sequences
of 1001 must be detected.
An example output is shown below:
x: 0 0 0 1 1 0 1 0 0 1 0 0 1 1 1…..
y: 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0…..
Carla decides to use an ASM to implement her circuit. Her
implementation consists of a 4-bit Shift Right Register ‘A’.
Bits of input x are shifted into ‘A’: if A contains ‘1001’ in
any clock cycle, output ‘y’ is set to 1 and otherwise to zero.
Pseudocode for Carla’s implementation is shown below.
A = 0000
In each clock cycle do:
Shift right bit x into register A
If (A==1001):
y=1
Else:
y=0
The ASM has a start input ‘s’ — the pattern matcher circuit
starts running when the user sets s to 1. Once the pattern
matcher starts running, it never stops (i.e., there is no
“Done” state).
(i) [5 Points] Draw an ASM of Carla’s pattern matcher,
clearly demarcating states, Moore-type or Mealy-type
actions, and conditionals. (Example: “Shift Rt. x into A” is
an action and “A=1001?” is a condition.)
(ii) [10 Points] Next Carla decides to update her
implementation to keep track of the number of times
pattern ‘1001’ has been observed in a 3-bit output called
“Ct”
When “Ct” becomes 2 (i.e., after two pattern matches),
Carla outputs a “Done” signal. Example outputs are shown
below, note that the Ct output increments a clock period
after each match. Likewise, the Done signal is enabled
one clock period after Ct becomes 2.
x: 0 0 0 1 1 0 1 0 0 1 0 0 1 1 1…..
y: 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0…..
Ct: 0 0 0 0 0 0 0 0 0 0 1 1 1 2 2…..
Done: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1…..
Draw an ASM of Carla’s updated pattern matcher, clearly
demarcating states, Moore-type or Mealy-type actions,
and conditionals.
(iii) [10 Points] Draw the datapath circuit for Carla’s
pattern matcher from part (ii). Your datapath circuit can
make use of different types of registers (regular, counter,
shift register) as studied in class, multiplexers, and
combinational logic gates (AND/NANDs etc.).
(iv) [5 Points] Draw an ASM for the control circuit
corresponding to your solutions from parts (ii) and (iii).
Q2 [30 Points]. ASM Based Adder/Multiplier.
In class, we learnt how to design a shift-and-add multiplier
that computes P = A*B for two n-bit inputs A and B. The
ASM for the multiplier is shown in Fig. 7.23.
We want to update the shift-and-add multiplier to perform
two different functions based on a command input “Cmd”
such that:
(a) If Cmd=0, the output P = A+B.
(b) If Cmd=1, the output P = A*B (as before).
We will call this new module that can perform both addition
and multiplication operations the add/mult unit.
(i) [10 Points] Complete the ASM for the add/mult unit.
State S1 and S3 are already done for you. You are
allowed to add as many additional states to the ASM as
you need. (Note: in state S1, “Cmd” is also being loaded
from the user.)
(ii) [10 Points] Draw a datapath circuit for the shift-add
unit. The registers containing inputs A, B and Cmd are
already done for you below. Your datapath circuit can
make use of different types of registers (regular, counter,
shift register) as studied in class, multiplexers, and
combinational logic gates (AND/NANDs etc.). In addition,
you are allowed to use a SINGLE 2n-bit adder in your
datapath circuit.
(iii) [10 Points] Draw the ASM representing the control
circuit for the add/mult unit. Note that as we have been
doing in class, you do not need to worry about the control
inputs needed to Load A, B and Cmd. You can leave these
out of your solution.
Q3 [20 Points]. FSM Based Pattern Matcher.
You would like to design an FSM that outputs a logic ‘1’
when the past four inputs are 1100 or 1101. Overlapping
patterns are allowed.
w: 0 1 1 0 1 1 0 0 0 1 0 1 1 0 0…..
z: 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1…..
(i) [10 Points] Derive the state diagram for this FSM. You
must the fewest possible number of states.
(ii) [10 Points] Derive minimal SOP expressions for the
next state and output variables as a function of the current
state and input. You are free to use any state assignment.
(iii) [10 Points] Based on the derived expressions,
implement the FSM as a circuit using D-flip-flops, and
inverters, AND gates and OR gates, (the AND and OR
gates can have multiple inputs).