Transformada rápida de Fourier ciclotómica

La transformada rápida de Fourier ciclotómica es un tipo de algoritmo de transformada rápida de Fourier sobre cuerpos finitos . ^[1] Este algoritmo primero descompone una DFT en varias convoluciones circulares y luego deriva los resultados de la DFT a partir de los resultados de la convolución circular. Cuando se aplica a una DFT sobre , este algoritmo tiene una complejidad multiplicativa muy baja. En la práctica, dado que generalmente existen algoritmos eficientes para convoluciones circulares con longitudes específicas, este algoritmo es muy eficiente. ^[2] ${\displaystyle GF(2^{m})}$

Fondo

La transformada de Fourier discreta sobre cuerpos finitos encuentra una amplia aplicación en la decodificación de códigos de corrección de errores, como los códigos BCH y los códigos Reed-Solomon . Generalizada a partir del cuerpo complejo , una transformada de Fourier discreta de una secuencia sobre un cuerpo finito GF( p ^m ) se define como ${\displaystyle \{f_{i}\}_{0}^{N-1}}$

${\displaystyle F_{j}=\sum _{i=0}^{N-1}f_{i}\alpha ^{ij},0\leq j\leq N-1,}$

donde es la raíz primitiva N -ésima de 1 en GF( p ^m ). Si definimos la representación polinómica de como ${\displaystyle \alpha }$ ${\displaystyle \{f_{i}\}_{0}^{N-1}}$

${\displaystyle f(x)=f_{0}+f_{1}x+f_{2}x^{2}+\cdots +f_{N-1}x^{N-1}=\sum _{0}^{N-1}f_{i}x^{i},}$

Es fácil ver que es simplemente . Es decir, la transformada de Fourier discreta de una secuencia la convierte en un problema de evaluación polinómica. ${\displaystyle F_{j}}$ ${\displaystyle f(\alpha ^{j})}$

Escrito en formato matricial,

${\displaystyle \mathbf {F} =\left[{\begin{matrix}F_{0}\\F_{1}\\\vdots \\F_{N-1}\end{matrix}}\right]=\left[{\begin{matrix}\alpha ^{0}&\alpha ^{0}&\cdots &\alpha ^{0}\\\alpha ^{0}&\alpha ^{1}&\cdots &\alpha ^{N-1}\\\vdots &\vdots &\ddots &\vdots \\\alpha ^{0}&\alpha ^{N-1}&\cdots &\alpha ^{(N-1)(N-1)}\end{matrix}}\right]\left[{\begin{matrix}f_{0}\\f_{1}\\\vdots \\f_{N-1}\end{matrix}}\right]={\mathcal {F}}\mathbf {f} .}$

La evaluación directa de la DFT es compleja. Las transformadas rápidas de Fourier son simplemente algoritmos eficientes que evalúan el producto matriz-vector mencionado anteriormente. ${\displaystyle O(N^{2})}$

Algoritmo

Primero, definimos un polinomio linealizado sobre GF(p ^m ) como

${\displaystyle L(x)=\sum _{i}l_{i}x^{p^{i}},l_{i}\in \mathrm {GF} (p^{m}).}$

${\displaystyle L(x)}$se llama linealizado porque , lo que proviene del hecho de que para los elementos ${\displaystyle L(x_{1}+x_{2})=L(x_{1})+L(x_{2})}$ ${\displaystyle x_{1},x_{2}\in \mathrm {GF} (p^{m}),}$ ${\displaystyle (x_{1}+x_{2})^{p}=x_{1}^{p}+x_{2}^{p}.}$

Nótese que es invertible módulo porque debe dividir el orden del grupo multiplicativo del cuerpo . Por lo tanto, los elementos se pueden dividir en clases laterales ciclotómicas módulo : ${\displaystyle p}$ ${\displaystyle N}$ ${\displaystyle N}$ ${\displaystyle p^{m}-1}$ ${\displaystyle \mathrm {GF} (p^{m})}$ ${\displaystyle \{0,1,2,\ldots ,N-1\}}$ ${\displaystyle l+1}$ ${\displaystyle N}$

${\displaystyle \{0\},}$

${\displaystyle \{k_{1},pk_{1},p^{2}k_{1},\ldots ,p^{m_{1}-1}k_{1}\},}$

${\displaystyle \ldots ,}$

${\displaystyle \{k_{l},pk_{l},p^{2}k_{l},\ldots ,p^{m_{l}-1}k_{l}\},}$

donde . Por lo tanto, la entrada a la transformada de Fourier se puede reescribir como ${\displaystyle k_{i}=p^{m_{i}}k_{i}{\pmod {N}}}$

${\displaystyle f(x)=\sum _{i=0}^{l}L_{i}(x^{k_{i}}),\quad L_{i}(y)=\sum _{t=0}^{m_{i}-1}y^{p^{t}}f_{p^{t}k_{i}{\bmod {N}}}.}$

De esta manera, la representación polinómica se descompone en una suma de polinomios lineales, y por lo tanto viene dada por ${\displaystyle F_{j}}$

${\displaystyle F_{j}=f(\alpha ^{j})=\sum _{i=0}^{l}L_{i}(\alpha ^{jk_{i}})}$.

Desarrollando con la base propia , tenemos donde , y por la propiedad del polinomio linealizado , tenemos ${\displaystyle \alpha ^{jk_{i}}\in \mathrm {GF} (p^{m_{i}})}$ ${\displaystyle \{\beta _{i,0},\beta _{i,1},\ldots ,\beta _{i,m_{i}-1}\}}$ ${\displaystyle \alpha ^{jk_{i}}=\sum _{s=0}^{m_{i}-1}a_{ijs}\beta _{i,s}}$ ${\displaystyle a_{ijs}\in \mathrm {GF} (p)}$ ${\displaystyle L_{i}(x)}$

${\displaystyle F_{j}=\sum _{i=0}^{l}\sum _{s=0}^{m_{i}-1}a_{ijs}\left(\sum _{t=0}^{m_{i}-1}\beta _{i,s}^{p^{t}}f_{p^{t}k_{i}{\bmod {N}}}\right)}$

Esta ecuación se puede reescribir en forma matricial como , donde es una matriz sobre GF( p ) que contiene los elementos , es una matriz diagonal en bloques y es una matriz de permutación que reagrupa los elementos en de acuerdo con el índice de clase coconjunto ciclotómico. ${\displaystyle \mathbf {F} =\mathbf {AL\Pi f} }$ ${\displaystyle \mathbf {A} }$ ${\displaystyle N\times N}$ ${\displaystyle a_{ijs}}$ ${\displaystyle \mathbf {L} }$ ${\displaystyle \mathbf {\Pi } }$ ${\displaystyle \mathbf {f} }$

Nótese que si se utiliza la base normal para expandir los elementos del campo de , el i-ésimo bloque de viene dado por: ${\displaystyle \{\gamma _{i}^{p^{0}},\gamma _{i}^{p^{1}},\cdots ,\gamma _{i}^{p^{m_{i}-1}}\}}$ ${\displaystyle \mathrm {GF} (p^{m_{i}})}$ ${\displaystyle \mathbf {L} }$

${\displaystyle \mathbf {L} _{i}={\begin{bmatrix}\gamma _{i}^{p^{0}}&\gamma _{i}^{p^{1}}&\cdots &\gamma _{i}^{p^{m_{i}-1}}\\\gamma _{i}^{p^{1}}&\gamma _{i}^{p^{2}}&\cdots &\gamma _{i}^{p^{0}}\\\vdots &\vdots &\ddots &\vdots \\\gamma _{i}^{p^{m_{i}-1}}&\gamma _{i}^{p^{0}}&\cdots &\gamma _{i}^{p^{m_{i}-2}}\\\end{bmatrix}}}$

que es una matriz circulante . Es bien sabido que un producto matriz-vector circulante se puede calcular de manera eficiente mediante convoluciones . Por lo tanto, reducimos con éxito la transformada de Fourier discreta en convoluciones cortas.

Complejidad

Cuando se aplica a un campo característico -2 GF(2 ^m ), la matriz es simplemente una matriz binaria. Solo se utiliza la adición al calcular el producto matriz-vector de y . Se ha demostrado que la complejidad multiplicativa del algoritmo ciclotómico está dada por , y la complejidad aditiva está dada por . ^[2] ${\displaystyle \mathbf {A} }$ ${\displaystyle \mathrm {A} }$ ${\displaystyle \mathrm {L\Pi f} }$ ${\displaystyle O(n(\log _{2}n)^{\log _{2}{\frac {3}{2}}})}$ ${\displaystyle O(n^{2}/(\log _{2}n)^{\log _{2}{\frac {8}{3}}})}$

Referencias

1. SV Fedorenko y PV Trifonov, Fedorenko, SV; Trifonov, PV. (2003). "Sobre el cálculo de la transformada rápida de Fourier sobre cuerpos finitos" (PDF) . Actas del Taller internacional sobre teoría de codificación algebraica y combinatoria : 108–111.
2. Wu, Xuebin; Wang, Ying; Yan, Zhiyuan (2012). "Sobre algoritmos y complejidades de transformadas rápidas de Fourier ciclotómicas sobre campos finitos arbitrarios". IEEE Transactions on Signal Processing . 60 (3): 1149–1158. doi :10.1109/tsp.2011.2178844.