# how to do IFFT using only FFT?

Started by 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
>
>
```