CS 251, Fall 2021, Assignment 1.0.0
Due Monday, September 27th, 10:00 PM;
No lates accepted
You are required to read, complete and sign, and submit (as well as follow)
the following statement of Academic Integrity.
Statement of Academic Integrity for CS 251 Winter 2021, Assignment 1
I declare the following statements to be true:
• I have not used any unauthorized aids.
• I recognize that while I can discuss the questions in this assignment on Piazza and
other forums with the instructors and with other students in the class, the write up
that I am submitting is my own.
• I am aware that misconduct related to course work can result in significant penalties,
including failing the course and suspension (this is covered in Policy 71:)
https://uwaterloo.ca/secretariat/policies-procedures-guidelines/policy-71
Student Name:
UW ID#:
Signature:
Date:
1
1. (3 points)
Write an ARM program starting at address 080 that reads the value stored from
memory address 232 into X9 and then adds 2021 to it. The final value is stored back
to memory address 32. You may use register X1 for temporary storage, but you should
not change the value of any other register.
080
084
088
092
2
2. (8 points)
Write an ARM assembly program starting at address 000 to shift the values stored in
an array “left” by one. I.e.,
M [i] = M [i + 1],
where X1 contains the first address to be shifted into and X2 contains the last address to
be shifted into. So for example, if X1 contains “64” and X2 contains “80”, and M[64]=3,
M[72]=7, M[80]=17, M[88]=67, then after executing your program, you should have
M[64]=7, M[72]=17, M[80]=67, M[88]=67. You may assume X2≥X1≥ 0 and that
both X1 and X2 contain multiples of 8. You may use any other registers as temporary
registers, but you should not change the value of registers X1 or X2, and you should
add a comment stating what your temporary registers were used for. Extra lines may
be added if required.
000
004
008
012
016
020
024
028
032
036
040
044
048
052
056
3
3. (8 points) Write your student number here:
(a) (3 points) For 3 inputs A, B, C, construct the truth table for the function F that
is 1 when the binary number ABC is a digit in your student ID. For example, if
your student ID is 20340259, the rows 000, 010, 011, 100, and 101 should be 1,
while the other entries should be 0 (we are ignoring 8’s and 9’s in your student
ID).
A B C F
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
(b) (3 points) Give the unreduced sum of products expression for F :
F =
(c) (2 points) Draw the circuit that implements F from part (b). You should not
reduce the formula or the circuit.
4
4. (8 points)
(a) (6 points) Complete the truth table table for output F in the following circuit,
giving the truth table values for the internal signals A, B, and C and D as
intermediate steps.
C
D
A
X
Y
F
B
X Y A B C D F
0 0
0 1
1 0
1 1
(b) (2 point)
Give a simplified Boolean formula for F in terms of X, Y . Also provide a simplified
Boolean formula for C in terms of X, Y .
F =
C =
5
5. (6 points)
Given the transistor circuit below, complete the table below, determining the internal
resistances for Q1 to Q4 and the final output Z. The transistors Q1 to Q4 resistances
should be High or Low (or ‘H’ or ‘L’). The output Z may be 0, 1, float ‘–’, or short-
circuit ‘*’. You may assume all resistances are accurate when determining the final
output Z.
A B
B
V
A
V
Z
Q1 Q2
Q3 Q4
A B Q1 Q2 Q3 Q4 Z
0 0
0 1
1 0
1 1
6
6. (4 points) In the diagram below are two 4–1 multiplexors with its select lines tied to A
and B (where the select lines that A and B are tied to are swapped in the two figures).
Suppose we want to implement the following function using this multiplexor:
A B F
0 0 0
0 1 1
1 0 0
1 1 1
Label the inputs to each multiplexor D0, D1, D2, D3 so that the output Q is given by
the truth table for F . The labels you may use are 0 or 1.
M
U
X
M
U
X
D0
D1
D2
D3
S1 S0
B A
Q
D0
D1
D2
D3
S1 S0
A B
Q
7
The remaining questions will NOT be used to compute your as-
signment mark; they are included here as additional questions
you may want to try to aid your understanding of the course
material. Solutions to these questions will not be provided.
7. In the diagram below is a 4–1 multiplexor with its select lines tied to A and B. Suppose
we want to implement the following function using this multiplexor:
A B C F
0 0 0 0
0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 1
1 1 1 1
Label the inputs D0, D1, D2, D3 so that the output Q is given by the truth table for
F . The labels you may use are C, C̄, 0, or 1.
M
U
X
M
U
X
D0
D1
D2
D3
S1 S0
B A
Q
D0
D1
D2
D3
S1 S0
A B
Q
8. Draw a CMOS circuit that takes two inputs, A and B, and performs the NOR op-
eration at an output Z. You must only use NMOS and PMOS transistors. Be sure
to clearly indicate a Power connection and grounding of your circuit. You may look
up this configuration on the web, but it must be accurately drawn below. You should
look up ‘CMOS NOR’. The circuit must be implemented with CMOS configurations
as was the NAND operation from class.
8
9. Below is a diagram of a 2× 1 multiplexor taking two 64-bit inputs and pro ducing one
64-bit output. On the right, is the internal configuration of 2 × 1 MUXes that will
implement this operation.
Further down, we have drawn a 16×1 multiplexor taking 16 inputs that are 32-bits each
and producing one 32-bit result. Draw the internal configuration of MUXes that will
implement the 16×1 MUX. You do not need to draw all of the inputs or all the necessary
multiplexors, but you should use (…) where necessary to simplify your diagram. The
number of inputs and the number of multiplexors you use should be clearly marked.
Be sure to label the width of the input lines, the width of the select bits, etc. Also,
be sure to clearly indicate where the select bits feed into each multiplexor. You should
label the inputs to the multiplexors and the bit position clearly using the convention
RXY (for example R20 indicates the zero bit of R2).
9