Got a YouTube account?

Νέο: ενεργοποιείστε μεταφράσεις και λεζάντες που δημιουργήθηκαν από θεατές στο κανάλι σας στο YouTube!

English υπότιτλους

← Source Encoding (Language of Coins: 4/9)

Introduction to coding theory (variable length source coding) with a lossless compression problem. This simplified problem only deals with sending unary symbols (plucks) to send single symbols. Source encoding attempts to compress the data from a source in order to transmit it more efficiently.

Πάρτε τον Κωδικό ενσωμάτωσης
11 Γλώσσες

Showing Revision 8 created 05/30/2013 by Mike Ridgway.

  1. We begin with a problem.
  3. Alice and Bob live in tree forts,
  4. which are far apart,
  5. with no line of sight between them.
  6. And they need to communicate.
  7. So they decide to run a wire
  8. between the two houses.
  9. They pull the wire tight,
  10. and attach a tin can to each end –
  11. allowing them to send their voices
  12. faintly along the wire.
  13. [BOB - MUFFLED] "Hello?"
  14. [ALICE - MUFFLED] Hello? I can't hear you.
  15. [BOB - MUFFLED] I can hear you, but just barely.
  16. [ALICE - MUFFLED] 1. 2. 3. 4. 5.
  17. However, there is a problem:
  18. 'noise.'
  19. Whenever there is a high wind,
  20. it becomes impossible to hear
  21. the signal over the noise.
  22. So they need a way to increase
  23. the energy level of the signal,
  24. to separate it from the noise.
  25. This gives Bob an idea.
  26. They can simply pluck the wire,
  27. which is much easier to detect over the noise.
  28. But this leads to a new problem.
  29. How do they encode their messages as plucks?
  30. Well, since they want to play
  31. board games across a distance,
  32. they tackle the most common messages first –
  33. the outcome of two dice rolls.
  34. In this case, the messages they are sending
  35. can be thought of as a selection
  36. from a finite number of 'symbols' –
  37. in this case, the eleven possible numbers,
  38. which we call a 'discrete source.'
  39. At first, they decide to use the simplest method.
  40. They send the result as the number of plucks.
  41. So, to send a '3,' they send three plucks.
  42. '9' is nine plucks.
  43. And '12' is twelve plucks.
  44. However, they soon realize that this takes
  45. much longer than it needs to.
  46. From practice, they find that their maximum pluck speed
  47. is two plucks per second.
  48. Any faster, and they will get confused.
  49. So two plucks per second can be thought of as the 'rate' –
  50. or 'capacity' – for sending information in this way.
  52. And it turns out that
  53. the most common roll is a 7 –
  54. so it takes 3.5 seconds to send the number 7.
  56. Alice then realizes they can do much better
  57. if they change their coding strategy.
  58. She realizes that the odds of each number being sent
  59. [follow] a simple pattern.
  60. There is one way to roll a 2.
  61. [There are] two ways to roll a 3.
  62. Three ways to roll a 4.
  63. Four ways to roll a 5.
  64. Five ways to roll a 6.
  65. And six ways to roll a 7 –
  66. the most common [result].
  67. And five ways to roll an 8.
  68. Four ways for a 9 –
  69. and so on, back to one way for a 12.
  70. This is a graph showing
  71. the number of ways each result can occur.
  72. And the pattern is obvious.
  73. So now, let's change the graph to
  74. 'number of plucks versus each symbol.'
  75. She proceeds by mapping
  76. the most common number –
  77. 7 – to the shortest signal – one pluck.
  79. She then proceeds to the next most probable number.
  80. And if there is a tie, she picks one at random.
  81. In this case, she selects 6 to be two plucks,
  82. and then 8 to be three plucks,
  83. and then back to 5 to be four plucks,
  84. and 9 is five plucks,
  85. and back and forth, until we reach 12,
  86. which is assigned to 11 plucks.
  87. Now, the most common number, 7,
  88. can be sent in less than a second –
  89. a huge improvement.
  90. This simple change allows them to send
  91. more information in the same amount of time, on average.
  92. In fact, this coding strategy is optimal
  93. for this simple example –
  94. in that it's impossible for you
  95. to come up with a shorter method
  96. of sending two dice rolls – using identical plucks.
  97. However, after playing with the wire for some time,
  98. Bob hits on a new idea.