# Information Theory and Coding

 Question 1
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).
$\begin{array}{|c|c|c|c|c|c|c|c|c|} \hline Symbols & a & b & c & d & e & f & g & h \\ \hline Frequency& \frac{1}{2} & \frac{1}{4} & \frac{1}{8} & \frac{1}{16} & \frac{1}{32} & \frac{1}{64} & \frac{1}{128} & \frac{1}{128} \\ of \; occurrence& &&&&&&& \\ \hline \end{array}$
 A 0.25 B 1.98 C 2.48 D 3.36
GATE EC 2023   Communication Systems
Question 1 Explanation:
The average number of questions when asked in the most efficient sequence, to determine the chosen symbol $=\min$ possible number of questions per symbol $(H)$
$H=\sum_{i} P_{x}\left(x_{i}\right) \log _{2} \frac{1}{P_{x}\left(x_{i}\right)} =\frac{1}{2} \log _{2} 2+\frac{1}{4} \log _{2} 4+\frac{1}{8} \log _{2} 8+\frac{1}{16} \log _{2} 16+\frac{1}{32} \log _{2} 32+\frac{1}{64} \log _{2} 64+2 \times \frac{1}{128} \log _{2} 128 =1.984 \frac{\text { Questions }}{\text { Symbol }}$
 Question 2
Consider communication over a memoryless binary symmetric channel using a (7, 4) Hamming code. Each transmitted bit is received correctly with probability $(1-\epsilon )$, and flipped with probability $\epsilon$. For each codeword transmission, the receiver performs minimum Hamming distance decoding, and correctly decodes the message bits if and only if the channel introduces at most one bit error.
For $\epsilon =0.1$, the probability that a transmitted codeword is decoded correctly is _________ (rounded off to two decimal places).
 A 0.25 B 0.65 C 0.85 D 0.94
GATE EC 2022   Communication Systems
Question 2 Explanation:
Here (7, 4) Hamming code is given
P(0/1) = P(1/0) (due to bindary symmetry channel) = 0.1
When n bits are transmitted then probability of getting error in $\gamma$ bits $= ^nC_rP^r(1-p)^{n-r}$
P:Bit error probability
$P_c=C_0(0.1)^0[1-0.1]^{7-0}+^7C_1(0.1)(1-0.1)^{7-1}=(0.9)^7+7 \times 0.1 \times (0.9)^6=0.85$
$P_C$ : Prob of all most one bit error.

 Question 3
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 $\alpha$ lies in the interval [0.25, 1]. The value of $\alpha$ for which the capacity of this channel is maximized, is ________ (rounded off to two decimal places). A -1 B -2 C 2 D 1
GATE EC 2022   Communication Systems
Question 3 Explanation: Channel capacity,
$C_s=Max[I(X:Y)]$
$I[(X:Y)]=H(Y)-H\left ( \frac{Y}{X} \right )$
Where,
$H\left ( \frac{Y}{X} \right )=-\sum_{i=1}^{3}\sum_{i=1}^{3}P(x_i,y_i) \log_2P\left ( \frac{y_i}{x_i} \right )$
$P\left ( \frac{Y}{X} \right )=\begin{matrix} &y_1 & y_2 & y_3\\ x_1 &1-\alpha & \alpha & 0\\ x_2 &0 &1-\alpha &\alpha \\ x_3 & \alpha & 0 & 1-\alpha \end{matrix}$
For simplication convenience, let $[P(X)]=[1\;\;0\;\;0]$
\begin{aligned} [P(X,Y)]&=[P(X)]_d\cdot \left [ P\left ( \frac{Y}{X} \right ) \right ]\\ [P(X,Y)]&=\begin{bmatrix} 1-\alpha & \alpha &0 \\ 0& 0&0 \\ 0 & 0 &0 \end{bmatrix}\\ H\left ( \frac{Y}{X} \right )&=-((1-\alpha ) \log_2 (1-\alpha )+\alpha \log _2 \alpha )\\ I(X:Y)&=H(Y)+(1-\alpha ) \log_2 (1-\alpha )+ \log _2 \alpha \\ C_s&=MAX\left \{ (X:Y) \right \}\\ &=MAX\left \{ H(Y)+(1-\alpha ) \log_2 (1-\alpha )+ \log _2 \alpha \right \}\\ &=log_2 3+(1-\alpha ) \log_2 (1-\alpha )+\alpha \log _2 \alpha \end{aligned}
Plot of $(1-\alpha ) \log_2 (1-\alpha )+\alpha \log _2 \alpha$ $C_s$ will be maximum at $\alpha =0$ and 1.
Given $\alpha \in [0.25,1]$
Hence, $\alpha =1$ is correct answer.
 Question 4
A digital transmission system uses a (7,4) systematic linear Hamming code for transmitting data over a noisy channel. If three of the message-codeword pairs in this code $(\text{m}_{i} ; \text{c}_{i})$, where $\text{c}_{i}$ is the codeword corresponding to the $i^{th}$ message $\text{m}_{i}$ , are known to be (1100; 0101 100), ( 1110; 0011110) and (0110; 1000110), then which of the following is a $\text{valid codeword}$ in this code?
 A $1101001$ B $1011010$ C $0001011$ D $0110100$
GATE EC 2021   Communication Systems
Question 4 Explanation:
Given codewords:$\left.\begin{array}{l} C_{1}=0101100 \\ C_{2}=0011110 \\ C_{3}=1000110 \end{array}\right\}$
in given above codewords, first n - k = 3 bits are parity bits and last K = 4 bits are message bits.
Given is (7, 4) systematic linear hamming code. For a linear code, sum of two codewords belong to the code is also a codeword belonging to the code.
\begin{aligned} C_{1} \oplus C_{2}&=0110010=C_{4} \\ C_{2} \oplus C_{3}&=1011000=C_{5} \\ C_{1} \oplus C_{3}&=1101010=C_{6} \\ C_{3} \oplus C_{4}&=1110100=C_{7} \end{aligned}
Based on codewords $C_{6}$ and $C_{7}$ options (a) and (d) will incorrect.
Given codewords in the form of $\Rightarrow \underbrace{P_{1} \quad P_{2} \quad P_{3}}_{\text {Parity bits }} \;\underbrace{d_{1}\quad d_{2} \quad d_{3} \quad d_{4} }_{\text {Message bits }}$
\begin{aligned} \text { From observation } \Rightarrow & P_{1}=d_{1} \oplus d_{2} \oplus d_{4} \\ & P_{2}=d_{2} \oplus d_{3} \oplus d_{4} \\ & P_{3}=d_{1} \oplus d_{2} \oplus d_{3} \end{aligned}
From given options, option (C) only satisfying above relations.
So, that option (C) will be correct.
 Question 5
A speech signal, band limited to $4\:\text{kHz}$, is sampled at 1.25 times the Nyquist rate. The speech samples, assumed to be statistically independent and uniformly distributed in the range $-5\:V$ to $+5\:V$, are subsequently quantized in an 8-bit uniform quantizer and then transmitted over a voice-grade $\text{AWGN}$ telephone channel. If the ratio of transmitted signal power to channel noise power is $26\:\text{dB}$, the minimum channel bandwidth required to ensure reliable transmission of the signal with arbitrarily small probability of transmission error (rounded off to two decimal places) is _____ $\text{kHz}$.
 A 9.25 B 3.65 C 8.65 D 4.56
GATE EC 2021   Communication Systems
Question 5 Explanation:
\begin{aligned} f_{m}&=4 \mathrm{kHz} \\ f_{s}&=1.25 \mathrm{NR}=1.25 \times\left(2 f_{m}\right)=10 \mathrm{kHz} \end{aligned} $n=8$ bits/sample and $\frac{S}{N}=26 \mathrm{~dB}=10^{2.6}$
For arbitrarily small probability of transmission error,
\begin{aligned} C & \geq R_{b} \Rightarrow B \log _{2}\left(1+\frac{S}{N}\right) \geq n f_{S} \\ \text{Blog}_{2}\left(1+10^{2.6}\right) & \geq 8 \times 10 \mathrm{~K} \Rightarrow B \geq 9.25 \mathrm{kHz} \\ B_{\min } &=9.25 \mathrm{kHz} \end{aligned}

There are 5 questions to complete.