A Note on the Deletion Channel Capacity

Author name not available (Why is that?)

Publication date: 11 November 2012

Abstract: Memoryless channels with deletion errors as defined by a stochastic channel matrix allowing for bit drop outs are considered in which transmitted bits are either independently deleted with probability

d

or unchanged with probability

1 - d

. Such channels are information stable, hence their Shannon capacity exists. However, computation of the channel capacity is formidable, and only some upper and lower bounds on the capacity exist. In this paper, we first show a simple result that the parallel concatenation of two different independent deletion channels with deletion probabilities

d_{1}

and

d_{2}

, in which every input bit is either transmitted over the first channel with probability of

l a m b d a

or over the second one with probability of

1 - l a m b d a

, is nothing but another deletion channel with deletion probability of

d = l a m b d a d_{1} + (1 - l a m b d a) d_{2}

. We then provide an upper bound on the concatenated deletion channel capacity

C (d)

in terms of the weighted average of

C (d_{1})

,

C (d_{2})

and the parameters of the three channels. An interesting consequence of this bound is that

C (l a m b d a d_{1} + (1 - l a m b d a)) l e q l a m b d a C (d_{1})

which enables us to provide an improved upper bound on the capacity of the i.i.d. deletion channels, i.e.,

C (d) l e q 0.4143 (1 - d)

for

d g e q 0.65

. This generalizes the asymptotic result by Dalai as it remains valid for all

d g e q 0.65

. Using the same approach we are also able to improve upon existing upper bounds on the capacity of the deletion/substitution channel.

Has companion code repository: https://github.com/JarekDuda/DeletionChannelPracticalCorrection

This page was built for publication: A Note on the Deletion Channel Capacity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6237074)