• 0

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