1
$\begingroup$

I came across the following question:

A source $X$ emits symbols from the alphabet $A_x$ with $|A_x| = 8$. We want to construct a prefix-free source code for this source.

We want to find a code with codeword lengths $(1,3,3,3,5,5,5,5)$. Can such a code exist? If yes, give such a code. If not, prove that.

I checked Kraft's inequality for the given set of lengths and it's fulfilled. So how can we write such a code?

$\endgroup$
  • $\begingroup$ Proofs of Kraft's inequality would indicate an algorithm for constructing the code. $\endgroup$ – Yuval Filmus Feb 2 at 6:10
2
$\begingroup$

0

100

101

110

11100

11101

11110

11111

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ If you want codes in lexicographic order, each code in this list is actually forced. So you don't actually need to evaluate Kraft's inequality, just write down codes with the given lengths until you either run out of possibilities or you don't. $\endgroup$ – gnasher729 Feb 2 at 18:01

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.