課程名稱︰計算機概論
課程性質︰選修
課程教師：莊永裕
開課學院：電資學院
開課系所︰資工系
考試日期（年月日）︰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.