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