# Confusion in N of N-point-FFT

On what basis, N of N-point-fft is chosen? What can go wrong if I don't select it to be power of 2? How is this N related to sampling frequency?

Firstly, you need to know that the FFT computes the DFT (discrete Fourier transform) in an efficient manner. Hence, the output of an N-point FFT and N-point DFT are exactly the same.

Now, especially, if N is a power-of-two, the FFT can be calculated very efficiently. Though, if N can be factorized into rel. small prime numbers (2, 3, 5), still the calculation can be done very efficiently. Strictly speaking, the Radix-2 FFT only works, if N is power-of-two. However, in common implementations in software, N can be any number and the implementation chooses the appropriate algorithms for most efficient calculation.

Hence, if N is power of two, the calculation by FFT is just a bit faster, compared to when N would be a large prime number.

Regarding sampling frequency: If $F_s$ is your sampling frequency and $T$ is the duration of the FFT window, then $N=TF_s$. It's hard to answer more detailed what you mean by relation to sampling frequency, because I dont know exactly what you are asking.

Regarding your comment: The DFT maps a subset of the frequency range $[0,\dots,F_s]$ to the $N$ DFT-bins, which are indexed by $k=0,\ldots,N-1$. Since all frequency bins in the DFT output have the same distance to each other (i.e. they are linearly spaced), you immediately end up with $f=\frac{k}{N}F_s$, i.e. the $k$th bin corresponds to the physical frequency $f=\frac{k}{N}F_s$.

• I'm asking about this mapping formula: f/fs=k/N, where f is the analog bandwidth. I'm unable to understand it. – anonymous Feb 27 '17 at 9:49
• I added a small explanation. Is it still unclear? – Maximilian Matthé Feb 27 '17 at 10:03
• " T is the duration of the FFT window, then N=TFs ". Here T=k/N? For example, if I take N =1024 and k is the range of samples of signal of interest e.g., k =750-290=460, then f=(0.44921875)* fs. Am I getting the formula right? – anonymous Feb 27 '17 at 10:20
• No, you first define $T$ and $F_s$. Then, within the time window $T$ you get $N$ samples (in time domain), due to sampling with frequency $F_s$. So, you define $T$ and $F_s$ a priori, and then you get $N$. From this, after DFT, you can calculate that the value in the $k$th bin of the N-point DFT corresponds to the physical frequency $k/N F_s$. – Maximilian Matthé Feb 27 '17 at 11:19