The binary Kraft inequality states that codeword lengths

l (a)

of a prefix code, or more generally a uniquely decodable code, satisfy

\sum_{a} 2^{- l (a)} \leq 1.

Conversely, positive integer lengths obeying this inequality can be realized by a binary prefix code.

b

Solution

The Shannon lengths are

l_{S} (a) = ⌈ lo g_{2} (1/ P (a))⌉

. Their Competitive optimality of the Shannon code says that for every binary uniquely decodable code of lengths

l_{C}

k

P {l_{S} (X) \geq l_{C} (X) + k} \leq 2^{- k + 1} .

On this event,

P (X) < 2^{- l_{C} (X) - k + 1}

. Summing and applying the Kraft inequality proves

P {l_{S} (X) \geq l_{C} (X) + k} \leq 2^{- k + 1} \sum_{a} 2^{- l_{C} (a)} \leq 2^{- k + 1} .

Relabel the symbols so

p_{1} \geq \dots \geq p_{m}

and assign all finite binary strings in nondecreasing length order, beginning with the empty string. The

i

th string has length

L (i) = ⌊ lo g_{2} i ⌋ .

Since

1 \geq \sum_{j = 1}^{i} p_{j} \geq i p_{i}

L (i) \leq lo g_{2} i \leq lo g_{2} (1/ p_{i}) .

E [L (X)] \leq i \sum p_{i} lo g_{2} (1/ p_{i}) = H (X) .

For the uniform distribution, the code in part c has

E [L (X)] = \frac{1}{m} \sum_{i = 1}^{m} ⌊ lo g_{2} i ⌋ < lo g_{2} m = H (X),

because every summand is at most

lo g_{2} m

and at least one is strictly smaller. For

m = 3

, the explicit code

C (1) = λ

C (2) = 0

C (3) = 1

2/3 < lo g_{2} 3

There are no discussions about this article yet.

There are currently no matching articles.