Past exam of the communication Theory course of the University of Oxford / 2011 / 2 / c

Table of contents
- Solution c

Solution

Let

F_{k} = \sum_{r < k} p_{r}

and let

J_{k} = [F_{k}, F_{k} + p_{k})

be the probability cell of symbol

k

. Its midpoint is

G_{k} = F_{k} + p_{k} /2

. Use the binary expansion terminating in zeros at a dyadic rational, so truncation to

l_{k}

bits gives

a_{k} = 2^{- l_{k}} ⌊ 2^{l_{k}} G_{k} ⌋ .

The chosen codeword corresponds to the dyadic interval

D_{k} = [a_{k}, a_{k} + 2^{- l_{k}})

. It contains

G_{k}

, and its width satisfies

2^{- l_{k}} \leq p_{k} /2

. Consequently

a_{k} > G_{k} - 2^{- l_{k}} \geq F_{k}, a_{k} + 2^{- l_{k}} \leq G_{k} + 2^{- l_{k}} \leq F_{k} + p_{k} .

Thus

D_{k} \subseteq J_{k}

. The probability cells are disjoint, so the code intervals are disjoint. If one binary codeword were a prefix of another, its dyadic interval would contain the other's interval, contradicting this disjointness. Hence the code is instantaneous.

Finally,

l_{k} = ⌈ - lo g_{2} p_{k} ⌉ + 1 < - lo g_{2} p_{k} + 2

. Multiplying by

p_{k}

and summing yields

E L < H (X) + 2.

This is the Shannon-Fano-Elias code: the extra bit makes the dyadic interval narrow enough to remain inside the cell around its midpoint.

Figure 1.
Midpoint coding places disjoint dyadic intervals inside probability cells
. An original example with probabilities two fifths, three tenths, one fifth, and one tenth. Each orange dyadic code interval contains its black midpoint and lies inside its blue probability cell, proving that the displayed codewords cannot be prefixes of one another. Details.

 Ancestors (11)

 View article source

 Discussion (0) New discussion

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version