7.1: Introducción
- Page ID
- 87090
Objetivos de aprendizaje
- Estudiar la descripción algebraica de la DFT y sobre la derivación algebraica de la FFT de base general Cooley-Tukey a partir de Factoring the Signal Processing Operators.
por Markus Pueschel, Universidad Carnegie Mellon
En el procesamiento de señal de tiempo discreto infinito o no periódico, existe una fuerte conexión entre la\(z\) transformada, la serie Laurent, la convolución y la transformada de Fourier de tiempo discreto (DTFT). Como cabría esperar, existe una conexión similar para el DFT pero lleva sorpresas. A saber, resulta que el marco adecuado para el DFT requiere operaciones de módulo de polinomios, lo que significa trabajar con los llamados álgebras polinomiales. Asociado con álgebras polinómicas se encuentra el teorema del resto chino, que describe el DFT algebraicamente y puede ser utilizado como una herramienta para derivar concisamente diversos FFT así como algoritmos de convolución (ver también Algoritmos DFT cortos de Winograd). El marco de álgebra polinomial se desarrolló completamente para el procesamiento de señales como parte de la teoría algebraica de procesamiento de señales (ASP). ASP identifica la estructura subyacente a muchas transformaciones utilizadas en el procesamiento de señales, proporciona una visión profunda de sus propiedades y permite la derivación de sus algoritmos rápidos. Aquí nos enfocamos en la descripción algebraica de la DFT y en la derivación algebraica de la FFT general Cooley-Tukey de Factoring the Signal Processing Operators. La derivación hará uso y extenderá la Descripción Polinomial de Señales. Comenzamos por motivar la aparición de operaciones de módulo.
La\(z\) -transform asocia con señales discretas infinitas\(X+(\ldots,x(-1),x(0),x(1),\dots)\) una serie Laurent:
\[X \mapsto X(s) = \sum_{n \in \mathbb{Z}} x(n)s^n \nonumber \]
Aquí solíamos\(s=z^{-1}\) simplificar la notación en lo siguiente. El DTFT de\(X\) es la evaluación de\(X(s)\) en el círculo unitario
\[X(e^{-jw}), -\pi\lt\omega\le\pi \nonumber \]
Finalmente, el filtrado o convolución (lineal) es simplemente la multiplicación de las series Laurent,
\[X \mapsto X(s) = \sum_{n \in \mathbb{Z}}^{N-1} x(n)s^n \nonumber \]
y que el DFT es una evaluación de estos polinomios. En efecto, la definición del DFT en los algoritmos cortos de DFT de Winograd muestra que
\[ C(k) = X(W_N^k)=X\left(e^{-j\dfrac{2\pi k}{N}}\right),\; 0\le k \lt N \nonumber \]
es decir, la DFT calcula las evaluaciones del polinomio\(X(s)\) en las\(n\) raíces de la unidad.
El problema surge con el equivalente de Ecuación, ya que la multiplicación\(H(s)X(s)\) de dos polinomios de grado\(N-1\) produce uno de grado\(2N-2\). Además, no coincide con la convolución circular conocida por estar asociada con la DFT. La solución a ambos problemas es reducir el módulo del producto\(s^n-1\):
\[H*_{\text{circ}}X \leftrightarrow H(s)X(s)\,\text{mod}\,(s^n-1) \nonumber \]
| Concepto | Tiempo Infinito | Tiempo finito |
| Señal | \(X(s)=\sum_{n\in\mathbb{z}}x(n)s^n\) | \(\sum_{n=0}^{N-1}x(n)s^n\) |
| Filtrar | \(H(s)=\sum_{n\in\mathbb{z}}h(n)s^n\) | \(\sum_{n=0}^{N-1}h(n)s^n\) |
| Convolución | \(H(s)X(s)\) | \(H(s)X(s)\text{mod}(s^n-1)\) |
| Transformada de Fourier | \(\text{DTFT:} X(e^{-j\omega}), -\pi\lt\omega\le\pi\) | \(\text{DFT:} X\left(e^{-j\dfrac{2\pi k}{n}}\right), 0\le k\lt n\) |
Procesamiento de señal de tiempo discreto infinito y finito
El polinomio resultante vuelve a tener grado\(N−1\) y esta forma de convolución se vuelve equivalente a la convolución circular de los coeficientes polinomiales. También observamos que los puntos de evaluación en Ecuación son precisamente las raíces de\(s^n-1\). Esta conexión quedará clara en este capítulo.
La discusión se resume en la Tabla.
El marco adecuado para describir la multiplicación de polinomios módulo a polinomio fijo son álgebras polinómicas. Junto con el teorema del resto chino, proporcionan el apuntalamiento teórico para el DFT y el FFT Cooley-Tukey.
En este capítulo, la DFT surgirá naturalmente como un mapeo lineal con respecto a las bases elegidas, es decir, como una matriz. De hecho, la definición muestra que si todas las entradas y salidas se recogen en vectores\(X=(X(0),\ldots,X(N−1))\) y\(C=(C(0),\ldots C(N−1))\), entonces los Algoritmos DFT cortos de Winograd son equivalentes a
\[C=DFT_N\,X, \nonumber \]
donde
\[DFT_N=\left[W_N^{kn}\right]_{0\le k,n \lt N^.} \nonumber \]
El punto de vista matricial se adopta en los libros FFT.
Colaborador
- ContribeeBurrus