Hispanopedia Wiki
Articulo de referencia

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 complej...

Hispanopedia WikiContenido en espanolLectura gratuita

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 .

Definición

Sea R un anillo cualquiera , seanorte≥1{\displaystyle n\geq 1}Sea un número entero y seaα∈R{\displaystyle \alpha \in R}sea ​​una raíz enésima principal de la unidad, definida por: [ 1 ]

La transformada discreta de Fourier mapea una n -tupla(v0,…,vnorte−1){\displaystyle (v_{0},\ldots,v_{n-1})}de elementos de R a otra n -tupla(F0,…,Fnorte−1){\displaystyle (f_{0},\ldots ,f_{n-1})}de elementos de R según la siguiente fórmula:

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

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

αk≠1{\displaystyle \alpha ^{k}\neq 1}para1≤k<norte{\displaystyle 1\leq k<n}
Prueba

Llevarβ=αk{\displaystyle \beta =\alpha ^{k}}con1≤k<norte{\displaystyle 1\leq k<n}. Desdeαnorte=1{\displaystyle \alpha ^{n}=1},βnorte=(αnorte)k=1{\displaystyle \beta ^{n}=(\alpha ^{n})^{k}=1}, donación:

βnorte−1=(β−1)(∑j=0norte−1βj)=0{\displaystyle \beta ^{n}-1=(\beta -1)\left(\sum _{j=0}^{n-1}\beta ^{j}\right)=0}

donde la suma coincide ( 1 ). Dado queα{\displaystyle \alpha }es una raíz primitiva de la unidad,β−1≠0{\displaystyle \beta -1\neq 0}Dado que R es un dominio de integridad, la suma debe ser cero. ∎

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

Inverso

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

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

Prueba

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

1norte∑k=0norte−1Fkα−jk=1norte∑k=0norte−1∑j′=0norte−1vj′αj′kα−jk=1norte∑j′=0norte−1vj′∑k=0norte−1α(j′−j)k.{\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 avj{\displaystyle v_{j}}, porque ∑k=0norte−1α(j′−j)k=0{\displaystyle \sum _{k=0}^{n-1}\alpha ^{(j'-j)k}=0}cuandoj′≠j{\displaystyle j'\neq j}(por ( 1 ) conk=j′−j{\displaystyle k=j'-j}), y ∑k=0norte−1α(j′−j)k=norte{\displaystyle \sum _{k=0}^{n-1}\alpha ^{(j'-j)k}=n}cuandoj′=j{\displaystyle j'=j}. ∎

Formulación de la matriz

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:

[F0F1⋮Fnorte−1]=[111⋯11αα2⋯αnorte−11α2α4⋯α2(norte−1)⋮⋮⋮⋱⋮1αnorte−1α2(norte−1)⋯α(norte−1)(norte−1)][v0v1⋮vnorte−1].{\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

[v0v1⋮vnorte−1]=1norte[111⋯11α−1α−2⋯α−(norte−1)1α−2α−4⋯α−2(norte−1)⋮⋮⋮⋱⋮1α−(norte−1)α−2(norte−1)⋯α−(norte−1)(norte−1)][F0F1⋮Fnorte−1].{\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(v0,…,vnorte−1){\displaystyle (v_{0},\ldots,v_{n-1})}con un polinomio formal

pagv(incógnita)=v0+v1incógnita+v2incógnita2+⋯+vnorte−1incógnitanorte−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:

Fk=v0+v1αk+v2α2k+⋯+vnorte−1α(norte−1)k.{\displaystyle f_{k}=v_{0}+v_{1}\alpha ^{k}+v_{2}\alpha ^{2k}+\cdots +v_{n-1}\alpha ^{(n-1)k}.\,}

Esto significa queFk{\displaystyle f_{k}}es simplemente el valor del polinomiopagv(incógnita){\displaystyle p_{v}(x)}paraincógnita=αk{\displaystyle x=\alpha ^{k}}, es decir,

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

pagF(incógnita)=F0+F1incógnita+F2incógnita2+⋯+Fnorte−1incógnitanorte−1,{\displaystyle p_{f}(x)=f_{0}+f_{1}x+f_{2}x^{2}+\cdots +f_{n-1}x^{n-1},}

esto significa que

vj=1nortepagF(α−j).{\displaystyle v_{j}={\frac {1}{n}}p_{f}(\alpha ^{-j}).}

Podemos resumirlo de la siguiente manera: si los valores depagv(incógnita){\displaystyle p_{v}(x)}son los coeficientes depagF(incógnita){\displaystyle p_{f}(x)}, entonces los valores depagF(incógnita){\displaystyle p_{f}(x)}son los coeficientes depagv(incógnita){\displaystyle p_{v}(x)}, hasta un factor escalar y reordenamiento. [ 2 ]

Casos especiales

Números complejos

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

α=mi−2πinorte,{\displaystyle \alpha =e^{\frac {-2\pi i}{n}},}

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

Fk=∑j=0norte−1vjmi−2πinortejk.{\displaystyle f_{k}=\sum _{j=0}^{n-1}v_{j}e^{{\frac {-2\pi i}{n}}jk}.}

Sobre los números complejos, a menudo es habitual normalizar las fórmulas para la DFT y la DFT inversa utilizando el factor escalar.1norte{\displaystyle {\frac {1}{\sqrt {n}}}}en ambas fórmulas, en lugar de1{\displaystyle 1}en la fórmula para la DFT y1norte{\displaystyle {\frac {1}{n}}}en la fórmula para la DFT inversa. Con esta normalización, la matriz DFT es entonces unitaria. Nótese quenorte{\displaystyle {\sqrt {n}}}No tiene sentido en un campo arbitrario.

Campos finitos

SiF=GRAMOF(q){\displaystyle F=\mathrm {GF} (q)}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 aq−1{\displaystyle q-1}, porque el orden multiplicativo de cada elemento debe dividir el tamaño del grupo multiplicativo de F , que esq−1{\displaystyle q-1}Esto, en particular, garantiza quenorte=1+1+⋯+1⏟norte timetromis{\displaystyle n=\underbrace {1+1+\cdots +1} _{n\ {\rm {times}}}}es invertible, de modo que la notación1norte{\displaystyle {\frac {1}{n}}}en ( 3 ) tiene sentido.

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

Formulación polinómica sin raíz n- ésima

SuponerF=GRAMOF(pag){\displaystyle F=\mathrm {GF} (p)}. Sipag∤norte{\displaystyle p\nmid n}, puede ser el caso quenorte∤pag−1{\displaystyle n\nmid p-1}Esto significa que no podemos encontrar unnorteth{\displaystyle n^{th}}raíz de unidad enF{\displaystyle F}Podemos considerar la transformada de Fourier como un isomorfismo.F[donorte]=F[incógnita]/(incógnitanorte−1)≅⨁iF[incógnita]/(PAGi(incógnita)){\displaystyle \mathrm {F} [C_{n}]=\mathrm {F} [x]/(x^{n}-1)\cong \bigoplus _{i}\mathrm {F} [x]/(P_{i}(x))}para algunos polinomiosPAGi(incógnita){\displaystyle P_{i}(x)}, de acuerdo con el teorema de Maschke . El mapeo viene dado por el teorema chino del resto , y el inverso viene dado aplicando la identidad de Bézout para polinomios. [ 3 ]

incógnitanorte−1=∏d|norteΦd(incógnita){\displaystyle x^{n}-1=\prod _{d|n}\Phi _{d}(x)}, un producto de polinomios ciclotómicos. FactorizaciónΦd(incógnita){\displaystyle \Phi _{d}(x)}enF[incógnita]{\displaystyle F[x]}es equivalente a factorizar el ideal primo(pag){\displaystyle (p)}enZ[ζ]=Z[incógnita]/(Φd(incógnita)){\displaystyle \mathrm {Z} [\zeta ]=\mathrm {Z} [x]/(\Phi _{d}(x))}Obtenemosgramo{\displaystyle g}polinomiosPAG1…PAGgramo{\displaystyle P_{1}\ldots P_{g}}de gradoF{\displaystyle f}dóndeFgramo=φ(d){\displaystyle fg=\varphi (d)}yF{\displaystyle f}es el orden depag mod d{\displaystyle p{\text{ mod }}d}.

Como se indicó anteriormente, podemos extender el campo base aGRAMOF(q){\displaystyle \mathrm {GF} (q)}para encontrar una raíz primitiva, es decir, un campo de división paraincógnitanorte−1{\displaystyle x^{n}-1}. Ahoraincógnitanorte−1=∏k(incógnita−αk){\displaystyle x^{n}-1=\prod _{k}(x-\alpha ^{k})}, por lo tanto un elemento∑j=0norte−1vjincógnitaj∈F[incógnita]/(incógnitanorte−1){\displaystyle \sum _{j=0}^{n-1}v_{j}x^{j}\in F[x]/(x^{n}-1)}mapas a∑j=0norte−1vjincógnitajmod(incógnita−αk)≡∑j=0norte−1vj(αk)j{\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}}para cadak{\displaystyle k}.

Cuando p divide a n

Cuandopag|norte{\displaystyle p|n}, aún podemos definir unFpag{\displaystyle F_{p}}-isomorfismo lineal como se indicó anteriormente. Nótese que(incógnitanorte−1)=(incógnitametro−1)pags{\displaystyle (x^{n}-1)=(x^{m}-1)^{p^{s}}}dóndenorte=metropags{\displaystyle n=mp^{s}}ypag∤metro{\displaystyle p\nmid m}Aplicamos la factorización anterior aincógnitametro−1{\displaystyle x^{m}-1}y ahora obtenga la descomposiciónF[incógnita]/(incógnitanorte−1)≅⨁iF[incógnita]/(PAGi(incógnita)pags){\displaystyle F[x]/(x^{n}-1)\cong \bigoplus _{i}F[x]/(P_{i}(x)^{p^{s}})}Los módulos que aparecen ahora son indescomponibles en lugar de irreducibles.

Orden de la matriz DFT

Suponerpag∤norte{\displaystyle p\nmid n}así que tenemos unnorteth{\displaystyle n^{th}}raíz de la unidadα{\displaystyle \alpha }. DejarA{\displaystyle A}Sea la matriz DFT anterior una matriz de Vandermonde con entradasAij=αij{\displaystyle A_{ij}=\alpha ^{ij}}para0≤i,j<norte{\displaystyle 0\leq i,j<n}. Recuerda que∑j=0norte−1α(k−l)j=norteδk,l{\displaystyle \sum _{j=0}^{n-1}\alpha ^{(k-l)j}=n\delta _{k,l}}ya que sik=l{\displaystyle k=l}, entonces cada entrada es 1. Sik≠l{\displaystyle k\neq l}, entonces tenemos una serie geométrica con razón comúnαk−l{\displaystyle \alpha ^{k-l}}, así obtenemos1−αnorte(k−l)1−αk−l{\displaystyle {\frac {1-\alpha ^{n(k-l)}}{1-\alpha ^{k-l}}}}. Desdeαnorte=1{\displaystyle \alpha ^{n}=1}el numerador es cero, perok−l≠0{\displaystyle k-l\neq 0}por lo tanto, el denominador es distinto de cero.

Primero calculando el cuadrado,(A2)ik=∑j=0norte−1αj(i+k)=norteδi,−k{\displaystyle (A^{2})_{ik}=\sum _{j=0}^{n-1}\alpha ^{j(i+k)}=n\delta _{i,-k}}InformáticaA4=(A2)2{\displaystyle A^{4}=(A^{2})^{2}}De manera similar y simplificando los deltas, obtenemos(A4)ik=norte2δi,k{\displaystyle (A^{4})_{ik}=n^{2}\delta _{i,k}}. De este modo,A4=norte2Inorte{\displaystyle A^{4}=n^{2}I_{n}}y el orden es4⋅orden(norte2){\displaystyle 4\cdot {\text{ord}}(n^{2})}.

Normalización de la matriz DFT

Para alinearnos con el caso complejo y asegurar que la matriz sea exactamente de orden 4, podemos normalizar la matriz DFT anterior.A{\displaystyle A}con1norte{\displaystyle {\frac {1}{\sqrt {n}}}}. Tenga en cuenta que, sin embargonorte{\displaystyle {\sqrt {n}}}puede que no exista en el campo de divisiónFq{\displaystyle F_{q}}deincógnitanorte−1{\displaystyle x^{n}-1}, podemos formar una extensión cuadráticaFq2≅Fq[incógnita]/(incógnita2−norte){\displaystyle F_{q^{2}}\cong F_{q}[x]/(x^{2}-n)}en la que existe la raíz cuadrada. Entonces podemos establecerU=1norteA{\displaystyle U={\frac {1}{\sqrt {n}}}A}, yU4=Inorte{\displaystyle U^{4}=I_{n}}.

Unitaridad

Suponerpag∤norte{\displaystyle p\nmid n}. Uno puede preguntarse si la matriz DFT es unitaria sobre un campo finito . Si las entradas de la matriz son sobreFq{\displaystyle F_{q}}, entonces uno debe asegurarseq{\displaystyle q}es un cuadrado perfecto o se extiende aFq2{\displaystyle F_{q^{2}}}para definir el automorfismo de orden dosincógnita↦incógnitaq{\displaystyle x\mapsto x^{q}}Consideremos la matriz DFT anterior.Aij=αij{\displaystyle A_{ij}=\alpha ^{ij}}. Tenga en cuenta queA{\displaystyle A}es simétrico. Conjugando y transponiendo, obtenemosAij∗=αqji{\displaystyle A_{ij}^{*}=\alpha ^{qji}}.

(AA∗)ik=∑j=0norte−1αj(i+qk)=norteδi,−qk{\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 elnorte{\displaystyle n}normalizando de modo queU=1norteA{\displaystyle U={\frac {1}{\sqrt {n}}}A}y(UU∗)ik=δi,−qk{\displaystyle (UU^{*})_{ik}=\delta _{i,-qk}}. De este modoU{\displaystyle U}es unitario si y solo siq≡−1(modnorte){\displaystyle q\equiv -1\,({\text{mod}}\,n)}. Recuerda que puesto que tenemos unnorteth{\displaystyle n^{th}}raíz de la unidad,norte|q2−1{\displaystyle n|q^{2}-1}Esto significa queq2−1≡(q+1)(q−1)≡0(modnorte){\displaystyle q^{2}-1\equiv (q+1)(q-1)\equiv 0\,({\text{mod}}\,n)}. Nota siq{\displaystyle q}Para empezar, no era un cuadrado perfecto.norte|q−1{\displaystyle n|q-1}y entoncesq≡1(modnorte){\displaystyle q\equiv 1\,({\text{mod}}\,n)}.

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

Por ejemplo, cuandopag=3,norte=8{\displaystyle p=3,n=8}nos extendemos aF32{\displaystyle F_{3^{2}}}para obtener una raíz octava de la unidad.q2=9{\displaystyle q^{2}=9}, entoncesq≡3(mod8){\displaystyle q\equiv 3\,({\text{mod}}\,8)}y en este casoq+1≢0{\displaystyle q+1\not \equiv 0}yq−1≢0{\displaystyle q-1\not \equiv 0}.UU∗{\displaystyle UU^{*}}es la raíz cuadrada de la identidad, por lo tantoU{\displaystyle U}no es unitario.

Valores propios de la matriz DFT

Cuandopag∤norte{\displaystyle p\nmid n}, tenemos unnorteth{\displaystyle n^{th}}raíz de la unidadα{\displaystyle \alpha }en el campo de divisiónFq≅Fpag[incógnita]/(incógnitanorte−1){\displaystyle F_{q}\cong F_{p}[x]/(x^{n}-1)}. Tenga en cuenta que el polinomio característico de la matriz DFT anterior puede no descomponerse enFq{\displaystyle F_{q}}La matriz DFT es de orden 4. Es posible que necesitemos ir a una extensión adicional.Fq′{\displaystyle F_{q'}}, la extensión de descomposición del polinomio característico de la matriz DFT, que al menos contiene raíces cuartas de la unidad. Sia{\displaystyle a}es un generador del grupo multiplicativo deFq′{\displaystyle F_{q'}}, entonces los valores propios son{±1,±a(q′−1)/4}{\displaystyle \{\pm 1,\pm a^{(q'-1)/4}\}}, en analogía exacta con el caso complejo. Ocurren con alguna multiplicidad no negativa.

Transformación teórica de números

La transformada teórica de números (NTT) [ 4 ] se obtiene especializando la transformada discreta de Fourier aF=Z/pag{\displaystyle F={\mathbb {Z} }/p}, 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 apag−1{\displaystyle p-1}, así que tenemospag=ξnorte+1{\displaystyle p=\xi n+1}para un entero positivo ξ . Específicamente, seaω{\displaystyle \omega }ser un primitivo(pag−1){\displaystyle (p-1)}raíz enésima de la unidad, entonces raíz enésima de la unidadα{\displaystyle \alpha }se puede encontrar dejandoα=ωξ{\displaystyle \alpha =\omega ^{\xi }}.

por ejemplo parapag=5{\displaystyle p=5},α=2{\displaystyle \alpha =2}

21=2(mod5)22=4(mod5)23=3(mod5)24=1(mod5){\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}}}

cuandonorte=4{\displaystyle N=4}

[F(0)F(1)F(2)F(3)]=[1111124314141342][F(0)F(1)F(2)F(3)]{\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 anilloZ/metro{\displaystyle \mathbb {Z} /m}, 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 de la teoría 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.

En general, simetro=∏ipagimii{\textstyle m=\prod _{i}p_{i}^{e_{i}}}, entonces uno puede encontrar unnorteth{\textstyle n^{th}}raíz de la unidad módulo m al encontrar la raíz primitivanorteth{\textstyle n^{th}}raíces de la unidadgramoi{\displaystyle g_{i}}modpagimii{\textstyle p_{i}^{e_{i}}}, lo que produce una tuplagramo=(gramoi)i∈∏i(Z/pagimiiZ)∗{\textstyle g=\left(g_{i}\right)_{i}\in \prod _{i}\left(\mathbb {Z} /p_{i}^{e_{i}}\mathbb {Z} \right)^{\ast }}. La preimagen degramo{\displaystyle g}bajo el teorema chino del resto el isomorfismo es unnorteth{\textstyle n^{th}}raíz de la unidadα{\textstyle \alpha }de tal manera queαnorte/2=−1modmetro{\textstyle \alpha ^{n/2}=-1\mod m}Esto garantiza que se cumplan las condiciones de suma anteriores. Debemos tener quenorte|φ(pagimii){\textstyle n|\varphi (p_{i}^{e_{i}})}para cadai{\displaystyle i}, dóndeφ{\displaystyle \varphi }es la función totiente de Euler . [ 6 ]

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 Solinas264−232+1{\displaystyle 2^{64}-2^{32}+1}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 ]

Transformación ponderada discreta

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.

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 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.F1norte.{\displaystyle \mathbf {F} _{1^{n}}.}

En particular, la aplicabilidad deO(norteregistro⁡norte){\displaystyle O(n\log n)}Los algoritmos de transformada rápida de Fourier para calcular la transformada de Fourier no lineal (NTT), combinados con el teorema de convolución, hacen que esta transformada, basada en la teoría de números, proporcione 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.

Algoritmos rápidos

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.

Véase también

Referencias

  1. 1 2 3 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.
  2. ↑ Lidl, R.; Pilz, G. (1999). Álgebra abstracta aplicada (2.ª  ed.). Wiley. págs. 217–219 . ISBN  0-387-98290-6.
  3. ↑ "La DFT modular del grupo simétrico" . GitHub .
  4. ↑ Agarwal, R.; Burrus, C. (abril de 1974). "Convolución rápida mediante transformadas de número 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. ↑ Walters, Jackson; Silverman, Thomas. "ntt" . crates.io . Consultado el 14 de febrero de 2025 .
  7. ↑ Satriawan, Ardianto; Syafalni, Infall; Mareta, Rella; Anshori, Isa; Shalannanda, Wervyan; Barra, Aleams (2023). "Revisión conceptual sobre la transformación teórica de números y revisión exhaustiva de sus implementaciones" . IEEE Access . 11 : 70288–70316 . doi : 10.1109/ACCESS.2023.3294446 .
  8. ↑ Craig-Wood, Nick. "DWT enteros mod 2 64 -2 32 +1" . www.craig-wood.com .
  9. ↑ Crandall, Richard; Fagin, Barry (1994), "Transformadas ponderadas discretas y aritmética de enteros grandes" (PDF) , Mathematics of Computation , 62 (205): 305–324 , doi : 10.2307/2153411 , JSTOR 2153411 
  10. ↑ Yao Wang ; Xuelong Zhu (1988). "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. doi : 10.1109/49.1926 .
  • https://www.apfloat.org/ntt.html