I have begin to test the Fast Fourrier Transform from Fast Fourier Transform for to understand how the FFT wotk but I don’t understand results
The real part is only 0.5f and the imaginary part is 0.0f at the wanted frequency when I use the simple signal(angle) = cos( angle )
The real part is 1.0f and the imaginary part is always 0.0f at the wanted frequency when I use the signal(angle) = cos(angle + i sin(angle)
What sort of “Fourrier transform” other than the DFT/FFT have I to handle if I want 1.0f for the real part and 1.0f for the imaginary part at the wanted frequency when I use signal(angle) = cos(angle) + i sin(angle) ???
Here are the content of files I use :
- fft.h
#ifndef _FFT_H_
#define _FFT_H_
/*
This computes an in-place complex-to-complex DFT
x and y are the real and imaginary arrays of 2^m points.
dir = 1 gives forward transform
dir = -1 gives reverse transform
*/
int DFT( int dir, int m, double *x1, double *y1 );
/*
This computes an in-place complex-to-complex FFT
x and y are the real and imaginary arrays of 2^m points.
dir = 1 gives forward transform
dir = -1 gives reverse transform
*/
int FFT( int dir, long m, double *x, double *y );
#endif /* _FFT_H_ */
fft.c
include <stdlib.h>
#include <stdio.h>
#include <math.h>
#define FALSE 0
#define TRUE 1
/*
Direct fourier transform
*/
int DFT( int dir, int m, double *x1, double *y1 )
{
long i,k;
double arg;
double cosarg,sinarg;
double *x2=NULL,*y2=NULL;
x2 = malloc( m * sizeof(double));
y2 = malloc( m * sizeof(double));
if (x2 == NULL || y2 == NULL)
return(FALSE);
for ( i = 0 ; i < m ; i++ ) {
x2[i] = 0;
y2[i] = 0;
arg = - dir * 2.0 * 3.141592654 * (double)i / (double)m;
for ( k = 0 ; k < m ; k++ ) {
cosarg = cos(k * arg);
sinarg = sin(k * arg);
x2[i] += (x1[k] * cosarg - y1[k] * sinarg);
y2[i] += (x1[k] * sinarg + y1[k] * cosarg);
}
}
/* Copy the data back */
if (dir == 1) {
for ( i = 0 ; i < m; i++ ) {
x1[i] = x2[i] / (double)m;
y1[i] = y2[i] / (double)m;
}
} else {
for ( i = 0 ; i < m ; i++ ) {
x1[i] = x2[i];
y1[i] = y2[i];
}
}
free(x2);
free(y2);
return(TRUE);
}
/*
This computes an in-place complex-to-complex FFT
x and y are the real and imaginary arrays of 2^m points.
dir = 1 gives forward transform
dir = -1 gives reverse transform
*/
int FFT( int dir, int m, double *x, double *y )
{
long n,i,i1,j,k,i2,l,l1,l2;
double c1,c2,tx,ty,t1,t2,u1,u2,z;
/* Calculate the number of points */
n = 1;
for ( i = 0 ; i < m ; i++ )
n *= 2;
// printf("n= %ld
", n);
/* Do the bit reversal */
i2 = n >> 1;
j = 0;
for ( i = 0 ; i < n -1 ; i++ ) {
if (i < j) {
tx = x[i];
ty = y[i];
x[i] = x[j];
y[i] = y[j];
x[j] = tx;
y[j] = ty;
}
k = i2;
while (k <= j ) {
j -= k;
k >>= 1;
}
j += k;
}
// printf("/* Compute the FFT */
");
c1 = -1.0;
c2 = 0.0;
l2 = 1;
for (l=0;l<m;l++) {
l1 = l2;
l2 <<= 1;
u1 = 1.0;
u2 = 0.0;
for (j=0;j<l1;j++) {
for (i=j;i<n;i+=l2) {
i1 = i + l1;
t1 = u1 * x[i1] - u2 * y[i1];
t2 = u1 * y[i1] + u2 * x[i1];
x[i1] = x[i] - t1;
y[i1] = y[i] - t2;
x[i] += t1;
y[i] += t2;
}
z = u1 * c1 - u2 * c2;
u2 = u1 * c2 + u2 * c1;
u1 = z;
}
c2 = sqrt((1.0 - c1) / 2.0);
if (dir == 1)
c2 = -c2;
c1 = sqrt((1.0 + c1) / 2.0);
}
/* Scaling for forward transform */
if (dir == 1) {
for (i=0;i<n;i++) {
x[i] /= n;
y[i] /= n;
}
}
return(TRUE);
}
test.c
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <stdbool.h>
#include "fft.h"
#define EPSILON 0.001f
int size = 16;
int size2 = 4;
double *reals;
double *images;
void CreateArrays( int n )
{
reals = malloc( (n+1) * sizeof(double) );
images = malloc( (n+1) * sizeof(double) );
}
void FreeArrays()
{
free(reals);
free(images);
}
void InitArraysCos( int n, float freq )
{
int i;
double angle, delta;
angle = 0.0f;
delta = 2.0f * M_PI / (float)(n);
for( i = 0 ; i < n ; i++ )
{
reals[i] = cos( angle * freq );
images[i] = 0.0f;
angle += delta;
}
}
void InitArraysCosSin( int n, float freq )
{
int i;
double angle, delta;
angle = 0.0f;
delta = 2.0f * M_PI / (float)(n);
for( i = 0 ; i < n ; i++ )
{
reals[i] = cos( angle * freq );
images[i] = sin( angle * freq );
angle += delta;
}
}
void PrintArrays( int n, bool zeroes )
{
int i;
for( i = 0 ; i < n ; i++ )
{
if( (fabs(reals[i]) > EPSILON ) || (fabs(images[i]) > EPSILON ) || ( zeroes == true ) )
{
printf(" Freq[%d] = (%f , %f)
", i, reals[i], images[i] );
}
}
}
int main( int argc , char **argv)
{
float freq;
printf("FFT v0.1 by Cyclone
");
CreateArrays(size);
for( freq = 1 ; freq < size / 2 ; freq++)
{
printf("
Init Arrays signal(angle) = cos(angle) for freq %1f Hz ...
", freq);
InitArraysCos(size, freq);
// PrintArrays(size, true);
printf("
Compute DFT for freq %1f Hz ...
", freq);
InitArraysCos(size, freq);
DFT(1, size, reals, images);
PrintArrays(size / 2, false);
printf("
Compute FFT for freq %1f Hz...
", freq);
InitArraysCos(size, freq);
FFT(1, size2, reals, images);
PrintArrays(size / 2 , false);
printf("
-----------------------
");
printf("
Init Arrays signal(angle) = cos(angle) + i sin(angle) for freq %1f Hz ...
", freq);
InitArraysCosSin(size, freq);
// PrintArrays(size, true);
printf("
Compute DFT for freq %1f Hz ...
", freq);
InitArraysCosSin(size, freq);
DFT(1, size, reals, images);
PrintArrays(size / 2, false);
printf("
Compute FFT for freq %1f Hz...
", freq);
InitArraysCosSin(size, freq);
FFT(1, size2, reals, images);
PrintArrays(size / 2 , false);
printf("
=======================
");
}
FreeArrays();
return 0;
}
makefile
all : fft.o test
fft.o : fft.c
gcc -c fft.c -o fft.o
test : test.c fft.o
gcc test.c fft.o -o test -lm
clean :
rm fft.o test
and the result of the execution of ./test
FFT v0.1 by Cyclone
Init Arrays signal(angle) = cos(angle) for freq 1.000000 Hz ...
Compute DFT for freq 1.000000 Hz ...
Freq[1] = (0.500000 , -0.000000)
Compute FFT for freq 1.000000 Hz...
Freq[1] = (0.500000 , -0.000000)
-----------------------
Init Arrays signal(angle) = cos(angle) + i sin(angle) for freq 1.000000 Hz ...
Compute DFT for freq 1.000000 Hz ...
Freq[1] = (1.000000 , -0.000000)
Compute FFT for freq 1.000000 Hz...
Freq[1] = (1.000000 , 0.000000)
=======================
Init Arrays signal(angle) = cos(angle) for freq 2.000000 Hz ...
Compute DFT for freq 2.000000 Hz ...
Freq[2] = (0.500000 , -0.000000)
Compute FFT for freq 2.000000 Hz...
Freq[2] = (0.500000 , 0.000000)
-----------------------
Init Arrays signal(angle) = cos(angle) + i sin(angle) for freq 2.000000 Hz ...
Compute DFT for freq 2.000000 Hz ...
Freq[2] = (1.000000 , -0.000000)
Compute FFT for freq 2.000000 Hz...
Freq[2] = (1.000000 , 0.000000)
=======================
Init Arrays signal(angle) = cos(angle) for freq 3.000000 Hz ...
Compute DFT for freq 3.000000 Hz ...
Freq[3] = (0.500000 , -0.000000)
Compute FFT for freq 3.000000 Hz...
Freq[3] = (0.500000 , 0.000000)
-----------------------
Init Arrays signal(angle) = cos(angle) + i sin(angle) for freq 3.000000 Hz ...
Compute DFT for freq 3.000000 Hz ...
Freq[3] = (1.000000 , -0.000000)
Compute FFT for freq 3.000000 Hz...
Freq[3] = (1.000000 , -0.000000)
=======================
Init Arrays signal(angle) = cos(angle) for freq 4.000000 Hz ...
Compute DFT for freq 4.000000 Hz ...
Freq[4] = (0.500000 , -0.000000)
Compute FFT for freq 4.000000 Hz...
Freq[4] = (0.500000 , 0.000000)
-----------------------
Init Arrays signal(angle) = cos(angle) + i sin(angle) for freq 4.000000 Hz ...
Compute DFT for freq 4.000000 Hz ...
Freq[4] = (1.000000 , -0.000000)
Compute FFT for freq 4.000000 Hz...
Freq[4] = (1.000000 , 0.000000)
=======================
Init Arrays signal(angle) = cos(angle) for freq 5.000000 Hz ...
Compute DFT for freq 5.000000 Hz ...
Freq[5] = (0.500000 , -0.000000)
Compute FFT for freq 5.000000 Hz...
Freq[5] = (0.500000 , 0.000000)
-----------------------
Init Arrays signal(angle) = cos(angle) + i sin(angle) for freq 5.000000 Hz ...
Compute DFT for freq 5.000000 Hz ...
Freq[5] = (1.000000 , -0.000000)
Compute FFT for freq 5.000000 Hz...
Freq[5] = (1.000000 , 0.000000)
=======================
Init Arrays signal(angle) = cos(angle) for freq 6.000000 Hz ...
Compute DFT for freq 6.000000 Hz ...
Freq[6] = (0.500000 , -0.000000)
Compute FFT for freq 6.000000 Hz...
Freq[6] = (0.500000 , -0.000000)
-----------------------
Init Arrays signal(angle) = cos(angle) + i sin(angle) for freq 6.000000 Hz ...
Compute DFT for freq 6.000000 Hz ...
Freq[6] = (1.000000 , -0.000000)
Compute FFT for freq 6.000000 Hz...
Freq[6] = (1.000000 , -0.000000)
=======================
Init Arrays signal(angle) = cos(angle) for freq 7.000000 Hz ...
Compute DFT for freq 7.000000 Hz ...
Freq[7] = (0.500000 , -0.000000)
Compute FFT for freq 7.000000 Hz...
Freq[7] = (0.500000 , 0.000000)
-----------------------
Init Arrays signal(angle) = cos(angle) + i sin(angle) for freq 7.000000 Hz ...
Compute DFT for freq 7.000000 Hz ...
Freq[7] = (1.000000 , -0.000000)
Compute FFT for freq 7.000000 Hz...
Freq[7] = (1.000000 , 0.000000)
=======================
It exist something like a Fast Discret Cosinus Transform, a Fast Discret Sinus Transform and/or a “Fast Discret Cosinus Transform for the real part mixed with a Fast Sinus Transform for the imaginary part” ?
And/or can I use the real part for the left channel and the imaginary part for the right channel on a stereo sound for example ?
(if this is only a story of multiply by two for to have values that I want, it is not really a problem)