Algorithmic Information Theory: Mathematics of Digital Information Processing

Front Cover
Springer Science & Business Media, Feb 15, 2007 - Computers - 443 pages
0 Reviews
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).
 

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

Data Compaction 11 Entropy Coding 111 Discrete Sources and Their Entropy
5
112 Towards Huffman Coding
10
113 Arithmetic Coding
32
The Example LZW 121 LZW Coding
43
122 The LZW Decoder
45
Cryptography
49
211 The DES Scheme
50
212 The Cipher DES in Detail
53
32 Trigonometric Interpolation
190
321 Trigonometric Polynomials
191
331 Fourier Series
198
332 The WhittakerShannon Theorem for Elementary Periodic Functions
203
A Sketch
209
334 The Sampling Theorem
214
Error Control Codes 41 The ReedSolomon Codes 411 Preliminaries Polynomial Codes
220
412 ReedSolomon Codes
225

The Cipher Rijndael 221 Some Elementary Arithmetic
60
222 Specification of Rijndael
77
223 The Key Schedule
86
224 Decryption with Rijndael
92
231 Encryption and Decryption via Exponentiation
93
232 The Cryptosystem RSA
97
241 Message Digests via SHA1
101
Digital Signature Algorithm
112
243 Auxiliary Algorithms for DSA
116
244 The Signature Algorithm rDSA
122
245 ECDSA Elliptic Curve Digital Signatures
125
Information Theory and Signal Theory Sampling and Reconstruction
171
311 Basic Properties
172
312 The Fast Fourier Transform Algorithm
183
421 Encoding Digital Filtering in Binary Arithmetic
239
The Viterbi Method
253
Data Reduction Lossy Compression
267
51 DFT Passband Filtering and Digital Filtering
268
52 The Discrete Cosine Transform
274
521 Functional Description of the DCT
275
522 The 2D DCT
293
523 The KarhunenLoeve Transform and the DCT
305
531 Two Channel Filter Banks
314
532 The Discrete Wavelet Transform
372
References
435
Index
438
Copyright

Other editions - View all

Common terms and phrases