0
$\begingroup$

I have a random source which is with no memory and have this alphabet (A,B,C). Each symbol in the alphabet has a probability ( A = 0.5, B= 0.25, C = 0.25) It's given that each message including exactly 60 chars.
And need to fund a Huffman code when we coding a pair of chars and the channel gets those chars ( 0, 1, 2).

I know how to do it when the channel gets only two chars (0,1).

I created the pairs of chars, and calculated the probability of each pair 

AA 0.25
AB 0.125
AC 0.125
BA 0.125
BB 0.0625
BC 0.0625
CA 0.125
CB 0.0625
CC 0.0625

after that I sorted the list and the final result is :

AA 0.25
AB 0.125
AC 0.125
BA 0.125
CA 0.125
BB 0.0625
BC 0.0625
CB 0.0625
CC 0.0625

now I know how to solve it when the channel gets only (0,1) but How to solve it when the channel get (0,1,2)? how to create the Huffman code with three channel symbols?

$\endgroup$
3
  • $\begingroup$ The algorithm to construct a $n$-ary Huffman code is exactly the same as in the binary case, except that at each step you take the $n$ least probable values instead of the two least probable. $\endgroup$ Commented Jan 27, 2014 at 10:40
  • $\begingroup$ You also need to add dummy symbols (with probability 0) to ensure that in the last step, you have $n$ symbols remaining. That is, with $k$ steps left, $1+k(n-1)$ symbols should be remaining. $\endgroup$ Commented Jan 27, 2014 at 10:49
  • $\begingroup$ right! I didn't solve this kind of questions a long time and I was confused with Fanno :) $\endgroup$ Commented Jan 27, 2014 at 11:11

1 Answer 1

Reset to default
1
$\begingroup$

To do an n-ary Huffman code, you can simply use the algorithm used in the binary case, but taking the n least probable values instead of the 2 least probable.

However, there is something more to do before the algorithm : in order to build a well-constructed n-ary Huffman tree, you need your number of possbilities to be congruent to 1 modulo n-1 (because at each iteration, you compress n nodes into a single one, as if you removed n-1 possibilities).

In your case, you have 9 possibilities and n-1 = 2 so you are good to go, but if it wasn't the case, you would simply have to add another with probability 0.

$\endgroup$
2
  • $\begingroup$ right! I didn't solve this kind of questions a long time and I was confused with Fanno :) Thank you for refreshing my memory :) $\endgroup$ Commented Jan 27, 2014 at 11:12
  • 1
    $\begingroup$ You're welcome ! :) $\endgroup$ Commented Jan 27, 2014 at 11:15

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.