Multiplier-less discrete sinusoidal and lapped transforms using sum-of-powers-of-two (sopot) coefficients

This paper proposes a new family of multiplier-less discrete cosine and sine transforms called the SOPOT DCTs and DSTs. The fast algorithm of Wang (1994) is used to parameterize all the DCTs and DSTs in terms of certain (2/spl times/2) matrices, which are then converted to SOPOT representation. The forward and inverse transforms can be implemented with the same set of SOPOT coefficients. A random search algorithm is also proposed to search for these SOPOT coefficients. Experimental results show that the (2/spl times/2) basic matrix can be implemented, on the average, in 6 to 12 additions. The proposed algorithms therefore require only O(N log/sub 2/ N) additions, which is very attractive for VLSI implementation. Using these SOPOT DCTs/DSTs, a family of SOPOT Lapped Transforms (LT) is also developed. They have similar coding gains but much lower complexity than their real valued counterparts.