Transforms
[Basic]


Detailed Description

All the transforms functions currently supported by the DSP library.

Benchmark on the AT32UC targets


Complex Fast Fourier Transform

This function computes a complex FFT from an input signal. It uses the Radix-4 "Decimate In Time" algorithm and does not perform a calculation "in place" which means that the input buffer has to be different from the output buffer.
Here is the formula of the FFT:
transforms_fft_equation.gif
Relative functions:


Complex inverse Fast Fourier Transform

This function computes a complex inverse FFT from an input signal. It uses the Radix-4 "Decimate In Time" algorithm and does not perform a calculation "in place" which means that the input buffer has to be different from the output buffer.
Here is the formula of the iFFT:
transforms_ifft_equation.gif
Relative functions:


Real to complex Fast Fourier Transform

This function computes a complex FFT from a real input signal. It uses the Radix-4 "Decimate In Time" algorithm and does not perform a calculation "in place" which means that the input buffer has to be different from the output buffer.
Here is the formula of the FFT:
transforms_fft_equation.gif
Relative functions:



Functions

void dsp16_trans_complexfft (dsp16_complex_t *vect1, dsp16_complex_t *vect2, int nlog)
 16-bit fixed point version of the complex FFT algorithm.
void dsp16_trans_complexifft (dsp16_complex_t *vect1, dsp16_complex_t *vect2, int nlog)
 16-bit fixed point version of the complex iFFT algorithm.
void dsp16_trans_realcomplexfft (dsp16_complex_t *vect1, dsp16_t *vect2, int nlog)
 16-bit fixed point version of the real to complex FFT algorithm.
void dsp32_trans_realcomplexfft (dsp32_complex_t *vect1, dsp32_t *vect2, int nlog)
 32-bit fixed point version of the real to complex FFT algorithm.


Function Documentation

void dsp16_trans_complexfft ( dsp16_complex_t vect1,
dsp16_complex_t vect2,
int  nlog 
)

16-bit fixed point version of the complex FFT algorithm.

Parameters:
vect1 A pointer on a 16-bit complex vector which is the output buffer of this function.
vect2 A pointer on a 16-bit complex vector which is the input buffer of this function.
nlog It is the base-2-logarithm of the size of the input/output vector.
Due to its implementation, this function computes only 4^n-point complex FFT. Therefore, the nlog argument has to be even.
Note:
The following requirements have to be matched:
  • The size of the output buffer has to be the same as the size of the input buffer.
  • This function uses a static twiddle factors table which determines the maximal FFT size which can be performed. By default it is 1024. Please check the value of DSP16_N_TWIDDLE_FACTORS.
  • vect1 and vect2 MUST be 4-byte aligned. Please use A_ALIGNED to do so.
  • To avoid overflowing values, the resulting vector amplitude is scaled by 2^nlog.

Definition at line 73 of file trans_dsp16_complex_fft.c.

References DSP16_N_TWIDDLE_FACTORS, DSP16_QB, dsp16_twiddle_factors, dsp16_twiddle_factors2, dsp16_complex_t::imag, and dsp16_complex_t::real.

00074 {
00075   int size;
00076   int m;
00077   int stage, j, r, indice, inc_indice, r_brev, r_temp;
00078   dsp16_t e_real, e_imag, e2_real, e2_imag, e3_real, e3_imag;
00079   dsp16_t temp;
00080   int i0, i1, i2, i3;
00081   dsp32_t a0_real, a0_imag, a1_real, a1_imag, a2_real, a2_imag, a3_real, a3_imag;
00082 
00083   size = 1 << nlog;
00084 
00085   for(r=0; r<size; r += 4)
00086   {
00087     r_brev = 0;
00088     r_temp = r;
00089     for(j=0; j<nlog; j++)
00090     {
00091       r_brev <<= 1;
00092       if (r_temp & 1)
00093         r_brev |= 1;
00094       r_temp >>= 1;
00095     }
00096 
00097     a0_real = vect2[r_brev].real;
00098     a0_imag = vect2[r_brev].imag;
00099     r_brev += size >> 2;
00100     a1_real = vect2[r_brev].real;
00101     a1_imag = vect2[r_brev].imag;
00102     r_brev += size >> 2;
00103     a2_real = vect2[r_brev].real;
00104     a2_imag = vect2[r_brev].imag;
00105     r_brev += size >> 2;
00106     a3_real = vect2[r_brev].real;
00107     a3_imag = vect2[r_brev].imag;
00108 
00109     vect1[r].real = (a0_real + a2_real + a1_real + a3_real) >> 2;
00110     vect1[r].imag = (a0_imag + a2_imag + a1_imag + a3_imag) >> 2;
00111     vect1[r + 2].real = (a0_real + a2_real - a1_real - a3_real) >> 2;
00112     vect1[r + 2].imag = (a0_imag + a2_imag - a1_imag - a3_imag) >> 2;
00113 
00114     vect1[r + 1].real = (a0_real - a2_real + a1_imag - a3_imag) >> 2;
00115     vect1[r + 1].imag = (a0_imag - a2_imag - a1_real + a3_real) >> 2;
00116     vect1[r + 3].real = (a0_real - a2_real - a1_imag + a3_imag) >> 2;
00117     vect1[r + 3].imag = (a0_imag - a2_imag + a1_real - a3_real) >> 2;
00118   }
00119 
00120   m = 4;
00121   inc_indice = (DSP16_N_TWIDDLE_FACTORS/8);
00122   for(stage=4; stage <= nlog; stage+=2)
00123   {
00124     m <<= 2;
00125 
00126     indice = 0;
00127 
00128     for(r=0; r<size; r += m)
00129     {
00130       i0 = r;
00131       i1 = i0 + (m >> 2);
00132       i2 = i1 + (m >> 2);
00133       i3 = i2 + (m >> 2);
00134 
00135       a0_real = vect1[i0].real;
00136       a0_imag = vect1[i0].imag;
00137       a1_real = vect1[i2].real;
00138       a1_imag = vect1[i2].imag;
00139       a2_real = vect1[i1].real;
00140       a2_imag = vect1[i1].imag;
00141       a3_real = vect1[i3].real;
00142       a3_imag = vect1[i3].imag;
00143 
00144       vect1[i0].real = (a0_real + a2_real + a1_real + a3_real) >> 2;
00145       vect1[i0].imag = (a0_imag + a2_imag + a1_imag + a3_imag) >> 2;
00146       vect1[i2].real = (a0_real + a2_real - a1_real - a3_real) >> 2;
00147       vect1[i2].imag = (a0_imag + a2_imag - a1_imag - a3_imag) >> 2;
00148 
00149       vect1[i1].real = (a0_real - a2_real + a1_imag - a3_imag) >> 2;
00150       vect1[i1].imag = (a0_imag - a2_imag - a1_real + a3_real) >> 2;
00151       vect1[i3].real = (a0_real - a2_real - a1_imag + a3_imag) >> 2;
00152       vect1[i3].imag = (a0_imag - a2_imag + a1_real - a3_real) >> 2;
00153     }
00154 
00155     for(j=1; j<(m >> 2); j++)
00156     {
00157       indice += inc_indice;
00158 
00159       //  e = exp(1.0*j*-2*PI*%i/m);
00160       e_real = dsp16_twiddle_factors[indice];
00161       e_imag = dsp16_twiddle_factors[indice + 1];
00162 
00163 #if DSP_OPTIMIZATION & DSP_OPTI_SIZE
00164       //  e2 = exp(2.0*j*-2*PI*%i/m);
00165       if (indice >= DSP16_N_TWIDDLE_FACTORS/4)
00166       {
00167         r = DSP16_N_TWIDDLE_FACTORS - (indice << 1);
00168         e2_real = -dsp16_twiddle_factors[r];
00169         e2_imag = dsp16_twiddle_factors[r + 1];
00170 
00171         if (r < DSP16_N_TWIDDLE_FACTORS/3)
00172         {
00173           r = indice - r;
00174           e3_real = -dsp16_twiddle_factors[r];
00175           e3_imag = -dsp16_twiddle_factors[r + 1];
00176         }
00177         else
00178         {
00179           r -= indice;
00180           e3_real = -dsp16_twiddle_factors[r];
00181           e3_imag = dsp16_twiddle_factors[r + 1];
00182         }
00183       }
00184       else
00185       {
00186         r = indice << 1;
00187         e2_real = dsp16_twiddle_factors[r];
00188         e2_imag = dsp16_twiddle_factors[r + 1];
00189 
00190         if (r >= DSP16_N_TWIDDLE_FACTORS/3)
00191         {
00192           r = DSP16_N_TWIDDLE_FACTORS - (indice + r);
00193           e3_real = -dsp16_twiddle_factors[r];
00194           e3_imag = dsp16_twiddle_factors[r + 1];
00195         }
00196         else
00197         {
00198           r += indice;
00199           e3_real = dsp16_twiddle_factors[r];
00200           e3_imag = dsp16_twiddle_factors[r + 1];
00201         }
00202       }
00203 
00204 #else
00205       //  e2 = exp(2.0*j*-2*PI*%i/m);
00206       e2_real = dsp16_twiddle_factors2[indice*2];
00207       e2_imag = dsp16_twiddle_factors2[indice*2 + 1];
00208 
00209       //  e3 = exp(3.0*j*-2*PI*%i/m);
00210       e3_real = dsp16_twiddle_factors2[indice*2 + 2];
00211       e3_imag = dsp16_twiddle_factors2[indice*2 + 3];
00212 #endif
00213 
00214       for(r=0; r<size; r += m)
00215       {
00216         i0 = j + r;
00217         i1 = i0 + (m >> 2);
00218         i2 = i1 + (m >> 2);
00219         i3 = i2 + (m >> 2);
00220 
00221 #if DSP_OPTIMIZATION & DSP_OPTI_ACCURACY
00222         a0_real = vect1[i0].real;
00223         a0_imag = vect1[i0].imag;
00224 #else
00225         a0_real = vect1[i0].real >> 2;
00226         a0_imag = vect1[i0].imag >> 2;
00227 #endif
00228 
00229         a1_real = vect1[i2].real;
00230         a1_imag = vect1[i2].imag;
00231         a2_real = vect1[i1].real;
00232         a2_imag = vect1[i1].imag;
00233         a3_real = vect1[i3].real;
00234         a3_imag = vect1[i3].imag;
00235 
00236 #if DSP_OPTIMIZATION & DSP_OPTI_ACCURACY
00237 
00238         temp = (a1_real*e_real - a1_imag*e_imag) >> (DSP16_QB);
00239         a1_imag = (a1_real*e_imag + a1_imag*e_real) >> (DSP16_QB);
00240         a1_real = temp;
00241         temp = (a2_real*e2_real - a2_imag*e2_imag) >> (DSP16_QB);
00242         a2_imag = (a2_real*e2_imag + a2_imag*e2_real) >> (DSP16_QB);
00243         a2_real = temp;
00244         temp = (a3_real*e3_real - a3_imag*e3_imag) >> (DSP16_QB);
00245         a3_imag = (a3_real*e3_imag + a3_imag*e3_real) >> (DSP16_QB);
00246         a3_real = temp;
00247 
00248         vect1[i0].real = (a0_real + a2_real + (a1_real + a3_real)) >> 2;
00249         vect1[i0].imag = (a0_imag + a2_imag + (a1_imag + a3_imag)) >> 2;
00250         vect1[i2].real = (a0_real + a2_real - (a1_real + a3_real)) >> 2;
00251         vect1[i2].imag = (a0_imag + a2_imag - (a1_imag + a3_imag)) >> 2;
00252 
00253         vect1[i1].real = (a0_real - a2_real + (a1_imag - a3_imag)) >> 2;
00254         vect1[i1].imag = (a0_imag - a2_imag - (a1_real - a3_real)) >> 2;
00255         vect1[i3].real = (a0_real - a2_real - (a1_imag - a3_imag)) >> 2;
00256         vect1[i3].imag = (a0_imag - a2_imag + (a1_real - a3_real)) >> 2;
00257 #else
00258         temp = (a1_real*e_real - a1_imag*e_imag) >> (DSP16_QB + 1);
00259         a1_imag = (a1_real*e_imag + a1_imag*e_real) >> (DSP16_QB + 1);
00260         a1_real = temp;
00261         temp = (a2_real*e2_real - a2_imag*e2_imag) >> (DSP16_QB + 1);
00262         a2_imag = (a2_real*e2_imag + a2_imag*e2_real) >> (DSP16_QB + 1);
00263         a2_real = temp;
00264         temp = (a3_real*e3_real - a3_imag*e3_imag) >> (DSP16_QB + 1);
00265         a3_imag = (a3_real*e3_imag + a3_imag*e3_real) >> (DSP16_QB + 1);
00266         a3_real = temp;
00267 
00268         vect1[i0].real = (a0_real + a2_real + (a1_real + a3_real));
00269         vect1[i0].imag = (a0_imag + a2_imag + (a1_imag + a3_imag));
00270         vect1[i2].real = (a0_real + a2_real - (a1_real + a3_real));
00271         vect1[i2].imag = (a0_imag + a2_imag - (a1_imag + a3_imag));
00272 
00273         vect1[i1].real = (a0_real - a2_real + (a1_imag - a3_imag));
00274         vect1[i1].imag = (a0_imag - a2_imag - (a1_real - a3_real));
00275         vect1[i3].real = (a0_real - a2_real - (a1_imag - a3_imag));
00276         vect1[i3].imag = (a0_imag - a2_imag + (a1_real - a3_real));
00277 #endif
00278       }
00279     }
00280     inc_indice >>= 2;
00281   }
00282 }

void dsp16_trans_complexifft ( dsp16_complex_t vect1,
dsp16_complex_t vect2,
int  nlog 
)

16-bit fixed point version of the complex iFFT algorithm.

Parameters:
vect1 A pointer on a 16-bit complex vector which is the output buffer of this function.
vect2 A pointer on a 16-bit complex vector which is the input buffer of this function.
nlog It is the base-2-logarithm of the size of the input/output vector.
Due to its implementation, this function computes only 4^n-point complex iFFT. Therefore, the nlog argument has to be even.
Note:
The following requirements have to be matched:
  • The size of the output buffer has to be the same as the size of the input buffer.
  • This function uses a static twiddle factors table which determines the maximal FFT size which can be performed. By default it is 1024. Please check the value of DSP16_N_TWIDDLE_FACTORS.
  • vect1 and vect2 MUST be 4-byte aligned. Please use A_ALIGNED to do so.
  • To avoid overflowing values, the resulting vector amplitude is scaled by 2^nlog.

Definition at line 73 of file trans_dsp16_complex_ifft.c.

References DSP16_N_TWIDDLE_FACTORS, DSP16_QB, dsp16_twiddle_factors, dsp16_twiddle_factors2, dsp16_vect_complex_conj(), dsp16_complex_t::imag, and dsp16_complex_t::real.

00074 {
00075   int size;
00076   int m;
00077   int stage, j, r, indice, inc_indice, r_brev, r_temp;
00078   dsp16_t e_real, e_imag, e2_real, e2_imag, e3_real, e3_imag;
00079   dsp16_t temp;
00080   int i0, i1, i2, i3;
00081   dsp32_t a0_real, a0_imag, a1_real, a1_imag, a2_real, a2_imag, a3_real, a3_imag;
00082 
00083   size = 1 << nlog;
00084 
00085   for(r=0; r<size; r += 4)
00086   {
00087     r_brev = 0;
00088     r_temp = r;
00089     for(j=0; j<nlog; j++)
00090     {
00091       r_brev <<= 1;
00092       if (r_temp & 1)
00093         r_brev |= 1;
00094       r_temp >>= 1;
00095     }
00096 
00097     a0_real = vect2[r_brev].imag;
00098     a0_imag = vect2[r_brev].real;
00099     r_brev += size >> 2;
00100     a1_real = vect2[r_brev].imag;
00101     a1_imag = vect2[r_brev].real;
00102     r_brev += size >> 2;
00103     a2_real = vect2[r_brev].imag;
00104     a2_imag = vect2[r_brev].real;
00105     r_brev += size >> 2;
00106     a3_real = vect2[r_brev].imag;
00107     a3_imag = vect2[r_brev].real;
00108 
00109     vect1[r].real = (a0_real + a2_real + a1_real + a3_real) >> 2;
00110     vect1[r].imag = (a0_imag + a2_imag + a1_imag + a3_imag) >> 2;
00111     vect1[r + 2].real = (a0_real + a2_real - a1_real - a3_real) >> 2;
00112     vect1[r + 2].imag = (a0_imag + a2_imag - a1_imag - a3_imag) >> 2;
00113 
00114     vect1[r + 1].real = (a0_real - a2_real + a1_imag - a3_imag) >> 2;
00115     vect1[r + 1].imag = (a0_imag - a2_imag - a1_real + a3_real) >> 2;
00116     vect1[r + 3].real = (a0_real - a2_real - a1_imag + a3_imag) >> 2;
00117     vect1[r + 3].imag = (a0_imag - a2_imag + a1_real - a3_real) >> 2;
00118   }
00119 
00120   m = 4;
00121   inc_indice = (DSP16_N_TWIDDLE_FACTORS/8);
00122   for(stage=4; stage <= nlog; stage+=2)
00123   {
00124     m <<= 2;
00125 
00126     indice = 0;
00127 
00128     for(r=0; r<size; r += m)
00129     {
00130       i0 = r;
00131       i1 = i0 + (m >> 2);
00132       i2 = i1 + (m >> 2);
00133       i3 = i2 + (m >> 2);
00134 
00135       a0_real = vect1[i0].real;
00136       a0_imag = vect1[i0].imag;
00137       a1_real = vect1[i2].real;
00138       a1_imag = vect1[i2].imag;
00139       a2_real = vect1[i1].real;
00140       a2_imag = vect1[i1].imag;
00141       a3_real = vect1[i3].real;
00142       a3_imag = vect1[i3].imag;
00143 
00144       vect1[i0].real = (a0_real + a2_real + a1_real + a3_real) >> 2;
00145       vect1[i0].imag = (a0_imag + a2_imag + a1_imag + a3_imag) >> 2;
00146       vect1[i2].real = (a0_real + a2_real - a1_real - a3_real) >> 2;
00147       vect1[i2].imag = (a0_imag + a2_imag - a1_imag - a3_imag) >> 2;
00148 
00149       vect1[i1].real = (a0_real - a2_real + a1_imag - a3_imag) >> 2;
00150       vect1[i1].imag = (a0_imag - a2_imag - a1_real + a3_real) >> 2;
00151       vect1[i3].real = (a0_real - a2_real - a1_imag + a3_imag) >> 2;
00152       vect1[i3].imag = (a0_imag - a2_imag + a1_real - a3_real) >> 2;
00153     }
00154 
00155     for(j=1; j<(m >> 2); j++)
00156     {
00157       indice += inc_indice;
00158 
00159       //  e = exp(1.0*j*-2*PI*%i/m);
00160       e_real = dsp16_twiddle_factors[indice];
00161       e_imag = dsp16_twiddle_factors[indice + 1];
00162 
00163 #if DSP_OPTIMIZATION & DSP_OPTI_SIZE
00164       //  e2 = exp(2.0*j*-2*PI*%i/m);
00165       if (indice >= DSP16_N_TWIDDLE_FACTORS/4)
00166       {
00167         r = DSP16_N_TWIDDLE_FACTORS - (indice << 1);
00168         e2_real = -dsp16_twiddle_factors[r];
00169         e2_imag = dsp16_twiddle_factors[r + 1];
00170 
00171         if (r < DSP16_N_TWIDDLE_FACTORS/3)
00172         {
00173           r = indice - r;
00174           e3_real = -dsp16_twiddle_factors[r];
00175           e3_imag = -dsp16_twiddle_factors[r + 1];
00176         }
00177         else
00178         {
00179           r -= indice;
00180           e3_real = -dsp16_twiddle_factors[r];
00181           e3_imag = dsp16_twiddle_factors[r + 1];
00182         }
00183       }
00184       else
00185       {
00186         r = indice << 1;
00187         e2_real = dsp16_twiddle_factors[r];
00188         e2_imag = dsp16_twiddle_factors[r + 1];
00189 
00190         if (r >= DSP16_N_TWIDDLE_FACTORS/3)
00191         {
00192           r = DSP16_N_TWIDDLE_FACTORS - (indice + r);
00193           e3_real = -dsp16_twiddle_factors[r];
00194           e3_imag = dsp16_twiddle_factors[r + 1];
00195         }
00196         else
00197         {
00198           r += indice;
00199           e3_real = dsp16_twiddle_factors[r];
00200           e3_imag = dsp16_twiddle_factors[r + 1];
00201         }
00202       }
00203 
00204 #else
00205       //  e2 = exp(2.0*j*-2*PI*%i/m);
00206       e2_real = dsp16_twiddle_factors2[indice*2];
00207       e2_imag = dsp16_twiddle_factors2[indice*2 + 1];
00208 
00209       //  e3 = exp(3.0*j*-2*PI*%i/m);
00210       e3_real = dsp16_twiddle_factors2[indice*2 + 2];
00211       e3_imag = dsp16_twiddle_factors2[indice*2 + 3];
00212 #endif
00213 
00214       for(r=0; r<size; r += m)
00215       {
00216         i0 = j + r;
00217         i1 = i0 + (m >> 2);
00218         i2 = i1 + (m >> 2);
00219         i3 = i2 + (m >> 2);
00220 
00221 #if DSP_OPTIMIZATION & DSP_OPTI_ACCURACY
00222         a0_real = vect1[i0].real;
00223         a0_imag = vect1[i0].imag;
00224 #else
00225         a0_real = vect1[i0].real >> 2;
00226         a0_imag = vect1[i0].imag >> 2;
00227 #endif
00228 
00229         a1_real = vect1[i2].real;
00230         a1_imag = vect1[i2].imag;
00231         a2_real = vect1[i1].real;
00232         a2_imag = vect1[i1].imag;
00233         a3_real = vect1[i3].real;
00234         a3_imag = vect1[i3].imag;
00235 
00236 #if DSP_OPTIMIZATION & DSP_OPTI_ACCURACY
00237 
00238         temp = (a1_real*e_real - a1_imag*e_imag) >> (DSP16_QB);
00239         a1_imag = (a1_real*e_imag + a1_imag*e_real) >> (DSP16_QB);
00240         a1_real = temp;
00241         temp = (a2_real*e2_real - a2_imag*e2_imag) >> (DSP16_QB);
00242         a2_imag = (a2_real*e2_imag + a2_imag*e2_real) >> (DSP16_QB);
00243         a2_real = temp;
00244         temp = (a3_real*e3_real - a3_imag*e3_imag) >> (DSP16_QB);
00245         a3_imag = (a3_real*e3_imag + a3_imag*e3_real) >> (DSP16_QB);
00246         a3_real = temp;
00247 
00248         vect1[i0].real = (a0_real + a2_real + (a1_real + a3_real)) >> 2;
00249         vect1[i0].imag = (a0_imag + a2_imag + (a1_imag + a3_imag)) >> 2;
00250         vect1[i2].real = (a0_real + a2_real - (a1_real + a3_real)) >> 2;
00251         vect1[i2].imag = (a0_imag + a2_imag - (a1_imag + a3_imag)) >> 2;
00252 
00253         vect1[i1].real = (a0_real - a2_real + (a1_imag - a3_imag)) >> 2;
00254         vect1[i1].imag = (a0_imag - a2_imag - (a1_real - a3_real)) >> 2;
00255         vect1[i3].real = (a0_real - a2_real - (a1_imag - a3_imag)) >> 2;
00256         vect1[i3].imag = (a0_imag - a2_imag + (a1_real - a3_real)) >> 2;
00257 
00258 #else
00259 
00260         temp = (a1_real*e_real - a1_imag*e_imag) >> (DSP16_QB + 1);
00261         a1_imag = (a1_real*e_imag + a1_imag*e_real) >> (DSP16_QB + 1);
00262         a1_real = temp;
00263         temp = (a2_real*e2_real - a2_imag*e2_imag) >> (DSP16_QB + 1);
00264         a2_imag = (a2_real*e2_imag + a2_imag*e2_real) >> (DSP16_QB + 1);
00265         a2_real = temp;
00266         temp = (a3_real*e3_real - a3_imag*e3_imag) >> (DSP16_QB + 1);
00267         a3_imag = (a3_real*e3_imag + a3_imag*e3_real) >> (DSP16_QB + 1);
00268         a3_real = temp;
00269 
00270         vect1[i0].real = (a0_real + a2_real + (a1_real + a3_real));
00271         vect1[i0].imag = (a0_imag + a2_imag + (a1_imag + a3_imag));
00272         vect1[i2].real = (a0_real + a2_real - (a1_real + a3_real));
00273         vect1[i2].imag = (a0_imag + a2_imag - (a1_imag + a3_imag));
00274 
00275         vect1[i1].real = (a0_real - a2_real + (a1_imag - a3_imag));
00276         vect1[i1].imag = (a0_imag - a2_imag - (a1_real - a3_real));
00277         vect1[i3].real = (a0_real - a2_real - (a1_imag - a3_imag));
00278         vect1[i3].imag = (a0_imag - a2_imag + (a1_real - a3_real));
00279 
00280 #endif
00281       }
00282     }
00283     inc_indice >>= 2;
00284   }
00285 
00286   dsp16_vect_complex_conj(vect1, vect1, size);
00287 }

void dsp16_trans_realcomplexfft ( dsp16_complex_t vect1,
dsp16_t vect2,
int  nlog 
)

16-bit fixed point version of the real to complex FFT algorithm.

Parameters:
vect1 A pointer on a 16-bit complex vector which is the output buffer of this function.
vect2 A pointer on a 16-bit real vector which is the input buffer of this function.
nlog It is the base-2-logarithm of the size of the input/output vector.
Due to its implementation, this function computes only 4^n-point complex FFT. Therefore, the nlog argument has to be even.
Note:
The following requirements have to be matched:
  • The size of the output buffer has to be the same as the size of the input buffer.
  • This function uses a static twiddle factors table which determines the maximal FFT size which can be performed. By default it is 1024. Please check the value of DSP16_N_TWIDDLE_FACTORS.
  • vect1 and vect2 MUST be 4-byte aligned. Please use A_ALIGNED to do so.
  • To avoid overflowing values, the resulting vector amplitude is scaled by 2^nlog.

Definition at line 53 of file trans_dsp16_realcomplex_fft.c.

References DSP16_N_TWIDDLE_FACTORS, DSP16_QB, dsp16_twiddle_factors, dsp16_twiddle_factors2, dsp16_complex_t::imag, and dsp16_complex_t::real.

Referenced by dsp_calculate_fft().

00054 {
00055   int size;
00056   int m;
00057   int stage, j, r, indice, inc_indice, r_brev, r_temp;
00058   dsp16_t e_real, e_imag, e2_real, e2_imag, e3_real, e3_imag;
00059   dsp16_t temp;
00060   int i0, i1, i2, i3;
00061   dsp32_t a0_real, a0_imag, a1_real, a1_imag, a2_real, a2_imag, a3_real, a3_imag;
00062 
00063   size = 1 << nlog;
00064 
00065   for(r=0; r<size; r += 4)
00066   {
00067     r_brev = 0;
00068     r_temp = r;
00069     for(j=0; j<nlog; j++)
00070     {
00071       r_brev <<= 1;
00072       if (r_temp & 1)
00073         r_brev |= 1;
00074       r_temp >>= 1;
00075     }
00076 
00077     a0_real = vect2[r_brev];
00078     r_brev += size >> 2;
00079     a1_real = vect2[r_brev];
00080     r_brev += size >> 2;
00081     a2_real = vect2[r_brev];
00082     r_brev += size >> 2;
00083     a3_real = vect2[r_brev];
00084 
00085     vect1[r].real = (a0_real + a2_real + a1_real + a3_real) >> 2;
00086     vect1[r].imag = 0;
00087     vect1[r + 2].real = (a0_real + a2_real - a1_real - a3_real) >> 2;
00088     vect1[r + 2].imag = 0;
00089 
00090     vect1[r + 1].real = (a0_real - a2_real) >> 2;
00091     vect1[r + 1].imag = (-a1_real + a3_real) >> 2;
00092     vect1[r + 3].real = (a0_real - a2_real) >> 2;
00093     vect1[r + 3].imag = (a1_real - a3_real) >> 2;
00094   }
00095 
00096   m = 4;
00097   inc_indice = (DSP16_N_TWIDDLE_FACTORS/8);
00098   for(stage=4; stage <= nlog; stage+=2)
00099   {
00100     m <<= 2;
00101 
00102     indice = 0;
00103 
00104     for(r=0; r<size; r += m)
00105     {
00106       i0 = r;
00107       i1 = i0 + (m >> 2);
00108       i2 = i1 + (m >> 2);
00109       i3 = i2 + (m >> 2);
00110 
00111       a0_real = vect1[i0].real;
00112       a0_imag = vect1[i0].imag;
00113       a1_real = vect1[i2].real;
00114       a1_imag = vect1[i2].imag;
00115       a2_real = vect1[i1].real;
00116       a2_imag = vect1[i1].imag;
00117       a3_real = vect1[i3].real;
00118       a3_imag = vect1[i3].imag;
00119 
00120       vect1[i0].real = (a0_real + a2_real + a1_real + a3_real) >> 2;
00121       vect1[i0].imag = (a0_imag + a2_imag + a1_imag + a3_imag) >> 2;
00122       vect1[i2].real = (a0_real + a2_real - a1_real - a3_real) >> 2;
00123       vect1[i2].imag = (a0_imag + a2_imag - a1_imag - a3_imag) >> 2;
00124 
00125       vect1[i1].real = (a0_real - a2_real + a1_imag - a3_imag) >> 2;
00126       vect1[i1].imag = (a0_imag - a2_imag - a1_real + a3_real) >> 2;
00127       vect1[i3].real = (a0_real - a2_real - a1_imag + a3_imag) >> 2;
00128       vect1[i3].imag = (a0_imag - a2_imag + a1_real - a3_real) >> 2;
00129     }
00130 
00131     for(j=1; j<(m >> 2); j++)
00132     {
00133       indice += inc_indice;
00134 
00135       //  e = exp(1.0*j*-2*PI*%i/m);
00136       e_real = dsp16_twiddle_factors[indice];
00137       e_imag = dsp16_twiddle_factors[indice + 1];
00138 
00139 #if DSP_OPTIMIZATION & DSP_OPTI_SIZE
00140       //  e2 = exp(2.0*j*-2*PI*%i/m);
00141       if (indice >= DSP16_N_TWIDDLE_FACTORS/4)
00142       {
00143         r = DSP16_N_TWIDDLE_FACTORS - (indice << 1);
00144         e2_real = -dsp16_twiddle_factors[r];
00145         e2_imag = dsp16_twiddle_factors[r + 1];
00146 
00147         if (r < DSP16_N_TWIDDLE_FACTORS/3)
00148         {
00149           r = indice - r;
00150           e3_real = -dsp16_twiddle_factors[r];
00151           e3_imag = -dsp16_twiddle_factors[r + 1];
00152         }
00153         else
00154         {
00155           r -= indice;
00156           e3_real = -dsp16_twiddle_factors[r];
00157           e3_imag = dsp16_twiddle_factors[r + 1];
00158         }
00159       }
00160       else
00161       {
00162         r = indice << 1;
00163         e2_real = dsp16_twiddle_factors[r];
00164         e2_imag = dsp16_twiddle_factors[r + 1];
00165 
00166         if (r >= DSP16_N_TWIDDLE_FACTORS/3)
00167         {
00168           r = DSP16_N_TWIDDLE_FACTORS - (indice + r);
00169           e3_real = -dsp16_twiddle_factors[r];
00170           e3_imag = dsp16_twiddle_factors[r + 1];
00171         }
00172         else
00173         {
00174           r += indice;
00175           e3_real = dsp16_twiddle_factors[r];
00176           e3_imag = dsp16_twiddle_factors[r + 1];
00177         }
00178       }
00179 
00180 #else
00181       //  e2 = exp(2.0*j*-2*PI*%i/m);
00182       e2_real = dsp16_twiddle_factors2[indice*2];
00183       e2_imag = dsp16_twiddle_factors2[indice*2 + 1];
00184 
00185       //  e3 = exp(3.0*j*-2*PI*%i/m);
00186       e3_real = dsp16_twiddle_factors2[indice*2 + 2];
00187       e3_imag = dsp16_twiddle_factors2[indice*2 + 3];
00188 #endif
00189 
00190       for(r=0; r<size; r += m)
00191       {
00192         i0 = j + r;
00193         i1 = i0 + (m >> 2);
00194         i2 = i1 + (m >> 2);
00195         i3 = i2 + (m >> 2);
00196 
00197 #if DSP_OPTIMIZATION & DSP_OPTI_ACCURACY
00198         a0_real = vect1[i0].real;
00199         a0_imag = vect1[i0].imag;
00200 #else
00201         a0_real = vect1[i0].real >> 2;
00202         a0_imag = vect1[i0].imag >> 2;
00203 #endif
00204 
00205         a1_real = vect1[i2].real;
00206         a1_imag = vect1[i2].imag;
00207         a2_real = vect1[i1].real;
00208         a2_imag = vect1[i1].imag;
00209         a3_real = vect1[i3].real;
00210         a3_imag = vect1[i3].imag;
00211 
00212 #if DSP_OPTIMIZATION & DSP_OPTI_ACCURACY
00213 
00214         temp = (a1_real*e_real - a1_imag*e_imag) >> (DSP16_QB);
00215         a1_imag = (a1_real*e_imag + a1_imag*e_real) >> (DSP16_QB);
00216         a1_real = temp;
00217         temp = (a2_real*e2_real - a2_imag*e2_imag) >> (DSP16_QB);
00218         a2_imag = (a2_real*e2_imag + a2_imag*e2_real) >> (DSP16_QB);
00219         a2_real = temp;
00220         temp = (a3_real*e3_real - a3_imag*e3_imag) >> (DSP16_QB);
00221         a3_imag = (a3_real*e3_imag + a3_imag*e3_real) >> (DSP16_QB);
00222         a3_real = temp;
00223 
00224         vect1[i0].real = (a0_real + a2_real + (a1_real + a3_real)) >> 2;
00225         vect1[i0].imag = (a0_imag + a2_imag + (a1_imag + a3_imag)) >> 2;
00226         vect1[i2].real = (a0_real + a2_real - (a1_real + a3_real)) >> 2;
00227         vect1[i2].imag = (a0_imag + a2_imag - (a1_imag + a3_imag)) >> 2;
00228 
00229         vect1[i1].real = (a0_real - a2_real + (a1_imag - a3_imag)) >> 2;
00230         vect1[i1].imag = (a0_imag - a2_imag - (a1_real - a3_real)) >> 2;
00231         vect1[i3].real = (a0_real - a2_real - (a1_imag - a3_imag)) >> 2;
00232         vect1[i3].imag = (a0_imag - a2_imag + (a1_real - a3_real)) >> 2;
00233 #else
00234         temp = (a1_real*e_real - a1_imag*e_imag) >> (DSP16_QB + 1);
00235         a1_imag = (a1_real*e_imag + a1_imag*e_real) >> (DSP16_QB + 1);
00236         a1_real = temp;
00237         temp = (a2_real*e2_real - a2_imag*e2_imag) >> (DSP16_QB + 1);
00238         a2_imag = (a2_real*e2_imag + a2_imag*e2_real) >> (DSP16_QB + 1);
00239         a2_real = temp;
00240         temp = (a3_real*e3_real - a3_imag*e3_imag) >> (DSP16_QB + 1);
00241         a3_imag = (a3_real*e3_imag + a3_imag*e3_real) >> (DSP16_QB + 1);
00242         a3_real = temp;
00243 
00244         vect1[i0].real = (a0_real + a2_real + (a1_real + a3_real));
00245         vect1[i0].imag = (a0_imag + a2_imag + (a1_imag + a3_imag));
00246         vect1[i2].real = (a0_real + a2_real - (a1_real + a3_real));
00247         vect1[i2].imag = (a0_imag + a2_imag - (a1_imag + a3_imag));
00248 
00249         vect1[i1].real = (a0_real - a2_real + (a1_imag - a3_imag));
00250         vect1[i1].imag = (a0_imag - a2_imag - (a1_real - a3_real));
00251         vect1[i3].real = (a0_real - a2_real - (a1_imag - a3_imag));
00252         vect1[i3].imag = (a0_imag - a2_imag + (a1_real - a3_real));
00253 #endif
00254       }
00255     }
00256     inc_indice >>= 2;
00257   }
00258 }

void dsp32_trans_realcomplexfft ( dsp32_complex_t vect1,
dsp32_t vect2,
int  nlog 
)

32-bit fixed point version of the real to complex FFT algorithm.

Parameters:
vect1 A pointer on a 32-bit complex vector which is the output buffer of this function.
vect2 A pointer on a 32-bit real vector which is the input buffer of this function.
nlog It is the base-2-logarithm of the size of the input/output vector.
Due to its implementation, this function computes only 4^n-point complex FFT. Therefore, the nlog argument has to be even.
Note:
The following requirements have to be matched:
  • The size of the output buffer has to be the same as the size of the input buffer.
  • This function uses a static twiddle factors table which determines the maximal FFT size which can be performed. By default it is 1024. Please check the value of DSP32_N_TWIDDLE_FACTORS.
  • vect1 and vect2 MUST be 4-byte aligned. Please use A_ALIGNED to do so.
  • To avoid overflowing values, the resulting vector amplitude is scaled by 2^nlog.

Definition at line 52 of file trans_dsp32_realcomplex_fft.c.

References DSP32_N_TWIDDLE_FACTORS, DSP32_QB, dsp32_twiddle_factors, dsp32_twiddle_factors2, dsp32_complex_t::imag, and dsp32_complex_t::real.

00053 {
00054   int size;
00055   int m;
00056   int stage, j, r, indice, inc_indice, r_brev, r_temp;
00057   dsp32_t e_real, e_imag, e2_real, e2_imag, e3_real, e3_imag;
00058   dsp32_t temp;
00059   int i0, i1, i2, i3;
00060     // 64-bit type
00061   long long a0_real, a0_imag, a1_real, a1_imag, a2_real, a2_imag, a3_real, a3_imag;
00062 
00063   size = 1 << nlog;
00064 
00065   for(r=0; r<size; r += 4)
00066   {
00067     r_brev = 0;
00068     r_temp = r;
00069     for(j=0; j<nlog; j++)
00070     {
00071       r_brev <<= 1;
00072       if (r_temp & 1)
00073         r_brev |= 1;
00074       r_temp >>= 1;
00075     }
00076 
00077     a0_real = vect2[r_brev];
00078     r_brev += size >> 2;
00079     a1_real = vect2[r_brev];
00080     r_brev += size >> 2;
00081     a2_real = vect2[r_brev];
00082     r_brev += size >> 2;
00083     a3_real = vect2[r_brev];
00084 
00085     vect1[r].real = (a0_real + a2_real + a1_real + a3_real) >> 2;
00086     vect1[r].imag = 0;
00087     vect1[r + 2].real = (a0_real + a2_real - a1_real - a3_real) >> 2;
00088     vect1[r + 2].imag = 0;
00089 
00090     vect1[r + 1].real = (a0_real - a2_real) >> 2;
00091     vect1[r + 1].imag = (-a1_real + a3_real) >> 2;
00092     vect1[r + 3].real = (a0_real - a2_real) >> 2;
00093     vect1[r + 3].imag = (a1_real - a3_real) >> 2;
00094   }
00095 
00096   m = 4;
00097   inc_indice = (DSP32_N_TWIDDLE_FACTORS/8);
00098   for(stage=4; stage <= nlog; stage+=2)
00099   {
00100     m <<= 2;
00101 
00102     indice = 0;
00103 
00104     for(r=0; r<size; r += m)
00105     {
00106       i0 = r;
00107       i1 = i0 + (m >> 2);
00108       i2 = i1 + (m >> 2);
00109       i3 = i2 + (m >> 2);
00110 
00111       a0_real = vect1[i0].real;
00112       a0_imag = vect1[i0].imag;
00113       a1_real = vect1[i2].real;
00114       a1_imag = vect1[i2].imag;
00115       a2_real = vect1[i1].real;
00116       a2_imag = vect1[i1].imag;
00117       a3_real = vect1[i3].real;
00118       a3_imag = vect1[i3].imag;
00119 
00120       vect1[i0].real = (a0_real + a2_real + a1_real + a3_real) >> 2;
00121       vect1[i0].imag = (a0_imag + a2_imag + a1_imag + a3_imag) >> 2;
00122       vect1[i2].real = (a0_real + a2_real - a1_real - a3_real) >> 2;
00123       vect1[i2].imag = (a0_imag + a2_imag - a1_imag - a3_imag) >> 2;
00124 
00125       vect1[i1].real = (a0_real - a2_real + a1_imag - a3_imag) >> 2;
00126       vect1[i1].imag = (a0_imag - a2_imag - a1_real + a3_real) >> 2;
00127       vect1[i3].real = (a0_real - a2_real - a1_imag + a3_imag) >> 2;
00128       vect1[i3].imag = (a0_imag - a2_imag + a1_real - a3_real) >> 2;
00129     }
00130 
00131     for(j=1; j<(m >> 2); j++)
00132     {
00133       indice += inc_indice;
00134       
00135       //  e = exp(1.0*j*-2*PI*%i/m);
00136       e_real = dsp32_twiddle_factors[indice];
00137       e_imag = dsp32_twiddle_factors[indice + 1];
00138 
00139 #if DSP_OPTIMIZATION & DSP_OPTI_SIZE
00140       //  e2 = exp(2.0*j*-2*PI*%i/m);
00141       if (indice >= DSP32_N_TWIDDLE_FACTORS/4)
00142       {
00143         r = DSP32_N_TWIDDLE_FACTORS - (indice << 1);
00144         e2_real = -dsp32_twiddle_factors[r];
00145         e2_imag = dsp32_twiddle_factors[r + 1];
00146 
00147         if (r < DSP32_N_TWIDDLE_FACTORS/3)
00148         {
00149           r = indice - r;
00150           e3_real = -dsp32_twiddle_factors[r];
00151           e3_imag = -dsp32_twiddle_factors[r + 1];
00152         }
00153         else
00154         {
00155           r -= indice;
00156           e3_real = -dsp32_twiddle_factors[r];
00157           e3_imag = dsp32_twiddle_factors[r + 1];
00158         }
00159       }
00160       else
00161       {
00162         r = indice << 1;
00163         e2_real = dsp32_twiddle_factors[r];
00164         e2_imag = dsp32_twiddle_factors[r + 1];
00165 
00166         if (r >= DSP32_N_TWIDDLE_FACTORS/3)
00167         {
00168           r = DSP32_N_TWIDDLE_FACTORS - (indice + r);
00169           e3_real = -dsp32_twiddle_factors[r];
00170           e3_imag = dsp32_twiddle_factors[r + 1];
00171         }
00172         else
00173         {
00174           r += indice;
00175           e3_real = dsp32_twiddle_factors[r];
00176           e3_imag = dsp32_twiddle_factors[r + 1];
00177         }
00178       }
00179 
00180 #else
00181       //  e2 = exp(2.0*j*-2*PI*%i/m);
00182       e2_real = dsp32_twiddle_factors2[indice*2];
00183       e2_imag = dsp32_twiddle_factors2[indice*2 + 1];
00184 
00185       //  e3 = exp(3.0*j*-2*PI*%i/m);
00186       e3_real = dsp32_twiddle_factors2[indice*2 + 2];
00187       e3_imag = dsp32_twiddle_factors2[indice*2 + 3];
00188 #endif
00189 
00190       for(r=0; r<size; r += m)
00191       {
00192         i0 = j + r;
00193         i1 = i0 + (m >> 2);
00194         i2 = i1 + (m >> 2);
00195         i3 = i2 + (m >> 2);
00196 
00197 #if DSP_OPTIMIZATION & DSP_OPTI_ACCURACY
00198         a0_real = vect1[i0].real;
00199         a0_imag = vect1[i0].imag;
00200 #else
00201         a0_real = vect1[i0].real >> 2;
00202         a0_imag = vect1[i0].imag >> 2;
00203 #endif
00204 
00205         a1_real = vect1[i2].real;
00206         a1_imag = vect1[i2].imag;
00207         a2_real = vect1[i1].real;
00208         a2_imag = vect1[i1].imag;
00209         a3_real = vect1[i3].real;
00210         a3_imag = vect1[i3].imag;
00211 
00212 #if DSP_OPTIMIZATION & DSP_OPTI_ACCURACY
00213 
00214         temp = (a1_real*e_real - a1_imag*e_imag) >> (DSP32_QB);
00215         a1_imag = (a1_real*e_imag + a1_imag*e_real) >> (DSP32_QB);
00216         a1_real = temp;
00217         temp = (a2_real*e2_real - a2_imag*e2_imag) >> (DSP32_QB);
00218         a2_imag = (a2_real*e2_imag + a2_imag*e2_real) >> (DSP32_QB);
00219         a2_real = temp;
00220         temp = (a3_real*e3_real - a3_imag*e3_imag) >> (DSP32_QB);
00221         a3_imag = (a3_real*e3_imag + a3_imag*e3_real) >> (DSP32_QB);
00222         a3_real = temp;
00223 
00224         vect1[i0].real = (a0_real + a2_real + (a1_real + a3_real)) >> 2;
00225         vect1[i0].imag = (a0_imag + a2_imag + (a1_imag + a3_imag)) >> 2;
00226         vect1[i2].real = (a0_real + a2_real - (a1_real + a3_real)) >> 2;
00227         vect1[i2].imag = (a0_imag + a2_imag - (a1_imag + a3_imag)) >> 2;
00228 
00229         vect1[i1].real = (a0_real - a2_real + (a1_imag - a3_imag)) >> 2;
00230         vect1[i1].imag = (a0_imag - a2_imag - (a1_real - a3_real)) >> 2;
00231         vect1[i3].real = (a0_real - a2_real - (a1_imag - a3_imag)) >> 2;
00232         vect1[i3].imag = (a0_imag - a2_imag + (a1_real - a3_real)) >> 2;
00233 #else
00234         temp = (a1_real*e_real - a1_imag*e_imag) >> (DSP32_QB + 1);
00235         a1_imag = (a1_real*e_imag + a1_imag*e_real) >> (DSP32_QB + 1);
00236         a1_real = temp;
00237         temp = (a2_real*e2_real - a2_imag*e2_imag) >> (DSP32_QB + 1);
00238         a2_imag = (a2_real*e2_imag + a2_imag*e2_real) >> (DSP32_QB + 1);
00239         a2_real = temp;
00240         temp = (a3_real*e3_real - a3_imag*e3_imag) >> (DSP32_QB + 1);
00241         a3_imag = (a3_real*e3_imag + a3_imag*e3_real) >> (DSP32_QB + 1);
00242         a3_real = temp;
00243 
00244         vect1[i0].real = (a0_real + a2_real + (a1_real + a3_real));
00245         vect1[i0].imag = (a0_imag + a2_imag + (a1_imag + a3_imag));
00246         vect1[i2].real = (a0_real + a2_real - (a1_real + a3_real));
00247         vect1[i2].imag = (a0_imag + a2_imag - (a1_imag + a3_imag));
00248 
00249         vect1[i1].real = (a0_real - a2_real + (a1_imag - a3_imag));
00250         vect1[i1].imag = (a0_imag - a2_imag - (a1_real - a3_real));
00251         vect1[i3].real = (a0_real - a2_real - (a1_imag - a3_imag));
00252         vect1[i3].imag = (a0_imag - a2_imag + (a1_real - a3_real));
00253 #endif
00254       }
00255     }
00256     inc_indice >>= 2;
00257   }
00258 }


Generated on Fri Feb 19 02:23:22 2010 for AVR32 UC3 - EVK1104 DSPLib Demo Documentation by  doxygen 1.5.5