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}
(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}
0.25 | |
1.98 | |
2.48 | |
3.36 |
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 }}
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).
For \epsilon =0.1 , the probability that a transmitted codeword is decoded correctly is _________ (rounded off to two decimal places).
0.25 | |
0.65 | |
0.85 | |
0.94 |
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.
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).
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).
-1 | |
-2 | |
2 | |
1 |
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?
1101001 | |
1011010 | |
0001011 | |
0110100 |
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.
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}.
9.25 | |
3.65 | |
8.65 | |
4.56 |
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}
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.