Vector quantization with variable-precision classification.

Abstract

We investigate variable-precision classification (VPC) for speeding vector quantization (VQ). VPC evaluates bit-serially, from the most significant bit. When the magnitude of the error due to the unevaluated bits is less than the absolute magnitude of the discriminant, we can classify without processing the remaining bits. A proof shows that as the operand precision increases, the average necessary precision becomes asymptotically independent of the operand precision, VPC makes the complexity of the L(2) norm equivalent to the L(1) norm. In VQ of real images, on average, the codevector element's precision necessary for classification was under four bits. We implemented binary classification circuitry using VPC and conventional approaches. The key modules were designed and their performance estimated assuming 1.0-mum gate array technology. The implementations could search binary pruned trees at the television quality video rate. When the overall execution time is important, VPC more than halves the computational complexity.