Why do people say that the fast Fourier transform (FFT) “views”, or “interprets”, or “assumes” its input sequence is periodic? I ask this question because the activities of viewing, interpreting, and assuming can only be performed by a living creature with a brain.
$\begingroup$
$\endgroup$
4
-
$\begingroup$ Probably slight projecting. Performing an FFT might be considered an extension to one's self, so personal attributes may sneak in. Or maybe it makes it less impersonal when explaining it to someone and, thus, the meaning becomes "you can't view or interpret, etc, because..". Just a guess. $\endgroup$– a concerned citizenApr 25, 2021 at 22:32
-
1$\begingroup$ Take a look at this answer to the same question. It's because the FFT is just a fast or optimized method to compute the DFT. And the DFT is precisely the same math as the DFS, the Discrete Fourier Series. And Fourier Series is about periodic functions. $\endgroup$– robert bristow-johnsonApr 26, 2021 at 1:36
-
$\begingroup$ At risk of engaging in a semantic debate, what it means to me when I’m thinking it in my head is that the DFT and IDFT are periodic when evaluated outside the range 0 -> N-1. Anything beyond that and I usually have an application in mind with additional context. I have a hard time seeing what all the fuss is about. $\endgroup$– Dan SzaboApr 27, 2021 at 17:42
-
$\begingroup$ There's also... $\endgroup$– OverLordGoldDragonApr 26 at 13:46
Add a comment
|
5 Answers
$\begingroup$
$\endgroup$
3
It's not the DFT/FFT algorithm "who" views (or "assumes", or "interprets") it's input being periodic, rather it's the "mathematician's mindset" that assumed periodic signals at the input of the algorithm, and designed the algorithm that way.
It's exactly on par with saying that "Newton's laws assume that space & time are absolute..."; laws of mechanics do not have a "brain" to assume such a thing, rather Newton himself made that assumption that the time & space were absolute, and then formulated his laws accordingly, which compute dynamical quantities based on that assumption.
Today we know (believe) that those assumptions are not valid (Special Relativity), yet if you use Newton's laws to compute high-speed phenomena, you may end up objects having speeds larger than speed of light; this inconsistency is due to fact that the "assumptions of the law" are not validated. Here the assumptions are reflected into the mathematical structure of the formulation of the law.
Moving to DSP; in essence, Discrete Fourier Transform (DFT) is by definition one period of the Discrete Fourier Series (DFS); and very naturally DFS works with periodic sequences. I don't know who defined it that way, but it's the case.
So, you cannot compute the DFS of a single rectangular pulse, for example. If you try to find the DFS/DFT coefficients of such a nonperiodic pulse, internally, the mathematical algorithm treats it as if it were periodically extended, and computes the coefficients that way; by fitting periodic sine waves to the periodically extending waveform. Then, when you want to synthesize back the input waveform with the given DFT/DFS coefficients, and evaluating the formula for all n, then you will get not a single pulse but a periodic extension of that pulse. So the zeros outside of the pulse duration are not naturally generated by the inverse DFS/DFT (synthesis) formula.
You must externally force your output to be zero for those out of duration samples. And that's typically what's done with the DFT block length definition.
-
1$\begingroup$ Re: "I don't know who defined it that way..." That would be the "F" in DFT, FFT and any FT, Joseph Fourier. $\endgroup$ Apr 26, 2021 at 13:14
-
$\begingroup$ @RBarryYoung Thank you, I understand that you're referring to the periodicity of the input being defined by J.Fourier, but when I said I don't know who defined it that way..., I was referring to the definition: "DFT is by definition one period of DFS" (previous line), and I wanted to say I didn't know who defined it so, and (afaik) it's not J.Fourier who defined DFT as one period of DFS... Anyway thanks again ;-)) $\endgroup$– Fat32Apr 26, 2021 at 23:14
-
$\begingroup$ @Fat32, it's not who "defined" the DFT to be the DFS, it's who identified the DFT as the DFS. if you have two objects A and B, if all of the elements of Object A are identical to the elements of Object B and vise versa, then Object A and Object B are identical. they might even be different labels for the very same single object. $\endgroup$ Apr 27, 2021 at 4:28
$\begingroup$
$\endgroup$
6
Most objectively, it depends on how we view it. There's those who insist on viewing the Discrete Fourier Transform as a "special case" of the continuous Fourier Transform - and interpret all input/output behavior in terms of continuous FT "with a brickwall". Then there's those who view it as a standalone transform that operates on finite observations - a tool to directly "communicate" with reality. I go deeper here and here.
I'm in the latter camp; I've learned much since writing these Q&A's, and haven't budged a bit. Continuous FT is useful for predicting certain DFT behaviors, but also enables flaws in not only mathematical but physical reasoning if one's not careful.
The one and only thing that DFT "assumes", without dispute, is that the input is finite (in length and values). Nothing else is required for it to produce valid results.
answered Apr 25, 2021 at 23:19
-
2$\begingroup$ You wrote, "Nothing else is required for it to produce valid results." Well said! I completely agree with you. $\endgroup$ Apr 26, 2021 at 9:34
-
$\begingroup$ "Nothing else is required for it to produce valid results." --- $$ $$ it's a falsehood. the DFT is not just any old one-to-one transform. it's a one-to-one transform in which the basis functions are all periodic with period $N$. $\endgroup$ Apr 27, 2021 at 4:31
-
$\begingroup$ Hi Robert. I believe OverLordGoldDragon’s comment, “Nothing else is required for it to produce valid results” was referring to the DFT’s input sequence and not to the DFT’s basis functions. I believe he was saying the only restrictions on DFT input sequences are that (1) the input sample values must be finite in amplitude and (2) finite in length. Thus any input sequence that meets those two restrictions can be applied to the DFT algorithm to produce valid spectral results. $\endgroup$ Apr 27, 2021 at 11:09
-
$\begingroup$ @robertbristow-johnson They're periodic in extension, yes. But that's an imposition; the algorithm itself does not demand it be extended. Nor is it extended in much practice, which'd be akin to claiming the DFT of N points describes something beyond those N points. There's nice mathematics for describing what happens if we do extend, but it doesn't change these facts. $\endgroup$ Apr 27, 2021 at 14:23
-
$\begingroup$ //" I believe he was saying the only restrictions on DFT input sequences are that (1) the input sample values must be finite in amplitude and (2) finite in length"// Yes, but @RichardLyons, the claim //"Nothing else is required for it to produce valid results."// is still wrong. This will go exactly the same way as the fights we had on comp.dsp about it, even a quarter century later. $\endgroup$ Apr 27, 2021 at 14:48
$\begingroup$
$\endgroup$
12
I thank everyone for their comments and Answers. And the links given herein are very interesting. I confess that I did not word my question as well as I should have. I wasn’t asking why people believe that DFT input sequences were periodic. I was asking why people insist on personifying the DFT algorithm. (Personification: the act of giving human characteristics to animals or objects.)
I believe that it is incorrect to write that the DFT views, or interprets, or assumes anything because the DFT cannot perform mental activities. (Square root algorithms don't pass judgement, trigonometric algorithms don't form opinions, and the DFT algorithm does not make assumptions.)
-
1$\begingroup$ That's fair, but I take it's commonly understood as just a shorthand in speech, like "
fit()assumes input is array, not list" in place of "the authors offit()intend for the input to be an array, not list". $\endgroup$ Apr 26, 2021 at 12:09 -
$\begingroup$ @OverLordGoldDragon. Your example of personification is not too objectionable. But the personification when saying “the DFT assumes its input sequence is periodic” is quite misleading because it’s impossible to compute the N-point DFT of a periodic sequence. (Periodic sequences are, by definition, infinite in length.) $\endgroup$ Apr 26, 2021 at 17:31
-
$\begingroup$ Exactly, there's also that. The "continuist's" idea is, DFT captures a full period of the continuous-time spectrum, which repeats the period infinitely (if input also repeats infinitely), so we don't have to operate on the full infinite input. While true, inserts much optional context, and can mislead. $\endgroup$ Apr 26, 2021 at 17:53
-
$\begingroup$ First, this question probably belongs in English.stackexchange.com, not here. Secondly, if you did ask there, I believe that you would discover that this is both entirely valid English and an entirely valid way to use the verb To Assume. $\endgroup$ Apr 26, 2021 at 21:04
-
1$\begingroup$ @OverLordGoldDragon : " DFT captures a full period of the continuous-time spectrum," $$ $$ no, it doesn't. the DFT "captures" a full period of discrete-time data. the regular-old Fourier Series works on a full period of continuous-time signal. $\endgroup$ Apr 27, 2021 at 4:40
$\begingroup$
$\endgroup$
Guilty as charged, as I just recently used this sub=optimal phrasing in an answer (which probably triggered the question). :-)
I was asking why people insist on personifying the DFT algorithm.
In my case it was just sloppiness/laziness. Many beginners are not aware of the underlying periodicity and it's implications. It's a very common misconception but it's awkward to write "You are using an FFT. This a specific algorithm to implement the Discrete Fourier Transform which is applicable only to discrete signals. That means your signal is assumed to be discrete in both the time and frequency domain, which in turns means it's also periodic both domains".
$\begingroup$
$\endgroup$
0
I probably am guilty too of using this poor wording. I do think it provides great intuition to realize that the DFT like the Fourier Series Expansion will provide the same result for non-zero values if the waveform is finite or periodic, repeating over the original time interval of interest. A fundamental difference is when the axis extends to infinity in one domain, it will be continuous in the other. So for the case of a periodic discrete time sequence with time that extends to infinity, the frequency axis will be continuous, although having a value zero for all values except at harmonics of the repetition rate in time which can have non-zero values for magnitude and phase. When the discrete sequence only extends for a finite time, as input to the DFT, the results are discrete in frequency and only exist at the harmonics of the duration of the time domain waveform.
So agreed, the DFT doesn't assume anything! The result of the DFT is consistent with the result we would get for the Fourier Transform of a periodic waveform, yes. I concur that concise and accurate wording is important, so thanks Richard for calling us out on that!
answered Apr 27, 2021 at 0:23