Extremal Problems of Error Exponents and Capacity of Duplication Channels

• Author / Creator

  Ramezani, Mahdi

• One of the most stunning results of information theory is the channel coding theorem addressing the maximum rate of reliable communication over a noisy channel, known as channel capacity. In this thesis, we consider two problems emerging from the classic channel coding theorem. First, we study the extremal problems of the channel reliability function, which is the exponent with which the probability of making a wrong decision vanishes. To this end, we introduce a set of fundamental channels which exhibit significant monotonicity properties and invoke the theory of Chebychev systems to utilize such properties. We show that the binary symmetric channel (BSC) and binary erasure channel (BEC), which happen to be among the fundamental channels, are the two extremes of the channel reliability function. Also, we show that given a rate and a probability of error as a performance measure, BSC (BEC) needs the longest (shortest) code length to achieve such performance.
  While the first problem is pure theoretical, the second problem addresses a challenging practical scenario. The most fundamental assumption in the classic channel coding theorem is that we receive as many symbols as we send. In reality, however, this is not always true, e.g., a miss-sampling at a conventional receiver might duplicate a symbol. The extra symbol confuses a receiver as it has no clue about the position of duplication. Such scenarios are collectively known as channels with synchronization errors. Unlike their classic counterparts, there is only little known about either the capacity or coding techniques for channels with synchronization errors, even in their simplest forms. In this part, we study the duplication channel by introducing a series expansion for its capacity.

• Subjects / Keywords

  • Random-coding error exponent
  • Insertion/deletion channels
  • Information theory
  • Capacity expansion
  • Error exponents
  • Channel dispersion
  • Channel reliability function
  • Symmetric channels
  • Binary erasure channel (BEC)
  • Chebychev systems
  • T-systems
  • Binary symmetric channel (BSC)
  • Set of basis channels
  • Memoryless binary-input symmetric-output channels
  • Duplication channels
  • Channels with synchronization errors

• Graduation date

  Spring 2013

• Type of Item

  Thesis

• Degree

  Doctor of Philosophy

• DOI

  https://doi.org/10.7939/R3VQ4C

• License

  This thesis is made available by the University of Alberta Libraries with permission of the copyright owner solely for non-commercial purposes. This thesis, or any portion thereof, may not otherwise be copied or reproduced without the written consent of the copyright owner, except to the extent permitted by Canadian copyright law.