Check yourself: If the amount of information received is proportional to the amount uncertainty resolved, which piece of data conveys the most information? The least?
Most information? The card is a heart The card is not the Ace of spades The card is a face card (J, Q, K) The card is the Queen of Hearts Least information? The card is a heart The card is not the Ace of spades The card is a face card (J, Q, K) The card is the Queen of Hearts

Check yourself: An unfair coin with p(TAILS)=1/8 is tossed. How much information is received upon learning the outcome is... ± 0.001. You can use log2() ...heads? ± 0.001. You can use log2() ...tails?

Check yourself: What is the entropy of a fair 6-sided die roll? ± 0.001. You can use log2() Entropy of die (bits) What is the entropy of the unfair coin (p(TAILS)=1/8)? ± 0.001. You can use log2() Entropy of die (bits)

Check yourself: When our sheep moved to the city, it started bleating "10011110". We think it might be using the video's encoding:

• B->0,
• A->11,
• C->100,
• D->101.

BAA? What is it calling?

Check yourself: We map the integers 1 through 6 to the outcome of a fair six-sided die by using a 3-bit fixed-length encoding. ± 0.001. You can use log2() Expected length? How does it compare to the entropy of the die? Is that expected? How does it compare? Length greater than entropy Length same as entropy Length smaller than entropy Ben Bitdiddle finds the die and rolls 5, 2, then 6. What would Bitdiddle's message be? 0b01101001... Bitdiddle's message:

Check yourself: Using two's complement, what are the largest and smallest 5-bit numbers? You can use binary (0b1010), hex (0xA) or decimal (10). Largest 5-bit number? You can use binary (0b1010), hex (0xA) or decimal (10). Smallest 5-bit number?

Check yourself: Ben Bitdiddle just heard of variable-length encodings and uses the following to encode the outcome of rolling a fair six-sided die:

• 1->1,
• 2->01,
• 3->001,
• 4->0001,
• 5->00001,
• 6->000001.

± 0.001. 1/8*3+... Expected length?

Check yourself: Alyssa P. Hacker, unconvinced by Ben's efforts in the previous problem, uses Huffman's algorithm and gets:

• 1->000,
• 2->001,
• 3->010,
• 4->011,
• 5->10,
• 6->11.

±0.001 Expected length?

Check yourself:Consider messages built from four symbols with the following probabilities: A:1/6, B:1/6, C:2/6, D:2/6. The Huffman algorithm sometimes involves making arbitrary choices that can lead to trees with different shapes. However, their expected length should all be identical. Find two trees for the above probabilities, and compute their expected length. ±0.001 Expected length? The two trees have a different height, what is the height of the tallest? Sequoia? Height of tallest tree?

Check yourself: In order to more efficiently communicate unfair coin tosses (p(TAILS)=1/8), we want to encode them in pairs. Hint: you've already computed the entropy of one toss, how is it related to that of two tosses? ± 0.001 Entropy of coin tosses? Using 1-bit per coin toss, what is the expected length of a message communicating the outcome of a pair of tosses? ± 0.001 Expected length? Knowing the probabilities are:

• HH: 49/64,
• HT: 7/64,
• TH: 7/64,
• TT: 1/64.

Build a Huffman encoding of the pairs of outcomes. ± 0.001 Expected length? How much shorter is it? ± 0.001 Old length/new length?

To detect errors in transmission, we add an even parity bit to our 3-bit fixed length encoding of the of a fair six-sided die. That is, we add a bit to make the total number of 1s even. What is the encoding for each roll? 0b001 + parity? 1? 0b010 + parity? 2? 0b011 + parity? 3? 0b100 + parity? 4? 0b101 + parity? 5? 0b110 + parity? 6?

We add more parity bits to allow the receiver to correct transmission errors: we write 3 rolls in a 3x3 matrix and add an even parity bit for every row and column.
For example, Ben's role of 5, 2 then 6 would be:

5: 101 0 <
2: 010 1 <- row parity bits
6: 110 0 <
   001 <- column parity bits

First transmission:
1100
0000
0101
100 0b... First? 0b... Second? 0b... Third?
Second transmission:
1011
0110
0011
011 0b... First? 0b... Second? 0b... Third?
Third transmission:
0111
1001
0110
100 0b... First? 0b... Second? 0b... Third?