課程名稱︰計算機組織與組合語言 課程性質︰必修 課程教師︰莊永裕 開課學院：電資 開課系所︰資工 考試日期（年月日）︰ 2009/11/9 14:20~17:20 考試時限（分鐘）： 180min 是否需發放獎勵金：是 試題 : It's a "open-book" exam. Use * to represent the irrelevant values and the values not specified in the questions. Please use the following notations for logic gates. Feel free to change the orientations of the gates and the positions of inputs and outputs. You are free to use other circuits. However, if they are not introduced in the class, you have to implement them before using them. + AND/OR/NOT + k-bit full adder + k-wide n-to-1 multiplexer + N ×K register + k-bit comparator 1. (10%) What are the 8-bit 2's complement representations of the following decimal numbers? Please give both their binary and hexadecimal representations. a. 89 b. -45 _ 2. (10%) Prove that (a) x．(x + y) = x (b) (x + y)(x + y) = y using Boolean algebra (not truth table). 3. (20%) Implement a circuit 1cnt3 to count 1-bits in a 3-bit input. The 1cnt3 circuits accepts a 3-bit input X=X2X1X0 and outputs a 2-bit output C=C1C0 if there are C 1-bits in X. For example, if X=101, C=10 since there are two 1-bits in X. (a) Write down the truth table (5%), the corresponding logic expression (5%) and logic gate implementation (5%) for 1cnt3. (b) Implement 1cnt7 which accepts a 7-bit input X=X6X5...X0 and outputs C=C2C1C0, the number of 1-bits in X (5%). 4. (20%) Design a circuit to implement a 16 ×8 queue (Figure 1(a)). There are 16 words in the queue and each word is 8-bit. A queue is a data structure based on the principle of First-In-First-Out (FIFO). Pointers front and end point to the head and the tail of the queue. Two operations can be used to change the content of the queue. Dequeue removes and element from the front and enqueue inserts an element at the end. For example, Figure 1(b) shows an empty queue. Initially, both pointers are 0x0000. In Figure 1(c), enqueue 1 inserts an element '1' into the queue, and end is updated to 0x0001, the address of the next available slot for insertion. In Figure 1(d), enqueue 2 inserts an element '2' into the queue and end is updated to 0x0010. In Figure 1(e), dequeue removes it from the queue and update front as 0x0001, the next valid element. Two 1-bit inputs W and op determine the operation of the queue circuits as the following. Other than dequeue and enqueue, lenth return the number of valid elements in the queue and read reads the content of the front element without modifying the queue. Note that the pointers could be wrapped around. you need to take care of this, but you can assume that the number of elements in the queue is always less than 16. The queue also has an 8-bit input D-in, the element to be inserted and an 8-bit output D-out. (You can assume that both front and end are initialized as 0x0000.) W op operation semantics 0 0 length D-out = number of elements in the queue. 0 1 read D-out = queue[front] 1 0 dequeue front++; 1 1 enqueue queue[end] = D-in; end++; Figure 1: Queue. (a) 16 ×8 queue. ┌──────┐ │ 16 ×8 │ │ queue │ ─┤D-in D-out├─ 8 │ │8 │Clock W op│ └───┬─┬┘ │ │ (b) empty queue front→0 : end →1 : 2 : 3 : : : F : (c) enqueue 1 front→0 : 1 end →1 : 2 : 3 : : : F : (d) enqueue 2 front→0 : 1 1 : 2 end →2 : 3 : : : F : (e) dequeue 0 : front→1 : 2 end →2 : 3 : : : F : 5. (10%) The "jump register" instruction in the original TOY machine uses Rd as the register to hold the address to jump to. Explain why it is wrong and how to fix this. 6. (10%) Draw the required datapath on the datapath sheet for (a) instruction fetch and (b) the set of instructions {"add", "store indirect" and "jump register"}. Only draw the necessary part but not the whole TOY datapath. Add multiplexers only if necessary. Remember to sign your name and return the datapath sheet with your answer sheet. 7. (20%) Convert the following TOY assembly code into TOY machine code. Remember that the first instruction should start at the address 0x10. What is the program's output? How many cycles does the program take from staring to halting? (Cycles means the times of instruction or clock.) A DW 15 B DW 9 ld RA, A ld RB, B L1 sub RE, RA, RB bz RE, L3 bp RE, L2 sub RB, RB, RA bz R0, L1 L2 sub RA, RA, RB bz R0, L1 L3 st RA, 0xFF halt --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 123.204.86.9