Skip to:Content
|
Bottom
Cover image for Algorithmic information theory : mathematics of digital information processing
Title:
Algorithmic information theory : mathematics of digital information processing
Personal Author:
Series:
Signals and communication technology ; 1860-4862
Publication Information:
London : Springer, 2006
ISBN:
9783540332183

Available:*

Library
Item Barcode
Call Number
Material Type
Item Category 1
Status
Searching...
30000010113509 QA76.9.D33 S44 2006 Open Access Book Book
Searching...

On Order

Summary

Summary

Shall we be destined to the days of eternity, on holy-days,as well as working days, to be shewing the RELICKS OF LEARNING, as monks do the relicks of their saints - without working one - one single miracle with them? Laurence Sterne, Tristram Shandy This book deals with information processing; so it is far from being a book on information theory (which would be built on description and estimation). The reader will be shown the horse, but not the saddle. At any rate, at the very beginning, there was a series of lectures on "Information theory, through the looking-glass of an algebraist", and, as years went on, a steady process of teaching and learning made the material evolve into the present form. There still remains an algebraic main theme: algorithms intertwining polynomial algebra and matrix algebra, in the shelter of signal theory. A solid knowledge of elementary arithmetic and Linear Algebra will be the key to a thorough understanding of all the algorithms working in the various bit-stream landscapes we shall encounter. This priority of algebra will be the thesis that we shall defend. More concretely: We shall treat, in ?ve chapters of increasing di?culty, ?ve sensibly di?erent subjects in Discrete Mathem- ics. The?rsttwochaptersondatacompaction(losslessdatacompression)and cryptography are on an undergraduate level - the most di?cult mathematical prerequisite will be a sound understanding of quotient rings, especially of- nite ?elds (mostly in characteristic 2).


Table of Contents

1 Data Compactionp. 5
1.1 Entropy Codingp. 5
1.1.1 Discrete Sources and Their Entropyp. 5
1.1.2 Towards Huffman Codingp. 10
1.1.3 Arithmetic Codingp. 32
1.2 Universal Codes: The Example LZWp. 43
1.2.1 LZW Codingp. 43
1.2.2 The LZW Decoderp. 45
2 Cryptographyp. 49
2.1 The Data Encryption Standardp. 50
2.1.1 The DES Schemep. 50
2.1.2 The Cipher DES in Detailp. 53
2.2 The Advanced Encryption Standard: The Cipher Rijndaelp. 60
2.2.1 Some Elementary Arithmeticp. 60
2.2.2 Specification of Rijndaelp. 77
2.2.3 The Key Schedulep. 86
2.2.4 Decryption with Rijndaelp. 92
2.3 The Public Key Paradigm and the Cryptosystem RSAp. 93
2.3.1 Encryption and Decryption via Exponentiationp. 93
2.3.2 The Cryptosystem RSAp. 97
2.4 Digital Signaturesp. 101
2.4.1 Message Digests via SHA-1p. 101
2.4.2 DSA: Digital Signature Algorithmp. 112
2.4.3 Auxiliary Algorithms for DSAp. 116
2.4.4 The Signature Algorithm rDSAp. 122
2.4.5 ECDSA - Elliptic Curve Digital Signaturesp. 125
3 Information Theory and Signal Theory: Sampling and Reconstructionp. 171
3.1 The Discrete Fourier Transformp. 172
3.1.1 Basic Propertiesp. 172
3.1.2 The Fast Fourier Transform Algorithmp. 183
3.2 Trigonometric Interpolationp. 190
3.2.1 Trigonometric Polynomialsp. 191
3.2.2 Sampling and Reconstructionp. 193
3.3 The Whittaker-Shannon Theoremp. 198
3.3.1 Fourier Seriesp. 198
3.3.2 The Whittaker-Shannon Theorem for Elementary Periodic Functionsp. 203
3.3.3 The (Continuous) Fourier Transform: A Sketchp. 209
3.3.4 The Sampling Theoremp. 214
4 Error Control Codesp. 221
4.1 The Reed-Solomon Codesp. 221
4.1.1 Preliminaries: Polynomial Codesp. 221
4.1.2 Reed-Solomon Codesp. 225
4.2 Convolutional Codesp. 239
4.2.1 Encoding: Digital Filtering in Binary Arithmeticp. 239
4.2.2 Decoding: The Viterbi Methodp. 253
5 Data Reduction: Lossy Compressionp. 267
5.1 DFT, Passband Filtering and Digital Filteringp. 268
5.2 The Discrete Cosine Transformp. 274
5.2.1 Functional Description of the DCTp. 275
5.2.2 The 2D DCTp. 293
5.2.3 The Karhunen-Loeve Transform and the DCTp. 305
5.3 Filter Banks and Discrete Wavelet Transformp. 314
5.3.1 Two Channel Filter Banksp. 314
5.3.2 The Discrete Wavelet Transformp. 372
Referencesp. 435
Indexp. 439
Go to:Top of Page