how to do IFFT using only FFT?

Started by kiki November 27, 2004
Hi all,

Suppose we are only given the function for FFT,  but we don't have IFFT 
routine...

and we have a real input data squence x,

y=fft(x),

now how to use FFT only to obtain the x=ifft(y)?

--------------------------------------

What if the input data sequence x is complex-valued?

Thanks alot 


kiki wrote:
> > Hi all, > > Suppose we are only given the function for FFT, but we don't have IFFT > routine... > > and we have a real input data squence x, > > y=fft(x), > > now how to use FFT only to obtain the x=ifft(y)?
Assuming an array x of complex numbers representing the FFT data: A = fft (imag(x) + i * real (x)); B = imag (A) + i * ral (A); result = B / length (b); Erik -- +-----------------------------------------------------------+ Erik de Castro Lopo nospam@mega-nerd.com (Yes it's valid) +-----------------------------------------------------------+ Linux, the UNIX defragmentation tool.
Hi

Pointer arithmetic can do this also for a real input sequence. let 
Y=FFT(X), where X=[x(0) x(1) x(2) ... x(N-1)]. Then FFT(Y/length(Y)) is 
[x(0) x(N-1) x(N-2) x(N-3) ... x(1)], i.e. the time-inverse, except for 
the first element.

Regards

Brian Dam Pedersen
M.Sc.EE



Erik de Castro Lopo wrote:
> kiki wrote: > >>Hi all, >> >>Suppose we are only given the function for FFT, but we don't have IFFT >>routine... >> >>and we have a real input data squence x, >> >>y=fft(x), >> >>now how to use FFT only to obtain the x=ifft(y)? > > > Assuming an array x of complex numbers representing the FFT data: > > A = fft (imag(x) + i * real (x)); > B = imag (A) + i * ral (A); > result = B / length (b); > > > Erik
to add a third method, just FFT and complex conjugate the result.  oh i
s'pose you also have to divide by N (the length of the sequence).  except
for that factor (and it's kinda arbitrary where it should go), the only
difference between the DFT and iDFT is the replacement of j with -j, and the
difference between j and -j is not qualitative.  they both have equal claim
to be sqrt(-1).

r b-j


in article coa61c$1t8$1@news.cybercity.dk, Brian Dam Pedersen at
brian.pedersen@mail.danbbs.dk wrote on 11/27/2004 10:20:

> Hi > > Pointer arithmetic can do this also for a real input sequence. let > Y=FFT(X), where X=[x(0) x(1) x(2) ... x(N-1)]. Then FFT(Y/length(Y)) is > [x(0) x(N-1) x(N-2) x(N-3) ... x(1)], i.e. the time-inverse, except for > the first element. > > Regards > > Brian Dam Pedersen > M.Sc.EE > > > > Erik de Castro Lopo wrote: >> kiki wrote: >> >>> Hi all, >>> >>> Suppose we are only given the function for FFT, but we don't have IFFT >>> routine... >>> >>> and we have a real input data squence x, >>> >>> y=fft(x), >>> >>> now how to use FFT only to obtain the x=ifft(y)? >> >> >> Assuming an array x of complex numbers representing the FFT data: >> >> A = fft (imag(x) + i * real (x)); >> B = imag (A) + i * ral (A); >> result = B / length (b); >> >> >> Erik >
You forgot a step.

Conjugate, fft, conjugate, scale



ifft(x)
  ==
conj( fft( conj(x) ) )/length(x)




robert bristow-johnson wrote:
> to add a third method, just FFT and complex conjugate the result. oh i > s'pose you also have to divide by N (the length of the sequence). except > for that factor (and it's kinda arbitrary where it should go), the only > difference between the DFT and iDFT is the replacement of j with -j, and the > difference between j and -j is not qualitative. they both have equal claim > to be sqrt(-1). > > r b-j > > > in article coa61c$1t8$1@news.cybercity.dk, Brian Dam Pedersen at > brian.pedersen@mail.danbbs.dk wrote on 11/27/2004 10:20: > > >>Hi >> >>Pointer arithmetic can do this also for a real input sequence. let >>Y=FFT(X), where X=[x(0) x(1) x(2) ... x(N-1)]. Then FFT(Y/length(Y)) is >>[x(0) x(N-1) x(N-2) x(N-3) ... x(1)], i.e. the time-inverse, except for >>the first element. >> >>Regards >> >>Brian Dam Pedersen >>M.Sc.EE >> >> >> >>Erik de Castro Lopo wrote: >> >>>kiki wrote: >>> >>> >>>>Hi all, >>>> >>>>Suppose we are only given the function for FFT, but we don't have IFFT >>>>routine... >>>> >>>>and we have a real input data squence x, >>>> >>>>y=fft(x), >>>> >>>>now how to use FFT only to obtain the x=ifft(y)? >>> >>> >>>Assuming an array x of complex numbers representing the FFT data: >>> >>>A = fft (imag(x) + i * real (x)); >>>B = imag (A) + i * ral (A); >>>result = B / length (b); >>> >>> >>>Erik >> >
"Erik de Castro Lopo" <nospam@mega-nerd.com> wrote in message 
news:41A851A5.5238BA57@mega-nerd.com...
> kiki wrote: >> >> Hi all, >> >> Suppose we are only given the function for FFT, but we don't have IFFT >> routine... >> >> and we have a real input data squence x, >> >> y=fft(x), >> >> now how to use FFT only to obtain the x=ifft(y)? > > Assuming an array x of complex numbers representing the FFT data: > > A = fft (imag(x) + i * real (x)); > B = imag (A) + i * ral (A); > result = B / length (b); > > > Erik > -- > +-----------------------------------------------------------+ > Erik de Castro Lopo nospam@mega-nerd.com (Yes it's valid) > +-----------------------------------------------------------+ > Linux, the UNIX defragmentation tool.
Wah, it worked! Great! what is the theory behind this? I tried to resort to the formular for DFT but did not a theory of getting your above trick... could you please explain why it works? Thanks a lot
in article 7k6qd.44909$T13.11627@fe2.columbus.rr.com, Mark Borgerding at
mark@borgerding.net wrote on 11/27/2004 16:28:

> You forgot a step. > > Conjugate, fft, conjugate, scale > > > > ifft(x) == conj( fft( conj(x) ) )/length(x) >
you're right, i was thinking real input. if we replace j with -j, we have to do it everywhere. i guess then this becomes equivalent to Erik's post. r b-j
> robert bristow-johnson wrote: >> to add a third method, just FFT and complex conjugate the result. oh i >> s'pose you also have to divide by N (the length of the sequence). except >> for that factor (and it's kinda arbitrary where it should go), the only >> difference between the DFT and iDFT is the replacement of j with -j, and the >> difference between j and -j is not qualitative. they both have equal claim >> to be sqrt(-1). >> >> r b-j >> >> >> in article coa61c$1t8$1@news.cybercity.dk, Brian Dam Pedersen at >> brian.pedersen@mail.danbbs.dk wrote on 11/27/2004 10:20: >> >> >>> Hi >>> >>> Pointer arithmetic can do this also for a real input sequence. let >>> Y=FFT(X), where X=[x(0) x(1) x(2) ... x(N-1)]. Then FFT(Y/length(Y)) is >>> [x(0) x(N-1) x(N-2) x(N-3) ... x(1)], i.e. the time-inverse, except for >>> the first element. >>> >>> Regards >>> >>> Brian Dam Pedersen >>> M.Sc.EE >>> >>> >>> >>> Erik de Castro Lopo wrote: >>> >>>> kiki wrote: >>>> >>>> >>>>> Hi all, >>>>> >>>>> Suppose we are only given the function for FFT, but we don't have IFFT >>>>> routine... >>>>> >>>>> and we have a real input data squence x, >>>>> >>>>> y=fft(x), >>>>> >>>>> now how to use FFT only to obtain the x=ifft(y)? >>>> >>>> >>>> Assuming an array x of complex numbers representing the FFT data: >>>> >>>> A = fft (imag(x) + i * real (x)); >>>> B = imag (A) + i * real (A); >>>> result = B / length (b); >>>> >>>> >>>> Erik >>> >>
On Sat, 27 Nov 2004 13:40:02 -0800, "kiki" <lunaliu3@yahoo.com> wrote:

> >"Erik de Castro Lopo" <nospam@mega-nerd.com> wrote in message >news:41A851A5.5238BA57@mega-nerd.com... >> kiki wrote: >>> >>> Hi all, >>> >>> Suppose we are only given the function for FFT, but we don't have IFFT >>> routine... >>> >>> and we have a real input data squence x, >>> >>> y=fft(x), >>> >>> now how to use FFT only to obtain the x=ifft(y)? >> >> Assuming an array x of complex numbers representing the FFT data: >> >> A = fft (imag(x) + i * real (x)); >> B = imag (A) + i * ral (A); >> result = B / length (b); >> >> >> Erik >> -- >> +-----------------------------------------------------------+ >> Erik de Castro Lopo nospam@mega-nerd.com (Yes it's valid) >> +-----------------------------------------------------------+ >> Linux, the UNIX defragmentation tool. > >Wah, it worked! Great! what is the theory behind this? I tried to resort to >the formular for DFT but did not a theory of getting your above trick... >could you please explain why it works? > >Thanks a lot
Hi, does it work? Does it give *exactly* the same results as the standard IFFT? [-Rick-]
"Rick Lyons" <r.lyons@_BOGUS_ieee.org> wrote in message
news:41a9d43f.50639171@news.sf.sbcglobal.net...
> On Sat, 27 Nov 2004 13:40:02 -0800, "kiki" <lunaliu3@yahoo.com> wrote: > > > > >"Erik de Castro Lopo" <nospam@mega-nerd.com> wrote in message > >news:41A851A5.5238BA57@mega-nerd.com... > >> kiki wrote: > >>> > >>> Hi all, > >>> > >>> Suppose we are only given the function for FFT, but we don't have
IFFT
> >>> routine... > >>> > >>> and we have a real input data squence x, > >>> > >>> y=fft(x), > >>> > >>> now how to use FFT only to obtain the x=ifft(y)? > >> > >> Assuming an array x of complex numbers representing the FFT data: > >> > >> A = fft (imag(x) + i * real (x)); > >> B = imag (A) + i * ral (A); > >> result = B / length (b); > >> > >> > >> Erik > >> -- > >> +-----------------------------------------------------------+ > >> Erik de Castro Lopo nospam@mega-nerd.com (Yes it's valid) > >> +-----------------------------------------------------------+ > >> Linux, the UNIX defragmentation tool. > > > >Wah, it worked! Great! what is the theory behind this? I tried to resort
to
> >the formular for DFT but did not a theory of getting your above trick... > >could you please explain why it works? > > > >Thanks a lot > > Hi, > > does it work? Does it give *exactly* the same > results as the standard IFFT? > > [-Rick-] > > > >
Hi Rick - I tried it with scilab and it was as exact as I could want ( had some differences at the 1.e-17 level ) - best of luck - Mike

Mike Yarwood wrote:
> "Rick Lyons" <r.lyons@_BOGUS_ieee.org> wrote in message > news:41a9d43f.50639171@news.sf.sbcglobal.net... > >>On Sat, 27 Nov 2004 13:40:02 -0800, "kiki" <lunaliu3@yahoo.com> wrote: >> >> >>>"Erik de Castro Lopo" <nospam@mega-nerd.com> wrote in message >>>news:41A851A5.5238BA57@mega-nerd.com... >>> >>>>kiki wrote: >>>> >>>>>Hi all, >>>>> >>>>>Suppose we are only given the function for FFT, but we don't have > > IFFT > >>>>>routine... >>>>> >>>>>and we have a real input data squence x, >>>>> >>>>>y=fft(x), >>>>> >>>>>now how to use FFT only to obtain the x=ifft(y)? >>>> >>>>Assuming an array x of complex numbers representing the FFT data: >>>> >>>> A = fft (imag(x) + i * real (x)); >>>> B = imag (A) + i * ral (A); >>>> result = B / length (b); >>>> >>>> >>>>Erik >>>>-- >>>>+-----------------------------------------------------------+ >>>> Erik de Castro Lopo nospam@mega-nerd.com (Yes it's valid) >>>>+-----------------------------------------------------------+ >>>>Linux, the UNIX defragmentation tool. >>> >>>Wah, it worked! Great! what is the theory behind this? I tried to resort > to >>>the formular for DFT but did not a theory of getting your above trick... >>>could you please explain why it works?
The identities involved are: 1. ( Y + i X ) = { ( -i ) ( X + i Y ) }^* where Z = X + i Y is complex and adjacent terms are implicitly multiplied. This shows that the interchange of the real and imaginary parts can be expressed in terms of the usual operations on complex numbers. 2. FT^-1 ( Z ) = { FT ( Z^* ) }^* where the inverse FT has the same scaling as the FT. This is the common identity for the FT and its inverse. so FT ( { -i Z }^* ) = i FT ( Z^* ) = i { FT^-1 ( Z ) }^* or { FT ( { -i Z }^* ) }^* = -i { { FT^-1 ( Z ) }^* }^* = -i FT^-1 ( Z ) or i { FT ( { -i Z }^* ) }^* = FT^-1 ( Z ) and finally { -i FT ( { -i Z }^* ) }^* = FT^-1 ( Z ) which is just the usual identity plus { -i ( -i )^* }^* = 1 combined with the observation interchanging the real and imaginary parts is easy in programming and is ( -i Z )^* in algebra. All assuming no typos and the usual ASCII art and notation.
>>>Thanks a lot >> >>Hi, >> >> does it work? Does it give *exactly* the same >>results as the standard IFFT? >> >>[-Rick-] >> >> >> >> > > Hi Rick - I tried it with scilab and it was as exact as I could want ( had > some differences at the 1.e-17 level ) - best of luck - Mike > >