Encoding a channel with Huffman Code

Question

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?

Answer 1

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.