A method for computing the DFT of vector quantized data

A method is presented for computing the discrete Fourier transform (DFT) of data compressed using vector quantization (VQ). The VQ compressed data are not reconstructed before use; instead, a codebook that has been processed with the DFT (discrete Fourier transform) algorithm is used for VQ reconstruction. An overlap-and-add technique is used to combine the processed reconstruction codebook vectors to give the DFT directly. The technique is suitable for both one-dimensional and multidimensional DFTs or, in general, any linear process. The technique is called the computation compression technique (CCT). The CCT implementation yields exactly the same result as if the compressed data had been reconstructed and the DFT performed on the data directly. CCT convolution on a 68020/6881-based computer is described. Speedups of two orders of magnitude are obtained