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

• Fast Hartley Transform (similar to FFT, but 2x faster)
  Posted by legacy on 26 Jan, 2016 12:40
• 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
• #1 Reply
  Posted by coppice on 26 Jan, 2016 14:30
• 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.
• #2 Reply
  Posted by andre_teprom on 26 Jan, 2016 14:40
• Taking a quick search on the web, could find something.
  

  Quote

  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

  
  
  
• #3 Reply
  Posted by legacy on 26 Jan, 2016 15:02
• Quote from: legacy on 26 Jan, 2016 12:40

  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 
• #4 Reply
  Posted by larsdenmark on 27 Jan, 2016 23:57
• 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.
  
• #5 Reply
  Posted by KE5FX on 28 Jan, 2016 00:38
• 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.
• #6 Reply
  Posted by krapht on 29 Jan, 2016 20:15
• 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.
• #7 Reply
  Posted by confusedElectron on 03 Feb, 2016 21:29
• 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
• #8 Reply
  Posted by Marco on 07 Feb, 2016 19:26
• 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).
• #9 Reply
  Posted by legacy on 07 Feb, 2016 19:35
• 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