Suppose you are sending information through a deletion channel with a deletion rate of .5 and then the output of this channel is sent through a sticky channel with a repeat rate of .5 also. No error correction is allowed in this scenario, the information is not coded in any way.I am not looking for an error correction code for this composite channel, I am NOT sending any information through the channel, I just want to calculate the channel capacity. It is well known that the capacity of the IID deletion channel is unknown. What I am hoping for is to show that if you concatenate a deletion channel with a sticky channel that the capacity for the combined channels is zero, or close to zero. Anybody out there who can do this?
$\begingroup$
$\endgroup$
10
-
$\begingroup$ puuuuuh. I'd start with actually drawing kind of a decision tree that starts with "bit 0 is sent", "deleted || not deleted", "sticks || doesn't stick", and then simply sums up all the probabilities of branches that lead to correct transmissions (e.g. if a bit is deleted, but it's the same bit as the bit sent before, and that bit sticks, then you've got no error at all...). This will yield an infinite tree, but you might be able to see a way to note down that sum. $\endgroup$– Marcus MüllerCommented Dec 25, 2018 at 21:04
-
$\begingroup$ @MarcusMüller; So if it yields an infinite tree does that mean that the channel capacity is zero ? Thanks for replying and Merry Christmas too ! $\endgroup$– William HirdCommented Dec 26, 2018 at 0:40
-
$\begingroup$ no, it doesn't mean that. $\endgroup$– Marcus MüllerCommented Dec 26, 2018 at 10:35
-
$\begingroup$ by the way, I changed your title: The channel you're describing isn't noisy. $\endgroup$– Marcus MüllerCommented Dec 26, 2018 at 10:43
-
3$\begingroup$ " Channeling" Dilip Sarwate, Dilip, we need your help with this one, LOL ! $\endgroup$– William HirdCommented Dec 26, 2018 at 18:46
|
Show 5 more comments
1 Answer
$\begingroup$
$\endgroup$
7
The identical and identically distributed (IID) binary deletion and sticky channels are both general repeat channels each characterized by a discrete probability distribution of repeating an input bit in the output $D$ times with $D \in 0, 1, 2, 3, 4, \dots$ with $D\!=\!0$ meaning that the input bit does not appear in the output of the channel at all. The question's probabilities for the deletion channel (first channel, hence the subscript $1$) are given by:
$$P(D_1) = \left[\tfrac{1}{2}, \tfrac{1}{2}, 0, 0, 0, \dots\right],\tag{1}$$
which is to say $P(D_1\!=\!0)=P(D_1\!=\!1)=\frac{1}{2},$ as given in the question.
An IID sticky channel with input duplication probability $\frac{1}{2},$ as given in the question, and of a variety that may at most double the number of bits, is also a general repeat channel, with $D_2\text{-}$times repeat probabilities:
$$P(D_2) = \left[0, \tfrac{1}{2}, \tfrac{1}{2}, 0, 0, \dots\right]\tag{2}$$
Generally, without hard-coding the above numbers, the concatenation (cascade, in series) of the above two channels into a single channel is also a general repeat channel with $D_1D_2\text{-}$times repeat probabilities:
$$P(D_1D_2) = \left[P(D_1\!=\!0) + P(D_2\!=\!0)\\- P(D_1\!=\!0)P(D_2\!=\!0),\\ P(D_1\!=\!1)P(D_2\!=\!1),\\ P(D_1\!=\!2)P(D_2\!=\!1) + P(D_1\!=\!1)P(D_2\!=\!2),\\ P(D_1\!=\!3)P(D_2\!=\!1) + P(D_1\!=\!1)P(D_2\!=\!3),\\ P(D_1\!=\!4)P(D_2\!=\!1)\!+\!P(D_1\!=\!1)P(D_2\!=\!4)\!\\+\!P(D_1\!=\!2)P(D_2\!=\!2),\\ \dots\right]\tag{3}$$
These are probabilities for the possible values of the product of independent variables $D_1$ and $D_2.$ For example the last entry before the ellipsis collects probabilities for the three mutually exclusive events $4\times1=$ $1\times4=$ $2\times2$ $=4.$ Note that $P(D_1D_2) = P(D_2D_1),$ so it does not matter which channel comes first. Using the values of $P(D_1)$ and $P(D_2)$ from Eqs. 1 & 2, we get:
$$P(D_1D_2) = \left[\tfrac{1}{2}, \tfrac{1}{4}, \tfrac{1}{4}, 0, 0, \dots\right]\tag{4}$$
This characterization of the concatenated channel appears more complex than the same for the deletion and sticky channels. For each of the latter, finding the capacity appears to be an open research problem (now at the end of 2018). So I doubt the capacity of the concatenated channel is known either. However, it may be possible to find upper and/or lower bounds. For the capacity of the deletion channel, there seems to be a lower bound $1/18,$ see: Capacity of a Binary Deletion Channel.
Your question says that there should be no error correction. As far as I understand, the channel capacity does not depend on error correction, but if a working code can be demonstrated, then it gives a lower bound for channel capacity.
Mahdi Cheraghchi calls the general repeat channels $\mathcal{D}\text{-}$channels, where $\mathcal{D}$ would be the distribution of $D=D_1D_2$ for the concatenated channel. Perhaps you will find something of interest in their work (Cheraghchi 2018):
A $\mathcal{D}\text{-}$repeat channel, given a bit, draws an independent sample $D ≥ 0$ from $\mathcal{D}$ and outputs $D$ copies of the received bit.
Our framework can be applied to obtain capacity upper bounds for any repetition distribution (the deletion and Poisson-repeat channels corresponding to the special cases of Bernoulli and Poisson distributions).
References
- Mahdi Cheraghchi. 2018. Capacity upper bounds for deletion-type channels. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2018). ACM, New D_2ork, ND_2, USA, 493-506. DOI: https://doi.org/10.1145/3188745.3188768 (arD_1iv:1711.01630 [cs.IT])
answered Dec 30, 2018 at 23:37
-
$\begingroup$ Thanks for replying, I thought I was not going to get any answer ! $\endgroup$ Commented Dec 31, 2018 at 0:05
-
$\begingroup$ Does this mean that the concatenated channel has zero capacity ? $\endgroup$ Commented Dec 31, 2018 at 0:06
-
$\begingroup$ @WilliamHird no, but I haven't deciphered what the paper (Cheraghchi 2018) says. $\endgroup$ Commented Dec 31, 2018 at 0:07
-
-
2$\begingroup$ OK, seeing how there is a small probability that someone else is going to give a better answer than you, I will give you the bounty as a belated Christmas present, and Happy New Year to all my cyberspace colleagues here at StackExchange. $\endgroup$ Commented Dec 31, 2018 at 11:56