tmb@wheaties.ai.mit.edu (Thomas M. Breuel) (08/05/90)
Does anyone know or have pointers to the literature or code about how to do multidimensional Hartley transforms (i.e., is it obvious that a 2D HT is the same as 2 1D HT's, or do I need some correction), and what the correlation and convolution theorems look like for multidimensional Hartley transforms? A straightforward derivation and implementation of the convolution/correlation theorems would give 4 times the number of multiplications for a convolution/ correlation as the corresponding (complex) Fourier method and not allow the operation to be done "in place" (replacing one of the input arrays). I think by rearranging terms I can fix this, but I would rather not have to work it out myself. Also, does anyone have code for the FHT (C/Fortran)? Currently, I am using a REALFFT routine and re-arrange the output, which is probably not very inefficient, but not quite as fast as it could be. Have the patent issues involving the FHT been resolved? Thanks, Thomas. tmb@ai.mit.edu PS: the Hartley transform is a real transform that is closely related to the Fourier transform and has some practical advantages over it if all you want to do is operate on real data.
tmb@wheaties.ai.mit.edu (Thomas M. Breuel) (08/05/90)
Oh, well, the answers turn out to be simple (I thought about it while waiting for the subway--"think--then post")... sorry to have bothered the list with the first set of questions, but I would still be interested in the answer to this question: |Also, does anyone have code for the FHT (C/Fortran)? Currently, I am |using a REALFFT routine and re-arrange the output, which is probably |not very inefficient, but not quite as fast as it could be. Have the |patent issues involving the FHT been resolved? Thanks, Thomas. tmb@ai.mit.edu PS: the other questions were: |Does anyone know or have pointers to the literature or code about how |to do multidimensional Hartley transforms (i.e., is it obvious that a |2D HT is the same as 2 1D HT's, or do I need some correction), The answer is obvious if you write f(x,y)=(cas px)(cas qy) as the set of basis functions, where cas x=(sin x)+(cos x). |and what |the correlation and convolution theorems look like for multidimensional |Hartley transforms? [and: can we get the same number of multiplies |as for the FT case] It turns out that it isn't too hard to show that if you apply the HT 1D correlation/convolution theorem first in the X and then in the Y direction, you get the correct answer and in the same number of multiplies as the complex (Fourier) version. You get the 1D versions from the corresponding Fourier theorems and the relation 2F=(H+HR)+i(-H+HR), where HR(x)=H(-x).