Computer Science – Information Theory
Scientific paper
2011-02-24
Computer Science
Information Theory
37 pages, Submitted to IEEE Transactions on Information Theory
Scientific paper
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. We consider a decoder that decodes the positions of the deleted and inserted runs in addition to the transmitted codeword. Analyzing the performance of such a decoder leads to a computable 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 cases of deletion channels and duplication channels where previous results exist, our rates are very close to the best-known capacity lower bounds.
Ramchandran Kannan
Tatikonda Sekhar
Venkataramanan Ramji
No associations
LandOfFree
Achievable Rates for Channels with Deletions and Insertions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Achievable Rates for Channels with Deletions and Insertions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Achievable Rates for Channels with Deletions and Insertions will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-709001