Fast Hartley transform (interactive demo included)
Andrey Demenev
Posts: 377
What: Fast Hartley transform. I am not going to write math here. In simple words, Harley transform converts from time domain to frequency domain. Hartley transform of finite discrete data (for example, electrical signal sampled with analog-to-digital convertor) is called Discrete Hartley Transform. Direct computation of Discrete Hartley Transform takes much time. An algorithm allowing to significantly reduce calculation time is called Fast Hartley Transform. Other similar transforms exist (Sine, Cosine, Fourier, etc), each with their own properties. Fourier transform is best known and most used for spectral analysis. In many cases, Hartley transform can be used instead of Fourier transform. In general, Hartley transform takest 2 times less memory and roughly 2 times less time compared to Fourier transform, because Fourier transform operates on complex numbers, and Hartley transform - on real numbers. Though, there exist fast Fourier transform algorithms working with real numbers.
Why: just for fun
First practical use coming to mind is audio spectrum analyzer.
How: "standard" in-place radix-2 decimation-in-time fast Hartley transform. The code was translated almost 1:1 from C++ source by J
Why: just for fun
First practical use coming to mind is audio spectrum analyzer.How: "standard" in-place radix-2 decimation-in-time fast Hartley transform. The code was translated almost 1:1 from C++ source by J
zip
42K
Comments
NickL
"Object exceeds runtime memory limit by 123 longs."
Nick
Great DEMO!
Since you don't need to double buffer the video in this demo, you can save half of the display memory AND load it from the Propeller IDE if you change a couple lines in the CON block so that they read...
and
bitmap_base = $3000 display_base = $3000Well, I could make it without double buffering, but display update is too slow, and fliccker is visible. The better way would be to reduce amount memory used by display.
Attached is a modified demo using less display tiles, should fit the memory without optimization. First post has been updated accordingly
http://forums.parallax.com/entry.php?86-Ripple-Draw
For the frame rate trade, simply do not present the display with new data, until all the strips have been drawn. Frame rates possible, depend on 60Hz or 50Hz divided by the number of strips chosen for the display.
You can also trade image integrity, allowing "tearing", by still drawing the strips in the same way, while allowing new data. That is the technique shown in the videos.
Both can be done either with a small partial buffer (recommended), or no buffer at all, if the draw speed is quick enough. For the no-buffer approach, there is a more advanced method, where the clearing of the draw strip is done incrementally, isolating flicker zones to small parts of the active strip, not shown. If you are interested in that, let me know. IMHO, the video for the single buffer was a bit aggressive, with some flicker to be seen. That illustrates the draw speed limits in action, as significant flicker can be seen in the time consuming objects, and not so much at all with the fast ones.
Finally, a sweep works for some images well, and not others. The strips can be interleaved, to eliminate the "sweep" effect seen in both videos, or the frame rate trade-off with no new data can be done to minimize, and in some cases, completely eliminate the sweeping motion.
Great demo! I can't wait to run this. A read earlier in my blog might explain some of why. Thanks for your explanation that filled a gap for me.
After comparing your FHT version with my pasm version, I have concluded that a major contributor to the significant dfferences in spreed is the handing of dsin/dcos. Your approach uses the sin table in the prop chip while my algorithm calculates updated values which involves 4 multiplications per cycle.
I have made some modifications in your fht.spin to conform to the syntax of my applications as well as include some additional functions {see attached fhtm.spin), especially Convolve & Autocorrelate. I have also attached another demo (MakingWaves) which is the inverse of your demo, although not as elegant.
NickL
Also, I have been experimenting with another Fourier-related transform - constant-Q transform. Fourier and Hartley transforms have linear frequency resolution. This makes them not very well suited for audio analysis. Human auditory system has high resolution at low frequencies, and the resolution decreases with frequency increase. Fourier transform provides redundant resolution at higher frequencies, but too low resolution at lower frequencies. Instead of analyzing equally spaced narrow bands (as in FT), CQT can analyze frequency bands with (reasonably) arbitrary center frequencies and bandwidths. Later I'll post results of my experiments with this transform
I just found this thread and I'm excited about the prospect of higher frequency resolution at audible frequencies.
I'm trying to make an audio tuner for my dissertation, and I've been playing around with the FFT that Beau posted a while back.
I stumbled on the video of the Constant-Q transform and I was mightily impressed.
I was wondering if there was any progress made and advice that could be given to a budding young propeller enthusiast?
Cheers
Now the problem, I need the FHT from 16384 data points but doesn't work well, can anyone help me? I dont understand completly how your code work, I am new in PASM (and english XD).
If I reduce the data points to 8192 all works nice.
The image show the problem, It's like aliasing but it is not.
The clock output in my code is for a low pass filter, I use a MAX293 (8th order low pass filter with a variable cutoff frecuency, "electronics witchcraft")
"serial fht.spin" is an example.
"matserial.m" is a script to receive data from serial and plot in matlab.