But how can it fit so much music? (The FLAC Codec #2 – Lossless Audio Compression)

UPDATE: Martijn van Beurden, one of the two authors of the IETF FLAC spec, has left a comment with some corrections and additional explanations! The comment is pinned below.

Episode 2 of the deep-dive series into FLAC, digital audio and its lossless compression. This video deals with the ideas and theory behind FLAC’s compression methods, including Linear Predictive Coding, Exponential Golomb Coding and Interchannel Decorrelation.

Chapters:
00:00 - Previously...
01:43 - Audio compression basics
03:16 - Excursion 1: Polynomials
04:13 - Linear Predictive Coding
09:02 - Excursion 2: Why these specific predictors?
11:40 - Excursion 2: A more formal method
15:54 - Linear Predictive Coding: Final remarks
17:20 - Residuals
19:55 - Residuals: Variable bit depth
22:36 - Residuals: Arbitrary order Exponential Golomb Coding
25:25 - Residuals: Extension to whole numbers
26:09 - Interchannel Decorrelation
27:26 - Ending

Footnotes (square brackets in the video):
[1] It’s more complicated than that. MP3 transforms the samples into the frequency domain using an FFT called MDCT (Modified Discrete Cosine Transform) and then splits those up into subbands which are quantized and reduced in resolution, throwing away information. Also, there’s additional steps before and after the FFT.
[3] This is of course a simplification, not all functions can be approximated well with Taylor series polynomials. However, there is a way of proving or disproving that the Taylor series converges to the original function, which means the infinite Taylor “polynomial” is exactly equal to the approximated function.
[4] Fun fact: Computers use these exact formulas for calculating sine and cosine.
[5] This way of writing series might seem weird to the math-inclined, but it’s how signals in digital signal processing theory are sometimes notated. You might also see regular function notation (that’s what my German textbook does), but I don’t use it here to emphasize the fact that we’re in discrete signal land instead of continuous function land.
[8] In case you’re wondering: There’s also the regular Golomb code. Instead of 2^k as a parameter it uses any integer parameter M, and it’s just quotient*factor + remainder encoding where the quotient is M. By framing it this way, Exponential Golomb is both a special case of Elias gamma coding and Golomb coding.
A general note about the LPC coefficient derivation section: I’m skipping over a significant amount of formalism, as the distance between samples is technically a constant h. However, as mentioned in the end of the geometric motivation, in our approximations we assume h=1 which makes all the h-related factors disappear. Therefore, I elected to leave them out entirely in order to simplify the equations.
Another general note about the whole video: I’m leaving out a lot of the concrete implementation considerations, so if you are already thinking hard about how on earth some of these things can work together, it will probably be addressed in the third video.

[ktmf]

Thanks for making an educational video on FLAC :)

I hope this is not too blunt, but I'd like to point out a few problems in it :(

1) FLAC does not actually use Exp-Golomb coding, it works with Rice coding. The idea is similar, but it is ideal for a different distribution of residuals. Rice coding is actually simpler. To convert the residual samples to Rice symbols, we take a certain Rice parameter (I'll not discuss how to find the optimal parameter) and split the number according to it.

If we need to store the number 9 (1001 in binary) with Rice parameter 3, we split that binary number in a most significant part (1) and a least significant part (001). The Rice parameter determines how many bits go into the least significant part. The 1 is stored unary (so becomes 01) and the rest is stored directly. A decoder can parse this, because the unary part is self-terminating, and the number of bits that follow the unary number is known. The number 7 (111) becomes the symbol 1111 (unary 1, binary 111), the number 34 (100010) becomes

So, instead of a 3-part code, we only have a 2-part code.

2) At 15:11 you remark that higher order polynomials take more time to compute and more warm-up samples, but this is often not the reason lower order fixed predictors are used. The problem is that all derivations you do up to that point assume a stationary signal, but this is often not the case. The high coefficients used in higher order predictors make them increasingly sensitive to noise. This often results in the noise getting 'amplified', and the residual getting larger instead of smaller when compared with a smaller order predictor.


For example, to derive the third order fixed predictor, it makes sense to start from the last known sample, the last known first order discrete derivative and the last known second order discrete derivative. We add these three together. The last known sample is s[n-1]. The last known first order discrete derivative is s[n-1] - s[n-2], i.e. the difference between the last two samples. The last known second order discrete derivative is ((s[n-1] - s[n-2]) - (s[n-2] - s[n-3])), i.e. the difference between the last two first order discrete derivatives. If we put that all together we get 3*s[n-1] - 3*s[n-2] + s[n-3]. So, I don't know where the factorials went, but just trying to explain this without using a Taylor expansion seems to work fine.

I hope this helps you :)

[artanisax]

Holy what a fantastic elaboration and wanting ep. 3 desperately (it has been a year :<)

[PaulAup]

Incredible series. I am NOT a math person but i found the whole thing incredibly interesting. Cant wait for part 3 if that ever comes out!

Very very good work.

[mylegalname]

Here from the comments on the QOI video. Really glad I read the comments over there! This video is great.

[xDnator]

Crazy quality video! I was shocked seeing you only have 1000 subs

[jayapayax]

Great content! I hope you can upload part 3 soon.

[Live-wstl]

Thanks for the overview! I'm looking forward to the final video and also something about how to write a codec for it

[ianbolfa]

Great content. Also I loved the animations and the editing.

[kleinesfilmroellchen]

Source code is now available! Link in the description.

[kulikgabor]

Thank you for all the insights! I don't quite understand the mid side part of the video. If the left and the right samples are 16 bit integers, the sum will fit only into 32 bit integer which is big. If I divide them by 2 that will fit but the result gets rounded like if the left is 0 and the right is 1 the result would be 0 just like if they were both 0. How could I do this properly and take advantage on the side part being very small and keep the mid part small as well?

[AlvaroALorite]

21:23 "all numbers in binary begin in 1"not entirely true; that's always true only in the case that those are "positive non-zero integer (natural) numbers" AND they are stored as *big endian*, right? You sort of imply it later, but I feel like it should be clarified :)

[volkerjung]

Hi, Filmröllchen, ich habe mit großen Erwartungen Dein Video angesehen und bin gleichzeitig hocherfreut und andererseits aber auch ziemlich deprimiert. Der Grund: Vielleicht bin ich doof. Ich verstehs nämlich nicht wirklich. Ich habe das Thema seit 20 Jahren auf dem Schirm, steige aber nicht WIRKLICH dahinter. Ich habe in all der Zeit keine Ressource gefunden, die es so erklärt, daß mans verstehen MUSS. Du bist tatsächlich wohl am nähesten dran - aber es fehlen in meinen Augen viele, viele Details und eine Einordnung in übergeordnete Konzepte. Wenn man sich mit LAC beschäftigt, landet man schnell bei "linear predictive coding" und da wird dann immer was von Filtern erzählt, die mit irgendeiner obskuren Levensin-Durbon-Rekursion berechnet werden - und so weiter.

Was man aber definitiv NIE findet, ist irgendwer, der die Sache mal exakt so darstellt, daß mann schon unterirdisch dumm sein muß, um nicht zu kapieren, wie der Hase läuft. Unterirdisch dumm bin ich nicht, nur normal dumm. Kurz: Du ordnest das Verfahren leider in keiner Weise ein und erklärst nicht, wie sich das in die Mathematik allgemein einbettet und wie es zu anderen Erklärungen wenigstens ansatzweise kompatibel ist.

Vielleicht können wir und darüber etwas austauschen...

Als Dein Video losging, dachte ich: Hey, endlich erklärts mir mal einer wirklich, wie der Quark funktioniert.Dann kamen die Polynome, die sich durch Punkte schlängelten und irgendwie sah das alles ziemlich vielversprechend aus. Dann die Erklärung mit dem "trivialen" Fall der Differenzbildung, also Prädiktor Order 2, grafisch gut ausgearbeitet.

Und dann machst Du leider den Fehler, den nahezu alle Erklärer machen: Das "triviale" Beispiel wird erschöpfend behandelt, obwohl es doch TRIVIAL ist. Anschließend gehts ans Eingemachte und DAS wird dann nicht mehr ins Detail zerlegt? Da wird dann nichts mehr GEZEIGT? Sollte man nicht wenigstens den Prädiktoren 3. und 4. Ordnung mal bei der Arbeit ZUSCHAUEN können?

Ich kapiere nicht im Ansatz, was mir diese Koeffizienten nützen. In der Wikipedia steht zum Beispiel, das Audiosignal würde bei Flac in Blöcke zerlegt und zu denen würden dann irgendwelche Filterkoeffizienten berechnet werden, Du hingegen sagst, es wäre ne doofe Idee, längere Passagen prädiktieren zu wollen...

Kurz und gut: Ich bin nach wie vor verloren in mmehr oder minder nur anreißenden Erklärungen, die die Sache nicht vollständig darlegen, so, daß es UNMÖGLICH ist, es nicht zu verstehen.

Vielleicht können wir darüber mal reden und vielleicht können wir zusammen an ner tiefgreifenderen Erklärung arbeiten, die wirklich der Dümmste noch schnallen muß?

Deine Erklärung hat mir mehr gesagt als jede zuvor - ein paar sehr entscheidende Details bleiben aber im Dunklen, mutmaßlich, weil sie für Dich quasi "trivial" sind, dummerweise nicht für den, der eben nicht in der Tiefe der Materie steckt und noch dazu von anderen Pseudoerklärungen quasi schon versaut wurde.

Auch dieses Weglassen der Nenner hab ich nicht kapiert - da rechne ich mir was aus und schmeiß die Nenner einfach weg und das SCHADET mir nicht? Vielleicht tut es das ja wirklich nicht... Aber WARUM? Ob ein Wert 6 mal größer ist oder nicht, erscheint mir jetzt nicht vollkommen irrelevant, es sei denn, er wäre sowieso so winzig, daß man sich ihn auch gleich schenken könnte.

Ich biete Dir an, das perfekte Opfer fürs Finden der perfekten Erklärung zu sein - vielleicht würdest Du das ja gut finden, zumal ja Teil 3 sowieso aussteht...

DANKE auf jeden Fall dafür, daß Du mich etwas tiefer an die Sache herangeführt hast!

Besten Gruß,
Volker