Coding Theory
- Related pages
Related video: https://www.khanacademy.org/computing/computer-science/informationtheory/info-theory/v/source-encoding-language-of-coins-4-9
Source encoding #
Say Alice and Bob want to communicate with each other over some cable. They both live far from each other, so they decided to run a wire between both of their houses. Their communication has been working fine until winter. When winter arrived, lots wind noise started to happen and they are unable to communicate with each other over their cable communication system. With the wind, it becomes impossible to hear the signal over the noise.
Bob then encodes the message using plucks instead of voice. Plucks generate a much higher noise, so it’s much better to hear on the other side, however, how can Bob encode the message as plucks?
Discrete source #
The discrete source is a selection of a finite number of symbols. Say we have 2 common dice (6 possible numbers in each dice), totaling 12 possible numbers.
| Dice A | Dice B |
|---|---|
| 1 | 1 |
| 2 | 2 |
| 3 | 3 |
| 4 | 4 |
| 5 | 5 |
| 6 | 6 |
If Bob wants to send the result of rolled dice A with a result of 4, he could send 4 plucks, or the result of 12 (dice A + B), that would be 12 plucks. This may seem OK up to a certain point, but as your numbers grew (max of 12 in this example), it may be harder to understand the signal, so the message needs to be sent slowly so the other end can understand. The rate (or capacity) is the amount of time it takes for each plug to be sent, for example, say number 2 (2 plucks) takes an average of 2 second per pluck, so 4 seconds in total.