Talk:Kraft–McMillan inequality

Proof of existence of a prefix code doesn't seem to make sense to me

I'm talking about this:

Conversely, given any ordered sequence of $n$ natural numbers,

$\ell _{1}\leq \ell _{2}\leq \dots \leq \ell _{n}$

satisfying the Kraft's inequality, one can construct a prefix code with codeword lengths equal to $\ell _{i}$ by pruning subtrees from a full $r$-ary tree of depth $\ell _{n}$. First choose any node from the full tree at depth $\ell _{1}$ and remove all of its descendents. This removes $r^{-\ell _{1}}$ fraction of the nodes from the full tree from being considered for the rest of the remaining codewords. Next iteration removes $r^{-\ell _{2}}$ fraction of the full tree for total of $r^{-\ell _{1}}+r^{-\ell _{2}}$. After $m$ iterations,

$\sum _{i=1}^{m}r^{-\ell _{i}}$

fraction of the full tree nodes are removed from consideration for any remaining codewords. But, by the assumption, this sum is less than 1 for all $m<n$, thus prefix code with lengths $\ell _{i}$ can be constructed for all $n$ source symbols.

First, it's wrong that purging a node at depth $\ell _{1}$ removes $r^{-\ell _{1}}$ fraction of the nodes from the full tree. It would be true for leaf nodes. But this isn't of much help either. Just knowing that we have $r^{-k}$ of the leaf nodes yet unpurged does not mean that we have a whole full subtree at depth k yet unpurged. Is the above-quoted text actually meant to be a proof?

Hi @Darij:. If I read the history right, you left that unsigned comment on 24 April 2011‎. If you are still interested, note that I've just reworked the proof in question. Hopefully it makes more sense now. Cheers, Gamall Wednesday Ida (talk) 19:49, 28 September 2016 (UTC)

Hi @Gamall Wednesday Ida:. Thanks for the edits! The proof has grown much in clarity while I was away! (And yes, that was me, back before I had an idea how to sign edits.) I have taken the liberty to edit it even further, hopefully clarifying a few more things. While the proof was morally correct, the way it was written the logic was slightly backwards: the algorithm works not because we don't remove more leaves than we have (removing leaves is never the intent, but always just an effect!), but because we always can find a surviving node at level $\ell _{i}$. The leaves are just the canary that tells us that we can indeed find such a node. (This is purely an issue of writing.) Darij (talk) 06:29, 6 December 2016 (UTC)

Hello Darij! Thanks for giving this some attention. I agree with the point above. I've taken a very quick look at the current state and am not convinced it's optimal yet. The use of strict inequalities at the end, even if justified for k < n, might end up confusing matters. More crucially, the sentence It clearly suffices to check that up until the last step, there is at least one leaf node remaining (because as long as there is at least one leaf node, there is also at least one node at each level $\leq \ell _{n}$) seems flatly false to me, and is backwards compared to what you say, correctly, above. Having a leaf left of course does not automatically mean you can fit anything *above* (shorter length) that. I'll look more into it sometime, but can't say when, as I'm rather busy at the moment. — Gamall Wednesday Ida (t · c) 12:39, 6 December 2016 (UTC)

Still seems wrong to me after a second reading. I'm removed that specific sentence until we can work it out here. I have not touched the remainder of your edit, which looks good to me. — Gamall Wednesday Ida (t · c) 20:28, 6 December 2016 (UTC)

Excuse me for butting in to your conversation here, but exactly the same issue had puzzled me. I suggest the following modification, and I would be interested to read what you all think about my suggestion, if anything:

EDIT:

Call a full subtree of height $h$ whose leaves are a subset of the leaves of the full binary tree of depth $l_{m}$, an $h$-triangle.

Identify a codeword of length $l$ with a node in the tree at depth $l$, as usual, and also with the $(l_{m}-l)$-triangle rooted at that node.

Initially, for each $h$ there are $2^{l_{m}-h}$ $h$-triangles.

When we choose a node at depth $l_{i}$ to represent a codeword of length $l_{i}$, then we delete exactly $1$ $(l_{m}-l_{i})$-triangle, and in general, for each $p$ with $l_{i}\leq p\leq l_{m}$, exactly $2^{p-l_{i}}$ of the $(l_{m}-p)$-triangles (namely, those that were contained in that big $(l_{m}-l_{i})$-triangle).

Therefore, when the time comes to choose a node at depth $l_{j}$ to represent the $j$th symbol, equivalently, to choose an $(l_{m}-l_{j})$-triangle, we have already deleted exactly $\sum _{i=1}^{j-1}2^{l_{j}-l_{i}}$ of the $2^{l_{m}-(l_{m}-l_{j})}=2^{l_{j}}$ original $(l_{m}-l_{j})$-triangles.

The algorithm is feasible if, and only if, for each $j$, this last sum is strictly less than $2^{l_{j}}$.

However, $\sum _{i=1}^{j-1}2^{l_{j}-l_{i}}<\sum _{i=1}^{j}2^{l_{j}-l_{i}}\leq \sum _{i=1}^{m}2^{l_{j}-l_{i}}=2^{l_{j}}\sum _{i=1}^{m}2^{-l_{i}}\leq 2^{l_{j}}$, by hypothesis, so everything is ok. Jumpers for goalposts, enduring image (talk) 11:32, 17 November 2022 (UTC)

Relations among prefix code, uniquely decodable code and Kraft's inequality

How about adding something as follows:

Let $K(x)$ denotes the lengths of a code $x$ satisfy Kraft's inequality; $P(x)$ denotes that code $x$ is prefix code; $U(x)$ denotes that code $x$ is uniquely decodable code. Then:

• $\forall x[P(x)\Rightarrow U(x)\Rightarrow K(x)]$
• $\forall x[K(x)\Rightarrow \exists xP(x)\Rightarrow \exists xU(x)]$

I was confused when I tried to figure out the relations among kraft's inequality, prefix code and uniquely decodable code. This is what I thought about the relations. But I'm not sure whether it's right.

--Li3939108 (talk) 18:20, 24 September 2012 (UTC)

This version seems more specific and informative and the one above seems redundant.

Let ${\mathcal {L}}x$ denotes the relation that a code $x$ has the lengths ${\mathcal {L}}$; $K({\mathcal {L}})$ denotes the lengths ${\mathcal {L}}$ of a given set of codewords satisfy Kraft's inequality ; $P(x)$ denotes that code $x$ is prefix code; $U(x)$ denotes that code $x$ is uniquely decodable code; Then:

• $\forall x\forall {\mathcal {L}}[P(x)\Rightarrow U(x)\Rightarrow {\mathcal {L}}x\&K({\mathcal {L}})]$
• $\forall x\forall {\mathcal {L}}[K({\mathcal {L}})\Rightarrow \exists xP(x)\&{\mathcal {L}}x\Rightarrow \exists xU(x)\&{\mathcal {L}}x]$

--Li3939108 (talk) 21:23, 24 September 2012 (UTC)