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).
hvs@ee.upenn.edu (H.V. Sorensen) (08/05/90)
>tmb@wheaties.ai.mit.edu (Thomas M. Breuel) writes >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? I am glad to see you solved your own problem, but will have to dissapooint you. If you are interested in speed, you should stick with the real-input FFTs. It has been shown several places, that the Hartley transform requires more arithmetic operations than the real-input FFT. (The number of multiplications are the same, while the number of additions are N-2 more for the Hartley transform, where N is the transform length). Hope this helps you, Henrik Sorensen ****************************************************************************** * Henrik Sorensen Department of Electrical Enginering * * Internet: hvs@ee.upenn.edu University of Pennsylvania * ******************************************************************************
rbl@nitrex.UUCP ( Dr. Robin Lake ) (08/06/90)
In article <9706@life.ai.mit.edu> tmb@ai.mit.edu writes: | >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? | > ... | > | >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. Perhaps not right on target, but I find the following at hand: R. N. Bracewell "Numerical Transforms" Science, 11 May 1990, pg 697ff. P. Duhamel and M. Vetterli "Improved Fourier and Hartley Transform Algorithms ... " IEEE Trans ASSP. #6, June 1987, pg.818 ff. Surprisingly, nothing in the books on Fast Algorithms or MultiDimensional Signal Processing. Rob Lake BP Research rbl@BP.COM