CSEE W3827
Fundamentals of Computer Systems
Homework Assignment 1
Solutions
Prof. Stephen A. Edwards
Columbia University
Due September 20th, 2011 at 10:35 AM
Show your work for each problem; we are more interested in how you
get the answer than whether you get the right answer.
This document is formatted for on-screen viewing.
1. What are the values, in decimal, of the bytes
10011100
and
01111000,
if they are interpreted as 8-bit
(a) Binary numbers?
100111002 = 128 + 16 + 8 + 4 = 156;
011110002 = 64 + 32 + 16 + 8 = 120
(b) One’s complement numbers?
−(11000112 ) = −(64 + 32 + 2 + 1) = −99;
011110002 = 64 + 32 + 16 + 8 = 120
(c) Two’s complement numbers?
100111002 = −128 + 16 + 8 + 4 = −100 or
01100011 + 1 = 01100100 = 64 + 32 + 4 = −100;
011110002 = 64 + 32 + 16 + 8 = 120
2. The DEC PDP-8 used 12-bit words.
(a) What were the most negative and most positive decimal
numbers one of its words could represent using two’s
complement?
−211 = −2048 and 211 − 1 = 2047
(b) Assuming a word represented an address in memory, how
many different locations could the PDP-8 address?
212 = 4096
3. Convert the hexadecimal number “DEAD” into
(a) Binary
1101 1110 1010 1101
(b) Octal
157255 (interpret groups of three bits)
(c) Decimal
13 · 163 + 14 · 162 + 10 · 161 + 13 · 160 = 57005
(d) Binary-Coded Decimal
5700510 = 0101 0111 0000 0000 0101BCD
4. Show that 2 + −7 = −5 is also true when done in binary using
(a) Signed-magnitude numbers
0010 + 1111 = −(111 − 010) = −(101) = 1101
Make sure you strip off the sign bits
(b) One’s complement numbers
0010 + 1000 = 1010 = −(0101) (normal binary addition)
(c) Two’s complement numbers
0010 + 1001 = 1011 = −(101) (normal binary addition)
5. Show 42 + 49 = 91 in BCD. Make sure you show when corrections
are necessary to normal binary addition.
0100 0010
+ 0100 1001
1000 1011 The result of normal binary addition
+ 0110 Add 6 since this digit exceeded 9
1001 0001
6. Complete the truth table for the following Boolean functions:
(a) XYZ + XYZ + XYZ
(b) (X + Y)(Y + Z)(X + Z)
X Y Z a b
0 0 0 0 0
0 0 1 0 0
0 1 0 0 1
0 1 1 1 0
1 0 0 0 0
1 0 1 1 1
1 1 0 1 1
1 1 1 0 1
7. Consider the function F, whose truth table is below.
(a) Write F as a sum of minterms and draw
X Y Z F the corresponding circuit.
0 0 0 0 X YZ + X Y Z + X Y Z + X Y Z + X Y Z
0 0 1 1
0 1 0 1 (b) Write F as a product of maxterms and
0 1 1 0 draw the corresponding circuit.
1 0 0 1 (X + Y + Z)(X + Y + Z)(X + Y + Z)
1 0 1 1
1 1 0 0 (c) Complete the Karnaugh map for F as
1 1 1 1 shown below.
Z
0 1 0 1
X 1 1 1 0
Y
8. Consider the function F = X Y Z + X Y Z + X Y Z + X Y Z
(a) Simplify the function using a Karnaugh map: draw the map F,
circle implicants, and write the simplified function in algebraic
form.
Z
1 0 0 1
X 1 0 0 1
Y=Z
(b) Show how applying the axioms of Boolean algebra can
produce the same result.
F = XYZ+XYZ+XYZ+XYZ
= Z(X Y + X Y + X Y + X Y)
= Z X(Y + Y) + X(Y + Y)
= Z(X1 + X1)
= Z(X + X)
= Z1
= Z
9. Design a circuit that takes two two-bit binary numbers (A1 and A0 ,
B1 and B0 ) and produces a true output when, in binary, A is strictly
greater than B.
(a) Fill in the truth table
A1 A0 B1 B0 A>B
(b) Fill in the Karnaugh map
and use it to minimize 0 0 0 0 0
0 0 0 1 0
B0
0 0 1 0 0
0 0 1 1 0
0 0 0 0 0 1 0 0 1
1 0 0 0 0 1 0 1 0
A0 0 1 1 0 0
1 1 0 1 0 1 1 1 0
A1 1 0 0 0 1
1 1 0 0 1 0 0 1 1
1 0 1 0 0
B1 1 0 1 1 0
A1 B1 + A0 B0 B1 + A0 A1 B0 1 1 0 0 1
1 1 0 1 1
(c) Draw the circuit you 1 1 1 0 1
derived from the map in 1 1 1 1 0
part (b).
A0
B0
A1 B1 + A0 B0 B1 + A0 A1 B0
B1
A1
