# How can I test an implementation of DFT for correctness?

A friend of mine implemented a DFT algorithm for a project we're working on, and we're not quite sure how to test whether or not its correct. We're only in the eleventh grade, so we have very little experience in Fourier Analysis.

I remembered reading somewhere that the Fourier transform of the square wave function was the sinc function, so we thought that if the output of the program was the sinc function then the implementation was correct, but we quickly realized it wouldn't be that simple. Below is a picture of what the program outputs (blue is DFT scaled logarithmically to be in decibels):

!

Below is essentially the same as above only with lines instead of a solid fill:

!

Hmm, well that doesn't look anything like the sinc function. After looking at the code, I realized it was actually a plot of $\sqrt{r^2 + i^2}$ where $r$ and $i$ are the real and imaginary parts of the DFT respectively. So now I'm out of ideas as to how to test the validity of this program.

Does the output look correct? What other tests can we perform to verify the implementation?

A very quick and easy test that catches all relevant structural mistakes follows from a fundamental property of the Fourier transform (and also its inverse): It is a square root of the sequence order reversal operator. That means applying your implementation twice on a data vector will reverse the sequence order and applying it four times will give your original data back.

Note that this requires the so called unitary scaling convention, where the Fourier transform and its inverse share the same scaling factor. Otherwise you will get back a scaled version of the original signal.

The simplest way to test your DFT algorithm is to get hold of a free FFT program and give it (and also your DFT program) identical inputs. There are many free versions of FFTs on the Internet (eg: http://sourceforge.net/projects/kissfft/). And an FFT is just a faster, more efficient, more accurate DFT.

I also see that your pictures seem to show a label of 'signed integer,' so you should make sure that the FFT code you use to compare to your DFT can handle that type of input.

Your pictures look suspect - it seems to be a square wave with a lot of ringing to it. Are you sure you're not using a sinc function as your input? And if those pictures are supposed to be outputs, why are they slightly asymmetrical?(note the differences of the left side/right side square wave edges).

FFT (or DFT) testing can actually get far more complicated, since you have to be familiar with testing strategies and inputs that exercise your code to the fullest. There is no one input test pattern that will detect all code bugs. And although an FFT will often give you a slightly different output than a DFT, those differences are not usually significant for many users.

• Ok, thanks for the advice! The inputs are square wave signal .wav files generated by audiocheck.net/audiofrequencysignalgenerator_squaretone.php, that's why it looks asymmetrical. We want to design a program that extracts data from song files in .wav format, so this was just an example to start us off. Can you suggest any resources (books, articles, video series, etc.) that could aid us in fully testing our implementations of signal processing algorithms? – user3002473 Apr 5 '15 at 3:13
• A Google search for FFT testing will reveal 100,000's of hits. And some of them are quite sophisticated. Algorithm testing can be a very complicated field - a casual user may run a program millions of times with different inputs before they find the one that overflows and crashes the program. Adequate testing is supposed to find those problems ahead of time. – user14819 Apr 5 '15 at 3:36

see what the output of your DFT is with all zeros for the input, $x[n]=0$ (output should be all zeros, $X[k]=0$).

then see what the output is for all zero input except $x[0]=1$ (should be all $X[k]=1$, depending on scaling).

then see what the output is for all zero input except for $x[1]=1$ (should be $X[k]=e^{-j2\pi k/N}$, with the same scaling).

then see what the output is for all zero input except for $x[2]=1$ (should be $X[k]=e^{-j4\pi k/N}$).

then see what the output is for all zero input except for $x[3]=1$ (should be $X[k]=e^{-j6\pi k/N}$).

etc.

if you do that for enough of these samples, it should be okay for general input unless there are numerical problems. is this a floating or fixed-point DFT?