FFT/IFFT on real signals

Started by alomar March 21, 2010
Dear all,

I have a question about the FFT and IFFT on real signals.

For example, I want to perform 512-point FFT/IFFT pair on real signals,
x[0], x[1], ... , x[511]. There is a well-known method that 512-point FFT
on real signals can be simplified to 256-point FFT. However, how about the
IFFT? The spectrum of real signals is conjugate symmetric about N/2. I need
to perform 512-point IFFT or there exists a simplification?

May you have a good day
              Alomar Wang
On Mar 21, 9:22=A0pm, "alomar" <alomar.wang@n_o_s_p_a_m.gmail.com>
wrote:
> Dear all, > > I have a question about the FFT and IFFT on real signals. > > For example, I want to perform 512-point FFT/IFFT pair on real signals, > x[0], x[1], ... , x[511]. There is a well-known method that 512-point FFT > on real signals can be simplified to 256-point FFT. However, how about th=
e
> IFFT? The spectrum of real signals is conjugate symmetric about N/2. I ne=
ed
> to perform 512-point IFFT or there exists a simplification?
just do the reverse of each post-operation (as a pre-operation in the iFFT) and reverse each butterfly. real x[n] goes in, one *half* of the complex conjugate symmetric X[k] comes out. you may have an issue of what exactly to do with the Nyquist point since although it's known to be real (as is the DC point), it extends beyond X[N/2-1]. i have seen implementations that simply do not compute real part of X[N/2] (we know the imag part is zero), and i've seen an implementation that puts Re{ X[N/2] } into the Im{ X[0] } locations (because the imag part of X[0] is also known to be zero). in the latter, then N unique real numbers get transformed to N unique real numbers and the transformation remains perfectly invertible. r b-j
>On Mar 21, 9:22=A0pm, "alomar" <alomar.wang@n_o_s_p_a_m.gmail.com> >wrote: >> Dear all, >> >> I have a question about the FFT and IFFT on real signals. >> >> For example, I want to perform 512-point FFT/IFFT pair on real signals, >> x[0], x[1], ... , x[511]. There is a well-known method that 512-point
FFT
>> on real signals can be simplified to 256-point FFT. However, how about
th=
>e >> IFFT? The spectrum of real signals is conjugate symmetric about N/2. I
ne=
>ed >> to perform 512-point IFFT or there exists a simplification? > >just do the reverse of each post-operation (as a pre-operation in the >iFFT) and reverse each butterfly. > >real x[n] goes in, one *half* of the complex conjugate symmetric X[k] >comes out. > >you may have an issue of what exactly to do with the Nyquist point >since although it's known to be real (as is the DC point), it extends >beyond X[N/2-1]. i have seen implementations that simply do not >compute real part of X[N/2] (we know the imag part is zero), and i've >seen an implementation that puts Re{ X[N/2] } into the Im{ X[0] } >locations (because the imag part of X[0] is also known to be zero). >in the latter, then N unique real numbers get transformed to N unique >real numbers and the transformation remains perfectly invertible. > >r b-j >
Yes, the best way to figure out the whole things is to get hands dirty. The N-points FFT/IFFT pair on real signals can be simplified to N/2-points FFT/IFFT. I just put the X[N/2] (real only) in DC's imaginary part.