Intereting Posts

Suppose $a_n>0$ for $n\in \mathbb{N}$. Prove that $\prod_{n=1}^\infty (1+a_n)$ converges if and only if $\sum_{n=1}^\infty a_n<\infty$.
A Curious Binomial Sum Identity without Calculus of Finite Differences
How to simplify this equation: $1\cdot N + 2(N-1) + 3(N -2) + \cdots + i(N – i + 1) + \dots + N \cdot1$?
Proof that if $\gcd(a,b) = 1$ and $a\mid n$ and $b\mid n$, $ab \mid n$
Application of the Hahn- Banach theorem
Differential operator applied to convolution
A Question on Compact Operators
Matrices whose Linear Combinations are All Singular
Open mapping theorem and second category
Is There A Polynomial That Has Infinitely Many Roots?
First Cohomology Group
Minimum of identical independent Poisson random variables
No simple group of order $96$
How to prove that the tangent to a circle is perpendicular to the radius drawn to the point of contact?
Abount linear functional: If $T(B)$ is bounded, is $T$ bounded?

If I have a program that can compute FFT’s for sizes that are powers of 2, how can I use it to compute FFT’s for other sizes?

I have read that I can supposedly zero-pad the original points, but I’m lost as to how this gives me the correct answer. If I transform a function with 5 points, I expect to get back a 5-point DFT, and I don’t understand how I can extract that from the 8-point DFT (which was calculated with zero-padding).

- Need some help with this recurrence equation
- Algorithms for Finding the Prime Factorization of an Integer
- Reasoning the calculation of the Hilbert's distance
- Counting primes
- Efficient algorithm for calculating the tetration of two numbers mod n?
- Algorithm to compute Gamma function

- Merge Sort time complexity analysis
- Heuristics for topological sort
- Honest and Deceitful Professors Problem
- Efficient computation of $\sum_{k=1}^n \lfloor \frac{n}{k}\rfloor$
- how to calculate fourier transform of a power of radial function
- How to calculate discrepancy of a sequence
- Functions that are their own Fourier transformation
- Proving Stone's Formula for Constructively obtaining the Spectral Measure for $A=A^\star$
- Finding a (small) prime great enough that there are at least m elements of order m
- Is there a polynomial-time algorithm to find a prime larger than $n$?

Sure, you can use a radix-2 FFT to compute FFTs for lengths not a power of 2 (but it is not as efficient as using methods specifically tailored to the factors of the sequence length). However, it’s not as easy as merely padding the original array. The right way of going about it, due to Rabiner, Schafer, and Rader, is termed the *“chirp-z transform”*. (This is a slightly condensed version of the paper previously linked to.)

To motivate the chirp-z idea, consider the 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 $\left(e^{-2\pi i/N}\right)^{k^2/2}$ is what is termed as a “chirp”; hence the name “chirp-z transform”.

Chirp-z thus consists of three stages:

- taking the Hadamard (componentwise) product of the original sequence with the chirp
- convolving with the reciprocal chirp (which of course is equivalent to the inverse FFT of the product of the FFTs of the Hadamard product and the reciprocal chirp)
- taking the Hadamard product of that result with a chirp. We see that three or so FFTs are needed (barring the possibility of an exploitable symmetry being present).

MATLAB’s Signal Processing toolbox implements this algorithm as the function `czt()`

. See the code in the corresponding M-file for implementation details.

I (the original poster) ended up making a Python version using SciPy, so I thought I’d edit this answer to include the code:

```
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]
```

If you want to code a DFT of size $N=5$ you have several options:

- 8-point FFT, after zero-padding
- Evaluate the DFT directly
- Special FFT algorithms (eg: Rader)

The zero-padding option is popular, and it’s exact (in two senses: the inverse gives you back the original zero-padding sequence; and both the 8-point transform and the 5-point transform correspond to the same underlying continuous DTFT, only sampled at different frequencies). But you can’t (directly, efficiently) obtain from it the 5-point DTF. So, of you really want those 5 values, this is not the alternative.

The naive alternative, to compute the 5-point DFT directly, evaluating the formula, is -of course- not a FFT (not ‘fast’) but for such a small size the difference might not be important.

The other alternative (a true 5-point FFT) is the most efficient but also the more complex to understand and implement. And you can’t use a elementary power-of-two FFT program to implement this.

Are you aware of FFTW? It’s been available for free for years; I have used it and can attest to its ease of use and speed.

Equivalence between 5 point FFT and 8 point FFT. Depending on your sampling frequency you split the FFT range(Nyquist frequency is max) in either 5 or 8 bins. If you want badly to go back to 5 point output you have to find some decent interpolation. Since 5 is almost half of 8, linear interpolation might give significant errors, so you should try something like cubic spline. Test it to estimate errors before using, to see if they are acceptable or not.

- Conditions for continuous extension of a function on an open set to its closure
- The number of solutions of $ax^2+by^2\equiv 1\pmod{p}$ is $ p-(\frac{-ab}{p})$
- Show that the set $\mathbb{Q}(\sqrt{p})=\{a+b\sqrt{p}; a,b,p\in\mathbb{Q},\sqrt{p}\notin \mathbb{Q}\}$ is a field
- Why is a straight line the shortest distance between two points?
- Prove by induction that $n^5-5n^3+4n$ is divisible by 120 for all n starting from 3
- Show that if $G$ is simple a graph with $n$ vertices and the number of edges $m>\binom{n-1}{2}$, then $G$ is connected.
- Chain of length $2^{\aleph_0}$ in $ (P(\mathbb{N}),\subseteq)$
- $\int_0^1 {\frac{{\ln (1 – x)}}{x}}$ without power series
- Norm of Fredholm integral operator equals norm of its kernel?
- Solving $|x-2| + |x-5|=3$
- Does there exist non-compact metric space $X$ such that , any continuous function from $X$ to any Hausdorff space is a closed map ?
- The centralizer of an element x in free group is cyclic
- Homomorphisms of graded modules
- Does a non-trivial solution exist for $f'(x)=f(f(x))$?
- Book recommendation for network theory