Last few talks . . .

• We looked at various data compression techniques

Last few talks . . .

• We looked at various data compression techniques

• Mostly considered random input vectors coming from simple probability distribution

Last few talks . . .

• We looked at various data compression techniques

• Mostly considered random input vectors coming from simple probability distribution

• Mostly each component was independent of others

Motivation

• Betters compression for real world data which often has interesting co-relation

Motivation

• Betters compression for real world data which often has interesting co-relation

• Noisy channel with input $x$ and output $y$ can be looked at as joint ensembles where x and y are dependent

Motivation

• Betters compression for real world data which often has interesting co-relation

• Noisy channel with input $x$ and output $y$ can be looked at as joint ensembles where x and y are dependent

• Information content in context of noisy channels

Dependent Random Variables

• Entropy

$$H(X) = \sum_{x \in A_x} P(x) \log_2 \frac{1}{P(x)}$$

Dependent Random Variables

• Entropy

$$H(X) = \sum_{x \in A_x} P(x) \log_2 \frac{1}{P(x)}$$

• Joint entropy

$$H(X,Y) = \sum_{xy \in A_xA_y} P(x,y) \log_2 \frac{1}{P(x,y)}$$

Dependent Random Variables

• Entropy

$$H(X) = \sum_{x \in A_x} P(x) \log_2 \frac{1}{P(x)}$$

• Joint entropy

$$H(X,Y) = \sum_{xy \in A_xA_y} P(x,y) \log_2 \frac{1}{P(x,y)}$$

• For independent random variables

$$H(X,Y) = H(X) + H(Y) \iff P(x,y) = P(x)P(y)$$

Dependent Random Variables

• Conditional entropy of $X$ given $y=b_k$

$$H(X | y = b_k) = \sum_{x \in A_x} P(x|y=b_k) \log_2 \frac{1}{P(x | y=b_k)}$$

Dependent Random Variables

• Conditional entropy of $X$ given $y=b_k$

$$H(X | y = b_k) = \sum_{x \in A_x} P(x|y=b_k) \log_2 \frac{1}{P(x | y=b_k)}$$

• Conditional entropy of $X$ given $Y$

$$H(X | Y) = \sum_{y \in A_y} P(y) \left[ \sum_x P(x|y)\log_2 \frac{1}{P(x|y)} \right]$$

Dependent Random Variables

• Conditional entropy of $X$ given $Y$ $$H(X | Y) = \sum_{xy \in A_xA_y} P(x | y) \log_2 \frac{1}{P(x | y)}$$

Dependent Random Variables

• Chain rule of conditional entropy

$$H(X,Y) = H(X) + H(Y|X) = H(Y) + H(X|Y)$$

Dependent Random Variables

• Chain rule of conditional entropy

$$H(X,Y) = H(X) + H(Y|X) = H(Y) + H(X|Y)$$

Proof-

$$H(X,Y) = \sum_{xy \in A_xA_y} P(x,y) \log_2 \frac{1}{P(x,y)}$$

Dependent Random Variables

• Chain rule of conditional entropy

$$H(X,Y) = H(X) + H(Y|X) = H(Y) + H(X|Y)$$

Proof-

$$H(X,Y) = \sum_{xy \in A_xA_y} P(x,y) \log_2 \frac{1}{P(x,y)}$$

$$H(X,Y) = \sum_{xy \in A_xA_y} P(x,y) \log_2 \frac{1}{P(x|y)P(y)}$$

Mutual information between $X$ and $Y$

• Mutual information measures information $X$ contains about $Y$ or vice versa

Mutual information between $X$ and $Y$

• Mutual information measures information $X$ contains about $Y$ or vice versa

• Relative entropy or KL divergence between P(x) and Q(x)

$$D_{KL}(P \parallel Q) = \sum_x P(x) \log \frac{P(x)}{Q(x)}$$

Mutual information between $X$ and $Y$

• Mutual information measures information $X$ contains about $Y$ or vice versa

• Relative entropy or KL divergence between P(x) and Q(x)

$$D_{KL}(P \parallel Q) = \sum_x P(x) \log \frac{P(x)}{Q(x)}$$

• So mutual information $I(X;Y)$, cane be understood as relative entropy between the joint distribution and the product of marginal distributions

Mutual information between $X$ and $Y$

• Mutual information measures information $X$ contains about $Y$ or vice versa

• Relative entropy or KL divergence between P(x) and Q(x)

$$D_{KL}(P \parallel Q) = \sum_x P(x) \log \frac{P(x)}{Q(x)}$$

• So mutual information $I(X;Y)$, cane be understood as relative entropy between the joint distribution and the product of marginal distributions

$$I(X;Y) = D_{KL}(P(x,y) \parallel P(x)P(y))$$

Mutual information between $X$ and $Y$

$$I(X;Y) = \sum_{xy \in A_xA_y} P(x,y) \log_2 \frac{P(x,y)}{P(x)P(y)}$$

Mutual information between $X$ and $Y$

$$I(X;Y) = \sum_{xy \in A_xA_y} P(x,y) \log_2 \frac{P(x,y)}{P(x)P(y)}$$

$$I(X;Y) = \sum_{xy \in A_xA_y} P(x,y) \log_2 \frac{P(x|y)P(y)}{P(x)P(y)}$$

Mutual information between $X$ and $Y$

$$I(X;Y) = \sum_{xy \in A_xA_y} P(x,y) \log_2 \frac{P(x,y)}{P(x)P(y)}$$

$$I(X;Y) = \sum_{xy \in A_xA_y} P(x,y) \log_2 \frac{P(x|y)P(y)}{P(x)P(y)}$$

$$I(X;Y) = \sum_{xy \in A_xA_y} P(x,y) \log_2 \frac{P(x|y)}{P(x)}$$

Mutual information between $X$ and $Y$

$$I(X;Y) = \sum_{xy \in A_xA_y} P(x,y) \log_2 \frac{P(x,y)}{P(x)P(y)}$$

$$I(X;Y) = \sum_{xy \in A_xA_y} P(x,y) \log_2 \frac{P(x|y)P(y)}{P(x)P(y)}$$

$$I(X;Y) = \sum_{xy \in A_xA_y} P(x,y) \log_2 \frac{P(x|y)}{P(x)}$$

$$I(X;Y) = \sum_{xy \in A_xA_y} P(x,y) \log_2 \frac{P(x|y)}{P(x)}$$

Noisy channels

• A discrete memoryless channel $Q$ is characterized $A_x$ and $A_y$ and $P(y|x)$

Noisy channels

• A discrete memoryless channel $Q$ is characterized $A_x$ and $A_y$ and $P(y|x)$

• $Q$ defines conditional prob. $P(y|x)$, if we choose an input dist. $P(X)$ we then have a joint dist.

$$P(x, y) = P(x|y)p(y)$$

Noisy channels

• A discrete memoryless channel $Q$ is characterized $A_x$ and $A_y$ and $P(y|x)$

• $Q$ defines conditional prob. $P(y|x)$, if we choose an input dist. $P(X)$ we then have a joint dist.

$$P(x, y) = P(x|y)p(y)$$

• we can bayes theorem to infer input given the output

$$P(x | y) = \frac{P(y | x) P(x)}{ P(y) }$$

1. BSC

• $A_x = {0, 1}$
• $A_y = {0, 1}$

Image Credit: Wikimedia

Example.

• Consider BSC with $f= 0.15, p_0 = 0.9, p_1 = 0.1$, compute $P(x=1|y=0)$

Example.

• Consider BSC with $f= 0.15, p_0 = 0.9, p_1 = 0.1$, compute $P(x=1|y=0)$

$$P(x=1|y=0) = \frac{P(y=0|x=1)P(x=1)}{P(y=0)}$$

Example.

• Consider BSC with $f= 0.15, p_0 = 0.9, p_1 = 0.1$, compute $P(x=1|y=0)$

$$P(x=1|y=0) = \frac{P(y=0|x=1)P(x=1)}{P(y=0)}$$

$$P(x=1|y=0) = \frac{0.15 \times 0.1}{0.9 \times 0.85 + 0.1 \times 0.15 }$$

Example.

• Consider BSC with $f= 0.15, p_0 = 0.9, p_1 = 0.1$, compute $P(x=1|y=0)$

$$P(x=1|y=0) = \frac{P(y=0|x=1)P(x=1)}{P(y=0)}$$

$$P(x=1|y=0) = \frac{0.15 \times 0.1}{0.9 \times 0.85 + 0.1 \times 0.15 }$$

$$P(x=1|y=0) = \frac{0.015 \times 0.1}{0.78} = 0.019$$

Example.

• Consider BSC with $f= 0.15, p_0 = 0.9, p_1 = 0.1$, compute $P(x=1|y=0)$

$$P(x=1|y=0) = \frac{P(y=0|x=1)P(x=1)}{P(y=0)}$$

$$P(x=1|y=0) = \frac{0.15 \times 0.1}{0.9 \times 0.85 + 0.1 \times 0.15 }$$

$$P(x=1|y=0) = \frac{0.015 \times 0.1}{0.78} = 0.019$$

• From above we know that $P(y=0) = 0.78, P(y=1) = 0.22$, let's look at mutual information

Example.

• Consider BSC with $f= 0.15, p_0 = 0.9, p_1 = 0.1$, compute $P(x=1|y=0)$

$$P(x=1|y=0) = \frac{P(y=0|x=1)P(x=1)}{P(y=0)}$$

$$P(x=1|y=0) = \frac{0.15 \times 0.1}{0.9 \times 0.85 + 0.1 \times 0.15 }$$

$$P(x=1|y=0) = \frac{0.015 \times 0.1}{0.78} = 0.019$$

• From above we know that $P(y=0) = 0.78, P(y=1) = 0.22$, let's look at mutual information

$$I(X;Y) = H(Y) - H(Y|X)$$

Example.

• Consider BSC with $f= 0.15, p_0 = 0.9, p_1 = 0.1$, compute $P(x=1|y=0)$

$$P(x=1|y=0) = \frac{P(y=0|x=1)P(x=1)}{P(y=0)}$$

$$P(x=1|y=0) = \frac{0.15 \times 0.1}{0.9 \times 0.85 + 0.1 \times 0.15 }$$

$$P(x=1|y=0) = \frac{0.015 \times 0.1}{0.78} = 0.019$$

• From above we know that $P(y=0) = 0.78, P(y=1) = 0.22$, let's look at mutual information

$$I(X;Y) = H(Y) - H(Y|X)$$

$$I(X;Y) = H_2(0.22) - H_2(0.15) = 0.76 − 0.61 = 0.15 bits.$$

$$H_2(p) = p \log \frac{1}{p} + (1-p) \log \frac{1}{(1-p)}$$

Capacity of a channel $Q$

$$C(Q) = \max_{P_x} I(X;Y)$$

• The distribution $P_x$ that achieves the maximum is called the optimal input distribution, denoted by $P^*_x$

Capacity of a channel $Q$

$$C(Q) = \max_{P_x} I(X;Y)$$

• The distribution $P_x$ that achieves the maximum is called the optimal input distribution, denoted by $P^*_x$

• Eventually we will learn that the $C(Q)$ does indeed measure the maximum amount of error-free information that can be transmitted over the channel per unit time.

Capacity of a channel $Q$

$$C(Q) = \max_{P_x} I(X;Y)$$

• The distribution $P_x$ that achieves the maximum is called the optimal input distribution, denoted by $P^*_x$

• Eventually we will learn that the $C(Q)$ does indeed measure the maximum amount of error-free information that can be transmitted over the channel per unit time.

• If we look at BSC channel again with $f= 0.15, p_0 = 0.9, p_1 = 0.1$, mutual information was:

$$I(X;Y) = H_2(0.22) - H_2(0.15) = 0.76 − 0.61 = 0.15 bits.$$

Capacity of a channel $Q$

$$C(Q) = \max_{P_x} I(X;Y)$$

• The distribution $P_x$ that achieves the maximum is called the optimal input distribution, denoted by $P^*_x$

• Eventually we will learn that the $C(Q)$ does indeed measure the maximum amount of error-free information that can be transmitted over the channel per unit time.

• If we look at BSC channel again with $f= 0.15, p_0 = 0.9, p_1 = 0.1$, mutual information was:

$$I(X;Y) = H_2(0.22) - H_2(0.15) = 0.76 − 0.61 = 0.15 bits.$$

• Optimal input distribution is $p_0 = 0.5, p_1 = 0.5$, keeping the same noise level we get

$$C(Q_{BSC}) = H_2(0.5) - H_2(0.15) = 1 − 0.61 = 0.39 bits.$$

2. BEC

• $A_x = { 0, 1 }$
• $A_y = {0, ?, 1}$

Image Credit: Wikimedia

Example.

• Let's look at capacity for BEC with general $p_e=f$

Example.

• Let's look at capacity for BEC with general $p_e=f$

$$I(X;Y) = H(X) - H(X|Y)$$

Example.

• Let's look at capacity for BEC with general $p_e=f$

$$I(X;Y) = H(X) - H(X|Y)$$

• We can again use symmetry argument at use 0.5, 0.5 distribution, so $H(X) = H_2(0.5)$

• As for $H(X|Y)$, we are uncertain about x given y only when y is ?

• Above as probability $f / 2 + f / 2$, so $H(X|Y) = f H_2(0.5)$

• So $C = I(X;Y) = H_2(0.5) - f H_2(0.5) = 1 - f$

• This can also be done without assuming symmetry first

• This can also be done without assuming symmetry first

• Consider prob distribution ${p_0, p_1}$

• This can also be done without assuming symmetry first

• Consider prob distribution ${p_0, p_1}$

• With prob of $y = ?$ as $p_0 f + p_1 f = f$, $H(X|Y) = f H_2(p_1)$

• This can also be done without assuming symmetry first

• Consider prob distribution ${p_0, p_1}$

• With prob of $y = ?$ as $p_0 f + p_1 f = f$, $H(X|Y) = f H_2(p_1)$

• $I(X;Y) = H_2(p_1) - f H_2(p_1) = (1 - f)H_2(p_1)$

• This can also be done without assuming symmetry first

• Consider prob distribution ${p_0, p_1}$

• With prob of $y = ?$ as $p_0 f + p_1 f = f$, $H(X|Y) = f H_2(p_1)$

• $I(X;Y) = H_2(p_1) - f H_2(p_1) = (1 - f)H_2(p_1)$

• $I(X;Y)$ achieves maximum when $p_1 = 0.5$

3. Z Channel

• $A_x = {0, 1}$
• $A_y = {0, 1}$

$$\begin{array}{ccccccccc} 0 & \xrightarrow{} & 0 \\ & \nearrow{p_e} \\ 1 & \xrightarrow{} & 1 \\ \end{array}$$

Example.

• Consider Z channel with $p_e=f= 0.15, p_0, p_1$

Example.

• Consider Z channel with $p_e=f= 0.15, p_0, p_1$

$$P(y=1)=p_1(1-f)$$

Example.

• Consider Z channel with $p_e=f= 0.15, p_0, p_1$

$$P(y=1)=p_1(1-f)$$

$$I(X;Y) = H(Y) - H(Y|X)$$

Example.

• Consider Z channel with $p_e=f= 0.15, p_0, p_1$

$$P(y=1)=p_1(1-f)$$

$$I(X;Y) = H(Y) - H(Y|X)$$

$$I(X;Y) = H_2(p_1(1-f)) - (p_0 H_2(0) + p_1 H_2(f))$$

Example.

• Consider Z channel with $p_e=f= 0.15, p_0, p_1$

$$P(y=1)=p_1(1-f)$$

$$I(X;Y) = H(Y) - H(Y|X)$$

$$I(X;Y) = H_2(p_1(1-f)) - (p_0 H_2(0) + p_1 H_2(f))$$

$$I(X;Y) = H_2(p_1(1-f)) - p_1 H_2(f))$$

Example.

• Consider Z channel with $p_e=f= 0.15, p_0, p_1$

$$P(y=1)=p_1(1-f)$$

$$I(X;Y) = H(Y) - H(Y|X)$$

$$I(X;Y) = H_2(p_1(1-f)) - (p_0 H_2(0) + p_1 H_2(f))$$

$$I(X;Y) = H_2(p_1(1-f)) - p_1 H_2(f))$$

$$p^*_1 = \frac{1 / (1-f)}{1+2^{(H_2(f) / (1-f))}}$$

Example.

• Consider Z channel with $p_e=f= 0.15, p_0, p_1$

$$P(y=1)=p_1(1-f)$$

$$I(X;Y) = H(Y) - H(Y|X)$$

$$I(X;Y) = H_2(p_1(1-f)) - (p_0 H_2(0) + p_1 H_2(f))$$

$$I(X;Y) = H_2(p_1(1-f)) - p_1 H_2(f))$$

$$p^*_1 = \frac{1 / (1-f)}{1+2^{(H_2(f) / (1-f))}}$$

• For $f=0.15$ we get $p^*_1 = 0.445$ to maximize mutual information

Example.

• Consider Z channel with $p_e=f= 0.15, p_0, p_1$

$$P(y=1)=p_1(1-f)$$

$$I(X;Y) = H(Y) - H(Y|X)$$

$$I(X;Y) = H_2(p_1(1-f)) - (p_0 H_2(0) + p_1 H_2(f))$$

$$I(X;Y) = H_2(p_1(1-f)) - p_1 H_2(f))$$

$$p^*_1 = \frac{1 / (1-f)}{1+2^{(H_2(f) / (1-f))}}$$

• For $f=0.15$ we get $p^*_1 = 0.445$ to maximize mutual information

• With this prob dist $C(Q_z) = 0.685$

4. Noisy typewriter

• $A_x = A_y = {A, B, ...., Z, -}$
• Circular arrangements for the letters

Intuition for noisy channel coding theorem

• For a channel $Q$, there is a non-negative number $C$ (channel capacity), with the following property

Intuition for noisy channel coding theorem

• For a channel $Q$, there is a non-negative number $C$ (channel capacity), with the following property

• For any $\epsilon > 0$ and $R < C$, for large enough $N$, there exists a block code of length $N$ and $rate \geq R$ and a decoding algorithm, such that

Intuition for noisy channel coding theorem

• For a channel $Q$, there is a non-negative number $C$ (channel capacity), with the following property

• For any $\epsilon > 0$ and $R < C$, for large enough $N$, there exists a block code of length $N$ and $rate \geq R$ and a decoding algorithm, such that

• the maximal probability of block error is $\leq \epsilon$

Example

• For the noisy typewriter, we can define prob distribution such that only third letter is used

Example

• For the noisy typewriter, we can define prob distribution such that only third letter is used

• These letters form a non-confusable subset of the input alphabet, block code of length N = 1

Example

• For the noisy typewriter, we can define prob distribution such that only third letter is used

• These letters form a non-confusable subset of the input alphabet, block code of length N = 1

• the error-free information rate of this system is $log_2(9)bits$

Conti: Intuition for noisy channel coding theorem

• If we use any channel lot of times (say N) in sequence then that collection behaves much like noisy typewriter channel

Conti: Intuition for noisy channel coding theorem

• If we use any channel lot of times (say N) in sequence then that collection behaves much like noisy typewriter channel

• What applies to noisy typewriter channel applies to noisy channel in general

Conti: Intuition for noisy channel coding theorem

• If we use any channel lot of times (say N) in sequence then that collection behaves much like noisy typewriter channel

• What applies to noisy typewriter channel applies to noisy channel in general

• Consider extended BSC channel, each block code of length $N$ and total input space ($X$) of size $2^N$

Conti: Intuition for noisy channel coding theorem

• If we use any channel lot of times (say N) in sequence then that collection behaves much like noisy typewriter channel

• What applies to noisy typewriter channel applies to noisy channel in general

• Consider extended BSC channel, each block code of length $N$ and total input space ($X$) of size $2^N$

• For BSC output alphabets will be same as input, input can map any number of outputs $Y$

• But for large N, there will be output typical set with collection size $2^{NH(Y)}$

• But for large N, there will be output typical set with collection size $2^{NH(Y)}$

• Size of each typical set is $2^{NH(Y|X)}$

• But for large N, there will be output typical set with collection size $2^{NH(Y)}$

• Size of each typical set is $2^{NH(Y|X)}$

• We can choose prob dist $P_x$ so that we get non confusable typical set for input channel

• We can choose prob dist $P_x$ so that we get non confusable typical set for input channel

• almost certainly non confusable input sets = $\frac{2^{NH(Y)}}{2^{NH(Y|X)}}$

• We can choose prob dist $P_x$ so that we get non confusable typical set for input channel

• almost certainly non confusable input sets = $\frac{2^{NH(Y)}}{2^{NH(Y|X)}}$

$$2^{N(H(Y)-H(Y|X))} = 2^{NI(X;Y)} \leq 2^{NC}$$

• We can choose prob dist $P_x$ so that we get non confusable typical set for input channel

• almost certainly non confusable input sets = $\frac{2^{NH(Y)}}{2^{NH(Y|X)}}$

$$2^{N(H(Y)-H(Y|X))} = 2^{NI(X;Y)} \leq 2^{NC}$$

• We can communicate C bits per cycle error free! (using one of the non confusable inputs)

Interesting Problem for discussion: Exercise 9.19