Signal Processing Stack Exchange is a question and answer site for practitioners of the art and science of signal, image and video processing. It only takes a minute to sign up.
Sign up to join this community
What "are" they? What's a sensible way to interpret the coefficients (and what isn't)? To pose specifics:
Are either of the above true?
At it's most fundamental, the DFT is about fitting a set of basis functions to a given set of sampled data. The basis functions are all sinusoidal functions, expressed as the complex exponential with a purely imaginary exponent. Using the most common scaling convention each basis function, without its scaling coefficient, is:
$$ g_k[n] \triangleq \tfrac1N e^{j \omega_k n} $$
For the DFT:
$$ \omega_k = \frac{2 \pi k}{N} $$
and the basis functions add up as
$$\begin{align} x[n] &= \sum\limits_{k=0}^{N-1} X[k] \ g_k[n]\\ \\ &= \sum\limits_{k=0}^{N-1} X[k] \ \tfrac1N e^{j \omega_k n} \\ \\ &= \tfrac1N \sum\limits_{k=0}^{N-1} X[k] \ e^{j \frac{2 \pi k}{N} n} \\ \end{align}$$
It's real easy to solve for the coefficients:
$$\begin{align} X[k] &= \sum\limits_{n=0}^{N-1} x[n] \ e^{ -j \frac{2 \pi k}{N} n} \\ \end{align}$$
To be clear, DFT coefficients do NOT give the amplitude and phases of real sinusoidal components of the original signal unless the signal itself is real, but rather give the amplitude and phase of the exponential frequency components scaled by $N$, which are given in the form of $c_ke^{j\omega_k n}$ and referred to as "complex sinusoids".
The sum of complex weighted exponentials is directly from the inverse DFT formula as given below:
$$x[n] = \frac{1}{N}\sum_{k=0}^{N-1}X[k]e^{j \omega_k n}$$
Where each $X[k]$ is given as:
$$X[k] = \sum_{n=0}^{N-1}x[n]e^{-j \omega_k n}$$
Showing how each sample is restored as the sum of all the properly weighted and phased frequency components each in the form of $e^{j \omega_k n}$.
The generalized expression $Ae^{j\phi}$ is a phasor with magnitude $A$ and angle $\phi$. Thus every coefficient in the DFT is a complex number that represents the magnitude and starting phase of a complex phasor in time that rotates at an integer multiple of the fundamental frequency, which is given by the inverse of the total time duration of the time-domain waveform (similar to the continuous-time Fourier Series expansion).
Stated another way, the inverse DFT reconstructs any arbitrary time-domain sequence of samples both real and complex from a set of basis functions of the form of $e^{j\omega_k n}$, and the DFT maps any arbitrary time-domain sequence of samples both real and complex into the components of those basis functions (showing how much of each basis function is contained in the time domain signal and it's phase relationship to all the other components).
To give this visual meaning, with the OP further clarified in the comments is desired, consider this: We can select any arbitrary $N$ samples throughout a complex plane representing a discrete complex time-domain waveform, such that we sequence through each of those samples in turn. The DFT amazingly will return to us the magnitude and starting phase for $N$ vectors, with each vector rotating an integer number of cycles starting with 0 (no rotation) up to $N-1$ cycles around the unit circle, such that if we add all these spinning phasors (and divide by $N$), the end point of this spinning geometrical contraption will pass through every time domain sample exactly at the correct moment in time.
To immediately visualize this, consider the simplest case of a 2 point IDFT which would result in
$$x[n] = \frac{1}{N}\sum_{k=0}^{N-1}X[k]e^{j \omega_k n} = \frac{X_0}{2}e^{j0}+\frac{X_1}{2}e^{j\omega_1 n}$$
where $\omega_1$ is 1 rotation and is depicted by the following graphic.
Consider if we chose as time domain samples $[1,0]$: The DFT result is $[1,1]$ representing a phasor of magnitude $1$ and angle $0$ that doesn't rotate, added to a phasor of magnitude $1$ that rotates one cycle (just as depicted in the graphic above), so at both samples in time the above graphic will be at $[2,0]$, and after dividing by $N$ is our original sequence.
Consider if we chose as time domain samples $[1,1]$: The DFT result is $[2,0]$ representing a phasor of magnitude $2$ and angle $0$ that doesn't rotate, added to a phasor of magnitude $0$, so at both samples in time the result will be at $[2,2]$, and after dividing by $N$ is our original sequence.
Finally consider if we chose as time domain samples $[1+j1,-1+j1]$: The DFT result is $[2j, 2]$ representing a phasor of magnitude $2$ and angle $\pi/2$ that doesn't rotate, added to a phasor of magnitude $2$ and angle $0$ that rotates one cylce (as depicted in the graphic below), so at both samples in time the result will be at $[2+j2, -2+j2]$, and after dividing by $N$ is our original sequence.
atan2() function, which is what i was saying. but what i am still worried about (i gotta blast out the math) is the minus sign.
$\endgroup$
Sep 21, 2020 at 19:23
Note: Originally I failed to mention the "complex" clarification to follow (and at bottom), hence the downvotes (which now are undue). The coefficients give amplitude and phase of a complex sinusoid. So instead of just summing real sinusoids, we're also summing imaginary (to a nonzero).
This terminology is also used ubiquitously in Wavelet Tour, with one line reading near-identical to mine (pg 26):
(1) - no. (2) - no. But not entirely no.
The truest meaning stems from the definition of forward and inverse transforms, but it won't directly answer all pertinent questions; latter is a matter of what said definitions imply. The formulation I find most intuitive stems from the inverse:
DFT coefficients describe the sinusoids that, when added, yield the original signal. -- In detail:
DFT coefficients, $X_k$, give amplitudes and phases of sinusoids at integer frequencies $k$, from $0$ to $N-1$, that sum to the original signal $x[n]$, comprised of $N$ points.
That's all. This is the one description that must hold no matter the context. (1) and (2) "turn out true" GIVEN certain criteria are met, but the coefficients themselves don't inherently warrant any of them.
Case 1: $f=1, 4,$ and $8$ adjacent, each lasting for 100 samples.
There are only three frequencies, so if the coefficients indeed describe "what frequencies are in a signal", what's with all these other frequencies?
"There are three peaks, one for each frequency; other values are due to sharp jumps between frequencies, insufficient samples for proper representation, and other imperfections."
Nonsense. There's nothing 'imperfect' about the coefficients; they simply don't directly answer for "which frequencies are in the signal". Instead, they give the amplitudes, phases, and frequencies of sinusoids that, when added, equal the original signal.
This is sometimes formulated as "Fourier Transform tells us which frequencies are in the signal, not when they occur". True, but it misses the point.
Case 2: $f=1$, 100 samples, with a 1 sample "dip".
What's with all the higher frequencies, even if they are relatively small? Surely this is noise, and not part of the 'actual' signal, and we should just pretend they're zero - right?
Wrong. These can very well be 100 different sources overlapping exactly as described by coefficient to produce this exact dip. It could also be noise. We don't know. Of course we can make rational assumptions about what's plausible, but this requires knowledge about the source system; how many sinusoidal sources are there, if any? What noise can we expect? The example above is trivial; if we know nothing else, it's almost certainly noise - but a real-world signal is far more intricate.
This addresses both (2) and (1). Not only "we don't know", but we can't know anything exactly the source system just by observing it (its "output"). It could be a magnetic pole spun at 1Hz, with an electrical shock inserted in the circuit at an instant. Or it could be 100 antennas synched just right. The end-result is identical, and it's the only thing the DFT operates on.
Case 3: $f=1$.
Now we know the source is a sinusoid of $f=1$, right? It has to be!
Nope. The source could very well be a bunch of triangle waves, square waves, a happy coincidence, or infinite other possibilities. But what if we know it's periodic? Even then: sinusoids are only one, not only, example of periodic orthogonal basis functions.
PS, the slight non-zero values in the coefficients in this case are due to 100 samples imperfectly representing an $f=1$ signal. It's also true in Case 1, but is far besides the point.
So when do the coefficients exactly represent the "frequencies in the signal", if ever?
Only one possibility; if the signal is:
In other words, if it does accurately describe (1), it only "happens to be the case" (i.e. coincidence). The more the source deviates from any of the six above, the less the coefficients meet (1) or (2).
If the DFT can't tell us anything about the source, why use it? -- Because most of the time we have some knowledge of the source, allowing us to assume some traits and deduce others (e.g. electric motors). Other times we don't care about the nature of the source, but only the signal and how we can manipulate it (e.g. recorded audio, power transmission).
What "is" the DFT? -- A transform. A mapping. An algorithm. Something that takes numbers, and returns other numbers, according to some rule. What it's not is a descriptor of the "true nature" of the signal.
Does DFT assume the input's periodicity? -- Nothing about the coefficients or the reconstructed signal change regardless what the signal is outside the portion that was transformed. The DFT describes only that portion, nothing else. The extension of the inverse, however, is periodic, and this becomes relevant in certain operations (e.g. below) - but again, no info on the original signal.
But DFT derivation from the Fourier Transform is only valid if input is periodic. -- The DFT neither requires nor assumes FT's existence; it is standalone. "From FT" is only one derivation, not sole. Where periodicity is relevant is when FT's properties are assumed to also apply to DFT.
In circular convolution, multiplying FT's coefficients exactly corresponds to time-domain convolution, but not DFT's; for DFT one must pad, which changes the coefficients. So in this sense, the interpretation of DFT coefficients changes with the periodicity assumption.
What about the meaning from the "forward transform" perspective? This is more about how we get the coefficients in the first place, and why they take on the values they take, which is its own topic. For start, it's better posed as a question:
Why does the forward transform yield the coefficients that describe the frequencies, amplitudes, and phases of sinusoids that sum to the (transformed) signal?
I defer to this excellent video and this text for exploring the answer.
NOTE: Answer uses real sinusoids to illustrate concepts for simplicity, which holds for real-valued inputs. However, this isn't the whole story, and may mislead, but we can apply the same concepts to the complete picture. The more complete definition adds one word:
DFT coefficients, $X_k$, give amplitudes and phases of complex sinusoids at integer frequencies $k$, from $0$ to $N-1$, that sum to the original signal $x[n]$, comprised of $N$ points.
For a real-valued input, due to symmetry of $X$'s imaginary components, the imaginary components of (coefficient-multiplied) complex sinusoids sum to zero. However, the imaginary component of the complex sinusoid (basis function) does not contribute zero; it contributes to the real component:
$$ (A + jB) e^{j\theta} = (A + jB) (C + jD) = (AC - BD) + j(AD + BC), \\ C = \cos{(\theta)},\ D = \sin({\theta}) $$
Thus, the real sinusoids used throughout the answer actually owe part to the imaginary component of the complex basis function, so it's not just summing the real component of the basis.
For a complex input, we're doing all the same summation, and can visualize it the same, except $(AD + BC)$ no longer ends up being zero.