a.

The person's number is the sum of the top left numbers of each card that contain the person's number.

b.

Due to the theorem, which states that each positive integer can be uniquely written as a binary number aj, aj-1, ... , a1, a0. One will notice that the top-left numbers of each card represents a binary digit location. 1 is 00001, 2 is 00010, 4 is 00100, 8 is 01000, and 16 is 10000. If one converts all the numbers on the cards to binary, one will notice that for the card with 1 on the top-left, the a0 spot (binary number: a4 a3 a2 a1 a0) will always be 1 for all of the numbers on that card. The numbers on the card with 2 on the top-left will always have 1 for the a1 spot. The numbers on the card with 4 on the top-left will always have 1 for the a2 spot, and so on. So for example, if the user chose the number 6, which translates to 00110, 1 in the a1 and a2 spots, 6 would appear on the card with 2 and 4 on the top-left.

c.

(card size: 4x8)

Card #1, top-left=1, binary a2a1a0=XX1, varying X by row:

01,03,05,07; (a5a4a3=000)

09,11,13,15; (a5a4a3=001)

17,19,21,23; (a5a4a3=010)

25,27,29,31; (a5a4a3=011)

33,35,37,39; (a5a4a3=100)

41,43,45,47; (a5a4a3=101)

49,51,53,55; (a5a4a3=110)

57,59,61,63; (a5a4a3=111)

Card #2, top-left=2, binary a2a1a0=X1X, varying X by row:

02,03,06,07; (a5a4a3=000)

10,11,14,15; (a5a4a3=001)

18,19,22,23; (a5a4a3=010)

26,27,30,31; (a5a4a3=011)

34,35,38,39; (a5a4a3=100)

42,43,46,47; (a5a4a3=101)

50,51,54,55; (a5a4a3=110)

58,59,62,63; (a5a4a3=111)

Card #3, top-left=4, binary a2a1a0=1XX, varying X by row:

04,05,06,07; (a5a4a3=000)

12,13,14,15; (a5a4a3=001)

20,21,22,23; (a5a4a3=010)

28,29,30,31; (a5a4a3=011)

36,37,38,39; (a5a4a3=100)

44,45,46,47; (a5a4a3=101)

52,53,54,55; (a5a4a3=110)

60,61,62,63; (a5a4a3=111)

Card #4, top-left=8, binary a3a2a1a0=1YXX, varying X by row:

08,09,10,11; (a5a4a3a2=0010)

12,13,14,15; (a5a4a3a2=0011)

24,25,26,27; (a5a4a3a2=0110)

28,29,30,31; (a5a4a3a2=0111)

40,41,42,43; (a5a4a3a2=1010)

44,45,46,47; (a5a4a3a2=1011)

56,57,58,59; (a5a4a3a2=1110)

60,61,62,63; (a5a4a3a2=1111)

Card #5, top-left=8, binary a4a3a2a1a0=1YYXX, varying X by row:

16,17,18,19; (a5a4a3a2=0100)

20,21,22,23; (a5a4a3a2=0101)

24,25,26,27; (a5a4a3a2=0110)

28,29,30,31; (a5a4a3a2=0111)

48,49,50,51; (a5a4a3a2=1100)

52,53,54,55; (a5a4a3a2=1101)

56,57,58,59; (a5a4a3a2=1110)

60,61,62,63; (a5a4a3a2=1111)

Card #6, top-left=8, binary a5a4a3a2a1a0=1YYYXX, varying X by row:

32,33,34,35; (a5a4a3a2=1000)

36,37,38,39; (a5a4a3a2=1001)

40,41,42,43; (a5a4a3a2=1010)

44,45,46,47; (a5a4a3a2=1011)

48,49,50,51; (a5a4a3a2=1100)

52,53,54,55; (a5a4a3a2=1101)

56,57,58,59; (a5a4a3a2=1110)

60,61,62,63; (a5a4a3a2=1111)

d.

Card #1:

01,04,07;

10,13,16;

19,22,25;

Card #2:

02,05,08;

11,14,17;

20,23,26;

Card #3:

03,04,05;

12,13,14;

21,22,23;

Card #4:

06,07,08;

15,16,17;

24,25,26;

Card #5:

09,10,11;

12,13,14;

15,16,17;

Card #6:

18,19,20;

21,22,23;

24,25,26;

Problem 1.2

a.

{0000000, 1101001, 0101010, 1000011, 1001100, 0100101, 1100110, 0001111, 1110000, 0011001, 1011010, 0110011, 0111100, 1010101, 0010110, 1111111}

b.

ie. 0000000 becomes 0101000.

Hamming code will find that there are bit errors at bit 2 and bit 4.

c.

ie. 1000011 becomes 0000000.

d.

0010110: 0,1,1,0; 0,1,1,0; 0,1,1,0; All even, so therefore none of the bits are wrong. The codeword that was sent was 0010110 (The original message was 1110).

e.

i) 1011111: 1,1,1,1; 0,1,1,1; 1,1,1,1; p2 was odd. However, nothing else was odd, so it is probably position 2 that was flipped. The original codeword was 1111111.

ii) The check bits did not tell me that because it does not have a way to detect 3-bit errors (errors consisting of 3 incorrect bits).

f.

previous example: 0101000 (originally 0000000).

Hamming code can not tell if the error occurred at position 6, or if the error occured at position 2 and 4.

Problem 1.3

a.

i) k=2, 3 codewords are {00,01,10}. If we get 11, then we know there's an error, but we don't know where (detects 1 error). If we get 00, there could have been an error, but we don't know that for sure (detects 0 errors). And so we'll go with the least, being detects 0 errors. And thus, we really can't correct any, since we can't detect any.

ii) k=3, 3 codewords are {101,110,011}. We can detect 1 error max, but we can't correct any.

iii) k=5, 3 codewords are {00000,11110,11001}. We can detect 1 errors max, but we still can't correct any errors.

iv) k=6, 3 codewords are {000000,111100,110011}. We can detect 2 errors max, and we can correct at least 1 error (possibly up to two, depending on location of the errors).

v) k=8, 3 codewords are {00000000, 11111000, 11000111}. We can detect 3 errors max, and correct as least 2 errors (possibly up to three, again, depending on location of the errors).

Chart:

distance d |
k | Code C | # of errors detected |
# of errors corrected |
|||
---|---|---|---|---|---|---|---|

codeword 1 | codeword 2 | codeword 3 | |||||

b.

number of errors detected = distance-2. ii is an exception, because it can use even-parity to check.

c.

number of errors corrected = number of errors detected-1 = distance-3