Information Theory and Coding

Description

The book provides a comprehensive treatment of Information Theory and Coding as required for understanding and appreciating the basic concepts. It starts with the mathematical prerequisites and then uncovers major topics by way of different chapters on Information Theory, Source Coding, Communication Channels, Error Control Codes, Burst Errors, Convolution Codes and also a brief chapter on Cryptography. The book emphasizes on theoretical concepts and problem solving. The book is intended for undergraduate and postgraduate students of Electronics and Communication Engineering, Computer Science and Engineering, Information Technology and Telecommunication Engineering.

About the Author

Muralidhar Kulkarni is currently Professor in the Department of Electronics and Communication Engineering (ECE)

Table of Contents

Preface

1 Mathematical Prerequisite

1.1 Introduction

1.2 Groups

1.3 Rings

1.4 Field

1.5 Quotient Ring

1.6 Vector Space

1.7 Introduction to Probability Theory

1.8 Random Variables

1.9 Statistical Averages

1.10 Frequently Encountered Density Functions

1.11 Random Processes

1.12 Joint CDF

1.13 Joint PDF

1.14 Autocorrelation Function

2 Information Theory

2.1 Introduction

2.2 Measure of Information

2.3 Average Information Content (Entropy) of a Zero Memory Source

2.4 Extension of Zero Memory Source

2.5 Entropy of a Source with Memory

3 Source Coding

3.1 Introduction

3.2 Types of Codes

3.3 Prefix Codes

3.4 Source Coding Theorem

3.5 Shannon’s First Encoding Theorem

3.6 Shannon-Fano Encoding Algorithm

3.7 Huffman Code (Compact Codes)

3.8 Extended Huffman Coding

3.9 Arithmetic Coding

3.10 Lempel-Ziv Algorithm

3.11 Run Length Encoding

3.12 An Overview on Image Compression

3.13 Introduction to Speech Compression

4 Information Channels

4.1 Introduction

4.2 Channel Models

4.3 System Entropies

4.4 Mutual Information (Trans information)

4.5 Channel Capacity

4.6 Capacity of Channels

4.7 Continuous Channels

5 Error Control Coding

5.1 Introduction

5.2 Need for Error Control Coding

5.3 Types of Codes

5.4 Coding Gain

5.5 Linear Block Codes

5.6 The Hamming Codes

5.7 Probability of an Undetected Error Pattern for an LBC over a BSC

5.8 Equivalent Codes

5.9 Cyclic Codes

5.10 Golay Codes

5.11 Shortened Cyclic Codes

6 Burst Error Correcting Codes

6.1 Introduction

6.2 Burst Errors

6.3 Interleaved Codes

6.4 Product Codes

6.5 Fire Codes

6.6 BCH Codes

6.7 Non-Binary BCH Codes and Reed-Solomon Codes

7 Convolution Codes

7.1 Introduction

7.2 Convolution Encoder

7.3 Representation of Convolution Code

7.4 Transfer Function of a Convolution Code

7.5 Distance Properties of Convolution Codes

7.6 Decoding of Convolution Codes

7.7 Stack Algorithm

7.8 Known Good Convolution Codes

7.9 Turbo Codes

7.10 LDPC Codes

7.11 Introduction to Trellis Coded Modulation

8 Cryptography and Information Security

8.1 Introduction

8.2 Introduction to Number Theory

8.3 An Overview of Cryptographic Algorithms

8.4 Symmetric Key Cryptography

8.5 Asymmetric Key Cryptography

8.6 Diffie-Hellman Key Exchange Algorithm

8.7 Data Encryption Standard

8.8 Triple DES

8.9 Advanced Encryption Standard (AES)

8.10 One-Way Hash Function

8.11 Cryptanalysis

Summary

Review Questions