Fast Hartley Transform (similar to FFT, but 2x faster)

[legacy]

hi guys
Discrete Hartley transform is an analogue of discrete Fourier transform for real data, but it takes ONLY a real sequence as an input.

Do you happen to have on hand a good good implementation in C ?
I have to port it to different machines

thank you in advance

[coppice]

Googling "FHT in C" get you some code, but if you are concerned about the highest speed you might need something more tailored to the qualities of your platform. Depending how you implement things, the FHT may actually be slower than a well tuned FFT.

[andre_teprom]

Taking a quick search on the web, could find something.

A "working" implementation of the FHT in C:

• http://www.embedded.com/design/connectivity/4403178/Doing-Hartley-Smartly

Not sure how usabe are the pseudo c-codes, anyway...

• http://caxapa.ru/thumbs/455725/algorithms.pdf

[legacy]

Do you happen to have on hand a good good implementation in C ?

"happen to have on hand" should mean: do you already have (at least have seen) a pretty chunk of tested good C implementation ?
google doesn't tell you about that, google just reports whatever comes into the search key (which means, up to the 90% is … useless)
and I have no time, at least not now, to implement/test/check things
I am late, deadline coming, because my job-colleagues haven't done their homework 

thank you the same 

[larsdenmark]

If you are in a hurry then you most likely best off using an implementation of the FFT where you most likely will be able to find a fast generic implementation or specific optimized versions for your particular hardware. You can calculate the Hartley transform from a FFT. Note that the memory requirement of the FFT is twice as high, though.

Even if you do find an implementation of the Fast Hartley Transform that suits you, you will need to verfify that it works and then you'll need a method based on the FFT.

[KE5FX]

One important point that people seem to overlook in the FHT articles is that you don't have to zero out the complex elements when passing real input to an FFT.  You can stuff the next buffer full of real samples into the imaginary fields.  I've never needed to do this, but I'd probably look at it before resorting to a nonstandard transform.

[krapht]

A well optimized FFT implementation is equally as fast as the FHT, even with purely real inputs. There are optimization tricks you can do so that the complex computation is not wasted. I don't remember exactly how, though, but I know there is literature out there about it.

[confusedElectron]

Some time ago I used this code:  http://vtchl.uiuc.edu/node/557,

which is based on this library:  http://wiki.openmusiclabs.com/wiki/ArduinoFHT,

in order to implement a simple spectrum analyser on an Arduino board.

At the time I was just looking for something that worked, but as the guy above me noted, the FHT is not necessarily faster than a FFT specialized in processing real inputs. Take a look at this link: http://www.fftw.org/doc/The-Discrete-Hartley-Transform.html

[Marco]

There are ways to use a normal FFT for real Fourier transform as well, you can efficiently do two transforms at the same time or do a 2N point real transform with a N point FFT.

TI has a lot of code (which I did use, around 2 decades ago).

[legacy]

thank you, guys, at the end of the week (friday and saturday, a few days ago), I have git-pulled a cool FFT implementation
I have recycled my old code, and spent my time trying to optimize and adapt it: luckily with great results at the end

this, after I explained to my colleagues that FFT is as fast as the Fast Hartley Transform

thank you to have pointed it out