1
$\begingroup$

According to wikipedia, Kraft's inequality holds with equality when a code is complete. Huffman encoding produces a complete code that is optimal. Are all complete codes optimal and vice versa?

$\endgroup$
2
$\begingroup$

No. If I have three symbols with probabilities A = 0.5, B = 0.25 and C = 0.25 then A=0, B=10, C=11 is complete and optimal. B=0, A=10, C=11 is complete but absolutely not optimal.

An optimal code on the other hand must be complete, because otherwise you can shorten the encoding of some symbol.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.