Hi Folks, A few weeks ago, I posted a query on FFT scaling. After your kind replys, I got it working. I was able to get the real only FFT to work. By this I mean, there was no imaginary data input. However how does one test a complex FFT to make sure it is working? Is there a datafile that could be generated and what would the output result look like? Also...In what sort of application would a complex fft be used? Thanks alot Bob
testing FFTs
Started by ●July 4, 2003
Reply by ●July 4, 20032003-07-04
Bob wrote:> > Hi Folks, > > A few weeks ago, I posted a query on FFT scaling. > After your kind replys, I got it working. I was > able to get the real only FFT to work. By this > I mean, there was no imaginary data input. > > However how does one test a complex FFT to make sure > it is working? Is there a datafile that could > be generated and what would the output result look > like?One very simple test would be to generate a complex sinusoid, x[nT] = r*e^{i*2*pi*f*n*T}, where T is 1/Fs Fs is the sample rate, and f lies between -Fs/2 and +Fs/2. If you use a rectangular window you should see a sinc-like patter whose peak moves around according to f.> Also...In what sort of application would a complex fft be used?There is a way to perform an FFT on 2N point real points using an N-point FFT. In other applications the signal itself can be complex. A very common application in which this is true is when dealing with digital communication signals in which you are working with baseband I and Q samples. This technique is called, amongst other things, quadrature modulation/demodulation. Rick Lyons' book "Understanding Digital Signal Processing" has a lot of information on quadrature modulation and demodulation. -- % Randy Yates % "...the answer lies within your soul %% Fuquay-Varina, NC % 'cause no one knows which side %%% 919-577-9882 % the coin will fall." %%%% <yates@ieee.org> % 'Big Wheels', *Out of the Blue*, ELO http://home.earthlink.net/~yatescr
Reply by ●July 4, 20032003-07-04
In article 3F062329.31186F88@ieee.org, Randy Yates at yates@ieee.org wrote on 07/04/2003 21:00:> Bob wrote: >> >> Hi Folks, >> >> A few weeks ago, I posted a query on FFT scaling. >> After your kind replys, I got it working. I was >> able to get the real only FFT to work. By this >> I mean, there was no imaginary data input. >> >> However how does one test a complex FFT to make sure >> it is working? Is there a datafile that could >> be generated and what would the output result look >> like? > > One very simple test would be to generate a complex > sinusoid, x[nT] = r*e^{i*2*pi*f*n*T}, where T is 1/Fs > Fs is the sample rate, and f lies between -Fs/2 and +Fs/2. > If you use a rectangular window you should see a sinc-like > patter whose peak moves around according to f.except if the frequency of the complex sinusoid is mid-bin. i.e. f = n*Fs/N where N is the FFT size and -N/2 < n < N/2 .>> Also...In what sort of application would a complex fft be used? > > There is a way to perform an FFT on 2N point real points using an N-point > FFT.yeah, you can't work out the details but the odd samples go into the imaginary parts of the FFT input and then you have to do a little massaging on the output.> In other applications the signal itself can be complex. A very > common application in which this is true is when dealing with > digital communication signals in which you are working with > baseband I and Q samples. This technique is called, amongst other > things, quadrature modulation/demodulation. Rick Lyons' book "Understanding > Digital Signal Processing" has a lot of information on quadrature modulation > and demodulation.one way i would recommend testing an FFT is to take any arbitrary input, FFT it, then inverse FFT, and finally subtract the original input from the result. it's unlikely that both the FFT and iFFT will err in a way to undo each other's mistakes. r b-j
Reply by ●July 4, 20032003-07-04
Bob wrote:> Hi Folks, > > A few weeks ago, I posted a query on FFT scaling. > After your kind replys, I got it working. I was > able to get the real only FFT to work. By this > I mean, there was no imaginary data input. > > However how does one test a complex FFT to make sure > it is working? Is there a datafile that could > be generated and what would the output result look > like?This was discussed a few months ago ("Testing FFT routines" thread I think), so have a look for it in google.> Also...In what sort of application would a complex fft be used?Any place you have a complex (aka "analytic") signal I guess. e.g. As the output of a bandpass sampling arrangement which gives you complex samples with sampling frequency > bandwidth (instead of the usual twice maximum frequency for base band signals). You can also use 1 complex FFT to do 2 real FFT's (1 in the real part and 1 in the imaginary part). The separate DFT's of the two real signals can be extracted from the complex FFT output using simple additional step which relies on the symmetry of the DFT of real signals. (Sometimes you don't even need to do this last step if you're using the FFT for fast convolution with a real impulse response.) Regards -- Adrian Hey
Reply by ●July 5, 20032003-07-05
In article BB2BA8E8.1EF6%rbj@surfglobal.net, robert bristow-johnson at rbj@surfglobal.net wrote on 07/04/2003 21:58:> In article 3F062329.31186F88@ieee.org, Randy Yates at yates@ieee.org wrote > on 07/04/2003 21:00: >...>> >> One very simple test would be to generate a complex >> sinusoid, x[nT] = r*e^{i*2*pi*f*n*T}, where T is 1/Fs >> Fs is the sample rate, and f lies between -Fs/2 and +Fs/2. >> If you use a rectangular window you should see a sinc-like >> patter whose peak moves around according to f. > > except if the frequency of the complex sinusoid is mid-bin. i.e. f = n*Fs/N > where N is the FFT size and -N/2 < n < N/2 .i meant to add that you don't see the sinc but you'll see a single bin spike at the nth bin.>>> Also...In what sort of application would a complex fft be used? >> >> There is a way to perform an FFT on 2N point real points using an N-point >> FFT. > > yeah, you can't work out the details but the odd samples go into the > imaginary parts of the FFT input and then you have to do a little massaging > on the output.and here i meant to say that you *can* work out the details. whatever. r b-j
Reply by ●July 5, 20032003-07-05
stenasc@yahoo.com (Bob) wrote:>Hi Folks, > >A few weeks ago, I posted a query on FFT scaling. >After your kind replys, I got it working. I was >able to get the real only FFT to work. By this >I mean, there was no imaginary data input. > >However how does one test a complex FFT to make sure >it is working? Is there a datafile that could >be generated and what would the output result look >like?I typically code my FFT's in C first, before implementing on a DSP. Then, I either get a hold of a known data set input and output, and confirm against that. Or else, you can input a clean sine wave ( fabricated in C ), so that it resides on a single bin ... and confirm that it ends up there, and of the correct amplitude. Once the C version works, the DSP assembly version can be confirmed against it.> >Also...In what sort of application would a complex fft be used?I know there are some applications that require both the real and imaginary info. What comes to mind also is that the complex fft can be used to perform 2 real fft's. Regards, Robert www.gldsp.com ( modify address for return email ) www.numbersusa.com www.americanpatrol.com
Reply by ●July 5, 20032003-07-05
robert bristow-johnson <rbj@surfglobal.net> wrote:>one way i would recommend testing an FFT is to take any arbitrary input, FFT >it, then inverse FFT, and finally subtract the original input from the >result. it's unlikely that both the FFT and iFFT will err in a way to undo >each other's mistakes.Ah yeah, that's one I've done before too. Robert www.gldsp.com ( modify address for return email ) www.numbersusa.com www.americanpatrol.com
Reply by ●July 5, 20032003-07-05
stenasc@yahoo.com (Bob) wrote in message news:<20540d3a.0307041523.7f672cd4@posting.google.com>...> Hi Folks, > > A few weeks ago, I posted a query on FFT scaling. > After your kind replys, I got it working. I was > able to get the real only FFT to work. By this > I mean, there was no imaginary data input. > > However how does one test a complex FFT to make sure > it is working? Is there a datafile that could > be generated and what would the output result look > like?When I went to college, the DSP teacher handed out a pascal code for complex-valued FFT. What we got was the source code printed on a piece of paper. The teacher said that was the routine everybody used who didn't write commercial code, so I had quite high expectations when I sat down typing it into my own computer. However, I didn't get anything sane-looking out when I tested the routine. I tried to use one single sine located exactly on one of the Fourier frequencies, but no such thing as a line spectrum. I checked the code, I had written everything down as printed, I asked the professor, but once he heard I couldn't find any typos he couldn't help me, nor could he suggest where to look for errors... quite frustrating. I left the code alone and went on with other stuff. After a few weeks I thought it was too bad not having a working FFT routine, so I decided to give it another try before I attempted coding the whole thing from scratch. I found the error. The code we had got from the teacher used the symbol "l" (lowercase L) as an internal indexing variable. Even worse, it was used only once in the code, in a setting like for k=l to m do In the printed text it was impossible to distinguish from the number 1, which I had written when I type copied the code. Once that blunder was corrected, the code worked just fine. I have never used lowercase L as variable name in any of my code ever since.> Also...In what sort of application would a complex fft be used?All over the place. First, with an FFT routine that accepts complex data as input, you have the IFFT routine for free. The difference between the FFT and IFFT is basically a scaling of the result. You need to pay some attention to phase conjugates as well, but that's details. The only reason I can see for writing specialized, real-only FFTs, are high-performance real time systems. In some types of applications the complex forward FFT is very useful. I have worked with data that consist of time series recorded by sensor arrays. Lots of algorithms that are useful for these kinds of data can be formulated as 2D DFTs. While the 2D DFT can be implemented as two 1D DFT pairs, time <-> frequency and aperture <-> wavenumber, and the transform pairs commute (i.e. it makes no formal difference what order one chooses to compute the time to frequency transform and aperture to wavenumber transform), most algorithms are based on first transforming the real-valued data from time to frequency, and then compute some sort of transform of the now complex-valued spatial data contained in each (frequency, space) vector. Yep, Jerry and Randy, even if the ADCs in these applications sample real-valued data, after the temporal transform I regard the spatial data in each frequency vector as "complex data", no different than if they should be provided by a complex-valued ADC. < running for cover... > Rune> Thanks alot > Bob
Reply by ●July 5, 20032003-07-05
Rune Allnor wrote:> > ... I found the error. The code > we had got from the teacher used the symbol "l" (lowercase L) > as an internal indexing variable. Even worse, it was used only once > in the code, in a setting likeHelp me avoid sleepless nights. If the only appearance of the offending variable was in> > for k=l to m do >What was the starting value of k when the line was executed? ...> > Yep, Jerry and Randy, even if the ADCs in these applications sample > real-valued data, after the temporal transform I regard the spatial > data in each frequency vector as "complex data", no different than > if they should be provided by a complex-valued ADC.After the transform, that's what it is. The storage needed for N points tells the whole story.> < running for cover... >Chicken!> RuneJerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●July 5, 20032003-07-05
Jerry Avins <jya@ieee.org> wrote in message news:<3F06DD76.2AFBE9D7@ieee.org>...> Rune Allnor wrote: > > > > ... I found the error. The code > > we had got from the teacher used the symbol "l" (lowercase L) > > as an internal indexing variable. Even worse, it was used only once > > in the code, in a setting like > > Help me avoid sleepless nights. If the only appearance of the offending > variable was in > > > > for k=l to m do > > > What was the starting value of k when the line was executed?Yep, you're right. l had to be initialized somewhere. As far as I remember it was initialized at the very start at the procedure.> ... > > > > Yep, Jerry and Randy, even if the ADCs in these applications sample > > real-valued data, after the temporal transform I regard the spatial > > data in each frequency vector as "complex data", no different than > > if they should be provided by a complex-valued ADC. > > After the transform, that's what it is. The storage needed for N points > tells the whole story. > > > < running for cover... > > > Chicken!Better safe than sorry... Rune> > Jerry
