Transformada de Fourier discreta sobre un anillo

Generalización de la transformada de Fourier a cualquier anillo

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

Definición

Sea R un anillo cualquiera , 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 de Fourier discreta 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 entero (que incluye los campos ), basta elegir como primitiva la raíz n- ésima de la unidad , que sustituye la condición ( 1 ) por: ^[1] ${\displaystyle \alpha }$

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

Prueba

Tomar con . Dado que , , 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 ). Como es una raíz primitiva de la 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 es una potencia de dos: ( 1 ) puede reemplazarse por . ^[1] ${\displaystyle \alpha ^{n/2}=-1}$

Inverso

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

donde es 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 de Fourier discreta es un operador lineal , se puede describir mediante la multiplicación de matrices . En notación matricial, la transformada de Fourier discreta 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 de Fourier inversa 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 polinómica

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 suma en la definición de la transformada de Fourier discreta ( 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 observar 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 las raíces n- ésimas de la unidad, que son exactamente las potencias de . ${\displaystyle \alpha }$

De manera similar, la definición de la transformada de Fourier inversa ( 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 resumir esto 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 campo de los números complejos, entonces las raíces 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}},}$

lo 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 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 fórmulas, en lugar de hacerlo en la fórmula de la DFT y en la fórmula de la DFT inversa. Con esta normalización, la matriz de la DFT es unitaria. Nótese que esto 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 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 sea 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 de Fourier discreta es la reducción de códigos Reed-Solomon a códigos BCH en la teoría de codificación . Dicha transformación se puede llevar a cabo de manera eficiente con algoritmos rápidos adecuados, por ejemplo, la transformada rápida de Fourier ciclotómica . ${\displaystyle \mathrm {GF} (q)}$

Formulación polinómica sin n^Elraíz

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 . El mapa se obtiene mediante el teorema del resto chino , y el inverso se obtiene 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 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 se indicó anteriormente, podemos extender el campo base a para encontrar una raíz primitiva, es decir, un campo de división para . Ahora bien, 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 p divide n

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

Normalización de la matriz DFT

Para alinearnos con el caso complejo y asegurarnos de que la matriz sea exactamente de orden 4, podemos normalizar la matriz DFT anterior con . Tenga en cuenta que, aunque puede que no exista en el cuerpo 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}}$

Unitaridad

Supongamos . Se puede preguntar si la matriz DFT es unitaria sobre un cuerpo finito . Si las entradas de la matriz son sobre , entonces se debe asegurar que es un cuadrado perfecto o se extiende a para definir el automorfismo de orden dos . Considere 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}}$

por un argumento de serie geométrica similar al anterior. Podemos eliminar el mediante la normalización de modo que y . Por lo tanto, es unitario si y solo si . Recordemos que, dado que tenemos una raíz de 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 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 ejemplo no estándar, cuando extendemos a para obtener una octava raíz de la unidad. , entonces , y en este caso y . es una raíz cuadrada de la identidad, por lo que no es unitario. ${\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 , tenemos una raíz de unidad en el cuerpo de descomposición . Nótese que el polinomio característico de la matriz DFT anterior no puede descomponerse en . La matriz DFT es de orden 4. Es posible que debamos ir a una extensión adicional , la extensión de descomposición del polinomio característico de la matriz DFT, que al menos contiene cuartas raíces de unidad. Si es un generador del grupo multiplicativo de , entonces los valores propios son , en analogía exacta con el caso complejo. Se producen 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}\}}$

Transformación de la teoría de números

La transformada teórica de números (NTT) ^[4] se obtiene especializando la transformada de Fourier discreta en , los enteros módulo un primo p . Este es un cuerpo finito , y las raíces n ésimas primitivas de la unidad existen 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 una raíz n ésima de la unidad se puede encontrar 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 }}$

p.ej. 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 numérica puede tener sentido 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 numérica, 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}$

Transformación ponderada discreta

La transformada ponderada discreta (DWT) es una variación de la transformada de Fourier discreta sobre anillos arbitrarios que implica ponderar la entrada antes de transformarla multiplicándola elemento por elemento 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 , incluyendo la transformada inversa, el teorema de convolución y la mayoría de los algoritmos de transformada rápida 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 también se cumplen, con pruebas idénticas, sobre anillos arbitrarios. En el caso de los cuerpos, esta analogía se puede formalizar 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 ^{[ 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 teórica de números proporciona una manera eficiente de calcular convoluciones exactas de secuencias de números enteros. 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 ; la NTT no tiene redondeo porque trata exclusivamente con números enteros de tamaño fijo que se pueden representar con exactitud. ${\displaystyle O(n\log n)}$

Algoritmos rápidos

Para la implementación de un algoritmo "rápido" (similar a cómo la FFT calcula la DFT ), a menudo es deseable que la longitud de la transformada 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 longitud de la transformada se factoriza.

Véase también

• Transformada de Fourier discreta (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 de STOC 2007, págs. 57-66. Sección 2: La transformada de Fourier discreta.
2. R. Lidl y G. Pilz. Álgebra abstracta aplicada, 2.ª edición. Wiley, 1999, págs. 217-219.
3. "Jacksonwalters/DFT-grupos finitos". GitHub .
4. Agarwal, R.; Burrus, C. (abril de 1974). "Convolución rápida utilizando transformadas de números de Fermat con aplicaciones al filtrado digital". IEEE Transactions on Acoustics, Speech, and Signal Processing . 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". IEEE Transactions on Computers . 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 números 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