Foundations and Trends® in Communications and Information Theory > Vol 11 > Issue 1-2

Asymptotic Estimates in Information Theory with Non-Vanishing Error Probabilities

By Vincent Y. F. Tan, Department of Electrical and Computer Engineering and Department of Mathematics, National University of Singapore, Singapore, vtan@nus.edu.sg

 
Suggested Citation
Vincent Y. F. Tan (2014), "Asymptotic Estimates in Information Theory with Non-Vanishing Error Probabilities", Foundations and Trends® in Communications and Information Theory: Vol. 11: No. 1-2, pp 1-184. http://dx.doi.org/10.1561/0100000086

Publication Date: 23 Sep 2014
© 2014 V. Y. F. Tan
 
Subjects
Data compression,  Detection and estimation,  Information theory and statistics,  Multiuser information theory,  Joint source/channel coding,  Shannon theory,  Rate-distortion theory,  Source coding,  Statistical signal processing
 

Free Preview:

Download extract

Share

Download article
In this article:
Part I: Fundamentals 
1. Introduction 
2. Binary Hypothesis Testing 
Part II: Point-To-Point Communication 
3. Source Coding 
4. Channel Coding 
Part III: Network Information Theory 
5. Channels with Random State 
6. Distributed Lossless Source Coding 
7. A Special Class of Gaussian Interference Channels 
8. A Special Class of Gaussian Multiple Access Channels 
9. Summary, Other Results, Open Problems 
Acknowledgements 
References 

Abstract

This monograph presents a unified treatment of single- and multi-user problems in Shannon’s information theory where we depart from the requirement that the error probability decays asymptotically in the blocklength. Instead, the error probabilities for various problems are bounded above by a non-vanishing constant and the spotlight is shone on achievable coding rates as functions of the growing blocklengths. This represents the study of asymptotic estimates with non-vanishing error probabilities.

In Part I, after reviewing the fundamentals of information theory, we discuss Strassen’s seminal result for binary hypothesis testing where the type-I error probability is non-vanishing and the rate of decay of the type-II error probability with growing number of independent observations is characterized. In Part II, we use this basic hypothesis testing result to develop second- and sometimes, even third-order asymptotic expansions for point-to-point communication. Finally in Part III, we consider network information theory problems for which the second order asymptotics are known. These problems include some classes of channels with random state, the multiple-encoder distributed lossless source coding (Slepian-Wolf) problem and special cases of the Gaussian interference and multiple-access channels. Finally, we discuss avenues for further research.

DOI:10.1561/0100000086
ISBN: 978-1-60198-852-2
206 pp. $99.00
Buy book (pb)
 
ISBN: 978-1-60198-853-9
206 pp. $240.00
Buy E-book (.pdf)
Table of contents:
Part I: Fundamentals
1. Introduction
2. Binary Hypothesis Testing
Part II: Point-To-Point Communication
3. Source Coding
4. Channel Coding
Part III: Network Information Theory
5. Channels with Random State
6. Distributed Lossless Source Coding
7. A Special Class of Gaussian Interference Channels
8. A Special Class of Gaussian Multiple Access Channels
9. Summary, Other Results, Open Problems
Acknowledgements
References

Asymptotic Estimates in Information Theory with Non-Vanishing Error Probabilities

This self-contained tutorial presents a unified treatment of single- and multi-user problems in Shannon’s information theory considering in particular the cases that depart from the requirement that the error probability decays asymptotically in the blocklength. Instead, the error probabilities for various problems are bounded above by a non-vanishing constant and the spotlight is shone on achievable coding rates as functions of the growing blocklengths. This represents the study of asymptotic estimates with non-vanishing error probabilities.

Divided into three parts, the monograph begins with an introduction to binary hypothesis testing. From there the author develops the theme for point-to-point communication systems. Finally, Network Information Theory problems such as channels with random state, the multiple-encoder distributed lossless source coding (Slepian-Wolf) problem and special cases of the Gaussian interference and multiple-access channels are considered.

The monograph is written in a didactic nature that makes it accessible for students, researchers and engineers building practical communication systems.

 
CIT-086