# Example of a prefix-free code

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 preﬁx-free source code for this source.

We want to ﬁnd 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?

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

0

100

101

110

11100

11101

11110

11111

• 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. – gnasher729 Feb 2 at 18:01