FFT testing

I'm in the process of testing a hardware floating point FFT.  It is 
working well with the literally millions of vectors we have thrown at 
it, comparing well with a software FFT.  The test vectors to date have 
mostly been example vectors taken from the application.

Additionally, I tested it initially with the classic dual sines for a 
few selected cases while verifying the basic function, as well as 
impulses and constants.  My customer wants to test the "corner cases" to 
see what the limits of the hardware are, however I am coming up blank 
for tests that would stress it more than a dual sine (one sine with 
minimum amplitude, one with maximum).

Can anyone here suggest a better test to stress a floating point FFT?

On Jan 30, 9:08 pm, Ray Andraka <r...@andraka.com> wrote:
> I'm in the process of testing a hardware floating point FFT.  It is
> working well with the literally millions of vectors we have thrown at
> it, comparing well with a software FFT.  The test vectors to date have
> mostly been example vectors taken from the application.
>
> Additionally, I tested it initially with the classic dual sines for a
> few selected cases while verifying the basic function, as well as
> impulses and constants.  My customer wants to test the "corner cases" to
> see what the limits of the hardware are, however I am coming up blank
> for tests that would stress it more than a dual sine (one sine with
> minimum amplitude, one with maximum).
>
> Can anyone here suggest a better test to stress a floating point FFT?

Ray,

We usually test our FFTs with minimum of the following, hope this
helps:

In the following, the value of N is the length of the FFT.

  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, ....

These tests have been carefully chosen to expose design issues
commonly found in FFT logic.  The single FFT tests are designed to
expose problems with the arithmetic or control used when processing a
single set of FFT data.  The multi FFT tests are designed to expose
problems with the logic that controls how multiple sets of data are
passed through the FFT logic.

tdillon@dilloneng.com wrote:

> On Jan 30, 9:08 pm, Ray Andraka <r...@andraka.com> wrote:
> 
>>I'm in the process of testing a hardware floating point FFT.  It is
>>working well with the literally millions of vectors we have thrown at
>>it, comparing well with a software FFT.  The test vectors to date have
>>mostly been example vectors taken from the application.
>>
>>Additionally, I tested it initially with the classic dual sines for a
>>few selected cases while verifying the basic function, as well as
>>impulses and constants.  My customer wants to test the "corner cases" to
>>see what the limits of the hardware are, however I am coming up blank
>>for tests that would stress it more than a dual sine (one sine with
>>minimum amplitude, one with maximum).
>>
>>Can anyone here suggest a better test to stress a floating point FFT?
> 
> 
> Ray,
> 
> We usually test our FFTs with minimum of the following, hope this
> helps:
> 
> In the following, the value of N is the length of the FFT.
> 
>   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, ....
> 
> These tests have been carefully chosen to expose design issues
> commonly found in FFT logic.  The single FFT tests are designed to
> expose problems with the arithmetic or control used when processing a
> single set of FFT data.  The multi FFT tests are designed to expose
> problems with the logic that controls how multiple sets of data are
> passed through the FFT logic.
> 

Tom,

Thanks. Yes, those are the similar to the tests I run.  They all fall 
under one of the following:  constant input, impulse inputs at various 
offsets, single sinusoids (which we do for debug and initial 
verification) and dual sinusoids.  I also run a suite of double 
impulses.  The dual sines and double impulses are designed to expose 
overlap and precision issues (one has a large amplitude, one a small 
amplitude).  The inputs to all these are complex.  I'm pretty sure these 
tests cover the "corner cases" but I don't have a proof of that.  The 
customer is looking for something to "stress" the design, and in 
particular the floating point arithmetic.  Smith and Smith refer to a 
similar set of 4 classes of tests, but again the stated reason is for 
debug rather than rigorous verification.  I was hoping that someone had 
a set of rigorous verification or error quantification sets to run the 
FFT against.

On Jan 30, 7:08 pm, Ray Andraka <r...@andraka.com> wrote:
> I'm in the process of testing a hardware floating point FFT.
>
>  My customer wants to test the "corner cases" to
> see what the limits of the hardware are, however I am coming up blank
> for tests that would stress it more than a dual sine (one sine with
> minimum amplitude, one with maximum).
>
> Can anyone here suggest a better test to stress a floating point FFT?

It's hard to tell what the corners are when you don't give the
processor's functions, environment or specifications, but why let that
stop us?

Numeric concerns:
1) Overflow behavior: yes it's broke, but is it broke like we want?
2) Underflow behavior: rounding and denormalized behavior
3) Are NaN's supported: at input, output
4) How are illegal inputs responded to, replaced, ignored?

Functional concerns:
1) If there is a scaling function, can any value produce divide by 0?
2) Has every combination of transform size and type and data format
been tested over the range of data values? This might take until the
sun burns dim so you might need to convince yourself and your customer
what is an adequate subset. Sometimes completeness in the
architectural tests is used to justify the subseting of functional
tests.
3) Are illegal inputs or outputs reported, or any other status?

Architectural concerns:
1) Are all register and memory locations exercised in all relevant
states (0/1 bitwise, specified values for bit groups)?
2) Are all ports and paths exercised in all relevant states?

Is the comparison software a bit exact emulation?

Consider any that are appropriate for you processor.

Dale B. Dalrymple
http://dbdimages.com

On Jan 30, 7:08 pm, Ray Andraka <r...@andraka.com> wrote:
> I'm in the process of testing a hardware floating point FFT.
>
>  My customer wants to test the "corner cases" to
> see what the limits of the hardware are, however I am coming up blank
> for tests that would stress it more than a dual sine (one sine with
> minimum amplitude, one with maximum).
>
> Can anyone here suggest a better test to stress a floating point FFT?

It's hard to tell what the corners are when you don't give the
processor's functions, environment or specifications, but why let that
stop us?

Numeric concerns:
1) Overflow behavior: yes it's broke, but is it broke like we want?
2) Underflow behavior: rounding and denormalized behavior
3) Are NaN's supported: at input, output
4) How are illegal inputs responded to, replaced, ignored?

Functional concerns:
1) If there is a scaling function, can any value produce divide by 0?
2) Has every combination of transform size and type and data format
been tested over the range of data values? This might take until the
sun burns dim so you might need to convince yourself and your customer
what is an adequate subset. Sometimes completeness in the
architectural tests is used to justify the subseting of functional
tests.
3) Are illegal inputs or outputs reported, or any other status?

Architectural concerns:
1) Are all register and memory locations exercised in all relevant
states (0/1 bitwise, specified values for bit groups)?
2) Are all ports and paths exercised in all relevant states?

Is the comparison software a bit exact emulation?

Consider any that are appropriate for you processor.

Dale B. Dalrymple
http://dbdimages.com

On Jan 30, 7:08 pm, Ray Andraka <r...@andraka.com> wrote:
> I'm in the process of testing a hardware floating point FFT.
>
>  My customer wants to test the "corner cases" to
> see what the limits of the hardware are, however I am coming up blank
> for tests that would stress it more than a dual sine (one sine with
> minimum amplitude, one with maximum).
>
> Can anyone here suggest a better test to stress a floating point FFT?

It's hard to tell what the corners are when you don't give the
processor's functions, environment or specifications, but why let that
stop us?

Numeric concerns:
1) Overflow behavior: yes it's broke, but is it broke like we want?
2) Underflow behavior: rounding and denormalized behavior
3) Are NaN's supported: at input, output
4) How are illegal inputs responded to, replaced, ignored?

Functional concerns:
1) If there is a scaling function, can any value produce divide by 0?
2) Has every combination of transform size and type and data format
been tested over the range of data values? This might take until the
sun burns dim so you might need to convince yourself and your customer
what is an adequate subset. Sometimes completeness in the
architectural tests is used to justify the subseting of functional
tests.
3) Are illegal inputs or outputs reported, or any other status?

Architectural concerns:
1) Are all register and memory locations exercised in all relevant
states (0/1 bitwise, specified values for bit groups)?
2) Are all ports and paths exercised in all relevant states?

Is the comparison software a bit exact emulation?

Consider any that are appropriate for you processor.

Dale B. Dalrymple
http://dbdimages.com

On Jan 31, 4:08 am, Ray Andraka <r...@andraka.com> wrote:
[...]
>
> Can anyone here suggest a better test to stress a floating point FFT?

Now I haven't verified a floating point FFT, but for a fixed point one
I used code coverage to point out areas of the logic that did not get
exercised during verification. I know that this cannot be taken as an
indicator for corner cases, but allows to look at the verification
from a different point of view. Maybe that is a starting point to
determine new corner cases and verify them?

Cheers,

Guenter