|
Hi friends, the source code for the Real FFT can be downloaded from ADI. It implements a real N-point FFT using a N/2-point complex FFT, plus some signal reassembling. If the input signal is however real _and_ symmetric (as is the case for a linear-phase frequency response), additional speed-up can be achieved as compared to the Real FFT, because the resulting imaginary part does not have to be calculated. Has anybody implemented this optimization for the Real FFT and is willing to share? Regards, Andor |
|
|
Real Symmetric FFT
Started by ●December 9, 2003
Reply by ●December 9, 20032003-12-09
|
Andor Bariska- > the source code for the Real FFT can be downloaded from ADI. It > implements a real N-point FFT using a N/2-point complex FFT, plus > some signal reassembling. > > If the input signal is however real _and_ symmetric (as is the case > for a linear-phase frequency response), additional speed-up can be > achieved as compared to the Real FFT, because the resulting imaginary > part does not have to be calculated. Just curious, but how can a real signal in time domain be symmetric? Since it has no imaginary component, symmetric w.r.t. to what? To midpoint in analysis framesize? To amplitude? Jeff Brower system engineer Signalogic |
Reply by ●December 9, 20032003-12-09
|
> Date: Tue, 09 Dec 2003 07:48:47 -0600 > From: Jeff Brower <> > Subject: Re: Real Symmetric FFT > > Andor Bariska- > > > the source code for the Real FFT can be downloaded from ADI. It > > implements a real N-point FFT using a N/2-point complex FFT, plus > > some signal reassembling. > > > > If the input signal is however real _and_ symmetric (as is the case > > for a linear-phase frequency response), additional speed-up can be > > achieved as compared to the Real FFT, because the resulting imaginary > > part does not have to be calculated. > > Just curious, but how can a real signal in time domain be symmetric? > Since it has no imaginary component, symmetric w.r.t. to what? To > midpoint in analysis framesize? > To amplitude? > > Jeff Brower > system engineer > Signalogic > Hi Jeff, I do not think it really does matter if a real signal in time domain is/isn't symmetric. The problem is an abstract math problem. It has been attended: ccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc c c Subroutine RQEFT( X, N, M, S, C, Nmax2 ) c c A real quarter wave even (QE) symmetric sequence of length N=2**M c has the form c X(0),X(1),...,X(N/2-1),X(N/2-1),...,X(1),X(0) c c While the array X must have length N, only the first N/2 elements c are accessed. c c S - array of sin() table initialized to length Nmax2>=2*N by FFTI c C - array of cos() table initialized to length Nmax2>=2*N by FFTI c c This routine requires approximately N*M+N floating point operations. c c The output from this routine will agree with the forward FFT (RFFTF) c applied to the real sequence c X(0),X(1),....,X(N/2-1),X(N/2-1),...,X(1),X(0). c c c Steve Kifowit, November 1997 c c Reference: c Paul N. Swarztrauber, Symmetric FFTs, Mathematics of Computation, c 47 (1986), pp. 323-346. c cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc Regards, Andrew -- |
