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

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.

• The cases you are asking about are treated exactly the same, with the difference that you will be considering an augmented alphabet for transmitter and/or receiver symbols, with the addition of the "nothing" symbol. You should redefine the symbol and channel probabilities for this case and then calculate rate using the standard formula. Jan 30, 2018 at 7:29
– Paul
Jan 30, 2018 at 14:37
• @Paul Wrote a more elaborate version of my comment as an answer. Thanks for the motivation! :) Jan 30, 2018 at 17:36

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.
• Thanks for the answer! I'm also thinking of using something like a 0 or a null character to represent the errors. However, if we use a 0, the source rate for $X$ will be different considering the different probability of making omit/add errors, which means, the information rate of $X$ is dependent on the channel and the noise? Jan 30, 2018 at 19:51
• @DrustZ Of course, if you introduce a $0$ ("null") symbol in your alphabets, you need to figure out the new joint probabilities (which, typically, will depend on the physical channel and noise properties). Apologies for my comment on your formula (now removed); I did not notice the subscript in the notation (I was expecting the notation $p(i|j)$ instead). Jan 30, 2018 at 20:06