Upper Bounds on the Capacity of Deletion Channels Using Channel Fragmentation

Mojtaba Rahmati, Tolga M. Duman

Research output: Contribution to journalArticlepeer-review

22 Scopus citations


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.

Original languageEnglish (US)
Article number6949683
Pages (from-to)146-156
Number of pages11
JournalIEEE Transactions on Information Theory
Issue number1
StatePublished - Jan 1 2015


  • Binary deletion channel
  • capacity upper bounds
  • channel capacity
  • deletion/substitution channe
  • non-binary deletion channel

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences


Dive into the research topics of 'Upper Bounds on the Capacity of Deletion Channels Using Channel Fragmentation'. Together they form a unique fingerprint.

Cite this