Turn on suggestions

Auto-suggest helps you quickly narrow down your search results by suggesting possible matches as you type.

Showing results for

- Intel Community
- Software Development SDKs and Libraries
- Intel® Integrated Performance Primitives
- Avoiding Time Aliasing with FFTs

- Subscribe to RSS Feed
- Mark Topic as New
- Mark Topic as Read
- Float this Topic for Current User
- Bookmark
- Subscribe
- Mute
- Printer Friendly Page

daven-hughes

Beginner

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

09-29-2013
03:14 PM

48 Views

Avoiding Time Aliasing with FFTs

I am trying to design a convolution function with FFTs. The FFT functions state objects have fixed buffer sizes and I need to decouple the sizes of the input and output arrays to avoid time aliasing (wrapping).

First of all I know that there's an IppsConv function, but I need my own implementation for a few reasons.

The convolution operation takes input with size n and kernel with size m and produces an output vector with size n+m-1. Using an ippsFFT routine, you must specify in the state object the sizes of the input and output.

Now, you can use separate state objects for forward FFT and inverse FFT, but in either case both input arrays are equal sizes, so different-order states will simply up- or down-sample the signal, not give you the 'tail' of the convolution.

Relevant code:

[cpp]if(useFFT)

{

ippsFFTFwd_RToCCS_32f (timeInput, (Ipp32f*) freqInput, stateOrder7, 0 );

ippsMul_32fc_I (freqImpulse + 1, freqInput + 1, inputSize / 2 );

ippsFFTInv_CCSToR_32f ((Ipp32f*) freqInput, convDest, stateOrder8, 0 );

}

else

{

ippsConv_32f(timeImpulse, kernelSize, timeInput, inputSize, convDest);

}[/cpp]

I attached the results of using convolution and states with different orders.

Link Copied

5 Replies

Thomas_Jensen1

Beginner

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

09-29-2013
11:45 PM

48 Views

I have a few comments:

First of all, I know for sure that IPP image convolution functions internally switch to FFT when some size is larger than X.

Thus, you might now need to implement your own FFT for your vector...

Second, to prevent time domain wrapping, simply append zeroes to your buffer. If you buffer is N and your kernel is M, then expand the buffer to N+M-1 and put zeroes in at the right/bottom. Then FFT/DFT the entire buffer, and just use the left/top of the result.

Igor_A_Intel

Employee

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

09-30-2013
01:08 AM

48 Views

Hi,

I haven't found any question in your post, so I guess that you just share your experience... There are a lot of different interesting FFT applications... To remove wrapping you can just cut an output from Conv function. For example ippsCrossCorr has a bit different API that makes possible to remove wrapping with correspoding input parameters like lowLag and dstLen.

regards, Igor

daven-hughes

Beginner

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

09-30-2013
06:24 AM

48 Views

Oh, I must have edited out my question.

The question is how do I achieve the exaclty the same result as the ippsConv function with the usual convolution algorithm in frequency domain (fft input -> complex multiply kernel and input -> ifft)

Thanks

daven-hughes

Beginner

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

09-30-2013
08:19 AM

48 Views

Thomas Jensen wrote:

First of all, I know for sure that IPP image convolution functions internally switch to FFT when some size is larger than X.

Thus, you might now need to implement your own FFT for your vector...

There's a DSP convolution algorithm too - like I say I know about it, but I need a custom implementation.

Thomas Jensen wrote:

Second, to prevent time domain wrapping, simply append zeroes to your buffer. If you buffer is N and your kernel is M, then expand the buffer to N+M-1 and put zeroes in at the right/bottom. Then FFT/DFT the entire buffer, and just use the left/top of the result.

I understand the theory, zero padding etc, but my problem is implementing it with the IPP functions.

Basically, I don't know how to tell the FFTInv function "use order 7 for the input but use order 8+ (for padding) for the output." You can only give it one state object, with one order.

daven-hughes

Beginner

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

09-30-2013
12:40 PM

48 Views

Okay, I've figured it out!

I needed to pad the forward FFT as well, thought it was just the inverse that needed padding.

For more complete information about compiler optimizations, see our Optimization Notice.