Analytical Lower Bounds on the Capacity of Insertion and Deletion Channels

Details Analytical Lower Bounds on the Capacity of Insertion and Deletion Channels Analytical Lower Bounds on the Capacity of Insertion and Deletion Channels

2011-01-06

arxiv.org/abs/1101.1310v1

Computer Science

Information Theory

Submitted to the IEEE Transaction on Information Theory

Scientific paper

We develop several analytical lower bounds on the capacity of binary insertion and deletion channels by considering independent uniformly distributed (i.u.d.) inputs and computing lower bounds on the mutual information between the input and output sequences. For the deletion channel, we consider three different models: independent identically distributed (i.i.d.) deletion channel, i.i.d. deletion/substitution channel and i.i.d. deletion channel with additive white Gaussian noise (AWGN). The latter two models are introduced to incorporate effects of the channel noise along with synchronization errors. For the insertion channel case we assume the transmitted bits are replaced with two bits with a certain probability independently of other insertion events. We consider two specific cases: Gallager's model where the pair of bits are random and uniform over the four possibilities, and the sticky channel where transmitted bits are duplicated. The general approach taken is similar in all cases, however the specific computations differ. Furthermore, the approach yields a useful lower bound on the capacity for a wide range of deletion probabilities for the deletion channels, while it provides a beneficial bound only for very low insertion probabilities for the insertion models adopted. We emphasize the importance of these results by noting that 1) our results are the first analytical bounds on the capacity of deletion-AWGN channels, 2) the results developed are the best available analytical lower bounds on the deletion/substitution case, 3) for the deletion only channel, our results competes well with the best available lower bounds for small deletion probabilities and they explicitly obtain the first order terms in the recently proved capacity expansions, 4) for both sticky and Gallager insertion channel models, the new lower bounds improve the existing results for small insertion probabilities.

Affiliated with

Also associated with

No associations

Rating

Analytical Lower Bounds on the Capacity of Insertion and Deletion Channels 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 Analytical Lower Bounds on the Capacity of Insertion and Deletion Channels, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Analytical Lower Bounds on the Capacity of Insertion and Deletion Channels will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-482928