# Why does fft require a power of 2 sample numbers? [closed]

I'm a beginner in signal processing, I do not know if I'm right but what I understand so far is if I have a signal of 44100 samples I have 22050 frequencies

so if I choose 512 samples for the fft the 43588 samples will not be analyzed I can only edit the spectrum from 44100/512 = 86.1hz to 22050hz if I want to edit the frequency 1hz I'll have to give 441000 samples to the fft but I can only give it or 65536 samples to analyze all the 22050 frequencies then with 65536 given to the fft I can edit up to the frequency 32768hz

• It's a bit unclear what this question is about. In some program (you don't tell us which), you can only select power-of-2 FFT lengths. Truth is that the FFT exists for other lengths, too. So that's a software-specific restriction there. Then you make statements about what happens when you select 512, and my guess is that these statements are false, but I can't tell you, because you don't tell us how you know! – Marcus Müller Apr 12 '18 at 0:24
• a good fft library like fftw isn’t restricted to a power of 2. Sizes that can be factored in trms of small primes will be fast. stay away from large prime numbers – user28715 Apr 12 '18 at 0:52

to add to what Louis said, normally in both science and in engineering, novel algorithms are more primitive (requiring restrictions, i.e. $N=2^p$) than mature algorithms of the same function. so it's only historical that the first FFTs may have been power of 2 length.

the original Cooley and Tukey Decimation-in-Frequency FFT can be expressed as

\begin{align} X[k] &= \sum\limits_{n=0}^{N-1} x[n] e^{-j 2 \pi nk/N} \\ \\ &= \sum\limits_{n=0}^{N/2-1} x[n] e^{-j 2 \pi nk/N} + \sum\limits_{n=N/2}^{N-1} x[n] e^{-j 2 \pi nk/N} \\ \\ &= \sum\limits_{n=0}^{N/2-1} x[n] e^{-j 2 \pi nk/N} + \sum\limits_{n=0}^{N/2-1} x[n+\tfrac{N}{2}] e^{-j 2 \pi (n+N/2)k/N} \\ \\ &= \sum\limits_{n=0}^{N/2-1} x[n] e^{-j 2 \pi nk/N} + e^{-j 2 \pi (N/2)k/N} \sum\limits_{n=0}^{N/2-1} x[n+\tfrac{N}{2}] e^{-j 2 \pi nk/N} \\ \\ &= \sum\limits_{n=0}^{N/2-1} x[n] e^{-j 2 \pi nk/N} + e^{-j \pi k} \sum\limits_{n=0}^{N/2-1} x[n+\tfrac{N}{2}] e^{-j 2 \pi nk/N} \\ \\ &= \sum\limits_{n=0}^{N/2-1} x[n] e^{-j 2 \pi nk/N} + (-1)^k \sum\limits_{n=0}^{N/2-1} x[n+\tfrac{N}{2}] e^{-j 2 \pi nk/N} \\ \\ &= \begin{cases} \sum\limits_{n=0}^{N/2-1} x[n] e^{-j 2 \pi nk/N} + \sum\limits_{n=0}^{N/2-1} x[n+\tfrac{N}{2}] e^{-j 2 \pi nk/N} \quad &k = 2m & \text{(even)}\\ \sum\limits_{n=0}^{N/2-1} x[n] e^{-j 2 \pi nk/N} - \sum\limits_{n=0}^{N/2-1} x[n+\tfrac{N}{2}] e^{-j 2 \pi nk/N} \quad &k = 2m+1 & \text{(odd)} \\ \end{cases} \\ \\ &= \begin{cases} \sum\limits_{n=0}^{N/2-1} (x[n] + x[n+\tfrac{N}{2}]) e^{-j 2 \pi nk/N} \quad &k = 2m \\ \sum\limits_{n=0}^{N/2-1} (x[n] - x[n+\tfrac{N}{2}]) e^{-j 2 \pi nk/N} \quad &k = 2m+1 \\ \end{cases} \\ \\ &= \begin{cases} \sum\limits_{n=0}^{N/2-1} (x[n] + x[n+\tfrac{N}{2}]) e^{-j \pi nk/(N/2)} \quad &k = 2m \\ \sum\limits_{n=0}^{N/2-1} (x[n] - x[n+\tfrac{N}{2}]) e^{-j \pi nk/(N/2)} \quad &k = 2m+1 \\ \end{cases} \\ \\ &= \begin{cases} X_0[m]=\sum\limits_{n=0}^{N/2-1} (x[n]+x[n+\tfrac{N}{2}]) e^{-j \pi n(2m)/(N/2)} \quad &k = 2m \\ X_1[m]=\sum\limits_{n=0}^{N/2-1} (x[n]-x[n+\tfrac{N}{2}]) e^{-j \pi n(2m+1)/(N/2)} \quad &k = 2m+1 \\ \end{cases} \\ \\ &= \begin{cases} X_0[m]=\sum\limits_{n=0}^{N/2-1} (x[n]+x[n+\tfrac{N}{2}]) e^{-j 2 \pi nm/(N/2)} \quad &k = 2m \\ X_1[m]=\sum\limits_{n=0}^{N/2-1} \big((x[n] - x[n+\tfrac{N}{2}]) e^{-j 2 \pi n/N}\big) e^{-j 2 \pi nm/(N/2)} \quad &k = 2m+1 \\ \end{cases} \\ \end{align}

So the cost of the original DFT is $N^2$ multiplications and $N(N-1)$ additions. This DIF thing turns it into $\tfrac{N}{2}$ multiplications and $N$ additions plus the cost of two $\tfrac{N}{2}$-size DFTs. The latter would be twice $\left(\tfrac{N}2\right)^2$ multiplications and $\tfrac{N}2(\tfrac{N}2-1)$ additions.

so which is bigger?

\begin{align} N^2 &\lessgtr 2\left(\tfrac{N}{2}\right)^2 + \tfrac{N}{2} & \text{multiplications} \\ \\ N(N-1) &\lessgtr 2\tfrac{N}{2}\left(\tfrac{N}{2}-1\right) + N & \text{additions} \\ \end{align}

You can work out that the right-hand side is smaller. So here you now know that you can save computation by dividing the problem into two DFT problems of half the size.

The in-place computation (that does not require you to allocate an additional data buffer to "ping-pong" with) indicates that

\begin{align} x[n] &\leftarrow (x[n]+x[n+\tfrac{N}{2}]) \quad &k = 2m \\ x[n+\tfrac{N}{2}] &\leftarrow (x[n] - x[n+\tfrac{N}{2}]) e^{-j 2 \pi n/N} \quad &k = 2m+1 \\ \end{align}

and then work on the two $\tfrac{N}2$ sized DFT in a recursive manner.

The bit-reversed addressing comes in that you'll toss the $X_0[m]$ (even $k$) into the "zeroth" half (the earlier half, where $0 \le n < \tfrac{N}2$) and the $X_1[m]$ (odd $k$) into the "oneth" half (the latter half, where $\tfrac{N}2 \le n < N$). (Here is a place where my religion points an accusing finger at MATLAB for enshrining the terms "first half" and "second half", which i won't use.)

So now you save computation by cutting your problem into two halves. Doesn't it stand to reason that you will also save computation, if the two halves are themselves halved into quarters? This is why it is natural and, in my opinion the easiest, to think about and implement an FFT for just powers of two.

It doesn't. An FFT is just a method or implementation of computing a DFT that runs faster if the length (N) can be factored. It runs relatively faster (compared to a DFT of the same length) given a larger number of small prime factors of N, and is simpler for smaller numbers of unique prime factors of N (such as: only one).

Picking just one prime factor, such as the smallest, 2, makes textbook derivations and examples of FFT computations use less ink in the textbook and/or less chalk on the chalkboard.

But many modern FFT libraries are capable of computing an FFT for an N that is a composite product of several other (fairly small) prime factors, not just 2.

I'm not sure it will answer your question but FFT is an algorithm that computes DFT (Discrete Fourier Transform) in a fast way, generally in $O(N \cdot \log_2(N))$ instead of $O(N^2)$. To achieve this the input matrix has to be a power of 2 (here is why) but many FFT algorithm can handle any size of input since the matrix can be zero-padded.

If this is not automatically done you have to choose the next power of 2 if you want to 'keep' all the frequences.

• No, you don’t zero pad. The article you link uses the radix 2 case as an example but clearly states factoring N is the key – user28715 Apr 12 '18 at 14:19
• You are right, a power of 2 sample number is not required, it is only the optimum size for fast computation of the DFT. Thus, zero-padding is used for performance improvements. – Louis Lac Apr 12 '18 at 15:14
• I don’t think you can say that is true either, particularly with modern hardware, i.e. multi threading, cache size, multiple cores, precision..... – user28715 Apr 12 '18 at 15:23
• @StanleyPawlukiewicz, i think hotpaw is right about using the least ink to describe radix-2 FFT algorithms. but it is true what you say. i think. it's just easier to code a radix-2 or radix-4 DIF or DIT FFT. – robert bristow-johnson Apr 13 '18 at 0:52