3.3: La DFT como Evaluación Polinómica

La\(\mathit{Z}\) -transformada de una secuencia numérica\(x(n)\) se define como:

\[X(z)=\sum_{n=0}^{\infty }x(n)z^{-n} \nonumber \]

que es lo mismo que la descripción polinómica en la Ecuación 3.1.1 pero con un exponente negativo. Para una\(N\) secuencia de longitud finita, la ecuación anterior se convierte en

\[X(z)=\sum_{n=0}^{\infty }x(n)z^{-n} \nonumber \]

\[X(z)=x(0)+x(1)z^{-1}+x(2)z^{-2}+...+x(N-1)z^{-N+1} \nonumber \]

Este polinomio de\(N-1\) orden toma los valores de la DFT de\(x(n)\) cuando se evalúa en

\[z=e^{j2\pi k/N} \nonumber \]

lo que da

\[C(k)=X(z)\mid _{z=e^{j2\pi k/N}}=\sum_{n=0}^{N-1}x(n)e^{-j2\pi nk/N} \nonumber \]

En términos del polinomio de exponente positivo de la ecuación anterior, la DFT es:

\[C(k)=X(s)\mid _{s=W^{k}} \nonumber \]

donde

\[W=e^{-j2\pi /N} \nonumber \]

es una\(N^{th}\) raíz de unidad (\(W\)elevarse al\(N^{th}\) poder da uno). Los\(N\) valores de la DFT se encuentran\(X(s)\) evaluados en las\(N\)\(N^{th}\) raíces de la unidad que están igualmente espaciadas alrededor del círculo unitario en el plano del complejo s.

Un método de evaluación\(X(z)\) es la llamada regla de Horner o evaluación anidada. Cuando se expresa como un cálculo recursivo, la regla de Horner se convierte en el algoritmo de Goertzel que tiene algunas ventajas computacionales especialmente cuando solo se necesitan unos pocos valores de la DFT.

Otro método para evaluar\(X(s)\) es el módulo de reducción de residuos (\(s-W^k\)) como se muestra en la Ecuación 3.3.1 anterior. Cada evaluación requiere\(N\) multiplicaciones y por lo tanto,\(N^2\) multiplicaciones para los\(N\) valores de\(C(k)\).

\[C(k)=((X(s)))_{(s-W^{k})} \nonumber \]

Se puede lograr una reducción considerable en la aritmética requerida si algunas operaciones pueden compartirse entre las reducciones para diferentes valores de\(k\). Esto se hace llevando a cabo la reducción de residuos en etapas que se pueden compartir en lugar de hacerlo en un solo paso para cada una\(k\) en la ecuación anterior.

Los\(N\) valores de la DFT son valores de\(X(s)\) evaluados a\(s\) igual a las\(N\) raíces del polinomio

\[P(s)=s^{N}-1 \nonumber \]

que son\(W^k\). Primero, asumiendo que\(N\) es par, factor\(P(s)\) como:

\[P(s)=(s^{N}-1)=P_{1}(s)P_{2(s)}=(s^{N/2}-1)(s^{N/2}+1) \nonumber \]

X (s)\(X(s)\) se reduce el módulo de estos dos factores para dar dos polinomios de residuos,\(X_1(s)\) y\(X_2(s)\). Este proceso se repite factorizando\(P_1\) y reduciendo aún más\(X_1\) luego factorizando\(P_2\) y reduciendo\(X_2\). Esto se continúa hasta que los factores son de primer grado lo que da los valores de DFT deseados como en la Ecuación. Esto se ilustra para un DFT de longitud 8. El polinomio cuyas raíces son\(W^k\), factores como

\[P(s)=s^{8}-1 \nonumber \]

\[P(s)=[s^{4}-1][s^{4}+1] \nonumber \]

\[P(s)=[(s^{2}-1)(s^{2}+1)][(s^{2}-j)(s^{2}+j)] \nonumber \]

\[P(s)=[(s-1)(s+1)(s-j)(s+j)][s-a)(s+a)(s-ja)(s+ja)] \nonumber \]

donde

\[a^{2}=j \nonumber \]

La reducción\(X(s)\) por la primera factorización da dos polinomios de tercer grado:

\[X(s)=x_{0}+x_{1}s+x_{2}s^{2}+...+x_{7}s^{7} \nonumber \]

da los polinomios de residuos

\[X_{1}(s)=((X(S)))_{(s^{4}-1)}=(x_{0}+x_{4})+(x_{1}+x_{5})s+(x_{2}+x_{6})s^{2}+(x_{3}+x_{7})s^{3} \nonumber \]

\[X_{2}(s)=((X(S)))_{(s^{4}+1)}=(x_{0}-x_{4})+(x_{1}-x_{5})s+(x_{2}-x_{6})s^{2}+(x_{3}-x_{7})s^{3} \nonumber \]

Se llevan a cabo dos niveles más de reducción para finalmente dar el DFT. Un examen minucioso muestra que el algoritmo resultante es la diezmation-in-frequency radix-2 Cooley-Tukey FFT. Martens ha utilizado este enfoque para derivar un algoritmo DFT eficiente.

Se pueden desarrollar otros algoritmos y tipos de FFT utilizando representaciones polinómicas y algunos se presentan en la generalización en DFT y FFT - An Algebraica View.

Colaborador

• ContribeeBurrus