課程名稱︰計算機概論 課程性質︰選修 課程教師：莊永裕 開課學院：電資學院 開課系所︰資工系 考試日期（年月日）︰2015.11.03 考試時限（分鐘）：180分鐘 試題 : ┌─────────────────────────────────────┐ │CSIE 1000 Introduction to Computers National Taiwan University│ │Fall 2015 Department of CSIE│ │ │ │ Midterm Exam │ │ November 3, 2015 (total: 105 points) │ └─────────────────────────────────────┘ ˙ Use * to represent the irrelevant values and the values not specified in the question. ˙ Feel free to use circuits introduced in the class. The following are some circuits that you may need. Feel free to change the orientations of the gates, the positions of inputs and outputs and the number of bits. On the other hand, for any circuit that was not introduced in the class, you have to implement it before using. ˙ Note that you do not need to really wire up all components as long as you name the signals clearly. Circuits: http://i.imgur.com/CoOqHbj.png 1. (8%) What are the 8-bit 2's complement representations of the following decimal numbers? Please give both their binary and hexadecimal representations. a. 39 b. -19 _ 2. (10%) Show that (a) x · (x + y) = x and (b) (x + y)(x + y) = y using Boolean algebra rules (not truth table). 3. (8%) Implement a circuit to realize the 3-bit mod3 function. The circuit has a 3-bit input X = X_2 X_1 X_0 and a 2-bit output Y = Y_1 Y_0 satisfying Y = X%3. For example, if X is 101, then Y is 10 because 5%3 = 2. Write down the truth tables and its corresponding logic expressions for Y_1 and Y_0. 4. (15%) Design a two-bit multiplier which accepts two 2-bit inputs, X = X_1 X_0 and Y = Y_1 Y_0, and outputs a 4-bit number Z = Z_3 Z_2 Z_1 Z_0, where Z is the product of X and Y, i.e. Z = X × Y. (1) Write down the truth tables for Z_3, Z_2, Z_1, Z_0. (2) What are their sum of products expressions? (Do not simplify them.) (3) Use K-map to obtain the simplified expressions if possible. 5. (10%) In Hack ALU, the following configurations of inputs are used for -x and x + 1. Explain why they work. ────────────────── zx nx zy ny f no out ────────────────── 0 0 1 1 1 1 -x 0 1 1 1 1 1 x+1 ────────────────── 6. (12%) Draw the required datapath on the datatpath sheet for (a) instruction fetch and (b) the set of instructions {"xor", "store", "branch zero", "jump and link"} (without instruction fetch). Only draw the necessary part but not the whole TOY datapath. Add multiplexers only if necessary. Remember to sign your name and return the datatpath sheet with your answer sheet. Datatpath Sheet: http://i.imgur.com/iuVmv03.png 7. (12%) Refer to the TOY architecture (Figure 3; note that the numbering could be different from the lecture), please specify the operations of MUX_PC, MUX_MEM, MUX_REGR, MUX_ALU, MUX_REGW, WRITE_REG, WRITE_MEM, and ALU_OP during the execution stage for the instructions "xor", "store indirect" and "branch if zero". As an example, for "jump and link", they would be MUX_PC = 0, MUX_MEM = *, MUX_REGR = *, MUX_ALU = 1, MUX_REGW = 01, WRITE_REG = 1, WRITE_MEM = 0, and ALU_OP = *. (For ALU_OP, you only need to specify 3-bit ALU_control as specified in Figure 3.) Figure 3: http://i.imgur.com/BmQTGVC.png 8. (15%) Assume that you are designing a processor for the Tic-Tac-Toe game in which two players, O and X, take turns marking the spaces in a 3×3 grid (Figure 1(a)). The player who first succeeds in placing three respective marks in a horizontal, vertical, or diagonal row wins the game. One of the key components for the processor would be a sequential circuit which stores the current configuration of the 3×3 grid. A grid cell could be in one of the three statuses: unoccupied, occupied by O and occupied by X, and thus can be represented by 2 bits. Design a (3×3)×2 memory chip for the purpose. The chip has two 2-bit addresses for the position of the cell, (x, y), a 2-bit W_data input and a 2-bit output R_data along with the clock and write enable. Figure 1(b) sketches its interface. You can assume that the inputs are all valid. For example, both X and Y are within the set {0, 1, 2}. Note that there are many design options. As long as the design works properly, it is a correct one. Figure 1: http://i.imgur.com/Khu5MQ6.png 9. (15%) What is output of the following TOY program? How many cycles does it take from starting to halting? 00: 000F 01: 0009 10: 8A00 11: 8B01 12: 2EAB 13: CE19 14: DE17 15: 2BBA 16: C012 17: 2AAB 18: C012 19: 9AFF 1A: 0000 Figure 2: TOY reference card. ┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐ │15│14│13│12│11│10│ 9│ 8│ 7│ 6│ 5│ 4│ 3│ 2│ 1│ 0│ ┌────┼─┴─┴─┴─┼─┴─┴─┴─┼─┴─┴─┴─┼─┴─┴─┴─┤ │Format 1│ opcode │ dest d │ source s │ source t │ ├────┼───────┼───────┼───────┴───────┤ │Format 2│ opcode │ dest d │ addr │ └────┴───────┴───────┴───────────────┘ ┌─┬────────┬──┬─────────────┐ │＃│ Operation │ Fmt│ Pseudocode │ ├─┼────────┼──┼─────────────┤ │0:│halt │ 1 │exit(0) │ ├─┼────────┼──┼─────────────┤ │1:│add │ 1 │R[d] ← R[s] + R[t] │ ├─┼────────┼──┼─────────────┤ │2:│subtract │ 1 │R[d] ← R[s] - R[t] │ ├─┼────────┼──┼─────────────┤ │3:│and │ 1 │R[d] ← R[s] & R[t] │ ├─┼────────┼──┼─────────────┤ │4:│xor │ 1 │R[d] ← R[s] ^ R[t] │ ├─┼────────┼──┼─────────────┤ │5:│shift left │ 1 │R[d] ← R[s] << R[t] │ ├─┼────────┼──┼─────────────┤ │6:│shift right │ 1 │R[d] ← R[s] >> R[t] │ ├─┼────────┼──┼─────────────┤ │7:│load addr │ 2 │R[d] ← addr │ ├─┼────────┼──┼─────────────┤ │8:│load │ 2 │R[d] ← mem[addr] │ ├─┼────────┼──┼─────────────┤ │9:│store │ 2 │mem[addr] ← R[d] │ ├─┼────────┼──┼─────────────┤ │A:│load indirect │ 1 │R[d] ← mem[R[t]] │ ├─┼────────┼──┼─────────────┤ │B:│store indirect │ 1 │mem[R[t]] ← R[d] │ ├─┼────────┼──┼─────────────┤ │C:│branch zero │ 2 │if (R[d] == 0) pc ← addr │ ├─┼────────┼──┼─────────────┤ │D:│branch positive │ 2 │if (R[d] > 0) pc ← addr │ ├─┼────────┼──┼─────────────┤ │E:│jump register │ 1 │pc ← R[t] │ ├─┼────────┼──┼─────────────┤ │F:│jump and link │ 2 │R[d] ← pc; pc ← addr │ └─┴────────┴──┴─────────────┘ Register 0 always 0. Loads from mem[FF] from stdin. Stores to mem[FF] to stdout. --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.163.254.247 ※ 文章網址: https://webptt.com/m.aspx?n=bbs/NTU-Exam/M.1461561924.A.643.html ※ 編輯: rod24574575 (1.163.254.247), 04/25/2016 13:27:36