Title :
On the encoding complexity of scalar quantizers
Author :
Hui, Dennis ; Neuhoff, David L.
Author_Institution :
Dept. of Electr. Eng., Michigan Univ., Ann Arbor, MI, USA
Abstract :
It is shown that as rate increases the problem of asymptotically optimal scalar quantization has polynomial-time (or space) encoding complexity if the distribution function corresponding to the one-third power of the source density is polynomial-time (or space) computable in the Turing sense
Keywords :
computational complexity; encoding; quantisation (signal); Turing encoder; asymptotically optimal scalar quantization; distribution function; encoding complexity; one-third power; polynomial-time encoding complexity; scalar quantizers; source density; space encoding complexity; Arithmetic; Distributed computing; Distribution functions; Encoding; Polynomials; Power engineering computing; Quantization; Rate distortion theory; Rate-distortion; Turing machines;
Conference_Titel :
Information Theory, 1995. Proceedings., 1995 IEEE International Symposium on
Conference_Location :
Whistler, BC
Print_ISBN :
0-7803-2453-6
DOI :
10.1109/ISIT.1995.550359
