פרופ' יורם רייך

Speaker: Eli Haim

Ph.D. student under the supervision of Prof. Uri Erez and Prof. Yuval Kochman

Wednesday, January 24^th, 2018 at 15:00
Room 011, Kitot Bldg., Faculty of Engineering

Error Probability Bounds in Information Theory: Role of Structure, Performance Criteria and Decision Rules

Abstract

Communication and compression problems exhibit an inherent tradeoff between the blocklength used, the cardinality of the codebook and the reliability attained. While generally an explicit characterization of the tradeoff is difficult, many simple bounds as well as asymptotics have been established over the years.

The capacity may be viewed as a first-order performance characterization. It is the maximal rate for which the error probability goes to zero in the limit where the blocklength tends to infinity. The channel error exponent is a second-order performance characteristic of such asymptotics that is based on the Chernoff bound and large-deviations analysis. Dispersion is another second-order performance characteristic that is based on Berry-Esseen type bounds and central-limit asymptotics.

While in single-user problems the rate and the reliability are both scalar quantities, in the extension to multi-user problems they are replaced by regions. This leads to richer performance criteria, where some collapse to a scalar quantity, while others take the form multi-dimensional regions. In other words, this leads to ramifications of the tradeoffs.

We derive novel upper bounds for the probability of error events for several communication scenarios.

In the first part of the talk we present novel bounds on the error probability of additive (as well as ``nearly-additive'') multiple-access channels. Specifically, it is shown that using structured codes allows to attain expurgation in a distributed manner.

We then consider the channel dispersion criterion for multi-user channels and present a  ``local'' notion of dispersion, in which the dispersion is set according to the trajectory of the rates as they approach the boundary of the capacity region. This notion allows to reduce the problem to the single-user dispersion case.

Finally, we return to consider single-user channels. We derive new finite blocklength achievable bounds for the performance of decoding subject to different decision rules. We do so using random-coding union bounds both with and without an erasure option. We show that for erasure decoding, in striking contrast to non-erasure decoding, bounds based likelihood threshold decoding can be superior to bounds based on pairwise codeword-likelihood comparisons.