New 2nDCT algorithms suitable for VLSI implementation

Small length Discrete Cosine Transforms (DCT´s) are used for image data compression. In that case, length 8 or 16 DCT´s are needed to be performed at video rate. We propose two new implementation of DCT´s which have several interesting features, as far as VLSI implementation is concerned. A first one, using modulo-arithmetic, needs only one multiplication per input point, so that a single multiplier is needed on-chip. A second one, based on a decomposition of the DCT into polynomial products, and evaluation of these polynomial products by distributed arithmetic, results in a very small chip, with a great regularity and testability. Furthermore, the same structure can be used for FFT computation by changing only the ROM-part of the chip. Both new architectures are mainly based on a new formulation of a length-2ⁿDCT as a cyclic convolution, which is explained in the first section of the paper.