xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

留学生论文指导和课程辅导

无忧GPA：https://www.essaygpa.com

工作时间：全年无休-早上8点到凌晨3点

微信客服：xiaoxionga100

微信客服：ITCS521

无代写-CSE 140

时间：2021-03-10

First Name: Last Name: PID:

Version A Solution

Left Neighbor

Right Neighbor

Seat No.

CSE 140 Midterm 2

Prof. Tajana Simunic Rosing

Winter 2018

● Do not start the exam until you are told.

● The examination will be graded out of 100, with 10 extra bonus points.

● Write your name and PID at the top of every page. Do not separate the pages.

● Turn off and put away all your electronics.

● This is a closed-book, closed-notes, no calculator exam.

You may only refer to one 8 ½ x 11” page of your handwritten notes.

● Do not look at anyone else’s exam.

● Do not talk to anyone but an exam proctor during the exam. If you have a question,

raise your hand and an exam proctor will come to you.

● You have 80 minutes to finish the exam. When the time is finished, you must stop.

● Write your answers in the space provided.

● To get the most partial credit, clearly and neatly show all steps of your work.

Problem 1 15 points

Problem 2 10 points

Problem 3 15 points

Problem 4 25 points

Problem 5 25 points

Problem 6 20 points

Total points 100 points + 10 bonus

1

First Name: Last Name: PID:

1. Design a pattern recognizer that outputs a 1 when it detects among 4 input bits zero or

more 0s followed by zero or more 1s - 0011, 0000, and 1111 are some examples.

Here is sample output of the pattern recognizer.

Time ->

Input: 0110001011001110100101111

Output: XXX0001000000110000000011

a. (5pts) Use a shift register to recognize the pattern. Complete the circuit using a

minimum number of inverters and two-input logic gates, connected only to the Q

outputs of the FFs. Assume there are no setup or hold violations. Note that

values flow from left to right.

2

First Name: Last Name: PID:

b. (10pts) Draw the state diagram for a Mealy FSM that recognizes the same

pattern. Use as few states as possible.

Or with clever trick:

3

First Name: Last Name: PID:

2. Consider the following sequential circuit with input and output.

a. (8pts) Fill in the excitation table. You can assume initial state is encoded as 00.

Excitation Table

Q1(t) Q0(t) Input Q1(t + 1) Q0(t + 1) M

0 0 0 0 1 0

0 1 0 1 0 0

1 0 0 1 1 1

1 1 0 0 0 1

0 0 1 1 1 1

0 1 1 0 0 1

1 0 1 0 1 0

1 1 1 1 0 0

b. (2pts) Is this design Mealy or Moore FSM?

Moore

4

First Name: Last Name: PID:

3. (15pts) Complete the timing diagram for the circuit below. Assume near zero delay for all

elements. Initial state of the flip flop is 0. Initial value of Y is 1 and of Z is 0. Setup, hold times

and clock skew can be neglected.

CLK

A

B

E

F

Y

5

First Name: Last Name: PID:

4. (25pts) Consider the following FSM diagram.

a. (10pts) Assuming the following state encoding: S0 = 00, S1 = 01, S2 = 10, S3 = 11, draw

the combinational circuit for the LSB of the next state, Q0(t+1), using minimal number of

gates.

6

First Name: Last Name: PID:

b. (6pts) Assuming the same state encoding as part (a), find the number of bit changes of

transitions between the states. Complete the table below.

Transition Number of bit change

S0 → S1 1

S0 → S2 1

S0 → S3 2

S1 → S3 1

S2 → S0 1

S3 → S0 2

Total 8

c. (3pts) Using minimum bit change heuristics, assign the state values so that the number

of bit changes is minimized during the state transitions. Complete the table below.

State Encoding Encoding

S0 11 11

S1 00 00

S2 10 01

S3 01 10

d. (6 pts) Assuming the state encoding in part (c), find the number of bit changes of

transitions between the states. Complete the table below.

Transition Number of bit changes

S0 → S1 2

S0 → S2 1

S0 → S3 1

S1 → S3 1

S2 → S0 1

S3 → S0 1

Total 7

7

First Name: Last Name: PID:

5. (25pts) The following HLSM reads two eight-bit numbers, A and B, from two 10x8 register

files and increments a counter if either of them is zero when a start signal is given. This process

is done ten times, one time for each word in the register. The final output is provided in

ResultReg.

a. (9pts) There are nine missing components (states/controls) in the HLSM below.

Fix what is needed so that the HLSM works correctly.

8

First Name: Last Name: PID:

b. (7pts) Design the datapath for this system.

c. (9pts) Connect datapath to control and show all input/outputs for both datapath and

control.

9

First Name: Last Name: PID:

5. (20 pts) Answer the following questions using the data given below:

Logic gate tpd tcd

NOT 10ns 10ns

AND 30ns 20ns

OR 30ns 20ns

XOR 40ns 30ns

tsetup 20ns

thold 35ns

tccq 10ns

tpcq 60ns

a. Assuming tskew = 0

i. (5pts) Find the maximum clock frequency.

10

First Name: Last Name: PID:

ii. (5pts) Does the circuit have a hold time violation? Show your work.

b. Assuming tskew = 10ns

i. (5pts) What is the maximum clock frequency? How does it compare to

the one calculated in part a-i? Show your work.

ii. (5pts) Consider the modified circuit shown in figure 2, does the modified

circuit have a hold time violation? Show your work

11

First Name: Last Name: PID:

This page is intentionally left blank.

12

学霸联盟

Version A Solution

Left Neighbor

Right Neighbor

Seat No.

CSE 140 Midterm 2

Prof. Tajana Simunic Rosing

Winter 2018

● Do not start the exam until you are told.

● The examination will be graded out of 100, with 10 extra bonus points.

● Write your name and PID at the top of every page. Do not separate the pages.

● Turn off and put away all your electronics.

● This is a closed-book, closed-notes, no calculator exam.

You may only refer to one 8 ½ x 11” page of your handwritten notes.

● Do not look at anyone else’s exam.

● Do not talk to anyone but an exam proctor during the exam. If you have a question,

raise your hand and an exam proctor will come to you.

● You have 80 minutes to finish the exam. When the time is finished, you must stop.

● Write your answers in the space provided.

● To get the most partial credit, clearly and neatly show all steps of your work.

Problem 1 15 points

Problem 2 10 points

Problem 3 15 points

Problem 4 25 points

Problem 5 25 points

Problem 6 20 points

Total points 100 points + 10 bonus

1

First Name: Last Name: PID:

1. Design a pattern recognizer that outputs a 1 when it detects among 4 input bits zero or

more 0s followed by zero or more 1s - 0011, 0000, and 1111 are some examples.

Here is sample output of the pattern recognizer.

Time ->

Input: 0110001011001110100101111

Output: XXX0001000000110000000011

a. (5pts) Use a shift register to recognize the pattern. Complete the circuit using a

minimum number of inverters and two-input logic gates, connected only to the Q

outputs of the FFs. Assume there are no setup or hold violations. Note that

values flow from left to right.

2

First Name: Last Name: PID:

b. (10pts) Draw the state diagram for a Mealy FSM that recognizes the same

pattern. Use as few states as possible.

Or with clever trick:

3

First Name: Last Name: PID:

2. Consider the following sequential circuit with input and output.

a. (8pts) Fill in the excitation table. You can assume initial state is encoded as 00.

Excitation Table

Q1(t) Q0(t) Input Q1(t + 1) Q0(t + 1) M

0 0 0 0 1 0

0 1 0 1 0 0

1 0 0 1 1 1

1 1 0 0 0 1

0 0 1 1 1 1

0 1 1 0 0 1

1 0 1 0 1 0

1 1 1 1 0 0

b. (2pts) Is this design Mealy or Moore FSM?

Moore

4

First Name: Last Name: PID:

3. (15pts) Complete the timing diagram for the circuit below. Assume near zero delay for all

elements. Initial state of the flip flop is 0. Initial value of Y is 1 and of Z is 0. Setup, hold times

and clock skew can be neglected.

CLK

A

B

E

F

Y

5

First Name: Last Name: PID:

4. (25pts) Consider the following FSM diagram.

a. (10pts) Assuming the following state encoding: S0 = 00, S1 = 01, S2 = 10, S3 = 11, draw

the combinational circuit for the LSB of the next state, Q0(t+1), using minimal number of

gates.

6

First Name: Last Name: PID:

b. (6pts) Assuming the same state encoding as part (a), find the number of bit changes of

transitions between the states. Complete the table below.

Transition Number of bit change

S0 → S1 1

S0 → S2 1

S0 → S3 2

S1 → S3 1

S2 → S0 1

S3 → S0 2

Total 8

c. (3pts) Using minimum bit change heuristics, assign the state values so that the number

of bit changes is minimized during the state transitions. Complete the table below.

State Encoding Encoding

S0 11 11

S1 00 00

S2 10 01

S3 01 10

d. (6 pts) Assuming the state encoding in part (c), find the number of bit changes of

transitions between the states. Complete the table below.

Transition Number of bit changes

S0 → S1 2

S0 → S2 1

S0 → S3 1

S1 → S3 1

S2 → S0 1

S3 → S0 1

Total 7

7

First Name: Last Name: PID:

5. (25pts) The following HLSM reads two eight-bit numbers, A and B, from two 10x8 register

files and increments a counter if either of them is zero when a start signal is given. This process

is done ten times, one time for each word in the register. The final output is provided in

ResultReg.

a. (9pts) There are nine missing components (states/controls) in the HLSM below.

Fix what is needed so that the HLSM works correctly.

8

First Name: Last Name: PID:

b. (7pts) Design the datapath for this system.

c. (9pts) Connect datapath to control and show all input/outputs for both datapath and

control.

9

First Name: Last Name: PID:

5. (20 pts) Answer the following questions using the data given below:

Logic gate tpd tcd

NOT 10ns 10ns

AND 30ns 20ns

OR 30ns 20ns

XOR 40ns 30ns

tsetup 20ns

thold 35ns

tccq 10ns

tpcq 60ns

a. Assuming tskew = 0

i. (5pts) Find the maximum clock frequency.

10

First Name: Last Name: PID:

ii. (5pts) Does the circuit have a hold time violation? Show your work.

b. Assuming tskew = 10ns

i. (5pts) What is the maximum clock frequency? How does it compare to

the one calculated in part a-i? Show your work.

ii. (5pts) Consider the modified circuit shown in figure 2, does the modified

circuit have a hold time violation? Show your work

11

First Name: Last Name: PID:

This page is intentionally left blank.

12

学霸联盟