Slashdot Mirror

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?