Foundations of Coding Theory and Applications

Although devoted to constructions of good codes for error control, secrecy or data compression, the emphasis is on the first direction. Introduces a number of important classes of error-detecting and error-correcting codes as well as their decoding methods. Background material on modern algebra is presented where required. The role of error-correcting codes in modern cryptography is treated as are data compression and other topics related to information theory. The definition-theorem proof style used in mathematics texts is employed through the book but formalism is avoided wherever possible.

Jiri Adamek is the author of Foundations of Coding: Theory and Applications of Error-Correcting Codes with an Introduction to Cryptography and Information Theory, published by Wiley.

Introduction

1

(2)

Part I Coding and Information Theory

3

(58)

Coding and Decoding

5

(12)

Coding

5

(1)

Unique Decoding

6

(1)

Block Codes and Instantaneous Codes

7

(2)

Some Important Block Codes

9

(2)

Construction of Instantaneous Codes

11

(1)

Kraft's Inequality

12

(1)

McMillan's Theorem

13

(4)

Exercises

14

(2)

Notes

16

(1)

Huffman Codes

17

(8)

Information Source

17

(1)

Huffman Codes

17

(1)

Construction of Binary Huffman Codes

18

(3)

Example

21

(1)

Construction of General Huffman Codes

22

(3)

Exercises

24

(1)

Notes

24

(1)

Data Compression and Entropy

25

(14)

An Example of Data Compression

25

(1)

The Idea of Entropy

26

(2)

The Definition of Entropy

28

(1)

An Example

29

(1)

Maximum and Minimum Entropy

30

(2)

Extensions of a Source

32

(1)

Entropy and Average Length

33

(1)

Shannon's Noiseless Coding Theorem

34

(2)

Concluding Remarks

36

(3)

Exercises

36

(2)

Notes

38

(1)

Reliable Communication Through Unreliable Channels

39

(22)

Binary Symmetric Channels

40

(2)

Information Rate

42

(2)

An Example of Increased Reliability

44

(2)

Hamming Distance

46

(2)

Detection of Errors

48

(1)

Correction of Errors

49

(1)

Channel Capacity

50

(6)

Shannon's Fundamental Theorem

56

(5)

Exercises

58

(2)

Notes

60

(1)

Part II Error-Correcting Codes

61

(230)

Binary Linear Codes

63

(16)

Binary Addition and Multiplication

63

(1)

Codes Described by Equations

64

(1)

Binary Linear Codes

65

(2)

Parity Check Matrix

67

(2)

Hamming Codes---Perfect Codes for Single Errors

69

(6)

The Probability of Undetected Errors

75

(4)

Exercises

77

(1)

Notes

78

(1)

Groups and Standard Arrays

79

(12)

Commutative Groups

79

(2)

Subgroups and Cosets

81

(3)

Decoding by Standard Arrays

84

(7)

Exercises

87

(2)

Notes

89

(2)

Linear Algebra

91

(24)

Fields and Rings

91

(2)

The Fields Zp

93

(2)

Linear Spaces

95

(3)

Finite-Dimensional Spaces

98

(3)

Matrices

101

(4)

Operations on Matrices

105

(3)

Orthogonal Complement

108

(7)

Exercises

111

(3)

Notes

114

(1)

Linear Codes

115

(22)

Generator Matrix

115

(4)

Parity Check Matrix

119

(2)

Syndrome

121

(1)

Detection and Correction of Errors

122

(3)

Extended Codes and Other Modifications

125

(3)

Simultaneous Correction and Detection of Errors

128

(2)

MacWilliams Identity

130

(7)

Exercises

133

(2)

Notes

135

(2)

Reed-Muller Codes: Weak Codes with Easy Decoding

137

(24)

Boolean Functions

138

(2)

Boolean Polynomials

140

(4)

Reed-Muller Codes

144

(3)

Geometric Interpretation: Three-Dimensional Case

147

(4)

Geometric Interpretation: General Case

151

(3)

Decoding Reed-Muller Codes

154

(7)

Exercises

159

(1)

Notes

160

(1)

Cyclic Codes

161

(36)

Generator Polynomial

161

(6)

Encoding Cyclic Codes

167

(4)

Parity Check Polynomial

171

(4)

Decoding Cyclic Codes

175

(5)

Error-Trapping Decoding

180

(2)

Golay Code: A Perfect Code for Triple Errors

182

(3)

Burst Errors

185

(3)

Fire Codes: High-Rate Codes for Burst Errors

188

(9)

Exercises

192

(2)

Notes

194

(3)

Polynomials and Finite Fields

197

(32)

Zeros of Polynomials

197

(4)

Algebraic Extensions of a Field

201

(5)

Galois Fields

206

(1)

Primitive Elements

207

(4)

The Characteristic of a Field

211

(2)

Minimal Polynomial

213

(3)

Order

216

(3)

The Structure of Finite Fields

219

(2)

Existence of Galois Fields

221

(8)

Exercises

223

(4)

Notes

227

(2)

BCH Codes: Strong Codes Correcting Multiple Errors

229

(28)

Hamming Codes as Cyclic Codes

230

(2)

Double-Error-Correcting BCH Codes

232

(7)

BCH Codes

239

(6)

Reed-Solomon Codes and Derived Burst-Error-Correcting Codes

245

(1)

Generalized Reed-Muller Codes

246

(2)

Goppa Codes: Asymptotically Good Codes

248

(9)

Exercises

255

(1)

Notes

256

(1)

Fast Decoding of BCH Codes

257

(12)

Error Location and Error Evaluation

258

(2)

Euclidean Algorithm

260

(3)

The Decoding Algorithm

263

(6)

Exercises

266

(1)

Notes

267

(2)

Convolutional Codes

269

(22)

Linear Codes and Convolutional Codes

269

(5)

Generator Polynomials and Generator Matrices

274

(5)

Maximum-Likelihood Decoding of Convolutional Codes

279

(4)

The Viterbi Decoding Algorithm

283

(8)

Exercises

288

(2)

Notes

290

(1)

Part III Cryptography

291

(28)

Cryptography

293

(26)

A Noisy Wiretap

294

(2)

Secret-Key Encryption

296

(7)

Public-Key Encryption

303

(2)

Encryption Based on Large Prime Numbers

305

(2)

Encryption Based on Knapsack Problems

307

(2)

Data Encryption Standard

309

(10)

Exercises

316

(1)

Notes

317

(2)

Appendixes

319

(8)

A Galois Fields

321

(4)

B BCH Codes and Reed-Muller Codes

325

(2)

Bibliography

327

(4)

List of Symbols

331

(2)

Index

333

What is included with this book?

The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.

The Used, Rental and eBook copies of this book are not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.

FREE SHIPPING

Rent More, Save More! Use code: BBRENTAL

5% off 1 book, 7% off 2 books, 10% off 3+ books

Foundations of Coding Theory and Applications of Error-Correcting Codes with an Introduction to Cryptography and Information Theory

Summary

Author Biography

Table of Contents

Supplemental Materials

FREE SHIPPING

Rent More, Save More! Use code: BBRENTAL

5% off 1 book, 7% off 2 books, 10% off 3+ books

Foundations of Coding Theory and Applications of Error-Correcting Codes with an Introduction to Cryptography and Information Theory

Summary

Author Biography

Table of Contents

Supplemental Materials

Digital License