<< Chapter < Page Chapter >> Page >

The source code has a few subtle differences that are not revealed in the pseudocode. The pseudocode in [link] requires an array of complex numbers x n for input, but the source code requires a reference to an array of complex numbers with a stride A stride of n would indicate that only every n t h term is being referred to. – this avoids copying x n into three separate arrays, viz. x 2 n 2 , x 4 n 4 + 1 and x 4 n 4 - 1 , with every invocation of [link] . The subtle complication arises due to the cyclic shifting of the x 4 n 4 - 1 term; the negative shifting results in pointers that reference data before the start of the array. Rather than immediately wrapping the references around to end of the array such that they always point to validdata, the recursion proceeds until the base cases are reached before any adjustment is performed. Once at the leaves of the recursion, any pointers that reference data lying before the start of the input array are incremented by N elements, In this case, N refers to the size of the outer most transform rather than the size of the sub-transform. so as to point to the correct data.

  IF  N = 1     RETURN  x 0   ELSIF  N = 2      X 0 x 0 + x 1      X 1 x 0 - x 1   ELSE      U k 2 = 0 , , N / 2 - 1 TANGENTFFT 4 N / 2 ( x 2 n 2 )      Z k 4 = 0 , , N / 4 - 1 TANGENTFFT 8 N / 4 ( x 4 n 4 + 1 )      Z k 4 = 0 , , N / 4 - 1 ' TANGENTFFT 8 N / 4 ( x 4 n 4 - 1 )     FOR  k = 0  to  N / 4 - 1        X k U k + ( ω N k s N / 4 , k Z k + ω N - k s N / 4 , k Z k ' )        X k + N / 2 U k - ( ω N k s N / 4 , k Z k + ω N - k s N / 4 , k Z k ' )        X k + N / 4 U k + N / 4 - i ( ω N k s N / 4 , k Z k - ω N - k s N / 4 , k Z k ' )        X k + 3 N / 4 U k + N / 4 + i ( ω N k s N / 4 , k Z k - ω N - k s N / 4 , k Z k ' )     END FOR   ENDIF  RETURN  X k
TANGENTFFT 4 N ( x n )
  IF  N = 1     RETURN  x 0   ELSIF  N = 2      X 0 x 0 + x 1      X 1 x 0 - x 1   ELSIF  N = 4      T k 2 = 0 , 1 TANGENTFFT 8 2 ( x 2 n 2 )      T k 2 = 0 , 1 ' TANGENTFFT 8 2 ( x 2 n 2 + 1 )      X 0 T 0 + T 0 '      X 2 T 0 - T 0 '      X 1 T 1 + T 1 '      X 3 T 1 - T 1 '   ELSE      U k 4 = 0 , , N / 4 - 1 TANGENTFFT 8 N / 4 ( x 4 n 4 )      Y k 8 = 0 , , N / 8 - 1 TANGENTFFT 8 N / 8 ( x 8 n 8 + 2 )      Y k 8 = 0 , , N / 8 - 1 ' TANGENTFFT 8 N / 8 ( x 8 n 8 - 2 )      Z k 4 = 0 , , N / 4 - 1 TANGENTFFT 8 N / 4 ( x 4 n 4 + 1 )      Z k 4 = 0 , , N / 4 - 1 ' TANGENTFFT 8 N / 4 ( x 4 n 4 - 1 )     FOR  k = 0  to  N / 8 - 1        α N , k s N / 4 , k / s N , k        β N , k s N / 8 , k / s N / 2 , k        γ N , k s N / 4 , k + N / 8 / s N , k + N / 8        δ N , k s N / 2 , k / s N , k        ϵ N , k s N / 2 , k + N / 8 / s N , k + N / 8        Ω 0 ω N k * α N , k        Ω 1 ω N k + N / 8 * γ N , k        Ω 2 ω N 2 k * β N , k        T 0 ( Ω 2 Y k + Ω ¯ 2 Y k ) * δ N , k        T 1 i ( Ω 2 Y k - Ω ¯ 2 Y k ) * ϵ N , k        X k U k * α N , k + T 0 + ( Ω 0 Z k + Ω ¯ 0 Z k ' )        X k + N / 2 U k * α N , k + T 0 - ( Ω 0 Z k + Ω ¯ 0 Z k ' )        X k + N / 4 U k * α N , k - T 0 - i ( Ω 0 Z k - Ω ¯ 0 Z k ' )        X k + 3 N / 4 U k * α N , k - T 0 + i ( Ω 0 Z k - Ω ¯ 0 Z k ' )        X k + N / 8 U k + N / 8 * γ N , k - T 1 + ( Ω 1 Z k + N / 8 + Ω ¯ 0 Z k + N / 8 ' )        X k + 3 N / 8 U k + N / 8 * γ N , k + T 1 - i ( Ω 1 Z k + N / 8 - Ω ¯ 0 Z k + N / 8 ' )        X k + 5 N / 8 U k + N / 8 * γ N , k - T 1 - ( Ω 1 Z k + N / 8 + Ω ¯ 0 Z k + N / 8 ' )        X k + 7 N / 8 U k + N / 8 * γ N , k + T 1 + i ( Ω 1 Z k + N / 8 - Ω ¯ 0 Z k + N / 8 ' )     END FOR   ENDIF  RETURN  X k
TANGENTFFT 8 N ( x n )

Tangent

The tangent FFT is divided into two functions, described with pseudocode in [link] and [link] . If the tangent FFT is computed prior to convolution in the frequency domain, theconvolution kernel can absorb the final scaling and only [link] is required. Otherwise [link] is used as a wrapper around [link] to perform the rescaling, and the result X k is in the correct basis.

[link] is similar to [link] , except that Z k and Z k ' are computed with [link] , and thus scaled by 1 / s N / 4 , k . Because Z k and Z k ' are respectively multiplied by the coefficients ω N k and ω N - k , the results are scaled into the correct basis by absorbing s N / 4 , k into the coefficients.

Get Jobilize Job Search Mobile App in your pocket Now!

Get it on Google Play Download on the App Store Now




Source:  OpenStax, Computing the fast fourier transform on simd microprocessors. OpenStax CNX. Jul 15, 2012 Download for free at http://cnx.org/content/col11438/1.2
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'Computing the fast fourier transform on simd microprocessors' conversation and receive update notifications?

Ask