Name Student ID #
First Last
University of California Los Angeles Computer Science Department
CSM51A/EEM16 Final Exam Winter Quarter 2016 March 16th 2016
This is a closed book exam. Absolutely nothing is permitted except pen, pencil and eraser to write your solutions. Any academic dishonesty will be prosecuted to the full extent permissible by university regulations.
Time allowed 180 minutes.
Problem (possible points)
Points
1 (20)
2 (20)
3 (20)
4 (20)
5 (20)
Total (100)
Problem 1 (20 points)
Using at most 1 JK flip-flop, at most 1 SR flip-flop, and at most 8 D flip-flops, design a system as specified below. You may use any gates to implement your combinational logic.
Input set: {0,1}
Output: 1, if x(t, t-3)=11-0, x(t-4, t-7)=1-10 or 0-0-, x(t-8, t-11)=1001
0, otherwise
For example, for the given input sequence x(t, t-11)=110010101001, output is 1. For the input sequence x(t, t-11)=101001011001, output is 0.
Problem 1) Extra Page
Problem 2 (20 points)
Seven 4-bit positive numbers are given: A, B, C, D, E, F, G. Among the seven numbers, three of them are equal and the rest are not. Find the sum of the four numbers that are not equal. Use shift registers (as few and as small as possible), one 2-bit comparator, one 2-bit adder, and any other combinational logic. You are not allowed to use the combinational logic to implement any extra comparators or adders.
A 2-bit comparator compares two 2-bit numbers. A 2-bit adder adds two 2-bit numbers.
For example, A=B=C=0001, D=0010, E=0011, F=0100, G=0101. The system should output D+E+F+G=1110.
Problem 2) Extra Page
Problem 3 (20 points)
Two synchronized binary streams: a and b are given. Design a system that outputs 1 only when pattern P is detected in stream a. Pattern P is initially set to be “1001”, and is updated based on the following rules.
t denotes the earliest clock cycle when pattern P is detected in stream a. Then pattern P is updated to the most recent 4 bits in stream b at time t: P = b(t–3, t). The detection of the updated pattern P starts from clock cycle t+1 in stream a.
Use shift registers (as few and as small as possible) and 4-data input multiplexers (as few and as small as possible) to implement your system.
For example:
In clock cycle t=8, pattern 1001 is earliest detected in stream a. Your system outputs 1 and P is updated to b(5,6,7,8)=1110. Starting from clock cycle 9, in clock cycle t=11, pattern 1110 is earliest detected in stream a. Your system outputs 1 and P is updated to b(8,9,10,11)=0000. Then starting from clock cycle 12, in clock cycle t=19, pattern 0000 is earliest detected in stream a. Your system outputs 1 and P is updated to b(16,17,18,19)=1010. The above process continues infinitely.
cycle
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
a
0
0
1
1
1
0
0
1
1
1
0
0
0
1
1
0
0
0
0
1
b
0
1
0
1
1
1
1
0
0
0
0
0
1
1
1
1
0
1
0
1
Problem 3) Extra Page
Problem 4 (20 points)
Using the provided architecture below, implement the following program. (CLL0 is the write signal to LL0).
Operation
Op-code
Description
ADD
001
𝑧=𝑥+𝑦
SUB
011
𝑧=𝑥−𝑦
NEG
111
𝑧 = −𝑥
ZERO
000
𝑧=0
INCR
100
𝑧=𝑥+1
DECR
010
𝑧=𝑥−1
statement 1 : a = b + c; statement 2 : d = a + e; statement 3: f = a + c; statement 4 : g = f – d; statement 5 : h = g + I;
Software-based Design
R3
R2
R1
R0
RR3
RR2
RR1
RR0
L3
L2
L1
L0
CL3 CL2 CL1 CL0
ML 2
F2
3
CLL0
F1
3
CR3
CR2
CR1
CR0
MR 2 ALU
MUX
ALU
CRR3 CRR2 CRR1 CRR0
MRR 2 MUX
FSM
CLB
counter
MUX
LL0
F1, F2,
ML, MR, MRR,MLL, CL0-3, CR0-3, CLL0, CRR0-3
Problem 4) Extra Page
Problem 5 (20 points)
Design a modulo-11 up/down counter using a regular modulo-16 counter and any combinational logic. The modulo-11 up/down counter has four modes; count up by 1, count up by 2, count down by 1, and no count. A formal description of the modulo-11 up/down counter is shown below.
Inputs: ctrl_0, ctrl_1 ∈ {0, 1} State/Output: s ∈ {0, 1, …, 10}
The state transition function is defined as:
ì s(t) if ctrl_0= 0 and ctrl_1= 0
ï (s(t)+1)mod11 if ctrl_0= 0 and ctrl_1= 1 s(t+1)=í (s(t)+2)mod11 ifctrl_0=1andctrl_1=0
ï
(s(t)-1)mod11 ifctrl_0=1andctrl_1=1 î
You can assume that -1 mod 11 = 10.
Problem 5) Extra Page