# Kraft's inequality and Shannon's noiseless coding theorem for an encoding

A discrete memoryless source W has words $w_1,w_2,w_3,w_4,w_5,w_6$ that occur with probablilities $0.05,0.05,0.15,0.2,0.25,0.3$ respectivley.

Does there exist a compact instantaneous binary encoding for this source with word lengths $2, 2, 4, 4, 5$ and $5$?

Shannon's Noiseless coding theroem that says a compact encoding has expected wordlength $n$ where $n\leq \frac{H(W)}{\log_2(D)}$. I get $H(W)=2.328$ and $n=1.901$, but in this case the expected word length is $3.67$ so it cannont be a compact encoding.

I feel like I have gone wrong here, could somebody tell me how? Because I have gone on to the next question where I perform Huffman coding to achieve a compact instantaneous encoding however the word length for this encoding is still higher than $1.901$ so fee like I must have my value for $n$ wrong but can't see how?

## 1 Answer

I don't know what a "compact instantaneous binary encoding" is, but I'm guessing it's a prefix code that saturates Kraft's inequality. If so, your numbers don't correspond to a compact prefix code, since $1/4+1/4+1/16+1/16+1/32+1/32 < 1$.

Shannon's noiseless coding theorem states that when optimally encoding large blocks, in the limit the average encoding size per data item is the entropy. You can prove the upper bound part of the theorem using Huffman coding applied to large blocks. Huffman coding produces a code whose average bit length is at most $H(X)+1$, where $X$ is the source. If you use Huffman coding on blocks of size $n$, the average bit length per data item becomes $H(X)+1/n$ (why?), and by letting $n\to\infty$, you can get as close to the entropy as you want.