Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Reddit
Contact us
Hide Buttons

Create a protocol to transmit numbers efficiently or Huffman coding puzzle


Problem statment

There are two people on different sides of the bridge. The only way they can communicate is via Flash lights. One person wants to communicate the numbers, came up with roll of two dices, meaning numbers between 2 – 12. Design a protocol which communicates these numbers with minimum number of flash lights.

Observations

  • Flash light can turn on – off, represts Binary numbers 0, 1
  • We need to communicate numbers between 2 – 12 they have some distribution. If you see the distribution of two random dice roll then it will look as the following

dicediagram

And you can notice the number 7 has the most probability. The frequency distribution will look like the following

rolling-two-dice-bar-chart-of-scores


To use the minimum number of flash lights we need to assign the minimum number of bits to the numbers which has the highest frequency.

Solution

Huffman coding is a lossless data compression algorithm with the following characteristics.

  • The most frequent character gets the smallest code and the least frequent character gets the largest code.
  • The variable-length codes assigned to input characters are Prefix Codes, means the codes (bit sequences) are assigned in such a way that the code assigned to one character is not prefix of code assigned to any other character.
  • This is how Huffman Coding makes sure that there is no ambiguity when decoding the generated bit stream.

Refer to the following article to learn more about the implementation details of the Huffman Coding


You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *