Este capítulo sólo rasca la superficie de la conexión entre álgebra y el DFT o procesamiento de señales en general. Proporcionamos algunas referencias para su posterior lectura.
Derivación algebraica de algoritmos de transformación
Como se mencionó anteriormente, el uso de álgebras polinomiales y el CRT subyace en gran parte del trabajo inicial sobre FFT y algoritmos de convolución. Por ejemplo, el trabajo de Winograd sobre FFT minimiza el número de multiplicaciones no racionales. Esto y su trabajo sobre la teoría de la complejidad en general hace un uso intensivo de álgebras polinomiales (ver Capítulo Winograd's Short DFT Algorithms para más información y referencias).
Dado que se\(\mathbb{C}[x]/(s^N-1)=\mathbb{C}[C_N]\) puede ver un álgebra de grupo para el grupo cíclico, los métodos mostrados en este capítulo pueden traducirse al contexto de la teoría de la representación grupal. Sin embargo, las transformadas de Fourier para grupos solo han encontrado aplicaciones esporádicas. A lo largo de una línea de trabajo relacionada, utilizando la teoría de grupos es posible que para descubrir y generar ciertos algoritmos para transformaciones trigonométricas, como las transformadas discretas de coseno (DCT), automáticamente usando un programa de computadora.
Más recientemente, el marco de álgebra polinomial se extendió para incluir la mayoría de las transformaciones trigonométricas utilizadas en el procesamiento de señales, además de la DFT, las transformadas discretas de coseno y seno y varias DFT reales, incluida la transformada discreta de Hartley. Resulta que las mismas técnicas que se muestran en este capítulo se pueden aplicar para derivar, explicar y clasificar la mayoría de los algoritmos conocidos para estas transformaciones e incluso obtener una gran clase de nuevos algoritmos que incluyen algoritmos general-radix para las transformaciones discretas de coseno y seno (DCTS/DSTs).
Esta última línea de trabajo es parte de la teoría algebraica del procesamiento de señales brevemente discutida a continuación.
Teoría del procesamiento de señales algebraicas
Las propiedades algebraicas de las transformaciones utilizadas en el trabajo anterior sobre la derivación de algoritmos indican una conexión entre el álgebra y el procesamiento de señal (lineal) en sí mismo. Este es de hecho el caso y fue completamente desarrollado en un reciente cuerpo de trabajo llamado teoría algebraica de procesamiento de señales (ASP).
ASP identifica primero la estructura algebraica del procesamiento de señales (lineal): los supuestos comunes sobre las operaciones disponibles para filtros y señales hacen del conjunto de filtros un álgebraAA“role="presentation” style="position:relative;” tabindex="0"> \(\mathfrak{A}\)y el conjunto de señales asociadasAA“role="presentación” style="position:relative;” tabindex="0">\(\mathfrak{A}\) -moduleAA“role="presentación” style="position:relative;” tabindex="0">\(\mathfrak{M}\). ASP luego construye una teoría de procesamiento de señales formalmente a partir de la definición axiomática de un modelo de señal: un triple(A,M,Φ)(A,M,Φ)“role="presentation” style="position:relative;” tabindex="0">\(\mathfrak{A,M,\Phi }\) donde\(\mathfrak{\Phi }\) generaliza la idea delzz“role="presentation” style="position:relative;” tabindex="0">\(z\) -transformar a asignaciones de espacios vectoriales de valores de señal aAA“role="presentación” style="position:relative;” tabindex="0">\(\mathfrak{M}\). Si se da un modelo de señal, otros conceptos, como espectro, transformada de Fourier, respuesta de frecuencia se definen automáticamente pero toman diferentes formas para diferentes modelos. Por ejemplo, el tiempo infinito y finito como se discute en la Tabla 7.4.1 a continuación, son dos ejemplos de modelos de señal. Su definición completa se proporciona en la Tabla 7.4.1 e identifica la noción propiamente dicha de unzz“role="presentación” style="position:relative;” tabindex="0">MM“role="presentación” style="position:relative;” tabindex="0"> \(\mathbb{C}^n\rightarrow \mathbb{C}[s]/(s^n-1)\)
Modelo de señal |
Tiempo infinito |
Tiempo finito |
AA“role="presentación” style="position:relative;” tabindex="0"> \[\mathfrak{A} \nonumber \] |
\[\left \{ \sum_{n\in \mathbb{Z}}H(n)s^n\mid (...,H(-1),H(0),H(1),...)\in l^1(\mathbb{Z}) \right \} \nonumber \] |
\[\mathbb{C}[x]/(s^n-1) \nonumber \] |
\[\mathfrak{M} \nonumber \] |
\[\left \{ \sum_{n\in \mathbb{Z}}X(n)s^n\mid (...,X(-1),X(0),X(1),...)\in l^2(\mathbb{Z}) \right \} \nonumber \] |
\[\mathbb{C}[s]/(s^n-1) \nonumber \] |
\[\mathfrak{\Phi} \nonumber \] |
\[\Phi :l^2(\mathbb{Z})\rightarrow \mathfrak{M} \nonumber \] |
\[\Phi :\mathbb{C}^n\rightarrow \mathfrak{M} \nonumber \] |
Tabla 7.4.1 Modelos de tiempo infinito y finito definidos en ASP
ASP muestra que muchos modelos de señal son en principio posibles, cada uno con su propia noción de filtrado y transformada de Fourier. Los que apoyan la invarianza por desplazamiento tienen álgebras conmutativas. Dado que los álgebras conmutativas finito-dimensionales son precisamente álgebras polinomiales, se explica su aparición en el procesamiento de señales. Por ejemplo, ASP identifica los álgebras polinomiales subyacentes a los DCT y DSTs, que de ahí se convierten en transformadas de Fourier en el sentido ASP. Los modelos de señal se denominan modelos de espacio finito ya que admiten el procesamiento de señal basado en un operador de desplazamiento no dirigido, diferente del desplazamiento de tiempo dirigido. ASP proporciona muchos más conocimientos, incluyendo la necesidad y opciones para elegir las condiciones de límite, las propiedades de las transformaciones, las técnicas para derivar nuevos modelos de señal y la obtención concisa de los algoritmos mencionados anteriormente.