Algoritmo FFT de base vectorial

El algoritmo FFT de base vectorial es un algoritmo de transformada rápida de Fourier (FFT) multidimensional, que es una generalización del algoritmo FFT de Cooley-Tukey ordinario que divide las dimensiones de la transformada por bases arbitrarias. Descompone una transformada discreta de Fourier (DFT ) multidimensional (MD) en MD DFT sucesivamente más pequeñas hasta que, finalmente, solo es necesario evaluar MD DFT triviales. ^{[ 1 ]}

El algoritmo FFT multidimensional más común es el algoritmo de filas y columnas, que consiste en transformar la matriz primero en un índice y luego en otro (véase más información en FFT ). Posteriormente, se desarrolló un FFT bidimensional directo de base 2 ^{[ 2 ]} , que puede eliminar el 25 % de las multiplicaciones en comparación con el método convencional de filas y columnas. Este algoritmo se ha extendido a matrices rectangulares y bases arbitrarias ^{[ 3 ]} , dando lugar al algoritmo general de base vectorial.

El algoritmo FFT de base vectorial puede reducir significativamente el número de multiplicaciones complejas, en comparación con el algoritmo de vector fila. Por ejemplo, para un${\displaystyle N^{M}}$matriz de elementos (M dimensiones y tamaño N en cada dimensión), el número de múltiplos complejos del algoritmo FFT de raíz vectorial para base 2 es${\displaystyle {\frac {2^{M}-1}{2^{M}}}N^{M}\log _{2}N}$Mientras tanto, para el algoritmo de filas y columnas, es${\displaystyle {\frac {MN^{M}}{2}}\log _{2}N}$. Y, en general, se obtienen ahorros aún mayores en multiplicaciones cuando este algoritmo se opera sobre bases más grandes y sobre matrices de mayor dimensión. ^{[ 3 ]}

En general, el algoritmo de base vectorial reduce significativamente la complejidad estructural de la DFT tradicional, al contar con un mejor esquema de indexación, a costa de un ligero aumento en las operaciones aritméticas. Por ello, este algoritmo se utiliza ampliamente en numerosas aplicaciones de ingeniería, ciencia y matemáticas, por ejemplo, en implementaciones de procesamiento de imágenes ^{[ 4 ]} y en el diseño de procesadores FFT de alta velocidad ^{[ 5 ] .}

Al igual que con el algoritmo FFT de Cooley-Tukey , la FFT de base vectorial bidimensional se obtiene descomponiendo la DFT bidimensional regular en sumas de DFT más pequeñas multiplicadas por factores de "redondeo".

Un algoritmo de decimación en el tiempo ( DIT ) significa que la descomposición se basa en el dominio del tiempo.${\displaystyle x}$, ver más en el algoritmo FFT de Cooley-Tukey .

Suponemos que la DFT bidimensional está definida.

${\displaystyle X(k_{1},k_{2})=\sum _{n_{1}=0}^{N_{1}-1}\sum _{n_{2}=0}^{N_{2}-1}x[n_{1},n_{2}]\cdot W_{N_{1}}^{k_{1}n_{1}}W_{N_{2}}^{k_{2}n_{2}},}$

dónde${\displaystyle k_{1}=0,\dots ,N_{1}-1}$, y${\displaystyle k_{2}=0,\dots ,N_{2}-1}$, y${\displaystyle x[n_{1},n_{2}]}$es un${\displaystyle N_{1}\times N_{2}}$matriz y${\displaystyle W_{N}=\exp(-j2\pi /N)}$.

Para simplificar, supongamos que${\displaystyle N_{1}=N_{2}=N}$y la raíz-${\displaystyle (r\times r)}$es tal que${\displaystyle N/r}$es un número entero.

Utilizando el cambio de variables:

• ${\displaystyle n_{i}=rp_{i}+q_{i}}$, dónde${\displaystyle p_{i}=0,\ldots ,(N/r)-1;q_{i}=0,\ldots ,r-1;}$
• ${\displaystyle k_{i}=u_{i}+v_{i}N/r}$, dónde${\displaystyle u_{i}=0,\ldots ,(N/r)-1;v_{i}=0,\ldots ,r-1;}$

dónde${\displaystyle i=1}$o${\displaystyle 2}$, entonces la DFT bidimensional se puede escribir como: ^{[ 6 ]}

${\displaystyle X(u_{1}+v_{1}N/r,u_{2}+v_{2}N/r)=\sum _{q_{1}=0}^{r-1}\sum _{q_{2}=0}^{r-1}\left[\sum _{p_{1}=0}^{N/r-1}\sum _{p_{2}=0}^{N/r-1}x[rp_{1}+q_{1},rp_{2}+q_{2}]W_{N/r}^{p_{1}u_{1}}W_{N/r}^{p_{2}u_{2}}\right]\cdot W_{N}^{q_{1}u_{1}+q_{2}u_{2}}W_{r}^{q_{1}v_{1}}W_{r}^{q_{2}v_{2}},}$

La ecuación anterior define la estructura básica de la raíz DIT 2-D.${\displaystyle (r\times r)}$"mariposa". (Véase "mariposa" unidimensional en el algoritmo FFT de Cooley-Tukey ).

Cuando${\displaystyle r=2}$, la ecuación se puede dividir en cuatro sumatorias, y esto lleva a: ^{[ 1 ]}

${\displaystyle X(k_{1},k_{2})=S_{00}(k_{1},k_{2})+S_{01}(k_{1},k_{2})W_{N}^{k_{2}}+S_{10}(k_{1},k_{2})W_{N}^{k_{1}}+S_{11}(k_{1},k_{2})W_{N}^{k_{1}+k_{2}}}$para${\displaystyle 0\leq k_{1},k_{2}<{\frac {N}{2}}}$,

dónde${\displaystyle S_{ij}(k_{1},k_{2})=\sum _{n_{1}=0}^{N/2-1}\sum _{n_{2}=0}^{N/2-1}x[2n_{1}+i,2n_{2}+j]\cdot W_{N/2}^{n_{1}k_{1}}W_{N/2}^{n_{2}k_{2}}}$.

El${\displaystyle S_{ij}}$puede ser visto como el${\displaystyle N/2}$DFT de -dimensiones, cada una sobre un subconjunto de la muestra original:

• ${\displaystyle S_{00}}$es la DFT sobre esas muestras de${\displaystyle x}$para lo cual ambos${\displaystyle n_{1}}$y${\displaystyle n_{2}}$son pares;
• ${\displaystyle S_{01}}$es la DFT sobre las muestras para las cuales${\displaystyle n_{1}}$es par y${\displaystyle n_{2}}$es extraño;
• ${\displaystyle S_{10}}$es la DFT sobre las muestras para las cuales${\displaystyle n_{1}}$es extraño y${\displaystyle n_{2}}$es par;
• ${\displaystyle S_{11}}$es la DFT sobre las muestras para las cuales ambas${\displaystyle n_{1}}$y${\displaystyle n_{2}}$son extraños.

Gracias a la periodicidad de la exponencial compleja , podemos obtener las siguientes identidades adicionales, válidas para${\displaystyle 0\leq k_{1},k_{2}<{\frac {N}{2}}}$:

• ${\displaystyle X{\biggl (}k_{1}+{\frac {N}{2}},k_{2}{\biggr )}=S_{00}(k_{1},k_{2})+S_{01}(k_{1},k_{2})W_{N}^{k_{2}}-S_{10}(k_{1},k_{2})W_{N}^{k_{1}}-S_{11}(k_{1},k_{2})W_{N}^{k_{1}+k_{2}}}$;
• ${\displaystyle X{\biggl (}k_{1},k_{2}+{\frac {N}{2}}{\biggr )}=S_{00}(k_{1},k_{2})-S_{01}(k_{1},k_{2})W_{N}^{k_{2}}+S_{10}(k_{1},k_{2})W_{N}^{k_{1}}-S_{11}(k_{1},k_{2})W_{N}^{k_{1}+k_{2}}}$;
• ${\displaystyle X{\biggl (}k_{1}+{\frac {N}{2}},k_{2}+{\frac {N}{2}}{\biggr )}=S_{00}(k_{1},k_{2})-S_{01}(k_{1},k_{2})W_{N}^{k_{2}}-S_{10}(k_{1},k_{2})W_{N}^{k_{1}}+S_{11}(k_{1},k_{2})W_{N}^{k_{1}+k_{2}}}$.

De manera similar, un algoritmo de decimación en frecuencia ( DIF , también llamado algoritmo de Sande-Tukey) significa que la descomposición se basa en el dominio de la frecuencia.${\displaystyle X}$, ver más en el algoritmo FFT de Cooley-Tukey .

Utilizando el cambio de variables:

• ${\displaystyle n_{i}=p_{i}+q_{i}N/r}$, dónde${\displaystyle p_{i}=0,\ldots ,(N/r)-1;q_{i}=0,\ldots ,r-1;}$
• ${\displaystyle k_{i}=ru_{i}+v_{i}}$, dónde${\displaystyle u_{i}=0,\ldots ,(N/r)-1;v_{i}=0,\ldots ,r-1;}$

dónde${\displaystyle i=1}$o${\displaystyle 2}$y la ecuación DFT se puede escribir como: ^{[ 6 ]}

${\displaystyle X(ru_{1}+v_{1},ru_{2}+v_{2})=\sum _{p_{1}=0}^{N/r-1}\sum _{p_{2}=0}^{N/r-1}\left[\sum _{q_{1}=0}^{r-1}\sum _{q_{2}=0}^{r-1}x[p_{1}+q_{1}N/r,p_{2}+q_{2}N/r]W_{r}^{q_{1}v_{1}}W_{r}^{q_{2}v_{2}}\right]\cdot W_{N}^{p_{1}v_{1}+p_{2}v_{2}}W_{N/r}^{p_{1}u_{1}}W_{N/r}^{p_{2}u_{2}},}$

Se ha demostrado que el algoritmo FFT de base dividida es un método útil para la DFT unidimensional. Este método se ha aplicado a la FFT de base vectorial para obtener una FFT de base vectorial dividida. ^{[ 6 ] [ 7 ]}

En el algoritmo convencional de raíz vectorial 2D, descomponemos los índices${\displaystyle k_{1},k_{2}}$en 4 grupos:

${\displaystyle {\begin{array}{lcl}X(2k_{1},2k_{2})&:&{\text{even-even}}\\X(2k_{1},2k_{2}+1)&:&{\text{even-odd}}\\X(2k_{1}+1,2k_{2})&:&{\text{odd-even}}\\X(2k_{1}+1,2k_{2}+1)&:&{\text{odd-odd}}\end{array}}}$

Mediante el algoritmo de raíz vectorial dividida, los tres primeros grupos permanecen sin cambios, el cuarto grupo impar-impar se descompone aún más en otros cuatro subgrupos, y siete grupos en total:

${\displaystyle {\begin{array}{lcl}X(2k_{1},2k_{2})&:&{\text{even-even}}\\X(2k_{1},2k_{2}+1)&:&{\text{even-odd}}\\X(2k_{1}+1,2k_{2})&:&{\text{odd-even}}\\X(4k_{1}+1,4k_{2}+1)&:&{\text{odd-odd}}\\X(4k_{1}+1,4k_{2}+3)&:&{\text{odd-odd}}\\X(4k_{1}+3,4k_{2}+1)&:&{\text{odd-odd}}\\X(4k_{1}+3,4k_{2}+3)&:&{\text{odd-odd}}\end{array}}}$

Eso significa que el cuarto término en la base DIT 2-D-${\displaystyle (2\times 2)}$ecuación,${\displaystyle S_{11}(k_{1},k_{2})W_{N}^{k_{1}+k_{2}}}$se convierte en: ^{[ 8 ]}

${\displaystyle A_{11}(k_{1},k_{2})W_{N}^{k_{1}+k_{2}}+A_{13}(k_{1},k_{2})W_{N}^{k_{1}+3k_{2}}+A_{31}(k_{1},k_{2})W_{N}^{3k_{1}+k_{2}}+A_{33}(k_{1},k_{2})W_{N}^{3(k_{1}+k_{2})},}$

dónde${\displaystyle A_{ij}(k_{1},k_{2})=\sum _{n_{1}=0}^{N/4-1}\sum _{n_{2}=0}^{N/4-1}x[4n_{1}+i,4n_{2}+j]\cdot W_{N/4}^{n_{1}k_{1}}W_{N/4}^{n_{2}k_{2}}}$

El 2-DN por N DFT se obtiene luego mediante el uso sucesivo de la descomposición anterior, hasta la última etapa.

Se ha demostrado que el algoritmo de raíz vectorial dividida ha ahorrado alrededor del 30% de las multiplicaciones complejas y aproximadamente la misma cantidad de sumas complejas para operaciones típicas.${\displaystyle 1024\times 1024}$matriz, en comparación con el algoritmo de raíz vectorial. ^{[ 7 ]}