# Why does the frequency in the DFT have to be an integer?

I don't know why the result of DFT and FFT in MATLAB like below images..

fs=128; t=0:1/fs:1-1/fs; x=cos(2*pi*3.5*t); X=fft(x); N=length(x); n=0:N-1; f=fs*n/N; plot(f,abs(X)/N);

If I set the frequency to an integer, the result of above is like this

fs=128; t=0:1/fs:1-1/fs; x=cos(2*pi*3*t); X=fft(x); N=length(x); n=0:N-1; f=fs*n/N; plot(f,abs(X)/N);

Please teach me why the difference is occured..

There are a few different ways to interpret the math of the DFT. The one I find most suitable to explain this and other properties of the DFT assumes that the continuous Fourier domain was sampled, which causes the time domain to become periodic (just like the signal was sampled, causing the Fourier domain to become periodic).

If your signal contains a sine wave, it has a single frequency. But if a non-integer number of periods of this sine wave is represented by the samples in your discrete signal, then there will be a discontinuity when replicating these samples. This discontinuity contains all frequencies.

The "frequency" parameter used in the DFT, often represented as k, is in relation to the length of the signal. If your signal shows exactly a single period of the sine wave, this sine wave has a frequency k=1. If you see exactly two periods, it has a frequency k=2. If you see one and a half periods, then k would be 1.5, which does not exist.

Draw one and a half period of a sine wave. Now copy that signal multiple times end to end:

x = cos(linspace(0,3*pi,1000));
plot(repmat(x,1,7))
set(gca,'xticklabel',0:7)


You now have a signal where the lowest frequency corresponds to the repetition of the original signal, the period length is the length of the original signal. This is k=1. The next frequency is twice this lowest frequency (period is half). You will notice if you study the graph above that there is nothing that repeats with a frequency of 1.5 times the lowest frequency (period is 1.5 times the original signal). Such a frequency does not exist because of how the signal was constructed.

• Perfect. Thank you. DFT detect one period, so not integer period and sampling frequency will make discontinuity wave form. Is this right? – Park Jun 23 '18 at 7:55
• @Park: indeed. The width of the signal determines the base frequency, and all frequencies must be integer multiples of this frequency, otherwise it cannot be represented in the periodic signal. – Cris Luengo Jun 23 '18 at 7:57
• I didn't downvote.. I don't have surffrage. – Park Jun 23 '18 at 8:04
• It is not required to assume that the data is periodic to do a DFT. Segments of signals of any frequency (below Nyquist) can be completely represented by a DFT, just not in the obvious manner, as it is an invertible (non-lossy) transform. – hotpaw2 Jun 23 '18 at 20:48
• Much better. Periodicity outside the aperture is a useful assumption, but not the only one, nor always the most suitable one. A-priori knowledge about the waveform outside the DFT aperture may make other assumptions more correct. -1 removed. – hotpaw2 Jun 25 '18 at 16:01

A DFT of length N is a matrix decomposition into N basis vectors, which happen to be N orthogonal sinusoids (or 2N if you consider the basis vectors to be real cosine and real sine sinusoids instead of complex exponential sinusoids).

If a signal exactly matches one of those DFT basis vectors in frequency, then it gets represented as the magnitude and phase of that one single basis vector.

However, if the signal doesn't exactly match the frequency of one of those N sinusoids (e.g. is not exactly integer periodic in the DFT length), then information has to represented somehow and not the same way as an exact match in frequency. Thus, the information about it's exact frequency gets spread (decomposed) into all N DFT results, but mostly the DFT result bins nearest in frequency to the signal. This is about how information is represented in the transform, and does not need any false assumptions about periodicity of any signal as continued outside the DFT window.

Another interpretation is that this spread is a windowing artifact inherent in using any finite length FFT or DFT on a potentially longer signal that is not exactly integer periodic in aperture, due to a circular discontinuity that can not be easily represented by a set of only purely circular continuous basis vectors.

• if someone gives you a DFT result, could you distinguish it from a signal that was originally periodic or something that was truncated in time? I don’t think periodic extension is essential in every case, but it isn’t strictly false and is useful when thinking about circular convolution – user28715 Jun 23 '18 at 19:01
• Absolutely correct as to the periodic assumption not being strictly false. However it is very often false when sampling real-world data of a signal that is not somehow synchronized to the sample rate or to the FFT length. And I prefer to think of circular convolution effects as an artifact of non-lossy non-zero-padded fixed-vector-length convolution, not a characteristic of the signal itself. – hotpaw2 Jun 23 '18 at 20:38
• Simple rules like discrete time, periodic frequency, discrete frequency, periodic time are sometimes useful to students. O&S covers the DFT more than one way. I prefer the filter bank perspective but I think the Matrix multiplication perspective is the most agnostic. – user28715 Jun 23 '18 at 21:00
• The filter bank interpretation also works well, except one then has to explain the weird artifact that the filter response of each filter just happens to be exactly zero at all integer multiple frequencies except one, and non-zero everywhere else. – hotpaw2 Jun 23 '18 at 23:31
• Zero crossings happen – user28715 Jun 23 '18 at 23:33

When you consider only finite length of a signal, spectrum of the signal widen. it's the same as multiplying signal with a rectangular window. when we multiply two signals their spectrum convolved with each other, so spectrum of your infinite length signal which is a single delta function in Fourier space convoluted with spectrum of rectangular window which is a sinc function.

Now considering FFT actually samples the spectrum of finite length signal, sometimes bins of FFT place over zeros of the sinc function (integer frequency in your case) and we have illusion of single frequency spectrum.

This image is from Oppenheim's book which show the actual spectrum and the sampled spectrum obtained by FFT for a signal containing 2 monochromes.

this image shows FFT with more points.

• The DFT is also interpreted as a single cycle of a periodic signal. The truncation of time doesn’t broaden a periodic signal – user28715 Jun 23 '18 at 10:38
• @StanleyPawlukiewicz, it's the truncated signal which is repeating in the periodic signal, so it's broadened beforehand!!! – Mohammad M Jun 23 '18 at 15:04
• If some one gives you a periodic waveform of period T, you calculate a Fourier Series with that period. It isn’t being truncated. It had a discrete spectrum to begin with. – user28715 Jun 23 '18 at 18:44
• @StanleyPawlukiewicz, when you say "truncation of time doesn’t broaden a periodic signal" it means regardless of truncation interval it doesn't broaden the spectrum, but if a signal were periodic and also the truncation interval exactly matches the period (situations that never happen in reality) there would be no broadening and the spectrum contain delta functions exactly at the DFT bins. – Mohammad M Jun 24 '18 at 11:29
• Uniform samples in time gives periodic frequency spectra, uniform samples in frequency give periodic time waveforms. Does every frequency spectrum derive from a time sequence? or is the frequency equally fundamental? I gave an answer based on linear algebra, precisely because it avoids those issues and it explains the results given by the OP. Your answer isn’t wrong. It isn’t simple either and the “never happens” was what happened. The OP accepted your answer, be happy. I don’t think you answered the original question but a related question – user28715 Jun 24 '18 at 12:13

There are a few different ways of showing this. Matrix multiplication is one way. If you have a full rank square matrix $\mathbf{A}$ then $$\mathbf{A}\mathbf{A}^{-1}= \mathbf{I}$$ The DFT can be expressed as a matrix vector multiplication. There is a Matlab function called dftmtx(N) which will calculate one of size $N$. The DFT matrix is an orthogonal matrix so if $\mathbf{A}$ is a $N$ x $N$ DFT Matrix $$\mathbf{A} \mathbf{A}^{H}= N \mathbf{I}$$ so if we take a row $\mathbf{a}_1$ (first row) of $\mathbf{A}$ $$\mathbf{A} \mathbf{a}_1^{H}=\begin{bmatrix} N \\ 0 \\ \vdots \\ 0\end{bmatrix}$$ and this is true for any row of $\mathbf{A}$ (adjusting for the location in the output vector) The DFT is also linear so if $\mathbf{b}= \alpha \mathbf{a}_1 + \beta \mathbf{a}_2$ $$\mathbf{A} \mathbf{b}^{H}= N\begin{bmatrix}\alpha\\ \beta \\ 0 \\ \vdots \\ 0\end{bmatrix}$$

When you chose x=cos(2*pi*3*t) (integer frequency) is corresponds to two rows of $\mathbf{A}$ and you get 2 nonzero therms.

When you chose x=cos(2*pi*3.5*t) (non integer frequency) you need all the rows to represent it and your DFT output shows that.

Incidentally your frequency axes should go from -128/2 to 128/2

The relationship $A A^H=aI$ isn’t limited to a DFT. There are other transforms

• I appreciate your answer, but I can't understand about 'When you chose x=cos(2*pi*3*t) (integer frequency) is corresponds to two rows of A and you get 2 nonzero therms. When you chose x=cos(2*pi*3.5*t) (non integer frequency) you need all the rows to represent it and your DFT output shows that.' this. I don't know how to integer make two nonzero terms... Please explain easier..! I'm just beginner. – Park Jun 23 '18 at 4:45
• So, if the frequency is integer. Then orthogonal with A and can I get 2 nonzero terms? Additionally, if the frequency is not integer, then, does it will not be orthogonal? I'm confused.. – Park Jun 23 '18 at 5:01
• Real x= (x+conj(x))/2. cos is real part of exp(j x). this is a property of complex numbers not about DFT. – user28715 Jun 23 '18 at 10:29