課程名稱︰計算機概論 課程性質︰選修 課程教師︰莊永裕 開課學院：電資學院 開課系所︰資工系 考試日期（年月日）︰2014.11.11 考試時限（分鐘）：180 是否需發放獎勵金：是 （如未明確表示，則不予發放） 試題 : ┌─────────────────────────────────────┐ │CSIE 1000 Introduction to Computers National Taiwan University│ │Fall 2014 Department of CSIE│ │ │ │ Midterm Exam │ │ November 11, 2014 (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. 圖：http://i.imgur.com/U37j02F.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. 45 b. -28 2. (8%) The INC circuit adds one to the input. The 4-bit INC circuit accepts a 4-bit input X and outputs a 4-bit Y so that Y = X + 1 (please ignore the overflow issue). Please design a 4-bit INC circuit using only 1-bit half adders. 3. (18%) Figure 1(a) shows a 2-bit comparator which has two 2-bit unsigned-integer inputs, X = X_1 X_0 and Y = Y_1 Y_0, and three output bits G, E, L for the conditions of X > Y, X = Y and X < Y, respectively. (a) Write down the truth table for the three boolean functions G, E and L. (6%) (b) Write down their SOP forms. (6%) (c) Use K-map to simplify their expressions if possible. (6%) No need to draw their circuit diagrams for this question. Figure 1: http://i.imgur.com/ua1VgJX.png 4. (8%) Design a 4-bit comparator as shown in Figure 1(b). Hint: Use the 2-bit comparator from the last question. Note that even if you do not answer the above question or your design is wrong, you can still use 2-bit comparators as black boxes in your design. 5. (12%) Design a circuit to implement the following pseudo code. Here, the variables A, B, X, Y, Z are registers containing 4-bit unsigned integers. Hint: in addition to registers, you will need a 4-bit comparator and some multiplexers. Similarly, you can just use 4-bit comparators as black boxes in this question no matter whether you answer the above question correctly. if (A < B) then Z := X + A else if (A == B) then Z := X + B else Y := A + B 6. (12%) In Hack ALU, the following configurations of inputs are used for (x + 1), (y - x) and (x | y). Explain why they work. ─────────────────── zx nx zy ny f no out ─────────────────── 0 1 1 1 1 1 x + 1 0 0 0 1 1 1 y - x 0 1 0 1 0 1 x | y ─────────────────── 7. (12%) Draw the required datapath on the datatpath sheet for (a) instruction fetch and the set of instructions {"jump register", "jump and link"}; and (b) the set of instructions {"sub", "load", "store indirect", "branch zero"} (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/vexG8Zy.png 8. (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 "add", "load indirect" and "jump register". 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, 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/AQgXLKa.jpg 9. (15%) Binary-coded decimal (BCD) is a binary encoding of decimal numbers where each decimal digit is represented by 4 bits. For example, the bit string 0100 1001 will be interpreted as 49 in decimal. In this question, you are asked to design a 2-digit decimal counter (2DC) which will count between 00 to 99 as shown in Figure 1(c). It has two inputs: a 2-bit op and an 8-bit D_in (representing a 2-digit BCD). You can assume that the input D_in is always valid. 2DC has two 4-bit outputs, D_1 and D_0, each for a decimal digit. They can be connected to two 7-segment displays as the outputs. You can use the 7-segment display decoder in homework #1 to control the displays. The 2DC counter has the following operations. Hint: implement 2DC using two 4-bit registers, one for a decimal digit. ──────────────────── op[1] op[0] operation semantics ──────────────────── 0 0 reset count = 0 0 1 set count = D_in 1 0 inc INC(count); 1 1 inc DEC(count); ──────────────────── INC(count) ≡ if (count < 99) count++; DEC(count) ≡ if (count > 0) count--; 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.160.228.135 ※ 文章網址: http://webptt.com/m.aspx?n=bbs/NTU-Exam/M.1416537600.A.1C8.html