GATE 2024 EC Q.34: solution and answer

GATE 2024 · ECQ.34 · 1 mark · NAT

A source transmits symbols from an alphabet of size 16. The value of maximum achievable entropy (in bits) is ________ .

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The maximum achievable entropy is $4$ bits per symbol.

Official answer: 4Source: Official answer key, GATE 2024 EC (IISc Bengaluru)

A source with $M$ symbols has entropy $H = - \sum_{i = 1}^{M} p_{i} lo g_{2} p_{i}$ , in bits per symbol.
$H$ is largest when all symbols are equally likely, $p_{i} = 1/ M$ . This follows from Jensen's inequality, because $lo g_{2}$ is concave: $H = \sum_{i} p_{i} lo g_{2} \frac{1}{p _{i}} \leq lo g_{2} (\sum_{i} p_{i} \cdot \frac{1}{p _{i}}) = lo g_{2} M$ . Equality holds when every $p_{i}$ is equal.
At that point $H_{m a x} = - \sum_{i = 1}^{M} \frac{1}{M} lo g_{2} \frac{1}{M} = lo g_{2} M$ .
For $M = 16$ : $H_{m a x} = lo g_{2} 16 = lo g_{2} 2^{4} = 4$ bits per symbol.

KEY IDEA

Entropy is maximised by a uniform distribution over the alphabet, so $H_{m a x} = lo g_{2} M$ bits per symbol.

WATCH OUT FOR

Using the natural log, which gives $ln 16 \approx 2.77$ nats rather than bits. Another slip is taking the answer as 16, the alphabet size, or as 15 (M-1).

From the GATE 2024 EC paper. Every question of this paper · Download the full paper · All 9 Information theory questions, with notes

GATE 2024 EC Q.34: solution and answer

Answer and solution

More Information theory questions