Answer key · Unit 6

Information and codes.

Each lesson’s practice questions, their correct answers and the mistakes they spot. Answers read off the Scene use the same setting the learner sees.

Misconception catalogue

Answer key 5

Lesson 1 of 5 · About 20 minutes

Surprise measured in bits

What the word information means in computer science: how much uncertainty a message removes, why a fair coin flip carries one bit, and why a rare outcome is more surprising.

Open the lesson

The 5 steps and their answers

Step 1 of 5
Open this step
What information is
Practice · Choose
Question
Two messages reach you. The first says “The sun rose this morning”. The second gives the result of a fair coin flip. Which carries more information, in Shannon’s sense?

Correct answer
- Correct The result of the coin flip
Setup, choices and feedback
The Scene at this step
Chance of heads
50 %
Code block size
4 flipsdefaulthidden
Measure and compress
Coins
Choices
Shown in a random order.
- Correct The result of the coin flip
- Wrong The message about the sun, because it is about something more important
  Misconception: Takes information to be how important or meaningful a message is, not how much uncertainty it removes.
  Feedback from the catalogue
  In computer science information does not measure importance or meaning. It measures how much uncertainty a message removes: how much you did not know before it arrived. A message you knew in advance carries $0$ ⁠ bits, however important it is. The result of a fair coin flip, which matters to nobody, carries one whole bit, because you could not have guessed it.
- Wrong Both the same: each is one message
  Feedback
  Information is not counted in messages but in how much uncertainty each message removes. You could have written the message about the sun yourself before it arrived.
Feedback for a right answer
You knew the sun had risen before you read it, so that message removes no uncertainty: $0$ ⁠ bits. The coin’s result you could not have guessed, and its message removes one whole bit of uncertainty.

Hint
Before each message arrived, how sure were you of what it would say?

Worked solution
1. Information measures how much uncertainty a message removes, not how important it is.
2. That the sun rose was certain in advance: probability $1$ ⁠, surprise $0$ ⁠ bits.
3. A fair coin’s result cannot be guessed: each face has probability $\tfrac12$ ⁠, and the message carries one bit.
4. So the coin’s message carries more information.
If you chose the sun, you measured importance. To Shannon, a message you knew in advance tells you nothing, however important it is.
Step 2 of 5
Open this step
One bit
Practice · Calculate
Question
The coin is fair: Chance of heads is fixed at 50%. The surprise of an outcome with probability $p$ ⁠ is $-\log_2 p$ ⁠ bits. How many bits of surprise does heads carry?

Correct answer
1 ± 0.01
Setup, choices and feedback
The Scene at this step
Chance of heads
50 %fixed
Code block size
4 flipsdefaulthidden
Measure and compress
Coinsfixed
Accepted within
± 0.01
Computed from the Scene at this step’s setting
Surprise of a heads, −log₂ p, in bits (infinite when heads cannot happen)/nodes/stream/outputs/surpriseHeads
Wrong answers it recognises
- 0.5 ± 0.01
  Misconception: Gives the probability itself as the surprise or the entropy, instead of −log₂ p.
  Feedback from the catalogue
  The probability is not the surprise. The surprise of an outcome with probability $p$ ⁠ is $-\log_2 p = \log_2 \tfrac{1}{p}$ ⁠ bits: how many times you halve the chance from $1$ ⁠ to reach it. An outcome with probability $\tfrac12$ ⁠ carries one bit, not $0.5$ ⁠; an outcome with probability $\tfrac14$ ⁠ carries two bits, not $0.25$ ⁠. The probability is a number between $0$ ⁠ and $1$ ⁠, and the surprise grows as the probability gets smaller.
Feedback for a right answer
$-\log_2 \tfrac12 = \log_2 2 = 1$ ⁠: exactly one bit, the answer to one yes-or-no question. That is also why the tape gives each flip one bit.

Hint
$-\log_2 \tfrac12 = \log_2 2$ ⁠: to what power must you raise $2$ ⁠ to get $2$ ⁠?

Worked solution
1. The probability of heads: $p = \tfrac12$ ⁠.
2. The surprise: $-\log_2 p = \log_2 \tfrac{1}{p}$ ⁠.
3. Substitute: $\log_2 2 = 1$ ⁠, because $2^1 = 2$ ⁠.
4. Heads carries one bit.
If you answered $0.5$ ⁠, you gave the probability itself. The surprise is the logarithm of one over the probability.
Step 3 of 5
Open this step
A biased coin
Practice · Predict, then look
Question
Now the coin is biased: it lands heads in 90% of flips. Which face carries more surprise? Choose, and then Measure and compress moves to Entropy and shows the surprise of each face.

Correct answer
- Correct Tails, the rare outcome
Setup, choices and feedback
The Scene at this step
Chance of heads
90 %fixed
Code block size
4 flipsdefaulthidden
Measure and compress
Coinsfixed
Choices
- Correct Tails, the rare outcome
- Wrong Heads, because it turns up far more often
  Misconception: Thinks the likely outcome carries more information, because it turns up more often.
  Feedback from the catalogue
  The surprise of an outcome depends on how unexpected it is: $-\log_2 p$ ⁠. The smaller the chance, the bigger the surprise. When a coin lands heads 90% of the time, heads carries only $0.15$ ⁠ bits, because you guessed it in advance. The rare tails carries $3.32$ ⁠ bits. Heads does turn up more often, but each time it tells you little.
- Wrong Both the same, because every flip is printed as one bit
  Feedback
  The tape does give each flip one bit, but that is the length of the record, not the amount of information. A heads you guessed in advance tells you less than a tails you did not expect.
Once the prediction is locked in, the Scene changes
Measure and compress
Entropyfixed
The Scene then shows: 3.322 · Surprise of a tails, −log₂ (1 − p), in bits (infinite when tails cannot happen)/nodes/stream/outputs/surpriseTails
A prediction is never marked as a failure: the learner sees the outcome and the explanation either way.
Feedback for a right answer
Tails carries $-\log_2 0.1 \approx 3.32$ ⁠ bits, and heads only $-\log_2 0.9 \approx 0.15$ ⁠. When the coin almost always lands heads, heads is small news and tails is big news.

Hint
Which face would you guess before the flip? The surprise is what you did not guess.

Worked solution
1. The chance of heads is $0.9$ ⁠, of tails $0.1$ ⁠.
2. The surprise of heads: $-\log_2 0.9 \approx 0.15$ ⁠ bits.
3. The surprise of tails: $-\log_2 0.1 = \log_2 10 \approx 3.32$ ⁠ bits.
4. Tails, the rare outcome, carries far more surprise.
If you chose heads, you counted how often each face turns up. The surprise of one outcome depends on how unexpected it is.
Step 4 of 5
Open this step
Every halving is a bit
Practice · Calculate
Question
Chance of heads is now fixed at 25%. How many bits of surprise does heads carry?

Correct answer
2 ± 0.01
Setup, choices and feedback
The Scene at this step
Chance of heads
25 %fixed
Code block size
4 flipsdefaulthidden
Measure and compress
Coinsfixed
Accepted within
± 0.01
Computed from the Scene at this step’s setting
Surprise of a heads, −log₂ p, in bits (infinite when heads cannot happen)/nodes/stream/outputs/surpriseHeads
Wrong answers it recognises
- 0.25 ± 0.01
  Misconception: Gives the probability itself as the surprise or the entropy, instead of −log₂ p.
  Feedback from the catalogue
  The probability is not the surprise. The surprise of an outcome with probability $p$ ⁠ is $-\log_2 p = \log_2 \tfrac{1}{p}$ ⁠ bits: how many times you halve the chance from $1$ ⁠ to reach it. An outcome with probability $\tfrac12$ ⁠ carries one bit, not $0.5$ ⁠; an outcome with probability $\tfrac14$ ⁠ carries two bits, not $0.25$ ⁠. The probability is a number between $0$ ⁠ and $1$ ⁠, and the surprise grows as the probability gets smaller.
- 4 ± 0.01
  Misconception: Gives the number of equally likely outcomes, 1/p, instead of the bits it takes to tell them apart, log₂ (1/p).
  Feedback from the catalogue
  $\tfrac{1}{p}$ ⁠ is the number of equally likely outcomes: an outcome with probability $\tfrac14$ ⁠ is one of four equal possibilities. To tell four possibilities apart, two bits are enough, $00$ ⁠, $01$ ⁠, $10$ ⁠ and $11$ ⁠, because each bit doubles the number of possibilities. So the surprise is the logarithm: $\log_2 4 = 2$ ⁠, not $4$ ⁠. Eight possibilities take three bits, and a thousand about ten.
Feedback for a right answer
$-\log_2 \tfrac14 = \log_2 4 = 2$ ⁠ bits. Each halving of the chance adds one bit: $\tfrac12$ ⁠ carries one bit, $\tfrac14$ ⁠ two, $\tfrac18$ ⁠ three.

Hint
How many times must you halve $1$ ⁠ to reach $\tfrac14$ ⁠?

Worked solution
1. $p = 0.25 = \tfrac14$ ⁠.
2. The surprise: $-\log_2 \tfrac14 = \log_2 4$ ⁠.
3. $2^2 = 4$ ⁠, so $\log_2 4 = 2$ ⁠.
4. Heads carries $2$ ⁠ bits.
If you answered $4$ ⁠, you worked out $\tfrac{1}{p}$ ⁠ without the logarithm: that is the number of equal possibilities, not the bits it takes to tell them apart. If you answered $0.25$ ⁠, you gave the probability.
Step 5 of 5
Open this step
Rare news
Practice · Reach the target
Question
Tails on a 90% coin carries $\log_2 10 \approx 3.32$ ⁠ bits. Change Chance of heads until heads carries exactly the same surprise, then press Check.

Goal
- 3.32 ± 0.01
  At the start of the step: 1
Setup, choices and feedback
The Scene at this step
Chance of heads
50 %
Code block size
4 flipsdefaulthidden
Measure and compress
Entropyfixed
Read from the Scene at
Surprise of a heads, −log₂ p, in bits (infinite when heads cannot happen)/nodes/stream/outputs/surpriseHeads
One setting that reaches it
Chance of heads
10 %
Feedback for a right answer
At 10%: now heads is the rare outcome, one in ten, and $-\log_2 0.1 \approx 3.32$ ⁠. The surprise does not depend on the face’s name, only on its probability.

Feedback for a wrong answer
Not yet. Look for the chance at which heads comes up once in every ten flips.

Hint
The surprise depends only on the outcome’s probability. At what chance of heads does heads have probability $0.1$ ⁠?

Worked solution
1. You want $-\log_2 p \approx 3.32 = \log_2 10$ ⁠.
2. So $\tfrac{1}{p} = 10$ ⁠, that is $p = 0.1$ ⁠.
3. Set Chance of heads to 10%.
If you headed for 90%, you raised the chance of heads, and heads became more expected and less surprising.

Lesson 2 of 5 · About 20 minutes

Entropy

A source's average surprise: how to work it out, why it peaks for a fair coin and falls to zero when the outcome is certain, and why random noise is full of information.

Open the lesson

The 5 steps and their answers

Step 1 of 5
Open this step
The average surprise
Practice · Calculate
Question
Chance of heads is fixed at 90%. Heads carries $0.15$ ⁠ bits of surprise, and tails $3.32$ ⁠. What is the coin’s entropy, the average surprise per flip, in bits?

Correct answer
0.469 ± 0.01
Setup, choices and feedback
The Scene at this step
Chance of heads
90 %fixed
Code block size
4 flipsdefaulthidden
Measure and compress
Coinsfixed
Accepted within
± 0.01
Computed from the Scene at this step’s setting
Shannon entropy of one flip, H(p), in bits: the average surprise and the least any code can spend per flip/nodes/stream/outputs/entropy
Wrong answers it recognises
- 1.74 ± 0.02
  Misconception: Averages the surprises (or codeword lengths) as if every outcome were equally likely, without weighting each by its probability.
  Feedback from the catalogue
  Entropy, and the average cost of a code too, is a weighted average: each value counts by its probability. With a 90% coin, heads turns up in nine flips out of ten and tails in one, so $H = 0.9 \times 0.15 + 0.1 \times 3.32 \approx 0.47$ ⁠, not $\tfrac{0.15 + 3.32}{2} \approx 1.74$ ⁠. A plain average treats the rare tails as if it turned up in half the flips.
- 0.9 ± 0.01
  Misconception: Gives the probability itself as the surprise or the entropy, instead of −log₂ p.
  Feedback from the catalogue
  The probability is not the surprise. The surprise of an outcome with probability $p$ ⁠ is $-\log_2 p = \log_2 \tfrac{1}{p}$ ⁠ bits: how many times you halve the chance from $1$ ⁠ to reach it. An outcome with probability $\tfrac12$ ⁠ carries one bit, not $0.5$ ⁠; an outcome with probability $\tfrac14$ ⁠ carries two bits, not $0.25$ ⁠. The probability is a number between $0$ ⁠ and $1$ ⁠, and the surprise grows as the probability gets smaller.
Feedback for a right answer
$H = 0.9 \times 0.15 + 0.1 \times 3.32 \approx 0.47$ ⁠ bits per flip. Most flips bring a small surprise, and only one in ten a big one, so the average is under half a bit.

Hint
A weighted average: multiply each surprise by its chance, and add.

Worked solution
1. Heads: probability $0.9$ ⁠, surprise $0.152$ ⁠. Tails: probability $0.1$ ⁠, surprise $3.32$ ⁠.
2. Entropy is the weighted average of the surprises: $H = p \cdot (-\log_2 p) + (1-p) \cdot (-\log_2 (1-p))$ ⁠.
3. Substitute: $H = 0.9 \times 0.152 + 0.1 \times 3.32 \approx 0.137 + 0.332 = 0.469$ ⁠.
4. The entropy: about $0.47$ ⁠ bits per flip.
If you got $1.74$ ⁠, you took a plain average, $\tfrac{0.15 + 3.32}{2}$ ⁠, as if tails turned up in half the flips. It turns up in only a tenth of them.
Step 2 of 5
Open this step
The curve
Practice · Predict, then look
Question
The marker on the curve shows $0.47$ ⁠ bits for a coin that lands heads 90% of the time. Now the bias flips: the coin will land heads in only 10% of flips, and tails in 90%. What will its entropy be?

Correct answer
- Correct The same entropy, $0.47$ ⁠ bits
Setup, choices and feedback
The Scene at this step
Chance of heads
90 %fixed
Code block size
4 flipsdefaulthidden
Measure and compress
Entropyfixed
Choices
- Correct The same entropy, $0.47$ ⁠ bits
- Wrong Lower, because now heads, the outcome printed as 1, is rare
  Feedback
  The tape writes $1$ ⁠ for heads and $0$ ⁠ for tails, but that is only a convention. The entropy depends on the probabilities, not on the faces’ names or digits.
- Wrong Higher, because now the rare outcome is heads
  Feedback
  There is still one common outcome, $0.9$ ⁠, and one rare one, $0.1$ ⁠. Only the names have swapped.
Once the prediction is locked in, the Scene changes
Chance of heads
10 %fixed
Measure and compress
Entropyfixed
The Scene then shows: 0.469 · Shannon entropy of one flip, H(p), in bits: the average surprise and the least any code can spend per flip/nodes/stream/outputs/entropy
A prediction is never marked as a failure: the learner sees the outcome and the explanation either way.
Feedback for a right answer
The same entropy, $0.47$ ⁠ bits. The formula does not change when $p$ ⁠ and $1-p$ ⁠ swap, so the curve is symmetric about 50%: a coin biased to tails is exactly as predictable as one biased the same amount to heads.

Hint
Write down the new coin’s two probabilities and two surprises. What has changed?

Worked solution
1. On a coin with a 10% chance of heads, heads carries $3.32$ ⁠ bits and tails $0.15$ ⁠: the same two surprises, with the roles swapped.
2. The weights swap too: $H = 0.1 \times 3.32 + 0.9 \times 0.15 \approx 0.47$ ⁠.
3. The entropy equals that of the 90% coin.
What sets the entropy is how easy the flip is to guess, not which way the coin leans.
Step 3 of 5
Open this step
A certain coin
Practice · Predict, then look
Question
What will the entropy be when the coin always lands heads? Write a number in bits per flip, and then Chance of heads moves to 100%.

Correct answer
0 ± 0.01
A number prediction counts as right within ± 0.01
Setup, choices and feedback
The Scene at this step
Chance of heads
90 %fixed
Code block size
4 flipsdefaulthidden
Measure and compress
Entropyfixed
Once the prediction is locked in, the Scene changes
Chance of heads
100 %fixed
Measure and compress
Entropyfixed
The Scene then shows: 0 · Shannon entropy of one flip, H(p), in bits: the average surprise and the least any code can spend per flip/nodes/stream/outputs/entropy
A prediction is never marked as a failure: the learner sees the outcome and the explanation either way.
Feedback for a right answer
Zero. When the outcome is certain there is no uncertainty to remove: heads carries $-\log_2 1 = 0$ ⁠ bits, and tails never happens. Such a coin tells you nothing, even after a hundred flips.

Feedback for a wrong answer
The tape does print a bit for every flip, but the whole tape could have been written in advance, without looking at the coin. How much surprise is in that?

Hint
If you knew the whole tape before the first flip, how much would it tell you?

Worked solution
1. $p = 1$ ⁠: heads on every flip.
2. The surprise of heads: $-\log_2 1 = 0$ ⁠, because $2^0 = 1$ ⁠.
3. Tails never happens, so it adds $0$ ⁠ to the average.
4. $H = 1 \times 0 + 0 = 0$ ⁠ bits per flip.
If you wrote $1$ ⁠, you thought each flip carries a bit because the tape prints one bit per flip. That is the length of the record, not the information.
Step 4 of 5
Open this step
In between
Practice · Reach the target
Question
Change Chance of heads until the coin’s entropy is $0.81$ ⁠ bits per flip, then press Check.

Goal
- 0.811 ± 0.005
  At the start of the step: 1
Setup, choices and feedback
The Scene at this step
Chance of heads
50 %
Code block size
4 flipsdefaulthidden
Measure and compress
Entropyfixed
Read from the Scene at
Shannon entropy of one flip, H(p), in bits: the average surprise and the least any code can spend per flip/nodes/stream/outputs/entropy
One setting that reaches it
Chance of heads
25 %
Feedback for a right answer
At 75% (or 25%): $0.75 \times 0.415 + 0.25 \times 2 \approx 0.81$ ⁠. A coin that lands heads three flips out of four is still fairly surprising: four fifths of a bit per flip.

Feedback for a wrong answer
Not yet. Move the marker along the curve until its height is $0.81$ ⁠.

Hint
The entropy falls as you move away from 50%. Try a coin that lands heads three flips out of four.

Worked solution
1. You want $H(p) \approx 0.81$ ⁠.
2. Try $p = 0.75$ ⁠: heads carries $-\log_2 0.75 \approx 0.415$ ⁠, and tails $-\log_2 0.25 = 2$ ⁠.
3. $H = 0.75 \times 0.415 + 0.25 \times 2 \approx 0.311 + 0.5 = 0.811$ ⁠.
4. Set Chance of heads to 75%. 25% works too, since the curve is symmetric.
Step 5 of 5
Open this step
Random noise is full of information
Practice · Choose
Question
Two tapes of bits, the same length. Tape A looks completely random: about as many 0s as 1s, with no pattern at all. Tape B is almost all 1s. Which tape has the higher entropy per bit?

Correct answer
- Correct Tape A, the random one
Setup, choices and feedback
The Scene at this step
Chance of heads
50 %
Code block size
4 flipsdefaulthidden
Measure and compress
Entropy
Choices
Shown in a random order.
- Correct Tape A, the random one
- Wrong Tape B, because a random tape carries no message
  Misconception: Thinks a random-looking stream with no pattern carries little information, because it means nothing.
  Feedback from the catalogue
  The opposite is true. Information in Shannon’s sense is uncertainty, and a random stream with no pattern is as unpredictable as anything can be: you cannot guess its next bit, so every bit surprises. Its entropy is close to one bit per bit, the most there is. A stream that is almost all 1s is easy to guess, and its entropy is close to zero. That is also why a compressed or encrypted file looks like noise: everything predictable has already been taken out of it.
- Wrong Both the same, because they are the same length
  Feedback
  A tape’s length says how many bits are written on it, not how much information they carry. You could guess almost all of tape B without reading it.
Feedback for a right answer
Tape A. When you cannot guess the next bit, every bit surprises, and that is exactly high entropy: close to one bit per bit. On tape B the guess “one” is almost always right, so each bit tells you little.

Hint
On which tape is the next bit harder to guess?

Worked solution
1. Entropy measures how hard the next symbol is to guess.
2. On tape A each bit is like a fair coin flip: the entropy is close to $1$ ⁠ bit per bit.
3. On tape B the guess “one” is almost always right: the entropy is close to $0$ ⁠.
4. So tape A has the higher entropy.
If you chose tape B, you thought a random tape carries no information because it has no meaning. Information in Shannon’s sense is uncertainty, and random noise is as unpredictable as anything can be.

Lesson 3 of 5 · About 25 minutes

Compression

How Huffman's code shortens predictable data: short words for common blocks, why a fair coin does not compress, and why no code goes below the entropy.

Open the lesson

The 5 steps and their answers

Step 1 of 5
Open this step
Short words for what is common
Practice · Calculate
Question
Chance of heads is 90% and Code block size is two flips. Huffman’s code gives each pair a codeword: heads-heads 0, heads-tails 10, tails-tails 110, tails-heads 111. The pairs’ probabilities are $0.81$ ⁠, $0.09$ ⁠, $0.01$ ⁠ and $0.09$ ⁠, in the same order. How many bits does a pair cost, on average?

Correct answer
1.29 ± 0.01
Setup, choices and feedback
The Scene at this step
Chance of heads
90 %fixed
Code block size
2 flipsfixed
Measure and compress
Compressedfixed
Accepted within
± 0.01
Computed from the Scene at this step’s setting
Average codeword length, in bits, for one block of blockSize flips/nodes/stream/outputs/bitsPerBlock
Wrong answers it recognises
- 2.25 ± 0.01
  Misconception: Averages the surprises (or codeword lengths) as if every outcome were equally likely, without weighting each by its probability.
  Feedback from the catalogue
  Entropy, and the average cost of a code too, is a weighted average: each value counts by its probability. With a 90% coin, heads turns up in nine flips out of ten and tails in one, so $H = 0.9 \times 0.15 + 0.1 \times 3.32 \approx 0.47$ ⁠, not $\tfrac{0.15 + 3.32}{2} \approx 1.74$ ⁠. A plain average treats the rare tails as if it turned up in half the flips.
Feedback for a right answer
$0.81 \times 1 + 0.09 \times 2 + 0.01 \times 3 + 0.09 \times 3 = 1.29$ ⁠ bits a pair, instead of $2$ ⁠ on the upper tape. That is $0.645$ ⁠ bits a flip: the code saves more than a third.

Hint
Multiply each codeword’s length by its pair’s probability, and add.

Worked solution
1. The codeword lengths: $1$ ⁠, $2$ ⁠, $3$ ⁠ and $3$ ⁠ bits.
2. The pairs’ probabilities: $0.81$ ⁠, $0.09$ ⁠, $0.01$ ⁠ and $0.09$ ⁠.
3. Weighted average: $0.81 \times 1 + 0.09 \times 2 + 0.01 \times 3 + 0.09 \times 3 = 0.81 + 0.18 + 0.03 + 0.27 = 1.29$ ⁠.
4. A pair costs $1.29$ ⁠ bits on average.
If you got $2.25$ ⁠, you took a plain average of the lengths, $\tfrac{1 + 2 + 3 + 3}{4}$ ⁠. But the pair heads-heads, with the shortest word, turns up 81% of the time, and that is the whole secret of compression.
Step 2 of 5
Open this step
Nothing to bet on
Practice · Predict, then look
Question
The coin is fair, and the code reads blocks of four flips. When you open the compressed tape, how many bits per flip will it cost?

Correct answer
- Correct Exactly one bit per flip, like the upper tape
Setup, choices and feedback
The Scene at this step
Chance of heads
50 %fixed
Code block size
4 flipsfixed
Measure and compress
Entropyfixed
Choices
- Correct Exactly one bit per flip, like the upper tape
- Wrong Less than a bit, because a good code always saves something
  Misconception: Thinks any data can be squeezed below its entropy: with a cleverer code, longer blocks, or by compressing the compressed result again.
  Feedback from the catalogue
  Shannon proved that no code that loses nothing can spend fewer bits on average than the entropy. For a 90% coin the limit is $0.47$ ⁠ bits a flip: longer blocks bring the code close to it, but never past it. A fair coin, with an entropy of $1$ ⁠, cannot be compressed at all. And a tape that has already been compressed looks like a fair coin, so compressing it a second time saves nothing more.
- Wrong More than a bit, because the code adds long codewords
  Feedback
  Huffman’s code never costs more than the plain record: when there is nothing to bet on, it gives every block a word of the same length.
Once the prediction is locked in, the Scene changes
Measure and compress
Compressedfixed
The Scene then shows: 1 · Average bits per flip the Huffman code over blocks of blockSize spends (1 for the bare tape)/nodes/stream/outputs/bitsPerFlip
A prediction is never marked as a failure: the learner sees the outcome and the explanation either way.
Feedback for a right answer
Exactly one bit. With a fair coin each of the $16$ ⁠ blocks turns up with the same probability, $\tfrac{1}{16}$ ⁠, so no block deserves a short word: they all get four bits, and the lower tape is exactly as long as the upper one. The entropy is $1$ ⁠ bit per flip, and there is nothing to save.

Hint
With a fair coin, is any block of four flips likelier than another?

Worked solution
1. With a fair coin each block of four flips has probability $\left(\tfrac12\right)^4 = \tfrac{1}{16}$ ⁠.
2. When all $16$ ⁠ blocks are equal, the best code gives each one four bits: $\log_2 16 = 4$ ⁠.
3. Four bits for four flips: one bit per flip.
4. That is also the entropy of a fair coin, the limit no code can go below.
Compression is a bet on what is likely. When nothing is likelier than anything else, there is nothing to bet on.
Step 3 of 5
Open this step
Longer blocks
Practice · Reach the target
Question
Chance of heads is fixed at 90%. In blocks of one flip the code saves nothing: one bit per flip. Change Code block size until the code costs about $0.49$ ⁠ bits per flip, then press Check.

Goal
- 0.49 ± 0.005
  At the start of the step: 1
Setup, choices and feedback
The Scene at this step
Chance of heads
90 %fixed
Code block size
1 flips
Measure and compress
Compressedfixed
Read from the Scene at
Average bits per flip the Huffman code over blocks of blockSize spends (1 for the bare tape)/nodes/stream/outputs/bitsPerFlip
One setting that reaches it
Code block size
4 flips
Feedback for a right answer
In blocks of four: $0.49$ ⁠ bits per flip, very close to the $0.47$ ⁠ limit. The longer the block, the more different probabilities the code has to work with, and the cost closes in on the entropy from above.

Feedback for a wrong answer
Not yet. In blocks of two the code costs $0.645$ ⁠, and in three $0.53$ ⁠. Keep going.

Hint
Try longer blocks, one after another, and watch the count under the lower tape.

Worked solution
1. A block of one flip: two one-bit codewords, $1$ ⁠ bit per flip.
2. Blocks of $2$ ⁠: $0.645$ ⁠. Blocks of $3$ ⁠: $0.533$ ⁠.
3. Blocks of $4$ ⁠: $0.49$ ⁠.
4. Set Code block size to $4$ ⁠. At five and six the cost keeps falling slowly, toward $0.47$ ⁠.
A single flip does not compress, because a codeword cannot be shorter than one bit.
Step 4 of 5
Open this step
No word starts another
Practice · Choose
Question
In Huffman’s code for blocks of four flips of a 90% coin, the block four heads, the most common of all, gets a one-bit codeword. What does the block four tails, the rarest of all, get?

Correct answer
- Correct A codeword longer than four bits
Setup, choices and feedback
The Scene at this step
Chance of heads
90 %fixed
Code block size
4 flipsfixed
Measure and compress
Compressed
Choices
Shown in a random order.
- Correct A codeword longer than four bits
- Wrong Four bits, as on the upper tape
  Feedback
  If every block but one got four bits, there would be no room for a one-bit word: such a word “uses up” half of all possible words, because no other word may start with it.
- Wrong Also one bit
  Feedback
  Two blocks cannot share a codeword, or the receiver would not know which one was sent.
Feedback for a right answer
Ten bits. So that no codeword is the start of another, the short words of the common blocks “use up” room, and the rare blocks pay with long words. Four tails is so rare, probability $0.0001$ ⁠, that the price hardly shows in the average.

Hint
A one-bit word is the start of half of all possible words. Who pays for that?

Worked solution
1. In a code where no word is the start of another, the tape can be read with no gaps.
2. The word 0 for four heads rules out every other word that starts with 0: half of all words.
3. The other $15$ ⁠ blocks must start with 1, so some of them get words longer than four bits.
4. The rarest blocks, four tails among them, get the longest: ten bits.
A good code does not give every block the same length. It gives short words to what is common, and long ones to what is rare.
Step 5 of 5
Open this step
The limit
Practice · Choose
Question
A coin lands heads 90% of the time. Someone offers a clever code that records its flips, losing none, at $0.4$ ⁠ bits per flip on average, over millions of flips. What do you make of it?

Correct answer
- Correct It is impossible: the entropy, $0.47$ ⁠ bits per flip, is the limit
Setup, choices and feedback
The Scene at this step
Chance of heads
90 %
Code block size
6 flips
Measure and compress
Compressed
Choices
Shown in a random order.
- Correct It is impossible: the entropy, $0.47$ ⁠ bits per flip, is the limit
- Wrong It is possible, given long enough blocks
  Misconception: Thinks any data can be squeezed below its entropy: with a cleverer code, longer blocks, or by compressing the compressed result again.
  Feedback from the catalogue
  Shannon proved that no code that loses nothing can spend fewer bits on average than the entropy. For a 90% coin the limit is $0.47$ ⁠ bits a flip: longer blocks bring the code close to it, but never past it. A fair coin, with an entropy of $1$ ⁠, cannot be compressed at all. And a tape that has already been compressed looks like a fair coin, so compressing it a second time saves nothing more.
- Wrong It is possible: compress the compressed tape a second time
  Misconception: Thinks any data can be squeezed below its entropy: with a cleverer code, longer blocks, or by compressing the compressed result again.
  Feedback from the catalogue
  Shannon proved that no code that loses nothing can spend fewer bits on average than the entropy. For a 90% coin the limit is $0.47$ ⁠ bits a flip: longer blocks bring the code close to it, but never past it. A fair coin, with an entropy of $1$ ⁠, cannot be compressed at all. And a tape that has already been compressed looks like a fair coin, so compressing it a second time saves nothing more.
Feedback for a right answer
Shannon proved that no code that loses nothing can spend fewer bits on average than the entropy. Longer blocks bring the code close to $0.47$ ⁠, but not below. And a compressed tape already looks random, with an entropy of about one bit per bit, so a second compression gives nothing.

Hint
What did Shannon prove about the entropy and every code that loses nothing?

Worked solution
1. The entropy of a 90% coin: $H \approx 0.47$ ⁠ bits per flip.
2. By Shannon, every code that loses nothing spends at least $H$ ⁠ bits per flip on average.
3. $0.4 < 0.47$ ⁠, so the offer is impossible.
The ways around the limit do not work either: in blocks of six flips the code costs $0.47$ ⁠, right at the limit, and a tape that is already compressed hardly compresses further.

Lesson 4 of 5 · About 20 minutes

The parity bit

A noisy line flips bits: how many blocks arrive wrong, how one parity bit catches a flip, and what it cannot catch.

Open the lesson

The 5 steps and their answers

Step 1 of 5
Open this step
A noisy line
Practice · Calculate
Question
Chance a bit flips is fixed at 5%. Each block carries four bits, and each bit flips independently of the others. What is the chance that a block arrives with at least one error? Answer in per cent.

Correct answer
18.55 ± 0.2
Setup, choices and feedback
The Scene at this step
Chance a bit flips
5 %fixed
Check and repair
Bare bitsfixed
Accepted within
± 0.2
Computed from the Scene at this step’s setting
Chance a block of four bare data bits arrives wrong (0..1)/nodes/link/outputs/rawBlockError
Wrong answers it recognises
- 20 ± 0.2
  Misconception: Adds the chances of independent events (4 × 5% = 20%) instead of working out the chance through the complement, 1 − (1 − p)ⁿ.
  Feedback from the catalogue
  Adding chances works only for disjoint events, which cannot happen together. Flips of different bits can happen together, so adding counts twice the blocks in which two bits flipped, and with enough bits it would pass 100%. Use the complement: a block arrives intact only if every bit survives, $(1-p)^n$ ⁠, so the chance of at least one error is $1 - (1-p)^n$ ⁠. For four bits at 5%: $1 - 0.95^4 \approx 18.5\%$ ⁠, not 20%.
Feedback for a right answer
$1 - 0.95^4 \approx 0.185$ ⁠, that is about 18.5%: roughly one block in five. A block is intact only if all four bits survive, $0.95^4 \approx 0.815$ ⁠, and the rest are wrong.

Hint
The complement is easier: what is the chance that all four bits survive?

Worked solution
1. Each bit survives with chance $1 - 0.05 = 0.95$ ⁠.
2. The bits are independent, so all four survive with chance $0.95^4 \approx 0.815$ ⁠.
3. The complement: at least one error with chance $1 - 0.815 = 0.185$ ⁠.
4. The answer: about 18.5%.
If you got 20%, you added $4 \times 5\%$ ⁠. Adding counts twice the blocks in which two bits flipped, so it comes out too big.
Step 2 of 5
Open this step
A storm
Practice · Predict, then look
Question
Now a storm hits the line: Chance a bit flips goes up to 15% for each bit. Roughly what share of four-bit blocks will arrive wrong?

Correct answer
- Correct About half: roughly 48%
Setup, choices and feedback
The Scene at this step
Chance a bit flips
5 %fixed
Check and repair
Bare bitsfixed
Choices
- Correct About half: roughly 48%
- Wrong 60%: four times 15%
  Misconception: Adds the chances of independent events (4 × 5% = 20%) instead of working out the chance through the complement, 1 − (1 − p)ⁿ.
  Feedback from the catalogue
  Adding chances works only for disjoint events, which cannot happen together. Flips of different bits can happen together, so adding counts twice the blocks in which two bits flipped, and with enough bits it would pass 100%. Use the complement: a block arrives intact only if every bit survives, $(1-p)^n$ ⁠, so the chance of at least one error is $1 - (1-p)^n$ ⁠. For four bits at 5%: $1 - 0.95^4 \approx 18.5\%$ ⁠, not 20%.
- Wrong 15%, the same as one bit’s chance
  Feedback
  A block is wrong if any of its four bits flipped, so it is hit more often than any one bit on its own.
Once the prediction is locked in, the Scene changes
Chance a bit flips
15 %fixed
The Scene then shows: 0.478 · Chance a block of four bare data bits arrives wrong (0..1)/nodes/link/outputs/rawBlockError
A prediction is never marked as a failure: the learner sees the outcome and the explanation either way.
Feedback for a right answer
$1 - 0.85^4 \approx 1 - 0.52 = 0.48$ ⁠. Almost every other block arrives with an error, and without a code the receiver cannot tell which.

Hint
Work out the chance a block survives: $0.85^4$ ⁠.

Worked solution
1. Each bit survives with chance $0.85$ ⁠.
2. All four survive with chance $0.85^4 \approx 0.522$ ⁠.
3. At least one error: $1 - 0.522 \approx 0.478$ ⁠, about 48%.
If you chose 60%, you added the chances. With seven bits adding would give 105%, more than certainty, which shows it cannot be right.
Step 3 of 5
Open this step
A quieter line
Practice · Reach the target
Question
Change Chance a bit flips until about one block in ten, 10%, arrives with an error, then press Check.

Goal
- 0.1 ± 0.01
  At the start of the step: 0.3439
Setup, choices and feedback
The Scene at this step
Chance a bit flips
10 %
Check and repair
Bare bitsfixed
Read from the Scene at
Chance a block of four bare data bits arrives wrong (0..1)/nodes/link/outputs/rawBlockError
One setting that reaches it
Chance a bit flips
2.5 %
Feedback for a right answer
About 2.5% per bit: $1 - 0.975^4 \approx 0.096$ ⁠. When the chance is small, adding, $4 \times 2.5\% = 10\%$ ⁠, comes close, because hardly any block is hit twice. As the noise grows, the gap between adding and the right answer grows.

Feedback for a wrong answer
Not yet. Look for a chance per bit at which $1 - (1-p)^4 \approx 0.1$ ⁠.

Hint
When the chances are small, a block is hit about four times as often as a bit.

Worked solution
1. You want $1 - (1-p)^4 \approx 0.1$ ⁠, that is $(1-p)^4 \approx 0.9$ ⁠.
2. $1 - p \approx 0.9^{1/4} \approx 0.974$ ⁠, so $p \approx 0.026$ ⁠.
3. On the slider, in half-per-cent steps: 2.5% gives $1 - 0.975^4 \approx 0.096$ ⁠.
4. Set Chance a bit flips to 2.5%.
Step 4 of 5
Open this step
Count the 1s
Practice · Choose
Question
You send the four bits 1 0 1 1, and add a parity bit so that the count of 1s in all five bits is even. What is the parity bit?

Correct answer
- Correct $1$ ⁠
Setup, choices and feedback
The Scene at this step
Chance a bit flips
5 %
Check and repair
Bare bitsfixed
Choices
- Correct $1$ ⁠
- Wrong $0$ ⁠
  Feedback
  1 0 1 1 has three 1s. With a parity bit of $0$ ⁠ there are still three, and three is odd.
Feedback for a right answer
1 0 1 1 has three 1s, and a parity bit of $1$ ⁠ brings the count to four. If one bit flips on the way, the count will be odd, and the receiver will know something went wrong.

Hint
Count the 1s in the four bits. What must you add to make the count even?

Worked solution
1. Count the 1s in 1 0 1 1: three.
2. Three is odd, so one more is needed.
3. The parity bit is $1$ ⁠, and the block 1 0 1 1 1 holds four 1s.
The parity bit says nothing about the data itself. It only makes the count even, so that a single flip stands out.
Step 5 of 5
Open this step
What parity misses
Practice · Choose
Question
A block of four data bits and a parity bit sets out, and on the way two of its bits flip. What does the receiver see when it counts the 1s?

Correct answer
- Correct The count is even: the check passes, and the error goes unnoticed
Setup, choices and feedback
The Scene at this step
Chance a bit flips
5 %
Check and repair
Bare bitsfixed
Choices
Shown in a random order.
- Correct The count is even: the check passes, and the error goes unnoticed
- Wrong The count is odd: the check fails
  Misconception: Thinks a parity bit catches every error, however many bits flip.
  Feedback from the catalogue
  A parity bit only checks whether the count of 1s is even. Each flip changes the count by one, so one flip, or three, makes it odd and the check fails. But two flips change it by two, and the count stays even: the check passes, and the wrong block is taken as good. One parity check catches every odd number of flips, and misses every even number.
- Wrong The check fails and shows which two bits flipped
  Misconception: Thinks a failing parity check shows which bit flipped.
  Feedback from the catalogue
  One parity check answers just one yes-or-no question: is the count of 1s even? When it fails, any bit in the block could be to blame, the parity bit included, and the receiver can only ask for the block again. To find where the error is takes several overlapping checks, as in Hamming’s code: their answers together point to one position.
Feedback for a right answer
Each flip changes the count by one, and two flips change it by two: an even number stays even. One parity bit catches every odd number of flips, and misses every even number.

Hint
By how much does the count of 1s change when one bit flips? And when two flip?

Worked solution
1. Before sending, the block’s count of 1s is even.
2. Each flip adds one or takes one away, so it changes the parity.
3. Two flips change the parity twice, and it is even again.
4. The check passes, and the wrong block is taken as good.
Even when a parity check fails, it does not say which bit is to blame. It answers one question only: even or not.

Lesson 5 of 5 · About 25 minutes

Hamming's code

Three overlapping parity checks find which bit flipped and repair it: how to read them as a number in base 2, what happens when two bits flip, and what it costs.

Open the lesson

The 6 steps and their answers

Step 1 of 6
Open this step
Three overlapping checks
Practice · Predict, then look
Question
The line is perfectly quiet, but Faulty bit is 6: in every block the bit in position 6 flips. Which of the checks A, B and C will fail? Choose, and then Look inside moves to Parity checks.

Correct answer
- Correct B and C
Setup, choices and feedback
The Scene at this step
Chance a bit flips
0 %fixed
Faulty bit
6fixed
Bare bits / Repaired
Bare bits
Choices
- Correct B and C
- Wrong A and B
  Misconception: Reads the failing checks A B C as a binary number with A as the highest digit, instead of C B A.
  Feedback from the catalogue
  In Hamming’s code check A covers the positions whose number has its $1$ ⁠ bit set, B its $2$ ⁠ bit, and C its $4$ ⁠ bit. So A is the lowest digit: read the checks in the order C B A. When B and C fail and A passes, write 1 1 0, that is $4 + 2 = 6$ ⁠. Reading them as A B C gives 0 1 1, that is $3$ ⁠, and the receiver would flip a good bit.
- Wrong All three, because a flip spoils the whole block
  Feedback
  Each check counts only the positions it covers. A check that does not cover position 6 does not notice it flip.
Once the prediction is locked in, the Scene changes
Bare bits / Repaired
Parity checks
The Scene then shows: 6 · The failing checks read as the binary number C B A (0 when all pass): the position of a lone flip/nodes/link/outputs/syndrome
A prediction is never marked as a failure: the learner sees the outcome and the explanation either way.
Feedback for a right answer
B and C. Position 6 is in check B (positions 2, 3, 6, 7) and in check C (positions 4, 5, 6, 7), but not in A. Read the checks in the order C B A: 1 1 0, which is 6 in base 2.

Hint
A covers 1, 3, 5, 7; B covers 2, 3, 6, 7; C covers 4, 5, 6, 7. Which of them contain 6?

Worked solution
1. Write 6 in base 2: $6 = 4 + 2$ ⁠, that is 110.
2. The $4$ ⁠ bit is set: check C covers position 6 and fails.
3. The $2$ ⁠ bit is set: check B covers it and fails.
4. The $1$ ⁠ bit is clear: check A does not cover it and passes.
If you chose A and B, you read 110 left to right as A B C. But A is the lowest digit, the ones digit.
Step 2 of 6
Open this step
Reading the checks
Practice · Calculate
Question
A new fault on the line, and this time you are not shown where. In every block checks A and B fail, and check C passes. In which position does the bit flip?

Correct answer
3 ± 0.1
Setup, choices and feedback
The Scene at this step
Chance a bit flips
0 %fixed
Faulty bit
3hidden
Bare bits / Repaired
Bare bitsfixed
Accepted within
± 0.1
Computed from the Scene at this step’s setting
The failing checks read as the binary number C B A (0 when all pass): the position of a lone flip/nodes/link/outputs/syndrome
Wrong answers it recognises
- 6 ± 0.1
  Misconception: Reads the failing checks A B C as a binary number with A as the highest digit, instead of C B A.
  Feedback from the catalogue
  In Hamming’s code check A covers the positions whose number has its $1$ ⁠ bit set, B its $2$ ⁠ bit, and C its $4$ ⁠ bit. So A is the lowest digit: read the checks in the order C B A. When B and C fail and A passes, write 1 1 0, that is $4 + 2 = 6$ ⁠. Reading them as A B C gives 0 1 1, that is $3$ ⁠, and the receiver would flip a good bit.
Feedback for a right answer
Position 3: the only one in A and B but not in C. In the order C B A the checks spell 0 1 1, that is $2 + 1 = 3$ ⁠. The receiver flips that bit, and the block is repaired.

Hint
Write $1$ ⁠ for each check that failed and $0$ ⁠ for each that passed, in the order C B A.

Worked solution
1. C passed, B failed, A failed: in the order C B A that is 0 1 1.
2. In base 2: $0 \times 4 + 1 \times 2 + 1 \times 1 = 3$ ⁠.
3. Check: position 3 is in A (1, 3, 5, 7) and in B (2, 3, 6, 7), not in C (4, 5, 6, 7).
4. The bit flips in position 3.
If you answered 6, you read the checks in the order A B C, 1 1 0. Position 6 is in B and C, not in A.
Step 3 of 6
Open this step
Parity bits flip too
Practice · Reach the target
Question
Change Faulty bit until only check C fails, while A and B pass. Press Check.

Goal
- 0 ± 0.1
  At the start of the step: 0
- 0 ± 0.1
  At the start of the step: 0
- 1 ± 0.1
  At the start of the step: 0
Setup, choices and feedback
The Scene at this step
Chance a bit flips
0 %fixed
Faulty bit
0
Bare bits / Repaired
Parity checksfixed
Read from the Scene at
1 when check A (positions 1 3 5 7) fails for a block whose only flip is at fault, else 0/nodes/link/outputs/checkA
Read from the Scene at
1 when check B (positions 2 3 6 7) fails for a block whose only flip is at fault, else 0/nodes/link/outputs/checkB
Read from the Scene at
1 when check C (positions 4 5 6 7) fails for a block whose only flip is at fault, else 0/nodes/link/outputs/checkC
One setting that reaches it
Faulty bit
4
Feedback for a right answer
Position 4, 100 in base 2: it is inside circle C only, and it is C’s parity bit. A parity bit can flip on the way too, and the code finds it like any other bit.

Feedback for a wrong answer
Not yet. Watch the red circles on the board: only C should be red.

Hint
Which position is inside circle C and no other circle?

Worked solution
1. You want the pattern C B A = 1 0 0.
2. In base 2 that is $4$ ⁠.
3. Position 4 is in check C (4, 5, 6, 7) only.
4. Set Faulty bit to $4$ ⁠.
Positions 1, 2 and 4, the powers of 2, are exactly the positions inside one circle only. That is why the parity bits sit there: each belongs to its own check.
Step 4 of 6
Open this step
Two flips
Practice · Choose
Question
In one block two bits flip, in positions 3 and 5. What does the receiver do?

Correct answer
- Correct Checks B and C fail, and it flips position 6, which was fine: the block ends up with three errors
Setup, choices and feedback
The Scene at this step
Chance a bit flips
5 %
Faulty bit
0fixed
Bare bits / Repaired
Repaired
Choices
Shown in a random order.
- Correct Checks B and C fail, and it flips position 6, which was fine: the block ends up with three errors
- Wrong It finds both errors and repairs both
  Misconception: Thinks a Hamming code repairs any number of flipped bits in a block.
  Feedback from the catalogue
  The Hamming (7,4) code repairs one flip in a block. When two bits flip, the checks that fail are those of one flip or the other but not both, and the pattern points to a third bit that was fine. The receiver dutifully flips it, and the block ends up with three errors. So even with the code some blocks arrive wrong: on a line that flips 5% of bits, about 4.4% of them.
- Wrong Every check passes, and it leaves the block alone
  Feedback
  In check A, which covers both 3 and 5, the two flips do cancel. But B covers only 3, and C only 5, so both of them fail.
Feedback for a right answer
A covers both 3 and 5, and the two flips cancel in it. B covers only 3, and C only 5, so they fail: C B A = 1 1 0, that is 6. The receiver flips position 6, which was fine. The code assumes at most one flip in a block, and when that fails, so does it.

Hint
For each check on its own: how many of positions 3 and 5 does it cover? An even number of flips does not make it fail.

Worked solution
1. Check A (1, 3, 5, 7) covers 3 and 5: two flips, the count stays even, A passes.
2. Check B (2, 3, 6, 7) covers only 3: B fails.
3. Check C (4, 5, 6, 7) covers only 5: C fails.
4. C B A = 1 1 0 = 6, and the receiver flips position 6.
5. Now three bits are wrong: 3, 5 and 6.
The Hamming (7,4) code repairs one flip in a block. Repairing two takes a code with more parity bits.
Step 5 of 6
Open this step
How often the code fails
Practice · Calculate
Question
Chance a bit flips is fixed at 5%, and the code repairs. A coded block arrives wrong only if two or more of its seven bits flipped. What is the chance of that? Answer in per cent.

Correct answer
4.438 ± 0.1
Setup, choices and feedback
The Scene at this step
Chance a bit flips
5 %fixed
Faulty bit
0fixed
Bare bits / Repaired
Repairedfixed
Accepted within
± 0.1
Computed from the Scene at this step’s setting
Chance a Hamming (7,4) block takes two or more flips and is decoded wrong (0..1)/nodes/link/outputs/codedBlockError
Wrong answers it recognises
- 0 ± 0.1
  Misconception: Thinks a Hamming code repairs any number of flipped bits in a block.
  Feedback from the catalogue
  The Hamming (7,4) code repairs one flip in a block. When two bits flip, the checks that fail are those of one flip or the other but not both, and the pattern points to a third bit that was fine. The receiver dutifully flips it, and the block ends up with three errors. So even with the code some blocks arrive wrong: on a line that flips 5% of bits, about 4.4% of them.
Feedback for a right answer
About 4.4%: $1 - 0.95^7 - 7 \times 0.05 \times 0.95^6 \approx 1 - 0.698 - 0.257 = 0.044$ ⁠. Without the code 18.5% of blocks arrive wrong; the code cuts that fourfold, at the price of three extra bits for every four.

Hint
Work out the complement: no flip, $0.95^7$ ⁠, or exactly one flip, $7 \times 0.05 \times 0.95^6$ ⁠.

Worked solution
1. A coded block is repaired if zero or one of its bits flipped.
2. No flip: $0.95^7 \approx 0.698$ ⁠.
3. Exactly one flip: $7$ ⁠ possible positions, $7 \times 0.05 \times 0.95^6 \approx 0.257$ ⁠.
4. Two or more flips: $1 - 0.698 - 0.257 \approx 0.044$ ⁠, about 4.4%.
If you answered $0$ ⁠, you thought the code repairs everything. It repairs one flip in a block, and two flips fool it.
Step 6 of 6
Open this step
The price
Practice · Calculate
Question
The message HELLO is five characters, eight bits each, sent in blocks of four bits. How many bits does one copy of it take on the line with Hamming’s code?

Correct answer
70 ± 0.1
Setup, choices and feedback
The Scene at this step
Chance a bit flips
5 %fixed
Faulty bit
0fixed
Bare bits / Repaired
Repairedfixed
Accepted within
± 0.1
Computed from the Scene at this step’s setting
Bits one copy of the message takes on the line with the code: seven for every four, fourteen per character/nodes/link/outputs/codedBits
Wrong answers it recognises
- 40 ± 0.1
  Misconception: Forgets that the parity bits travel down the line too, and counts only the message's own bits.
  Feedback from the catalogue
  Parity bits do not come for free: they are sent down the line like any other bit. In the Hamming (7,4) code every four data bits leave as seven, so one character, eight bits, takes fourteen on the line. That is the price of repair: three bits out of every seven carry no part of the message.
Feedback for a right answer
$70$ ⁠ bits: $40$ ⁠ data bits make $10$ ⁠ blocks, and each block leaves as seven bits. $30$ ⁠ of them are parity bits, which carry no part of the message. That is the price of repair: the line carries data at only $\tfrac47$ ⁠ of its rate.

Hint
How many blocks of four bits are in the message, and how many bits leave for each block?

Worked solution
1. The message: $5 \times 8 = 40$ ⁠ data bits.
2. In blocks of four: $\tfrac{40}{4} = 10$ ⁠ blocks.
3. Each coded block is $7$ ⁠ bits: $10 \times 7 = 70$ ⁠.
4. One copy takes $70$ ⁠ bits on the line.
If you answered $40$ ⁠, you counted only the message’s bits. The parity bits travel down the line like any other bit.

Across the unit · 13 misconceptions

Misconception catalogue

Each common mistake this unit recognises, in a few words. Open one for what the learner reads when an answer matches it, and where it is asked.

Index

Surprise measured in bits

What information is

Question

Correct answer

The Scene at this step

Choices

Hint

Worked solution

One bit

Question

Correct answer

The Scene at this step

Wrong answers it recognises

Hint

Worked solution

A biased coin

Question

Correct answer

The Scene at this step

Choices

Once the prediction is locked in, the Scene changes

Hint

Worked solution

Every halving is a bit

Question

Correct answer

The Scene at this step

Wrong answers it recognises

Hint

Worked solution

Rare news

Question

Goal

The Scene at this step

One setting that reaches it

Hint

Worked solution

Entropy

The average surprise

Question

Correct answer

The Scene at this step

Wrong answers it recognises

Hint

Worked solution

The curve

Question

Correct answer

The Scene at this step

Choices

Once the prediction is locked in, the Scene changes

Hint

Worked solution

A certain coin

Question

Correct answer

The Scene at this step

Once the prediction is locked in, the Scene changes

Hint

Worked solution

In between

Question

Goal

The Scene at this step

One setting that reaches it

Hint

Worked solution

Random noise is full of information

Question

Correct answer

The Scene at this step

Choices

Hint

Worked solution

Compression

Short words for what is common

Question

Correct answer

The Scene at this step

Wrong answers it recognises