Available:*
Library | Item Barcode | Call Number | Material Type | Item Category 1 | Status |
---|---|---|---|---|---|
Searching... | 30000010062180 | QA268 C62 2000 | Open Access Book | Book | Searching... |
On Order
Summary
Summary
Containing data on number theory, encryption schemes, and cyclic codes, this highly successful textbook, proven by the authors in a popular two-quarter course, presents coding theory, construction, encoding, and decoding of specific code families in an "easy-to-use" manner appropriate for students with only a basic background in mathematics offering revised and updated material on the Berlekamp-Massey decoding algorithm and convolutional codes. Introducing the mathematics as it is needed and providing exercises with solutions, this edition includes an extensive section on cryptography, designed for an introductory course on the subject.
Author Notes
D. R. Hankerson is Professor of Mathematics at Auburn University, Alabama
D. G. Hoffman is Professor of Mathematics at Auburn University, Alabama
D. A. Leonard is Professor of Mathematics at Auburn University, Alabama
C. C. Lindner is Professor of Mathematics at Auburn University, Alabama
K. T. Phelps is Professor of Mathematics at Auburn University, Alabama.
C. A. Rodger is Professor of Mathematics at Auburn University, Alabama
J. R. Wall is Professor of Mathematics at Auburn University, Alabama
Table of Contents
Preface | p. v |
Part I Coding Theory | |
1 Introduction to Coding Theory | p. 1 |
1.1 Introduction | p. 1 |
1.2 Basic assumptions | p. 2 |
1.3 Correcting and detecting error patterns | p. 4 |
1.4 Information rate | p. 6 |
1.5 The effects of error correction and detection | p. 7 |
1.6 Finding the most likely codeword transmitted | p. 8 |
1.7 Some basic algebra | p. 10 |
1.8 Weight and distance | p. 11 |
1.9 Maximum likelihood decoding | p. 12 |
1.10 Reliability of MLD | p. 16 |
1.11 Error-detecting codes | p. 18 |
1.12 Error-correcting codes | p. 22 |
2 Linear Codes | p. 27 |
2.1 Linear codes | p. 27 |
2.2 Two important subspaces | p. 28 |
2.3 Independence, basis, dimension | p. 30 |
2.4 Matrices | p. 35 |
2.5 Bases for C = [S] and C[superscript perpendicular, bottom] | p. 37 |
2.6 Generating matrices and encoding | p. 41 |
2.7 Parity-check matrices | p. 45 |
2.8 Equivalent codes | p. 48 |
2.9 Distance of a linear code | p. 52 |
2.10 Cosets | p. 53 |
2.11 MLD for linear codes | p. 57 |
2.12 Reliability of IMLD for linear codes | p. 62 |
3 Perfect and Related Codes | p. 65 |
3.1 Some bounds for codes | p. 65 |
3.2 Perfect codes | p. 70 |
3.3 Hamming codes | p. 72 |
3.4 Extended codes | p. 75 |
3.5 The extended Golay code | p. 77 |
3.6 Decoding the extended Golay code | p. 79 |
3.7 The Golay code | p. 82 |
3.8 Reed-Muller codes | p. 84 |
3.9 Fast decoding for RM(1, m) | p. 88 |
4 Cyclic Linear Codes | p. 91 |
4.1 Polynomials and words | p. 91 |
4.2 Introduction to cyclic codes | p. 96 |
4.3 Generating and parity check matrices for cyclic codes | p. 101 |
4.4 Finding cyclic codes | p. 104 |
4.5 Dual cyclic codes | p. 109 |
5 BCH Codes | p. 111 |
5.1 Finite fields | p. 111 |
5.2 Minimal polynomials | p. 115 |
5.3 Cyclic Hamming codes | p. 118 |
5.4 BCH codes | p. 120 |
5.5 Decoding 2 error-correcting BCH code | p. 122 |
6 Reed-Solomon Codes | p. 127 |
6.1 Codes over GF(2[superscript r]) | p. 127 |
6.2 Reed-Solomon codes | p. 129 |
6.3 Decoding Reed-Solomon codes | p. 135 |
6.4 Transform approach to Reed-Solomon codes | p. 141 |
6.5 Berlekamp-Massey algorithm | p. 148 |
6.6 Erasures | p. 153 |
7 Burst Error-Correcting Codes | p. 159 |
7.1 Introduction | p. 159 |
7.2 Interleaving | p. 163 |
7.3 Application to compact discs | p. 170 |
8 Convolutional Codes | p. 173 |
8.1 Shift registers and polynomials | p. 173 |
8.2 Encoding convolutional codes | p. 179 |
8.3 Decoding convolutional codes | p. 186 |
8.4 Truncated Viterbi decoding | p. 193 |
9 Reed-Muller and Preparata Codes | p. 205 |
9.1 Reed-Muller codes | p. 205 |
9.2 Decoding Reed-Muller codes | p. 208 |
9.3 Extended Preparata codes | p. 213 |
9.4 Encoding extended Preparata codes | p. 219 |
9.5 Decoding extended Preparata codes | p. 222 |
Part II Cryptography | |
10 Classical Cryptography | p. 227 |
10.1 Encryption schemes | p. 228 |
10.2 Symmetric-key encryption | p. 230 |
10.3 Feistel ciphers and DES | p. 238 |
10.3.1 The New Data Seal | p. 240 |
10.3.2 The Data Encryption Standard | p. 243 |
10.4 Notes | p. 249 |
11 Topics in Algebra and Number Theory | p. 253 |
11.1 Algorithms, complexity, and modular arithmetic | p. 253 |
11.2 Quadratic residues | p. 260 |
11.3 Primality testing | p. 264 |
11.4 Factoring and square roots | p. 267 |
11.4.1 Pollard's rho | p. 267 |
11.4.2 Random squares | p. 269 |
11.4.3 Square roots | p. 271 |
11.5 Discrete logarithms | p. 274 |
11.5.1 Baby-step giant-step | p. 274 |
11.5.2 Index calculus | p. 275 |
11.6 Notes | p. 277 |
12 Public-key Cryptography | p. 279 |
12.1 One-way and hash functions | p. 280 |
12.2 RSA | p. 284 |
12.3 Provable security | p. 290 |
12.4 ElGamal | p. 293 |
12.5 Cryptographic protocols | p. 297 |
12.5.1 Diffie-Hellman key agreement | p. 298 |
12.5.2 Zero-knowledge proofs | p. 299 |
12.5.3 Coin-tossing and mental poker | p. 301 |
12.6 Notes | p. 305 |
A The Euclidean Algorithm | p. 307 |
B Factorization of 1 + x[superscript n] | p. 311 |
C Example of Compact Disc Encoding | p. 313 |
D Solutions to Selected Exercises | p. 317 |
Bibliography | p. 335 |
Index | p. 343 |