Skip to main content

Bounds on the capacity of discrete memoryless channels corrupted by synchronization and substitution errors

Publication ,  Journal Article
Mercier, H; Tarokh, V; Labeau, F
Published in: IEEE Transactions on Information Theory
June 25, 2012

We study the capacity of discrete memoryless channels with synchronization errors and additive noise. We first show that with very large alphabets, their capacity can be achieved by independent and identically distributed input sources, and establish proven tight lower and upper capacity bounds. We also derive tight numerical capacity bounds for channels where the synchronization between the input and output is partly preserved, for instance using incorruptible synchronization markers. Such channels include channels with duplication errors, channels that only insert or delete zeros, and channels with bitshift errors studied in magnetic recording. Channels with small alphabets and corrupted by synchronization errors have an infinite memory. Revisiting the theoretical work of Dobrushin and adapting techniques used to compute capacity bounds for finite-state source/channel models, we compute improved numerical capacity lower bounds for discrete memoryless channels with small alphabets, synchronization errors, and memoryless noise. An interesting and somewhat surprising result is that as long as the input sequences are not completely deleted, the capacity of channels corrupted by discrete timing errors is always nonzero even if all the symbols are corrupted. © 2012 IEEE.

Duke Scholars

Published In

IEEE Transactions on Information Theory

DOI

ISSN

0018-9448

Publication Date

June 25, 2012

Volume

58

Issue

7

Start / End Page

4306 / 4330

Related Subject Headings

  • Networking & Telecommunications
  • 4613 Theory of computation
  • 4006 Communications engineering
  • 1005 Communications Technologies
  • 0906 Electrical and Electronic Engineering
  • 0801 Artificial Intelligence and Image Processing
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Mercier, H., Tarokh, V., & Labeau, F. (2012). Bounds on the capacity of discrete memoryless channels corrupted by synchronization and substitution errors. IEEE Transactions on Information Theory, 58(7), 4306–4330. https://doi.org/10.1109/TIT.2012.2191682
Mercier, H., V. Tarokh, and F. Labeau. “Bounds on the capacity of discrete memoryless channels corrupted by synchronization and substitution errors.” IEEE Transactions on Information Theory 58, no. 7 (June 25, 2012): 4306–30. https://doi.org/10.1109/TIT.2012.2191682.
Mercier H, Tarokh V, Labeau F. Bounds on the capacity of discrete memoryless channels corrupted by synchronization and substitution errors. IEEE Transactions on Information Theory. 2012 Jun 25;58(7):4306–30.
Mercier, H., et al. “Bounds on the capacity of discrete memoryless channels corrupted by synchronization and substitution errors.” IEEE Transactions on Information Theory, vol. 58, no. 7, June 2012, pp. 4306–30. Scopus, doi:10.1109/TIT.2012.2191682.
Mercier H, Tarokh V, Labeau F. Bounds on the capacity of discrete memoryless channels corrupted by synchronization and substitution errors. IEEE Transactions on Information Theory. 2012 Jun 25;58(7):4306–4330.

Published In

IEEE Transactions on Information Theory

DOI

ISSN

0018-9448

Publication Date

June 25, 2012

Volume

58

Issue

7

Start / End Page

4306 / 4330

Related Subject Headings

  • Networking & Telecommunications
  • 4613 Theory of computation
  • 4006 Communications engineering
  • 1005 Communications Technologies
  • 0906 Electrical and Electronic Engineering
  • 0801 Artificial Intelligence and Image Processing