Information transmitting rate of a noisy discrete channel with Omission/Adding errors

86 Views Asked by At

So for a discrete channel, we have a source which sends signal $i$ at probability $p(i)$ that $\sum p(i) = 1$, and the signal is transmitted through a noisy channel. In Shannon's original paper, the probability of character $i$ is received as $j$ is $p(i,j)$ because of noise.

Thus the transmitting rate of the channel could be calculated as $$ R = H(X) - H_Y(X)$$ $$ = -\sum_i p(i)log_2p(i) + \sum_{i,j} p(i,j)log_2p_j(i)$$

However, what if the noise could randomly omit the signal (sender sends signal $i$, receiver receives nothing) or add the signal (sender sends nothing but receiver receives signal $j$), instead of only changing signal $i$ to $j$?

How to calculate the transmitting rate then?

-- update --

OK, so to be more specific, the receiver doesn't know the signal is omitted or added by the noise. If the sender sends "abc" and receiver receives "bc", the receiver doesn't know there's "a" omitted.

1

There are 1 best solutions below

13
On BEST ANSWER

Suppose your original problem (channel) consisted of the transmitter sending symbols from the finite alphabet $\{X_i\}_{i=1}^{I}$ and the receiver observing symbols from the finite alphabet $\{Y_j\}_{i=1}^{J}$. Then, as you state, you can obtain the maximum rate by computing the mutual information for given joint input-output probabilities $p(i,j)\triangleq \mathbb{P}(\text{transmit } X_i, \text{receive } Y_j), i =1,\ldots I, j=1, \ldots J$.

Now, what you are doing by introducing the options of "omitting the signal" and/or "adding the signal" is essentially considering the augmented symbol alphabets $\{\tilde{X}_i\}_{i=1}^{I+1} \triangleq \{X_i\}_{i=1}^{I} \cup \{0\}$ and $\{\tilde{Y}_j\}_{j=1}^{J+1} \triangleq \{Y_j\}_{i=1}^{J} \cup \{0\}$, for the transmitter and receiver, respectively. This new setup/channel is, of course, also characterized by a set of joint probabilities $\mathbb{P}(\text{transmit } \tilde{X}_i, \text{receive } \tilde{Y}_j)$. Note that these probabilities should be, in general, different from the transition probabilities of the original channel, even for the pairs of non-zero transmit-receive symbols.

You can now repeat the exercise of computing the rate as you did for the original channel, this time considering the joint probabilities for the augmented alphabets.