Name Student ID #
First Last
University of California Los Angeles Computer Science Department
CSM51A/EEM16 Final Exam Winter Quarter 2015 March 20th 2015
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)
6 (20)
Total (120)
Problem 1 (20 points)
Use the dedicated register file architecture below to add the first 100 consecutive odd numbers starting after k. The consecutive odd numbers should begin with k+1 if k is an even number, and begin with k+2 if k is an odd number. You may assume that k is an unsigned number that has been preloaded (be clear about which register it is preloaded in). You may use larger register files than those provided, however you must use as few registers as possible.
Operation
Op-code
Description
ADD
001
SUB
011
NEG
111
ZERO
000
INCR
100
DECR
010
Problem 1) Extra Page
Problem 2 (20 points)
You are given the following system of equations:
Design a system which calculates x and y given a, b, c, d, e, and f. You may use any architecture of your choosing. You may also assume that n-bit dividers are available.
Problem 2) Extra Page
Problem 3 (20 points)
Create a system that outputs 4 on every 4th clock cycle, 5 on every 5th clock cycle, 7 on every 7th clock cycle, and 11 on every 11th clock cycle. If the cycle is a multiple of any combination of these periods, output 15. In all other cases, output 0. Use only mod-16 counters (as few as possible) and multiplexers (as few and as small as possible).
For example, here are the first 20 outputs:
Cycle:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Output:
0
0
0
4
5
0
7
4
0
5
11
4
0
7
5
4
0
0
0
15
Problem 3) Extra Page
Problem 4 (20 points)
Four unsigned 4-bit numbers are given: A, B, C, and D. Design a system which sorts the sums of each pair of the numbers in descending order. Each sum should have 5 bits (the most significant bit is the carry out bit), and only consider those sums that are palindromes. Use 1-bit comparators and multiplexers for your combinational logic.
For example, given inputs A=1001, B=0111, C=0101, D=1110, you can verify the following: A+B = 10000
A+C = 01110
A+D = 10111
B+C = 01100 B+D = 10101 C+D = 10011
Since only A+C and B+D are palindromes and B+D > A+C, the system outputs: 10101, 01110.
Problem 4) Extra Page
Problem 5 (20 points)
Five 4-bit positive numbers are given: A, B, C, D and E. Find the sum of the two largest values and the sum of two smallest values. Use shift registers, one 2-bit comparator, one 2- bit adder, and multiplexers to create your solution.
Problem 5) Extra Page
Problem 6 (20 points)
(a) Design a modulo-11 up/down counter using a regular modulo-16 counter and any combinational logic. A formal description of the modulo-11 up/down counter is shown below.
Inputs: countdown, countup ∈ {0, 1}
State/Output: s ∈ {0, 1, …, 10}
The state transition function is defined as:
(s(t) 1) mod 11 if countup 1 and countdown 0 s(t1)(s(t)1)mod11 ifcountup0andcountdown1 s(t) if countup 0 and countdown 0
You can assume that countup = 1 and countdown = 1 never happens and -1 mod 11 = 10.
(b) Using one modulo-11 up/down counter, design a system that outputs 1 if the input stream matches the pattern: x(t-n, t) = 10*1+.
Problem 6) Extra Page