En esta sección introducimos álgebras polinómicas y explicamos cómo se asocian a las transformaciones. Entonces identificamos esta conexión para el DFT. Posteriormente utilizamos álgebras polinomiales para derivar la FFT de Cooley-Tukey.
Álgebra polinómica
Un álgebra\(\mathbb{A}\) es un espacio vectorial que también proporciona una multiplicación de sus elementos de tal manera que sostiene la ley de distributividad (ver enlace para una definición completa). Los exampeles incluyen los conjuntos de números complejos\(\mathbb{C}\) o reales o\(\mathbb{R}\), y los conjuntos de polinomios complejos o reales en la variable\(s: \mathbb{C}[s]\) o\(\mathbb{R}[s].\)
El jugador clave en este capítulo es el álgebra polinómica. Dado un polinomio fijo\(P(s)\) de grado\(\text{deg}(P)=N\), definimos un álgebra polinómica como el conjunto
\[\mathbb{C}[s]/P(s)=\{X(s)\,|\,\text{deg}\,(X)\lt\text{deg}(P)\} \nonumber \]
de polinomios de grado menor que\(N\) con módulo de adición y multiplicación\(P\). Visto como un espacio vectorial, de\(\mathbb{C}[s]/P(s)\) ahí que tenga dimensión\(N\).
Cada polinomio\(X(s) \in \mathbb{C}[s]\) se reduce a un\(R(s)\) módulo polinómico único\(P(s)\) de grado menor que el que\(N.\,R(s)\) se calcula usando la división con el resto, a saber
\[X(s)=Q(s)P(s)+R(s),\;\text{deg}\,(R)\lt\text{deg}\,(P) \nonumber \]
En cuanto a esta ecuación, el módulo\(P,P(s)\) se convierte en cero, y obtenemos
\[X(s)\equiv R(s)\,\text{mod}\,P(s) \nonumber \]
Leemos esta ecuación como "\(X(s)\)es congruente (o igual)\(R(s)\) módulo”\(P(s)\). También escribiremos\(X(s)\,\text{mod}\,P(s)\) para denotar que\(X(s)\) se reduce el módulo\(P(s)\). Obviamente,
\[P(s) \equiv 0\,\text{mod}\,P(s) \nonumber \]
Como ejemplo sencillo consideramosA=C[s]/(s2-1)A=C[s]/(s2-1)“role="presentación” style="position:relative;” tabindex="0">
\[\mathbb{A}=\mathbb{C}[s]/(s^2-1) \nonumber \]
que tiene dimensión\(2\). Una posible base esb=(1,s)b=(1,s)“role="presentación” style="position:relative;” tabindex="0"> \(b=(1,s)\). En\(\mathbb{A}\), por ejemplo,
\[s\cdot (s+1)=s^2+s\equiv s+1\; \text{mod}\; (s^2-1) \nonumber \]
obtenido a través de división con descanso
\[s^2+s=1\cdot (s^2-1)+(s+1) \nonumber \]
o simplemente\(s^2\) sustituyendo por 1 (ya que\((s^2-1)=0\) implica\(s^2=1\)).
Teorema del resto chino (CRT)
Asumir\(P(S)=Q(s)R(s)\) factores en dos polinomios coprimos (sin factores comunes)\(Q\) y\(R\). Entonces el teorema del resto chino (CRT) para polinomios es el mapeo lineal, más precisamente, isomorfismo de álgebras o isomorfismo de\(\mathfrak{A}\) -módulos.
\[\Delta : \mathbb{C}[s]/P(s)\rightarrow \mathbb{C}[s]/Q(s)\oplus \mathbb{C}[s]/R(s) \nonumber \]
\[X(s) \mapsto (X(s)\: \text{mod}\: Q(s),X(s)\: \text{mod}\: R(s)) \nonumber \]
Aquí,\(\oplus\) es el producto cartesiano de espacios vectoriales con operación elementwise (también llamada suma directa externa). En palabras, el CRT afirma que la computación (suma, multiplicación, multiplicación escalar) en\(\mathbb{C}[s]/P(s)\) equivale a computar en paralelo en\(\mathbb{C}[s]/Q(s)\) y\(\mathbb{C}[s]/R(s)\).
Si elegimos bases\(b,c,d\) en los tres álgebras polinomiales, entonces se\(\Delta\) pueden expresar como una matriz. Como es habitual con el mapeo lineal, esta matriz se obtiene mapeando cada elemento de\(b\) con\(\Delta\), expresándolo en la concatenación\(c\cup d\) de las bases\(c\) y\(d\), y escribiendo los resultados en las columnas de la matriz.
Como ejemplo, consideramos de nuevo el polinomioP(s)=s2-1=(s-1)(s+1)P(s)=s2-1=(s-1)(s+1)“role="presentación” style="position:relative;” tabindex="0">
\[P(s)=s^2-1=(s-1)(s+1) \nonumber \]
y la descomposición del CRT
\[\Delta :\mathbb{C}[s]/(s^2-1)\rightarrow \mathbb{C}[s]/(s-1)\oplus \mathbb{C}[s]/(s+1) \nonumber \]
Como bases, elegimos\(b=(1,x),c=(1),d=(1).\Delta (1)=(1,1)\) con el mismo vector de coordenadas en\(c\cup d=(1,1)\). Además, debido a\(x\equiv 1\: \text{mod}\: (x-1)\) y\(x\equiv -1\: \text{mod}\: (x+1)\),\(\Delta (x)=(x,x)\equiv (1,-1)\) con el mismo vector de coordenadas. Así,\(\Delta\) en forma de matriz se encuentra la llamada matriz de mariposa, que es una DFT de tamaño 2:
\[DFT_2=\begin{bmatrix} 1 & 1\\ 1 & -1 \end{bmatrix} \nonumber \]
Transformas polinomiales
Supongamos que\(P(s)\in \mathbb{C}[s]\) tiene ceros distintos por paresα=(α0,⋯,αN-1)α=(α0,⋯,αN-1)“role="presentación” style="position:relative;” tabindex="0">\(\alpha =\alpha _0,...,\alpha _N-1\). Entonces el CRT se puede usar para descomponerse completamenteC[s]/P(s)C[s]/P(s)“role="presentation” style="position:relative;” tabindex="0"> \(\mathbb{C}[s]/P(s)\)en su espectro:
\[\Delta :\mathbb{C}[s]/P(s)\rightarrow \mathbb{C}[s]/(s-\alpha _0)\oplus ...\oplus \mathbb{C}[s]/(s-\alpha _{N-1}) \nonumber \]
\[X(s)\mapsto (X(s)\: \text{mod}\: (s-\alpha _0),...,X(s)\: \text{mod}\: (s-\alpha _{N-1}))=(s(\alpha _0),...,s(\alpha _{N-1})) \nonumber \]
Si elegimos una baseb=(P0(s),⋯,PN-1(s))b=(P0(s),⋯,PN-1(s))“role="presentation” style="position:relative;” tabindex="0">\(b=(P_0(s),...,P_{N-1}(s))\) enC[s]/P(s)C[s]/P(s)“role="presentation” style="position:relative;” tabindex="0">\(\mathbb{C}[s]/P(s)\) y basesbi=(1)bi=(1)“role="presentation” style="position:relative;” tabindex="0">\(b_i=(1)\) en cada\(\mathbb{C}[s]/(s-\alpha _i)\) entonces\(\Delta\), como un mapeo lineal, se representa mediante una matriz. La matriz se obtiene mapeando cada elemento basePnPn“role="presentation” style="position:relative;” tabindex="0"> \(P_n,\: 0\leq n< N\), y recogiendo los resultados en las columnas de la matriz. El resultado es:
\[\mathfrak{P}_{b,\alpha }=\left [ P_n(\alpha _k) \right ]_{0\leq k,n< N} \nonumber \]
y se llama la transformación polinómica paraA=C[s]/P(s)A=C[s]/P(s)“role="presentation” style="position:relative;” tabindex="0"> \(\mathfrak{A}=\mathbb{C}[s]/P(s)\)con base\(b\)
Si, en general, elegimosbi=(βi)bi=(βi)“role="presentation” style="position:relative;” tabindex="0"> \(b_i=(\beta _i)\)como base espectral, entonces la matriz correspondiente a la ecuación de descomposición es la transformada polinómica escalada
\[\text{diag}_{0\leq k< N}(1/\beta _n)\mathfrak{P}_{b,\alpha } \nonumber \]
donde\(\text{diag}_{0\leq k< N}(\gamma _n)\) denota una matriz diagonal con entradas diagonalesγnγn“role="presentación” style="position:relative;” tabindex="0"> \(\gamma _n\).
Nos referimos conjuntamente a las transformaciones polinómicas, escaladas o no, como transformadas de Fourier.
DFT como Transformación Polinómica
Demostramos que elDFTNDFTN“role="presentation” style="position:relative;” tabindex="0">\(\text{DFT}_N\) es una transformación polinómica paraA=C[s]/(sN-1)A=C[s]/(sN-1)“role="presentation” style="position:relative;” tabindex="0"> \(\mathfrak{A}=\mathbb{C}[s]/(s^N-1)\)con base\(b=1,s,...,s^{N-1}\). A saber,
\[s^{N-1}=\prod_{0\leq k< N}(x-W_{N}^{k}) \nonumber \]
lo que significa que\(\Delta\) toma la forma
\[\Delta :\mathbb{C}[s]/(s^N-1)\rightarrow \mathbb{C}[s]/(s-W_{N}^{0})\oplus ...\oplus \mathbb{C}[s]/(s-W_{N}^{N-1}) \nonumber \]
\[X(s)\mapsto (X(s)\: \text{mod}\: (s-W_{N}^{0}),...,X(s)\: \text{mod}\: (s-W_{N}^{N-1}))=(X(W_{N}^{0}),...,X(W_{N}^{N-1})) \nonumber \]
La transformada polinomial asociada se convierte por lo tanto
\[\mathfrak{P}_{b,\alpha }=\left [ W_{N}^{kn} \right ]_{0\leq k,n< N}=\text{DFT}_N \nonumber \]
Esta interpretación de la DFT se conoce desde hace mucho tiempo y aclara la conexión entre los puntos de evaluación y la convolución circular en las ecuaciones.
\(1-4\)Se definen los DFT de tipos,\(1\) siendo el tipo el DFT estándar. En el marco algebraico, el tipo\(3\) se obtiene eligiendoA=C[s]/(sN+1)A=C[s]/(sN+1)“role="presentation” style="position:relative;” tabindex="0"> \(\mathfrak{A}=\mathbb{C}[s]/(s^N+1)\)como álgebra con la misma base que antes:
\[\mathfrak{P}_{b,\alpha }=\left [ W_{N}^{(k+1/2)n} \right ]_{0\leq k,n< N}=\text{DFT}-3_{N} \nonumber \]
Las DFT de tipo\(2\) y\(4\) son transformadas polinómicas escaladas.
