Cover image for Coding theory and cryptography : the essentials
Title:
Coding theory and cryptography : the essentials
Series:
Monographs and textbooks in pure and applied mathematics ; 234
Edition:
2nd ed., rev. and expanded
Publication Information:
New York : Marcel Dekker, 2000
ISBN:
9780824704650
Added Author:

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

Prefacep. v
Part I Coding Theory
1 Introduction to Coding Theoryp. 1
1.1 Introductionp. 1
1.2 Basic assumptionsp. 2
1.3 Correcting and detecting error patternsp. 4
1.4 Information ratep. 6
1.5 The effects of error correction and detectionp. 7
1.6 Finding the most likely codeword transmittedp. 8
1.7 Some basic algebrap. 10
1.8 Weight and distancep. 11
1.9 Maximum likelihood decodingp. 12
1.10 Reliability of MLDp. 16
1.11 Error-detecting codesp. 18
1.12 Error-correcting codesp. 22
2 Linear Codesp. 27
2.1 Linear codesp. 27
2.2 Two important subspacesp. 28
2.3 Independence, basis, dimensionp. 30
2.4 Matricesp. 35
2.5 Bases for C = [S] and C[superscript perpendicular, bottom]p. 37
2.6 Generating matrices and encodingp. 41
2.7 Parity-check matricesp. 45
2.8 Equivalent codesp. 48
2.9 Distance of a linear codep. 52
2.10 Cosetsp. 53
2.11 MLD for linear codesp. 57
2.12 Reliability of IMLD for linear codesp. 62
3 Perfect and Related Codesp. 65
3.1 Some bounds for codesp. 65
3.2 Perfect codesp. 70
3.3 Hamming codesp. 72
3.4 Extended codesp. 75
3.5 The extended Golay codep. 77
3.6 Decoding the extended Golay codep. 79
3.7 The Golay codep. 82
3.8 Reed-Muller codesp. 84
3.9 Fast decoding for RM(1, m)p. 88
4 Cyclic Linear Codesp. 91
4.1 Polynomials and wordsp. 91
4.2 Introduction to cyclic codesp. 96
4.3 Generating and parity check matrices for cyclic codesp. 101
4.4 Finding cyclic codesp. 104
4.5 Dual cyclic codesp. 109
5 BCH Codesp. 111
5.1 Finite fieldsp. 111
5.2 Minimal polynomialsp. 115
5.3 Cyclic Hamming codesp. 118
5.4 BCH codesp. 120
5.5 Decoding 2 error-correcting BCH codep. 122
6 Reed-Solomon Codesp. 127
6.1 Codes over GF(2[superscript r])p. 127
6.2 Reed-Solomon codesp. 129
6.3 Decoding Reed-Solomon codesp. 135
6.4 Transform approach to Reed-Solomon codesp. 141
6.5 Berlekamp-Massey algorithmp. 148
6.6 Erasuresp. 153
7 Burst Error-Correcting Codesp. 159
7.1 Introductionp. 159
7.2 Interleavingp. 163
7.3 Application to compact discsp. 170
8 Convolutional Codesp. 173
8.1 Shift registers and polynomialsp. 173
8.2 Encoding convolutional codesp. 179
8.3 Decoding convolutional codesp. 186
8.4 Truncated Viterbi decodingp. 193
9 Reed-Muller and Preparata Codesp. 205
9.1 Reed-Muller codesp. 205
9.2 Decoding Reed-Muller codesp. 208
9.3 Extended Preparata codesp. 213
9.4 Encoding extended Preparata codesp. 219
9.5 Decoding extended Preparata codesp. 222
Part II Cryptography
10 Classical Cryptographyp. 227
10.1 Encryption schemesp. 228
10.2 Symmetric-key encryptionp. 230
10.3 Feistel ciphers and DESp. 238
10.3.1 The New Data Sealp. 240
10.3.2 The Data Encryption Standardp. 243
10.4 Notesp. 249
11 Topics in Algebra and Number Theoryp. 253
11.1 Algorithms, complexity, and modular arithmeticp. 253
11.2 Quadratic residuesp. 260
11.3 Primality testingp. 264
11.4 Factoring and square rootsp. 267
11.4.1 Pollard's rhop. 267
11.4.2 Random squaresp. 269
11.4.3 Square rootsp. 271
11.5 Discrete logarithmsp. 274
11.5.1 Baby-step giant-stepp. 274
11.5.2 Index calculusp. 275
11.6 Notesp. 277
12 Public-key Cryptographyp. 279
12.1 One-way and hash functionsp. 280
12.2 RSAp. 284
12.3 Provable securityp. 290
12.4 ElGamalp. 293
12.5 Cryptographic protocolsp. 297
12.5.1 Diffie-Hellman key agreementp. 298
12.5.2 Zero-knowledge proofsp. 299
12.5.3 Coin-tossing and mental pokerp. 301
12.6 Notesp. 305
A The Euclidean Algorithmp. 307
B Factorization of 1 + x[superscript n]p. 311
C Example of Compact Disc Encodingp. 313
D Solutions to Selected Exercisesp. 317
Bibliographyp. 335
Indexp. 343