arm_cfft_radix2_f32.c

00001 /* ----------------------------------------------------------------------   
00002 * Copyright (C) 2010-2013 ARM Limited. All rights reserved.   
00003 *   
00004 * $Date:        17. January 2013  
00005 * $Revision:    V1.4.1  
00006 *   
00007 * Project:      CMSIS DSP Library   
00008 * Title:        arm_cfft_radix2_f32.c   
00009 *   
00010 * Description:  Radix-2 Decimation in Frequency CFFT & CIFFT Floating point processing function   
00011 *   
00012 *   
00013 * Target Processor: Cortex-M4/Cortex-M3/Cortex-M0
00014 *  
00015 * Redistribution and use in source and binary forms, with or without 
00016 * modification, are permitted provided that the following conditions
00017 * are met:
00018 *   - Redistributions of source code must retain the above copyright
00019 *     notice, this list of conditions and the following disclaimer.
00020 *   - Redistributions in binary form must reproduce the above copyright
00021 *     notice, this list of conditions and the following disclaimer in
00022 *     the documentation and/or other materials provided with the 
00023 *     distribution.
00024 *   - Neither the name of ARM LIMITED nor the names of its contributors
00025 *     may be used to endorse or promote products derived from this
00026 *     software without specific prior written permission.
00027 *
00028 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
00029 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
00030 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
00031 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 
00032 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
00033 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
00034 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
00035 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
00036 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
00037 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
00038 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
00039 * POSSIBILITY OF SUCH DAMAGE.   
00040 * -------------------------------------------------------------------- */
00041 
00042 #include "arm_math.h"
00043 
00044 void arm_radix2_butterfly_f32(
00045   float32_t * pSrc,
00046   uint32_t fftLen,
00047   float32_t * pCoef,
00048   uint16_t twidCoefModifier);
00049 
00050 void arm_radix2_butterfly_inverse_f32(
00051   float32_t * pSrc,
00052   uint32_t fftLen,
00053   float32_t * pCoef,
00054   uint16_t twidCoefModifier,
00055   float32_t onebyfftLen);
00056 
00057 extern void arm_bitreversal_f32(
00058     float32_t * pSrc,
00059     uint16_t fftSize,
00060     uint16_t bitRevFactor,
00061     uint16_t * pBitRevTab);
00062 
00063 /**   
00064 * @ingroup groupTransforms   
00065 */
00066 
00067 /**   
00068 * @addtogroup ComplexFFT   
00069 * @{   
00070 */
00071 
00072 /**   
00073 * @details
00074 * @brief Radix-2 CFFT/CIFFT.
00075 * @deprecated Do not use this function.  It has been superceded by \ref arm_cfft_f32 and will be removed
00076 * in the future.
00077 * @param[in]      *S    points to an instance of the floating-point Radix-2 CFFT/CIFFT structure.  
00078 * @param[in, out] *pSrc points to the complex data buffer of size <code>2*fftLen</code>. Processing occurs in-place.  
00079 * @return none.
00080 */
00081 
00082 void arm_cfft_radix2_f32(
00083 const arm_cfft_radix2_instance_f32 * S,
00084 float32_t * pSrc)
00085 {
00086 
00087    if(S->ifftFlag == 1u)
00088    {
00089       /*  Complex IFFT radix-2  */
00090       arm_radix2_butterfly_inverse_f32(pSrc, S->fftLen, S->pTwiddle,
00091       S->twidCoefModifier, S->onebyfftLen);
00092    }
00093    else
00094    {
00095       /*  Complex FFT radix-2  */
00096       arm_radix2_butterfly_f32(pSrc, S->fftLen, S->pTwiddle,
00097       S->twidCoefModifier);
00098    }
00099 
00100    if(S->bitReverseFlag == 1u)
00101    {
00102       /*  Bit Reversal */
00103       arm_bitreversal_f32(pSrc, S->fftLen, S->bitRevFactor, S->pBitRevTable);
00104    }
00105 
00106 }
00107 
00108 
00109 /**    
00110 * @} end of ComplexFFT group    
00111 */
00112 
00113 
00114 
00115 /* ----------------------------------------------------------------------    
00116 ** Internal helper function used by the FFTs    
00117 ** ------------------------------------------------------------------- */
00118 
00119 /*    
00120 * @brief  Core function for the floating-point CFFT butterfly process.   
00121 * @param[in, out] *pSrc            points to the in-place buffer of floating-point data type.   
00122 * @param[in]      fftLen           length of the FFT.   
00123 * @param[in]      *pCoef           points to the twiddle coefficient buffer.   
00124 * @param[in]      twidCoefModifier twiddle coefficient modifier that supports different size FFTs with the same twiddle factor table.   
00125 * @return none.   
00126 */
00127 
00128 void arm_radix2_butterfly_f32(
00129 float32_t * pSrc,
00130 uint32_t fftLen,
00131 float32_t * pCoef,
00132 uint16_t twidCoefModifier)
00133 {
00134 
00135    uint32_t i, j, k, l;
00136    uint32_t n1, n2, ia;
00137    float32_t xt, yt, cosVal, sinVal;
00138    float32_t p0, p1, p2, p3;
00139    float32_t a0, a1;
00140 
00141 #ifndef ARM_MATH_CM0_FAMILY
00142 
00143    /*  Initializations for the first stage */
00144    n2 = fftLen >> 1;
00145    ia = 0;
00146    i = 0;
00147 
00148    // loop for groups 
00149    for (k = n2; k > 0; k--)
00150    {
00151       cosVal = pCoef[ia * 2];
00152       sinVal = pCoef[(ia * 2) + 1];
00153 
00154       /*  Twiddle coefficients index modifier */
00155       ia += twidCoefModifier;
00156 
00157       /*  index calculation for the input as, */
00158       /*  pSrc[i + 0], pSrc[i + fftLen/1] */
00159       l = i + n2;
00160 
00161       /*  Butterfly implementation */
00162       a0 = pSrc[2 * i] + pSrc[2 * l];
00163       xt = pSrc[2 * i] - pSrc[2 * l];
00164 
00165       yt = pSrc[2 * i + 1] - pSrc[2 * l + 1];
00166       a1 = pSrc[2 * l + 1] + pSrc[2 * i + 1];
00167       
00168       p0 = xt * cosVal;
00169       p1 = yt * sinVal;
00170       p2 = yt * cosVal;
00171       p3 = xt * sinVal;  
00172       
00173       pSrc[2 * i]     = a0;   
00174       pSrc[2 * i + 1] = a1;       
00175       
00176       pSrc[2 * l]     = p0 + p1;
00177       pSrc[2 * l + 1] = p2 - p3;
00178       
00179       i++;
00180    }                             // groups loop end 
00181 
00182    twidCoefModifier <<= 1u;
00183 
00184    // loop for stage 
00185    for (k = n2; k > 2; k = k >> 1)
00186    {
00187       n1 = n2;
00188       n2 = n2 >> 1;
00189       ia = 0;
00190 
00191       // loop for groups 
00192       j = 0;
00193       do
00194       {
00195          cosVal = pCoef[ia * 2];
00196          sinVal = pCoef[(ia * 2) + 1];
00197          ia += twidCoefModifier;
00198 
00199          // loop for butterfly 
00200          i = j;
00201          do
00202          {
00203             l = i + n2;
00204             a0 = pSrc[2 * i] + pSrc[2 * l];
00205             xt = pSrc[2 * i] - pSrc[2 * l];
00206 
00207             yt = pSrc[2 * i + 1] - pSrc[2 * l + 1];
00208             a1 = pSrc[2 * l + 1] + pSrc[2 * i + 1];
00209             
00210             p0 = xt * cosVal;
00211             p1 = yt * sinVal;
00212             p2 = yt * cosVal;
00213             p3 = xt * sinVal;  
00214             
00215             pSrc[2 * i] = a0;   
00216             pSrc[2 * i + 1] = a1;       
00217             
00218             pSrc[2 * l]     = p0 + p1;
00219             pSrc[2 * l + 1] = p2 - p3;
00220             
00221             i += n1;
00222          } while( i < fftLen );                        // butterfly loop end 
00223          j++;
00224       } while( j < n2);                          // groups loop end 
00225       twidCoefModifier <<= 1u;
00226    }                             // stages loop end 
00227 
00228    // loop for butterfly 
00229    for (i = 0; i < fftLen; i += 2)
00230    {
00231       a0 = pSrc[2 * i] + pSrc[2 * i + 2];
00232       xt = pSrc[2 * i] - pSrc[2 * i + 2];
00233 
00234       yt = pSrc[2 * i + 1] - pSrc[2 * i + 3];
00235       a1 = pSrc[2 * i + 3] + pSrc[2 * i + 1];
00236       
00237       pSrc[2 * i] = a0;   
00238       pSrc[2 * i + 1] = a1;
00239       pSrc[2 * i + 2] = xt;
00240       pSrc[2 * i + 3] = yt;
00241    }                             // groups loop end 
00242 
00243 #else
00244  
00245    n2 = fftLen;
00246 
00247    // loop for stage 
00248    for (k = fftLen; k > 1; k = k >> 1)
00249    {
00250       n1 = n2;
00251       n2 = n2 >> 1;
00252       ia = 0;
00253 
00254       // loop for groups 
00255       j = 0;
00256       do
00257       {
00258          cosVal = pCoef[ia * 2];
00259          sinVal = pCoef[(ia * 2) + 1];
00260          ia += twidCoefModifier;
00261 
00262          // loop for butterfly 
00263          i = j;
00264          do
00265          {
00266             l = i + n2;
00267             a0 = pSrc[2 * i] + pSrc[2 * l];
00268             xt = pSrc[2 * i] - pSrc[2 * l];
00269 
00270             yt = pSrc[2 * i + 1] - pSrc[2 * l + 1];
00271             a1 = pSrc[2 * l + 1] + pSrc[2 * i + 1];
00272             
00273             p0 = xt * cosVal;
00274             p1 = yt * sinVal;
00275             p2 = yt * cosVal;
00276             p3 = xt * sinVal;  
00277             
00278             pSrc[2 * i] = a0;   
00279             pSrc[2 * i + 1] = a1;       
00280             
00281             pSrc[2 * l]     = p0 + p1;
00282             pSrc[2 * l + 1] = p2 - p3;
00283             
00284             i += n1;
00285          } while(i < fftLen);
00286          j++;
00287       } while(j < n2);
00288       twidCoefModifier <<= 1u;
00289    }
00290 
00291 #endif //    #ifndef ARM_MATH_CM0_FAMILY
00292 
00293 }
00294 
00295 
00296 void arm_radix2_butterfly_inverse_f32(
00297 float32_t * pSrc,
00298 uint32_t fftLen,
00299 float32_t * pCoef,
00300 uint16_t twidCoefModifier,
00301 float32_t onebyfftLen)
00302 {
00303 
00304    uint32_t i, j, k, l;
00305    uint32_t n1, n2, ia;
00306    float32_t xt, yt, cosVal, sinVal;
00307    float32_t p0, p1, p2, p3;
00308    float32_t a0, a1;
00309 
00310 #ifndef ARM_MATH_CM0_FAMILY
00311 
00312    n2 = fftLen >> 1;
00313    ia = 0;
00314 
00315    // loop for groups 
00316    for (i = 0; i < n2; i++)
00317    {
00318       cosVal = pCoef[ia * 2];
00319       sinVal = pCoef[(ia * 2) + 1];
00320       ia += twidCoefModifier;
00321 
00322       l = i + n2;
00323       a0 = pSrc[2 * i] + pSrc[2 * l];
00324       xt = pSrc[2 * i] - pSrc[2 * l];
00325 
00326       yt = pSrc[2 * i + 1] - pSrc[2 * l + 1];
00327       a1 = pSrc[2 * l + 1] + pSrc[2 * i + 1];
00328       
00329       p0 = xt * cosVal;
00330       p1 = yt * sinVal;
00331       p2 = yt * cosVal;
00332       p3 = xt * sinVal;  
00333       
00334       pSrc[2 * i] = a0;   
00335       pSrc[2 * i + 1] = a1;       
00336       
00337       pSrc[2 * l]     = p0 - p1;
00338       pSrc[2 * l + 1] = p2 + p3;  
00339    }                             // groups loop end 
00340 
00341    twidCoefModifier <<= 1u;
00342 
00343    // loop for stage 
00344    for (k = fftLen / 2; k > 2; k = k >> 1)
00345    {
00346       n1 = n2;
00347       n2 = n2 >> 1;
00348       ia = 0;
00349 
00350       // loop for groups 
00351       j = 0;
00352       do
00353       {
00354          cosVal = pCoef[ia * 2];
00355          sinVal = pCoef[(ia * 2) + 1];
00356          ia += twidCoefModifier;
00357 
00358          // loop for butterfly 
00359          i = j;
00360          do
00361          {
00362             l = i + n2;
00363             a0 = pSrc[2 * i] + pSrc[2 * l];
00364             xt = pSrc[2 * i] - pSrc[2 * l];
00365 
00366             yt = pSrc[2 * i + 1] - pSrc[2 * l + 1];
00367             a1 = pSrc[2 * l + 1] + pSrc[2 * i + 1];
00368             
00369             p0 = xt * cosVal;
00370             p1 = yt * sinVal;
00371             p2 = yt * cosVal;
00372             p3 = xt * sinVal;  
00373             
00374             pSrc[2 * i] = a0;   
00375             pSrc[2 * i + 1] = a1;       
00376             
00377             pSrc[2 * l]     = p0 - p1;
00378             pSrc[2 * l + 1] = p2 + p3; 
00379 
00380             i += n1;
00381          } while( i < fftLen );                 // butterfly loop end 
00382          j++;
00383       } while(j < n2);                      // groups loop end 
00384 
00385       twidCoefModifier <<= 1u;
00386    }                             // stages loop end 
00387 
00388    // loop for butterfly 
00389    for (i = 0; i < fftLen; i += 2)
00390    {   
00391       a0 = pSrc[2 * i] + pSrc[2 * i + 2];
00392       xt = pSrc[2 * i] - pSrc[2 * i + 2];
00393       
00394       a1 = pSrc[2 * i + 3] + pSrc[2 * i + 1];
00395       yt = pSrc[2 * i + 1] - pSrc[2 * i + 3];
00396       
00397       p0 = a0 * onebyfftLen;
00398       p2 = xt * onebyfftLen;
00399       p1 = a1 * onebyfftLen;
00400       p3 = yt * onebyfftLen; 
00401       
00402       pSrc[2 * i] = p0;
00403       pSrc[2 * i + 1] = p1;  
00404       pSrc[2 * i + 2] = p2;       
00405       pSrc[2 * i + 3] = p3;
00406    }                             // butterfly loop end 
00407 
00408 #else
00409 
00410    n2 = fftLen;
00411 
00412    // loop for stage 
00413    for (k = fftLen; k > 2; k = k >> 1)
00414    {
00415       n1 = n2;
00416       n2 = n2 >> 1;
00417       ia = 0;
00418 
00419       // loop for groups 
00420       j = 0;
00421       do
00422       {
00423          cosVal = pCoef[ia * 2];
00424          sinVal = pCoef[(ia * 2) + 1];
00425          ia = ia + twidCoefModifier;
00426 
00427          // loop for butterfly 
00428          i = j;
00429          do
00430          {
00431             l = i + n2;
00432             a0 = pSrc[2 * i] + pSrc[2 * l];
00433             xt = pSrc[2 * i] - pSrc[2 * l];
00434 
00435             yt = pSrc[2 * i + 1] - pSrc[2 * l + 1];
00436             a1 = pSrc[2 * l + 1] + pSrc[2 * i + 1];
00437             
00438             p0 = xt * cosVal;
00439             p1 = yt * sinVal;
00440             p2 = yt * cosVal;
00441             p3 = xt * sinVal;  
00442             
00443             pSrc[2 * i] = a0;   
00444             pSrc[2 * i + 1] = a1;       
00445             
00446             pSrc[2 * l]     = p0 - p1;
00447             pSrc[2 * l + 1] = p2 + p3;  
00448             
00449             i += n1;
00450          } while( i < fftLen );                    // butterfly loop end 
00451          j++;
00452       } while( j < n2 );                      // groups loop end 
00453 
00454       twidCoefModifier = twidCoefModifier << 1u;
00455    }                             // stages loop end 
00456 
00457    n1 = n2;
00458    n2 = n2 >> 1;
00459 
00460    // loop for butterfly 
00461    for (i = 0; i < fftLen; i += n1)
00462    {
00463       l = i + n2;
00464       
00465       a0 = pSrc[2 * i] + pSrc[2 * l];
00466       xt = pSrc[2 * i] - pSrc[2 * l];
00467       
00468       a1 = pSrc[2 * l + 1] + pSrc[2 * i + 1];
00469       yt = pSrc[2 * i + 1] - pSrc[2 * l + 1];
00470       
00471       p0 = a0 * onebyfftLen;
00472       p2 = xt * onebyfftLen;
00473       p1 = a1 * onebyfftLen;
00474       p3 = yt * onebyfftLen; 
00475       
00476       pSrc[2 * i] = p0;
00477       pSrc[2u * l] = p2;
00478      
00479       pSrc[2 * i + 1] = p1;    
00480       pSrc[2u * l + 1u] = p3;
00481    }                             // butterfly loop end 
00482 
00483 #endif //      #ifndef ARM_MATH_CM0_FAMILY
00484 
00485 }