COMP-273: MidTerm Examination Date: Thursday, October 22nd, 2020
Note: For this examination you are allowed to use a crib sheet which is no more than 2 single-sided pages in length. On the crib sheet you can write down things that you found difficult to remember. You should not consult anyone else, or discuss the con- tents of this exam, during the 24 hr period in which the exam is open.
Be sure to read through the entire question sheet and to pace yourself accordingly. There are 4 questions in all. Make sure to show your working and to comment any code you write. When in doubt, state any assumptions you have made. You can write on sheets of paper or use a tablet if you prefer, so long as your writing is legible. Scan your answers, together with your crib sheet, as a single PDF when you are done. Your PDF should be uploaded to the “Midterm Examination” folder, under the “Assignments” tab on mycourses. Remember that you have 4.5 hrs from the time that you have begun the midterm to complete the upload.
Question 1 (MIPS disassembly). [25%]
Copyright By PowCoder代写 加微信 powcoder
Consider the following snippet of sample code, viewed in MARS. The left hand column represents the address, in hexadecimal, of each MIPS instruction. The middle column is the representation of each instruction as a 32 bit number (written in hexadecimal). The right hand column is the corresponding MIPS instruction. Your task is complete the entries in the right hand column by parsing each instruction appropriately. In your final result you can represent registers by their numerical values but remember to assign labels where appropriate.
For this example, the following information may be useful. add has a function code of 2016. and has a function code of 2416. addi has an opcode of 816. or has a function code of 2516. sll has a function code of 016. slt has a function code of 2a16. bne has an opcode of 0516. beq has an opcode of 0416. jal has an opcode of 0316. j has an opcode of 0216. jr has a function code of 0816.
[0x00400024] 0x00004020 add $8, $0, $0
[0x00400028] 0x0005482a …
[0x0040002c] 0x11200004 …
[0x00400030] 0x01044020 …
[0x00400034] 0x20a5ffff …
[0x00400038] 0x0810000a …
[0x0040003c] 0x01001020 …
[0x00400040] 0x03e00008 jr $31
Question 2 (Circular Shifts and Boolean Algebra). [25%]
Consider a digital circuit that has five inputs, S1, S0, A2, A1, A0 Here S1S0 represents a 2’s comple- ment number N1 and A2A1A0 represents a 3 bit input string. The circuit has 3 outputs F2,F1,F0 which are to be interpeted as a 3 bit output string F2F1F0. The circuit has the following behaviour:
• When N1 = -2, the output string is obtained by circularly shifting the input string twice to the left.
• When N1 = -1, the output string is obtained by circularly shifting the input string once to the left.
• When N1 = 0, the output string is obtained by circularly shifting the input string once to the right.
• When N1 = 1, the output string is obtained by circularly shifting the input string twice to the right.
a) Draw a truth table for the outputs F0, F1, F2 in terms of the inputs S1, S0, A2, A1, A0. [10 marks] b) Give a sum-of-products (disjunction of conjunctions) expression for each of the outputs F0, F1, F2,
based on the truth table you have drawn. [5 marks]
c) Give a product-of-sums (conjunction of disjunctions) expression for each of the outputs F0, F1, F2, based on the truth table you have drawn. [5 marks]
d) Try to simplify the sum-of-products expressions in part b) using the laws of Boolean algebra. [5 marks]
Question 3 (MIPS). [25%]
How many slices of pizza can a person obtain by making n straight cuts with a pizza knife? Or, more academically: What is the maximum number Ln of regions defined by n lines in the plane? If you start looking at the small cases you should be able convince yourself via a proof by induction that:
Ln = Ln−1 + n, for n > 0.
Write a simple subroutine called “pizza” to implement this algorithm, but do not use recursion. The subroutine has a single input argument: $a0 → n, and it returns the answer via a single return value in the appropriate register. You can assume that the input argument by which the subroutine is first called is an unsigned integer, i.e., it is non-negative. Use proper register conventions and comment your code.
Question 4 (Sequential Circuits – Shift Registers). [25%]
You are given 4 rising edge triggered D flip-flops, where each flip-flop has two outputs Q and Q ̄. These flip-flops also have S and R inputs, which can be used on start up to initialize the output Q to a 1 or a 0, respectively, when the operation begins. (The S and R inputs are simply used to initialize the flip-flops, and they have nothing to do with an RS latch.)
Using a clock signal, a multiplexor with a single control signal S and any additional circuitry necessary, design a circuit that has the following behaviour. If S = 0 it should implement a circular shift to the right. If S = 1 it should implement a circular shift to the left. A circular shift has the property that the binary digit shifted out at one end is shifted in at the other end.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com