推 godgunman :好快XD 11/10 03:53
課程名稱︰計算機組織與組合語言
課程性質︰必修
課程教師︰莊永裕
開課學院：電資
開課系所︰資工
考試日期（年月日）︰ 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