IN THE EC SYLLABUS

Information theory

Entropy, source coding and channel capacity

Information theory measures how much uncertainty a source carries (entropy), how compactly it can be written down (source coding) and how fast data can be sent reliably over a noisy channel (channel capacity). The core results are entropy, the Kraft inequality, Huffman coding, mutual information, the capacities of the binary symmetric and binary erasure channels, and the Shannon-Hartley law.

9 previous-year questions · 9 solved · 5 practice questions

Information and entropy

Convention: all logarithms are to base 2 unless stated, so information is measured in bits. A discrete memoryless source (DMS) emits symbols $x_{i}$ with probabilities $p_{i}$ , independently of one another. A rarer symbol carries more information when it occurs.

INFORMATION OF A SYMBOL

I (x_{i}) = lo g_{2} \frac{1}{p _{i}} = - lo g_{2} p_{i} bits

Always non-negative; a certain event ( $p_{i} = 1$ ) carries 0 bits.

ENTROPY OF A DMS

H (X) = - i = 1 \sum M p_{i} lo g_{2} p_{i} bits/symbol

Average information per symbol. Take $0 lo g 0 = 0$ .

BOUNDS ON ENTROPY

0 \leq H (X) \leq lo g_{2} M

Minimum 0 when one symbol has probability 1; maximum $lo g_{2} M$ when all $M$ symbols are equiprobable.

BINARY ENTROPY FUNCTION

H_{b} (p) = - p lo g_{2} p - (1 - p) lo g_{2} (1 - p)

Entropy of a two-symbol source. $H_{b} (0.5) = 1$ , symmetric about $p = 0.5$ , $H_{b} (0) = H_{b} (1) = 0$ .

EXTENDED SOURCE

H (X^{n}) = n H (X)

For the $n$ th extension of a DMS (blocks of $n$ independent symbols, $M^{n}$ block symbols).

EXAM TIP

If the source emits $r$ symbols per second, the information rate is $R = r H$ bits/s. Check whether a question asks for bits per symbol or bits per second.

Joint and conditional entropy, mutual information

For a channel with input $X$ and output $Y$ , the conditional entropy $H (X ∣ Y)$ is the uncertainty about the input that remains after the output is seen. Mutual information is the uncertainty removed by observing $Y$ .

JOINT AND CONDITIONAL ENTROPY

H (X, Y) = H (X) + H (Y ∣ X) = H (Y) + H (X ∣ Y)

Chain rule. If $X$ and $Y$ are independent, $H (X, Y) = H (X) + H (Y)$ . The conditional entropy is an average: $H (Y ∣ X) = \sum_{x} p (x) H (Y ∣ X = x)$ .

MUTUAL INFORMATION

I (X; Y) = H (X) - H (X ∣ Y) = H (Y) - H (Y ∣ X) = H (X) + H (Y) - H (X, Y)

Symmetric in $X$ and $Y$ ; $I (X; Y) \geq 0$ , with equality exactly when $X$ and $Y$ are independent.

MUTUAL INFORMATION FROM PROBABILITIES

I (X; Y) = x \sum y \sum p (x, y) lo g_{2} \frac{p ( x , y )}{p ( x ) p ( y )}

Here $p (x, y) = p (x) P (y ∣ x)$ and $p (y) = \sum_{x} p (x) P (y ∣ x)$ . Terms with $p (x, y) = 0$ contribute 0.

CONDITIONING REDUCES ENTROPY

H (X ∣ Y) \leq H (X)

Equality only for independent $X$ and $Y$ . Also $I (X; X) = H (X)$ .

EXAM TIP

For a lossless channel, where the input can always be recovered from the output, $H (X ∣ Y) = 0$ so $I (X; Y) = H (X)$ . For a channel whose output is independent of the input, $I (X; Y) = 0$ .

Source coding

A source code maps each symbol to a binary codeword of length $l_{i}$ . A prefix code has no codeword that is the start of another, so it is instantaneously decodable.

AVERAGE CODE LENGTH

\overline{L} = i \sum p_{i} l_{i} bits/symbol

Binary code alphabet.

KRAFT INEQUALITY

i = 1 \sum M 2^{- l_{i}} \leq 1

A binary prefix code with lengths $l_{i}$ exists if and only if this holds. Every uniquely decodable binary code also satisfies it, so nothing is gained in length by giving up the prefix property. It tests lengths only; a set of codewords can obey it and still not be prefix-free.

SOURCE CODING THEOREM

H (X) \leq \overline{L} < H (X) + 1

The lower bound holds for every uniquely decodable binary code; an optimal binary prefix code (e.g. Huffman) also meets the upper bound. Using the $n$ th extension, $H (X) \leq \overline{L}_{n} / n < H (X) + 1/ n$ .

EFFICIENCY AND REDUNDANCY

η = \frac{H ( X )}{L}, redundancy = 1 - η

Binary code. For a code alphabet of $r$ symbols, $η = \frac{H ( X )}{L lo g _{2} r}$ . A binary code with $\overline{L} = H$ has $η = 1$ ; this needs every $p_{i}$ to be a power of $\frac{1}{2}$ .

Huffman coding procedure

Arrange the symbols in decreasing order of probability.
Combine the two smallest probabilities into one node and re-sort the list.
Repeat until one node of probability 1 remains.
Starting from the root, assign 0 and 1 to the two branches at each merge; read each symbol's codeword back from the root.
Check: $\overline{L}$ equals the sum of the probabilities of all merged (internal) nodes.

Shannon-Fano procedure

Arrange the symbols in decreasing order of probability.
Split the list into two groups whose total probabilities are as nearly equal as possible.
Assign 0 to the upper group and 1 to the lower group.
Repeat inside each group until every group has one symbol.

EXAM TIP

Ties in Huffman coding can give different sets of lengths, but the average length $\overline{L}$ is always the same. Huffman is optimal among prefix codes; Shannon-Fano is not always.

Discrete memoryless channels: BSC and BEC

A discrete memoryless channel is described by transition probabilities $P (y ∣ x)$ . The capacity per channel use is the largest mutual information over all input distributions.

CHANNEL CAPACITY

C = P (x) max I (X; Y) bits per channel use

For a channel used $r$ times per second, the capacity is $r C$ bits/s.

BINARY SYMMETRIC CHANNEL (CROSSOVER PROBABILITY P)

C_{BSC} = 1 - H_{b} (p)

Reached with equiprobable inputs. $C = 1$ at $p = 0$ or $p = 1$ , and $C = 0$ at $p = \frac{1}{2}$ .

BSC WITH INPUT P(X=1) = Α

I (X; Y) = H_{b} (α (1 - p) + (1 - α) p) - H_{b} (p)

From $I = H (Y) - H (Y ∣ X)$ : $H (Y ∣ X) = H_{b} (p)$ for every input, and $P (Y = 1) = α (1 - p) + (1 - α) p$ . The maximum, at $α = \frac{1}{2}$ , is $1 - H_{b} (p)$ .

BINARY ERASURE CHANNEL (ERASURE PROBABILITY Ε)

C_{BEC} = 1 - ε

Each bit is either received correctly or marked as erased; reached with equiprobable inputs.

BEC WITH INPUT P(X=1) = Α

I (X; Y) = (1 - ε) H_{b} (α)

From $I = H (X) - H (X ∣ Y)$ : the input is known unless the bit is erased, so $H (X ∣ Y) = ε H_{b} (α)$ . The maximum, at $α = \frac{1}{2}$ , is $1 - ε$ .

Channel	Behaviour	Capacity (bits/use)
Noiseless binary	Output equals input	1
BSC, crossover $p$	Bit flipped with probability $p$	$1 - H_{b} (p)$
BEC, erasure $ε$	Bit lost with probability $ε$	$1 - ε$
BSC with $p = \frac{1}{2}$	Output independent of input	0

EXAM TIP

A BSC with $p = 0.9$ is as good as one with $p = 0.1$ , because the receiver can simply invert every bit: $H_{b} (p) = H_{b} (1 - p)$ .

Channel capacity theorem and the Shannon-Hartley law

The channel coding theorem: if the information rate $R$ is less than the capacity $C$ , there exists a coding scheme with arbitrarily small error probability; if $R > C$ , reliable communication is impossible. It does not say how to build the code.

DIFFERENTIAL ENTROPY (CONTINUOUS SOURCE)

h (X) = - \int_{- \infty}^{\infty} f (x) lo g_{2} f (x) d x

Unlike discrete entropy, it can be negative. Uniform on an interval of length $a$ : $h = lo g_{2} a$ . Gaussian with variance $σ^{2}$ : $h = \frac{1}{2} lo g_{2} (2 π e σ^{2})$ , the largest value for any density with that variance.

SHANNON-HARTLEY LAW

C = B lo g_{2} (1 + \frac{S}{N}) bits/s

Band-limited AWGN channel of bandwidth $B$ Hz. $S$ is the average received signal power and $S / N$ is the power ratio (not dB); $N = N_{0} B$ with two-sided noise PSD $N_{0} /2$ .

SNR IN DECIBELS

(\frac{S}{N})_{dB} = 10 lo g_{10} \frac{S}{N}

Convert to a ratio before using in the law: 20 dB means 100, 30 dB means 1000.

INFINITE-BANDWIDTH LIMIT

C_{\infty} = B \to \infty lim C = \frac{S}{N _{0}} lo g_{2} e \approx 1.44 \frac{S}{N _{0}}

At fixed signal power $S$ , capacity grows with $B$ but saturates, because the noise power $N_{0} B$ grows too.

SHANNON LIMIT (CONDITION FOR RELIABLE COMMUNICATION)

\frac{E _{b}}{N _{0}} \geq ln 2 \approx 0.693 (- 1.59 dB)

$E_{b}$ is the energy per bit. With $R = C$ and $S = E_{b} C$ : $\frac{E _{b}}{N _{0}} = \frac{2 ^{C / B} - 1}{C / B}$ , which tends to $ln 2$ as $C / B \to 0$ . Below this, no reliable communication is possible at any positive rate.

BANDWIDTH-SNR TRADE-OFF

\frac{S}{N} = 2^{C / B} - 1

For a target rate $C$ , a smaller bandwidth needs an exponentially larger SNR; a larger bandwidth allows a lower SNR.

WORKED EXAMPLE

A DMS emits five symbols with probabilities 0.4, 0.2, 0.2, 0.1, 0.1. Find its entropy, the average length of a binary Huffman code, and the code efficiency.

Solution

Entropy: $H = 0.4 lo g_{2} \frac{1}{0.4} + 2 (0.2) lo g_{2} \frac{1}{0.2} + 2 (0.1) lo g_{2} \frac{1}{0.1} = 0.5288 + 0.9288 + 0.6644 = 2.1219$ bits/symbol.
Huffman merges: $0.1 + 0.1 = 0.2$ ; then $0.2 + 0.2 = 0.4$ ; then $0.2 + 0.4 = 0.6$ ; then $0.6 + 0.4 = 1.0$ .
$\overline{L}$ = sum of merged node probabilities $= 0.2 + 0.4 + 0.6 + 1.0 = 2.2$ bits/symbol.
Check against the theorem: $2.1219 \leq 2.2 < 3.1219$ .
Efficiency $η = 2.1219/2.2 = 0.9645$ .

Answer: $H \approx 2.12$ bits/symbol, $\overline{L} = 2.2$ bits/symbol, $η \approx 96.5%$ .

WORKED EXAMPLE

A channel of bandwidth 4 kHz has a signal-to-noise power ratio of 31. Find its capacity, and the SNR (as a ratio) needed to carry 32 kbit/s in the same bandwidth.

Solution

$C = 4000 lo g_{2} (1 + 31) = 4000 lo g_{2} 32 = 4000 \times 5 = 20, 000$ bits/s.
For 32 kbit/s: $C / B = 32000/4000 = 8$ .
$S / N = 2^{8} - 1 = 255$ (about 24.1 dB).

Answer: $C = 20$ kbit/s; the SNR must rise to 255.

PREVIOUS-YEAR QUESTIONS

9 questions from the EC papers

Try each question first, then open the answer. We placed each question under a topic ourselves; the exam paper does not label topics.

See these papers in full: GATE ECE 2026 · GATE ECE 2025 · GATE ECE 2024 · GATE ECE 2023 · GATE ECE 2022 · GATE ECE 2020

GATE 2026 EC Q.55

GATE 2026 · ECQ.55 · 2 marks · MSQ

Let the relevant bandwidth ( $B$ ) of a digital communication system be 1 MHz and $k T = - 174$ dBm/Hz, where $k$ is Boltzmann's constant and 'T' is equivalent noise temperature of the receiver. The power ( $S$ ) of signal received through an additive Gaussian channel is $- 80$ dBm. Which of the following options is/are TRUE about Shannon capacity ( $C$ ) of the channel?

(A)
$C = B$
(B)
$C = 2 B$
(C)
$C > 3 B$
(D)
$C < B$

Answer and solution

GATE 2026 EC Q.55: answer and solution

See the question in the paper

Tap to open full size

GATE 2026 EC Q.55: answer and solution

GATE 2025 EC Q.15

GATE 2025 · ECQ.15 · 1 mark · MCQ

Consider an additive white Gaussian noise (AWGN) channel with bandwidth $W$ and noise power spectral density $\frac{N _{0}}{2}$ . Let $P_{a v}$ denote the average transmit power constraint.

Which one of the following plots illustrates the dependence of the channel capacity $C$ on the bandwidth $W$ (keeping $P_{a v}$ and $N_{0}$ fixed)?

GATE 2025 EC question 15: Four small plots, each with the vertical axis labelled C and the horizontal axis labelled W, both starting at the origin 0. — Figure from the GATE 2025 EC paper. It is part of the question.

(A)
Figure — C versus W: concave curve rising steeply from the origin and saturating at a horizontal asymptote.
(B)
Figure — C versus W: straight line through the origin with constant positive slope.
(C)
Figure — C versus W: convex curve starting with a small slope and rising increasingly steeply.
(D)
Figure — C versus W: curve rising from the origin to a peak and then decreasing.

Answer and solution

GATE 2025 EC Q.15: answer and solution

GATE 2025 EC Q.54

GATE 2025 · ECQ.54 · 2 marks · MSQ

The random variable $X$ takes values in ${- 1, 0, 1}$ with probabilities $P (X = - 1) = P (X = 1) = α$ and $P (X = 0) = 1 - 2 α$ , where $0 < α < 1/2$ . Let $g (α)$ denote the entropy of $X$ (in bits), parameterized by $α$ . Which of the following statements is/are TRUE?

(A)
$g (0.4) > g (0.3)$
(B)
$g (0.3) > g (0.4)$
(C)
$g (0.3) > g (0.25)$
(D)
$g (0.25) > g (0.3)$

Answer and solution

GATE 2025 EC Q.54: answer and solution

See the question in the paper

Tap to open full size

GATE 2025 EC Q.54: answer and solution

GATE 2025 EC Q.60

GATE 2025 · ECQ.60 · 2 marks · NAT

$X$ and $Y$ are Bernoulli random variables taking values in ${0, 1}$ . The joint probability mass function of the random variables is given by: $P (X = 0, Y = 0) = 0.06$ , $P (X = 0, Y = 1) = 0.14$ , $P (X = 1, Y = 0) = 0.24$ , $P (X = 1, Y = 1) = 0.56$ . The mutual information $I (X; Y)$ is ________ (rounded off to two decimal places).

Answer and solution

GATE 2025 EC Q.60: answer and solution

See the question in the paper

Tap to open full size

GATE 2025 EC Q.60: answer and solution

GATE 2024 EC Q.34

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 ________ .

Answer and solution

GATE 2024 EC Q.34: answer and solution

See the question in the paper

Tap to open full size

GATE 2024 EC Q.34: answer and solution

GATE 2023 EC Q.65

GATE 2023 · ECQ.65 · 2 marks · NAT

The frequency of occurrence of 8 symbols (a-h) is shown in the table below. A symbol is chosen and it is determined by asking a series of "yes/no" questions which are assumed to be truthfully answered. The average number of questions when asked in the most efficient sequence, to determine the chosen symbol, is ________ (rounded off to two decimal places).

GATE 2023 EC question 65: A table with two rows. — Figure from the GATE 2023 EC paper. It is part of the question.

Answer and solution

GATE 2023 EC Q.65: answer and solution

GATE 2022 EC Q.29

GATE 2022 · ECQ.29 · 1 mark · MSQ

Let $H (X)$ denote the entropy of a discrete random variable $X$ taking $K$ possible distinct real values. Which of the following statements is/are necessarily true?

(A)
$H (X) \leq lo g_{2} K$ bits
(B)
$H (X) \leq H (2 X)$
(C)
$H (X) \leq H (X^{2})$
(D)
$H (X) \leq H (2^{X})$

Answer and solution

GATE 2022 EC Q.29: answer and solution

See the question in the paper

Tap to open full size

GATE 2022 EC Q.29: answer and solution

GATE 2022 EC Q.61

GATE 2022 · ECQ.61 · 2 marks · NAT

The transition diagram of a discrete memoryless channel with three input symbols and three output symbols is shown in the figure. The transition probabilities are as marked. The parameter $α$ lies in the interval $[0.25, 1]$ . The value of $α$ for which the capacity of this channel is maximized, is ________ (rounded off to two decimal places).

GATE 2022 EC question 61: Bipartite transition diagram with inputs a, b, c on the left and outputs a, b, c on the right. — Figure from the GATE 2022 EC paper. It is part of the question.

Answer and solution

GATE 2022 EC Q.61: answer and solution

GATE 2020 EC Q.22

GATE 2020 · ECQ.22 · 1 mark · NAT

A binary random variable $X$ takes the value $+ 2$ or $- 2$ . The probability $P (X = + 2) = α$ . The value of $α$ (rounded off to one decimal place), for which the entropy of $X$ is maximum, is ______.

Answer and solution

GATE 2020 EC Q.22: answer and solution

See the question in the paper

Tap to open full size

GATE 2020 EC Q.22: answer and solution

PRACTICE

5 questions to test yourself

PRACTICE 11 mark · MCQ

Which one of the following sets of codeword lengths can be the lengths of a binary prefix code?

(A)
{1, 1, 2}
(B)
{2, 2, 2, 3, 3}
(C)
{1, 2, 2, 3}
(D)
{1, 2, 3, 3, 3}

Answer and solution

Answer: (B)

Apply Kraft: $\sum 2^{- l_{i}} \leq 1$ is required.
A: $0.5 + 0.5 + 0.25 = 1.25 > 1$ . C: $0.5 + 0.25 + 0.25 + 0.125 = 1.125 > 1$ . D: $0.5 + 0.25 + 3 (0.125) = 1.125 > 1$ .
B: $3 (0.25) + 2 (0.125) = 1.0 \leq 1$ , so a prefix code exists.

PRACTICE 22 marks · NAT

A binary symmetric channel has crossover probability $p = 0.1$ and is used 2000 times per second. Assuming the best input distribution, its capacity in bits per second is ______ (nearest integer).

Answer and solution

Answer: $1062$ (accepted range $\pm 5$ )

$H_{b} (0.1) = 0.1 lo g_{2} 10 + 0.9 lo g_{2} \frac{1}{0.9} = 0.3322 + 0.1368 = 0.4690$ .
$C = 1 - 0.4690 = 0.5310$ bits per use.
Rate $= 2000 \times 0.5310 \approx 1062$ bits/s.

PRACTICE 32 marks · MSQ

Which of the following statements are correct?

(A)
A source with $M$ symbols has maximum entropy $lo g_{2} M$ when all symbols are equiprobable.
(B)
The mutual information $I (X; Y)$ between the input and output of a channel is never negative.
(C)
The capacity of a binary symmetric channel with crossover probability 0.5 is 1 bit per use.
(D)
At fixed signal power and noise PSD, the Shannon-Hartley capacity grows without bound as the bandwidth tends to infinity.

Answer and solution

Answer: (A), (B)

A is true: entropy is maximised by the uniform distribution.
B is true: $I (X; Y) \geq 0$ , zero only for independent $X$ and $Y$ .
C is false: at $p = 0.5$ , $H_{b} = 1$ so $C = 0$ .
D is false: capacity saturates at $\frac{S}{N _{0}} lo g_{2} e \approx 1.44 S / N_{0}$ .

PRACTICE 41 mark · NAT

A discrete memoryless source emits four symbols with probabilities $\frac{1}{2}, \frac{1}{4}, \frac{1}{8}, \frac{1}{8}$ . Its entropy, in bits per symbol, is ______ (up to two decimal places).

Answer and solution

Answer: $1.75$ (accepted range $\pm 0.01$ )

$H = \frac{1}{2} (1) + \frac{1}{4} (2) + \frac{1}{8} (3) + \frac{1}{8} (3)$ .
$= 0.5 + 0.5 + 0.375 + 0.375 = 1.75$ bits/symbol.

PRACTICE 52 marks · NAT

A telephone-type channel has bandwidth 3 kHz and a signal-to-noise ratio of 20 dB. Its Shannon-Hartley capacity in bits per second is ______ (nearest integer).

Answer and solution

Answer: $19975$ (accepted range $\pm 30$ )

20 dB corresponds to $S / N = 1 0^{2} = 100$ .
$C = 3000 lo g_{2} (1 + 100) = 3000 lo g_{2} 101$ .
$lo g_{2} 101 = 6.6582$ , so $C \approx 3000 \times 6.6582 \approx 19, 975$ bits/s.

OFFICIAL GATE 2027 SYLLABUS WORDING

Copied from the GATE 2027 syllabus; see all 2027 syllabi.

GATE EC

Information Theory: Entropy, source coding, mutual information and channel capacity theorem

Preparing in Kolkata? IAE Academy's course for GATE ECE.