Information and coding theory / Gareth A. Jones and J. Mary Jones.

Format:

Book

Author/Creator:

Jones, Gareth A., 1946-

Contributor:

Jones, J. Mary (Josephine Mary), 1946-

Series:

Springer undergraduate mathematics series

Language:

English

Subjects (All):

Information theory.

Coding theory.

Physical Description:

xiii, 210 pages : illustrations ; 24 cm.

Place of Publication:

London ; New York : Springer, [2000]

Summary:

Information theory and coding theory are two related aspects of the same problem: how to transmit information efficiently and accurately. This book provides a clear introduction to both subjects, emphasising the relationship and links between the two. The first part, concentrating on information theory, covers uniquely decodable and instantaneous codes, Huffman coding, entropy, information channels and Shannon's Fundamental Theorem. The second part, on coding theory, uses linear algebra to construct examples of error-correcting codes, such as the Hamming, Hadamard, Golay and Reed-Muller codes.

The authors highlight carefully explained proofs and worked examples throughout and exercises with solutions are provided to consolidate understanding of the main concepts and techniques. Assuming only some basic probability theory and linear algebra, together with a little calculus, this book is aimed at second and third year undergraduate students in mathematics, electronics and computer science.

Contents:

1. Source Coding 1

1.2 Uniquely Decodable Codes 4

1.3 Instantaneous Codes 9

1.4 Constructing Instantaneous Codes 11

1.5 Kraft's Inequality 13

1.6 McMillan's Inequality 14

1.7 Comments on Kraft's and McMillan's Inequalities 16

2. Optimal Codes 19

2.1 Optimality 19

2.2 Binary Huffman Codes 22

2.3 Average Word-length of Huffman Codes 26

2.4 Optimality of Binary Huffman Codes 27

2.5 r-ary Huffman Codes 28

2.6 Extensions of Sources 30

3. Entropy 35

3.1 Information and Entropy 35

3.2 Properties of the Entropy Function 40

3.3 Entropy and Average Word-length 42

3.4 Shannon-Fano Coding 45

3.5 Entropy of Extensions and Products 47

3.6 Shannon's First Theorem 48

3.7 An Example of Shannon's First Theorem 49

4. Information Channels 55

4.1 Notation and Definitions 55

4.2 The Binary Symmetric Channel 60

4.3 System Entropies 62

4.4 System Entropies for the Binary Symmetric Channel 64

4.5 Extension of Shannon's First Theorem to Information Channels 67

4.6 Mutual Information 70

4.7 Mutual Information for the Binary Symmetric Channel 72

4.8 Channel Capacity 73

5. Using an Unreliable Channel 79

5.1 Decision Rules 79

5.2 An Example of Improved Reliability 82

5.3 Hamming Distance 85

5.4 Statement and Outline Proof of Shannon's Theorem 88

5.5 The Converse of Shannon's Theorem 90

5.6 Comments on Shannon's Theorem 93

6. Error-correcting Codes 97

6.1 Introductory Concepts 97

6.2 Examples of Codes 100

6.3 Minimum Distance 104

6.4 Hamming's Sphere-packing Bound 107

6.5 The Gilbert-Varshamov Bound 111

6.6 Hadamard Matrices and Codes 114

7. Linear Codes 121

7.1 Matrix Description of Linear Codes 121

7.2 Equivalence of Linear Codes 127

7.3 Minimum Distance of Linear Codes 131

7.4 The Hamming Codes 133

7.5 The Golay Codes 136

7.6 The Standard Array 141

7.7 Syndrome Decoding 143

Appendix A. Proof of the Sardinas-Patterson Theorem 153

Appendix B. The Law of Large Numbers 157

Appendix C. Proof of Shannon's Fundamental Theorem 159.

Notes:

Includes bibliographical references (pages 191-194) and indexes.

ISBN:

1852336226

OCLC:

43851358