University of California at Berkeley
University of California at Berkeley
College of Engineering
Department of Electrical Engineering and Computer Sciences
EECS150 J. Wawrzynek
Spring 2002 4/5/02
Midterm Exam II
Name:___________________________Solutions_______________________________
ID number:______________________________________________________________
This is a closed-book, closed-note exam. No calculators please. You have 3 hours. Each question is marked with its number of points (one point per expected minute of time).
Use the scrap paper to work out your answers, then neatly write your final answer in the space provided. We will only grade answers provided in the appropriate place.
Put your name and SID on each page.
Show your work. Write neatly and be well organized.
Good luck!
|problem |maximum |score |
|1 |28pts | |
|2 |10pts | |
|3 |10pts | |
|4 |15pts | |
|5 |14pts | |
|6 |12pts | |
|7 |11pts | |
|total |100pts | |
1. [28 pts] Short Answer.
a) [1pt] Any Boolean function can be implemented using multiplexers alone. (true or false)
b) [1pt] Dedicated carry-chains in FPGAs speed-up addition over carry-ripple adders using LUTS by approximately a factor of 4, 8, or 16 (choose one) _____________
c) [2pts] Equal comparison of 2 8-bit numbers (output =1 if two numbers are equal) requires at least _____31_____ 2-input AND/OR gates (assuming both complemented and uncomplemented inputs are available)
d) [1pt] For a SR-latch built from cross-coupled NAND gates, to set the latch, one of the the inputs must changed from logic level___HI___ to logic level___LO___.
e) [1pt] A toggle flip-flop can be built from a D-type flip-flop (with both Q and Q’ outputs) and how many 2-input AND/OR gates?
f) [1pt] How many distinct states are there in a n-bit Johnson Counter?
g) [2pt] A Two-dimensional “universal” shift-register (shift both left/right or up/down) could be built from D-type flip-flops and multiplexors with how many inputs?
h) [1pt] A Moore machine usually has fewer states than an equivalent Mealy machine. (true or false)
i) [1pt] If you were to build a 64:1 multiplexer from 4:1 multiplexers, you would need ___21__ 4:1 multiplexers.
j) [1pt] A sequential circuit is to output a 1 when an even number of one’s are input; otherwise the output is 0. The minimum number of flip-flops required is ___1____.
k) [1pt] A four to one multiplexer is to be implemented using a memory. How many [pic]words of memory are required, and how many bits must each word have?
l) [2pt] Given a Mealy machine with 3 inputs, 4 state flip-flops, and 5 outputs. What is the maximum possible number of transition arrows that can leave a single state?
m) [3pt] What is the minimum number of full-adder cells that are needed to reduce a list of M n-bit numbers to a pair of numbers using carry-save addition, in one clock cycle?
[pic]
[pic]
n) [6pt] Fill in the following table with delay and cost as a function of n for each type of n-bit adder structure (use the “big O” notation):
|Adder type |delay |cost |
|Ripple carry |O(n) |O(n) |
|Carry-Look-ahead |O(log n) |O(n) |
|Carry-Select |O(sqrt(n)) |O(n) |
o) [2pt] List two reasons why designers should carefully choose the state assignment in FSM design.
p) [2pt] What is the minimum number of 2-input gates that are needed to implement a 3-input decoder? (assume both complemented and uncomplemented versions of the input are available)
2. [10 pts] Consider the design of a Moore-style FSM with the following description: The FSM has 2 inputs, IN and RESET, and four outputs X0, X1, X2, and X3. After the RESET input is asserted the FSM accepts a stream of bits applied to the input IN. Bit patterns of the form 1((1 are “recognized” by the FSM, where each “(” may be either a 0 or a 1. After the rising edge of the clock on the cycle when the final 1 is passed in, the FSM asserts one of X0, … , X3 to indicate 00, 01, 10, or 11 for “((”. All other bit patterns result in no outputs being asserted. The RESET signal can come at any time and initializes the FSM to again look for bit patterns. Recognizable bit patterns do not overlap. For example, the bit stream (with time moving left to right through this bit string) 0101100100111010 contains only three recognized bit patterns, 1011, 1001, and 1101.
Fill in the symbolic state transition table and the output table below. (“symbolic” means that you do not need to encode the states – just make up state names).
3. [10pts] Consider the Mealy FSM with a state transition table shown below. An additional input, RESET, asynchronously sends the FSM to the S0 state.
In the space provided below, draw the circuit diagram for a one-hot encoded implementation of the FSM. Assume that the only circuit elements you have are inverters, 2-input AND and OR gates, and D-type flip-flops with asynchronous set and reset:
[pic]
4. [15 pts] Consider the design of a synchronous binary up-counter (no ripple counters allowed!). The counter has no count-enable input (CE) and no terminal-count (TC) output. Its only input, RESET, asynchronously sends the counter to the 0 state. The design elements in the table are the only ones available for your use. The flip-flops have asynchronous reset inputs. All delays are in ns. Ignore delay due to fan-out.
|Element |D-type FF |2-input EXOR |2-input AND |2-input OR |inverter |
|Cost |6 |3 |2 |2 |1 |
|Delay |1 (setup) |2 |2 |2 |1 |
| |1 (clk-to-Q) | | | | |
a) Using only elements from the table above, design an 8-bit counter with minimal cost that will function correctly with a clock period of 18ns. Draw your circuit in the place provided. Fill in the cost.
[pic]
Cost = INV + 7*EXOR + 6*AND + 8*FF = 1 + 21 + 12 + 48 = 82
Cycle time >= Tclk-to-Q + (6*TAND + TEXOR) + TSU >= 1 + (12 + 2) + 1 >= 16ns
b) Now assume the desired clock period is 15ns. Draw the circuit diagram for a counter (with the same functional specification as above) with minimal cost that will function correctly with a clock period of 15ns. Fill in the cost for this version.
[pic]
Cost = INV + 7*EXOR + 7*AND + 8*FF = 1 + 21 + 14 + 48 = 84
Cycle time >= Tclk-to-Q + (5*TAND + TEXOR) + TSU >= 1 + (10 + 2) + 1 >= 14ns
5. [14pts] Consider the design of an 3-bit array multiplier; a combinational logic circuit capable of multiplying 2 unsigned 3-bit numbers A and B, and generating a 6-bit result, P, within one clock cycle. Your design elements are shown with their associated delay in the table below. All delays are in ns.
|element |full-adder cell |2-input AND |
| |(any input to any output)| |
|delay |2 |1 |
Consider the design of a minimum cost multiplier. Assuming that both inputs A and B are applied at the same time, fill in the table below to indicate the worst-case delay from the inputs to each of the output bits in the result P. Hint: For this size multiplier, carry-save addition provides no advantage, so don’t use it. Justify your answer by drawing your circuit below.
| |delay |
|p0 |1 |
|p1 |3 |
|p2 |7 |
|p3 |9 |
|p4 |11 |
|p5 |11 |
6. [12 pts] A Moore style FSM with one input and one output has behavior described by the symbolic state transition table below.
a) Convert the Moore machine to a Mealy machine with the same behavior. Express your answer by filling in the symbolic state transition table in the space below. Use as few state as are necessary:
Observe that if the present state is A or D, given the same input, their behavior is the same (same state transition and output). So we can combine states A and D.
7. [12pts] Consider the design of a controller built from a FSM and a counter. The controller has one input, GO, and one output, DONE. When the GO signal is asserted (for at least one cycle) the controller waits for 12 cycles then asserts the DONE signal for one cycle, as shown below:
The controller must be built from a FSM and a 4-bit synchronous binary counter with count-enable (CE) and load (LD) inputs, parallel load signals (d3,d2,d1,d0), parallel output signals (q3,q2,q1,q0) and terminal-count output (TC).
a) In the space provided below, draw a state-transition-diagram for the FSM. You may choose between Moore and Mealy machines.
b) Make all necessary connections among the inputs and outputs, to implement the controller (assume the clock signal already is connected):
-----------------------
q3,q2,q1,q0
4-bit counter
NEXT
STATE IN STATE OUT
S0 0 S0 0
S0 1 S1 0
S1 0 S1 0
S1 1 S2 0
S2 0 S2 0
S2 1 S0 1
NEXT
STATE IN RESET STATE
FSM
CLK
GO
DONE
STATE OUTPUT
[pic]
[pic]
[pic]
A IN’ C 1
A IN B 0
C IN C 1
C IN’ A 1
B IN A 0
B IN’ B 0
[pic]
Cost = 84
Cost = 82
NEXT
STATE IN STATE
A 0 C
A 1 B
B 0 B
B 1 D
C 0 A
C 1 C
D 0 C
D 1 B
STATE OUTPUT
A 1
B 0
C 1
D 0
true
4
CE
NEXT
STATE IN STATE OUTPUT
TC
LD
d3,d2,d1,d0
GO
DONE
3
2n
6 or 9 if including the control
false
64 x 1
3 or 8
Delay, cost, and power
12
S0 0 0 S0 S0
1 0 S1 S1
S1 0 0 S2 S2
1 0 S3 S3
S2 0 0 S4 S4
1 0 S5 S5
S3 0 0 S6 S6
1 0 S7 S7
S4 0 0 S0 S8 X0
1 0 S8 S9 X1
S5 0 0 S2 S10 X2
1 0 S9 S11 X3
S6 0 0 S4
1 0 S10
S7 0 0 S6
1 0 S11
S8 0 0 S0
1 0 S1
S9 0 0 S0
1 0 S1
S10 0 0 S0
1 0 S1
S11 0 0 S0
1 0 S1
---- --- 1 S0
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related searches
- university of california at irvine ca
- university of california berkeley majors
- university of california berkeley cost
- university of california berkeley information
- university of california berkeley online
- university of california berkeley wiki
- university of california berkeley athletics
- university of california at berkeley
- university of california berkeley admissions
- university of california berkeley phd
- berkeley university of california tuition
- university of california berkeley extension