Algorithmic Information Theory: Mathematics of Digital Information Processing

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 five chapters of increasing difficulty, five sensibly different subjects in Discrete Mathematics. The first two chapters on data compaction (lossless data compression) and cryptography are on an undergraduate level – the most difficult mathematical prerequisite will be a sound understanding of quotient rings, especially of finite fields (mostly in characteristic 2). The next two chapters are already on a graduate level; the reader should be slightly acquainted with arguments in signal theory – although Lebesque integration could remain the “grey box” that it usually is. We encounter sampling – an innocent operation of tremendous epistemological impact: the Platonic mathematician leaving his heaven of continuity (rule=truth) for the earth of discreteness (diversity=uncertainty) will be plainly comforted by the great interpolation theorems that lift him back to the heights. The chapter on error control codes which are designed according to signal theoretical ideas, complements – on a purely algebraic level – the invasion of signal theory. The fifth and final chapter is the most important, in length as well as in complexity. It deals with lossy (image) compression, and yields the mathematical background for the understanding of JPEG and JPEG 2000. Now, our Platonic mathematician will be expelled from paradise: The discrete world becomes absolute, and all continuous constructions are plainly auxiliary and relative.