Transformada discreta de Fourier sobre un 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 suelen ser números complejos , sobre un anillo arbitrario .

Sea R un anillo cualquiera , sea un 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 según 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 denomina 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 de integridad (que incluye campos ), es suficiente elegir como raíz n- ésima primitiva de la unidad , lo que reemplaza la condición ( 1 ) por: ^{[ 1 ]}${\displaystyle \alpha }$

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

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

La inversa de la transformada discreta de Fourier se expresa como:

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

Dado que la transformada discreta de Fourier es un operador lineal , puede describirse mediante la 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}}.}$

A veces resulta 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}.\,}$

Al escribir 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 simplemente 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 precisamente 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}).}$

Podemos resumirlo de la siguiente manera: si los valores de son los coeficientes de , entonces los valores de son los coeficientes de , salvo un factor escalar y un reordenamiento. ^{[ 2 ]}${\displaystyle p_{v}(x)}$${\displaystyle p_{f}(x)}$${\displaystyle p_{f}(x)}$${\displaystyle p_{v}(x)}$

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

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

lo que da como resultado la fórmula habitual para la transformada discreta de Fourier compleja :

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

En el caso de los números complejos, suele ser habitual normalizar las fórmulas de la DFT y la DFT inversa utilizando el factor escalar en ambas, en lugar de en la fórmula de la DFT y en la de la DFT inversa. Con esta normalización, la matriz de la DFT resulta unitaria. Cabe destacar que esto no tiene sentido en un campo arbitrario. ${\displaystyle {\frac {1}{\sqrt {n}}}}$${\displaystyle 1}$${\displaystyle {\frac {1}{n}}}$${\displaystyle {\sqrt {n}}}$

Si es un cuerpo finito , donde q es una potencia prima , entonces la existencia de una raíz n- ésima primitiva implica automáticamente que n divide a , porque el orden multiplicativo de cada elemento debe dividir el tamaño del grupo multiplicativo de F , que es . Esto, en particular, asegura que es invertible, de modo que la notación en ( 3 ) tiene 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 realizar de manera eficiente con algoritmos rápidos adecuados, por ejemplo, la transformada rápida de Fourier ciclotómica . ${\displaystyle \mathrm {GF} (q)}$

Supongamos que . Si , puede darse el caso de que . Esto significa que no podemos encontrar una raíz de la unidad en . Podemos considerar la transformada de Fourier como un isomorfismo para algunos polinomios , de acuerdo con el teorema de Maschke . La aplicación viene dada 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\nmid p-1}$${\displaystyle n^{th}}$${\displaystyle F}$${\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 en es equivalente a factorizar el ideal primo en . Obtenemos polinomios de grado donde y es el 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 se indicó anteriormente, podemos extender el campo base para encontrar una raíz primitiva, es decir, un campo de división para . Ahora , por lo que un elemento se asigna a para cada . ${\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}}$${\displaystyle k}$

Cuando , aún podemos definir un isomorfismo -lineal como se indicó anteriormente. Nótese que donde y . Aplicamos la factorización anterior a , y ahora obtenemos la descomposición . Los módulos que aparecen ahora son 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}})}$

Supongamos que tenemos una raíz de la unidad . Sea la matriz DFT anterior, una matriz de Vandermonde con entradas para . Recordemos que, dado que si , entonces cada entrada es 1. Si , entonces tenemos una serie geométrica con razón común , por lo que obtenemos . Dado que el numerador es cero, pero , entonces el denominador es distinto de cero. ${\displaystyle p\nmid n}$${\displaystyle n^{th}}$${\displaystyle \alpha }$${\displaystyle A}$${\displaystyle A_{ij}=\alpha ^{ij}}$${\displaystyle 0\leq i,j<n}$${\displaystyle \sum _{j=0}^{n-1}\alpha ^{(k-l)j}=n\delta _{k,l}}$${\displaystyle k=l}$${\displaystyle k\neq l}$${\displaystyle \alpha ^{k-l}}$${\displaystyle {\frac {1-\alpha ^{n(k-l)}}{1-\alpha ^{k-l}}}}$${\displaystyle \alpha ^{n}=1}$${\displaystyle k-l\neq 0}$

Primero calculamos el cuadrado, . Calculando de forma similar y simplificando los deltas, obtenemos . Por lo tanto, y el orden es . ${\displaystyle (A^{2})_{ik}=\sum _{j=0}^{n-1}\alpha ^{j(i+k)}=n\delta _{i,-k}}$${\displaystyle A^{4}=(A^{2})^{2}}$${\displaystyle (A^{4})_{ik}=n^{2}\delta _{i,k}}$${\displaystyle A^{4}=n^{2}I_{n}}$${\displaystyle 4\cdot {\text{ord}}(n^{2})}$

Para alinearnos con el caso complejo y asegurar que la matriz sea exactamente de orden 4, podemos normalizar la matriz DFT anterior con . Nótese que, aunque puede que no exista en el campo de división de , podemos formar una extensión cuadrática en la que exista la raíz cuadrada. Entonces podemos establecer , y . ${\displaystyle A}$${\displaystyle {\frac {1}{\sqrt {n}}}}$${\displaystyle {\sqrt {n}}}$${\displaystyle F_{q}}$${\displaystyle x^{n}-1}$${\displaystyle F_{q^{2}}\cong F_{q}[x]/(x^{2}-n)}$${\displaystyle U={\frac {1}{\sqrt {n}}}A}$${\displaystyle U^{4}=I_{n}}$

Supongamos que . Se puede preguntar si la matriz DFT es unitaria sobre un cuerpo finito . Si las entradas de la matriz están sobre , entonces hay que asegurar que sea un cuadrado perfecto o extender a para definir el automorfismo de orden dos . Consideremos la matriz DFT anterior . Nótese que es simétrica. Conjugando y transponiendo, obtenemos . ${\displaystyle p\nmid n}$${\displaystyle F_{q}}$${\displaystyle q}$${\displaystyle F_{q^{2}}}$${\displaystyle x\mapsto x^{q}}$${\displaystyle A_{ij}=\alpha ^{ij}}$${\displaystyle A}$${\displaystyle A_{ij}^{*}=\alpha ^{qji}}$

${\displaystyle (AA^{*})_{ik}=\sum _{j=0}^{n-1}\alpha ^{j(i+qk)}=n\delta _{i,-qk}}$

mediante un argumento de serie geométrica similar al anterior. Podemos eliminar la normalizando de modo que y . Por lo tanto, es unitaria si y solo si . Recordemos que, dado que tenemos una raíz de la unidad, . Esto significa que . Nótese que si no era un cuadrado perfecto para empezar, entonces y por lo tanto . ${\displaystyle n}$${\displaystyle U={\frac {1}{\sqrt {n}}}A}$${\displaystyle (UU^{*})_{ik}=\delta _{i,-qk}}$${\displaystyle U}$${\displaystyle q\equiv -1\,({\text{mod}}\,n)}$${\displaystyle n^{th}}$${\displaystyle n|q^{2}-1}$${\displaystyle q^{2}-1\equiv (q+1)(q-1)\equiv 0\,({\text{mod}}\,n)}$${\displaystyle q}$${\displaystyle n|q-1}$${\displaystyle q\equiv 1\,({\text{mod}}\,n)}$

Por ejemplo, cuando necesitamos extender para obtener una raíz quinta de la unidad . ${\displaystyle p=3,n=5}$${\displaystyle q^{2}=3^{4}}$${\displaystyle q=9\equiv -1\,({\text{mod}}\,5)}$

Por ejemplo, cuando extendemos para obtener una raíz octava de la unidad, , entonces , y en este caso y . es una raíz cuadrada de la identidad, por lo que no es unitaria. ${\displaystyle p=3,n=8}$${\displaystyle F_{3^{2}}}$${\displaystyle q^{2}=9}$${\displaystyle q\equiv 3\,({\text{mod}}\,8)}$${\displaystyle q+1\not \equiv 0}$${\displaystyle q-1\not \equiv 0}$${\displaystyle UU^{*}}$${\displaystyle U}$

Cuando , tenemos una raíz de la unidad en el campo de descomposición . Nótese que el polinomio característico de la matriz DFT anterior puede no descomponerse sobre . La matriz DFT es de orden 4. Puede que necesitemos ir a una extensión más allá , la extensión de descomposición del polinomio característico de la matriz DFT, que al menos contiene raíces cuartas de la unidad. Si es un generador del grupo multiplicativo de , entonces los autovalores son , en analogía exacta con el caso complejo. Aparecen con alguna multiplicidad no negativa. ${\displaystyle p\nmid n}$${\displaystyle n^{th}}$${\displaystyle \alpha }$${\displaystyle F_{q}\cong F_{p}[x]/(x^{n}-1)}$${\displaystyle F_{q}}$${\displaystyle F_{q'}}$${\displaystyle a}$${\displaystyle F_{q'}}$${\displaystyle \{\pm 1,\pm a^{(q'-1)/4}\}}$

La transformada teórica de números (NTT) ^{[ 4 ]} se obtiene especializando la transformada discreta de Fourier a , los enteros módulo un primo p . Este es un campo finito , y existen raíces n -ésimas primitivas de la unidad siempre que n divide a , por lo que tenemos para un entero positivo ξ . Específicamente, sea una raíz n-ésima primitiva de la unidad, entonces se puede encontrar una raíz n- ésima de la unidad haciendo . ${\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 transformación 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 transformación teórica de números, como la Transformación de Números de Fermat ( m = ^2k + 1 ), utilizada por el algoritmo de Schönhage-Strassen , o la Transformación de Números de Mersenne ^{[ 5 ]} ( m = ^2k  − 1 ), utilizan un módulo compuesto. ${\displaystyle \mathbb {Z} /m}$

En general, si , entonces se puede encontrar una raíz de la unidad módulo m al encontrar raíces primitivas de la unidad módulo , lo que produce una tupla . La preimagen de bajo el isomorfismo del teorema chino del resto es una raíz de la unidad tal que . Esto asegura que se satisfacen las condiciones de suma anteriores. Debemos tener que para cada , donde es la función totiente de Euler . ^{[ 6 ]}${\textstyle m=\prod _{i}p_{i}^{e_{i}}}$${\textstyle n^{th}}$${\textstyle n^{th}}$${\displaystyle g_{i}}$${\textstyle p_{i}^{e_{i}}}$${\textstyle g=\left(g_{i}\right)_{i}\in \prod _{i}\left(\mathbb {Z} /p_{i}^{e_{i}}\mathbb {Z} \right)^{\ast }}$${\displaystyle g}$${\textstyle n^{th}}$${\textstyle \alpha }$${\textstyle \alpha ^{n/2}=-1\mod m}$${\textstyle n|\varphi (p_{i}^{e_{i}})}$${\displaystyle i}$${\displaystyle \varphi }$

La transformada rápida de Fourier se puede adaptar a NTT e implementar con solo operaciones enteras. ^{[ 7 ]} Algunas elecciones de m, como el primo de Solinas, son incluso más fáciles de calcular en computadoras, ya que no requieren ninguna operación de división para la reducción. ^{[ 8 ]}${\displaystyle 2^{64}-2^{32}+1}$

La transformada discreta ponderada (DWT) es una variación de la transformada discreta de Fourier sobre anillos arbitrarios que implica ponderar la entrada antes de transformarla multiplicándola elemento a elemento por un vector de ponderación, y luego ponderar el resultado por otro vector. ^{[ 9 ]} La transformada discreta ponderada de base irracional es un caso especial de esta.

La mayoría de los atributos importantes de la DFT compleja , incluyendo la transformada inversa, el teorema de convolución y la mayoría de los algoritmos de la transformada rápida de Fourier (FFT), dependen únicamente de la propiedad de que el núcleo de la transformada sea una raíz principal de la unidad. Estas propiedades también se cumplen, con demostraciones idénticas, sobre anillos arbitrarios. En el caso de los cuerpos, esta analogía puede formalizarse mediante el cuerpo con un elemento , considerando cualquier cuerpo con una raíz primitiva n -ésima de la unidad como un álgebra sobre el cuerpo de extensión.${\displaystyle \mathbf {F} _{1^{n}}.}$

En particular, la aplicabilidad de los algoritmos de transformada rápida de Fourier para calcular la transformada de Fourier no lineal (NTT), junto con el teorema de convolución, implica que la transformada basada en la teoría de números proporciona una forma eficiente de calcular convoluciones exactas de secuencias de enteros. Si bien la transformada discreta de Fourier (DFT) compleja puede realizar la misma tarea, es susceptible a errores de redondeo en la aritmética de punto flotante de precisión finita ; la NTT no presenta errores de redondeo porque trabaja exclusivamente con enteros de tamaño fijo que pueden representarse con exactitud. ${\displaystyle O(n\log n)}$

Para la implementación de un algoritmo "rápido" (similar a cómo la FFT calcula la DFT ), suele ser deseable que la longitud de la transformada sea también altamente 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, ^{[ 10 ]} que son eficientes independientemente de los factores de longitud de la transformada.

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

• https://www.apfloat.org/ntt.html