14
$\begingroup$

I'm involved with an effort to implement an FFT algorithm, and am curious what the recommended advice is for the input test data to use -- and why! -- and what accuracy to expect.

On test inputs, I've found a little guidance in old Usenet posts that I'll post as an answer, but it's just one person's suggestions without a lot of justification -- I haven't found anything that looks like a solid answer.

On accuracy, Wikipedia says that the error should be O(e log N), but what's a reasonable expectation in absolute terms?

Edit to add: The actual tests are in a form where I have stored arrays of input data and pre-computed "reference" output data to compare to, so I don't necessarily need something with a closed-form solution.

|improve this question
$\endgroup$
12
$\begingroup$

If you want to verify an FFT algorithm for correctness, in the sense that it performs the desired function that has the known properties of the discrete Fourier transform, then you can use the approach proposed in:

Ergün, Funda. (1995, June). Testing multivariate linear functions: Overcoming the generator bottleneck. In Proc. Twenty-Seventh Ann. ACM Symp. Theory of Computing. (p. 407–416).

The above paper is referenced by the makers of FFTW as their method of choice for verifying that a particular FFT implementation does what it should. The proposed technique distills the function into three main components that are verified with separate tests:

  • Linearity: The DFT (along with its other cousin transforms in the Fourier family) is a linear operator, so for all values of $a_1, a_2, x_1[n], x_2[n]$, the following equation must hold:

$$ \mathrm{FFT}(a_1 x_1[n] + a_2 x_2[n]) = a_1\mathrm{FFT}(x_1[n]) + a_2\mathrm{FFT}(x_2[n]) $$

  • DFT of the unit impulse: A time-domain signal equal to the Kronecker delta function is applied to the input of the FFT algorithm and the output is checked against the known DFT of the unit impulse function (it transforms to a constant value in all output bins). If the FFT algorithm provides an IFFT, it can be tested in reverse to show that it yields the unit impulse function again.

  • Time shift: Two sets of data are applied to the input of the FFT algorithm; the only difference between the two in the time domain is a constant time shift. Based on the known properties of the DFT, this should effect a known linear phase shift between the two signals' frequency domain representations, where the slope of the phase shift is proportional to the time shift.

The authors of the paper assert that these tests are sufficient to validate the correctness of an FFT implementation. I've not used this technique in the past, but it does seem to make sense, and I would trust FFTW's authors (who have produced a great piece of free software) as credible authorities on good approaches to the validation problem.

|improve this answer
$\endgroup$
  • $\begingroup$ Thanks! Do the authors have any suggestion for values of a1, a2, x1[n] and x2[n] to use in the linearity test (or do they assert that this largely doesn't matter)? And, for that matter, for the data sets to use for the time-shift test? $\endgroup$ – Brooks Moses Nov 12 '11 at 5:17
  • 3
    $\begingroup$ Having actually read the paper, I can answer my own question: The authors do not describe how one performs the linearity test, but instead assume that one has done it sufficient to prove that it is true for "most inputs". Also, this paper is describing a proof of exact correctness assuming exact arithmetic; it is not describing a means for characterizing the numerical error in an approximate program (as necessarily results from using finite-precision arithmetic). $\endgroup$ – Brooks Moses Nov 12 '11 at 7:24
  • $\begingroup$ I'll go ahead and mark this as accepted, because it's certainly the best answer so far -- but I'm still very interested in other answers that cover what test input data sets to use (and why), or details of expected accuracy. Thanks! $\endgroup$ – Brooks Moses Nov 15 '11 at 0:22
  • 2
    $\begingroup$ There are really two components to your question on validating an FFT algorithm: validating its correctness and measuring its numerical accuracy. My answer only addressed the first. It's tough to make any statements on what numerical accuracy to expect, because it is inherently implementation-dependent. The type of arithmetic (e.g. fixed versus floating point), the structure used to implement the algorithm, the FFT length (i.e. the number of stages used to decompose the problem), any shortcuts taken to improve execution speed, etc. will all play a factor and are difficult to generalize. $\endgroup$ – Jason R Nov 15 '11 at 2:45
  • $\begingroup$ Good point; I probably should have asked those as separate questions. $\endgroup$ – Brooks Moses Nov 18 '11 at 6:29
5
$\begingroup$

As mentioned in the question, I did find one set of suggestions in archived comp.dsp Usenet posts ( http://www.dsprelated.com/showmessage/71595/1.php , post by "tdillon"):

A.Single FFT tests - N inputs and N outputs
 1.Input random data
 2.Inputs are all zeros
 3.Inputs are all ones (or some other nonzero value)
 4.Inputs alternate between +1 and -1.
 5.Input is e^(8*j*2*pi*i/N) for i = 0,1,2, ...,N-1. (j = sqrt(-1))
 6.Input is cos(8*2*pi*i/N) for i = 0,1,2, ...,N-1.
 7.Input is e^((43/7)*j*2*pi*i/N) for i = 0,1,2, ...,N-1. (j = sqrt(-1))
 8.Input is cos((43/7)*2*pi*i/N) for i = 0,1,2, ...,N-1.

B.Multi FFT tests - run continuous sets of random data
 1.Data sets start at times 0, N, 2N, 3N, 4N, ....
 2.Data sets start at times 0, N+1, 2N+2, 3N+3, 4N+4, ....

The thread also suggests doing two sines, one with a large amplitude and one with a small amplitude.

As I say in the main question, I'm not sure if this is a particularly good set of answers, or if it's very complete, but I'm putting here so people can vote and comment on it.

|improve this answer
$\endgroup$
  • 1
    $\begingroup$ What would "1. Input random data" reveal? $\endgroup$ – Dilip Sarwate Nov 12 '11 at 1:46
  • 1
    $\begingroup$ @DilipSarwate: Fuzz-testing can be useful to reveal crashes. And, depending on the type of noise input (say, pink noise or white noise), could be useful in checking that the overall energy distribution is as expected. $\endgroup$ – smokris Nov 12 '11 at 2:46
  • 2
    $\begingroup$ @Dilip - My fft "smoke test" is that ifft(fft(random_stuff)) ~= random_stuff. $\endgroup$ – hotpaw2 Nov 12 '11 at 8:01
  • $\begingroup$ @hotpaw2 So "random stuff" means you just see a bunch of numbers that don't seem to fit any pattern such as a sinusoid? or do you test the output to see if the $N$ numbers can be considered to be "random" e.g. take the input to be complex Gaussians $\mathcal{CN}(0,1)$ and then do a hypothesis test to see if (with, say, $99\%$ confidence) the scatter plot of the FFT output looks like a scatter plot that would be obtained from $N$ $\mathcal{CN}(0,1)$ random samples? $\endgroup$ – Dilip Sarwate Nov 12 '11 at 12:59
  • 2
    $\begingroup$ @Dilip : I'm a hardware guy. I wanted something that might toggle a high percentage of all the bits in all the multipliers and CSAs. $\endgroup$ – hotpaw2 Nov 12 '11 at 16:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.