Clásico Fast Fourier Transfrom (FFT) funciona bien, cuando $n$ es potencia de 2. ¿Cómo generalizar el procedimiento de FFT cuando $n$ es potencia de 3? ¿Es posible modificar el algoritmo y preservar su corrección?
Gracias de antemano.
Respuestas
¿Demasiados anuncios?
fianchetto
Puntos
186
FFT se define para que cada descomposición a factores, es decir, si n $$ = p_1 ^ {r_1} \cdots p_k ^ {r_k}, $$ entonces la FFT de un $n$-vector es definible en $r_1+\cdots+r_k$ pasos:
Paso 1. Creamos un $p_1$-vector
Paso 2. Creamos un $p_1^2$-vector...
Paso $r_1$. Creamos un $p_1^{r_1}$-vector...
Paso $r_1\!+\!1$. Creamos un $p_1^{r_1}p_2$-vector, etcetera.
Oleg Pavliv
Puntos
7781
Permítanme tratar de explicar mi punto de vista para el paso recursivo para el cálculo de la FFT. Definir primero un par de cosas.
Deje $F_N=[\omega_n^{2\pi ikl/N}]_{k,l\leq N}$, ser la FFT de la matriz de orden $N$ $\omega_N = e^{2\pi i /N}$ $N$'th raíz de la unidad.
Deje $A\in{\mathbb R}^{m_1\times n_1}$ y $B\in{\mathbb R}^{m_1\times n_1}$ el producto de Kronecker $A\otimes B$ y la caja del producto $A\boxtimes B$ son definidos por $$ (A\otimes B)_{(i-1)m_2+j(k-1)n_2+l}=a_{ik}b_{jl}=(A\otimes B)_{(i,j),(k,l)} $$ y $$ (A\boxtimes B)_{(i-1)m_2+j(k-1)n_1+l}=a_{il}b_{jk}=(A\otimes B)_{(i,j),(k,l)} $$ Estas dos operaciones son útiles debido a que $(A\otimes B)\mathrm{vec}(X)=\mathrm{vec}(AXB)$ y $(A\boxtimes B)\mathrm{vec}(X)=\mathrm{vec}(AX^\top B)$.
Ahora definir $$ V_{mk}(\alpha)=\begin{pmatrix} 1 & 1 & 1 & \cdots & 1\\ 1 & \alpha & \alpha^2 & \cdots & \alpha^{k-1}\\ 1 & \alpha^2 & \alpha^4 & \cdots & \alpha^{2(k-1)}\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & \alpha^{m-1} & \alpha^{2(m-1)} & \cdots & \alpha^{(m-1)(k-1)} \end{pmatrix} $$ entonces si $N=km$ $$ F_N=(F_k\otimes I_m)\mathrm{diag}(V_{mk}(\omega_N))(I_k\boxtimes F_m) $$ Para el cálculo de la FFT de una señal de $x$ simplemente necesitamos para calcular $F_N x$. Ahora remodelar $x$ en una matriz de $X$ tal que $x=\mathrm{vec}(X)$, entonces podemos usar las reglas para la Kronecker y de la caja del producto para calcular la matriz de vectores producto de manera eficiente: $$ F_N \mathrm{vec}(X) = \mathrm{vec}((V_{mk}(\omega_N))\circ (F_m X^\la parte superior))F_k^\la parte superior), $$ donde $\circ$ denota elemento sabio de la multiplicación. En lugar de tomar $O(N^2)=O(k^2m^2)$ de las operaciones de esta expresión hace el trabajo en $O(km(k+m))$ operaciones. Ahora simplemente repita el procedimiento para factorizar $F_k$ $F_m$ de forma recursiva.
Lierre
Puntos
3285
No sé lo que quieres hacer con FFT, así que esto podría no ser relevante para usted,
Una buena generalización de la FFT para tamaño arbitrario, no sólo potencias de dos, es la transformada de Fourier truncada, introducido por Joris van der Hoeven, que se comporta bien para todos, y suaviza los saltos de la FFT. Se aplica muy bien a la multiplicación de los algoritmos (polinomio, enteros) basado en la transformada de Fourier.
Enlace al artículo : http://www.texmacs.org/joris/issac04/issac04.pdf
