arm_cfft_radix2_f32.c

00001 /* ----------------------------------------------------------------------
00002  * Project:      CMSIS DSP Library
00003  * Title:        arm_cfft_radix2_f32.c
00004  * Description:  Radix-2 Decimation in Frequency CFFT & CIFFT Floating point processing function
00005  *
00006  * $Date:        27. January 2017
00007  * $Revision:    V.1.5.1
00008  *
00009  * Target Processor: Cortex-M cores
00010  * -------------------------------------------------------------------- */
00011 /*
00012  * Copyright (C) 2010-2017 ARM Limited or its affiliates. All rights reserved.
00013  *
00014  * SPDX-License-Identifier: Apache-2.0
00015  *
00016  * Licensed under the Apache License, Version 2.0 (the License); you may
00017  * not use this file except in compliance with the License.
00018  * You may obtain a copy of the License at
00019  *
00020  * www.apache.org/licenses/LICENSE-2.0
00021  *
00022  * Unless required by applicable law or agreed to in writing, software
00023  * distributed under the License is distributed on an AS IS BASIS, WITHOUT
00024  * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
00025  * See the License for the specific language governing permissions and
00026  * limitations under the License.
00027  */
00028 
00029 #include "arm_math.h"
00030 
00031 void arm_radix2_butterfly_f32(
00032   float32_t * pSrc,
00033   uint32_t fftLen,
00034   float32_t * pCoef,
00035   uint16_t twidCoefModifier);
00036 
00037 void arm_radix2_butterfly_inverse_f32(
00038   float32_t * pSrc,
00039   uint32_t fftLen,
00040   float32_t * pCoef,
00041   uint16_t twidCoefModifier,
00042   float32_t onebyfftLen);
00043 
00044 extern void arm_bitreversal_f32(
00045     float32_t * pSrc,
00046     uint16_t fftSize,
00047     uint16_t bitRevFactor,
00048     uint16_t * pBitRevTab);
00049 
00050 /**
00051 * @ingroup groupTransforms
00052 */
00053 
00054 /**
00055 * @addtogroup ComplexFFT
00056 * @{
00057 */
00058 
00059 /**
00060 * @details
00061 * @brief Radix-2 CFFT/CIFFT.
00062 * @deprecated Do not use this function.  It has been superseded by \ref arm_cfft_f32 and will be removed
00063 * in the future.
00064 * @param[in]      *S    points to an instance of the floating-point Radix-2 CFFT/CIFFT structure.
00065 * @param[in, out] *pSrc points to the complex data buffer of size <code>2*fftLen</code>. Processing occurs in-place.
00066 * @return none.
00067 */
00068 
00069 void arm_cfft_radix2_f32(
00070 const arm_cfft_radix2_instance_f32 * S,
00071 float32_t * pSrc)
00072 {
00073 
00074    if (S->ifftFlag == 1U)
00075    {
00076       /*  Complex IFFT radix-2  */
00077       arm_radix2_butterfly_inverse_f32(pSrc, S->fftLen, S->pTwiddle,
00078       S->twidCoefModifier, S->onebyfftLen);
00079    }
00080    else
00081    {
00082       /*  Complex FFT radix-2  */
00083       arm_radix2_butterfly_f32(pSrc, S->fftLen, S->pTwiddle,
00084       S->twidCoefModifier);
00085    }
00086 
00087    if (S->bitReverseFlag == 1U)
00088    {
00089       /*  Bit Reversal */
00090       arm_bitreversal_f32(pSrc, S->fftLen, S->bitRevFactor, S->pBitRevTable);
00091    }
00092 
00093 }
00094 
00095 
00096 /**
00097 * @} end of ComplexFFT group
00098 */
00099 
00100 
00101 
00102 /* ----------------------------------------------------------------------
00103 ** Internal helper function used by the FFTs
00104 ** ------------------------------------------------------------------- */
00105 
00106 /*
00107 * @brief  Core function for the floating-point CFFT butterfly process.
00108 * @param[in, out] *pSrc            points to the in-place buffer of floating-point data type.
00109 * @param[in]      fftLen           length of the FFT.
00110 * @param[in]      *pCoef           points to the twiddle coefficient buffer.
00111 * @param[in]      twidCoefModifier twiddle coefficient modifier that supports different size FFTs with the same twiddle factor table.
00112 * @return none.
00113 */
00114 
00115 void arm_radix2_butterfly_f32(
00116 float32_t * pSrc,
00117 uint32_t fftLen,
00118 float32_t * pCoef,
00119 uint16_t twidCoefModifier)
00120 {
00121 
00122    uint32_t i, j, k, l;
00123    uint32_t n1, n2, ia;
00124    float32_t xt, yt, cosVal, sinVal;
00125    float32_t p0, p1, p2, p3;
00126    float32_t a0, a1;
00127 
00128 #if defined (ARM_MATH_DSP)
00129 
00130    /*  Initializations for the first stage */
00131    n2 = fftLen >> 1;
00132    ia = 0;
00133    i = 0;
00134 
00135    // loop for groups
00136    for (k = n2; k > 0; k--)
00137    {
00138       cosVal = pCoef[ia * 2];
00139       sinVal = pCoef[(ia * 2) + 1];
00140 
00141       /*  Twiddle coefficients index modifier */
00142       ia += twidCoefModifier;
00143 
00144       /*  index calculation for the input as, */
00145       /*  pSrc[i + 0], pSrc[i + fftLen/1] */
00146       l = i + n2;
00147 
00148       /*  Butterfly implementation */
00149       a0 = pSrc[2 * i] + pSrc[2 * l];
00150       xt = pSrc[2 * i] - pSrc[2 * l];
00151 
00152       yt = pSrc[2 * i + 1] - pSrc[2 * l + 1];
00153       a1 = pSrc[2 * l + 1] + pSrc[2 * i + 1];
00154 
00155       p0 = xt * cosVal;
00156       p1 = yt * sinVal;
00157       p2 = yt * cosVal;
00158       p3 = xt * sinVal;
00159 
00160       pSrc[2 * i]     = a0;
00161       pSrc[2 * i + 1] = a1;
00162 
00163       pSrc[2 * l]     = p0 + p1;
00164       pSrc[2 * l + 1] = p2 - p3;
00165 
00166       i++;
00167    }                             // groups loop end
00168 
00169    twidCoefModifier <<= 1U;
00170 
00171    // loop for stage
00172    for (k = n2; k > 2; k = k >> 1)
00173    {
00174       n1 = n2;
00175       n2 = n2 >> 1;
00176       ia = 0;
00177 
00178       // loop for groups
00179       j = 0;
00180       do
00181       {
00182          cosVal = pCoef[ia * 2];
00183          sinVal = pCoef[(ia * 2) + 1];
00184          ia += twidCoefModifier;
00185 
00186          // loop for butterfly
00187          i = j;
00188          do
00189          {
00190             l = i + n2;
00191             a0 = pSrc[2 * i] + pSrc[2 * l];
00192             xt = pSrc[2 * i] - pSrc[2 * l];
00193 
00194             yt = pSrc[2 * i + 1] - pSrc[2 * l + 1];
00195             a1 = pSrc[2 * l + 1] + pSrc[2 * i + 1];
00196 
00197             p0 = xt * cosVal;
00198             p1 = yt * sinVal;
00199             p2 = yt * cosVal;
00200             p3 = xt * sinVal;
00201 
00202             pSrc[2 * i] = a0;
00203             pSrc[2 * i + 1] = a1;
00204 
00205             pSrc[2 * l]     = p0 + p1;
00206             pSrc[2 * l + 1] = p2 - p3;
00207 
00208             i += n1;
00209          } while ( i < fftLen );                        // butterfly loop end
00210          j++;
00211       } while ( j < n2);                          // groups loop end
00212       twidCoefModifier <<= 1U;
00213    }                             // stages loop end
00214 
00215    // loop for butterfly
00216    for (i = 0; i < fftLen; i += 2)
00217    {
00218       a0 = pSrc[2 * i] + pSrc[2 * i + 2];
00219       xt = pSrc[2 * i] - pSrc[2 * i + 2];
00220 
00221       yt = pSrc[2 * i + 1] - pSrc[2 * i + 3];
00222       a1 = pSrc[2 * i + 3] + pSrc[2 * i + 1];
00223 
00224       pSrc[2 * i] = a0;
00225       pSrc[2 * i + 1] = a1;
00226       pSrc[2 * i + 2] = xt;
00227       pSrc[2 * i + 3] = yt;
00228    }                             // groups loop end
00229 
00230 #else
00231 
00232    n2 = fftLen;
00233 
00234    // loop for stage
00235    for (k = fftLen; k > 1; k = k >> 1)
00236    {
00237       n1 = n2;
00238       n2 = n2 >> 1;
00239       ia = 0;
00240 
00241       // loop for groups
00242       j = 0;
00243       do
00244       {
00245          cosVal = pCoef[ia * 2];
00246          sinVal = pCoef[(ia * 2) + 1];
00247          ia += twidCoefModifier;
00248 
00249          // loop for butterfly
00250          i = j;
00251          do
00252          {
00253             l = i + n2;
00254             a0 = pSrc[2 * i] + pSrc[2 * l];
00255             xt = pSrc[2 * i] - pSrc[2 * l];
00256 
00257             yt = pSrc[2 * i + 1] - pSrc[2 * l + 1];
00258             a1 = pSrc[2 * l + 1] + pSrc[2 * i + 1];
00259 
00260             p0 = xt * cosVal;
00261             p1 = yt * sinVal;
00262             p2 = yt * cosVal;
00263             p3 = xt * sinVal;
00264 
00265             pSrc[2 * i] = a0;
00266             pSrc[2 * i + 1] = a1;
00267 
00268             pSrc[2 * l]     = p0 + p1;
00269             pSrc[2 * l + 1] = p2 - p3;
00270 
00271             i += n1;
00272          } while (i < fftLen);
00273          j++;
00274       } while (j < n2);
00275       twidCoefModifier <<= 1U;
00276    }
00277 
00278 #endif //    #if defined (ARM_MATH_DSP)
00279 
00280 }
00281 
00282 
00283 void arm_radix2_butterfly_inverse_f32(
00284 float32_t * pSrc,
00285 uint32_t fftLen,
00286 float32_t * pCoef,
00287 uint16_t twidCoefModifier,
00288 float32_t onebyfftLen)
00289 {
00290 
00291    uint32_t i, j, k, l;
00292    uint32_t n1, n2, ia;
00293    float32_t xt, yt, cosVal, sinVal;
00294    float32_t p0, p1, p2, p3;
00295    float32_t a0, a1;
00296 
00297 #if defined (ARM_MATH_DSP)
00298 
00299    n2 = fftLen >> 1;
00300    ia = 0;
00301 
00302    // loop for groups
00303    for (i = 0; i < n2; i++)
00304    {
00305       cosVal = pCoef[ia * 2];
00306       sinVal = pCoef[(ia * 2) + 1];
00307       ia += twidCoefModifier;
00308 
00309       l = i + n2;
00310       a0 = pSrc[2 * i] + pSrc[2 * l];
00311       xt = pSrc[2 * i] - pSrc[2 * l];
00312 
00313       yt = pSrc[2 * i + 1] - pSrc[2 * l + 1];
00314       a1 = pSrc[2 * l + 1] + pSrc[2 * i + 1];
00315 
00316       p0 = xt * cosVal;
00317       p1 = yt * sinVal;
00318       p2 = yt * cosVal;
00319       p3 = xt * sinVal;
00320 
00321       pSrc[2 * i] = a0;
00322       pSrc[2 * i + 1] = a1;
00323 
00324       pSrc[2 * l]     = p0 - p1;
00325       pSrc[2 * l + 1] = p2 + p3;
00326    }                             // groups loop end
00327 
00328    twidCoefModifier <<= 1U;
00329 
00330    // loop for stage
00331    for (k = fftLen / 2; k > 2; k = k >> 1)
00332    {
00333       n1 = n2;
00334       n2 = n2 >> 1;
00335       ia = 0;
00336 
00337       // loop for groups
00338       j = 0;
00339       do
00340       {
00341          cosVal = pCoef[ia * 2];
00342          sinVal = pCoef[(ia * 2) + 1];
00343          ia += twidCoefModifier;
00344 
00345          // loop for butterfly
00346          i = j;
00347          do
00348          {
00349             l = i + n2;
00350             a0 = pSrc[2 * i] + pSrc[2 * l];
00351             xt = pSrc[2 * i] - pSrc[2 * l];
00352 
00353             yt = pSrc[2 * i + 1] - pSrc[2 * l + 1];
00354             a1 = pSrc[2 * l + 1] + pSrc[2 * i + 1];
00355 
00356             p0 = xt * cosVal;
00357             p1 = yt * sinVal;
00358             p2 = yt * cosVal;
00359             p3 = xt * sinVal;
00360 
00361             pSrc[2 * i] = a0;
00362             pSrc[2 * i + 1] = a1;
00363 
00364             pSrc[2 * l]     = p0 - p1;
00365             pSrc[2 * l + 1] = p2 + p3;
00366 
00367             i += n1;
00368          } while ( i < fftLen );                 // butterfly loop end
00369          j++;
00370       } while (j < n2);                      // groups loop end
00371 
00372       twidCoefModifier <<= 1U;
00373    }                             // stages loop end
00374 
00375    // loop for butterfly
00376    for (i = 0; i < fftLen; i += 2)
00377    {
00378       a0 = pSrc[2 * i] + pSrc[2 * i + 2];
00379       xt = pSrc[2 * i] - pSrc[2 * i + 2];
00380 
00381       a1 = pSrc[2 * i + 3] + pSrc[2 * i + 1];
00382       yt = pSrc[2 * i + 1] - pSrc[2 * i + 3];
00383 
00384       p0 = a0 * onebyfftLen;
00385       p2 = xt * onebyfftLen;
00386       p1 = a1 * onebyfftLen;
00387       p3 = yt * onebyfftLen;
00388 
00389       pSrc[2 * i] = p0;
00390       pSrc[2 * i + 1] = p1;
00391       pSrc[2 * i + 2] = p2;
00392       pSrc[2 * i + 3] = p3;
00393    }                             // butterfly loop end
00394 
00395 #else
00396 
00397    n2 = fftLen;
00398 
00399    // loop for stage
00400    for (k = fftLen; k > 2; k = k >> 1)
00401    {
00402       n1 = n2;
00403       n2 = n2 >> 1;
00404       ia = 0;
00405 
00406       // loop for groups
00407       j = 0;
00408       do
00409       {
00410          cosVal = pCoef[ia * 2];
00411          sinVal = pCoef[(ia * 2) + 1];
00412          ia = ia + twidCoefModifier;
00413 
00414          // loop for butterfly
00415          i = j;
00416          do
00417          {
00418             l = i + n2;
00419             a0 = pSrc[2 * i] + pSrc[2 * l];
00420             xt = pSrc[2 * i] - pSrc[2 * l];
00421 
00422             yt = pSrc[2 * i + 1] - pSrc[2 * l + 1];
00423             a1 = pSrc[2 * l + 1] + pSrc[2 * i + 1];
00424 
00425             p0 = xt * cosVal;
00426             p1 = yt * sinVal;
00427             p2 = yt * cosVal;
00428             p3 = xt * sinVal;
00429 
00430             pSrc[2 * i] = a0;
00431             pSrc[2 * i + 1] = a1;
00432 
00433             pSrc[2 * l]     = p0 - p1;
00434             pSrc[2 * l + 1] = p2 + p3;
00435 
00436             i += n1;
00437          } while ( i < fftLen );                    // butterfly loop end
00438          j++;
00439       } while ( j < n2 );                      // groups loop end
00440 
00441       twidCoefModifier = twidCoefModifier << 1U;
00442    }                             // stages loop end
00443 
00444    n1 = n2;
00445    n2 = n2 >> 1;
00446 
00447    // loop for butterfly
00448    for (i = 0; i < fftLen; i += n1)
00449    {
00450       l = i + n2;
00451 
00452       a0 = pSrc[2 * i] + pSrc[2 * l];
00453       xt = pSrc[2 * i] - pSrc[2 * l];
00454 
00455       a1 = pSrc[2 * l + 1] + pSrc[2 * i + 1];
00456       yt = pSrc[2 * i + 1] - pSrc[2 * l + 1];
00457 
00458       p0 = a0 * onebyfftLen;
00459       p2 = xt * onebyfftLen;
00460       p1 = a1 * onebyfftLen;
00461       p3 = yt * onebyfftLen;
00462 
00463       pSrc[2 * i] = p0;
00464       pSrc[2U * l] = p2;
00465 
00466       pSrc[2 * i + 1] = p1;
00467       pSrc[2U * l + 1U] = p3;
00468    }                             // butterfly loop end
00469 
00470 #endif //      #if defined (ARM_MATH_DSP)
00471 
00472 }
00473