CS 150, Spring 1993
Quiz #2



Problem #1

1. (25 pts) List the ROM contents in hexadecimal to implement the Moore type FSM shown below. The inputs A.H and B.H are synchronized. The states are assigned in numerical order, e.g. for state S4, Q2Q1Q0=100. (Follow normal state diagram assumptions: an output is not asserted if it is not listed, holding in the same state is implicit, etc.)

Fill in ROM contents in hexadecimal. (Binary answers will receive no credit):

Address DataAddress DataAddress DataAddress Data
0
1
8
9
10
11
18
19
2
3
A
B
12
13
1A
1B
4
5
C
D
14
15
1C
1D
6
7
E
F
16
17
1E
1F

FSM design/chip layout

Problem #2

2. (15 pts) You are given the state table for an FSM and a partial schematic for the state machine. Complete the design of state machine by adding wires and gates as necessary to the multiplexer inputs. Do not make any other changes to the circuit.

Present State
Q1 Q0
Input
EN
Output
SIGNAL
Next State
Q1 Q0
0 0
0 0
0
1
1
1
0 0
0 1
0 1
0 1
0
1
0
0
0 0
1 1
1 0
1 0
0
1
1
0
1 1
0 0
1 1
1 1
0
1
1
0
1 0
1 1

chip layout

Problem #3

3. (25 pts) This problem refers to the computer data path and control unit shown below. Assume that all registers in the data path section are run from the same CLOCK used in the control unit. You may assume that all control signals are asserted high, and that all registers in the data path have synchronous loads. The table below shows a portion of the micro-program (in symbolic form) stored in the 4Kx16 ROM in the control unit. (An x represents a don't care combination of bits, and a NOP is an abbreviation for no operation).

data path/control unit

micro-PC
address
OUT
15
OUT12
MEMCS
OUT11
MEMWE
OUT9..10
load grp 1
OUT6..8
load grp 2
OUT3..5
output enab
OUT0..2
ALU func
0x20100NOPSLOADR3OUTA plus 1
0x21100MARLDNOPR2OUTx
0x22111NOPNOPSOUTx
0x23101NOPNOPSOUTx
0x24100NOPSLOADR2OUTA plus 1
0x25100NOPR2LOADSOUTx
0x26100MARLDNOPR3OUTx
0x27110NOPR3LOADNOPx
0x28100NOPNOPNOPx

ALU function table:
ALU operationALU codeALU operationALU code
Y = A plus B000Y = A100
Y = A plus B plus carry001Y = 0101
Y = A plus 1010Y = 1110
Y = A minus 1011Y = -1111


3a. Determine the register transfer description for the micro-operations corresponding to each line of the micro-program listed above, and fill in the following table:

Register Transfer Description of Microprogram
micro-PC addressregister transfer description
0x20 
0x21 
0x23 
0x24 
0x25 
0x26 
0x27 


3b. If R3 is the CPU program counter, and R2 is used as the stack pointer, describe, in 10 words or less, the computer instruction corresponding to the above micro-program:

3c. Complete the timing diagram for the micro-instructions 0x24 through 0x27 (defined in table above). For the Data_Bus, show when the bus is tri-stated, and table what is on the bus, e.g. "r2".

timing diagram

Problem #4

4. (25 pts) You are given the following data path consisting of a random access memory, two registers, and a 4 bit counter. A Moore type FSM controller (shown below) driven from CLOCK.H generates control signals, which are asserted tFSM after the rising edge of the clock. Timing parameters are given in the table below. Given: tcountmax > tFSM > tDQmax.

SymbolsExplanations
tclockclock period
tskewclock skew to R2
tsetup, tholdsetup and hold times for '377
tDQmax, tDQminmax. and min. prop. delay from rising edge of clock to Q valid
tZAmax, tZAminmax. and min. time for '125 to become active (= propagation delay)
tAZmax, tAZminmax. and min. time for '125 to become tri-state
tcountmax, tcountmintime from rising edge of clock to '163 outputs
treadtime from CS asserted and address valid until RAM data out valid
tWEZmax, tWEZmintime from write enable asserted to RAM data out tri-stated
twrite, twriteholdmin. time for WE after data is valid, data hold time after WE not asserted

chip layout

Answer each part independently. The operation of the RAM is similar to the 2114 studied in lab 5. The control signal MEMCS.L is always asserted.

a. Explain, using register transfer notation, the data transfers taking place in each clock cycle.

b. What is the minimum tclock for R2 to be correctly written with the contents of R1?
tclock > ___ ?

c. What is the minimum tclock for R2 to be correctly written with the contents of RAM?
tclock > ___ ?

d. What conditions must be satisfied to ensure that thold for R2 is not violated?
thold < ___ ?

e. What conditions must be satisfied to ensure that the hold time for the RAM is not violated during the write cycle?
twritehold < ___ ?

f. There is a potential bus conflict at the beginning of a memory write cycle if the RAM output becomes tri-stated too late. What condition must be satisfied to avoid a bus conflict at this time?

timing diagram

Problem #5

5. (10 pts) Design the state diagram for a Mealey FSM with synchronized input W.H and output Y.H. The output Y should be asserted for one clock cycle whenever the sequence 1011 has been input on W. Note that the patterns may be overlapping, e.g. W = ...1011011000... should generate Y = ...0001001000... The machine should start assuming that a "0" has already been input.

Mealey machine



Posted by HKN (Electrical Engineering and Computer Science Honor Society)
University of California at Berkeley
If you have any questions about these online exams
please contact examfile@hkn.eecs.berkeley.edu.