Coding for data and computer communications

Contents......Page 9
Preface......Page 6
Part I: Channel Coding......Page 14
1.1 Information Theory and Algebraic Coding......Page 16
1.2 Error Control Codes......Page 17
1.3 Voting Codes......Page 19
1.4 Check Bits......Page 22
1.5 Parity Bits......Page 23
1.6 Hamming Distance......Page 24
1.7 Error-Correcting Codes......Page 26
1.8 Hamming Codes......Page 27
1.9 The SEC-DED Code......Page 29
1.10 Periodic Codes......Page 31
1.11 Compact Disc Error Control......Page 32
1.12 CD Description......Page 33
1.13 CD Data Encoding......Page 35
1.14 Reed–Solomon Codes......Page 37
1.15 Generating Polynomials......Page 42
1.16 Codes and Geometry......Page 44
2 Check Digits for Error Detection......Page 48
2.1 ISBN......Page 50
2.2 Barcodes......Page 52
2.3 Zip Barcodes......Page 57
2.4 Postal Money Orders......Page 59
2.5 Airline Tickets......Page 60
2.6 Banking......Page 61
2.7 Credit Cards......Page 62
2.8 The IBM Check Digit......Page 63
2.9 Two Or More Check Digits......Page 65
2.10 Hamming Check Digits......Page 66
2.11 The Verhoeff Check Digit Method......Page 69
Part II: Source Codes......Page 72
3 Statistical Methods......Page 79
3.2 Entropy......Page 80
3.3 Variable-Size Codes......Page 81
3.4 Decoding......Page 85
3.5 Huffman Coding......Page 86
3.6 Adaptive Huffman Coding......Page 93
3.7 Facsimile Compression......Page 100
3.8 Arithmetic Coding......Page 107
3.9 Adaptive Arithmetic Coding......Page 119
4 Dictionary Methods......Page 123
4.1 LZ77 (Sliding Window)......Page 125
4.2 LZSS......Page 128
4.3 LZ78......Page 131
4.4 LZW......Page 134
4.5 Summary......Page 144
5 Image Compression......Page 145
5.1 Introduction......Page 146
5.2 Image Types......Page 150
5.3 Approaches to Image Compression......Page 151
5.4 Intuitive Methods......Page 157
5.5 Image Transforms......Page 158
5.6 Orthogonal Transforms......Page 163
5.7 Subband Transforms......Page 175
5.8 Progressive Image Compression......Page 184
5.9 JPEG......Page 190
Part III: Secure Codes......Page 209
6 Basic Concepts......Page 211
6.1 The Caesar Cipher......Page 215
6.2 The Affine Cipher......Page 216
6.3 The One-Time Pad......Page 218
6.4 Kerckhoffs\' Principle......Page 220
7 Monoalphabetic Substitution Ciphers......Page 224
7.1 Letter Distributions......Page 225
7.2 The Pigpen Cipher......Page 227
7.3 Polybius\' Monoalphabetic Cipher......Page 228
7.5 The Playfair Cipher......Page 229
7.6 The Double Playfair Cipher......Page 231
7.7 Delastelle Fractionation......Page 232
7.8 Ohaver Encryption: Fractionated Morse......Page 233
7.9 Delastelle Trifid Fractionation......Page 234
7.10 Homophonic Substitution Ciphers......Page 235
8 Transposition Ciphers......Page 238
8.1 Simple Examples......Page 239
8.2 Cyclic Notation and Keys......Page 243
8.3 Transposition by Turning Template......Page 244
8.4 Columnar Transposition Cipher......Page 246
8.5 Double Transposition......Page 248
8.6 A 2-Step ADFGVX Cipher......Page 250
8.7 Conclusions......Page 251
9 Polyalphabetic Substitution Ciphers......Page 254
9.2 The Porta Polyalphabetic Cipher......Page 255
9.3 The Beaufort Cipher......Page 257
9.4 The Trithemius Cipher......Page 258
9.5 The Vigenère Cipher......Page 260
9.6 A Variation on Vigenère......Page 261
9.7 The Gronsfeld Cipher......Page 262
9.8 Generating Permutations......Page 263
9.9 The Eyraud Cipher......Page 265
9.10 The Hill Cipher......Page 267
9.11 The Jefferson Multiplex Cipher......Page 269
9.12 Strip Ciphers......Page 271
9.13 Polyphonic Ciphers and Ambiguity......Page 273
9.14 Polybius\' Polyalphabetic Cipher......Page 274
9.15 The Index of Coincidence......Page 275
10 Stream Ciphers......Page 279
10.1 Symmetric Key and Public Key......Page 281
10.2 Stream Ciphers......Page 282
10.3 Linear Shift Registers......Page 284
10.4 Nonlinear Shift Registers......Page 287
10.6 Dynamic Substitution......Page 291
10.7 The Latin Square Combiner......Page 293
10.8 SEAL Stream Cipher......Page 294
11 Block Ciphers......Page 298
11.1 Substitution–Permutation Ciphers......Page 299
11.2 Lucifer......Page 304
11.3 The Data Encryption Standard......Page 305
12 Public-Key Cryptography......Page 319
12.1 Diffie–Hellman–Merkle Keys......Page 320
12.2 Public-Key Cryptography......Page 322
12.3 RSA Cryptography......Page 323
12.4 Pretty Good Privacy......Page 327
12.5 Sharing Secrets: Threshold Schemes......Page 328
12.6 The Four Components......Page 334
12.7 Authentication......Page 336
12.8 SSL: Secure Socket Layer......Page 340
12.9 MD5 Hashing......Page 345
13 Data Hiding......Page 349
13.1 Basic Features......Page 351
13.2 Applications of Data Hiding......Page 354
13.4 Intuitive Methods......Page 356
13.5 Simple Digital Methods......Page 359
13.6 Data Hiding in Text......Page 360
13.7 Innocuous Text......Page 362
13.8 Mimic Functions......Page 366
14.1 LSB Encoding......Page 372
14.2 BPCS Steganography......Page 382
14.3 Lossless Data Hiding......Page 387
14.4 Data Hiding by Quantization......Page 391
14.5 Patchwork......Page 392
14.7 Robust Data Hiding in JPEG Images......Page 394
14.8 Robust Frequency Domain Watermarking......Page 400
14.9 Detecting Malicious Tampering......Page 403
14.10 Robust Wavelet-Based Watermarking......Page 405
14.11 Kundur–Hatzinakos Watermarking: I......Page 407
14.12 Kundur–Hatzinakos Watermarking: II......Page 409
14.14 The Zhao–Koch Method......Page 411
14.15 The Wu–Lee Method......Page 414
14.16 The CPT Method......Page 415
14.17 The TP Method......Page 418
14.18 Data Hiding in Fax Images......Page 422
15.1 Protecting Music Scores......Page 423
15.2 Data Hiding in MPEG-2 Video......Page 425
15.3 Digital Audio......Page 428
15.4 The Human Auditory System......Page 431
15.5 Audio Watermarking in the Time Domain......Page 435
15.6 Echo Hiding......Page 437
15.7 The Steganographic File System......Page 440
15.8 Ultimate Steganography?......Page 445
15.10 Current Software......Page 446
Part IV: Essential Resources......Page 450
A: Symmetry Groups......Page 451
B: Galois Fields......Page 455
C: Cyclic Redundancy Codes......Page 465
D: Projects......Page 468
Answers to Exercises......Page 473
A......Page 505
B......Page 506
C......Page 508
D......Page 511
E......Page 512
G......Page 513
H......Page 514
J......Page 515
L......Page 516
M......Page 517
P......Page 518
S......Page 520
U......Page 522
X......Page 523
Z......Page 524
Bibliography......Page 525
A......Page 535
C......Page 536
D......Page 539
F......Page 540
I......Page 541
K......Page 542
M......Page 543
P......Page 544
S......Page 546
T......Page 548
W......Page 549
Z......Page 550