Transformada discreta de Fourier sobre un anillo

Generalización de la transformada de Fourier a cualquier anillo.

En matemáticas , la transformada discreta de Fourier sobre un anillo generaliza la transformada discreta de Fourier (DFT), de una función cuyos valores son comúnmente números complejos , sobre un anillo arbitrario .

Definición

Sea R cualquier anillo , sea un número entero y sea una raíz n- ésima principal de la unidad, definida por: ^[1] ${\displaystyle n\geq 1}$ ${\displaystyle \alpha \in R}$

La transformada discreta de Fourier asigna una n -tupla de elementos de R a otra n -tupla de elementos de R de acuerdo con la siguiente fórmula: ${\displaystyle (v_{0},\ldots ,v_{n-1})}$ ${\displaystyle (f_{0},\ldots ,f_{n-1})}$

Por convención, se dice que la tupla está en el dominio del tiempo y el índice j se llama tiempo . Se dice que la tupla está en el dominio de la frecuencia y el índice k se llama frecuencia . La tupla también se llama espectro de . Esta terminología deriva de las aplicaciones de las transformadas de Fourier en el procesamiento de señales . ${\displaystyle (v_{0},\ldots ,v_{n-1})}$ ${\displaystyle (f_{0},\ldots ,f_{n-1})}$ ${\displaystyle (f_{0},\ldots ,f_{n-1})}$ ${\displaystyle (v_{0},\ldots ,v_{n-1})}$

Si R es un dominio integral (que incluye campos ), basta con elegir como primitiva n -ésima raíz de la unidad , que reemplaza la condición ( 1 ) por: ^[1] ${\displaystyle \alpha }$

${\displaystyle \alpha ^{k}\neq 1}$para ${\displaystyle 1\leq k<n}$

Prueba

Toma con . Desde , , dando: ${\displaystyle \beta =\alpha ^{k}}$ ${\displaystyle 1\leq k<n}$ ${\displaystyle \alpha ^{n}=1}$ ${\displaystyle \beta ^{n}=(\alpha ^{n})^{k}=1}$

${\displaystyle \beta ^{n}-1=(\beta -1)\left(\sum _{j=0}^{n-1}\beta ^{j}\right)=0}$

donde la suma coincide con ( 1 ). Puesto que es una raíz primitiva de unidad, . Como R es un dominio integral, la suma debe ser cero. ∎ ${\displaystyle \alpha }$ ${\displaystyle \beta -1\neq 0}$

Otra condición simple se aplica en el caso en que n sea una potencia de dos: ( 1 ) puede reemplazarse por . ^[1] ${\displaystyle \alpha ^{n/2}=-1}$

Inverso

La inversa de la transformada discreta de Fourier viene dada por:

donde está el inverso multiplicativo de n en R (si este inverso no existe, la DFT no se puede invertir). ${\displaystyle 1/n}$

Prueba

Sustituyendo ( 2 ) en el lado derecho de ( 3 ), obtenemos

${\displaystyle {\begin{aligned}&{\frac {1}{n}}\sum _{k=0}^{n-1}f_{k}\alpha ^{-jk}\\={}&{\frac {1}{n}}\sum _{k=0}^{n-1}\sum _{j'=0}^{n-1}v_{j'}\alpha ^{j'k}\alpha ^{-jk}\\={}&{\frac {1}{n}}\sum _{j'=0}^{n-1}v_{j'}\sum _{k=0}^{n-1}\alpha ^{(j'-j)k}.\end{aligned}}}$

Esto es exactamente igual a , porque cuando (por ( 1 ) con ) y cuando . ∎ ${\displaystyle v_{j}}$ ${\displaystyle \sum _{k=0}^{n-1}\alpha ^{(j'-j)k}=0}$ ${\displaystyle j'\neq j}$ ${\displaystyle k=j'-j}$ ${\displaystyle \sum _{k=0}^{n-1}\alpha ^{(j'-j)k}=n}$ ${\displaystyle j'=j}$

Formulación matricial

Dado que la transformada discreta de Fourier es un operador lineal , puede describirse mediante multiplicación de matrices . En notación matricial, la transformada discreta de Fourier se expresa de la siguiente manera:

${\displaystyle {\begin{bmatrix}f_{0}\\f_{1}\\\vdots \\f_{n-1}\end{bmatrix}}={\begin{bmatrix}1&1&1&\cdots &1\\1&\alpha &\alpha ^{2}&\cdots &\alpha ^{n-1}\\1&\alpha ^{2}&\alpha ^{4}&\cdots &\alpha ^{2(n-1)}\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&\alpha ^{n-1}&\alpha ^{2(n-1)}&\cdots &\alpha ^{(n-1)(n-1)}\\\end{bmatrix}}{\begin{bmatrix}v_{0}\\v_{1}\\\vdots \\v_{n-1}\end{bmatrix}}.}$

La matriz para esta transformación se llama matriz DFT .

De manera similar, la notación matricial para la transformada inversa de Fourier es

${\displaystyle {\begin{bmatrix}v_{0}\\v_{1}\\\vdots \\v_{n-1}\end{bmatrix}}={\frac {1}{n}}{\begin{bmatrix}1&1&1&\cdots &1\\1&\alpha ^{-1}&\alpha ^{-2}&\cdots &\alpha ^{-(n-1)}\\1&\alpha ^{-2}&\alpha ^{-4}&\cdots &\alpha ^{-2(n-1)}\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&\alpha ^{-(n-1)}&\alpha ^{-2(n-1)}&\cdots &\alpha ^{-(n-1)(n-1)}\end{bmatrix}}{\begin{bmatrix}f_{0}\\f_{1}\\\vdots \\f_{n-1}\end{bmatrix}}.}$

Formulación polinomial

A veces es conveniente identificar una n -tupla con un polinomio formal ${\displaystyle (v_{0},\ldots ,v_{n-1})}$

${\displaystyle p_{v}(x)=v_{0}+v_{1}x+v_{2}x^{2}+\cdots +v_{n-1}x^{n-1}.\,}$

Escribiendo la sumatoria en la definición de la transformada discreta de Fourier ( 2 ), obtenemos:

${\displaystyle f_{k}=v_{0}+v_{1}\alpha ^{k}+v_{2}\alpha ^{2k}+\cdots +v_{n-1}\alpha ^{(n-1)k}.\,}$

Esto significa que es solo el valor del polinomio para , es decir, ${\displaystyle f_{k}}$ ${\displaystyle p_{v}(x)}$ ${\displaystyle x=\alpha ^{k}}$

Por lo tanto, se puede ver 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 están en el dominio de la frecuencia. Aquí, por supuesto, es importante que el polinomio se evalúe en las raíces enésimas de la unidad, que son exactamente las potencias de . ${\displaystyle \alpha }$

De manera similar, la definición de la transformada inversa de Fourier ( 3 ) se puede escribir:

Con

${\displaystyle p_{f}(x)=f_{0}+f_{1}x+f_{2}x^{2}+\cdots +f_{n-1}x^{n-1},}$

esto significa que

${\displaystyle v_{j}={\frac {1}{n}}p_{f}(\alpha ^{-j}).}$

Esto lo podemos resumir de la siguiente manera: si los valores de son los coeficientes de , entonces los valores de son los coeficientes de , hasta un factor escalar y reordenando. ^[2] ${\displaystyle p_{v}(x)}$ ${\displaystyle p_{f}(x)}$ ${\displaystyle p_{f}(x)}$ ${\displaystyle p_{v}(x)}$

Casos especiales

Números complejos

Si es el cuerpo de números complejos, entonces las raíces enésimas de la unidad se pueden visualizar como puntos en el círculo unitario del plano complejo . En este caso se suele tomar ${\displaystyle F={\mathbb {C} }}$ ${\displaystyle n}$

${\displaystyle \alpha =e^{\frac {-2\pi i}{n}},}$

que produce la fórmula habitual para la transformada de Fourier discreta compleja :

${\displaystyle f_{k}=\sum _{j=0}^{n-1}v_{j}e^{{\frac {-2\pi i}{n}}jk}.}$

En 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 para la DFT y en la fórmula para la DFT inversa. Con esta normalización, la matriz DFT es entonces unitaria. Tenga en cuenta que eso no tiene sentido en un campo arbitrario. ${\displaystyle {\frac {1}{\sqrt {n}}}}$ ${\displaystyle 1}$ ${\displaystyle {\frac {1}{n}}}$ ${\displaystyle {\sqrt {n}}}$

campos finitos

Si es un campo finito , donde q es una potencia prima , entonces la existencia de una raíz nésima primitiva implica automáticamente que n divide , porque el orden multiplicativo de cada elemento debe dividir el tamaño del grupo multiplicativo de F , que es . Esto en particular garantiza que sea invertible, de modo que la notación en ( 3 ) tenga sentido. ${\displaystyle F=\mathrm {GF} (q)}$ ${\displaystyle q-1}$ ${\displaystyle q-1}$ ${\displaystyle n=\underbrace {1+1+\cdots +1} _{n\ {\rm {times}}}}$ ${\displaystyle {\frac {1}{n}}}$

Una aplicación de la transformada discreta de Fourier es la reducción de códigos Reed-Solomon a códigos BCH en la teoría de la codificación . Dicha transformada se puede llevar a cabo de manera eficiente con algoritmos rápidos adecuados, por ejemplo, la transformada rápida ciclotómica de Fourier . ${\displaystyle \mathrm {GF} (q)}$

Suponer . Si , puede que no sea el caso . Podemos ver la transformada de Fourier como un isomorfismo para algunos polinomios , de acuerdo con el teorema de Maschke . El mapa viene dado por el teorema chino del resto , y la inversa viene dada aplicando la identidad de Bézout para polinomios. ^[3] ${\displaystyle F=\mathrm {GF} (p)}$ ${\displaystyle p\nmid n}$ ${\displaystyle n|p-1}$ ${\displaystyle \mathrm {F} [C_{n}]=\mathrm {F} [x]/(x^{n}-1)\cong \bigoplus _{i}\mathrm {F} [x]/(P_{i}(x))}$ ${\displaystyle P_{i}(x)}$

${\displaystyle x^{n}-1=\prod _{d|n}\Phi _{d}(x)}$, un producto de polinomios ciclotómicos. Factorizar es equivalente a factorizar el ideal primo . Obtenemos polinomios de grado donde y es del orden de . ${\displaystyle \Phi _{d}(x)}$ ${\displaystyle F[x]}$ ${\displaystyle (p)}$ ${\displaystyle \mathrm {Z} [\zeta ]=\mathrm {Z} [x]/(\Phi _{d}(x))}$ ${\displaystyle g}$ ${\displaystyle P_{1}\ldots P_{g}}$ ${\displaystyle f}$ ${\displaystyle fg=\varphi (d)}$ ${\displaystyle f}$ ${\displaystyle p{\text{ mod }}d}$

Como arriba, podemos extender el campo base para encontrar una raíz primitiva, es decir, un campo de división para . Ahora , un elemento se asigna a . ${\displaystyle \mathrm {GF} (q)}$ ${\displaystyle x^{n}-1}$ ${\displaystyle x^{n}-1=\prod _{k}(x-\alpha ^{k})}$ ${\displaystyle \sum _{j=0}^{n-1}v_{j}x^{j}\in F[x]/(x^{n}-1)}$ ${\displaystyle \sum _{j=0}^{n-1}v_{j}x^{j}\mod (x-\alpha ^{k})\equiv \sum _{j=0}^{n-1}v_{j}(\alpha ^{k})^{j}}$

Cuando , aún podemos definir un isomorfismo lineal como se indicó anteriormente. Tenga en cuenta que dónde y . Aplicamos la factorización anterior y ahora obtenemos la descomposición . Los módulos que se producen son ahora indescomponibles en lugar de irreducibles. ${\displaystyle p|n}$ ${\displaystyle F_{p}}$ ${\displaystyle (x^{n}-1)=(x^{m}-1)^{p^{s}}}$ ${\displaystyle n=mp^{s}}$ ${\displaystyle p\nmid m}$ ${\displaystyle x^{m}-1}$ ${\displaystyle F[x]/(x^{n}-1)\cong \bigoplus _{i}F[x]/(P_{i}(x)^{p^{s}})}$

Transformada de teoría de números

La transformada de teoría de números (NTT) ^[4] se obtiene especializando la transformada discreta de Fourier en los números enteros módulo a primo p . Este es un campo finito , y las raíces primitivas n- ésimas de la unidad existen siempre que n se divide , por lo que tenemos un entero positivo ξ . Específicamente, sea una raíz primitiva de la unidad, entonces se puede encontrar una raíz n de la unidad dejando . ${\displaystyle F={\mathbb {Z} }/p}$ ${\displaystyle p-1}$ ${\displaystyle p=\xi n+1}$ ${\displaystyle \omega }$ ${\displaystyle (p-1)}$ ${\displaystyle \alpha }$ ${\displaystyle \alpha =\omega ^{\xi }}$

por ejemplo, para , ${\displaystyle p=5}$ ${\displaystyle \alpha =2}$

${\displaystyle {\begin{aligned}2^{1}&=2{\pmod {5}}\\2^{2}&=4{\pmod {5}}\\2^{3}&=3{\pmod {5}}\\2^{4}&=1{\pmod {5}}\end{aligned}}}$

cuando ${\displaystyle N=4}$

${\displaystyle {\begin{bmatrix}F(0)\\F(1)\\F(2)\\F(3)\end{bmatrix}}={\begin{bmatrix}1&1&1&1\\1&2&4&3\\1&4&1&4\\1&3&4&2\end{bmatrix}}{\begin{bmatrix}f(0)\\f(1)\\f(2)\\f(3)\end{bmatrix}}}$

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 . Casos especiales de la transformada teórica de números, como la transformada numérica de Fermat ( m = 2 ^k +1 ), utilizada por el algoritmo de Schönhage-Strassen , o la transformada numérica de Mersenne ^[5] ( m = 2 ^k  − 1 ), utilizan un módulo compuesto. ${\displaystyle \mathbb {Z} /m}$

Transformada ponderada discreta

La transformada ponderada discreta (DWT) es una variación de la transformada discreta de Fourier sobre anillos arbitrarios que implica ponderar la entrada antes de transformarla multiplicando elementos por un vector de peso y luego ponderar el resultado por otro vector. ^[6] 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 rápidos de transformada de Fourier (FFT), dependen únicamente de la propiedad de que el núcleo de la transformada es una raíz principal de la unidad. Estas propiedades se mantienen también, con idénticas pruebas, en anillos arbitrarios. En el caso de los campos, esta analogía se puede formalizar mediante el campo con un elemento , considerando cualquier campo con una primitiva n- ésima raíz unitaria como un álgebra sobre el campo de extensión ^{[ aclaración necesaria ]} ${\displaystyle \mathbf {F} _{1^{n}}.}$

En particular, la aplicabilidad de los algoritmos de transformada rápida de Fourier para calcular el NTT, combinada con el teorema de convolución, significa que la transformada de teoría 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 a errores de redondeo en la aritmética de coma flotante de precisión finita ; el NTT no tiene redondeo porque trata exclusivamente con números enteros de tamaño fijo que pueden representarse exactamente. ${\displaystyle O(n\log n)}$

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 la transformación también sea altamente compuesta, por ejemplo, una potencia de dos . Sin embargo, existen algoritmos de transformada rápida de Fourier especializados para campos finitos, como el algoritmo de Wang y Zhu, ^[7] que son eficientes independientemente de si la transformación factoriza o no.

Ver también

• Transformada discreta de Fourier (compleja)
• Transformada de Fourier en grupos finitos
• Suma de Gauss
• Circunvolución
• Análisis espectral de mínimos cuadrados
• Algoritmo de multiplicación

Referencias

1. Martin Fürer, "Multiplicación de enteros más rápida", Actas STOC 2007, págs. Sección 2: La transformada discreta de Fourier.
2. R. Lidl y G. Pilz. Álgebra abstracta aplicada, 2ª edición. Wiley, 1999, págs. 217–219.
3. https://github.com/jacksonwalters/dft-finite-field
4. Agarwal, R.; Burrus, C. (abril de 1974). "Convolución rápida utilizando transformaciones de números de Fermat con aplicaciones de filtrado digital". Transacciones IEEE sobre acústica, voz y procesamiento de señales . 22 (2): 87–97. doi :10.1109/TASSP.1974.1162555. ISSN  0096-3518.
5. Rader, CM (diciembre de 1972). "Convoluciones discretas mediante transformadas de Mersenne". Transacciones IEEE en computadoras . C-21 (12): 1269–1273. doi :10.1109/TC.1972.223497. ISSN  0018-9340. S2CID  1939809.
6. Crandall, Richard; Fagin, Barry (1994), "Transformaciones ponderadas discretas y aritmética de enteros grandes" (PDF) , Matemáticas de la Computación , 62 (205): 305–324, doi : 10.2307/2153411 , JSTOR  2153411
7. 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