Submitted via IRC for Bytram
The Math Trick Behind MP3s, JPEGs, and Homer Simpson's Face
Over a decade ago, I was sitting in a college math physics course and my professor spelt out an idea that kind of blew my mind. I think it isn't a stretch to say that this is one of the most widely applicable mathematical discoveries, with applications ranging from optics to quantum physics, radio astronomy, MP3 and JPEG compression, X-ray crystallography, voice recognition, and PET or MRI scans. This mathematical tool—named the Fourier transform, after 18th-century French physicist and mathematician Joseph Fourier—was even used by James Watson and Francis Crick to decode the double helix structure of DNA from the X-ray patterns produced by Rosalind Franklin. (Crick was an expert in Fourier transforms, and joked about writing a paper called, "Fourier Transforms for birdwatchers," to explain the math to Watson, an avid birder.)
You probably use a descendant of Fourier's idea every day, whether you're playing an MP3, viewing an image on the web, asking Siri a question, or tuning in to a radio station. (Fourier, by the way, was no slacker. In addition to his work in theoretical physics and math, he was also the first to discover the greenhouse effect.)
So what was Fourier's discovery, and why is it useful?
The story provides great visual examples of how even complex waves can be approximated by a series of sine waves summed together. Further, the parameters to the sine waves and a much more concise description of the approximated item. Examples are given of a roughly-square wave. Another example uses circles instead of sine waves. A great YouTube video shows these in action.
Wish I had this available to me before I was taught FT and FFT in college!
Related Stories
Hans Wennborg does a deep dive into the history and evolution of the Zip compression format and underlying algorithms in a blog post. While this lossless compression format became popular around three decades ago, it has its roots in the 1950s and 1970s. Notably, as a result of the "Arc Wars" of the 1980s, hitting BBS users hard, the Zip format was dedicated to the public domain from the start. The main work of the Zip format is performed through use of Lempel-Ziv compression (LZ77) and Huffman coding.
I have been curious about data compression and the Zip file format in particular for a long time. At some point I decided to address that by learning how it works and writing my own Zip program. The implementation turned into an exciting programming exercise; there is great pleasure to be had from creating a well oiled machine that takes data apart, jumbles its bits into a more efficient representation, and puts it all back together again. Hopefully it is interesting to read about too.
This article explains how the Zip file format and its compression scheme work in great detail: LZ77 compression, Huffman coding, Deflate and all. It tells some of the history, and provides a reasonably efficient example implementation written from scratch in C. The source code is available in hwzip-1.0.zip.
Previously:
Specially Crafted ZIP Files Used to Bypass Secure Email Gateways (2019)
Which Compression Format to Use for Archiving? (2019)
The Math Trick Behind MP3s, JPEGs, and Homer Simpson's Face (2019)
Ask Soylent: Internet-communication Archival System (2014)
(Score: 3, Insightful) by Anonymous Coward on Tuesday June 11 2019, @03:13PM (3 children)
Decomposition of signals into an infinite sum of sinusoids, this allow any signal of being quantized.
So instead of having to store the signal value at fixed interval (PCM), you get an approximation via sinus values (e.g.: 0.5*1kHz + 1*2kHz + 5*4kHz +...) for constant interval (CBR) or variable (VBR).
So it's a lossy format, but for most uses it's not really a problem.
While I'm here, why is it lossy?
Since it's an infinite sum to have the exact signal (barring special cases like having a signal as pure sinusoid), you have to have a cutoff level and this is going into numerical analysis with the remainder.
Math is love.
(Score: 3, Insightful) by bob_super on Tuesday June 11 2019, @04:58PM (1 child)
It's absolutely amazing how a phone will sample your voice, run transforms to find filter coefficients every few milliseconds, send those coefficient instead of the samples to save bandwidth, so that the receiving end applies those filters to pulse (or sine?) and noise to recreate your voice.
And you mom never realizes it's not actually your voice, but transformed noise.
Math is cool.
(Score: 4, Funny) by SomeGuy on Wednesday June 12 2019, @06:38AM
All that, and it still sounds like a robot trying to fuck my ear.
(Score: 5, Interesting) by bzipitidoo on Tuesday June 11 2019, @05:02PM
> While I'm here, why is it lossy?
The Fourier Transform Is not lossy. It wouldn't be a transform it if was. An example of a trivial transform is a simple change of units, like switching from inches to centimeters, or Fahrenheit to Celsius. A bit more involved is transforming from Cartesian coordinates (x and y distance) to polar coordinates (angle and radius).
What is inherently lossy is measurement. You talk as if PCM has no loss, and the sine waves can only be an approximation of the PCM. That is not so. The sine waves can contain exactly the same data as the PCM format. The inverse transform can take those sine waves and reproduce the data in PCM format, exactly as it was originally.
Where the loss in lossy compression enters is after the transform. The transform changes the data into a representation that is easier to work with. In the case of images, it's been noted that high frequency data is less likely to be missed. Lossy image and audio methods reduce the precision of those frequencies. For example, instead of storing any value between 0 and 255, which takes 8 bits, it could make do with values between 0 and 31 (multiplied by 8), which takes only 5 bits. Turns out, the precision can be reduced a great deal before quality is low enough that people begin to notice.
(Score: 3, Interesting) by ikanreed on Tuesday June 11 2019, @03:17PM (6 children)
Take classes literally any other kind of engineering besides the software kind. I remember when I was just out of college and still excited enough to almost finish all my side projects. And I wanted to make a visualization for a music player that did lightning strikes in time with the music, and did internet research and discovered forrier transforms.
I told my electrical engineer friend, and he'd learned all about them in undergrad signal processing, because it was incredibly basic stuff. Same with a mechanical engineer who'd learned it for analytics. Hell, there's algorithms I've learned from casual conversations with engineers that were more useful than a red-black tree ever will be. PID loops are hella useful.
(Score: 3, Interesting) by RS3 on Tuesday June 11 2019, @05:05PM (2 children)
You sound like a perfect candidate for an EE degree, but only if you can read. A reed won't help you. Unless you want to do a Fourier analysis of reed motion and the sound they produce.
Fourier transform is a special type of LaPlace transform. Those mathematicians figured this stuff out long before electronics. It's amazing how it all came together.
Fourier transform is a linear integration, and by definition is lossless, but would be very difficult to compute. An integration can be done computationally by a summation, (Greek capital Sigma), and becomes an approximation, only limited by how many data points you can reasonably sample and compute.
Signal analysis classes are often called: "discrete-time systems", which simply means that to calculate and process signals, we have to sample them- rather than infinitesimal time, it's defined discrete samples, so therefore Analog to Digital converters. Then we might do a discrete-time Fourier transform, which ends up being a somewhat recursive summation, do some processing, or display the results, for example: a spectral display- shows frequency components and their amplitudes.
The discrete-time Fourier transform (DFT) is horribly computationally intensive, so again the mathematicians figured out the FFT- Fast Fourier Transform, by doing linear and set algebra, finding redundancy in the calculations, and coming up with FFT computer algorithms which are used extensively every day. Again, you're a shoe-in!
Years ago I wrote some code to do DFT and it was stunningly slow. The FFT algorithm is a bit complicated, especially difficult to optimize, but over the many years it's been refined and widely available.
One way to do signal processing is to use FFT to convert a signal into frequency components, then do very simple math on them to increase some frequencies, decrease or totally cut some, then do an inverse FFT to get your now-modified signal back. For example an audio EQ (tone controls). However, signal processing with FFT and inverse FFT is computationally intensive, and even if a CPU can keep up, causes delays which are sometimes intolerable (because you have to accumulate samples before you can process). For that reason the mathematicians came up with FIR and IIR filters. I'll let you look that up if you're really that into self-hate! Then you can look up Butterworth, Chebyshev, Linkwitz-Reilly (spelling?), and other filter topologies.
And for you algorithm guys, look at DSP chips and "butterfly" https://en.wikipedia.org/wiki/Butterfly_diagram [wikipedia.org]
Oh, and sampling, Nyquist rate, and "windowing" (Hamm, Hanning, Blackman, triangle, rectangle...). If you like what you see, seriously look into some MSEE courses on signal processing. You'd need a couple of undergrad courses, but I think you'd excel.
If it's not obvious, it's what I mostly pursued in BS and MS EE courses. Of course, the job market wanted 3-5 years experience, so I did and do lots of other things, but knowing that stuff was foundational and comes in handy frequently.
(Score: 2) by ikanreed on Tuesday June 11 2019, @06:11PM (1 child)
Well, know, Hamm and Hanning I learned in advanced abstract algebra, which was a computer science class.
(Score: 2) by RS3 on Tuesday June 11 2019, @06:57PM
That's cool. Many of our EE classes were exactly the same as CompSci classes, like you could take EE421 or CompSci421. I never looked into the rest of the CompSci curriculum. It's good that they taught you that stuff- good practical real-world stuff. How many bubble-sorts can one person do in a lifetime!
(Score: 1) by Ethanol-fueled on Tuesday June 11 2019, @07:59PM
I was fortunate to get a textbook for a Signals and Systems class, for free from a friend. If there is any one textbook you want to grab for this, grab one of those. A single textbook not only covers transforms but also things like transfer functions of basic electronic circuits. I probably wouldn't qualify for such a class in that I have all the prerequisites, but the book makes perfect sense with a little knowledge of discrete math, complex numbers, and programming -- and after you read one you could probably do some basic DSP stuff and not have it all read like Chinese.
Hell, i still think finding the closed form to anything recursive is fucking awesome.
(Score: 2) by istartedi on Tuesday June 11 2019, @11:53PM (1 child)
I have a BSEE, and those courses were hard, but not as hard for me as differential equations or statistics. YMMV based on what gives your brain trouble. I absolutely crushed digital logic, and others struggled with that and not diff eq. Go figure. Pun intended.
Appended to the end of comments you post. Max: 120 chars.
(Score: 0) by Anonymous Coward on Wednesday June 12 2019, @07:30AM
I excelled at puns - and that, Sir, was not a pun. Intended.
(Score: 3, Informative) by Anonymous Coward on Tuesday June 11 2019, @03:28PM (2 children)
This is a great visualization: http://bgrawi.com/Fourier-Visualizations/ [bgrawi.com]
And if you want to roll up your sleeves and see another great visualization: https://www.youtube.com/watch?v=spUNpyF58BY [youtube.com]
(basically, that YT site is great for ANY kind of mathematical visualizations)
(Score: 4, Interesting) by AthanasiusKircher on Tuesday June 11 2019, @04:14PM (1 child)
Agreed. For those who haven't explored 3Blue1Brown's math channel [youtube.com] on YouTube, it has some of the best visualizations for a lot of lower-level college math concepts, combined with explanations that try to develop intuition of rather complicated math concepts (often by geometrical arguments and visualizations).
Digression: I love most of his videos on basic stuff, like intro calculus. My one very minor criticism is with more advanced topics, there is often an odd combination of handwaving through some really complicated ideas while simultaneously explaining really basic stuff unnecessarily. Take the Fourier Transform video parent linked, for example: 3Blue1Brown spends a bit of time trying to justify/explain wrapping a sine/cosine wave around the origin as some sort of visual metaphor. Except anyone with even a really, really basic sense of polar coordinates (and graphs of sine/cosine functions with varying frequencies in them) would know immediately where those graph shapes are coming from, why they end up creating a cardioid as the time interval of graphing lines up with the wave frequency, etc. Probably a 3-minute primer on polar coordinate graphing as part of that 21-minute video would have been more effective than some handwaving vagueness about wrapping waves around the origin and being mystified as the "center of mass" lines up when the waves are graphed in a certain way.
And yeah, the "center of mass" thing is then really handwaved over. We ignore basic polar coordinates, instead taking an excessive amount of time to explore properties that would be apparent to anyone who has spent 10 minutes graphing sines and cosines in polar coordinates, but then he introduces this "center of mass" thing with basically no explanation. What does "center of mass" mean for that wave? How is it calculated? Later, suddenly an integral appears, and then we're told that has something to do with center of mass... and again, a 30-second digression on how integration is used in physics to determine center of mass would have made it feel like an actual explanation. Same thing when Euler's formula stuff and complex coordinates are thrown in -- at least in that case he could point to a prior video he made on how that stuff works.
Again, these are relatively minor criticisms. I just am sometimes a little frustrated about how the author of that channel can be so good at explaining more basic concepts step-by-step, so you could actually show them to (say) an intro calc class, and they'd get a lot out of it. But the more advanced videos often skip over steps at precisely the most complex parts of the explanation. If I showed the Fourier video to a similar class, they'd wonder why he was wasting time because he doesn't assume knowledge of basic precalc concepts like polar coordinates and the complex plane, but then skips over several steps and suddenly throws in more advanced or borrowed concepts.
(Score: 2) by AthanasiusKircher on Tuesday June 11 2019, @04:18PM
Sorry -- all that said, it is truly an awesome video, with a much more detailed explanation of the math of Fourier transforms than TFA. So do watch it if you're interested in this stuff. (I didn't mean to be overly critical.)