algorithm - rapida - ¿Cómo calcular la Transformada de Fourier Discreta?

transformada rapida de fourier (3)

Aquí hay un muy buen ejemplo (en mi humilde opinión): http://www.phpclasses.org/package/6193-PHP-Compute-the-Fast-Fourier-Transform-of-sampled-data.html

Es un algoritmo de FFT escrito en PHP, y también tiene un cálculo complejo de números. Puede ser útil en tu caso.

Lo encontré increíblemente útil cuando estaba trabajando en mi proyecto de honores de ingeniería. También hay un par de buenos enlaces, pero no los tengo en este momento (actualmente no estoy en casa).

He estado tratando de encontrar algunos lugares que me ayuden a comprender mejor DFT y cómo calcularlo, pero fue en vano. Entonces necesito ayuda para entender DFT y su cálculo de números complejos.

Básicamente, solo estoy buscando ejemplos sobre cómo calcular DFT con una explicación sobre cómo se calculó porque, al final, estoy buscando crear un algoritmo para calcularlo.

He estado leyendo The Scientist and Engineer''s Guide to Digital Signal Processing Por Steven W. Smith. Es un pdf gratis En el Capítulo 12 pasa por una implementación de la FFT paso a paso (La FFT compleja con una entrada de número real) y presenta una RealFFT al final (que es la FFT modificada específicamente para entradas reales). Hay otro capítulo dedicado a la compleja FFT. El libro es un poco viejo, por lo que los ejemplos de programación escritos en BASIC y FORTRAN parecen antiguos, pero los conceptos están bien explicados e ilustrados.

Supongo que 1D DFT / IDFT ...

Todos los DFT usan esta fórmula:

X(k) se transforma el valor de la muestra (dominio complejo)
x(n) es el valor de muestra de datos de entrada (dominio real o complejo)
N es el número de muestras / valores en su conjunto de datos

Todo esto generalmente se multiplica por la constante de normalización c . Como puede ver para un solo valor, necesita N cálculos, por lo que para todas las muestras es O(N^2) que es lento.

Aquí mía Real <-> Dominio complejo DFT / IDFT en C ++ también puede encontrar pistas sobre cómo calcular transformaciones 2D con transformadas 1D y cómo calcular N-point DCT, IDCT por N-point DFT, IDFT allí.

Algoritmos rápidos

Existen algoritmos rápidos basados en dividir esta ecuación en partes impares y pares de la suma por separado (que da 2x N/2 sumas) que también es O(N) por valor individual, pero las 2 mitades son las mismas ecuaciones +/- algún ajuste constante. Entonces la mitad se puede calcular directamente desde el primero. Esto lleva a O(N/2) por valor individual. si aplica esto recursivamente, obtiene O(log(N)) por valor individual. Entonces todo se convirtió en O(N.log(N)) que es increíble pero también agrega estas restricciones:

¡Todos los DFFT necesitan que el conjunto de datos de entrada tenga el mismo tamaño que la potencia de dos!

Entonces puede dividirse recursivamente. El relleno cero para la mayor potencia más cercana de 2 se usa para tamaños de conjuntos de datos no válidos (en tecnología de audio a veces incluso con cambio de fase). Mira aquí:

mina Complex-> dominio complejo DFT, DFFT en C ++
algunos consejos sobre la construcción de algoritmos como FFT

Números complejos

c = a + i*b
c es un número complejo
a es su parte real (Re)
b es su parte imaginaria (Im)
i*i=-1 es unidad imaginaria

entonces el cálculo es así

adición:

c0+c1=(a0+i.b0)+(a1+i.b1)=(a0+a1)+i.(b0+b1)

multiplicación:

c0*c1=(a0+i.b0)*(a1+i.b1) =a0.a1+i.a0.b1+i.b0.a1+i.i.b0.b1 =(a0.a1-b0.b1)+i.(a0.b1+b0.a1)

real -> conversión compleja:

complex = real+i.0

[notas]

no olvide que necesita convertir datos a diferentes arreglos (no en su lugar)
la constante de normalización en la recursión de FFT es complicada (generalmente algo como /=log2(N) también depende de la condición de interrupción de la recursión)
no te olvides de detener la recursión si N=1 or 2 ...
cuidado, FPU puede desbordarse en grandes conjuntos de datos ( N es grande)
aquí algunas ideas para DFT / DFFT
aquí 2D FFT y ejemplo de envoltura
generalmente la fórmula de Euler se usa para calcular e^(ix)=cos(x)+i.sin(x)