Question for about FFT, maybe for BHOOSHANIYER or other person....

Hi. I'm using your code to do a fft: This is the code (the question
after it):

-----------------------------------------------------------------
/* fft256.c  complex data stored  re, im, re, im, re, ... im */
void fft256(float Z[512]) /* input data points and output  [0] to [511]

*/
{
  static float W[512];    /* scratch vector */
  static float E[258] =   /* constants for FFT algorithm */
  {1.0, 0.0, 0.999699, 0.0245412,
   0.998796, 0.0490677, 0.99729, 0.0735646,
   0.995185, 0.0980171, 0.99248, 0.122411,
   0.989177, 0.14673, 0.985278, 0.170962,
   0.980785, 0.19509, 0.975702, 0.219101,
   0.970031, 0.24298, 0.963776, 0.266713,
   0.95694, 0.290285, 0.949528, 0.313682,
   0.941544, 0.33689, 0.932993, 0.359895,
   0.92388, 0.382683, 0.91421, 0.405241,
   0.903989, 0.427555, 0.893224, 0.449611,
   0.881921, 0.471397, 0.870087, 0.492898,
   0.857729, 0.514103, 0.844854, 0.534998,
   0.83147, 0.55557, 0.817585, 0.575808,
   0.803208, 0.595699, 0.788346, 0.615232,
   0.77301, 0.634393, 0.757209, 0.653173,
   0.740951, 0.671559, 0.724247, 0.689541,
   0.707107, 0.707107, 0.689541, 0.724247,
   0.671559, 0.740951, 0.653173, 0.757209,
   0.634393, 0.77301, 0.615232, 0.788346,
   0.595699, 0.803208, 0.575808, 0.817585,
   0.55557, 0.83147, 0.534998, 0.844854,
   0.514103, 0.857729, 0.492898, 0.870087,
   0.471397, 0.881921, 0.449611, 0.893224,
   0.427555, 0.903989, 0.405241, 0.91421,
   0.382683, 0.92388, 0.359895, 0.932993,
   0.33689, 0.941544, 0.313682, 0.949528,
   0.290285, 0.95694, 0.266713, 0.963776,
   0.24298, 0.970031, 0.219101, 0.975702,
   0.19509, 0.980785, 0.170962, 0.985278,
   0.14673, 0.989177, 0.122411, 0.99248,
   0.0980171, 0.995185, 0.0735646, 0.99729,
   0.0490677, 0.998796, 0.0245412, 0.999699,
   0.0, 1.0, -0.0245412, 0.999699,
   -0.0490677, 0.998796, -0.0735646, 0.99729,
   -0.0980171, 0.995185, -0.122411, 0.99248,
   -0.14673, 0.989177, -0.170962, 0.985278,
   -0.19509, 0.980785, -0.219101, 0.975702,
   -0.24298, 0.970031, -0.266713, 0.963776,
   -0.290285, 0.95694, -0.313682, 0.949528,
   -0.33689, 0.941544, -0.359895, 0.932993,
   -0.382683, 0.92388, -0.405241, 0.91421,
   -0.427555, 0.903989, -0.449611, 0.893224,
   -0.471397, 0.881921, -0.492898, 0.870087,
   -0.514103, 0.857729, -0.534998, 0.844854,
   -0.55557, 0.83147, -0.575808, 0.817585,
   -0.595699, 0.803208, -0.615232, 0.788346,
   -0.634393, 0.77301, -0.653173, 0.757209,
   -0.671559, 0.740951, -0.689541, 0.724247,
   -0.707107, 0.707107, -0.724247, 0.689541,
   -0.740951, 0.671559, -0.757209, 0.653173,
   -0.77301, 0.634393, -0.788346, 0.615232,
   -0.803208, 0.595699, -0.817585, 0.575808,
   -0.83147, 0.55557, -0.844854, 0.534998,
   -0.857729, 0.514103, -0.870087, 0.492898,
   -0.881921, 0.471397, -0.893224, 0.449611,
   -0.903989, 0.427555, -0.91421, 0.405241,
   -0.92388, 0.382683, -0.932993, 0.359895,
   -0.941544, 0.33689, -0.949528, 0.313682,
   -0.95694, 0.290285, -0.963776, 0.266713,
   -0.970031, 0.24298, -0.975702, 0.219101,
   -0.980785, 0.19509, -0.985278, 0.170962,
   -0.989177, 0.14673, -0.99248, 0.122411,
   -0.995185, 0.0980171, -0.99729, 0.0735646,
   -0.998796, 0.0490677, -0.999699, 0.0245412,
   -1.0, 0.0};
  float Tre, Tim;
  int i, j, k, l, m;


   m = 128;
   l = 1;
   while(1)
   {
      k = 0;
      j = l;
      i = 0;
      while(1)
      {
         while(1)
         {
           /* W[i+k] = Z[i] + Z[m+i]; complex */
           W[2*(i+k)]   = Z[2*i]   + Z[2*(m+i)];
           W[2*(i+k)+1] = Z[2*i+1] + Z[2*(m+i)+1];


           /* W[i+j] = E[k] * (Z[i] - Z[m+i]); complex */
           Tre = Z[2*i]   - Z[2*(m+i)];
           Tim = Z[2*i+1] - Z[2*(m+i)+1];
           W[2*(i+j)]   = E[2*k] * Tre - E[2*k+1] * Tim;
           W[2*(i+j)+1] = E[2*k] * Tim + E[2*k+1] * Tre;
           i++;
           if(i >= j) break;
         }
         k = j;
         j = k+l;
         if(j > m) break;
      }
      l = l+l;
                  /* work back other way without copying */
      k = 0;
      j = l;
      i = 0;
      while(1)
      {
        while(1)
        {
          /* Z[i+k] = W[i] + W[m+i]; complex */
          Z[2*(i+k)]   = W[2*i]   + W[2*(m+i)];
          Z[2*(i+k)+1] = W[2*i+1] + W[2*(m+i)+1];


          /* Z[i+j] = E[k] * (W[i] - W[m+i]); complex */
          Tre = W[2*i]   - W[2*(m+i)];
          Tim = W[2*i+1] - W[2*(m+i)+1];
          Z[2*(i+j)]   = E[2*k] * Tre - E[2*k+1] * Tim;
          Z[2*(i+j)+1] = E[2*k] * Tim + E[2*k+1] * Tre;
          i++;
          if(i >= j) break;
        }
        k = j;
        j = k+l;
        if(j > m) break;
      }
      l = l+l;
      if(l > m) break; // result is in Z
   }

} /* end fft256 */

--------------------------------------------------------------------
This is the question:

1.-I stored the input data until do the fft in in this way:
Z[512]=[re,im,re,im,re,im......]

2.-I have only a real part for this reason I filled the img part with
0. At this point I have:
Z[512]=[re,0,re,0,re,0......]

The question is:
I know that the fft points are in the same array (array Z), but I don't
know what are the positions (because I only have real data, and not img
data), I think that they are in the odd positions, but in the even
position I have similar data (The shape of the graph with odd points is
similar with even points). or what is the data in the even points.

Excuse my english


Diego

<dfalvarado@utpl.edu.ec> wrote in message 
news:1117903874.920872.236920@g49g2000cwa.googlegroups.com...
> Hi. I'm using your code to do a fft: This is the code (the question
> after it):
>
> -----------------------------------------------------------------
> /* fft256.c  complex data stored  re, im, re, im, re, ... im */
> void fft256(float Z[512]) /* input data points and output  [0] to [511]
>
> */
> {
>  static float W[512];    /* scratch vector */
>  static float E[258] =   /* constants for FFT algorithm */
>  {1.0, 0.0, 0.999699, 0.0245412,
>   0.998796, 0.0490677, 0.99729, 0.0735646,
>   0.995185, 0.0980171, 0.99248, 0.122411,
>   0.989177, 0.14673, 0.985278, 0.170962,
>   0.980785, 0.19509, 0.975702, 0.219101,
>   0.970031, 0.24298, 0.963776, 0.266713,
>   0.95694, 0.290285, 0.949528, 0.313682,
>   0.941544, 0.33689, 0.932993, 0.359895,
>   0.92388, 0.382683, 0.91421, 0.405241,
>   0.903989, 0.427555, 0.893224, 0.449611,
>   0.881921, 0.471397, 0.870087, 0.492898,
>   0.857729, 0.514103, 0.844854, 0.534998,
>   0.83147, 0.55557, 0.817585, 0.575808,
>   0.803208, 0.595699, 0.788346, 0.615232,
>   0.77301, 0.634393, 0.757209, 0.653173,
>   0.740951, 0.671559, 0.724247, 0.689541,
>   0.707107, 0.707107, 0.689541, 0.724247,
>   0.671559, 0.740951, 0.653173, 0.757209,
>   0.634393, 0.77301, 0.615232, 0.788346,
>   0.595699, 0.803208, 0.575808, 0.817585,
>   0.55557, 0.83147, 0.534998, 0.844854,
>   0.514103, 0.857729, 0.492898, 0.870087,
>   0.471397, 0.881921, 0.449611, 0.893224,
>   0.427555, 0.903989, 0.405241, 0.91421,
>   0.382683, 0.92388, 0.359895, 0.932993,
>   0.33689, 0.941544, 0.313682, 0.949528,
>   0.290285, 0.95694, 0.266713, 0.963776,
>   0.24298, 0.970031, 0.219101, 0.975702,
>   0.19509, 0.980785, 0.170962, 0.985278,
>   0.14673, 0.989177, 0.122411, 0.99248,
>   0.0980171, 0.995185, 0.0735646, 0.99729,
>   0.0490677, 0.998796, 0.0245412, 0.999699,
>   0.0, 1.0, -0.0245412, 0.999699,
>   -0.0490677, 0.998796, -0.0735646, 0.99729,
>   -0.0980171, 0.995185, -0.122411, 0.99248,
>   -0.14673, 0.989177, -0.170962, 0.985278,
>   -0.19509, 0.980785, -0.219101, 0.975702,
>   -0.24298, 0.970031, -0.266713, 0.963776,
>   -0.290285, 0.95694, -0.313682, 0.949528,
>   -0.33689, 0.941544, -0.359895, 0.932993,
>   -0.382683, 0.92388, -0.405241, 0.91421,
>   -0.427555, 0.903989, -0.449611, 0.893224,
>   -0.471397, 0.881921, -0.492898, 0.870087,
>   -0.514103, 0.857729, -0.534998, 0.844854,
>   -0.55557, 0.83147, -0.575808, 0.817585,
>   -0.595699, 0.803208, -0.615232, 0.788346,
>   -0.634393, 0.77301, -0.653173, 0.757209,
>   -0.671559, 0.740951, -0.689541, 0.724247,
>   -0.707107, 0.707107, -0.724247, 0.689541,
>   -0.740951, 0.671559, -0.757209, 0.653173,
>   -0.77301, 0.634393, -0.788346, 0.615232,
>   -0.803208, 0.595699, -0.817585, 0.575808,
>   -0.83147, 0.55557, -0.844854, 0.534998,
>   -0.857729, 0.514103, -0.870087, 0.492898,
>   -0.881921, 0.471397, -0.893224, 0.449611,
>   -0.903989, 0.427555, -0.91421, 0.405241,
>   -0.92388, 0.382683, -0.932993, 0.359895,
>   -0.941544, 0.33689, -0.949528, 0.313682,
>   -0.95694, 0.290285, -0.963776, 0.266713,
>   -0.970031, 0.24298, -0.975702, 0.219101,
>   -0.980785, 0.19509, -0.985278, 0.170962,
>   -0.989177, 0.14673, -0.99248, 0.122411,
>   -0.995185, 0.0980171, -0.99729, 0.0735646,
>   -0.998796, 0.0490677, -0.999699, 0.0245412,
>   -1.0, 0.0};
>  float Tre, Tim;
>  int i, j, k, l, m;
>
>
>   m = 128;
>   l = 1;
>   while(1)
>   {
>      k = 0;
>      j = l;
>      i = 0;
>      while(1)
>      {
>         while(1)
>         {
>           /* W[i+k] = Z[i] + Z[m+i]; complex */
>           W[2*(i+k)]   = Z[2*i]   + Z[2*(m+i)];
>           W[2*(i+k)+1] = Z[2*i+1] + Z[2*(m+i)+1];
>
>
>           /* W[i+j] = E[k] * (Z[i] - Z[m+i]); complex */
>           Tre = Z[2*i]   - Z[2*(m+i)];
>           Tim = Z[2*i+1] - Z[2*(m+i)+1];
>           W[2*(i+j)]   = E[2*k] * Tre - E[2*k+1] * Tim;
>           W[2*(i+j)+1] = E[2*k] * Tim + E[2*k+1] * Tre;
>           i++;
>           if(i >= j) break;
>         }
>         k = j;
>         j = k+l;
>         if(j > m) break;
>      }
>      l = l+l;
>                  /* work back other way without copying */
>      k = 0;
>      j = l;
>      i = 0;
>      while(1)
>      {
>        while(1)
>        {
>          /* Z[i+k] = W[i] + W[m+i]; complex */
>          Z[2*(i+k)]   = W[2*i]   + W[2*(m+i)];
>          Z[2*(i+k)+1] = W[2*i+1] + W[2*(m+i)+1];
>
>
>          /* Z[i+j] = E[k] * (W[i] - W[m+i]); complex */
>          Tre = W[2*i]   - W[2*(m+i)];
>          Tim = W[2*i+1] - W[2*(m+i)+1];
>          Z[2*(i+j)]   = E[2*k] * Tre - E[2*k+1] * Tim;
>          Z[2*(i+j)+1] = E[2*k] * Tim + E[2*k+1] * Tre;
>          i++;
>          if(i >= j) break;
>        }
>        k = j;
>        j = k+l;
>        if(j > m) break;
>      }
>      l = l+l;
>      if(l > m) break; // result is in Z
>   }
>
> } /* end fft256 */
>
> --------------------------------------------------------------------
> This is the question:
>
> 1.-I stored the input data until do the fft in in this way:
> Z[512]=[re,im,re,im,re,im......]
>
> 2.-I have only a real part for this reason I filled the img part with
> 0. At this point I have:
> Z[512]=[re,0,re,0,re,0......]
>
> The question is:
> I know that the fft points are in the same array (array Z), but I don't
> know what are the positions (because I only have real data, and not img
> data), I think that they are in the odd positions, but in the even
> position I have similar data (The shape of the graph with odd points is
> similar with even points). or what is the data in the even points.
>
> Excuse my english
>
>
> Diego
>
Dear Diego - all of the outputs of the FFT are needed even though you have 
only put in real data.  Each pair of outputs contain the in-phase component 
(real part) and the orthogonal phase component (imaginary part) of the 
relevant DFT coefficient.  Only if you have input an even function will you 
see all of the coefficients imaginary parts go close to zero, otherwise you 
need both components of each coefficient to determine the magnitude and 
relative phase.
Best of Luck - Mike

Thank you, for your answer.

I need draw the power or amplitude spectrum. I think that if I put only
real data, at the output I don't need the imaginary part. I'm right. I
only need draw the amplitude spectrum. Or whant I have to do?

Excuse my english.

Diego

dfalvarado@utpl.edu.ec wrote:
> Thank you, for your answer.
> 
> I need draw the power or amplitude spectrum. I think that if I put only
> real data, at the output I don't need the imaginary part. I'm right. I
> only need draw the amplitude spectrum. Or whant I have to do?
> 
> Excuse my english.
> 
> Diego

Power goes with the square root of real squared plus imaginary squared.

P ~ sqrt(Re^2 + Im^2)

You can approximate this roughly as MAX(Im, Re) + .5*MIN(Im, Re).

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������

Thank you Jerry. I'm going to try it.

Do you know about a library that doesn't use sin() cos() exp()
functions, because I'm working with a motorola DSP and the compiler
that I'm using doesn't supportt this kind of functions. I think that I
have to use a code that uses a data tables (for instance for the
coeficients),

 Ah I'm forgetting something; the code would use fixed point. In this
moment I'm using a standar C FFT code(that uses float int, etc), but
the problem is that when I change the data types to fixed
point(__fixed__) the results are wrong, I think thta is better find
another code instead change the data type of the current code.

Than you again.   

Diego

dfalvarado@utpl.edu.ec wrote:
> Thank you Jerry. I'm going to try it.
> 
> Do you know about a library that doesn't use sin() cos() exp()
> functions, because I'm working with a motorola DSP and the compiler
> that I'm using doesn't supportt this kind of functions. I think that I
> have to use a code that uses a data tables (for instance for the
> coeficients),
> 
>  Ah I'm forgetting something; the code would use fixed point. In this
> moment I'm using a standar C FFT code(that uses float int, etc), but
> the problem is that when I change the data types to fixed
> point(__fixed__) the results are wrong, I think thta is better find
> another code instead change the data type of the current code.

Yes. Fixed-point code is not simply floating-point code with some name 
changes. Sometimes, very different algorithms are best for the two cases.

What to you need the transcendental functions for? Certainly not power 
calculation like Re*Re + Im*Im or an approximation like the one I described.

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������

OK. I need a algorithm thta:
1.-Doesn't use a sin, cos, exp, etc functions
2.-Uses only fixed point(for example: int short).
3.-Doesn't uses floating point (for example: float).
4.-Works with 256, 512,1024 data and very fast.

Why? because I'm using a DSP56824.

Do you know about code that has this features?

Thank you

Diego wrote:
> OK. I need a algorithm thta:
> 1.-Doesn't use a sin, cos, exp, etc functions

Use twiddle factors that are stored as constants in the code instead of 
computed when needed. That's faster anyway.

> 2.-Uses only fixed point(for example: int short).

'int' stands for integer. Fixed point is more general than that. Google 
for an understanding of it. Randy Yates has a good paper for that on 
line. 'int short' is unlikely to have enough bits to give meaningful 
results on a bit-addressable machine.

> 3.-Doesn't uses floating point (for example: float).

That follows from point 2.

> 4.-Works with 256, 512,1024 data and very fast.
>
> Why? because I'm using a DSP56824.

Have you looked on the chip maker's site?

> Do you know about code that has this features?
> 
> Thank you

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������

Jerry Avins wrote:

> Diego wrote:


(snip)

>> 2.-Uses only fixed point(for example: int short).

> 'int' stands for integer. Fixed point is more general than that. Google 
> for an understanding of it. Randy Yates has a good paper for that on 
> line. 'int short' is unlikely to have enough bits to give meaningful 
> results on a bit-addressable machine.

True, and it is useful to understand the difference.

In the case of a linear operation, such as FFT, though, if the binary
(or decimal) point of the input is shifted, the output will be shifted
by the same amount.  The FFT algorithm won't need to know the 
difference.  The user should know the difference, though.

-- glen

Jerry Avins wrote:

(snip)

> 'int' stands for integer. Fixed point is more general than that. Google 
> for an understanding of it. Randy Yates has a good paper for that on 
> line. 

In addition, some fixed point numbers are also integers, but
are still more general than the integers in many program
languages.

PL/I, and probably others, allow fixed point numbers with a negative
number of bits after the binary point.  That makes them integers,
but not not quite the same.

-- glen