Understanding the FFT Algorithm (2013) | Hacker News Reader

Understanding the FFT Algorithm (2013)

jakevdp.github.io

For anyone interested and with 30 minutes to spare, I would recommend the youtube video [1] by Reducible for an intuition on how FFT works.

[1]: https://youtu.be/h7apO7q16V0

If anyone is interested, I made a video about my favorite application of the 2D discrete Fourier transform, where it's used to erase rainbows on manga screen tones on color eink Kaleido 3 on Kobo Colour: https://youtu.be/Dw2HTJCGMhw?si=hlhwHv0qB6SoMha9

“Understanding X” with 3-story high equations don’t always go hand in hand

You softened your statement with 'not always' to which I would add, that different people might be looking for different levels of 'understanding' ;)

Where are these ‘3-story high’ equations you speak of? The most work I see in the article is 3 lines long.

A bit of a stretch, but does anyone have a good way of running an FFT on a pcap?

You mean like converting packet timestamps into a (uniformly) sampled time series (e.g., bytes or packets per ms) and run a NumPy/SciPy FFT on that series?

Something like Lomb–Scargle would possibly be a better fit I suppose. But yes that sort of flow, I could do it as a one off with a Python script as you state, but my interest is more if anyone has sunk their teeth into network packet analysis in the frequency domain from the ground up and wrapped up all the learnings into a thoughtfully designed interface.

I was searching for a Wireshark type plugin to do this but I couldn’t find anything.

Alternatively, equally useful would be learning about anyone who has started to do something like this and then realized that it didn’t actually help them analyze anything.

Jake VanderPlas also has an article on Understanding the Lomb-Scargle Periodogram [1] which I can recommend if you want to get into the details (it also includes a treatment of fourier-pairs + convolution to explain the 'artifacts' in DFT). There's a module for it in scipy, so it should be rather straightforward to try your analysis using timestamps for x and an array of ones for y. That algorithm is essentially a least-squares fit with sinusoids at pre-selected frequencies.

I've tried to use Lomb-Scargle to reduce the number of sampling points in magnetic resonance experiments, but had another dimension to take into account (similar to doing the analysis for each network port separately in your case). I got some spikes on some of the 'ports' which I couldn't reason about or reproduce when I did the same with periodic sampling and FFT. But the individual periodograms looked reasonable, if I remember correctly. Maybe we have a more regular user of LS around, who can point out common pitfalls. Otherwise you could generate some data from known frequencies to see what kind of artifacts you get.

You could maybe also take a look at the auto-correlation of the packet timestamps to see whether you can extract timescales on which patterns arise.

[1]: https://iopscience.iop.org/article/10.3847/1538-4365/aab766

> Understanding the Lomb-Scargle Periodogram [1]

Thank you, this points me at a solution to a different problem I have.

Who uses square brackets for big-O?

Reply on news.ycombinator.com