HW9

Dear all,

HW9… :)

1. Another question on channel capacity, given a channel with input alphabets \(\{1,2,\cdots,n\}\) and output alphabets \(\{1,2,\cdots,m\}\). If the probability of output \(Y\) given input \(X\) is always equal to some permutation of \(p_1, p_2,\cdots,p_m\), i.e., \(p_{Y|X}(i|j) = p_{\sigma_j(i)}\) for some permutation \(\sigma_j(\cdot)\). For example, \(p_1 = 0.2, p_2 = 0.3, p_3=0.5\) and \(\sigma_1(1)=2, \sigma_1(2)=1, \sigma_1(3)=3\). So \(p_{Y|X}(1|1)=p_{\sigma_1(1)}=p_2=0.3\), \(p_{Y|X}(2|1)=p_{\sigma_1(2)}=p_1=0.2\), and \(p_{Y|X}(3|1)=p_{\sigma_1(3)}=p_3=0.5\).

Moreover, assume that \(\sum_{j=1}^{m} p_{Y|X}(i|j) = \sum_{j=1}^{m} p_{Y|X}(i’|j)\) for any \(i\) and \(i'\).

Show that the capacity of the channel is

\( \log m - H(p_1,p_2,\cdots,p_m),\)

where \(H(p_1,p_2,\cdots,p_m) = - \sum_{i} p_i \log p_i \).

2. We have parallel Gaussian sources outputting 5 components each time. The components are independent of each other and their variances are 0.5, 2, 3, 4, 5, respectively. The distortion measure is defined as the average distortion as follows

\( D = \frac{1}{5} \sum_{i=1}^5 E[(X_i - \hat{X}_i)^2] \).

In the best scenario, how many bits are needed to compress the 10,000 inputs (50,000 components in total) to ensure distortion \(D \le 1\).

Best,

Sam