4
$\begingroup$

Why does the DFT have only $N$ components in it? I can see that after N components the frequency component is periodic and repeats with the same values but that does not seem to explain why we can have only $N$ components. Is this related to the sampling theorem? How does this all tie together?

$\endgroup$
2
  • $\begingroup$ The continuous Fourier Transform has this symmetry between the forward and inverse transforms. Because $+j$ and $−j$ both have equal claim to squaring to be $−1$, both have equal claim to being the imaginary unit. So the forward and inverse Fourier transforms are essentially the same. So uniform sampling in one domain will cause periodic extension in the reciprocal domain. So this means that the DFT has sampled (or "discrete") and periodic sequences in both domains. $N$ contiguous samples in either domain fully define the two periodic functions in the both domains. $\endgroup$ – robert bristow-johnson Sep 16 '20 at 0:52
  • $\begingroup$ I will offer my view, which is linear algebraic and brings intuition different from that of the answers below. A signal $\mathbf{s}$ of $N$ complex entries is a vector in the $N$-dimensional complex vector space $\mathbb{C}^N$. Once can express any such vector as a linear combination ($\mathbf{s} = c_0\mathbf{u}_0 + \cdots + c_{N-1}\mathbf{u}_{N-1}$) of the vectors in a basis of $\mathbb{C}^N$. Each basis of $\mathbb{C}^N$ has exactly $N$ vectors in it. The DFT of $\mathbf{s}$ is the list of coefficients of $\mathbf{s}$ with respect to one very convenient and intuitive basis of $\mathbb{C}^N$. $\endgroup$ – Joe Mack Sep 17 '20 at 18:34
2
$\begingroup$

The DFT is discrete in both time and frequency domains with the same number of samples in each domain, this means the input to the transform and the output of the transform are both discrete and both have $N$ samples. This is defined in the formula for the DFT where we have $N$ samples in time indexed as $n = 0$ to $N-1$ and $N$ samples in frequency indexed as $k = 0$ to $N-1$. The sampling frequency is located at $k = N$.

$$ X[k] = \sum_{n=0}^{N-1}x[n]e^{-j k \frac{2\pi}{N} n}$$

This is by definition, as for example the DTFT is continuous in frequency given by

$$ X(e^{j\omega}) = \sum_{n=-\infty}^{\infty}x[n]e^{-j\omega n}$$

As we see in the DFT formula, each sample $k$ in $X[k]$ is a correlation (sum of products) of the time domain waveform $x[n]$ with the frequency tone given by $e^{-j k \frac{2\pi}{N} n}$ -- observe that the form $e^{j\phi}$ is a phasor with magnitude $1$ and angle $\phi$, so we see that for each value of $k$ that we pick, $e^{-j k \frac{2\pi}{N} n}$ is just a phasor spinning at a different rate defined by $k$. This causes the correlation to maximize when $k$ is equal to or close to the frequency of $x[n]$.

The reason for $N$ samples is also quite intuitive since as the OP saw the transform mathematically behaves the same way as if the time domain waveform was periodic: This is similar to the Fourier Series Expansion (FSE) which decomposes any single valued analytic function into an infinite series of discrete frequencies, with each frequency an integer multiple of the fundamental, with the fundamental given by $f=1/T$ Hz where $T$ is the duration in seconds of the time domain signal: That makes sense as the FSE also behaves as if that time domain waveform continued to infinity as a periodic waveform; if we repeat an arbitrary waveform over $T$ seconds, it will have a fundamental frequency at $1/T$ Hz. It also must be discrete, since each of the individual components given by the higher harmonics will also repeat only over duration $T$, and we recreate the waveform by summing each of these component (so any component that didn't repeat over $T$ would violate our ability to do that).

Thus knowing we have $N$ samples in time, the fundamental frequency would then be at $1/N$. We also know that the sampling rate is at bin $k = N$ in frequency, thus the fundamental frequency is at $k=1$, and there must then be $N$ total frequency samples (some may be equal to 0), each one the integer multiple of the fundamental, just like the FSE!

Relationship to FSE

Fundamental Frequency

$\endgroup$
9
  • $\begingroup$ looks like we had overlapping edits, Dan. did mine trample over yours? $\endgroup$ – robert bristow-johnson Sep 15 '20 at 3:56
  • $\begingroup$ often the DTFT is expressed exactly as the bilateral Z-transform with the substitution of $z=e^{-j \omega}$. but i can't see what i clobbered. $\endgroup$ – robert bristow-johnson Sep 15 '20 at 3:58
  • 1
    $\begingroup$ @Robert I was simply changing the order of the variables in the exponent of the DFT to be $-j k \frac{2\pi}{N} n$- making it a more intuitive match to $\omega_o = \frac{2\pi}{N}$ in the last graphic. But thanks for all your good clean-up. If you noticed, I finally learned to put the slash in front of sin, cos etc $\endgroup$ – Dan Boschen Sep 15 '20 at 3:59
  • 1
    $\begingroup$ Yes often given in DFT related literature as $W_N^{nk}$; the "twiddle factors" introduced by Gentleman and Sande in 1966 in explaining the DFT. So the DFT is simply $\sum_{n=0}^{N-1}x[n]W_N^{nk}$ which is so much easier to read and work with. $\endgroup$ – Dan Boschen Sep 15 '20 at 12:39
  • 2
    $\begingroup$ A little additional commentary for the OP, other noobs, my nephew, and even some of the regulars: In a chicken vs the egg sense, the DFT precedes the DTFT. The DTFT is obtained by allowing the domain to be continuous, and extending it to infinity. That's how things work in math. So statements like "sampling of the DTFT causes the inverse transform to become periodic" (en.wikipedia.org/wiki/Discrete-time_Fourier_transform) are behavioral observations not foundational statements. As for the chicken or the egg. Eggs existed way before chickens, duh. $\endgroup$ – Cedron Dawg Sep 15 '20 at 14:12
2
$\begingroup$

Why does the DFT have only N components in it ?

As you pointed out, the DFT could have an infinity of components in it, that repeat every N entries. To some extent, this is what aliasing is all about -- you're putting those "missing" bits back in.

There's two reasons (or perhaps one and a half) to limit the DFT to N components, though: One is economy -- you don't need more than N components. The other is completeness -- if you want to have a transform with an inverse, then having extra points in the forward direction makes for an indeterminate transformation in the reverse direction.

In a way that you can regard the DFT is as multiplying a vector by a square matrix. So you can say $$X = \mathbf{A}_{DFT}\ x$$ where $X$ is a vector of samples in the frequency domain and $x$ is a vector of samples in the time domain. $\mathbf{A}_{DFT}$ is defined as $$\mathbf{A}_{DFT} = \begin{bmatrix} 1 && 1 && \cdots && 1 && \cdots && 1\\ 1 && e^{-2i \pi 2/N} && \cdots && e^{-2i \pi m/N} && \cdots && e^{-2i \pi (N-1)/N} \\ && && && \vdots && && \\ 1 && e^{-2i \pi n/N} && \cdots && e^{-2i \pi\ n\,m/N} && \cdots && e^{-2i \pi (N-1)n/N} \\ && && && \vdots && && \\ 1 && e^{-2i \pi (N-1)/N} && \cdots && e^{-2i \pi\ (N-1)\,m/N} && \cdots && e^{-2i \pi (N-1)^2/N} \end{bmatrix}$$

(Work this out for yourself -- first, because it's profound, and second, because I probably made some stupid typo in there somewhere).

It turns out that $\mathbf{A}_{DFT}$ is a square Hermitian orthoganal matrix, and just a scaling factor away from being orthonormal.

The nasty thing about this is that it puts the whole thing into hard-to-grok matrix notation. The nice thing about it is that the inverse DFT just falls right into your lap: $$x = \mathbf{A}_{IDFT} X$$ and so by inspection you can say that $$\mathbf{A}_{IDFT} = \mathbf{A}_{DFT}^{-1}$$

And that is why we stop at N points in our DFT: because each of the N points in the 'output' of a DFT is uniquely defined, and that N-point DFT carries all the information in the original vector $x$, without duplication. That, in turn, means that there's an inverse transformation -- that we can even find using linear algebra, if we're in a mood.

$\endgroup$
4
  • $\begingroup$ It looks like you only revealed one of your two reasons-- what is the second reason? $\endgroup$ – Dan Boschen Sep 15 '20 at 12:29
  • $\begingroup$ T'oh! Poor editing -- I figured out at the end that I was really only making one point, and only needed to make it one way. Stand by for edits... $\endgroup$ – TimWescott Sep 15 '20 at 16:12
  • $\begingroup$ Oh I liked the mystery of it all, and thought you should always do that — for instance when there are four reasons you say there are five and list the four $\endgroup$ – Dan Boschen Sep 15 '20 at 16:15
  • 4
    $\begingroup$ Trying, but I can't resist: "There are three types of Mathematicians, those who can count and those who can't." ;-) $\endgroup$ – Cedron Dawg Sep 15 '20 at 17:07
0
$\begingroup$

The Discrete Fourier Transform (DFT) is a transform from a signal to a spectrum, both being discrete sequences. The values in the signal are called samples and the values in the spectrum are called bins. The signal may typically be real valued or complex, but the spectrum usually needs to be complex. There are signals that have strictly real spectrums.

The definition establishes the calculation a single bin value from a range of sample values called a frame:

$$ X[k] = ? \cdot \sum_{n=L}^{H} x[n] e^{-i \frac{2\pi}{N} kn} $$

The DFT definition makes no assumptions about the values of the signal outside the frame.

Common notation is:

$\quad X[\,]$ is the spectrum

$\quad k$ is the bin index

$\quad x[\,]$ is the signal

$\quad n$ is the signal index

$\quad N$ is the sample count also known as the DFT frame size

Further notation is:

$\quad ?$ is the normalization factor (usually not shown, no conventional symbol)

$\quad L$ is the lowest sample index

$\quad H$ is the highest sample index

The definition of the DFT can have variations based on the conventions used. The first is the normalization factor. The three predominant ones are:

$\quad ? = 1 $ This is the most conventional, and what you will find with most code libraries.

$\quad ? = 1/N $ This is the more meaningful one in terms of usage, and IMO be "The Correct One".

$\quad ? = 1/\sqrt{N} $ This is the Linear Algebra preferred one, as it makes the Matrix representation (TimWescott's answer) unitary.

The input range as two common ranges:

$\quad L,H = 0,N-1 $ Is the common on in code libraries and usage.

$\quad L,H = -M,M $ This is an odd sized domain which is zero centered. This configuration is the more "natural" one where $N = 2M+1$. The symbol $M$ isn't a convention.

Because of the nature of the exponential expression in the defintion, $X[k]$ will be $N$ periodic. Therefore a spectrum of N bins will contain all the obtainable information and extra calculations are redundant. (The answer being sought, I presume).

The value of $k$ represents the frequency of the corresponding basis vector in the signal space in units of cycles per frame. Because of the discrete nature of the signal, and how the underlying trigonometric functions work, values of $k$ larger than $N/2$, or smaller than $-N/2$ (known as the Nyquist bin for even $N$ values) are indistinguishable from values within this range and are known as alias frequencies.

It is common to evaluate the DFT for bins 0 through $N-1$, usually done when the input range is also 0 through $N-1$. The second most common, is to evaluate the range from $-M$ to $M$ in the case of the corresponding input range. There is nothing that says you have to compute any or all the bins. The periodicity makes conversion between different choices easy without requiring recalculation.

$$ X[k] = X[k+N]$$

The inverse DFT is mathematically equivalent to the forward one without the negative sign in the exponent. The normalization factor should be chosen so that the product of the two normalization factors is $1/N$. This is not a requirement and many code libraries will provide an unnormalized IDFT.

Whether the negative sign is in the forward transform or the inverse is relevant for complex tones, as it is desired the a signal which is a pure complex tone of frequency $k$ cycles per frame should be represented by bin $k$ in the spectrum. Since a real pure tone is an average of two complex pure tones with equal magnitude, but opposite sign, frequencies, it will be represented in bin $k$ and bin $-k=N-k$ regardless of the sign.

Like the forward DFT, the inverse DFT is periodic in its output. Thus, if you take the inverse of the spectrum of a signal, the signal you generate is a new signal which matches the original signal exactly in the frame and is N periodic outside of it.

The "ideal use" of a DFT is to frame a periodic signal on a whole number of cycles. In this case, the inverse of the spectrum and the signal match inside and outside the frame. Since a periodic signal can always be represented as the weighted sum of a set of harmonic tones, and harmonic tones have frequencies that are whole integer multiples of the fundamental, the values of the weights can be determined directly from bin values.


The N periodicity of the output is trivial to prove straight from the definition:

$$ X[k+N] = ? \cdot \sum_{n=L}^{H} x[n] e^{-i \frac{2\pi}{N} (k+N)n} = ? \cdot \sum_{n=L}^{H} x[n] e^{-i \frac{2\pi}{N} kn } e^{-i 2\pi n} = X[k] $$

Where $e^{-i 2\pi n}$ always equals 1 when $n$ is an integer.

This can be shown directly from Euler's formula:

$$ \begin{aligned} e^{i\theta} &= \cos( \theta ) + i \sin( \theta ) \\ e^{-i 2\pi n} &= \cos(-2\pi n) + i \sin(-2\pi n) \\ &= 1 + i0 = 1 \end{aligned} $$

Note, this answer does not have any dependency to the corresponding continuous case, or even presumes its existence.


A representation of a $N=16$ DFT:

enter image description here

The animated gif is even cooler, but way too large to post.

$\endgroup$
27
  • 1
    $\begingroup$ The term bin has a quite common usage accross internet for referring to elements of the forward DFT sequence $X[k]$, yet its origin is not possibly DSP textbooks. I believe the source is the users from Computer Science, Data Science, or Statistics, who like demonstrating various data, statistics, or histograms, into graphs using bins for the index of a particular kind, which doesn't have better name for. Eventually the term gained some acceptance among Electrical Engineers (DSP guys) too. So we consider $k$ of $X[k]$ as the DFT index, the frequency-index, and $n$ as the time-index. $\endgroup$ – Fat32 Sep 15 '20 at 20:39
  • 1
    $\begingroup$ Futhermore, I'm not sure about what you mean by the term ideal utilisation,but the most typical professional enginering use of DFT is for analysing frequency spectrums of continuous-time signals. (The second most common utilization for DFT/FFT being efficient implementation of convolution). In that case, probability of observing a whole period of samples from a signal of unknown period is very low; the ideal lolipop frequency view practically does not happen. But various frequency estimation methods are developed to infer the frequencies of those peaks within the observed spectrum. $\endgroup$ – Fat32 Sep 15 '20 at 21:01
  • 1
    $\begingroup$ If you used the term ideal, in place of unrealistically perfect, then yes you are right, otherwise if it was used in place of correct or proper, then my comment applies; i.e., we never expect to capture (ADC) a whole period of a periodic signal; because you don't need it. If it's you are lucky, but if it's not you are still lucky...;-) $\endgroup$ – Fat32 Sep 15 '20 at 23:56
  • 1
    $\begingroup$ These kind of exclusive discussions with you solidified my opinion on the reasons of producing a collective specific terminology to identify every annoying feature of pedantic demagogue people... :-)). $k$ is the frequency-index and $n$ is the time index. bin is a trashy name, suitable for the use of statisticians or alike ;-)) Unlike mathematicians or statisticians, we the engineers are bound by phsyical reality... $\endgroup$ – Fat32 Sep 16 '20 at 0:07
  • 2
    $\begingroup$ pedantic? demagogue? (happy that someone else gets it.) $\endgroup$ – robert bristow-johnson Sep 16 '20 at 0:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.