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 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 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 cuerpo 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)}$

Formulación polinomial sin n^thraíz

Suponer . Si , puede darse el caso de que . Esto significa que no podemos encontrar una raíz de unidad en . Podemos ver la transformada de Fourier como un isomorfismo para algunos polinomios , de acuerdo con el teorema de Maschke . El mapa está dado por el teorema del resto chino , y la inversa está 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 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 for each . ${\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 p divide a n

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}})}$

Orden de la matriz DFT

Supongamos que tenemos una raíz de unidad . Sea la matriz DFT anterior, una matriz de Vandermonde con entradas para . Recuerde que como 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, 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 calculando el cuadrado, . Calculando de manera similar y simplificando los deltas, obtenemos . Por 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})}$

Normalizando la matriz DFT

Para alinearnos con el caso complejo y garantizar que la matriz sea exactamente de orden 4, podemos normalizar la matriz DFT anterior con . Tenga en cuenta que, aunque puede no existir en el campo de división de , podemos formar una extensión cuadrática en la que existe 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}}$

Unitaridad

Suponer . Uno puede preguntarse si la matriz DFT es unitaria en un campo finito . Si las entradas de la matriz terminaron , entonces uno debe asegurarse de que sea un cuadrado perfecto o extenderse para definir el automorfismo de orden dos . Considere la matriz DFT anterior . Tenga en cuenta que es simétrico. 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}}$

por un argumento de serie geométrica similar al anterior. Podemos eliminar normalizando para que y . Por tanto, es unitario si . Recordemos que dado que tenemos una raíz de unidad, . Esto significa que . Tenga en cuenta que, para empezar, no era un cuadrado perfecto, entonces y así . ${\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 hasta para obtener una quinta ^raíz de la unidad. . ${\displaystyle p=3,n=5}$ ${\displaystyle q^{2}=3^{4}}$ ${\displaystyle q=9\equiv -1\,({\text{mod}}\,5)}$

Para un no ejemplo, cuando extendemos hasta 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}$

Valores propios de la matriz DFT

Cuando tengamos una raíz de unidad en el campo de división . Tenga en cuenta que el polinomio característico de la matriz DFT anterior no puede dividirse . La matriz DFT es de orden 4. Es posible que necesitemos ir a una extensión adicional , la extensión de división del polinomio característico de la matriz DFT, que contiene al menos raíces cuartas de la unidad. Si es un generador del grupo multiplicativo de , entonces los valores propios son , en exacta analogía con el caso complejo. Ocurren con cierta 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}\}}$

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 n- ésimas primitivas 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 puede formalizarse mediante el campo con un elemento , considerando cualquier campo con una raíz n- ésima primitiva de la unidad 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 la 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 punto 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-groups
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