Quantization and Roundoff Errors
Principal Investigator: István Kollár

Uniform quantization is usually present at several stages of digital signal processing. Analog-to-digital conversion and arithmetic rounding are inherent to every digital equipment, working with measured signals. However, quantization is a nonlinear operation, even if its characteristic is uniform, therefore it is extremely difficult to investigate its effects. A very fruitful approach was introduced by Bernard Widrow in the late fifties. He recognized that quantization is a kind of discretization of the probability density function (PDF). Therefore, the effect of quantization on the PDF is a kind of sampling. If the signal's important properties are described by statistical means, a quantizing theorem, similar to the Shannon theorem, can assure proper measurement of them. This leads to the so-called statistical theory of quantization.

Since Widrow's original work several new results were formulated and published, concerning conditions of proper quantization, usage of dither and so on, but no comprehensive work on the topic was published. Meanwhile, with the spread of digital computers and digital signal processors, understanding the effects of quantization is increasingly important. The aim of this research is to summarize the available results on uniform quantization using the scientific literature, to do analytical and computer simulation investigations in order to check the statements, to answer possibly all open questions, and to present the results in a useful form, preferably in a book. The conditions of common work were first established when István Kollár obtained a Fulbright scholarship to Stanford in 1993. The collaboration turned out to be extremely useful. István Kollár stayed at Stanford and worked together with Bernard Widrow until June 1995. Since then, two mutual visits, and intensive Internet connection promote the common work. It is very effective when the manuscript of Bernard Widrow is being typed at Stanford, then proofread at Budapest by István Kollár, and it gets printed at Stanford with some correction marks for further work, through a computer login from Hungary. Such a cooperation would have been impossible a few years ago.

The first step of the work was to do thorough literature search, and compile a comprehensive bibliography of uniform quantization. Later, the scope of research was extended to floating-point quantization. Now the completed bibliography consists of 820 items. It is compiled in BibTeX, so it is directly usable in the book which is written in LaTeX. Most papers have even been acquired. A copy of this bibliography will be made available electronically.

Investigation of applications of uniform quantization led directly to floating-point quantization. Floating-point is the main data representation format of many recent digital signal processors and signal processing programs. We have recognized that the compressor-quantizer-expandor sequence describes the data processing procedure very well. We could use this model to develop important formulas which can be used in analysis and design.

The primary target of the project was the book "Quantization Noise" which has been already published. It consists of altogether 21 chapters and 12 appendices, typeset in LaTeX. The full Contents List (with temporary chapter numbering) and a few chapters of the book is available in is electronic form. Several new results were obtained and described. We have presented uniform quantizer theory in detail, and extended it to floating-point quantization.

Related publications

The work is done in cooperation with the Information Systems Laboratory (ISL) of Stanford University (CA, USA).


Cooperating partners at ISL: Bernard Widrow.
Further participants at DMIE: János Márkus, Attila Sárhegyi .