Information Theory And Coding Practice Questions

The mutual information is given by: $I(X;Y) = \sum_{x,y} P(x,y) \log_2 \left( \frac{P(x,y)}{P(x)P(y)} \right)$ Step 1: Compute marginals

Step 2: Compute mutual information We compute $P(x,y) \log_2 \left( \frac{P(x,y)}{P(x)P(y)} \right)$ for each combination: (i) $x=0,\ y=0$ : $P = 0.06,\quad P(X=0) = 0.20,\quad P(Y=0) = 0.30 \ \Rightarrow \frac{0.06}{0.20 \cdot 0.30} = 1.0,\quad \log_2(1) = 0 \ \Rightarrow \text{term} = 0.06 \cdot 0 = 0$ (ii) $x=0,\ y=1$ : $P = 0.14,\quad P(X=0) = 0.20,\quad P(Y=1) = 0.70 \ \Rightarrow \frac{0.14}{0.20 \cdot 0.70} = 1.0,\quad \log_2(1) = 0 \ \Rightarrow \text{term} = 0.14 \cdot 0 = 0$ (iii) $x=1,\ y=0$ : $P = 0.24,\quad P(X=1) = 0.80,\quad P(Y=0) = 0.30 \ \Rightarrow \frac{0.24}{0.80 \cdot 0.30} = 1.0,\quad \log_2(1) = 0 \ \Rightarrow \text{term} = 0.24 \cdot 0 = 0$ (iv) $x=1,\ y=1$ : $P = 0.56,\quad P(X=1) = 0.80,\quad P(Y=1) = 0.70 \ \Rightarrow \frac{0.56}{0.80 \cdot 0.70} = 1.0,\quad \log_2(1) = 0 \ \Rightarrow \text{term} = 0.56 \cdot 0 = 0$ So: $I(X;Y) = 0 + 0 + 0 + 0 = 0$

X is having outcomes of random experiment. Hence entropy $\mathrm{H}(\mathrm{x})$ will be maximum when are the events occur with equal probability. $\mathrm{H}(\mathrm{x})$ is Max at $\mathrm{P}[\mathrm{X}=-1]=\mathrm{P}[\mathrm{X}=0]=\mathrm{P}[\mathrm{X}=1]$ $=\frac{1}{3}=0.33$ $\mathrm{g}(0.4) > \mathrm{g}(0.3) \rightarrow$ wrong $\mathrm{g}(0.3) > \mathrm{g}(0.4) \rightarrow$ correct $\mathrm{g}(0.3) > \mathrm{g}(0.25) \rightarrow$ correct $\mathrm{g}(0.25) > \mathrm{g}(0.3) \rightarrow$ wrong

transmission of $-4 \rightarrow r=-4+\omega$ $f(r /-4)=\frac{1}{\sqrt{2 \pi}} e^{\frac{-(r+4)^{2}}{2 \times 4}}$ transmission of $0 \rightarrow r=\omega$ $f(r / 0)=\frac{1}{\sqrt{2 \pi}} e^{-\frac{r^{2}}{2 \times 4}}$ transmission of $4 \rightarrow r=4+n$ $f(r / 4)=\frac{1}{\sqrt{2 \pi}} e^{\frac{-(r-4)^{2}}{2 \times 4}}$ $P_{e}=P(-4) P_{e-4}+P(0) P_{e 0}+P(4) P_{e 4}$ Given

where, $r=N(4,4)$

$H_{\text {max }}=\log _{2} 16=4$

Let $P(X \geq Y)=P(X-Y \geq 0)$ $Z=X+(-Y)$

$P(Z \geq 0)=\frac{1}{2}$

Given information bit sequence $\rightarrow d=111010101$ Generator polymial $\rightarrow C(x)=x^{4}+x+1$ $C=10011$ Generator polynomial having 5 bits, so append $5-1=4$ bits to information sequence. $d=111010101010000$ Encoded sequence $=1110101011100$

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 }}$

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.

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 )$

For simplication convenience, let $[P(X)]=[1\;\;0\;\;0]$

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.

$n=8$ bits/sample and $\frac{S}{N}=26 \mathrm{~dB}=10^{2.6}$ For arbitrarily small probability of transmission error,

Given codewords:

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.

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 }}$

From given options, option (C) only satisfying above relations. So, that option (C) will be correct.

Probability of error in decoding single bit= $\alpha$ Then probability of no error will be $1- \alpha$ . Total N-bits transmitted, so that probability of no error in received block = $(1-\alpha )(1-\alpha )...N \, \text{ Times}$ $=(1-\alpha) ^{N}$ The Probability of received block is erroneous is $=1-(1-\alpha) ^{N}$

In a linear block code, the mapping from messages to codewords is strictly linear. This means the sum (XOR) of two message vectors yields a codeword that is the sum (XOR) of their respective codewords.\nWe are given:\n$C(0001) = 0000111$\n$C(0011) = 1100110$\nWe need to find $C(0010)$. Notice that the message $0010$ can be expressed as the bitwise XOR of $0011$ and $0001$:\n$0010 = 0011 \oplus 0001$\nDue to linearity, the codeword for $0010$ must be the XOR of the codewords for $0011$ and $0001$:\n$C(0010) = 1100110 \oplus 0000111 = 1100001$\nThis directly matches Option B.

According to the Plotkin bound.

For any value of k, the above bound will be satisfied. But as $n > k$ and n is fixed at 5. The maximum value of k that can be selected is 4. So, the maximum number of codewords possible is $2_{4} = 16$ .

Mutual information of two random variables is a measure of the mutual dependence of the two variables. Given that, X and Y are independent. Hence, $I(X:Y)=0$ .

The channel capacity of a memoryless binary symmetric channel can be expressed as, $C=1+p \log _{2} p+(1-p) \log _{2}(1-p)$

Given that

Hmesual irformation I(X;Y)= O for every possible input distribution, then the channel is called as useless (or) zero-capacity channel.

So, the given binary memoryless channel is "useless" channel.

Enlropy of sourco is given as

Subtracting (ii) from (i)

For distortionless transmission, C should be atleast of $R_{b}$