The Shannon-Fano lengths are

(ℓ_{1}, ℓ_{2}, ℓ_{3}, ℓ_{4}) = (4, 3, 2, 2) .

One corresponding prefix-free assignment is

1 \mapsto 1010, 2 \mapsto 100, 3 \mapsto 00, 4 \mapsto 01 .

Its expected word length is

\overline{ℓ}_{SF} = \frac{1}{10} 4 + \frac{2}{10} 3 + \frac{3}{10} 2 + \frac{4}{10} 2 = 2.4 .

ii

Solution

The Huffman coding merges are

\frac{1}{10} + \frac{2}{10} = \frac{3}{10}, \frac{3}{10} + \frac{3}{10} = \frac{6}{10}, \frac{4}{10} + \frac{6}{10} = 1.

For example, the resulting code may be

1 \mapsto 110, 2 \mapsto 111, 3 \mapsto 10, 4 \mapsto 0 .

Its expected length is

\overline{ℓ}_{H} = \frac{1}{10} 3 + \frac{2}{10} 3 + \frac{3}{10} 2 + \frac{4}{10} 1 = 1.9 .

The binary entropy is

H = \sum_{k = 1}^{4} p_{k} lo g_{2} \frac{1}{p _{k}} \approx 0.1 (3.32) + 0.2 (2.32) + 0.3 (1.74) + 0.4 (1.32) = 1.846.

H \leq \overline{ℓ} < H + 1

for the standard Shannon construction, while every prefix code obeys the lower bound. Numerically,

1.846 \leq 2.4 < 2.846, 1.846 \leq 1.9 < 2.846.

Thus both codes satisfy the theorem, with the Huffman code closer to the entropy lower bound.

There are no discussions about this article yet.

There are currently no matching articles.