Your first assignment is to play a bit with ASCII. First try some examples on the ASCII encoding webpage.

Problem 1. ASCII Encoding.

What is the decimal ASCII encoding of your first and last name?

Answer:

You can use the ASCII Converter webpage to check your answer and to see the binary representation as well. ASCII requires 7 bits per character because it encodes more than 64 characters, but fewer than 128. Most computers, however, use some type of extended ASCII which actually uses 8 bits per character. The ASCII converter uses one of these 8 bit extensions.

What is the binary ASCII encoding of your first name?

Answer:

Problem 2. ASCII Encoding and Corruption by Errors.

On the ASCII Encoding and Corruption by Errors webpage, you will work through several examples where you click the "Change Bits" button to "flip" bits in the 8 bit ASCII encoding of a sentence - you are playing the role of cosmic radiation or of a malfunction here.

Sometimes it may happen that a bit that was flipped in an earlier turn gets flipped again. That is OK - if it were cosmic radiation doing the flipping, and not your button, the chance that the same bit would be hit twice is also not zero - although it is small of course. Your button-clicking is a highly accelerated way of modeling the random bit flips that can happen naturally.

Type a short sentence (at most 15 characters) in the Bit Flipper (Flash). Now start flipping bits with the "Change Bits" button and fill out the following:

Answer:

First Sentence:

After how many bit flips was the sentence changed?

After how many bit flips was the sentence so much corrupted that it became unintelligible?

Also on the ASCII Encoding and Corruption by Errors  webpage, you will see a second version of the bit flipper. Use this Bit Flipper (Java) for a second sentence of your choosing. Pick a sentence that nearly fills the text window and press enter to see the ASCII binary representation. Start flipping bits and fill out the following:

First Sentence:

After how many bit flips was the sentence changed?

After how many bit flips was the sentence so much corrupted that it became unintelligible?

(non-math question - help us decide which Bit-Flipper is better) Which Bit-Flipper (Flash or Java) did you prefer and why?

Problem 3. ASCII Encoding and Corruption by Errors: The Tripling Code.

On the Redundancy webpage, you flip bits on the binary version of a text after every bit has been doubled. Now you can tell when a mistake was made - the two bits in a pair are not identical any more.

On the Triple Code, the bits are tripled. If, after some of the bits are flipped, you see a triplet where not all the bits are identical, you can take a majority vote and restore order. Only if more than one bit is flipped within a triplet will we start to make mistakes.

Try flipping bits using the tripling code version of your two sentences. (In order to get ready to experiment with a second sentence after you are finished with the first one, click the "Clear Inputs" button.)

Answer:

After how many bit flips was your first sentence changed?

After how many bit flips was your first sentence so much corrupted that it became unintelligible?

After how many bit flips was you second sentence changed?

After how many bit flips was your second sentence so much corrupted that it became unintelligible?

Problem 4. Wise Councillors.

A sultan has a council of Wise Councillors, and he wants to check whether they are really wise. After inviting them all to the palace, he announces that they will have to pass a test on the following day, and then proceeds to describe the test. They will be asked to stand in one straight line, behind each other, so that each Wise Councillor can see all the Councillors in front of, but not behind him/herself. They will then all be blindfolded, and hats will be placed on their heads; each hat is either completely red or completely blue; the hats are picked from a supply sufficiently large that, should he so choose, the sultan could decide to give them all red hats or all blue hats. Then all the Councillors' blindfolds will be removed, and each Councillor will be allowed to say, on his/her turn, just one word: "blue" or "red" - this is the guess of the Councillor for the color of the hat on his/her own head. All the Councillors will be able to hear the guesses of the others, but they are not (on penalty of death) to communicate with each other by any other means (no mirrors, no hand sinals, no coughing...) After giving them this description, the sultan assigns a rank order to each of the Councillors, indicating who will have to speak first, second, ... He also adds that the group of Councillors will pass the test if not more than one of their individual guesses is wrong; in this case they will be declared Truly Wise and richly rewarded. However, if more than one guess is wrong, they will be declared Formerly Wise and all will be executed. After this announcement, the sultan leaves his Wise Councillors to themselves, to discuss their strategy. They can decide on the order in which they will stand in line, and also on how they will each decide what to say; of course they want to pick a Truly Wise strategy.

Can you give a winning strategy if the sultan has two Wise Councillors?

Answer:

Can you give a winning strategy is the sultan has three Wise Councillors?

Answer:

Problem 5. Hamming Encoding.

After you have worked the examples on the Hamming Code (which tells you if you are correct or not), try the following:

Answer:

4 bit combination	7 bit Hamming codeword
0011
1001
0001
1101
1111

Problem 6. Proof of 4-7 Hamming Code.

Let us now try to detect some errors. You can of course try to find a correct codeword by inspecting the full list of codewords, each with their 7 digits, and selecting the closest one.

Or you can do the following (where means "parity addition"):

Compute d1 = b1 b2 b3 b5

d2 = b1 b3 b4 b6

d3 = b2 b3 b4 b7

If d1, d2 and d3 are all equal to zero, then this is already a codeword - nothing to correct.

If only one of d1, d2, d3 is different from zero, then you must correct one of the last three bits (b5 if d1=1, b6 if d2=1, b7 if d3=1).

If two of d1, d2, d3 are different from zero, then you must correct the bit that occurs in the definitions of the two d-bits that are 1, but not in the other one. for instance: if d1=d2=1, but d3=0, then we must correct b1, because it occurs in both d1 and d2, but not in d3.

If d1, d2, d3 are all three different from zero, then you must correct b3.

Can you explain why this procedure must work? That is, please show that no matter which bit is flipped, that the procedure corrects that flip. Don't forget to show that that when no flips occur, the procedure still works.

Answer:


























Problem 7. Correcting Errors using Hamming Codes.

Now try correcting the following examples - the 4 bit string asked in the last column is the string (b1 b2 b3 b4) from which we started the encoding; you find this by deleting the last 3 bits from the Hamming codeword:

Answer:

7 bit string	closest Hamming codeword	4 bit string
1001011
0110000
1011001
1111000
1111100
1011111

Problem 8. A Guessing Game.

I am thinking of a number between 1 and 16. You can ask me 7 "yes or no" question; I don't have to give a truthful answer to each of your 7 questions but I can lie at most once. Design the strategy to guess my number. (Hint. the Hamming code has 16 codewords, and its codewords are 7 bits long.)

Answer:

Problem 9. ASCII Encoding and Corruption by Errors: The Hamming Code.

Now we shall try out the error correcting properties of the Hamming code. Proceed to the Hamming Code and Error Correction webpage.

You can again type a sentence. The computer encodes it as follows: first, as noted earlier, the binary ASCII encoding uses 8 bits for every character; the long string obtained by putting all these 8 bit strings next to each other is then cut up in 4 bit chunks (because our Hamming code works with 4 bit pieces), and every one of these is replaced by the corresponding Hamming codeword of 7 bits.

Now you can flip bits again, to see whether the text will be corrupted, and how much, after the computer decodes your corrupted binary version.

Try it on the same two sentences that you used for the tripling code questions:

Answer:

After how many bit flips was your first sentence changed?

After how many bit flips was your first sentence so much corrupted that it became unintelligible?

After how many bit flips was your second sentence changed?

After how many bit flips was your second sentence so much corrupted that it became unintelligible?

Problem 10. Encoder Comparison.

We will now compare the 4-7 Hamming code with the tripling code:

Answer:

What is the ratio of the length of a Hamming encoded bit string to the length of the unencoded bit string?

What is the ratio of the length of a tripling code encoded bit string to the length of the unencoded bit string?

For each of the two sentences and for each coding scheme (tripling and Hamming), compute the ratio between the number of bit flips that caused the decoded sentence to change to the total number of bits in the binary version of your original sentence (before coding) and fill in the following table:

Sentence		ratio = %
First	# of bits flips for one change (tripling) ----------------------------------------- ASCII bit length	-----   =               %
Second	# of bits flips for one change (tripling)  ----------------------------------------- ASCII bit length	-----   =               %
First	# of bits flips for one change (Hamming) -------------------------------------------- ASCII bit length	-----   =               %
Second	# of bits flips for one change (Hamming) --------------------------------------------- ASCII bit length	-----   =               %

Compare these two results. What do you think the advantages and disadvantages of these two codes are, when you compare them with each other?

Problem C1. Word Sequence Game.

In my childhood I played a game, where I was given two words of the same length, for example, nerd and geek. I had to invent a sequence of English words from nerd to geek, such that each next word differs from the previous one in one place. For example: nerd, need, weed, week, geek. Another example of such sequence: math, mate, made, mode, code. Create such a sequence of length four where each word differs from the previous one in one binary bit. That is if you write the binary ASCII string for your words, then the string corresponding to a word should differ in only one place from the string for the previous word. Use lower case letters. Hint: three letter words may be easier than four letter words for this exercise.

Problem C2. Bit Flip.

Suppose you have a text file in ASCII format. Due to radiation one bit flipped inside the file. The result is that when you try to read this file, you see only half of it. Explain what happened.

Problem C3. Wise Councillors.

Solve the Wise Councillors problem when you have N wise men. Can you do it also when there are three possible hat colors, green, red and blue? (The Councillors can now each pick one of these three words for their guesses).