Algoritmo FFT de base vectorial

Algoritmo de transformada rápida multidimensional de Fourier

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 radices arbitrarios. Descompone una transformada de Fourier discreta (DFT) multidimensional (MD) en MD DFT sucesivamente más pequeñas hasta que, en última instancia, solo es necesario evaluar MD DFT triviales. ^[1]

El algoritmo FFT multidimensional más común es el algoritmo fila-columna, que significa transformar la matriz primero en un índice y luego en el otro, ver más en FFT . Luego se desarrolló una FFT 2-D directa radix-2, ^[2] que puede eliminar el 25% de los multiplicados en comparación con el enfoque convencional de fila-columna. Y este algoritmo se ha extendido a matrices rectangulares y radices arbitrarias, ^[3] que es el 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 una matriz de elementos (M dimensiones y tamaño N en cada dimensión), el número de múltiplos complejos del algoritmo FFT de base vectorial para radix-2 no se pudo analizar (SVG (MathML se puede habilitar mediante el complemento del navegador): Respuesta no válida ("La extensión Math no puede conectarse a Restbase") del servidor "http://localhost:6011/en.wikipedia.org/v1/":): {\displaystyle \frac{2^M -1}{2 ^M} N^M \log_2 N} , mientras tanto, para el algoritmo fila-columna, es . Y, en general, se obtienen ahorros aún mayores en multiplicaciones cuando este algoritmo se opera en radices más grandes y en matrices de dimensiones más altas. ^[3] ${\displaystyle N^{M}}$ ${\displaystyle {\frac {MN^{M}}{2}}\log _{2}N}$

En general, el algoritmo vector-radix reduce significativamente la complejidad estructural del DFT tradicional al tener un mejor esquema de indexación, a expensas de un ligero aumento en las operaciones aritméticas. Por lo tanto, este algoritmo se usa ampliamente para muchas aplicaciones en ingeniería, ciencia y matemáticas, por ejemplo, implementaciones en procesamiento de imágenes ^[4] y diseño de procesadores FFT de alta velocidad. ^[5]

Caja DIT 2D

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

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

Suponemos que la DFT 2-D 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}},}$

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

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

Usando 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;}$

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

${\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}},}$

"Mariposa" de una etapa para DIT vector-radix 2x2 FFT

La ecuación anterior define la estructura básica de la base DIT 2-D: "mariposa". (Ver "mariposa" 1-D en el algoritmo FFT de Cooley-Tukey ) ${\displaystyle (r\times r)}$

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

${\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}}}$

Puede verse como una DFT de dimensiones, cada una sobre un subconjunto de la muestra original: ${\displaystyle S_{ij}}$ ${\displaystyle N/2}$

• ${\displaystyle S_{00}}$es la DFT sobre aquellas muestras de para las cuales ambos y son pares; ${\displaystyle x}$ ${\displaystyle n_{1}}$ ${\displaystyle n_{2}}$
• ${\displaystyle S_{01}}$es la DFT sobre las muestras para las cuales es par e impar; ${\displaystyle n_{1}}$ ${\displaystyle n_{2}}$
• ${\displaystyle S_{10}}$es la DFT sobre las muestras para las cuales es par e impar; ${\displaystyle n_{1}}$ ${\displaystyle n_{2}}$
• ${\displaystyle S_{11}}$es la DFT sobre las muestras para las cuales ambos y son impares. ${\displaystyle n_{1}}$ ${\displaystyle n_{2}}$

Gracias a la periodicidad del exponencial complejo , 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}}}$.

Caja DIF 2D

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

Usando 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;}$

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

${\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}},}$

Otros enfoques

Se ha demostrado que el algoritmo FFT de base dividida es un método útil para DFT 1-D. Y 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 base vectorial 2-D, descomponemos los índices en 4 grupos: ${\displaystyle k_{1},k_{2}}$

${\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 división de vector-base, los primeros tres grupos permanecen sin cambios, el cuarto grupo impar-impar se descompone 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 ecuación de base DIT 2-D se convierte en: ^[8] ${\displaystyle (2\times 2)}$ ${\displaystyle S_{11}(k_{1},k_{2})W_{N}^{k_{1}+k_{2}}}$

${\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 base vectorial dividida ha ahorrado aproximadamente el 30% de las multiplicaciones complejas y aproximadamente el mismo número de sumas complejas para una matriz típica, en comparación con el algoritmo de base vectorial. ^[7] ${\displaystyle 1024\times 1024}$

Referencias

1. Dudgeon, Dan; Russell, Mersereau (septiembre de 1983). Procesamiento de señales digitales multidimensionales . Prentice Hall. pag. 76.ISBN​ 0136049591.
2. Rivard, G. (1977). "Transformada rápida directa de Fourier de funciones bivariadas". Transacciones IEEE sobre acústica, voz y procesamiento de señales . 25 (3): 250–252. doi :10.1109/TASSP.1977.1162951.
3. , D.; McClellan, J.; Chan, D.; Schuessler, H. (1977). "Transformación rápida de Fourier de base vectorial". ICASSP '77. Conferencia internacional IEEE sobre acústica, voz y procesamiento de señales . vol. 2. págs. 548–551. doi :10.1109/ICASSP.1977.1170349.
4. Buijs, H.; Pomerleau, A.; Fournier, M.; Tam, W. (diciembre de 1974). "Implementación de una transformada rápida de Fourier (FFT) para aplicaciones de procesamiento de imágenes". Transacciones IEEE sobre acústica, voz y procesamiento de señales . 22 (6): 420–424. doi :10.1109/TASSP.1974.1162620.
5. Badar, S.; Dandekar, D. (2015). "Diseño de procesador FFT de alta velocidad utilizando arquitectura canalizada Radix - ⁴ ". 2015 Congreso Internacional de Instrumentación y Control Industrial (ICIC) . págs. 1050-1055. doi :10.1109/IIC.2015.7150901. ISBN 978-1-4799-7165-7. S2CID  11093545.
6. Chan, Carolina del Sur; Ho, KL (1992). "Transformada de Fourier rápida de base vectorial dividida". Transacciones IEEE sobre procesamiento de señales . 40 (8): 2029-2039. Código Bib : 1992ITSP...40.2029C. doi :10.1109/78.150004.
7. Pei, Soo-Chang; Wu, Ja-Lin (abril de 1987). "Transformación rápida de Fourier 2D de base vectorial dividida". ICASP '87. Conferencia internacional IEEE sobre acústica, voz y procesamiento de señales . vol. 12. págs. 1987-1990. doi :10.1109/ICASSP.1987.1169345. S2CID  118173900.
8. Wu, H.; Paoloni, F. (agosto de 1989). "Sobre el algoritmo FFT de base dividida de vector bidimensional". Transacciones IEEE sobre acústica, voz y procesamiento de señales . 37 (8): 1302-1304. doi : 10.1109/29.31283.