Comp 260 SAMPLE FINAL

```Comp 260 SAMPLE FINAL
December 6, 2002
Dr. John G. Del Greco
Name
Instructions. Please show your work to ensure full credit. This test is worth 100 points and 30% of the
1. Do the following base conversions and arithmetic operations.
(a) Convert the base-10 number 53 to binary.
(b) Convert the binary number 0 1 1 0 0 1 1 1 0 1 0 1 0 0 1 1 to hexadecimal.
(c) Convert the octal number 3 7 1 5 2 6 3 4 7 7 to hexadecimal.
(d) Multiply the two hexadecimal numbers AB and CD. Do not convert to base 10 Þrst.
(e) Subtract the following two (unsigned) octal numbers.
(6 1 7 2 2 0)8
− (2 4 1 1 3 1)8
2. A combinational circuit is used to control a 6-segment LED (Light Emitting Diode) display of directional
and other symbols as shown below. (1000 represents the ‘+’ sign, 1001 represents the ‘-’ sign, 1010
represents a diamond and 1011 represents all segments illuminated). The circuit has four binary
inputs x1 , x2 , x3 , and x4 , and six binary outputs a, b, c, d, e and f. The string x3 x2 x1 x0 represents
one of the 12 symbols. (For example, 0101 represents the direction ‘SW’.) The circuit works as follows.
If 0011 is input (representing the direction ‘SE’), then b = c = d = 1 indicating that the corresponding
segments are to be illuminated whereas a = e = f = 0 indicating these segments are to be darkened
(a) If 0100 is input (direction ‘S’), determine each of the following outputs.
1.
2.
3.
4.
5.
6.
a=
b=
c=
d=
e=
f=
(b) Complete the truth table for the output b. The truth table has 16 lines although some of them
will result in ‘don’t care’ conditions.
x3
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
x2
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
x1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
x0
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1
b
X
X
X
X
(c) Find a minimal sum-of-products (SOP) form for the output b.
x01 x00
x03 x02
x03 x2
x01 x0
x1 x0
x1 x00
x3 x2
x3 x02
(d) Find a minimal sum-of-products (SOP) form for the output f .
x01 x00
x03 x02
x03 x2
x01 x0
x1 x0
x1 x00
x3 x2
x3 x02
(e) Using a decoder and OR gates, construct a ROM for the outputs a, c, and d. Use array notation
3. A certain sequential circuit contains a JK ßip-ßop A, a T ßip-ßop B, a single input x, and a single
output z. The input equations for the two ßip-ßops are given below.
JA = B0
KA = 1
TB = xA00
z = x0 B0 + xA00
(a) Draw the circuit diagram.
(b) Derive the next-state equation for the A ßip-ßop. Simplify completely.
(c) Complete the state table for the B ßip-ßop. (Hint: First derive the characteristic equation of
the B ßip-ßop.)
A0 B0 x B
0
0
0
0
0
1
0
1
0
0
1
1
1
0
0
1
0
1
1
1
0
1
1
1
4. A certain Mealy sequential circuit outputs a 1 if and only if there have been four or more consecutive
ones or two or more consecutive zeros input to the circuit. A partial drawing of the state diagram is
given below. No more states are needed, just arcs. Complete the drawing of the diagram.
5. Consider the following state diagram for a certain sequential circuit having one input x and one output
z. The circuit is to be designed using two D ßip-ßops A and B. (The two-bit number inside each node
is the current state A0 B0 .)
(a) Complete the state table of the circuit.
A0
0
0
0
0
1
1
1
1
B0
0
0
1
1
0
0
1
1
2
x
0
1
0
1
0
1
0
1
A
B
z
(b) Find a minimal SOP form for DA .
A00
B00 x0
B00 x
B0 x
B0 x0
B00 x0
B00 x
B0 x
B0 x0
B00 x0
B00 x
B0 x
B0 x0
A0
(c) Find a minimal SOP form for DB .
A00
A0
(d) Find a minimal SOP form for z.
A00
A0
(e) Draw the circuit diagram for this sequential circuit.
6. Consider the following combinational circuit constructed from a 4 − to − 1 multiplexer. The circuit has
inputs x, y and z and a single output A. (The ‘2’ input on the multiplexer is permanently connected
to binary 1.)
z
0
1
1
4-to-1
MUX
A
2
3
s1
s0
x
y
Construct the truth table of the circuit.
x
0
0
0
0
1
1
1
1
y
0
0
1
1
0
0
1
1
3
z
0
1
0
1
0
1
0
1
A
7. Consider the following function table of
output y.
Enable s1
0
X
1
0
1
0
1
1
1
1
some combinational circuit that has seven inputs and one
s0
X
0
1
0
1
x0
X
X
X
X
X
x1
X
X
X
X
X
x2
X
X
X
X
X
x3
X
X
X
X
X
y
hi − Z
x0
x1
x2
x3
Use exactly four three-state buﬀer gates and a single 2 − to − 4 decoder (equipped with an enable
input) to implement this circuit.
8. A certain register A has four control lines numbered c1 , c2 , c3 and c4 . The register is 8 bits wide, and
each bit is constructed with a T ßip-ßop. Assume that only one of the control lines can be equal to 1
at any one time. The input to the ith bit (that is, the ith T ßip-ßop) of the register is given by the
following formula.
¡
¢
(the notation A0i means current content)
TAi = c1 A0i + c2 + c3 xi + c4 A0i ⊕ Ii
The signal xi is deÞned as follows: x0 = 1 and for i ≥ 1, xi = xi−1 A0i−1 . The quantity Ii is the ith bit
of an external data source. Let I denote the vector of these data bits. That is, I = (I7 , I6 , . . . , I0 ).
(a) Draw the diagram for bit 0 of the register.
(b) What happens at the occurrence of a clock pulse when ci = 0 for every i.
(c) Fill in the blanks with one of the choices on the right.
c1 : A ←
(a) A
c2 : A ←
(b) I
c3 : A ←
(c) 0
(clear A)
c4 : A ←
(d) A + 1
(increment A)
9. A certain RAM has 8M words each having 32 bits.
(a) How many address bits are needed to read and write a RAM of this size?
(b) How wide (in bits) are the Data In and Data Out lines on this RAM?
(c) What is the memory capacity of this RAM in bytes?
(d) Suppose the RAM is to be constructed out of 128K × 32 RAM chips. How many chips are needed
to build the RAM?
(e) What size decoder is needed to generate the Chip Select signals to the rows of chips in the RAM?
10. Suppose that A and B are n-bit registers. Consider the following register transfer statements.
yz : B ← A
yz 0 : B ← A ⊕ C
(load B with A exclusive-NOR C)
Construct the hardware to implement these two register-transfer statements. Use three-state buﬀer
gates as part of your design. Make sure to label all your wires and components.
11. Consider the ALU described in class. For each operation listed below, write down the appropriate
ALU control signals that are needed to implement that operation. For example, if the operation is
4
AC ← AC + bus, the correct answer would be 1010XX0. If the operation cannot be implemented in
one clock period, write ‘NOT POSSIBLE’.
Operation
AC ← AC
AC ← 0
AC ← AC − bus
AC ← AC + 1
AC ← bus
AC ← AC ⊕ bus
AC ← AC ∧ bus
Description
complement AC
clear AC
subtract bus from AC
increment AC
exclusive-NOR AC with bus
OR AC with bus
ALUS [1...7]
12. For each of the following operations, formulate a sequence of instruction codes for that operation. For
example, for the operation ‘zero out the R register’, a correct answer would be 0BH (clear AC) followed
by 03H (move AC to R). You must only use the 16 instructions of the computer designed in class!
(a) do nothing for four clock periods
(b) multiply AC by 5 keeping the result in AC
(c) put a 1 into location 34A6H, a 2 into location 34A7H and a 3 into location 34A8H
(e) switch the contents of AC and memory location 0005H (You may use location 0000H as a temporary storage location.)
(a) The bus is 16 bits wide, but some of the registers, like DR, are only 8 bits wide.
register is placed on the bus, what bus lines are used?
If an 8-bit
(b) Write a boolean expression for the signal T RBU S that enables/disables the buﬀer gates connected
to the outputs of the T R register.
(c) Write a boolean expression for ARLOAD that controls when the AR register is loaded.
(d) Suppose that the clock period of the computer is 10ns. (ns = nanoseconds). How long would it
take for the ADD instruction to be fetched and executed on the computer?
14. Consider the following fragment of code for the computer designed in class.
ORG
DB
DB
DB
LDAC
MVAC
LDAC
XOR
NOT
STAC
END
0020H
AAH
55H
00H
0020H
0021H
0022H
(a) Write down the assembled code for the fragment (in hexadecimal) that the assembler would
5
output.
Location
0020H
0021H
0022H
0023H
0024H
0025H
0026H
0027H
0028H
0029H
002AH
002BH
002CH
002DH
002EH
Instruction Code or Data
(b) Describe in one or two sentences what this fragment of code is doing. Use words, not symbols!
(c) What is the content (in hexadecimal) of the following registers and memory locations after the
code fragment is executed? If the content cannot be determined, write ‘?’.
1.
2.
3.
4.
5.
6.
AC =
AR =
TR =
DR =
Z =
Location 0022H =
6
```