I've been looking at an article in IEEE signal processing: Conjugate Symmetric Sequency-Ordered Complex Hadamard Transform by Aung, Ng, and Rahardja.

Basically they define a transform which shares a lot of properties with the Discrete Fourier Transform but only requires addition and subtraction to implement. In that respect it's like a sequency-ordered Walsh-Hadamard transform, but this one operates in the complex domain and shares symmetries with the DFT. It's kind of cool, but it doesn't have quite enough sidelobe rejection to be very useful for pitch detection above 16 bands or so.

While I was poking at implementing it, though, I noticed that although the transform is defined recursively for a fast implementation in the article, there seems to be a VERY close connection to the decimation-in-time FFT which I didn't see called out in the paper. (It may very well have been and I just missed it.)

Anyway, in a radix-2 DIT FFT the transform of length N is defined as a permutation operation followed by a pair of length N/2 DFTs followed by the "twiddle factors", which are just complex exponentials spaced at multiples of e^(-i*pi/(n/2)). (I'm too tired to look up the LaTeX embedding syntax right now.)

The interesting part is that the CS-SCHT transform in the article above can be expressed identically except that the twiddle factors are different. In the DFT the twiddle factors are a simple sequence of points on the unit circle. In the CS-SCHT all of the factors are +/- 1, except for one that's -i. (It's that property that makes it possible to implement without multiplication). I haven't figured out the pattern yet, but I'm curious to see what it is.

What this gives me, though, is a nice compact way of specifying FFT-like transforms in terms only of the requisite twiddle factors. That gives me a very powerful design technique for integer-friendly FFT-like transforms. More to follow someday.