An efficient algorithm for the multiplierless realization of 2-D linear transforms

In this work, an algorithm is developed for the automatic generation of multiplierless architectures for two dimensional linear transforms. Though there are a number of algorithms developed for this purpose, the algorithm presented in this paper outperforms the previous ones: When regular CSD (canonic-signed-digit) representation is used for the quantization of scalars in the two dimensional coefficient matrix, architectures employing 20%-60% fewer adders than the original architectures. This is improved by an additional 15-25% if the recently-introduced CSD-4 representation is used for the quantization of scalars.