信息论、编码与密码学（英文版）

.problems 44
computer problems 46
2. channel capacity and coding 47
2.1 introduction 47
2.2 channel models 48
2.3 channel capacity 50
2.4 channel coding 52
2.5 information capacity theorem 56
2.6 the shannon limit 59
2.7 random selection of codes 61
2.8 concluding remarks 67
summary 68
problems 69
computer problems 71
part ii
error control coding
(channel coding)
3. linear block codes for error correction 75
3.1 introduction to error correcting codes 75
3.2 basic definitions 77
3.3 matrix description of linear block codes 81
3.4 equivalent codes 82
3.5 parity check matrix 85
3.6 decoding of a linear block code 87
3.7 syndrome decoding 94
3.8 error probability after coding (probability of error correction) 95
3.9 perfect codes 97
3.10 hamming codes 100
3.11 optimal linear codes 102
3.12 maximum distance separable (mds) codes 102
3.13 concluding remarks 102
summary 103
problems 105
computer problems 106
4. cyclic codes 108
4.1 introduction to cyclic codes 108
4.2 polynomials 109
4.3 the division algorithm for polynomials 110
4.4 a method for generating cyclic codes 115
4.5 matrix description of cyclic codes 119
4.6 burst error correction 121
4.7 fire codes 123
4.8 golay codes 124
4.9 cyclic redundancy check (crc) codes 125
4.10 circuit implementation of cyclic codes 128
4.11 concluding remarks 132
summary 132
problems 134
computer problems 135
5. bose-chaudhuri hocquenghem (bch) codes
5.1 introduction to bch codes 136
5.2 primitive elements 137
5.3 minimal polynomials 133
5.4 generator polynomials in terms of minimal polynomials 141
5.5 some examples of bch codes 143
5.6 decoding of bch codes 147
5.7 reed-solomon codes 150
5.8 implementation of reed-solomon encoders and decoders 153
5.9 nested codes 153
5.10 concluding remarks 155
summary 156
problems 157
computer problems 158
6. convolutional codes
6.1 introduction to convolutional codes 159
6.2 tree codes and trellis codes 160
6.3 polynomial description of convolutional codes
(analytical representation) 165
6.4 distance notions for convolutional codes 170
6.5 the generating function 173
6.6 matrix description of convolutional codes 776
6.7 viterbi decoding of convolutional codes 178
6.8 distance bounds for convolutional codes 185
6.9 performance bounds 187
6.10 known good convolutional codes 188
6.11 turbo codes 190
6.12 turbo decoding 192
6.13 concluding remarks 198
summary 199
problems 201
computer problems 203
7. trellis coded modulation 206
7.1 introduction to tcm 206
7.2 the concept of coded modulation 207
7.3 mapping by set partitioning 212
7.4 ungerboeck's tcm design rules 216
7.5 tcm decoder 220
7.6 performance evaluation for awgn channel 221
7.7 computation of dfree 227
7.8 tcm for fading channels 228
7.9 concluding remarks 232
summary 233
problems 234
computer problems 238
part iii
coding for secure communications
8. cryptography 241
8.1 introduction to cryptography 241
8.2 an overview of encryption techniques 242
8.3 operations used by encryption algorithms 245
8.4 symmetric (secret key) cryptography 246
8.5 data encryption standard (des) 248
8.6 international data encryption algorithm (idea) 252
8.7 rc ciphers 253
8.8 asymmetric (public-key) algorithms 254
8.9 the rsa algorithm 254
8.10 pretty good privacy (pgp) 256
8.11 one-way hashing 253
8.12 other techniques 260
8.13 secure communication using chaos functions 261
8.14 cryptanalysis 262
8.15 politics of cryptography 264
8.16 concluding remarks 265
summary 268
problems 269
computer problems 271
index 273

.　　optimal linear codes and maximum distance separable (MDS) codes are also introduced.
　　 Chapter 4 deals with cyclic codes, a sub-class of linear block codes. Cyclic codes are particularly useful for burst error correction. Fire codes, Golay codes and Cyclic Redundancy Check (CRC) codes are discussed as specific examples of cyclic codes. The chapter concludes with a section on the circuit implementation of cyclic codes.
　　 Chapter 5 takes the reader to the world of Bose-Chaudhuri Hocquenghem (BCH) codes, a very
　　powerful class of multiple error correcting codes. The Reed-Solomon codes, a sub-class of BCH
　　codes, is also discussed in this chapter.
　　 Chapter 6 takes a look at convolutional codes, which are essentially codes with memory. The
　　concept of Trellis codes is introduced to the reader and the Viterbi decoding technique is
　　discussed in detail. Some known good convolutional codes are also studied. Finally, the reader
　　is given a flavor of the not-so-old Turbo codes.
　　 Chapter 7 on Trellis Coded Modulation (TCM) talks about the combined coding and
　　modulation schemes. TCM encoding and decoding are discussed. The reader also learns how
　　to design TCM schemes for additive white Gaussian noise channels as well as fading channels.
　　Part III contains a chapter on Cryptography--Chapter 8 looks at yet another application of
　　coding, i.e. secure communications. The chapter discusses both the secret key and public key
　　encryption techniques using specific examples. Other techniques such as one-way hashing and
　　encryption using chaos functions are also discussed. The chapter concludes with a note on the
　　politics of cryptography.
　　 I have tried to include numerical examples as and when required. Each chapter ends with a
　　concluding remark, which contains brief historical notes describing the origins of the important
　　results and contributions. Also, there is a telegraphic summary at the end of each chapter, which
　　can be used as a ready reference, or a quick search mechanism for a particular formula or
　　definition, or simply a confidence builder prior to an exam. The end of the chapter problems
　　should help the enthusiastic reader crystallize the concepts discussed in the text. I have also
　　added computer-based exercises at the end of each chapter. It is recommended that these
　　computer problems should be made a part of learning this subject.
　　 I have tried my best to free the book from all errors. Unfortunately there does not exist a
　　foolproof error control technique for that! I have tried to include all the important, practical and interesting concepts related to this area. Comments from the readers regarding errors, omissions and other constructive suggestions are welcome at rbose@ee.iitd.ac.in Finally, I would like to quote Blaise Pascal, who said, "The last thing one knows when writing a book is what to put firsf .
　　 RANJAN Bose
　　 New Delhi