0
$\begingroup$

What "are" they? What's a sensible way to interpret the coefficients (and what isn't)? To pose specifics:

  1. DFT coefficients describe the frequencies present in a signal
  2. They describe the sinusoidal frequencies of the source

Are either of the above true?

$\endgroup$
  • 2
    $\begingroup$ I provided a linear algebraic interpretation in this answer to a related question. $\endgroup$ – Joe Mack Sep 17 at 23:05
  • 1
    $\begingroup$ Perhaps you will find this a more tangible physical interpretation for real valued signals: dsprelated.com/showarticle/768.php $\endgroup$ – Cedron Dawg Sep 18 at 1:55
  • 1
    $\begingroup$ Whether you want to skim, read, or study them doesn't matter much to anyone but yourself. They are there, available, and will remain so. The interpretation given in the article doesn't really apply to the inverse very well even though they are mathematically equivalent (sans the normalization). Every bin is at a Root of Unity by definition, it is inherent. The article makes it explicit. Nearly all my articles are novel. FYI, none of the down votes are mine, and I would strongly advise you to stop trying to use your voting power as a control tool. $\endgroup$ – Cedron Dawg Sep 18 at 13:46
  • 1
    $\begingroup$ @CedronDawg What 'control tool'? I didn't ask for any changes. Don't see what's with your accusations lately $\endgroup$ – OverLordGoldDragon Sep 18 at 14:27
  • 1
    $\begingroup$ I didn't see the latter comments below until after my comments. Nothing I have said is meant to be an "accusation". However, since you brought the word up, I also think styling your online persona on "The Accuser" is also a bad idea. Friendly advice. $\endgroup$ – Cedron Dawg Sep 18 at 14:37
1
$\begingroup$

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}$$

| improve this answer | |
$\endgroup$
  • $\begingroup$ This neither explains anything nor addresses (1) or (2) $\endgroup$ – OverLordGoldDragon Sep 18 at 12:38
  • 2
    $\begingroup$ $X[k]$ are the coefficients to each basis function in the linear summation. That's all that they are. Nothing else. The periodicity is obvious because each basis function is periodic with period $N$ so then any sum of the basis functions are also periodic with the same period. $\endgroup$ – robert bristow-johnson Sep 18 at 17:42
  • 2
    $\begingroup$ Perhaps one thing you might be missing is assigning the effect of windowing to the DFT. It's not the DFT that is windowing your data. It's the windowing that you do to the data before it is passed to the DFT. What the DFT does, by fitting those $N$ data values to the DFT basis functions (all of which are periodic with period $N$), is periodically extends the $N$ samples passed to the DFT. It always does that and it is inherent to the DFT. $\endgroup$ – robert bristow-johnson Sep 18 at 17:47
  • $\begingroup$ Perhaps the purpose of the Q&A isn't entirely clear; I sought to clear up some misconceptions about the coefficients. I thought I already had an answer - and I pretty much do for the real-valued input case, but since that's only a special case, it doesn't count, as my goal's to explain things at the fundamental level. I now seek the same level of intuition for the complex case, and I'll get there with time invested and may update my answer later. $\endgroup$ – OverLordGoldDragon Sep 18 at 21:34
  • 1
    $\begingroup$ Well, I can't always discern nor account for what is or is not "entirely clear" to someone else. I have once asked and answered a question myself (because I was spoiling for a fight). It doesn't always get perceived the way it was intended. But I spelled out, strictly speaking, what the DFT coefficients are about. They the weighting coefficients for a set of basis functions that are "sinusoidal". $\endgroup$ – robert bristow-johnson Sep 19 at 2:10
0
$\begingroup$

Update: In my previous version of this answer I was caught up on the expression $e^{j\omega t}$ can't be called "sinusoidal", (and can now interestingly start to see two sides of how it could be or it can't be thanks to RBJ's comments; depending on the definition, of which I can't find a consistent source for). I considered then asking as a separate question on that topic specifically, but now sense it may not be answerable-- if anyone thinks otherwise please comment and I will create the question for the clear answer. Otherwise I have moved my thoughts on that to the bottom to not detract from this answer. And regardless of the above I do appreciate the clarity of referring to $e^{j\omega t}$ as a "complex sinusoid" and take no issue with that.

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.

2 pt IDFT

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.

IDFT for j 1


Sidetrack (and perhaps to be posted as another question if a clear and non-trivial answer exists):

Is $e^{j\omega t}$ sinusoidal?

I have always considered it to NOT be sinusoidal, limiting my view of sinusoidal as representing a sine wave, and noting the the magnitude of $e^{j\omega t}$ is constant versus time, and consists of two sinusoids in quadrature relationship. RBJ protested in the comments, and threw some math at me which led me to consider otherwise- but still curious if this is generally settled or an item of debate having not yet found a clear and generally accepted definition of "sinusoidal"- does that exist?

For instance Wolfram defines sinusoid as a curve taking on the shape of the sine wave, specifically of the form:

$$f(x) = a\sin(\omega x + c) \label{1} \tag{1}$$

https://mathworld.wolfram.com/Sinusoid.html

Supporting my initial argument (or so I thought).

However, as RBJ pointed out the general relationship of $A\cos(\theta) + B\sin(\theta)$ as given below allows $A$ and $B$ to be complex:

$$A\cos(\theta) + B\sin(\theta) = \sqrt{A^2+B^2}\cos(\theta + \gamma) \label{2} \tag{2}$$

with $\gamma = \arg(A-jB)$

When $B = jA$ the above will result in:

$$A\cos(\theta) + jA\sin(\theta) = Ae^{j\theta}$$

however, using the summation relationship above results in $0$:

$$ = \sqrt{A^2 - A^2}\cos(\theta + \arg(2A))$$

So I was ready to conclude that $\ref{1}$ and $\ref{2}$ settled it for me, given that the two forms are sufficiently similar or can be made so with a simple phase added, but as I subsequently show the relationship doesn't support the case of $e^{j\theta}$ (resulting in zero unless I made a simple error).

[If we make $B = -jA$ we can proceed with a solution for $e^{-j\theta}$, but I would like to resolve the case above as well]

(I asked this question here: https://math.stackexchange.com/questions/3836769/a-cos-theta-b-sin-theta-for-complex-a-b)


Further derivation of $A\cos(\theta) + B\sin(\theta)$ to understand what occurs when $A$ and $B$ are not real:

$$A\cos(\theta) + B\sin(\theta)$$

$$= \frac{A}{2}e^{j\theta} + \frac{A}{2}e^{-j\theta} + \frac{B}{2j}e^{j\theta} - \frac{B}{2j}e^{-j\theta}$$ $$= \frac{A}{2}e^{j\theta} + \frac{A}{2}e^{-j\theta} - \frac{jB}{2}e^{j\theta} + \frac{jB}{2}e^{-j\theta}$$

At this point the geometry from the graphical depiction of this reveals the solution which is simplified to this when A an B are real, resulting in a real result of a single sine wave with a phase shift:

A cos (theta)  + B sin (theta)

Resulting in the known identity:

$$A\cos(\theta) + B\sin(\theta) = \sqrt{A^2+B^2}\cos(\theta - \gamma)$$

Where $\gamma = \tan^{-1}(B/A)$

Which is clearly a sinusoidal function. But consider what happens when $A$ is real and $B$ is imaginary, this will result in $jB$ to be real, aligning with one of the phasors additively and subtracting from the other:

A real B imaginary

Which is $$\frac{A+jB}{2}\cos(\theta) - jBe^{j\theta}$$

My question is if this result is considered sinusoidal, and if so what definition of sinusoid is used?

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ A complex exponential's real and imaginary parts are sinusoids, which is what I meant, and can clarify explicitly if needed. $\endgroup$ – OverLordGoldDragon Sep 18 at 12:39
  • 1
    $\begingroup$ yeah an important point, and that signals can be complex (so not sinusoids at all!) $\endgroup$ – Dan Boschen Sep 18 at 12:40
  • 1
    $\begingroup$ Completely agreed about the text, and I'm cautious with it, but that one key idea slipped my mind entirely as I became overly focused on real-valued inputs. And, nothing in particular to edit, just Stack Exchange won't allow me to change the vote unless an edit is made - so can insert a space or something. $\endgroup$ – OverLordGoldDragon Sep 18 at 13:40
  • 1
    $\begingroup$ @robertbristow-johnson and I am kind of bummed that Ced and BobK don't respect me :( $\endgroup$ – Dan Boschen Sep 21 at 18:18
  • 1
    $\begingroup$ @DanBoschen it's not just the $\arctan\left(\frac{-B}{A} \right)$. that is good only for $A>0$. there is that quadrant problem and you need that 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$ – robert bristow-johnson Sep 21 at 19:23
-1
$\begingroup$

UPDATE: I didn't screw up anything. 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), and my explanation remains useful. There might be a prettier, richer explanation, but everything I describe in my answer still applies.

Downvoters have nothing.


(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:

  1. Comprised of sinusoids ...
  2. of the exact frequencies ...
  3. at the exact amplitudes ...
  4. at the exact phases that are given by the coefficients, ...
  5. each lasting over the entirety of the transformed signal, ...
  6. and nothing else.

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.

| improve this answer | |
$\endgroup$

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.