Using Fast Fourier Transform

Fast Fourier Transform (FFT) is a universal method to increase performance of data processing, especially in the field of digital signal processing where filtering is essential.

The convolution theorem states that filtering of two signals in the spatial domain can be computed as point-wise multiplication in the frequency domain. The data transformation to and from the frequency domain is usually performed using the Fourier transform. You can apply the Finite Impulse Response (FIR) filter to the input signal by using Intel IPP FFT functions, which are optimized for Intel® processors. You can also increase the data array length to the next greater power of two by padding the array with zeroes and then applying the forward FFT function to the input signal and the FIR filter coefficients. Fourier coefficients obtained in this way are multiplied point-wise and the result can easily be transformed back to the spatial domain. The performance gain achieved by using FFT may be very significant.

If the applied filter is the same for several processing iterations, then the once calculated filter coefficients can be reused in each iteration. The twiddle tables and the bit reverse tables are created in the initialization function for the forward and inverse transforms at the same time. The following example presents the main operations of this kind of filtering:

ippsFFTInitAlloc_R_32f( &pFFTSpec, fftord, IPP_FFT_DIV_INV_BY_N, ippAlgHintNone );            
 
/// perform forward FFT to put source data xx to frequency domain            
ippsFFTFwd_RToPack_32f( xx, XX, pFFTSpec, 0 ); 
            
/// perform forward FFT to put filter coefficients hh to frequency domain          
ippsFFTFwd_RToPack_32f( hh, HH, pFFTSpec, 0 );
            
/// point-wise multiplication in freq-domain is convolution           
ippsMulPack_32f_I( HH, XX, fftlen );
            
/// perform inverse FFT to get result in time-domain
ippsFFTInv_PackToR_32f( XX, yy, pFFTSpec, 0 );
            
/// free FFT tables
ippsFFTFree_R_32f( pFFTSpec );

The zeros in the example above could be pointers to the external memory, which is another way to increase performance. Another way to significantly improve performance is using FFT and multiplication for processing large size data.

The signal processing FIR filter in Intel IPP is implemented using FFT, and you do not need to create a special implementation of the FIR functions.

Copyright © 2008 - 2011, Intel Corporation. All rights reserved.