Fast odd sinusoidal transform algorithms

Abstract

In a previous paper, the authors have shown that it is possible to map an odd-length type-II and type-III even discrete cosine transform (EDCT) to a real-valued DFT of the same length with sign changes and permutations only. In this work, the authors extend the approach to device-efficient algorithms for computing the odd discrete cosine and sine transforms (ODCT and ODST). It is found that a N point type-I ODCT can be reformulated as a (2N-1)-point DFT of a real-symmetric sequence. Also, by representing the odd indices in the type-II, -III and -IV transforms using the Ruritanian map, it is possible to construct a simple index mapping which maps the transforms to a type-I ODCT or ODST of the same length with permutations and sign changes only. Similar results are obtained for the odd sine transforms. Using the Kronecker matrix product representation of the multidimensional transforms all these algorithms can be generalized to higher dimensions.