Slashdot Mirror

superid writes "Several years ago while reading comp.dsp I found a link to The Weak Signal Challenge. On that page is a .wav file of a morse code signal bounced off the moon. The page author Mike Cook is offering $100 to the next person to successfully decode the morse code. Since I was the one who originally solved this, I promised Mike that I wouldn't divulge the answer or provide any clues. I can say thought that I didn't use anything special other than traditional signal processing techniques, octave, matlab, and patience. I think that overall I spent about 24 hours total sitting at my '486. I think it would be great to generate some interest in this. Maybe someone could come up with a novel solution and win $100!"

GregAllen writes "After searching for a good open-source AltiVec implementation of the Fast Fourier Transform (FFT), I have put together the AltiVec FFT page. It has all of the source, some benchmarks, and runs on Mac OS X or LinuxPPC. I even compared it to the venerable (but scalar) FFTW."

Between 1804 and 1807 Jean Fourier discovered the Fourier Transform: a means of transforming any function into its frequency components. He initially used it to study the propagation of heat in solids. Since then the Fourier transform has found a myriad of applications such as the JPEG, MPEG and MP3 formats... It's even been used to multiply polynomials. The main computational cost of the Fourier transform are the N^2 multiplications it requires. In 1903 Runge noticed that the number of multiplications required could be reduced to N.log(N) by using trigonometric symmetries. In 1965 this was applied in computers by Cooley and Tukey: the fast Fourier transform became popular. Since computers represent numbers in binary, multiplications and divisions by powers of 2 are commonly implemented by shifting bits left and right. Multiplications by constants are easily optimized using the same trick. In 1999 Trac Tran of Johns Hopkins University found an approximation to the DCT which causes very little error, yet uses only 13 shifts and 31 additions for N=8. Given the recursive nature of the FFT, this transform could be used as part of an FFT with N>8. Apparently, he has applied for a patent for this approximation. Do you think this is worth a patent? Do you know of prior art?