git.gag.com Git - debian/gnuradio/blob - gcell/include/gcell/spu/libfft.h

   1 /* --------------------------------------------------------------  */
   2 /* (C)Copyright 2008 Free Software Foundation, Inc.                */
   3 /* (C)Copyright 2001,2007,                                         */
   4 /* International Business Machines Corporation,                    */
   5 /* Sony Computer Entertainment, Incorporated,                      */
   6 /* Toshiba Corporation,                                            */
   7 /*                                                                 */
   8 /* All Rights Reserved.                                            */
   9 /*                                                                 */
  10 /* Redistribution and use in source and binary forms, with or      */
  11 /* without modification, are permitted provided that the           */
  12 /* following conditions are met:                                   */
  13 /*                                                                 */
  14 /* - Redistributions of source code must retain the above copyright*/
  15 /*   notice, this list of conditions and the following disclaimer. */
  16 /*                                                                 */
  17 /* - Redistributions in binary form must reproduce the above       */
  18 /*   copyright notice, this list of conditions and the following   */
  19 /*   disclaimer in the documentation and/or other materials        */
  20 /*   provided with the distribution.                               */
  21 /*                                                                 */
  22 /* - Neither the name of IBM Corporation nor the names of its      */
  23 /*   contributors may be used to endorse or promote products       */
  24 /*   derived from this software without specific prior written     */
  25 /*   permission.                                                   */
  26 /*                                                                 */
  27 /* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND          */
  28 /* CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,     */
  29 /* INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF        */
  30 /* MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE        */
  31 /* DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR            */
  32 /* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,    */
  33 /* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT    */
  34 /* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;    */
  35 /* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)        */
  36 /* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN       */
  37 /* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR    */
  38 /* OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,  */
  39 /* EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.              */
  40 /* --------------------------------------------------------------  */
  41 /* PROLOG END TAG zYx                                              */
  42
  43 #ifndef INCLUDED_LIBFFT_H
  44 #define INCLUDED_LIBFFT_H
  45
  46 // must be defined before inclusion of fft_1d_r2.h
  47 #define MAX_FFT_1D_SIZE 4096
  48
  49 /* fft_1d_r2
  50  * ---------
  51  * Performs a single precision, complex Fast Fourier Transform using
  52  * the DFT (Discrete Fourier Transform) with radix-2 decimation in time.
  53  * The input <in> is an array of complex numbers of length (1<<log2_size)
  54  * entries. The result is returned in the array of complex numbers specified
  55  * by <out>. Note: This routine can support an in-place transformation
  56  * by specifying <in> and <out> to be the same array.
  57  *
  58  * This implementation utilizes the Cooley-Tukey algorithm consisting
  59  * of <log2_size> stages. The basic operation is the butterfly.
  60  *
  61  *          p --------------------------> P = p + q*Wi
  62  *                        \      /
  63  *                         \    /
  64  *                          \  /
  65  *                           \/
  66  *                           /\
  67  *                          /  \
  68  *                         /    \
  69  *               ____     /      \
  70  *          q --| Wi |-----------------> Q = p - q*Wi
  71  *               ----
  72  *
  73  * This routine also requires pre-computed twiddle values, W. W is an
  74  * array of single precision complex numbers of length 1<<(log2_size-2)
  75  * and is computed as follows:
  76  *
  77  *      for (i=0; i<n/4; i++)
  78  *          W[i].real =  cos(i * 2*PI/n);
  79  *          W[i].imag = -sin(i * 2*PI/n);
  80  *      }
  81  *
  82  * This array actually only contains the first half of the twiddle
  83  * factors. Due for symmetry, the second half of the twiddle factors
  84  * are implied and equal:
  85  *
  86  *      for (i=0; i<n/4; i++)
  87  *          W[i+n/4].real =  W[i].imag =  sin(i * 2*PI/n);
  88  *          W[i+n/4].imag = -W[i].real = -cos(i * 2*PI/n);
  89  *      }
  90  *
  91  * Further symmetry allows one to generate the twiddle factor table
  92  * using half the number of trig computations as follows:
  93  *
  94  *      W[0].real = 1.0;
  95  *      W[0].imag = 0.0;
  96  *      for (i=1; i<n/4; i++)
  97  *          W[i].real =  cos(i * 2*PI/n);
  98  *          W[n/4 - i].imag = -W[i].real;
  99  *      }
 100  *
 101  * The complex numbers are packed into quadwords as follows:
 102  *
 103  *    quadword                        complex
 104  *  array element                   array elements
 105  *             -----------------------------------------------------
 106  *       i    |  real 2*i   |  imag 2*i  | real 2*i+1  | imag 2*i+1 |
 107  *             -----------------------------------------------------
 108  *
 109  */
 110
 111 void fft_1d_r2(vector float *out, vector float *in, vector float *W, int log2_size);
 112
 113 #endif /* INCLUDED_LIBFFT_H */