Algorithmic Information Theory

by Seibt, Peter

• ISBN13: 9783540332183
• ISBN10: 3540332189
• Format: Hardcover
• Copyright: 2006-11-15
• Publisher: Springer Verlag

Summary

This book treats the Mathematics of many important areas in digital information processing. It covers, in a unified presentation, five topics: Data Compression, Cryptography, Sampling (Signal Theory), Error Control Codes, Data Reduction. The thematic choices are practice-oriented. So, the important final part of the book deals with the Discrete Cosine Transform and the Discrete Wavelet Transform, acting in image compression. The presentation is dense, the examples and numerous exercises are concrete. The pedagogic architecture follows increasing mathematical complexity. A read-and-learn book on Concrete Mathematics, for teachers, students and practitioners in Electronic Engineering, Computer Science and Mathematics.

Table of Contents

Data Compaction	p. 5
Entropy Coding	p. 5
Discrete Sources and Their Entropy	p. 5
Towards Huffman Coding	p. 10
Arithmetic Coding	p. 32
Universal Codes: The Example LZW	p. 43
LZW Coding	p. 43
The LZW Decoder	p. 45
Cryptography	p. 49
The Data Encryption Standard	p. 50
The DES Scheme	p. 50
The Cipher DES in Detail	p. 53
The Advanced Encryption Standard: The Cipher Rijndael	p. 60
Some Elementary Arithmetic	p. 60
Specification of Rijndael	p. 77
The Key Schedule	p. 86
Decryption with Rijndael	p. 92
The Public Key Paradigm and the Cryptosystem RSA	p. 93
Encryption and Decryption via Exponentiation	p. 93
The Cryptosystem RSA	p. 97
Digital Signatures	p. 101
Message Digests via SHA-1	p. 101
DSA: Digital Signature Algorithm	p. 112
Auxiliary Algorithms for DSA	p. 116
The Signature Algorithm rDSA	p. 122
ECDSA - Elliptic Curve Digital Signatures	p. 125
Information Theory and Signal Theory: Sampling and Reconstruction	p. 171
The Discrete Fourier Transform	p. 172
Basic Properties	p. 172
The Fast Fourier Transform Algorithm	p. 183
Trigonometric Interpolation	p. 190
Trigonometric Polynomials	p. 191
Sampling and Reconstruction	p. 193
The Whittaker-Shannon Theorem	p. 198
Fourier Series	p. 198
The Whittaker-Shannon Theorem for Elementary Periodic Functions	p. 203
The (Continuous) Fourier Transform: A Sketch	p. 209
The Sampling Theorem	p. 214
Error Control Codes	p. 221
The Reed-Solomon Codes	p. 221
Preliminaries: Polynomial Codes	p. 221
Reed-Solomon Codes	p. 225
Convolutional Codes	p. 239
Encoding: Digital Filtering in Binary Arithmetic	p. 239
Decoding: The Viterbi Method	p. 253
Data Reduction: Lossy Compression	p. 267
DFT, Passband Filtering and Digital Filtering	p. 268
The Discrete Cosine Transform	p. 274
Functional Description of the DCT	p. 275
The 2D DCT	p. 293
The Karhunen-Loeve Transform and the DCT	p. 305
Filter Banks and Discrete Wavelet Transform	p. 314
Two Channel Filter Banks	p. 314
The Discrete Wavelet Transform	p. 372
References	p. 435
Index	p. 439
Table of Contents provided by Publisher. All Rights Reserved.