Saltar al contenido principal

# 13.3: Derivar la Transformada Rápida de Fourier

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$

$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$

( \newcommand{\kernel}{\mathrm{null}\,}\) $$\newcommand{\range}{\mathrm{range}\,}$$

$$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$

$$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$

$$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$

$$\newcommand{\Span}{\mathrm{span}}$$

$$\newcommand{\id}{\mathrm{id}}$$

$$\newcommand{\Span}{\mathrm{span}}$$

$$\newcommand{\kernel}{\mathrm{null}\,}$$

$$\newcommand{\range}{\mathrm{range}\,}$$

$$\newcommand{\RealPart}{\mathrm{Re}}$$

$$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$

$$\newcommand{\Argument}{\mathrm{Arg}}$$

$$\newcommand{\norm}[1]{\| #1 \|}$$

$$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$

$$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\AA}{\unicode[.8,0]{x212B}}$$

$$\newcommand{\vectorA}[1]{\vec{#1}} % arrow$$

$$\newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow$$

$$\newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vectorC}[1]{\textbf{#1}}$$

$$\newcommand{\vectorD}[1]{\overrightarrow{#1}}$$

$$\newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}}$$

$$\newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}}$$

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$

$$\newcommand{\avec}{\mathbf a}$$ $$\newcommand{\bvec}{\mathbf b}$$ $$\newcommand{\cvec}{\mathbf c}$$ $$\newcommand{\dvec}{\mathbf d}$$ $$\newcommand{\dtil}{\widetilde{\mathbf d}}$$ $$\newcommand{\evec}{\mathbf e}$$ $$\newcommand{\fvec}{\mathbf f}$$ $$\newcommand{\nvec}{\mathbf n}$$ $$\newcommand{\pvec}{\mathbf p}$$ $$\newcommand{\qvec}{\mathbf q}$$ $$\newcommand{\svec}{\mathbf s}$$ $$\newcommand{\tvec}{\mathbf t}$$ $$\newcommand{\uvec}{\mathbf u}$$ $$\newcommand{\vvec}{\mathbf v}$$ $$\newcommand{\wvec}{\mathbf w}$$ $$\newcommand{\xvec}{\mathbf x}$$ $$\newcommand{\yvec}{\mathbf y}$$ $$\newcommand{\zvec}{\mathbf z}$$ $$\newcommand{\rvec}{\mathbf r}$$ $$\newcommand{\mvec}{\mathbf m}$$ $$\newcommand{\zerovec}{\mathbf 0}$$ $$\newcommand{\onevec}{\mathbf 1}$$ $$\newcommand{\real}{\mathbb R}$$ $$\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}$$ $$\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}$$ $$\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}$$ $$\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}$$ $$\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$$ $$\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}$$ $$\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$$ $$\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}$$ $$\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}$$ $$\newcommand{\laspan}[1]{\text{Span}\{#1\}}$$ $$\newcommand{\bcal}{\cal B}$$ $$\newcommand{\ccal}{\cal C}$$ $$\newcommand{\scal}{\cal S}$$ $$\newcommand{\wcal}{\cal W}$$ $$\newcommand{\ecal}{\cal E}$$ $$\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}$$ $$\newcommand{\gray}[1]{\color{gray}{#1}}$$ $$\newcommand{\lgray}[1]{\color{lightgray}{#1}}$$ $$\newcommand{\rank}{\operatorname{rank}}$$ $$\newcommand{\row}{\text{Row}}$$ $$\newcommand{\col}{\text{Col}}$$ $$\renewcommand{\row}{\text{Row}}$$ $$\newcommand{\nul}{\text{Nul}}$$ $$\newcommand{\var}{\text{Var}}$$ $$\newcommand{\corr}{\text{corr}}$$ $$\newcommand{\len}[1]{\left|#1\right|}$$ $$\newcommand{\bbar}{\overline{\bvec}}$$ $$\newcommand{\bhat}{\widehat{\bvec}}$$ $$\newcommand{\bperp}{\bvec^\perp}$$ $$\newcommand{\xhat}{\widehat{\xvec}}$$ $$\newcommand{\vhat}{\widehat{\vvec}}$$ $$\newcommand{\uhat}{\widehat{\uvec}}$$ $$\newcommand{\what}{\widehat{\wvec}}$$ $$\newcommand{\Sighat}{\widehat{\Sigma}}$$ $$\newcommand{\lt}{<}$$ $$\newcommand{\gt}{>}$$ $$\newcommand{\amp}{&}$$ $$\definecolor{fillinmathshade}{gray}{0.9}$$

Para derivar la FFT, asumimos que la duración de la señal es una potencia de dos:$$N=2^l$$. Considere lo que sucede con los elementos pares e impares de la secuencia en el cálculo de DFT.

\begin{align}S(k) &=s(0)+s(2) e^{(-j) \frac{2 \pi 2 k}{N}}+\ldots+s(N-2) e^{(-j) \frac{2 \pi(N-2) k}{N}}+s(1) e^{(-j) \frac{2 \pi k}{N}}+s(3) e^{(-j) \frac{2 \pi \times (2+1) k}{N}}+\ldots+s(N-1) e^{(-j) \frac{2 \pi(N-2+1) k}{N}} \nonumber \\ &=s(0)+s(2)e^{(-j)\frac{2\pi k}{\frac{N}{2}}} + \ldots + s(N-2)e^{(-j) \frac{2 \pi\left(\frac{N}{2}-1\right) k}{\frac{N}{2}}} +\left( s(1)+s(3) e^{(-j) \frac{2 \pi k}{\frac{N}{2}}}+\dots+s(N-1) e^{(-j) \frac{2 \pi\left(\frac{N}{2}-1\right) k}{\frac{N}{2}}}\right) e^{\frac{-(j 2 \pi k)}{N}} \end{align} \nonumber

Cada término entre corchetes tiene la forma de un DFT de$$\frac{N}{2}$$ longitud. El primero es un DFT de los elementos pares y el segundo de los elementos impares. El primer DFT se combina con el segundo multiplicado por el exponencial complejo$$e^{\frac{-(j2\pi k)}{N}}$$. Las transformaciones de media longitud se evalúan cada una en índices de frecuencia$$k \in\{0, \ldots, N-1\}$$. Normalmente, el número de índices de frecuencia en un cálculo de DFT oscila entre cero y la longitud de transformación menos uno. La ventaja computacional de la FFT proviene del reconocimiento de la naturaleza periódica de la transformada discreta de Fourier. La FFT simplemente reutiliza los cálculos realizados en las transformaciones de media longitud y los combina a través de adiciones y la multiplicación por$$e^{\frac{-(j2\pi k)}{N}}$$, que no es periódica sobre$$\frac{N}{2}$$, para reescribir el Length-N DFT. La figura$$\PageIndex{1}$$ ilustra esta descomposición. Tal como está, ahora calculamos dos$$\frac{N}{2}$$ transformaciones de longitud (complejidad$$2O(\frac{N^2}{4})$$), multiplicamos una de ellas por la exponencial compleja (complejidad$$O(N)$$) y agregamos los resultados (complejidad$$O(N)$$). En este punto, la complejidad total aún está dominada por los cálculos de DFT de longitud media, pero el coeficiente de proporcionalidad se ha reducido.

Ahora por la diversión. Porque$$N=2^l$$, cada una de las transformaciones de media longitud se puede reducir a dos transformadas de un cuarto de longitud, cada una de estas a dos transformadas de octava longitud, etc. Esta descomposición continúa hasta que nos quedamos con transformaciones de longitud-2. Esta transformación es bastante simple, involucrando solo adiciones. Así, la primera etapa de la FFT tiene transformaciones de$$\frac{N}{2}$$ longitud-2 (ver la parte inferior de la Figura$$\PageIndex{1}$$). Los pares de estas transformaciones se combinan sumando una a la otra multiplicada por un exponencial complejo. Cada par requiere 4 adiciones y 4 multiplicaciones, dando un número total de cómputos igualados$$8 \frac{N}{4}=\frac{N}{2}$$. Este número de cómputos no cambia de una etapa a otra. Debido a que el número de etapas, el número de veces que la longitud se puede dividir por dos, es igual$$\log_2 N$$, la complejidad de la FFT es$$O(N \log N)$$.

Hacer un ejemplo hará que los ahorros computacionales sean más obvios. Veamos los detalles de un DFT de longitud 8. Como se muestra en la Figura$$\PageIndex{1}$$, primero descomponemos el DFT en dos DFT de longitud 4, con las salidas sumadas y restadas juntas en pares. Considerando Figura$$\PageIndex{1}$$ como el índice de frecuencia va de 0 a 7, reciclamos valores de los DFT de longitud-4 al cálculo final debido a la periodicidad de la salida de DFT. Al examinar cómo se recopilan los pares de salidas, creamos el elemento computacional básico conocido como mariposa (Figura$$\PageIndex{2}$$).

Al considerar juntos los cálculos que involucran frecuencias de salida comunes de las dos DFT de media longitud, vemos que las dos multiplica complejas están relacionadas entre sí, y podemos reducir aún más nuestro trabajo computacional. Al descomponer aún más las DFT de longitud 4 en dos DFT de longitud 2 y combinar sus salidas, llegamos al diagrama que resume la transformada rápida de Fourier de longitud 8 (Figura$$\PageIndex{1}$$). Si bien la mayoría de las multiplicidades complejas son bastante simples (multiplicando por$$e^{-(j \pi)}$$ medios negando partes reales e imaginarias), vamos a contarlas con el propósito de evaluar la complejidad como multiplicaciones complejas completas. Tenemos$$2N=16$$ multiplicaciones y adiciones$$\frac{N}{2}=4$$ complejas para cada etapa y$$\log_2 N = 3$$ etapas, haciendo que el número de cálculos básicos$$\frac{3N}{2}\log_2 N$$ como se predijo.

Ejercicio$$\PageIndex{1}$$

Tenga en cuenta que el orden de la secuencia de entrada en las dos partes de Figura$$\PageIndex{1}$$ no es exactamente el mismo. ¿Por qué no? ¿Cómo se determina el orden?

Contestar

El panel superior no ha utilizado el algoritmo FFT para calcular los DFT de longitud 4 mientras que el inferior tiene. El orden está determinado por el algoritmo.

Se descubrieron otros algoritmos “rápidos”, todos los cuales hacen uso de cuántos factores comunes tiene la longitud de transformación N. En teoría de números, el número de factores primos que tiene un entero dado mide qué tan compuesto es. Los números$$16$$ y$$81$$ son altamente compuestos (iguales$$2^4$$ y$$3^4$$ respectivamente), el número$$18$$ es menos so ($$2^1 3^2$$), y$$17$$ no en absoluto (es primo). En más de treinta años de desarrollo del algoritmo de transformada de Fourier, el algoritmo original de Cooley-Tukey es, de lejos, el más utilizado. Es tan eficiente desde el punto de vista computacional que las longitudes de transformación de potencia de dos se utilizan con frecuencia independientemente de cuál sea la longitud real de los datos.

This page titled 13.3: Derivar la Transformada Rápida de Fourier is shared under a CC BY license and was authored, remixed, and/or curated by Richard Baraniuk et al..