Information theory coding and cryptography

✍ Scribed by Mandal, Surajit; Manna, Nilotpal; Saha, Arjit

• Publisher: Pearson Education India; Dorling Kindersley (India)
• Year: 2013
• Tongue: English
• Leaves: 280
• Series: Always learning
• Category: Library

✦ Synopsis

"Information Theory, Coding & Cryptography" has been designed as a comprehensive text for the students of engineering discussing Source Encoding, Error Control Codes & Cryptography. The book contains the recent developments of coded modulation, trellises for codes, turbo coding for reliable data and interleaving. The text balances the mathematical rigor with exhaustive amount of solved, unsolved questions along with a database of MCQ's.

✦ Table of Contents

Cover......Page 1
Contents......Page 4
Foreword......Page 10
Preface......Page 12
Part A: Information Theory and Source Coding......Page 14
1.2 Fundamentals of Probability......Page 16
1.2.2 Axioms of Probability......Page 17
1.2.3 Elementary Theorems on Probability......Page 18
1.2.4 Conditional Probability......Page 19
1.2.5 Independent Events......Page 20
1.2.6 Total Probability......Page 21
1.3 Random Variables and Its Characteristics......Page 22
1.3.1 Discrete Random Variable and Probability Mass Function......Page 23
1.3.3 Distribution Function for Discrete Random Variable......Page 24
1.4 Statistical Averages......Page 25
1.5.2 Poisson Distribution......Page 26
1.6 Random Processes......Page 27
1.7.1 Sources of Noise......Page 28
1.7.3 Shot Noise......Page 29
1.8 Solved Problems......Page 30
Multiple Choice Questions......Page 32
Review Questions......Page 33
2.1 Introduction......Page 35
2.2 Measure of Information......Page 36
2.3 Entropy......Page 37
2.4 Information Rate......Page 40
2.5.1 Discrete Memoryless Channel......Page 41
2.5.2 Special Channels......Page 42
2.6 Joint Entropy and Conditional Entropy......Page 45
2.7 Mutual Information......Page 49
2.8.1 Special Channels......Page 51
2.10 Continuous Channel......Page 52
2.10.3 Shannon–Hartley Law......Page 53
2.11 Solved Problems......Page 56
Multiple Choice Questions......Page 59
Review Questions......Page 60
3.2 Coding Parameters......Page 62
3.3 Source Coding Theorem......Page 63
3.4 Classification of Codes......Page 64
3.5 Kraft Inequality......Page 67
3.6 Image Compression......Page 68
3.7 Speech and Audio Coding......Page 69
3.8 Shannon–Fano Coding......Page 71
3.9 Human Coding......Page 72
3.10 Arithmetic Coding......Page 73
3.11 Lempel–Ziv–Welch Coding......Page 74
3.12 Run-length Encoding......Page 76
3.14.1 The Masking Phenomenon......Page 77
3.14.2 Temporal Masking......Page 78
3.14.3 Perceptual Coding in MPEG Audio......Page 79
3.16 Linear Predictive Coding Model......Page 80
3.17 Solved Problems......Page 82
Multiple Choice Questions......Page 84
Review Questions......Page 85
Part B: Error Control Coding......Page 88
4.1 Introduction......Page 90
4.2.1 Code Rate......Page 91
4.4 Error Control Strategies......Page 92
4.4.1 Throughput Efficiency of ARQ......Page 93
4.5.1 Modular Arithmetic......Page 95
4.5.3 Groups......Page 98
4.5.4 Fields......Page 101
4.5.5 Arithmetic of Binary Field......Page 105
4.5.6 Roots of Equations......Page 107
4.5.7 Galois Field......Page 108
4.6 Vector Spaces......Page 111
4.6.2 Linear Combination......Page 113
4.6.4 Dimension......Page 114
4.6.6 Dual Space......Page 116
4.7.1 Row Space......Page 117
4.8 Solved Problems......Page 119
Multiple Choice Questions......Page 120
Review Questions......Page 121
5.2 Generator Matrices......Page 123
5.3 Parity-Check Matrices......Page 126
5.3.1 Dual Code......Page 127
5.4.1 Undetectable Error Pattern......Page 129
5.5 Error Detection......Page 131
5.6 Minimum Distance......Page 132
5.7 Error-detecting Capability......Page 133
5.9 Standard Array and Syndrome Decoding......Page 134
5.9.1 Coset and Coset Leader......Page 135
5.10 Probability of Undetected Errors Over a BSC......Page 136
5.11 Hamming Code......Page 138
5.12 Solved Problems......Page 139
Multiple Choice Questions......Page 144
Review Questions......Page 145
6.2 Generation......Page 149
6.2.1 Generation and Parity-check Matrices......Page 154
6.2.2 Realization of Cyclic Code......Page 156
6.3 Syndrome Computation and Error Detection......Page 159
6.4 Decoding......Page 161
6.5 Cyclic Hamming Code......Page 166
6.6 Shortened Cyclic Code......Page 167
6.8 Error-trapping Decoding......Page 168
6.8.1 Improved Error-trapping......Page 171
6.9 Majority Logic Decoding......Page 172
6.10 Cyclic Redundancy Check......Page 174
6.11 Solved Problems......Page 175
Multiple Choice Questions......Page 177
Review Questions......Page 178
7.3 Minimal Polynomials......Page 179
7.4 Generator Polynomials......Page 180
7.5 Decoding of BCH Codes......Page 182
7.6 Implementation of Galois Field......Page 185
7.7.2 Computation of Error Location Polynomial......Page 187
7.8.1 Reed–Solomon Code......Page 189
7.9 Weight Distribution......Page 192
7.10 Solved Problems......Page 193
Multiple Choice Questions......Page 196
Review Questions......Page 197
8.2 Tree and Trellis Codes......Page 198
8.3 Encoding......Page 200
8.4 Properties......Page 203
8.4.1 Structural Properties......Page 204
8.4.2 Distance Properties......Page 207
8.5.1 Threshold Decoding......Page 208
8.5.2 Sequential Decoding......Page 213
8.5.3 Viterbi Decoding......Page 218
8.6 Construction......Page 225
8.7 Implementation and Modification......Page 226
8.9 Turbo Coding and Decoding......Page 228
8.10 Interleaving Techniques: Block and Convolution......Page 232
8.11 Coding and Interleaving Applied to CD Digital Audio System......Page 236
8.11.1 CIRC Encoding and Decoding......Page 237
8.12 Solved Problems......Page 239
Multiple Choice Questions......Page 240
Review Questions......Page 241
Part C: Cryptography......Page 242
9.2 Plain Text, Cipher Text, and Key......Page 244
9.3 Substitution and Transposition......Page 245
9.4 Encryption and Decryption......Page 248
9.5 Symmetric-key Cryptography......Page 249
9.6 Data Encryption Standard......Page 250
9.6.2 Initial Permutation......Page 251
9.6.3 Details of Single Round......Page 252
9.7 Advance Versions of DES......Page 256
9.7.1 Double DES......Page 257
9.7.2 Triple DES......Page 258
9.8.1 Public and Private Key......Page 259
9.9.1 Example of RSA......Page 260
9.9.2 Strength of RSA......Page 261
9.11.1 The Algorithm......Page 262
9.13 Quantum Cryptography......Page 263
9.14 Solved Problems......Page 265
Multiple Choice Questions......Page 267
Review Questions......Page 268
A.1 Fermat's Little Theorem......Page 270
A.2 Chinese Remainder Theorem......Page 271
A.3 Prime Number Generation......Page 273
A.3.1 Sieve of Eratosthenes......Page 274
Bibliography......Page 276
Index......Page 278