(1) [Representation]
In class we saw how strings of bits could be used to represent sets of information. In some situations,
we want to make the representation as efficient as possible (i.e. to use the minimum
number of bits).
Consider here the representation of the alphabet. Suppose you wanted to represent all upper and lower
case letters (i.e., a, b, ... z, A, B, ... Z). Suggest a representation and
tell how many bits it requires.
How does your answer change if you are only representing the capital letters?
Answer:
With N bits, we can represent 2^N letters.
a) upper and lower letters: that's 52 letters in total. since 2^6 = 64 > 52 > 32 = 2^5, we need 6 bits
b) only capital letters: that's 26
letters in total. since 2^5 = 32 > 26 > 16 = 2^4, we need 5 bits.
Below is an example for representing all the 52 upper and lower letters. For
capital letters only, you can
omit the leftmost '0' and thus need 5 bits.
Letter  Representation  Letter  Representation  Letter  Representation  Letter  Representation 
A  0 0 0 0 0 0  N  0 0 1 1 0 1  a  1 0 0 0 0 0  n  1 0 1 1 0 1 
B  0 0 0 0 0 1  O  0 0 1 1 1 0  b  1 0 0 0 0 1  o  1 0 1 1 1 0 
C  0 0 0 0 1 0  P  0 0 1 1 1 1  c  1 0 0 0 1 0  p  1 0 1 1 1 1 
D  0 0 0 0 1 1  Q  0 1 0 0 0 0  d  1 0 0 0 1 1  q  1 1 0 0 0 0 
E  0 0 0 1 0 0  R  0 1 0 0 0 1  e  1 0 0 1 0 0  r  1 1 0 0 0 1 
F  0 0 0 1 0 1  S  0 1 0 0 1 0  f  1 0 0 1 0 1  s  1 1 0 0 1 0 
G  0 0 0 1 1 0  T  0 1 0 0 1 1  g  1 0 0 1 1 0  t  1 1 0 0 1 1 
H  0 0 0 1 1 1  U  0 1 0 1 0 0  h  1 0 0 1 1 1  u  1 1 0 1 0 0 
I  0 0 1 0 0 0  V  0 1 0 1 0 1  i  1 0 1 0 0 0  v  1 1 0 1 0 1 
J  0 0 1 0 0 1  W  0 1 0 1 1 0  j  1 0 1 0 0 1  w  1 1 0 1 1 0 
K  0 0 1 0 1 0  X  0 1 0 1 1 1  k  1 0 1 0 1 0  x  1 1 0 1 1 1 
L  0 0 1 0 1 1  Y  0 1 1 0 0 0  l  1 0 1 0 1 1  y  1 1 1 0 0 0 
M  0 0 1 1 0 0  Z  0 1 1 0 0 1  m  1 0 1 1 0 0  z  1 1 1 0 0 1 
(2) [Carry ripple adder]
(A) When we built the carryripple adder in class, we used a building block that took 3 inputs and
generated 2 outputs.
The inputs were one bit from each addend as well as a carry bit. The outputs are a bit from the sum and
a carry bit. The carry bits move from one building block to the next  we think of them as rippleing
down the circuit  hence the name.
Build a circuit for this building block from AND, OR and NOT gates.
Answer:
Truth Table:
X  Y  Cin  Cout  Z 
0  0  0  0  0 
0  0  1  0  1 
0  1  0  0  1 
0  1  1  1  0 
1  0  0  0  1 
1  0  1  1  0 
1  1  0  1  0 
1  1  1  1  1 
We can see from the truth table that:
Z = ( (NOT X) AND (NOT Y) AND (Cin) ) OR ( (NOT X) AND (Y) AND (NOT Cin) ) OR
( (X) AND (NOT Y) AND (NOT Cin) ) OR ( (X) AND (Y) AND (Cin) )
Cout = ( (NOT X) AND (Y) AND (Cin) ) OR ( (X) AND (NOT Y) AND (Cin) ) OR
( (X) AND (Y) AND (NOT Cin) ) OR ( (X) AND (Y) AND (Cin) )
We can then build the circuit:
(B) We could build a carryripple adder using a black box that took as input two bit chunks from
each of the inputs along with a carry bit and generated as output a 2 bit chunk of the output along
with a carry bit. So this box would take 5 inputs and generate 3 outputs.
The black box essentially performs the addition
Cin
X2
X1
Y2
Y1
==============
Cout Z2 Z1
where X2 and X1 are the bits of the first number, Y2 and Y1 are the bits of the second number and
Cin is the carry left over from the previous addition. Z2 and Z1 are the output bits of the sum and
Cout is the carry in the output.
If you were to build truth tables to describe this box, how many would you need and
how big would they be?
Answer:
One "easy" way is to build a truth table that has 5 inputs ( X1, Y1, X2, Y2, Cin ) and
3 outputs ( Z1, Z2, Cout), so the table will have 2^5 = 32 rows.
However, like what we did in class, we can rewrite the addition as:
C Cin
X2 X1
Y2 Y1
========== =========
Cout Z2 C Z1
Thus, we need only two truth tables with 2^3 = 8 rows each:
X2  Y2  C  Cout  Z2 
0  0  0  0  0 
0  0  1  0  1 
0  1  0  0  1 
0  1  1  1  0 
1  0  0  0  1 
1  0  1  1  0 
1  1  0  1  0 
1  1  1  1 
1

X1  Y1  Cin  C  Z1 
0  0  0  0  0 
0  0  1  0  1 
0  1  0  0  1 
0  1  1  1  0 
1  0  0  0  1 
1  0  1  1  0 
1  1  0  1  0 
1  1  1  1  1 
If someone gave you such a black box, how would you build an adder that worked for adding
4 bit numbers? for adding 16 bit numbers?
Answer:
We are going to build CarryRipple Adders using the black box:
4bit adder:
a3 a2 a1 a0
b3 b2 b1 b0
================
c3 d3 d2 d1 d0
16bit adder:
a15 a14 a13 a12 a11 a10 a9 a8 a7 a6 a5 a4 a3 a2 a1 a0
b15 b14 b13 b12 b11 a10 b9 b8 b7 b6 b5 b4 b3 b2 b1 b0
===============================================================
c15 d15 d14 d13 d12 d11 d10 d9 d8 d7 d6 d5 d4 d3 d2 d1 d0
(C) (extra credit) Use the universal method to give a design in terms of AND, OR and NOT gates
of the black box described in part B of this problem.
Answer:
From the two truth tables in part B), we can see that:
Z1 = ( (NOT X1) AND (NOT Y1) AND (Cin) ) OR ( (NOT X1) AND (Y1) AND (NOT Cin) ) OR
( (X1) AND (NOT Y1) AND (NOT Cin) ) OR ( (X1) AND (Y1) AND (Cin) )
C = ( (NOT X1) AND (Y1) AND (Cin) ) OR ( (X1) AND (NOT Y1) AND (Cin) ) OR
( (X1) AND (Y1) AND (NOT Cin) ) OR ( (X1) AND (Y1) AND (Cin) )
Z2 = ( (NOT X2) AND (NOT Y2) AND (C) ) OR ( (NOT X2) AND (Y2) AND (NOT C) ) OR
( (X2) AND (NOT Y2) AND (NOT C) ) OR ( (X2) AND (Y2) AND (C) )
Cout = ( (NOT X2) AND (Y2) AND (C) ) OR ( (X2) AND (NOT Y2) AND (C) ) OR
( (X2) AND (Y2) AND (NOT C) ) OR ( (X2) AND (Y2) AND (C) )
Thus the circuit:
(3) (Hexadecimal representation)
(A) How do we write the decimal number 10 in hexadecimal? How do we write the decimal number
100 in hexadecimal?
Answer:
(10)_{10} = (A)_{16}
(100)_{10} = (6 x 16^1 + 4 x 16^0) _{10} = (60)_{16} + (4)_{16} = (64)_{16}
(B) When we write the hexadecimal number 10, what is the corresponding decimal number? What
decimal number corresponds to the hexadecimal
number 100?
Answer:
(10)_{16} = (1 x 16^1 + 0 x 16^0)_{10} = (16)_{10}
(100)_{16} = (1 x 16^2 + 0 x 16^1 + 0 x 16^0) _{10} = (256 + 0 + 0)_{10} = (256)_{10}
(C) What is the sum of the hexadecimal numbers 1C and 2D? What is
their product?
Answer:
(1C)_{16} = (1 x 16^1 + 12)_{10} = (28)_{10 }
(2D)_{16} = (2 x 16^1 + 13)_{10} = (45)_{10}
(1C)_{16} + (2D)_{16} = (28 + 45)_{10} = (73)_{10} = (4 x 16^1 + 9 x 16^0)_{10} = (40)_{16} + (9)_{16} = (49)_{16}
(1C)_{16} x (2D)_{16} = (28 x 45) _{10} = (1260)_{10} = (4 x 16^2 + 14 x 16^1 + 12 x 16^0)_{10}
= (400)_{16} + (E0)_{16} + (C)_{16} = (4EC)_{16}
(4) (Numeracy)
In the last assignment, you determined that your computer could do an incredibly large number of
instructions during a COS 111 lecture. You calculated ths number by counting the number of times
your computer's clock ticks during the 75 minutes of a lecture. In this assignment, we will extend
this analysis to trying to solve a real problem.
Imagine that you are using your computer to try and determine my password. You do so, by taking
a guess at my password and then performing a test to see if you have guessed correctly. The test
you do is very complicated for reasons you will (hopefully) understand by the end of the semester.
Testing one password takes about 1 million instructions or 1 million ticks of your computer's clock.
How many passwords can you check during a COS 111 lecture?
Answer:
Suppose your computer has a clock rate of 900 MHz, then the result from problem 4 of Problem Set 1
is 4,050,000,000,000 ( or 4.05 x 10^12 ), which means your computer can execute 4.05 x 10^12
instructions during the 75 minutes of a COS 111 lecture.
Given the fact that testing one password takes about 1 million ( 10^6 ) instructions, the number of
passwords you can test during the 75 minutes of a COS 111 lecture is
4.05 x 10^12 / 10^6 = 4.05 x 10^6 (4.05 million)
Comments? Questions?  contact us at cs111@cs.princeton.edu