Table of Contents for

Information Theory, Coding and Cryptography

Contents

Foreword

Preface

PART A INFORMATION THEORY AND SOURCE CODING

1. Probability, Random Processes, and Noise

1.1 Introduction

1.2 Fundamentals of Probability

1.2.1 Algebra of Probability

1.2.2 Axioms of Probability

1.2.3 Elementary Theorems on Probability

1.2.4 Conditional Probability

1.2.5 Independent Events

1.2.6 Total Probability

1.3 Random Variables and Its Characteristics

1.3.1 Discrete Random Variable and Probability Mass Function

1.3.2 Cumulative Distribution Function

1.3.3 Distribution Function for Discrete Random Variable

1.3.4 Continuous Random Variable and Probability Density Function

1.4 Statistical Averages

1.5 Frequently Used Probability Distributions

1.5.1 Binomial Distribution

1.5.2 Poisson Distribution

1.5.3 Gaussian Distribution

1.6 Random Processes

1.7 Noise

1.7.1 Sources of Noise

1.7.2 Thermal Noise

1.7.3 Shot Noise

1.7.4 Partition Noise

1.7.5 Flicker Noise or 1/f Noise

1.8 Solved Problems

Multiple Choice Questions

Review Questions

2. Information Theory

2.1 Introduction

2.2 Measure of Information

2.3 Entropy

2.4 Information Rate

2.5 Channel Model

2.5.1 Discrete Memoryless Channel

2.5.2 Special Channels

2.6 Joint Entropy and Conditional Entropy

2.7 Mutual Information

2.8 Channel Capacity

2.8.1 Special Channels

2.9 Shannon’s Theorem

2.10 Continuous Channel

2.10.1 Differential Entropy

2.10.2 Additive White Gaussian Noise Channel

2.10.3 Shannon–Hartley Law

2.11 Solved Problems

Multiple Choice Questions

Review Questions

3. Source Codes

3.1 Introduction

3.2 Coding Parameters

3.3 Source Coding Theorem

3.4 Classification of Codes

3.5 Kraft Inequality

3.6 Image Compression

3.6.1 Image Formats, Containers, and Compression Standards

3.7 Speech and Audio Coding

3.8 Shannon–Fano Coding

3.9 Huffman Coding

3.10 Arithmetic Coding

3.11 Lempel–Ziv–Welch Coding

3.12 Run-length Encoding

3.13 MPEG Audio and Video Coding Standards

3.14 Psychoacoustic Model of Human Hearing

3.14.1 The Masking Phenomenon

3.14.2 Temporal Masking

3.14.3 Perceptual Coding in MPEG Audio

3.15 Dolby

3.16 Linear Predictive Coding Model

3.17 Solved Problems

Multiple Choice Questions

Review Questions

PART B ERROR CONTROL CODING

4. Coding Theory

4.1 Introduction

4.2 Types of Codes

4.2.1 Code Rate

4.3 Types of Errors

4.4 Error Control Strategies

4.4.1 Throughput Efficiency of ARQ

4.5 Mathematical Fundamentals

4.5.1 Modular Arithmetic

4.5.2 Sets

4.5.3 Groups

4.5.4 Fields

4.5.5 Arithmetic of Binary Field

4.5.6 Roots of Equations

4.5.7 Galois Field

4.6 Vector Spaces

4.6.1 Subspace

4.6.2 Linear Combination

4.6.3 Basis (or Base)

4.6.4 Dimension

4.6.5 Orthogonality

4.6.6 Dual Space

4.7 Matrices

4.7.1 Row Space

4.8 Solved Problems

Multiple Choice Questions

Review Questions

5. Linear Block Codes

5.1 Introduction

5.2 Generator Matrices

5.3 Parity-check Matrices

5.3.1 Dual Code

5.4 Error Syndrome

5.4.1 Undetectable Error Pattern

5.5 Error Detection

5.6 Minimum Distance

5.7 Error-detecting Capability

5.8 Error-correcting Capability

5.9 Standard Array and Syndrome Decoding

5.9.1 Coset and Coset Leader

5.10 Probability of Undetected Errors Over a BSC

5.11 Hamming Code

5.12 Solved Problems

Multiple Choice Questions

Review Questions

6. Cyclic Codes

6.1 Introduction

6.2 Generation

6.2.1 Generation and Parity-check Matrices

6.2.2 Realization of Cyclic Code

6.3 Syndrome Computation and Error Detection

6.4 Decoding

6.5 Cyclic Hamming Code

6.6 Shortened Cyclic Code

6.7 Golay Code

6.8 Error-trapping Decoding

6.8.1 Improved Error-trapping

6.9 Majority Logic Decoding

6.10 Cyclic Redundancy Check

6.11 Solved Problems

Multiple Choice Questions

Review Questions

7. BCH Codes

7.1 Introduction

7.2 Primitive Elements

7.3 Minimal Polynomials

7.4 Generator Polynomials

7.5 Decoding of BCH Codes

7.6 Implementation of Galois Field

7.7 Implementation of Error Correction

7.7.1 Syndrome Computation

7.7.2 Computation of Error Location Polynomial

7.8 Nonbinary BCH Codes

7.8.1 Reed–Solomon Code

7.9 Weight Distribution

7.10 Solved Problems

Multiple Choice Questions

Review Questions

8. Convolution Codes

8.1 Introduction

8.2 Tree and Trellis Codes

8.3 Encoding

8.4 Properties

8.4.1 Structural Properties

8.4.2 Distance Properties

8.5 Decoding

8.5.1 Threshold Decoding

8.5.2 Sequential Decoding

8.5.3 Viterbi Decoding

8.6 Construction

8.7 Implementation and Modification

8.8 Applications

8.9 Turbo Coding and Decoding

8.10 Interleaving Techniques: Block and Convolution

8.11 Coding and Interleaving Applied to CD Digital Audio System

8.11.1 CIRC Encoding and Decoding

8.11.2 Interpolation and Muting

8.12 Solved Problems

Multiple Choice Questions

Review Questions

PART C CRYPTOGRAPHY

9. Cryptography

9.1 Introduction

9.2 Plain Text, Cipher Text, and Key

9.3 Substitution and Transposition

9.4 Encryption and Decryption

9.5 Symmetric-key Cryptography

9.5.1 Stream Ciphers and Block Ciphers

9.6 Data Encryption Standard

9.6.1 Basic Principle

9.6.2 Initial Permutation

9.6.3 Details of Single Round

9.6.4 Inverse Initial Permutation

9.6.5 DES Decryption

9.6.6 Strength of DES

9.7 Advance Versions of DES

9.7.1 Double DES

9.7.2 Triple DES

9.8 Asymmetric-key Cryptography

9.8.1 Public and Private Key

9.9 RSA Algorithm

9.9.1 Example of RSA

9.9.2 Strength of RSA

9.10 Symmetric versus Asymmetric-key Cryptography

9.11 Diffie–Hellman Key Exchange

9.11.1 The Algorithm

9.12 Steganography

9.13 Quantum Cryptography

9.14 Solved Problems

Multiple Choice Questions

Review Questions

Appendix A Some Related Mathematics

A.1 Fermat’s Little Theorem

A.2 Chinese Remainder Theorem

A.3 Prime Number Generation

A.3.1 Sieve of Eratosthenes

Bibliography