# Problem Set 2: Solution

(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?

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

(A) When we built the carry-ripple 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 ripple-ing

down the circuit -- hence the name.

Build a circuit for this building block from AND, OR and NOT gates.

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 carry-ripple 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?

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?

We  are going to build Carry-Ripple Adders using the black box:

a3    a2    a1    a0

b3    b2    b1    b0

================

c3    d3    d2    d1    d0

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.

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:

(A) How do we write the decimal number 10 in hexadecimal? How do we write the decimal number

(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?

(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?

(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.

How many passwords can you check during a COS 111 lecture?

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)