CSE370 (Autumn 03) Assignment 1 Solution

2. CLD-II, Appendix A, problem 1, parts c, f, i, and j.

A.1.c Convert 01010112 to base 10

Expand: 01010112 = 0*26+1*25+0*24+1*23+0*22+1*21+1*20
Simplify: 25+23+21+20 = 32+8+2+1 = 4310

A.1.f Convert 1238 to base 10

Expand: 1238 = 1*82+2*81+3*80
Simplify: 82+2*8+3 = 64+16+3 = 8310

A.1.i Convert 3AE16 to base 10

Expand: 3AE16 = 3*162+10*161+14*160               (NOTE: A=10,B=11,...F=15)
Simplify: 3*162+10*16+14 = 768+160+14 = 94210

A.1.j Convert 1010.01012 to base 10

Expand: 10102 = 1*23+0*22+1*21+0*20+0*2-1+1*2-2+0*2-3+1*2-4      (NOTE: we just continue past the decimal point with negative exponents)
Simplify: 8+2+.25+.0625 = 10.312510

3. CLD-II, Appendex A, problem 2, parts d, and g.

A.2.d Convert 50010 to base 2

Use Successive Division:
500 ÷ 2 = 250 remainder 0
250 ÷ 2 = 125 remainder 0
125 ÷ 2 = 62 remainder 1
62 ÷ 2 = 31 remainder 0
31 ÷ 2 = 15 remainder 1
15 ÷ 2 = 7 remainder 1
7 ÷ 2 = 3 remainder 1
3 ÷ 2 = 1 remainder 1
1 ÷ 2 = 0 remainder 1

Remember that the last remainder is the first bit in the answer (you would multiply in the other direction to get the original number):
50010 =1111101002

A.2.g Convert 2.187510 to base 2

Convert each side of the decimal point separately
210 = 102
For the decimal use successive multiplication
.1875 * 2 = .3750 carry 0
.3750 * 2 = .7500 carry 0
.7500 * 2 = .5000 carry 1
.5000 * 2 = .0000 carry 1

Put the results for each part together to get the answer
2.187510 = 10.00112

4. CLD-II, Appendix A, problem 4, parts g, and h.

A.4.g Convert 7518 to base 2

8 = 23 so each octal digit represented 3 bits (binary digits) (basically an octal digit is simply short-hand for 3 binary digits).
Convert each octal digit to binary separately:

78 = 111, 58 = 101, 18 = 001

then the results are simply concatenated :

7518 = 1111010012

A.4.h Convert 0C516 to base 2

16 = 24 so each digit in hexadecimal represents 4 bits (basically a hex digit is simply short-hand for 4 binary digits)
Convert each hex digit to binary separately:

016 = 02, C16 = 1210 = 8+4 = 11002,516 = 510 = 0101

then the results are simply concatenated:

0C516 = 110001012

5. CLD-II, Appendix A, problem 7, parts b, and c.

A.7.b (binary addition) 

    111     <---- carries

  110111

+    101 

  111100

A.7.c (binary addition) 

  111110     <---- carries
  0111110 

+ 0010111 

  1010101

6. CLD-II, Chapter 1, problems 3 and 4 (all parts).

1.3 Encoding a deck of cards: (Answers could vary substantially - here are a few)

Scheme 0: There are 52 cards, therefore, use a 6 bit number to represent the card number 0 to 51 and leave 52 to 63 unused.  This encoding requires 6 bits:

V5 V4 V3 V2 V1 V0

Scheme 1: Observe that the cards come in groups of 13 (suit).  Therefore each card has 2 values that distinguish it: suit (Hearts,Clubs,Diamonds,Spades) and value (Ace,2,...,King). Since the suit can be one of four values, we need 2 bits to encode the suit (0, 1, 2, 3 assigned to clubs, diamonds, hearts, spades, respectively).  The value ranges from 1 to 13 (1=ace, 2, 3, ... , 10, 11=jack, 12=queen, 13=king).  Values of 0, 14, and 15 are unused.  This encoding also requires 6 bits:

V3 V2 V1 V0 S1 S0

Scheme 2: Since there are only 4 suits, we could just use 4 bits for the suit and a one-hot encoding (0001=clubs, 0010=diamonds, 0100=hearts, 1000=spades) that may be easier to decode.  This encoding requires 8 bits:

V3 V2 V1 V0 C D H S

Scheme 3: We may want to make it easy to distinguish face cards.  Another possible encoding would include a bit for face cards and non-face cards (F).  A jack, queen, and king would be encoded with F=1 and the value=0001, value=0002, and value=0003, respecitively.  Numbered cards and the ace would be encoded with F=0 and value equal to their number with the ace being a 1.  The values 0, 11, 12, 13, 14, 15 would not be used when F=0, the values 0, 4, ... , 15 would not be used when F=1.  This encoding uses 9 bits:

F V3 V2 V1 V0 C D H S

Scheme 4: We may want to make it easy to compare face cards to numbered cards (e.g., card1 > card2).  We'll change the previous encoding for the face cards to F=1 and values of 1011, 1100, and 1101 (11, 12, and 13 as in scheme 1 and 2).  Now the values 0, 1, ... , 10, 14, and 15 are not used when F=1.  This encoding uses 9 bits as for scheme 3, we've just changed the value for the jack, queen, and king:

F V3 V2 V1 V0 C D H S

Undoubtedly, there are many more, but we'll stop here.

1.4.a For each scheme in 1.3 encode the jack of diamonds

Scheme 0: We'll start numbering the cards from the ace of clubs, through to the king of clubs, then the ace of diamonds to the king of diamonds, then the hearts, and, finally, the spades.  The jack of diamonds is the 24th card with a number of 23.  Its encoding with this scheme is 010111 or:

V5' and V4 and V3' and V2 and V1 and V0

Scheme 1: The diamond suit is numbered 1 and the jack is the card with value 11. Its encoding with this scheme is 1011 concatenated with 01 to yield 101101 or:

V3 and V2' and V1 and V0 and S1' and S0

Scheme 2: The value is the same as the previous case, but the suit is represented by D = 1 and C = H = S = 0. Concatenating, the encoding is 10110100 or:

V3 and V2' and V1 and V0 and C' and D and H' and S'    - or, more simply, -    V3 and V2' and V1 and V0 and D

Scheme 3: The jack is a face card with value of 0001.  When we concatenate F = 1, value = 0001, and suit, CDHS = 0100, we get an encoding of 100010100 or:

F and V3' and V2' and V1' and V0 and D

Scheme 4: We now only have to vary the value.  Instead of 0001 for a jack, we use 1011.  The encoding is 110110100 or:

F and V3 and V2' and V1 and V0 and D

1.4.b For each scheme in 1.3 show the logic expression that describes a 7 of any suit

Scheme 0: With this scheme we have four cards to represent, the 7 of clubs (the 7th card), the 7 of diamonds (the 20th card), the 7 of hearts (the 33rd card), and the 7 of spades (the 46th card).  They'll have numbers 6, 19, 32, and 45, respectively.  Our quite long expression to cover these four cards will be: 

(V5' and V4' and V3' and V2 and V1 and V0') or (V5' and V4 and V3' and V2' and V1 and V0) or (V5 and V4' and V3' and V2' and V1' and V0') or (V5 and V4' and V3 and V2 and V1' and V0)

Scheme 1: This scheme will make things easier because we only need to look at the value part of the encoding.  We don't care what the suit is.  The expression is:

V3' and V2 and V1 and V0

Scheme 2: Since only the encoding of the suit changed from the previous scheme, the expression in this encoding is identical to the previous scheme:

V3' and V2 and V1 and V0

Scheme 3: The seven is not a face card, so F=0.  We still don't care about the suit.  The expression is:

F' and V3' and V2 and V1 and V0

Scheme 4: Nothing changes from the previous scheme, still a non-face card with value 7:

F' and V3' and V2 and V1 and V0

1.4.c For each scheme in 1.3 show that logic expression to describe any card of the heart suit.

Scheme 0: The heart suit is all the cards from the 27th to the 39th.  This corresponds to all the values between 26 and 38.  This is a 13 term expression (we only show the first and last terms for brevity):

(V5' and V4 and V3 and V2' and V1 and V0') or ... or (V5 and V4' and V3' and V2 and V1 and V0')

Scheme 1: We only care about the suit being hearts or 2.  The expression is simply:

S1 and S0'

Scheme 2: In this scheme its a single variable expression as we have a variable to directly represent the heart suit.  The expression is simply:

H

Scheme 3: This is the same as the previous scheme as we don't care about it being a face card or not.  Again, the expression is:

H

Scheme 4: Again, the same expression:

H

Comments to: cse370-webmaster@cs.washington.edu (Last Update: )