Conocer el álgebra polinomio subyacente a la DFT nos permite derivar la FFT Cooley-Tukey algebraicamente. Esto significa que en lugar de manipular la definición de DFT, manipulamos el álgebra polinómicaC[s]/(sN-1)C[s]/(sN-1)“role="presentación” style="position:relative;” tabindex="0"> \(\mathbb{C}[s]/(s^N-1)\). La idea básica es intuitiva. Mostramos que la DFT es la representación matricial de la ecuación de descomposición completa.La FFT de Cooley-Tukey ahora se deriva realizando esta descomposición en etapas como se muestra en la Fig. 7.3.1. Cada paso produce una matriz dispersa; por lo tanto,DFTNDFTN“role="presentation” style="position:relative;” tabindex="0"> \(\text{DFT}_N\)se factoriza en un producto de matrices dispersas, que será la representación matricial de la FFT de Cooley-Tukey.
Fig. 7.3.1 Idea básica detrás de la derivación algebraica de algoritmos tipo Cooley-Tukey
Esta descomposición escalonada puede formularse genéricamente para transformaciones polinómicas. Aquí, consideramos solo el DFT. Primero introducimos la notación matricial que usaremos y en particular el formalismo del producto Kronecker que se convirtió en corriente principal para los FFT. Luego primero derivamos la FFT de radix-2 usando una factorización desN-1sN-1“role="presentación” style="position:relative;” tabindex="0">\(s^N-1\). Posteriormente, se obtiene la FFT general-radix usando una descomposición desN-1sN-1“role="presentación” style="position:relative;” tabindex="0">sN-1sN-1“role="presentación” style="position:relative;” tabindex="0"> \(s^N-1\).
Notación Matricial
Denotamos elN×NN×N“role="presentation” style="position:relative;” tabindex="0"> matriz de\(N\times N\) identidad conININ“role="presentation” style="position:relative;” tabindex="0"> \(I_N\)y matrices diagonales con
\[\text{diag}_{0\leq k< N}(\gamma _k)=\begin{bmatrix} \gamma _0 & & & & \\ & . & & & \\ & & . & & \\ & & & . & \\ & & & & \gamma _{N-1} \end{bmatrix} \nonumber \]
ElN×NN×N“role="presentation” style="position:relative;” tabindex="0"> la matriz\(N\times N\) de permutación de zancada se define paraN=KMN=KM“role="presentation” style="position:relative;” tabindex="0"> \(N=KM\)por la permutación
\[L_{M}^{N}=iK+j\mapsto jM+i \nonumber \]
para\(0\leq i< K,\; 0\leq j< M\). Esta definición muestra queLMNLMN“role="presentation” style="position:relative;” tabindex="0"> \(L_{M}^{N}\)transpone una\(K\times M\) matriz almacenada en orden fila-mayor. Alternativamente, podemos escribir
\[L_{M}^{N}:i\mapsto \text{iM}\: \text{mod}\: N-1,\: \text{for}\: 0\leq i< N-1,\: N-1\mapsto N-1 \nonumber \]
Por ejemplo (·significa 0),
\[L_{2}^{6}=\begin{bmatrix} 1 & . & . & . & . & .\\ . & . & 1 & . & . & .\\ . & . & . & . & 1 & .\\ . & 1 & . & . & . & .\\ . & . & . & 1 & . & .\\ . & . & . & . & . & 1 \end{bmatrix} \nonumber \]
\(L_{N/2}^{N}\)a veces se llama el barajado perfecto.
Además, utilizamos operadores matriciales; es decir, la suma directa
\[A\oplus B=\begin{bmatrix} A & \\ & B \end{bmatrix} \nonumber \]
y el producto Kronecker o tensor
\[A\otimes B=\left [ a_{k,l}B \right ]_{k,l},\: \: \text{for}\: A=[a_{k,l}] \nonumber \]
En particular,
\[I_n\otimes A=A\oplus ...\oplus A=\begin{bmatrix} A & & & & \\ & . & & & \\ & & . & & \\ & & & . & \\ & & & & A \end{bmatrix} \nonumber \]
es diagonal de bloque.
También podemos construir una matriz más grande como una matriz de matrices, p.
\[\begin{bmatrix} A & B\\ B & A \end{bmatrix} \nonumber \]
Si se da un algoritmo para una transformada como un producto de matrices dispersas construidas a partir de las construcciones anteriores, entonces un algoritmo para la transposición o inversa de la transformada se puede derivar fácilmente usando propiedades matemáticas que incluyen
\[(AB)^T=B^TA^T,\; \; \; (AB)^{-1}=B^{-1}A^{-1} \nonumber \]
\[(A\oplus B)^T=A^T\oplus B^T,\; \; \; (A\oplus B)^{-1}=A^{-1}\oplus B^{-1} \nonumber \]
\[(A\otimes B)^T=A^T\otimes B^T,\; \; \; (A\otimes B)^{-1}=A^{-1}\otimes B^{-1} \nonumber \]
Las matrices de permutación son ortogonales, es decir,\(P^T=P^{-1}\). La transposición o inversión de matrices diagonales es obvia.
Radix-2 FFT
El DFT se descompone\(\mathfrak{A}=\mathbb{C}[s]/(s^N-1)\) con baseb=(1,s,⋯,sN-1)b=(1,s,⋯,sN-1)“role="presentation” style="position:relative;” tabindex="0">\(b=1,s,...,s^{N-1}\) como se muestra en la ecuación. AsumimosN=2MN=2M“role="presentación” style="position:relative;” tabindex="0"> \(N=2M\). Entonces
\[s^{2M}-1=(s^M-1)(s^M+1) \nonumber \]
factores y podemos aplicar el TRC en los siguientes pasos:
\[\mathbb{C}[s]/(s^N-1) \nonumber \]
\[\rightarrow \mathbb{C}[s]/(s^M-1)\oplus \mathbb{C}[s]/(s^M+1) \nonumber \]
\[\rightarrow \underset{0\leq i< M}{\oplus }\mathbb{C}[s]/(x-W_{N}^{2i})\oplus \underset{0\leq i< M}{\oplus }\mathbb{C}[s]/(x-W_{M}^{2i+1}) \nonumber \]
\[\rightarrow \underset{0\leq i< N}{\oplus }\mathbb{C}[s]/(x-W_{N}^{i}) \nonumber \]
Como bases en las álgebras más pequeñas\(\mathbb{C}[s]/(s^M-1)\) y\(\mathbb{C}[s]/(s^M+1)\), elegimos\(c=d=1,s,...,s^{M-1}\). La derivación de un algoritmo paraDFTNDFTN“role="presentation” style="position:relative;” tabindex="0">\(\text{DFT}_N\) basado en las ecuaciones es ahora completamente mecánico al leer la matriz para cada uno de los tres pasos de descomposición. El producto de estas matrices es igual alDFTNDFTN“role="presentación” style="position:relative;” tabindex="0"> \(\text{DFT}_N\).
Primero, derivamos la matriz de cambio baseBB“role="presentation” style="position:relative;” tabindex="0">\(B\) correspondiente a la ecuación. Para ello, tenemos que expresar los elementos basesn∈bsn∈b“role="presentation” style="position:relative;” tabindex="0">\(s^n\in b\) en la base\(c\cup d\); los vectores de coordenadas son las columnas deBB“role="presentación” style="position:relative;” tabindex="0">\(B\). Porque en realidad\(0\leq n< M,\: s^n\) está contenido enBB“role="presentation” style="position:relative;” tabindex="0">\(c\) yBB“role="presentación” style="position:relative;” tabindex="0">\(d\)cc“role="presentation” style="position:relative;” tabindex="0">, así que el primeroBB“role="presentación” style="position:relative;” tabindex="0">\(M\)MM“role="presentation” style="position:relative;” tabindex="0"> columnas deBB“role="presentation” style="position:relative;” tabindex="0"> \(B\)son
\[B=\begin{bmatrix} I_M & \ast \\ I_M & \ast \end{bmatrix} \nonumber \]
donde se\(\ast\) determinan las entradas a continuación. Para los elementos base\(s^{M+n},\: 0\leq n< M\), tenemos
\[s^{M+n}=s^n\: \text{mod}\: (s^M-1) \nonumber \]
\[s^{M+n}=-s^n\: \text{mod}\: (s^M+1) \nonumber \]
lo que arroja el resultado final
\[B=\begin{bmatrix} I_M & I_M\\ I_M & -I_M \end{bmatrix}=\text{DFT}_2\otimes I_M \nonumber \]
A continuación, consideramos la ecuación de pasos. \(\mathbb{C}[s]/(s^M-1)\)se descompone porDFTMDFTM“role="presentation” style="position:relative;” tabindex="0"> \(\text{DFT}_M\)y\(\mathbb{C}[s]/(s^M+1)\) por\(\text{DFT}-3_{M}\) en la ecuación.
Finalmente, la permutación en paso en la ecuación es la mezcla perfectaLMNLMN“role="presentation” style="position:relative;” tabindex="0">\(L_{M}^{N}\), que intercala los componentes espectrales par e impar (exponentes pares e impares deWNWN“role="presentation” style="position:relative;” tabindex="0"> \(W_N\)).
El algoritmo final obtenido es
\[\text{DFT}_{2M}=L_{M}^{N}(\text{DFT}_{M}\oplus \text{DFT}-3_{M})(\text{DFT}_{2}\otimes I_M) \nonumber \]
\[\text{DFT}_{2M}=L_{M}^{N}(I_2\otimes \text{DFT}_{M})(I_M\oplus D_M)(\text{DFT}_{2}\otimes I_M) \nonumber \]
La última expresión es la\(2\) radix-decimation-in-frequency Cooley-Tukey FFT. La correspondiente versión decimation-in-time se obtiene por transposición usando la ecuación y la simetría de la DFT:
\[\text{DFT}_{2M}=(\text{DFT}_{2}\otimes I_M))(I_M\oplus D_M)(I_2\otimes \text{DFT}_{M})L_{2}^{N} \nonumber \]
Las entradas de la matriz diagonalIM⊕DMIM⊕DM“role="presentation” style="position:relative;” tabindex="0"> \(I_M\oplus D_M\)se denominan comúnmente factores de twiddle.
FFT general
Para derivar algebraicamente la FFT de base general, utilizamos la propiedad de descomposición desN-1sN-1“role="presentación” style="position:relative;” tabindex="0">\(s^N-1\). A saber, siN=KMN=KM“role="presentation” style="position:relative;” tabindex="0"> \(N=KM\)entonces
\[s^N-1=(s^M)^K-1 \nonumber \]
Descomposición significa que el polinomio se escribe como la composición de dos polinomios: aquí,\(s^M\) se inserta en\(s^K-1\). Tenga en cuenta que esta es una propiedad especial: la mayoría de los polinomios no se descomponen.
A partir de esta descomposición polinómica, obtenemos la siguiente descomposición escalonada de\(\mathbb{C}[s]/(s^N-1)\), la cual es más general que la anterior en las ecuaciones. La idea básica es descomponerse primero con respecto al polinomio externotK-1tK-1“role="presentation” style="position:relative;” tabindex="0"> \(t^K-1,\: t=s^M\)y luego completamente.
\[\mathbb{C}[s]/(s^N-1)=\mathbb{C}[x]/\left ( (s^M)^K-1 \right ) \nonumber \]
\[\rightarrow \underset{0\leq i< K}{\oplus }\mathbb{C}[s]/(s^M-W_{K}^{i}) \nonumber \]
\[\rightarrow \underset{0\leq i< K}{\oplus }\underset{0\leq j< M}{\oplus }\mathbb{C}[s]/(x-W_{N}^{jK+i}) \nonumber \]
\[\rightarrow \underset{0\leq i< N}{\oplus }\mathbb{C}[s]/(x-W_{N}^{i}) \nonumber \]
Como bases en los álgebras más pequeños\(\mathbb{C}[s]/(s^M-W_{K}^{i})\) elegimosci=(1,s,⋯,sM-1)ci=(1,s,⋯,sM-1)“role="presentación” style="position:relative;” tabindex="0"> \(c_i=1,s,...,s^{M-1}\). Como antes, la derivación es completamente mecánica a partir de aquí: sólo se tienen que leer las tres matrices correspondientes a las ecuaciones.
El primer paso de descomposición requiere que calculemos\(s^n\: \text{mod}\: \left ( s^M-W_{K}^{i} \right ),\: 0\leq n< N\). Para ello, descomponemos el índice\(n\) como\(n=lM+m\) y calculamos
\[s^n=s^{lM+m}=(s^M)^ls^m\equiv W_{k}^{lm}s^m\: \text{mod}\: (s^M-W_{K}^{i}) \nonumber \]
Esto demuestra que la matriz para viene dada por:\(\text{DFT}_K\otimes I_M\)
En la ecuación escalonada, cada uno\(\mathbb{C}[s]/(s^M-W_{K}^{i})\) está completamente descompuesto por su transformada polinómica
\[\text{DFT}_M(i,K)=\text{DFT}_{M}.\text{diag}_{0\leq i< M}(W_{N}^{ij}) \nonumber \]
En este punto,\(\mathbb{C}[s]/(s^N-1)\) está completamente descompuesto, pero el espectro se ordena de acuerdo ajK+ijK+i“role="presentation” style="position:relative;” tabindex="0">\(jK+i,\: 0\leq i< M,\: 0\leq j< K,\) (\(j\)corre más rápido). El orden deseado esiM+jiM+j“role="presentación” style="position:relative;” tabindex="0"> \(iM+j\).
Así, en la ecuación escalonada, necesitamos aplicar la permutación\(jK+i\mapsto iM+j\), que es exactamente la permutación zancadaLMNLMN“role="presentation” style="position:relative;” tabindex="0"> \(L_{M}^{N}\)en la ecuación.
En resumen, se obtiene la FFT de decimatización en frecuencia de Cooley-Tukey con base arbitraria:
\[L_{M}^{N}\left ( \underset{0\leq i< K}{\oplus }\text{DFT}_M .\text{diag}_{0\leq i< M}\left ( W_{N}^{ij}\right )\right )(\text{DFT}_k\otimes I_M) \nonumber \]
\[=L_{M}^{N}(I_K{\otimes }\text{DFT}_M )T_{M}^{N}(\text{DFT}_k\otimes I_M) \nonumber \]
La matrizTMNTMN“role="presentation” style="position:relative;” tabindex="0"> \(T_{M}^{N}\)es diagonal y generalmente se llama la matriz de twiddle. La transposición usando la ecuación produce la versión correspondiente de la decimatización en el tiempo:
\[(\text{DFT}_k\otimes I_M)T_{M}^{N}(I_K{\otimes }\text{DFT}_M )L_{K}^{N} \nonumber \]