Seguro, usted puede utilizar un radix-2 de la FFT para calcular la Fft para longitudes no es una potencia de 2 (pero no es tan eficaz como el uso de métodos adaptados específicamente a los factores de la longitud de la secuencia). Sin embargo, no es tan fácil como simplemente de relleno de la matriz original. La manera correcta de ir sobre él, debido a Rabiner, Schafer, y Rader, se denomina "chirp-z transformar". (Esta es un poco la versión condensada del papel previamente vinculado.)
Para motivar el chirp-z idea, considere la posibilidad de la DFT
$$X_k=\sum_{n=0}^{N-1} x_n \left(e^{-2\pi i/N}\right)^{k n},\qquad k = 0,\dots,N-1$$
The key step, attributed to Bluestein, considers the algebraic identity
$$kn=\frac12(k^2+n^2-(k-n)^2)$$
Substituting into the DFT and expanding out the powers yields
$$\begin{align*}&\sum_{n=0}^{N-1} x_n \left(e^{-2\pi i/N}\right)^{\frac12(k^2+n^2-(k-n)^2)}\\=&\left(\left(e^{-2\pi i/N}\right)^{k^2/2}\right)\sum_{n=0}^{N-1} \left(x_n \left(e^{-2\pi i/N}\right)^{n^2/2}\left(e^{-2\pi i/N}\right)^{-\frac{(k-n)^2}2}\right)\end{align*}$$
and we then recognize that the summation expression is precisely in the form of a convolution. The factor $\a la izquierda(e^{-2\pi i/N}\right)^{k^2/2}$ es lo que se denomina como un "chirrido"; de ahí el nombre de "chirp-z transformar".
Chirp-z por lo tanto consta de tres etapas:
- tomando el Hadamard (de las componentes) producto de la secuencia original con el sonido
- convolving con el recíproco chirp (que por supuesto es equivalente a la FFT inversa del producto de la Fft de la Hadamard del producto y de la recíproca chirp)
- tomando el producto de Hadamard de ese resultado con un chirrido. Vemos que tres o tan Fft son necesarios (restricción de la posibilidad de un posible simetría presentes).
MATLAB de la caja de herramientas de Procesamiento de Señales implementa este algoritmo como la función czt(). Ver el código en el correspondiente M-file para detalles de implementación.
El Código
Yo (el cartel original) terminó haciendo una versión de Python usando SciPy, así que pensé en editar esta respuesta para incluir el código:
from scipy import *
def czt(x, m=None, w=None, a=None):
# Translated from GNU Octave's czt.m
n = len(x)
if m is None: m = n
if w is None: w = exp(-2j * pi / m)
if a is None: a = 1
chirp = w ** (arange(1 - n, max(m, n)) ** 2 / 2.0)
N2 = int(2 ** ceil(log2(m + n - 1))) # next power of 2
xp = append(x * a ** -arange(n) * chirp[n - 1 : n + n - 1], zeros(N2 - n))
ichirpp = append(1 / chirp[: m + n - 1], zeros(N2 - (m + n - 1)))
r = ifft(fft(xp) * fft(ichirpp))
return r[n - 1 : m + n - 1] * chirp[n - 1 : m + n - 1]
@vectorize # Rounds complex numbers
def cround(z, d=None): return round(z.real, d) + 1j * round(z.imag, d)
arr = [1.0, 2.0, 3.0]
print cround(czt(arr), 4) # [ 6.0+0.j -1.5+0.866j -1.5-0.866j]
print cround(fft(arr), 4) # [ 6.0+0.j -1.5+0.866j -1.5-0.866j]
