retagged by
2,873 views
5 votes
5 votes
we use huffman encoding to encode a b c with frequency fa fb fc.Which of the following code sequence is not possible?

code 1={0,10,11}

code 2={0,00,1}

code 3={10,00,01}
retagged by

4 Answers

4 votes
4 votes
Only code 1  is possible

Code 2 and code 3 is not possible.

Code 2 => 0 & 00. Here give 000, we can not distinguish 0 00 and 00 0 and 0 0 0.

Code 3 => Here issue is that this code can not be generated by Huffman algorithm in first place. It is simply not possible. (Try to take any example you can see you can not generate this. You can generate (00,01,10,11) but not just 3 of those !)
1 votes
1 votes
b is not posiible

try to make tree like huffman algo quetion.

http://www.cs.umd.edu/class/fall2012/cmsc132h/Projects/P7/project7.html
edited by
1 votes
1 votes

Huffman coding makes sure that there is no ambiguity when we decode the bit stream code .so the 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.

so code 1 which is possible ...this follow the prefix property ... ( no prefix is otherone prefix)..

code 2 which is not possible ... bcoz 00 does not follow the prefix property , 0 is code 00 also contain 0 as prefix , 

code 3  it follows prefix property  but one of them should be only one bit code ....so its not possible..

ref :http://www.geeksforgeeks.org/greedy-algorithms-set-3-huffman-coding/

 

edited by
0 votes
0 votes

I think code2 and code3 are not possible

Code2 = last level of code should be 1 bit. 0 and 1 in the same huffman tree and then 2 bit code 00 not possible.If the tree at the last level ended with 0 , the extended part will be 10 and 11.(See pic)

Code3= not possible as all 2 bit code. As we know last level of code of huffman tree must be 1 bit

Related questions

1 votes
1 votes
2 answers
2
Akash Kumar Roy asked Apr 26, 2018
3,933 views
what is Space complexity of Huffman coding?
1 votes
1 votes
3 answers
4
Parshu gate asked Nov 16, 2017
2,589 views
The following message is: GATE2018GAATTTEEEE22000011188What is the average length of bits required for encoding each letter using Huffman coding___?