An Introduction to Information Theory

by Fazlollah M. Reza

Overview

Written for an engineering audience, this book has a threefold purpose: (1) to present elements of modern probability theory — discrete, continuous, and stochastic; (2) to present elements of information theory with emphasis on its basic roots in probability theory; and (3) to present elements of coding theory.
The emphasis throughout the book is on such basic concepts as sets, the probability measure associated with sets, sample space, random variables, information measure, and capacity. These concepts proceed from set theory to probability theory and then to information and coding theories. No formal prerequisites are required other than the usual undergraduate mathematics included in an engineering or science program. However, since these programs may not include a course in probability, the author presents an introductory treatment of probability for those who wish to pursue the general study of statistical theory of communications.
The book is divided into four parts: memoryless discrete themes, memoryless continuum, schemes with memory, and an outline of some recent developments. An appendix contains notes to help familiarize the reader with the literature in the field, while the inclusion of many reference tables and an extensive bibliography with some 200 entries makes this an excellent resource for any student in the field.

Product Details

ISBN-13:	9780486158440
Publisher:	Dover Publications
Publication date:	06/15/2012
Series:	Dover Books on Mathematics
Sold by:	Barnes & Noble
Format:	eBook
Pages:	528
File size:	35 MB
Note:	This product may take a few minutes to download.

Table of Contents

PREFACE
CHAPTER 1 Introduction
1-1. Communication Processes
1-2. A Model for a Communication System
1-3. A Quantitative Measure of Information
1-4. A Binary Unit of Information
1-5. Sketch of the Plan
1-6. Main Contributors to Information theory
1-7. An Outline of Information Theory
Part 1 : Discrete Schemes without Memory
CHAPTER 2 Basic Concepts of Probability
2-1. Intuitive Background
2-2. Sets
2-3. Operations on Sets
2-4. Algebra of Sets
2-5. Functions
2-6. Sample Space
2-7. Probability Measure
2-8. Frequency of Events
2-9. Theorem of Addition
2-10. Conditional Probability
2-11. Theorem of Multiplication
2-12. Bayes's Theorem
2-13. Combinatorial Problems in Probability
2-14. Trees and State Diagrams
2-15. Random Variables
2-16. Discrete Probability Functions and Distribution
2-17. Bivariate Discrete Distributions
2-18. Binomial Distribution
2-19. Poisson's Distribution
2-20. Expected Value of a Random Variable
CHAPTER 3 Basic Concepts of Information Theory: Memoryless Finite Schemes
3-1. A Measure of Uncertainty
3-2. An Intuitive Justification
3-3. Formal Requirements for the Average Uncertainty
3-4. H Function as a Measure of Uncertainty
3-5. An Alternative Proof That the Entropy Function Possesses a Maximum
3-6. Sources and Binary Sources
3-7. Measure of Information for Two-dimensional Discrete Finite Probability Schemes
3-8. Conditional Entropies
3-9. A Sketch of a Communication Network
3-10. Derivation of the Noise Characteristics of a Channel
3-11. Some Basic Relationships among Different Entropies
3-12. A Measure of Mutual Information
3-13. Set-theory Interpretation of Shannon's Fundamental Inequalities
3-14. "Redundancy, Efficiency, and Channel Capacity"
3-15. Capacity of Channels with Symmetric Noise Structure
3-16. BSC and BEC
3-17. Capacity of Binary Channels
3-18. Binary Pulse Width Communication Channel
3-19. Uniqueness of the Entropy Function
CHAPTER 4 Elements of Encoding
4-1. The Purpose of Encoding
4-2. Separable Binary Codes
4-3. Shannon-Fano Encoding
4-4. Necessary and Sufficient Conditions for Noiseless
4-5. A Theorem on Decodability
4-6. Average Length of Encoded Messages
4-7. Shannon's Binary Encoding
4-8. Fundamental Theorem of Discrete Noiseless Coding
4-9. Huffman's Minimum-redundancy Code
4-10. Gilbert-Moore Encoding
4-11. Fundamental Theorem of Discrete Encoding in Presence of Noise
4-12. Error-detecting and Error-correcting Codes
4-13. Geometry of the Binary Code Space
4-14. Hammings Single-error Correcting Code
4-15. Elias's Iteration Technique
4-16. A Mathematical Proof of the Fundamental Theorem of Information Theory for Discrete BSC
4-17. Encoding the English Alphabet
Part 2: Continuum without Memory
CHAPTER 5 Continuous Probability Distribution and Density
5-1. Continuous Sample Space
5-2. Probability Distribution Functions
5-3. Probability Density Function
5-4. Normal Distribution
5-5. Cauchy's Distribution
5-6. Exponential Distribution
5-7. Multidimensional Random Variables
5-8. Joint Distribution of Two Variables: Marginal Distribution
5-9. Conditional Probability Distribution and Density
5-10. Bivariate Normal Distribution
5-11. Functions of Random Variables
5-12. Transformation from Cartesian to Polar Coordinate System
CHAPTER 6 Statistical Averages
6-1. Expected Values; Discrete Case
6-2. Expectation of Sums and Products of a Finite Number of Independent Discrete Random Variables
6-3. Moments of a Univariate Random Variable
6-4. Two Inequalities
6-5. Moments of Bivariate Random Variables
6-6. Correlation Coefficient
6-7. Linear Combination of Random Variables
6-8. Moments of Some Common Distribution Functions
6-9. Characteristic Function of a Random Variable
6-10. Characteristic Function and Moment-generating Function of Random Variables
6-11. Density Functions of the Sum of Two Random Variables
CHAPTER 7 Normal Distributions and Limit Theorems
7-1. Bivariate Normal Considered as an Extension of One-dimensional Normal Distribution
7-2. MuItinormal Distribution
7-3. Linear Combination of Normally Distributed Independent Random Variables
7-4. Central-limit Theorem
7-5. A Simple Random-walk Problem
7-6. Approximation of the Binomial Distribution by the Normal Distribution
7-7. Approximation of Poisson Distribution by a Normal Distribution
7-8. The Laws of Large Numbers
CHAPTER 8 Continuous Channel without Memory
8-1. Definition of Different Entropies
8-2. The Nature of Mathematical Difficulties Involved
8-3. Infiniteness of Continuous Entropy
8-4. The Variability of the Entropy in the Continuous Case with Coordinate Systems
8-5. A Measure of Information in the Continuous Case
8-6. Maximization of the Entropy of a Continuous Random Variable
8-7. Entropy Maximization Problems
8-8. Gaussian Noisy Channels
8-9. Transmission of Information in the Presence of Additive Noise
8-10. Channel Capacity in Presence of Gaussian Additive Noise and Specified Transmitter and Noise Average Power
8-11. Relation Between the Entropies of Two Related Random Variables
8-12. Note on the Definition of Mutual Information
CHAPTER 9 Transmission of Band-limited Signals
9-1. Introduction
9-2. Entropies of Continuous Multivariate Distributions
9-3. Mutual Information of Two Gaussian Random Vectors
9-4. A Channel-capacity Theorem for Additive Gaussian Noise
9-5. Digression
9-6. Sampling Theorem
9-7. A Physical Interpretation of the Sampling Theorem
9-8. The Concept of a Vector Space
9-9. Fourier-series Signal Space
9-10. Band-limited Singal Space
9-11. Band-limited Ensembles
9-12. Entropies of Band-limited Ensemble in Signal Space
9-13. A Mathematical Model for Communication of Continuous Signals
9-14 Optimal Decoding
9-15. A Lower Bound for the Probability of Error
9-16. An Upper Bound for the Probability of Error.
9-17. Fundamental Theorem of Continuous Memoryless Channels in Presence of Additive Noise
9-18. Thomasian's Estimate
Part 3 : Schemes with Memory
CHAPTER 10 Stochastic Processes
10-1. Stochastic Theory
10-2. Examples of a Stochastic Process
10-3. Moments and Expectations
10-4. Stationary Processes
10-5. Ergodic Processes
10-6. Correlation Coefficients and Correlation Functions
10-7. Example of a Normal Stochastic Process
10-8. Examples of Computation of Correlation Functions
10-9. Some Elementary Properties of Correlation Functions Stationary Processes
10-10. Power Spectra and Correlation Functions
10-11. Response of Linear Lumped Systems to Ergodic Excitation
10-12. Stochastic Limits and Convergence
10-13. Stochastic Differentiation and Integration
10-14. Gaussian-process Example of a Stationary Process
10-15. The Over-all Mathematical Structure of the Stochastic Processes
10-16. A Relation between Positive Definite Functions and Theory of Probability
CHAPTER 11 Communication under Stochastic Regimes
11-1. Stochastic Nature of Communication
11-2. Finite Markov Chains
11-3. A Basic Theorem on Regular Markov Chains
11-4. Entropy of a Simple Markov Chain
11-5. Entropy of a Discrete Stationary Source
11-6. Discrete Channels with Finite Memory
11-7. Connection of the Source and the Discrete Channel with Memory
11-8. Connection of a Stationary Source to a Stationary Channel
Part 4 : Some Recent Developments
CHAPTER 12 The Fundamental Theorem of Information Theory
PRELIMINARIES
12-1. A Decision Scheme
12-2. The Probability of Error in a Decision Scheme
12-3. A Relation between Error Probability and Equivocation
12-4. The Extension of Discrete Memoryless Noisy Channels
FEINSTEIN'S PROOF
12-5. On Certain Random Variables Associated with a Communication System
12-6. Feinstein's Lemma
12-7. Completion of the Proof
SHANNON'S PROOF
12-8. Ensemble Codes
12-9. A Relation between Transinformation and Error Probability
12-10. An Exponential Bound for Error Probability
WOLFOWITZ'S PROOF
12-11. The Code Book
12-12. A Lemma and Its Application
12-13. Estimation of Bounds
12-14. Completion of Wolfowitz's Proof
CHAPTER 13 Group Codes
13-1. Introduction
13-2. The Concept of a Group
13-3. Fields and Rings
13-4. Algebra for Binary n-Digit Words
13-5. Hammings Codes
13-6. Group Codes
13-7. A Detection Scheme for Group Codes
13-8. Slepian's Technique for Single-error Correcting Group Codes
13-9. Further Notes on Group Codes
13-10. Some Bounds on the Number of Words in a Systematic Code
APPENDIX Additional Notes and Tables
N-1 The Gambler with a Private Wire
N-2 Some Remarks on Sampling Theorem
N-3 Analytic Signals and the Uncertainty Relation
N-4 Elias's Proof of the Fundamental Theorem for BSC
N-5 Further Remarks oil Coding Theory
N-6 Partial Ordering of Channels
N-7 Information Theory and Radar Problems
T-1 Normal Probability Integral
T-2 Normal Distributions
T-3 A Summary of Some Common Probability Functions
T-4 Probability of No Error for Best Group Code
T-5 Parity-check Rules for Best Group Alphabets
T-6 Logarithms to the Base 2
T-7 Entropy of a Discrete Binary Source
BIBLIOGRAPHY
NAME INDEX
SUBJECT INDEX