课程名称︰计算机组织与组合语言 课程性质︰资工系必修 课程教师︰庄永裕 开课学院：电资学院 开课系所︰资讯工程学系 考试日期（年月日）︰97年10月27日(2008.10.27) 考试时限（分钟）：两个多小时 是否需发放奖励金：是 （如未明确表示，则不予发放） 试题 : 除了考题还有另外一张拿来画第6题的答案卷，上面有附上第9题拿来解释stack的图， 还有一个TOY reference card。 就是TOY machine的machine code的format表， 和opcode对应的operation、format、pseudocode的表。 ˙ Use * to represent the irrelevant values and the values not specified in the question. ˙ 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. (8%) What are the 8-bit 2's complement representations of the following decimal numbers? Please give both their binary and hexadecimal representations. a. 97 b. -21 _ 2. (10%) Prove (a) A(A + B) = AB and (b) A + AB = A + B both algebraically and using the truth table. 3. (10%) Implement a circuit to realize the divided-by-2 and divided-by-3 functions. The divided-by-2 function D2 outputs 1 if the input X can be divided by 2, that is, X%2 = 0. For example, if X is 101, D2 = 0 because 5%2 ≠ 0. Similarly, D3 output 1 if X%3 = 0; 0 otherwise. Assume 3-bit inputs X = X2 X1 X0. Write down the truth table, corresponding logic expressions and logic gate inplementations for D2 and D3. 有个Figure 1: Encoder, sorter and max-min. 4. (10%) A 4-to-2 encoder (Figure 1(a)) has four inputs A3, A2, A1, A0 and two outputs Z1, Z0. Only one of the four inputs can be 1 at a time. Assume that Ai is on, the output (Z1, Z0) will correspond to the binary representation of i. For example, when input A2=1, Z1 Z0 = 10. Write down the truth table for the 4-to-2 encoder and implement it with logic gates. 5. (15%) (a) A 4-bit 2-sorter(Figure 1(b)) has two 4-bit inputs A, B and two 4-bit outputs X, Y. The inputs A and B are unsigned integers. The output X is the larger one of A and B and Y is the smaller on of A and B. Design a 4-bit 2-sorter. (b) A 4-bit 3-sorter (Figure 1(c)) has three 4-bit inputs A, B, C and three 4-bit outputs X, Y, Z, where X, Y and Z are the result of sorting A, B, C so that X ≧ Y ≧ Z. Use 4-bit 2-sorters to composite a 4-bit 3-sorter. (c) A 9-maxmin(Figure 1(d)) has nine 4-bit unsigned inputs Xi, i=1..9 and two 4-bit outputs MAX and MIN where MAX = max(Xi). and MIN = min(Xi). Implement 9-maxmin. 有个Figure 2: TOY architecture. 6. (10%) Draw the required datapath on page 4 for instruction fetch and the set of instructions {"xor","store","branch zero" and "jump and link"}. Only the necessary part but not the whole TOY datapath. Add multiplexers if necessary. Remember to return page 4 with your answer sheet. 7. (12%) Refer to the TOY architecture (Figure 2), 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 "and", "load addr", "store indirect" and "branch zero". For example, the answer for "jump and link" would be MUX_PC = 1, MUXMEM = *, MUX_REGR = *, MUX_ALU = 1, MUX_REGW = 01, WRITE_REG = 1, WRITE_MEM = 0, ALU_OP = *. 8. (10%) Write a TOY program to print out the positive powers of 2 that can be represented by TOY, 1, 2, 4, 8, ... 9. (15%) Design a circuit to implement a 16 * 8 stack (Figure 3(a)). There are 16 words in the stack and each word is 8-bit. A stack is a data structure based on the principle of Last In First Out(LIFO). Two operations can be used to change the content of the stack. "Pop" removes an element from the top and 'push' adds an element at the top. A pointer "top" always points to the top valid element of the stack. For example, Figure 3(b) shows an empty stack. Initially, the top points to 1111 since the stack is empty and there is no valid element. In Figure 3(c), "push 1" will add an element into the stack and the top is updated to 0000, the address of the first valid element. In Figure 3(d), "push 2" will add an element into the stack and the top is updated to 0001. In Figure 3(e), "push 3" will add an element into the stack and the top is updated to 0010. In Figure 3(f), "pop" will remove the top element and the top is updated to 0001. Two 1-bit inputs W and op determines the operation of the stack circuit as the following. There are four operations. Other than push and pop, "read" reads the content of the top element without modifying the stack. "top" reads the content of the top pointer. In addition, the stack has an 8-bit input as the W Date for specifying the element to be written with the push command. There is also an 8-bit output R data for the data to be read out. (Ignore the issue of wrap-around.) W op operation semantics 0 0 read the content of stack[top] can be read from "R data" 0 1 top the content of top can be read from "R data" 1 0 push top++; write the "W data" to stack[top]; 1 1 pop top--; 另外，是openbook的。 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 61.31.138.32 ※ 编辑: a127a127 来自: 61.31.138.32 (11/17 12:21) 感谢补充<(_ _)> ※ 编辑: a127a127 来自: 219.81.146.231 (11/18 01:31)