Sorry. I missed one step / definition, that has been inserted below.
Rune
Rune Allnor wrote:
> bhooshaniyer wrote:
> > >I used to think the operations are the same?
> > >
> > >Thank you.
> > >
> >
> > Here is the equation for both forward and inverse transform:
> > (Iam not used to typing math equations in text files, but never the
> > less:)
> >
> > ----------------------------------------------
> > FFT:
> > x(F)= summation( x(n)* exp[(-j*2*pi/N)kn]
> > ---------
> > 0->N-1
> >
> > IFFT:
> > x(n)= 1/N * summation( x(n)* exp[(j*2*pi/N)kn]
> > ---------
> > 0->n-1
> > -------------------------------------------------
> >
> > They are the same from a computational point of view, where one
> utilizes
> > the same function to perform both forward and inverse transform.
>
> Stricktly speaking, the FFT and IFFT above are the DFT and IDFT,
> respectively.
>
> Apart from that, the best way to see why the interconnection between
> the DFT and IDFT is so close, is to write everything in terms of
linear
>
> algebra.
>
> First some definitions:
>
> x - Input data signal, N x 1 vector
> X - DFT of x, Nx 1 vector.
> x(n) - n'th coefficient of x
> X(k) - k'th coefficient of X
> w_k - N x 1 vector
> W - N x N matrix.
>
> I am using matlab's notation where x' means "the conjugated
> transposed of x". x^T means "x transposed".
>
> OK, first find element X(k) in the sepctrum:
>
> X(k) = w'_k * x [1]
>
> where
>
> w_k=[1 exp(j2pi*f_k), exp(j2pi*2f_k),...,exp(j2pi(N-1)*f_k)]^T [2]
> /sqrt(N)
>
> and
>
> f_k = k/N, k integer < N. [3]
>
> With these definitions, the DFT becomes
>
> X = Wx [4]
>
> and the IDFT becomes
>
> x = W^{-1}X. [5]
where
W = [w_0, w_1, ... , w_(N-1)].
> The interesting point is that W is unitary, i.e.
>
> W'W = WW' = I [6]
>
> which in turn means that
>
> W^{-1} = W'
[7.a]
> W'^{-1} = W
[7.b]
>
> which is easily verified by investigating the inner product
>
> c_pq = w_p'*w_q [8]
>
> for various combinations of p and q. More specifiucally,
>
> c_pq = 1 p==q
[9.a]
> c_pq = 0 p=/=q
[9.b]
>
> So the reason why the DFT and IDFT (and hence the FFT and the IFFT
> algorithms) are so similar, is the transform matrix W being unitary,
> as seen in equation [6] above. It is obvious from [6] that the choise
> of signum, +j or -j, in the forward transform has no significance
> for the maths.
>
> HTH,
>
> Rune
Reply by Rune Allnor●March 28, 20052005-03-28
bhooshaniyer wrote:
> >I used to think the operations are the same?
> >
> >Thank you.
> >
>
> Here is the equation for both forward and inverse transform:
> (Iam not used to typing math equations in text files, but never the
> less:)
>
> ----------------------------------------------
> FFT:
> x(F)= summation( x(n)* exp[(-j*2*pi/N)kn]
> ---------
> 0->N-1
>
> IFFT:
> x(n)= 1/N * summation( x(n)* exp[(j*2*pi/N)kn]
> ---------
> 0->n-1
> -------------------------------------------------
>
> They are the same from a computational point of view, where one
utilizes
> the same function to perform both forward and inverse transform.
Stricktly speaking, the FFT and IFFT above are the DFT and IDFT,
respectively.
Apart from that, the best way to see why the interconnection between
the DFT and IDFT is so close, is to write everything in terms of linear
algebra.
First some definitions:
x - Input data signal, N x 1 vector
X - DFT of x, Nx 1 vector.
x(n) - n'th coefficient of x
X(k) - k'th coefficient of X
w_k - N x 1 vector
W - N x N matrix.
I am using matlab's notation where x' means "the conjugated
transposed of x". x^T means "x transposed".
OK, first find element X(k) in the sepctrum:
X(k) = w'_k * x [1]
where
w_k=[1 exp(j2pi*f_k), exp(j2pi*2f_k),...,exp(j2pi(N-1)*f_k)]^T [2]
/sqrt(N)
and
f_k = k/N, k integer < N. [3]
With these definitions, the DFT becomes
X = Wx [4]
and the IDFT becomes
x = W^{-1}X. [5]
The interesting point is that W is unitary, i.e.
W'W = WW' = I [6]
which in turn means that
W^{-1} = W' [7.a]
W'^{-1} = W [7.b]
which is easily verified by investigating the inner product
c_pq = w_p'*w_q [8]
for various combinations of p and q. More specifiucally,
c_pq = 1 p==q [9.a]
c_pq = 0 p=/=q [9.b]
So the reason why the DFT and IDFT (and hence the FFT and the IFFT
algorithms) are so similar, is the transform matrix W being unitary,
as seen in equation [6] above. It is obvious from [6] that the choise
of signum, +j or -j, in the forward transform has no significance
for the maths.
HTH,
Rune
Reply by robert bristow-johnson●March 27, 20052005-03-27
in article T1q1e.13096$1S4.1363995@news.xtra.co.nz, Dr Tam at
ProfTam@yahoo.co.nz wrote on 03/26/2005 22:48:
>
> "bhooshaniyer" <bhooshaniyer@gmail.com> wrote in message
> news:wsmdnQOZJbwmh93fRVn-qw@giganews.com...
>>> I used to think the operations are the same?
>>>
>>> Thank you.
>>>
>>
>> Here is the equation for both forward and inverse transform:
>> (Iam not used to typing math equations in text files, but never the
>> less:)
> Strictly speaking the direct FFT whould have the 1/N. Why? Well consider a
> pure dc signal, its FFT will be the average.
it's a matter of convention and, while i agree with your preference - i have
the same, it's not the common convention in the literature and i finally got
tired of having it corrected in anything i wrote.
it would be nice if all the textbooks could be rewritten.
--
r b-j rbj@audioimagination.com
"Imagination is more important than knowledge."
Reply by Dr Tam●March 26, 20052005-03-26
"bhooshaniyer" <bhooshaniyer@gmail.com> wrote in message
news:wsmdnQOZJbwmh93fRVn-qw@giganews.com...
> >I used to think the operations are the same?
> >
> >Thank you.
> >
>
> Here is the equation for both forward and inverse transform:
> (Iam not used to typing math equations in text files, but never the
> less:)
>
> ----------------------------------------------
> FFT:
> x(F)= summation( x(n)* exp[(-j*2*pi/N)kn]
> ---------
> 0->N-1
>
> IFFT:
> x(n)= 1/N * summation( x(n)* exp[(j*2*pi/N)kn]
> ---------
> 0->n-1
> -------------------------------------------------
>
Strictly speaking the direct FFT whould have the 1/N.Why? Well consider a
pure dc signal, its FFT will be the average.
Dr Tam
Reply by Clay S. Turner●March 25, 20052005-03-25
"Randy Yates" <randy.yates@sonyericsson.com> wrote in message
news:xxpsm2jvka9.fsf@usrts005.corpusers.net...
> "Clay S. Turner" <Physics@Bellsouth.net> writes:
>> [...]
>
>> There is a simple linear transformation between the Hartley and
>> Fourier transforms, so one doesn't really have any info the other
>> doesn't.
>
> Hi Clay,
>
> I don't really mean to mince words here, but couldn't you say that the
> time domain "doesn't really have any info" the frequency domain
> doesn't, and vice-versa? After all, the FT is a linear transformation
> of the time domain.
>
> What I'm getting at is that, even though the HT may be isomorphic to
> the FT, it still might be a view of the signal that is useful for
> certain purposes that the FT doesn't provide.
>
> I dunno - maybe it's not useful. I certainly don't know of any reason
> to use it, but it would be shame to overlook some usefulness we haven't
> thought of.
> --
Hello Randy,
Certainly, the FT is a linear transform, but the freq. domain representation
is at least enough different than the time domain presentation to be quite
useful. The Hartley transform is so similar to the Fourier transform, that
its differences are simply academic. For example a single sinusoid in the
time domain gets mapped to a mix of plus and minus "frequencies". Actually
the Hartley really only looks at positive frequencies and the phase info is
distributed between the plus and minus frequency values. I.e., the plus
frequency is the component of the signal along a +45 degree phase shifted
sinusoid. and the minus frequency finds the orthogonal component along a -45
degree phase shifted sinusoid. For each frequency, both transforms perform
projections onto a pair of orthogonal sinusoids.
Clay
Reply by ●March 25, 20052005-03-25
"Clay S. Turner" <Physics@Bellsouth.net> writes:
> [...]
> There is a simple linear transformation between the Hartley and
> Fourier transforms, so one doesn't really have any info the other
> doesn't.
Hi Clay,
I don't really mean to mince words here, but couldn't you say that the
time domain "doesn't really have any info" the frequency domain
doesn't, and vice-versa? After all, the FT is a linear transformation
of the time domain.
What I'm getting at is that, even though the HT may be isomorphic to
the FT, it still might be a view of the signal that is useful for
certain purposes that the FT doesn't provide.
I dunno - maybe it's not useful. I certainly don't know of any reason
to use it, but it would be shame to overlook some usefulness we haven't
thought of.
--
Randy Yates
Sony Ericsson Mobile Communications
Research Triangle Park, NC, USA
randy.yates@sonyericsson.com, 919-472-1124
Reply by Clay S. Turner●March 25, 20052005-03-25
Hello Andor,
The Hartley is just a variation on the Fourier transform that is useful for
real valued signals. A FHT is supposed to be pretty good, but FFT methods
compete quite well. So I believe the Hartley transform is almost totally
academic these days. There is a simple linear transformation between the
Hartley and Fourier transforms, so one doesn't really have any info the
other doesn't.
Clay
"Andor" <an2or@mailcircuit.com> wrote in message
news:1111743674.514081.107790@z14g2000cwz.googlegroups.com...
> Thanks Clay. I've always wondered, in what applications is the Hartley
> transform used?
>
> Regards,
> Andor
>
Reply by Andor●March 25, 20052005-03-25
Thanks Clay. I've always wondered, in what applications is the Hartley
transform used?
Regards,
Andor
Reply by Clay S. Turner●March 23, 20052005-03-23
Andor,
The simple example of a self inverting transform is a Hartley transform.
Clay
"Andor" <an2or@mailcircuit.com> wrote in message
news:1111567486.428107.161760@z14g2000cwz.googlegroups.com...
> Haha, my example is not only non-trivial, it is also non-correct. The
> Hadamard transform, while unitary, is not Hermitian. Better examples of
> unitary and Hermitian operators are the Pauli operators. Unfortunately
> I can't think of an application of Pauli operators to DSP, which sort
> of nullifies my above comment (at least in this forum). Oh well.
>
Reply by Rick Lyons●March 23, 20052005-03-23
On Tue, 22 Mar 2005 21:39:14 -0500, robert bristow-johnson
<rbj@audioimagination.com> wrote:
>> On Tue, 22 Mar 2005 19:28:16 +0800, "Sea Squid"
>> <Sea.Squid@hotmail.com> wrote:
>>
>>> I used to think the operations are the same?
>
>in article 4240c70e.40154093@news.sf.sbcglobal.net, Rick Lyons at
>r.lyons@_BOGUS_ieee.org wrote on 03/22/2005 20:46:
>
>> If you've had formal engineering (mathematical) training,
>> then you must surely remember that the Fourier transform is
>> *not* equal the Inverse Fourier transform. To think that
>> they're equal is kinda like like saying that multiplication
>> and division are equal.
>
>boy, Rick, we could get into a deep philosophical disagreement here. when
>expressed as:
>
>
>FT:
> +inf
> X(f) = integral{ x(t) * exp(-j*2*pi*f*t) dt}
> -inf
>
>
>iFT:
> +inf
> x(t) = integral{ X(f) * exp(+j*2*pi*f*t) df}
> -inf
>
>
>
>the Fourier Transform and Inverse Fourier Transform are exactly the same
>thing except the +j is replaced by -j. the funny thing is that -j and +j
>have equal claim to being the sqrt(-1). both square to be -1.
>
>it is only a matter of convention which separates the two. multiplication
>and division are also inverse operations, but they are qualitatively
>different. the FT and iFT are only quantitatively different and only
>because of convention. that is what allows the Duality Theorem to exist.
>the FT and iFT are closer to the 1/x function, which is its own inverse.
>
>a similar argument could be made for the DFT and iDFT if the convention was
>modified slightly to put a 1/sqrt(N) in front of both summations. they
>would be the same damn thing if you switch -j and +j.
>
Hi Robert B-J,
well, ... humm. I was looking at Sea Squid's
question from a strictly "practical", spectrum analysis,
view point. But ... I agree with everything you wrote.
I realize that the DFT and the IDFT differ only in their
phase results, and that realization didn't occur to
me when I replied to Sea Squid.
Maybe his question was much "deeper" than I first thought.
Good Robert.
[-Rick-]