testing FFTs

On Fri, 04 Jul 2003 17:23:36 -0700, Bob wrote:
> 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?

Check out this paper:

Funda Ergun, "Testing multivariate linear functions: Overcoming the
generator bottleneck, Proc. 27th ACM Symposium on the Theory of Computing,
407-416 (1995).

This is the method that the FFTW package uses.

There are a lot of seemingly good tests that will fail to produce failures
for subtle errors.  The above method tests the linearity, impulse
response, and shift properties of the DFT.

-- 
Matthew Donadio (m.p.donadio@ieee.org)

On Fri, 04 Jul 2003 22:58:00 -0400, robert bristow-johnson 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.

It is more likely than you think.  When I was working on some FFT code I
was able to introduce a few errors that the above method did not pick up. 
My other post in this thread has the reference for a better method. 
basically, you test some of the properties of the FFT to verify
correctness.

-- 
Matthew Donadio (m.p.donadio@ieee.org)

Matthew Donadio wrote:
> 
> It is more likely than you think.  

I agree.

What about using the rather interesting result that the inverse 
fft can be calulated for A, by (Matlab/Octave notation):

    0) B = imag (A) + i * real (A)
    1) C = fft (B) / N
    2) D = imag (C) + i * real (C)

where D is the ifft of A.

If both this methods and the other method of calculaing the
inverse fft works and their results agree in the frequency
domain then it pretty unlikely that its wrong.

Erik
-- 
+-----------------------------------------------------------+
  Erik de Castro Lopo  nospam@mega-nerd.com (Yes it's valid)
+-----------------------------------------------------------+
"In civilian equipment, such as computers, the number
of components alone makes miniaturization essential if
the computer is to be housed in a reasonable-sized
building." Electronics Oct. 1, 1957, p. 178

allnor@tele.ntnu.no (Rune Allnor) wrote in message news:<f56893ae.0307050903.7598ce29@posting.google.com>...
> 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. 

Having saved your good night sleep, I'll try to secure your afternoon 
nap as well: "l" was also updated at the end of the foor loop.

Rune