Sea In[0], In[1], ... In[N-1] un array con los datos de entrada temporales a transformar, y Out[0], Out[1], ... Out[N-1] el buffer de salida. El algoritmo tiene dos pasos fundamentales:
Paso 1, Intercambio de bits (Bit reversal):
Se copian los datos del buffer de entrada al buffer de salida, pero la posición que ocupará cada dato en el array de salida vendrá determinada por una inversión de los bits de la posición ocupada en el array original.
Voy a explicar esto, que es simple, aunque confuso de comprender al principio. Se ve claramente con la siguiente tabla, para ocho muestras:
Posición de los datos del array de entrada | Posición de los datos arrayde salida: inversión de bit | ||
| Decimal | Binario | Binario | Decimal |
| 0 | 000 | 000 | 0 |
| 1 | 001 | 100 | 4 |
| 2 | 010 | 010 | 2 |
| 3 | 011 | 110 | 6 |
| 4 | 100 | 001 | 1 |
| 5 | 101 | 101 | 5 |
| 6 | 110 | 011 | 3 |
| 7 | 111 | 111 | 7 |
Como vemos en la tabla anterior, el dato de la posición 0, se copiaría en la posición 0 en el array de salida, el de la posición 1 en la posición 4, el de la posición 2 en la posición 2, etc.
De esta forma, si por ejemplo tuviésemos el siguiente array de entrada:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 1 | 3 | 5 | 2 | 5 | 1 | 3 | 4 |
en el array de salida obtendríamos:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 1 | 5 | 5 | 3 | 3 | 1 | 2 | 4 |
El algoritmo que se ocupa de la reordenación anterior es el siguiente (basado en desplazamientos y operaciones lógicas a nivel de bit):
- int k,khat,bit;
for (k=0, khat=0; k
{
Out[khat]=In[k];
for (bit=N/2; (khat & bit)!=0; bit >>=1)
khat ^= bit;
khat ^= bit; /* Fin del incremento de khat */
}
Paso 2, Iteración:
Una vez ordenado el array de salida, solo hay que realizar el siguiente bucle (donde * denota una multiplicación compleja) para obtener en el array de salida la transformada:
- # define pi 3.14159265358
for (n=2; n<=N; n <<= 1)
{
w=2*pi/n;
for (m=0; m
{
for (k=0; k
{
y=Out[m+k];
z=Out[m+k+n/2] * exp(-ikw);
Out[m+k]=(y+z)/2;
Out[m+k+n/2]=(y-z)/2;
}
}
}
segundo el array de entrada puede ser de cualquier tamañano?, segun lo q lei la fft se creo para q no haya el problema de q la onda sea simetrica, y bueno la respuesta ppor asi decirlo de una fft es la sumaoria de todas las frecuencias q componen la onda, hasta q frecuencia me da a la salida? me da la amplitud ? en la salida lo implemente en matlab pero me dio datos medios raros ? si no fuera mucha molestia podrias ampliar mucho mas el proceso y el porq de algunos pasos muchas gracias de ante mano
for (k=0; k
{
de realizar esta misma programacion pero en matlab?
La cuestion es que yo lo intento xo algo falla si me dieran ideas...seria
muy de agradecer
Gracias