En matemáticas, la transformada discreta de Fourier sobre un anillo arbitrario generaliza la transformada discreta de Fourier de una función cuyos valores son números complejos .
Definición
Dejar ser cualquier anillo , deja ser un entero y dejar ser una raíz n- ésima principal de la unidad, definida por: [1]
La transformada discreta de Fourier mapea una n- tupla de elementos de a otra n- tupla de elementos de según la siguiente fórmula:
Por convención, la tupla se dice que está en el dominio del tiempo y el índicese llama tiempo . La tuplase dice que está en el dominio de la frecuencia y el índicese llama frecuencia . La tuplatambién se llama el espectro de. Esta terminología se deriva de las aplicaciones de las transformadas de Fourier en el procesamiento de señales .
Si es un dominio integral (que incluye campos ), es suficiente elegircomo una raíz n- ésima primitiva de la unidad , que reemplaza la condición (1) por: [1]
- por
Prueba: tomar con . Desde, , donación:
donde la suma coincide (1). Desde es una raíz primitiva de unidad, . Desdees un dominio integral, la suma debe ser cero. ∎
Otra condición simple se aplica en el caso donde n es una potencia de dos: (1) puede ser reemplazado por. [1]
Inverso
La inversa de la transformada discreta de Fourier se da como:
dónde es el inverso multiplicativo de en (si esta inversa no existe, la DFT no se puede invertir).
Prueba: Sustituyendo (2) en el lado derecho de (3), obtenemos
Esto es exactamente igual a , porque Cuándo (por (1) con ), y Cuándo . ∎
Formulación de matriz
Dado que la transformada discreta de Fourier es un operador lineal , se puede describir mediante la multiplicación de matrices . En notación matricial, la transformada discreta de Fourier se expresa de la siguiente manera:
La matriz para esta transformación se llama matriz DFT .
De manera similar, la notación matricial para la transformada de Fourier inversa es
Formulación polinomial [2]
A veces es conveniente identificar un -tupla con un polinomio formal
Al escribir la suma en la definición de la transformada discreta de Fourier (2), obtenemos:
Esto significa que es solo el valor del polinomio por , es decir,
Por tanto, puede verse que la transformada de Fourier relaciona los coeficientes y los valores de un polinomio: los coeficientes están en el dominio del tiempo y los valores en el dominio de la frecuencia. Aquí, por supuesto, es importante que el polinomio se evalúe en ellas raíces de la unidad, que son exactamente los poderes de .
De manera similar, la definición de la transformada de Fourier inversa (3) se puede escribir:
Con
esto significa que
Podemos resumir esto de la siguiente manera: si los valores deson los coeficientes de, entonces los valores deson los coeficientes de, hasta un factor escalar y reordenamiento.
Casos especiales
Números complejos
Si es el campo de números complejos, entonces el Las raíces de la unidad se pueden visualizar como puntos en el círculo unitario del plano complejo . En este caso, uno suele tomar
que produce la fórmula habitual para la transformada de Fourier discreta compleja :
Sobre los números complejos, a menudo se acostumbra normalizar las fórmulas para la DFT y la DFT inversa utilizando el factor escalar en ambas fórmulas, en lugar de en la fórmula de la DFT y en la fórmula de la DFT inversa. Con esta normalización, la matriz DFT es entonces unitaria. Tenga en cuenta que no tiene sentido en un campo arbitrario.
Campos finitos
Si es un campo finito , dondees un poder primordial , entonces la existencia de un primitivoLa raíz implica automáticamente que divide , porque el orden multiplicativo de cada elemento debe dividir el tamaño del grupo multiplicativo de, cual es . Esto en particular asegura que es invertible, de modo que la notación en (3) tiene sentido.
Una aplicación de la transformada discreta de Fourier sobre es la reducción de los códigos Reed-Solomon de códigos BCH en la teoría de la codificación . Dicha transformación se puede llevar a cabo de manera eficiente con algoritmos rápidos adecuados, por ejemplo, transformada ciclotómica rápida de Fourier .
Transformada teórica de números
La transformada teórica de números (NTT) [3] se obtiene especializando la transformada discreta de Fourier en, los enteros módulo a primo p . Este es un campo finito , y las n- ésimas raíces de unidad primitivas existen siempre que n divide, entonces tenemos para un entero positivo ξ . Específicamente, deje ser un primitivo º raíz de la unidad, a continuación, un n º raíz de la unidad se puede encontrar dejando .
p. ej. para ,
Cuándo
La transformada teórica de números puede ser significativa en el anillo , incluso cuando el módulo m no es primo, siempre que exista una raíz principal de orden n . Los casos especiales de la transformada teórica de números, como la Transformada de números de Fermat ( m = 2 k +1 ), utilizada por el algoritmo de Schönhage-Strassen , o la Transformada de números de Mersenne [4] ( m = 2 k - 1 ) utilizan un módulo compuesto.
Transformada ponderada discreta
La transformada ponderada discreta (DWT) es una variación de la transformada de Fourier discreta sobre anillos arbitrarios que implican ponderar la entrada antes de transformarla multiplicando elemento por un vector de ponderación y luego ponderando el resultado por otro vector. [5] La transformada ponderada discreta de base irracional es un caso especial de esto.
Propiedades
La mayoría de los atributos importantes de la DFT compleja , incluida la transformada inversa, el teorema de convolución y la mayoría de los algoritmos de transformada de Fourier rápida (FFT), dependen únicamente de la propiedad de que el núcleo de la transformada es la raíz principal de la unidad. Estas propiedades también se mantienen, con pruebas idénticas, sobre anillos arbitrarios. En el caso de los campos, esta analogía puede ser formalizada por el campo con un elemento , considerando cualquier campo con una raíz primitiva n -ésima de la unidad como un álgebra sobre el campo de extensión.[ aclaración necesaria ]
En particular, la aplicabilidad de Los algoritmos rápidos de transformada de Fourier para calcular la NTT, combinados con el teorema de convolución, significan que la transformada teórica de números proporciona una forma eficiente de calcular convoluciones exactas de secuencias enteras. Si bien la DFT compleja puede realizar la misma tarea, es susceptible de error de redondeo en la aritmética de coma flotante de precisión finita ; el NTT no tiene redondeo porque trata puramente con números enteros de tamaño fijo que se pueden representar exactamente.
Algoritmos rápidos
Para la implementación de un algoritmo "rápido" (similar a cómo FFT calcula la DFT ), a menudo es deseable que la longitud de transformación también sea muy compuesta, por ejemplo, una potencia de dos . Sin embargo, existen algoritmos especializados de transformada rápida de Fourier para campos finitos, como el algoritmo de Wang y Zhu, [6] que son eficientes independientemente de si se transforman en factores de longitud.
Ver también
- Transformada discreta de Fourier (compleja)
- Suma de Gauss
- Circunvolución
- Algoritmo de multiplicación
Referencias
- ^ a b c Martin Fürer, " Multiplicación de enteros más rápida ", Actas de STOC 2007, págs. 57–66. Sección 2: La transformada discreta de Fourier.
- ^ R. Lidl y G. Pilz. Álgebra abstracta aplicada, 2ª edición. Wiley, 1999, págs. 217-219.
- ^ Agarwal, R .; Burrus, C. (abril de 1974). “Fast Convolution usando fermat number transforma con aplicaciones a filtrado digital” . Transacciones IEEE sobre acústica, habla y procesamiento de señales . 22 (2): 87–97. doi : 10.1109 / TASSP.1974.1162555 . ISSN 0096-3518 .
- ^ Rader, CM (diciembre de 1972). "Convoluciones discretas a través de Mersenne Transrorms" . Transacciones IEEE en computadoras . C-21 (12): 1269-1273. doi : 10.1109 / TC.1972.223497 . ISSN 0018-9340 .
- ^ Crandall, Richard; Fagin, Barry (1994), "Transformaciones ponderadas discretas y aritmética de números enteros grandes" (PDF) , Mathematics of Computation , 62 (205): 305–324, doi : 10.2307 / 2153411
- ^ Yao Wang y Xuelong Zhu, "Un algoritmo rápido para la transformada de Fourier sobre campos finitos y su implementación VLSI", IEEE Journal on Selected Areas in Communications 6 (3) 572-577, 1988
enlaces externos
- http://www.apfloat.org/ntt.html