摘要 :
We present a simple proof that the capacity of the binary independent and identically distributed (i.i.d.) deletion channel, where each bit is deleted independently with probability$d$, is at least$(1-d)/9$, by developing a corres...
展开
We present a simple proof that the capacity of the binary independent and identically distributed (i.i.d.) deletion channel, where each bit is deleted independently with probability$d$, is at least$(1-d)/9$, by developing a correspondence between the deletion channel and an insertion/deletion channel that we call a Poisson-repeat channel.
收起
摘要 :
This correspondence considers binary deletion channels, where bits are deleted independently with probability$d$; it improves upon the framework used to analyze the capacity of binary deletion channels established by Diggavi and G...
展开
This correspondence considers binary deletion channels, where bits are deleted independently with probability$d$; it improves upon the framework used to analyze the capacity of binary deletion channels established by Diggavi and Grossglauser, improving on their lower bounds. Diggavi and Grossglauser considered codebooks with codewords generated by a first-order Markov chain. They only consider typical outputs, where an output is typical if an$N$bit input gives an$N(1-d)(1-epsilon)$bit output. The improvements in this correspondence arise from two considerations. First, a stronger notion of a typical output from the channel is used, which yields better bounds even for the codebooks studied by Diggavi and Grossglauser. Second, codewords generated by more general processes than first-order Markov chains are considered.
收起
摘要 :
We study memoryless channels with synchronization errors as defined by a stochastic channel matrix allowing for symbol drop-outs or symbol insertions with particular emphasis on the binary and non-binary deletion channels. We offe...
展开
We study memoryless channels with synchronization errors as defined by a stochastic channel matrix allowing for symbol drop-outs or symbol insertions with particular emphasis on the binary and non-binary deletion channels. We offer a different look at these channels by considering equivalent models by fragmenting the input sequence where different subsequences travel through different channels. The resulting output symbols are combined appropriately to come up with an equivalent input–output representation of the original channel which allows for derivation of new upper bounds on the channel capacity. We consider both random and deterministic types of fragmentation processes applied to binary and nonbinary deletion channels. With two specific applications of this idea, a random fragmentation applied to a binary deletion channel and a deterministic fragmentation process applied to a nonbinary deletion channel, we prove certain inequality relations among the capacities of the original channels and those of the introduced subchannels. The resulting inequalities prove useful in deriving tighter capacity upper bounds for: 1) independent identically distributed (i.i.d.) deletion channels when the deletion probability exceeds 0.65 and 2) nonbinary deletion channels. Some extensions of these results, for instance, to the case of deletion/substitution channels are also explored.
收起
摘要 :
In this paper, we directly lower bound the information capacity for channels with independent identically distributed (i.i.d.) deletions and duplications. Our approach differs from previous work in that we focus on the information...
展开
In this paper, we directly lower bound the information capacity for channels with independent identically distributed (i.i.d.) deletions and duplications. Our approach differs from previous work in that we focus on the information capacity using ideas from renewal theory, rather than focusing on the transmission capacity by analyzing the error probability of some randomly generated code using a combinatorial argument. Of course, the transmission and information capacities are equal, but our change of perspective allows for a much simpler analysis that gives more general theoretical results. We then apply these results to the binary deletion channel to improve existing lower bounds on its capacity.
收起
摘要 :
The insertion-deletion channel takes as input a bit string x ? {0, 1}~n, and outputs a string where bits have been deleted and inserted independently at random. The trace reconstruction problem is to recover x from many independen...
展开
The insertion-deletion channel takes as input a bit string x ? {0, 1}~n, and outputs a string where bits have been deleted and inserted independently at random. The trace reconstruction problem is to recover x from many independent outputs (called "traces") of the insertion-deletion channel applied to x. We show that if x is chosen uniformly at random, then exp(O(log~(1/3) n)) traces suffice to reconstruct x with high probability. For the deletion channel with deletion probability q < 1=2 the earlier upper bound was exp(O(log~(1/2) n)). The case of q ≥ 1=2 or the case where insertions are allowed has not been previously analyzed, and therefore the earlier upper bound was as for worst-case strings, i.e., exp(O(log~(1/3) n)).We also show that our reconstruction algorithm runs in n~(1+o(1)) time. A key ingredient in our proof is a delicate two-step alignment procedure where we estimate the location in each trace corresponding to a given bit of x. The alignment is done by viewing the strings as random walks and comparing the increments in the walk associated with the input string and the trace, respectively.
收起
摘要 :
This paper considers a binary channel with deletions and insertions, where each input bit is transformed in one of the following ways: it is deleted with probability $d$, or an extra bit is added after it with probability $i$, or ...
展开
This paper considers a binary channel with deletions and insertions, where each input bit is transformed in one of the following ways: it is deleted with probability $d$, or an extra bit is added after it with probability $i$, or it is transmitted unmodified with probability $1-d-i$. A computable lower bound on the capacity of this channel is derived. The transformation of the input sequence by the channel may be viewed in terms of runs as follows: some runs of the input sequence get shorter/longer, some runs get deleted, and some new runs are added. It is difficult for the decoder to synchronize the channel output sequence to the transmitted codeword mainly due to deleted runs and new inserted runs. The main idea is a mutual information decomposition in terms of the rate achieved by a suboptimal decoder that determines the positions of the deleted and inserted runs in addition to decoding the transmitted codeword. The mutual information between the channel input and output sequences is expressed as the sum of the rate achieved by this decoder and the rate loss due to its suboptimality. Obtaining computable lower bounds on each of these quantities yields a lower bound on the capacity. The bounds proposed in this paper provide the first characterization of achievable rates for channels with general insertions, and for channels with both deletions and insertions. For the special case of the deletion channel, the proposed bound improves on the previous best lower bound for deletion probabilities up to 0.3.
收起
摘要 :
We present novel bounds on the capacity of the independent and identically distributed binary deletion channel. Four upper bounds are obtained by providing the transmitter and the receiver with genie-aided information on suitably...
展开
We present novel bounds on the capacity of the independent and identically distributed binary deletion channel. Four upper bounds are obtained by providing the transmitter and the receiver with genie-aided information on suitably-defined random processes. Since some of the proposed bounds involve infinite series, we also introduce provable inequalities that lead to more manageable results. For most values of the deletion probability, these bounds improve the existing ones and significantly narrow the gap with the available lower bounds. Exploiting the same auxiliary processes, we also derive, as a by-product, two simple lower bounds on the channel capacity, which, for low values of the deletion probability, are almost as good as the best existing lower bounds.
收起
摘要 :
This paper considers the capacity of binary deletion channels, where bits are deleted independently with probability $d$. It improves significantly upon the best previous framework used to obtain provable lower bounds on this capa...
展开
This paper considers the capacity of binary deletion channels, where bits are deleted independently with probability $d$. It improves significantly upon the best previous framework used to obtain provable lower bounds on this capacity by utilizing a stronger definition of a typical output from the channel. The new results give the best known provable bounds on the capacity for all values of $d$. Moreover, the techniques presented here extend to yield lower bounds for channels with certain types of random insertions, namely, duplications, or combinations of duplications and deletions. To demonstrate these techniques in this context, two binary channels are analyzed: a channel where each transmitted bit is copied with probability $v$ and a channel where each transmitted bit is copied a geometrically distributed number of times.
收起
摘要 :
The capacity of sticky channels, a subclass of insertion channels where each symbol may be duplicated multiple times, is considered. The primary result is to provide nearly tight numerical upper and lower bounds for the independen...
展开
The capacity of sticky channels, a subclass of insertion channels where each symbol may be duplicated multiple times, is considered. The primary result is to provide nearly tight numerical upper and lower bounds for the independent and identically distributed (i.i.d.) duplication channel.
收起
摘要 :
In the trace reconstruction problem, an unknown bit string x is an element of {0, 1}(n) is sent through a deletion channel where each bit is deleted independently with some probability q is an element of (0, 1), yielding a contrac...
展开
In the trace reconstruction problem, an unknown bit string x is an element of {0, 1}(n) is sent through a deletion channel where each bit is deleted independently with some probability q is an element of (0, 1), yielding a contracted string (x) over tilde. How many i.i.d. samples of (x) over tilde are needed to reconstruct x with high probability? We prove that there exist x, y is an element of {0, 1}(n) such that at least cn(5/4)/root log n traces are required to distinguish between x and y for some absolute constant c, improving the previous lower bound of cn. Furthermore, our result improves the previously known lower bound for reconstruction of random strings from c log(2) n to c log(9/4) n/root log log n.
收起
原文获取