CC 2.srt

1
00:00:00,080 --> 00:00:05,779
Hello and welcome, dear viewer, to the second
video in the three-part FLAC series.

2
00:00:05,779 --> 00:00:11,880
Today, I’m actually concerning myself with
what makes FLAC tick, and how it does its

3
00:00:11,880 --> 00:00:12,980
compression.

4
00:00:12,980 --> 00:00:18,270
Note that the first video, you can watch that
up here, was just an introduction to digital

5
00:00:18,270 --> 00:00:26,710
audio, so if you haven’t seen it and you
know all of these terms, you should be good.

6
00:00:26,710 --> 00:00:32,430
Last time, we saw how we can take a sound
wave and represent it literally with numbers,

7
00:00:32,430 --> 00:00:35,450
which is called Pulse Code Modulation.

8
00:00:35,450 --> 00:00:40,590
If you want to go the short route for storing
the audio data, you can of course take these

9
00:00:40,590 --> 00:00:44,790
PCM samples and throw them into your file
as-is.

10
00:00:44,790 --> 00:00:48,340
If you did that, you would get the WAV format.

11
00:00:48,340 --> 00:00:54,690
But as I mentioned in the first video, the
file sizes here get large fast.

12
00:00:54,690 --> 00:01:00,410
Simple math tells us that there are about
1.4 megabits of sample data for each second.

13
00:01:00,410 --> 00:01:06,890
However, FLAC can commonly compress this to
about half the size, 600 kilobits per second

14
00:01:06,890 --> 00:01:08,460
or even less.

15
00:01:08,460 --> 00:01:15,440
We can go further and reach for 150 kilobits
with MP3, but we’re here for lossless compression.

16
00:01:15,440 --> 00:01:20,170
Today I want to dig deep, so it’s easy to
lose track of what we’re trying to do, and

17
00:01:20,170 --> 00:01:21,760
what we have done so far.

18
00:01:21,760 --> 00:01:27,500
Therefore, let’s look at this sidebar once
in a while, just to keep the big picture in

19
00:01:27,500 --> 00:01:29,170
mind.

20
00:01:29,170 --> 00:01:44,130
Linear Predictive Coding
The 

21
00:01:44,130 --> 00:01:47,610
key to all kinds of compression is patterns.

22
00:01:47,610 --> 00:01:53,540
Last time, I demonstrated how repeats in data
can be easily removed with basic compression.

23
00:01:53,540 --> 00:02:00,210
Now, if you were to look at this audio data,
there’s no obvious repetition here.

24
00:02:00,210 --> 00:02:05,890
But remember that no matter how random this
looks, we’re still dealing with sound.

25
00:02:05,890 --> 00:02:11,380
And sound is made up of waves, whose defining
feature is that they repeat.

26
00:02:11,380 --> 00:02:13,860
But what are these waves, actually?

27
00:02:13,860 --> 00:02:18,360
I didn’t mention it in the last episode
because it wasn’t relevant, but the most

28
00:02:18,360 --> 00:02:21,740
basic kind of wave is a sine wave.

29
00:02:21,740 --> 00:02:27,660
The mathematical function takes parameters
that modify the amplitude, frequency, phase

30
00:02:27,660 --> 00:02:29,270
and offset of the wave.

31
00:02:29,270 --> 00:02:34,830
In fact, it’s the case that any sound can
be described just by the basic sine waves

32
00:02:34,830 --> 00:02:36,900
it is made out of.

33
00:02:36,900 --> 00:02:42,630
Now you might have a first idea of how to
store the samples: Check what sine waves constitute

34
00:02:42,630 --> 00:02:46,750
this signal, then just store those sine waves
and their parameters.

35
00:02:46,750 --> 00:02:52,940
That’s a great idea, in fact, you’re about
to reinvent MP3 and the Discrete Sine Transform.

36
00:02:52,940 --> 00:02:56,590
But for FLAC, we won’t see much of a benefit.

37
00:02:56,590 --> 00:03:01,050
The number of frequencies we need to store
is extremely large.

38
00:03:01,050 --> 00:03:06,060
It’s so large that we need just as much
data as for the samples themselves.

39
00:03:06,060 --> 00:03:10,390
And, sine waves are rather expensive to compute.

40
00:03:10,390 --> 00:03:13,240
So let’s use something simpler.

41
00:03:13,240 --> 00:03:16,970
How about a polynomial function?

42
00:03:16,970 --> 00:03:22,090
A quick refresher on high school calculus:
A monomial is any function like these, where

43
00:03:22,090 --> 00:03:27,860
the parameter x is taken to an integer power
and multiplied by a coefficient, and a polynomial

44
00:03:27,860 --> 00:03:30,459
is just adding a bunch of monomials.

45
00:03:30,459 --> 00:03:36,710
Linear functions, constant functions or quadratic
functions, they’re all polynomials.

46
00:03:36,710 --> 00:03:41,980
If we consider the coefficients again, there’s
only one coefficient per x term.

47
00:03:41,980 --> 00:03:49,750
So a function of degree 5, meaning 5 is the
highest power of x, can only have 6 coefficients.

48
00:03:49,750 --> 00:03:54,620
Don’t forget x^0, the constant term!

49
00:03:54,620 --> 00:03:57,209
But we need to take a step back.

50
00:03:57,209 --> 00:04:01,270
We want to approximate waves, which are sine
functions.

51
00:04:01,270 --> 00:04:05,349
Polynomials are nothing like sine functions,
at least not out of the box.

52
00:04:05,349 --> 00:04:09,849
Some of you are already guessing where I’m
going with this, so let me tell you about

53
00:04:09,849 --> 00:04:13,850
one of the most amazing things in calculus.

54
00:04:13,850 --> 00:04:19,069
Like sine itself, on the one hand we have
a lot of weird functions in math.

55
00:04:19,069 --> 00:04:23,249
On the other hand, we have the super-simple
polynomial functions.

56
00:04:23,249 --> 00:04:29,330
So how about we approximate a complicated
function, any function, with a polynomial?

57
00:04:29,330 --> 00:04:35,830
For starters, we pick a point x0 on the function
where the approximation is “centered”,

58
00:04:35,830 --> 00:04:37,080
so to speak.

59
00:04:37,080 --> 00:04:42,279
Then, our approximated function T should of
course have the same value as the original

60
00:04:42,279 --> 00:04:44,690
function at this point.

61
00:04:44,690 --> 00:04:50,080
And then, T should probably have the same
derivative in x0 as f does, so that its slope

62
00:04:50,080 --> 00:04:51,750
is the same.

63
00:04:51,750 --> 00:04:58,089
And then, T should probably have the same
second derivative in x0 as f does, so that

64
00:04:58,089 --> 00:05:00,630
its curve is the same.

65
00:05:00,630 --> 00:05:03,369
And so on, as long as you want to.

66
00:05:03,369 --> 00:05:07,129
If you’re curious about how we get this
formula, watch the linked video, I don’t

67
00:05:07,129 --> 00:05:08,250
have time right now.

68
00:05:08,250 --> 00:05:13,580
The gist is that especially for functions
that can be derived a lot, the approximation

69
00:05:13,580 --> 00:05:16,759
with a polynomial is really good.

70
00:05:16,759 --> 00:05:21,020
In the case of sine and cosine, in fact, arbitrarily
good!

71
00:05:21,020 --> 00:05:26,800
These formulas here is just what we get when
we put in the well-known values and derivatives

72
00:05:26,800 --> 00:05:29,099
of sine and cosine.

73
00:05:29,099 --> 00:05:34,650
The function T we just created is called the
Taylor Series of f, and it’s one of the

74
00:05:34,650 --> 00:05:38,810
most powerful numeric tools in existence.

75
00:05:38,810 --> 00:05:44,229
In our case, we just need to know this: It’s
very possible to approximate an audio wave

76
00:05:44,229 --> 00:05:45,520
closely with a polynomial.

77
00:05:45,520 --> 00:05:50,160
[sidebar: idea 2]
But, I have again kind of lied to you.

78
00:05:50,160 --> 00:05:55,039
Sure, we can approximate the audio wave with
a polynomial, and we can tune how close we

79
00:05:55,039 --> 00:05:58,259
get by choosing what degree the polynomial
is.

80
00:05:58,259 --> 00:06:04,449
But this kind of approximation breaks down
very fast with more than a handful of samples.

81
00:06:04,449 --> 00:06:11,139
The required polynomial degrees would be extremely
large, which is expensive and unstable on

82
00:06:11,139 --> 00:06:12,349
all fronts.

83
00:06:12,349 --> 00:06:14,909
Let’s try to improve things.

84
00:06:14,909 --> 00:06:20,419
I kind of skipped over it, but we’re of
course not in discrete real number math land.

85
00:06:20,419 --> 00:06:25,419
All our numbers are discrete and finite, both
in x and y.

86
00:06:25,419 --> 00:06:30,689
This means that we’re not dealing with approximating
a function with a function, we’re approximating

87
00:06:30,689 --> 00:06:36,529
a series with a series, or rather, a digital
signal with a digital signal.

88
00:06:36,529 --> 00:06:40,940
As long as we keep our signal defined like
this, however, we’re just switching up the

89
00:06:40,940 --> 00:06:44,520
notation, nothing actually changes, practically
speaking.

90
00:06:44,520 --> 00:06:48,460
The magic only happens once we use a recursive
definition [sidebar: idea 3].

91
00:06:48,460 --> 00:06:52,020
You might have heard about recursion before
[google joke], and here we just mean that

92
00:06:52,020 --> 00:06:58,289
we define a signal’s value as a combination
of previous signal values.

93
00:06:58,289 --> 00:07:02,319
Recursion is not super common in the kind
of calculus you learn in school, but it turns

94
00:07:02,319 --> 00:07:05,409
out to be a powerful tool for data compression.

95
00:07:05,409 --> 00:07:11,639
Now, you have to briefly take my word and
believe me that these specific recursive signal

96
00:07:11,639 --> 00:07:13,970
definitions are really great.

97
00:07:13,970 --> 00:07:16,159
What does this notation mean?

98
00:07:16,159 --> 00:07:23,110
The sample at position t is specified to be
two times the sample at position t-1 minus

99
00:07:23,110 --> 00:07:25,749
the sample at position t-2.

100
00:07:25,749 --> 00:07:31,240
Therefore, if we already know the previous
samples, we can compute the next sample very

101
00:07:31,240 --> 00:07:32,280
easily.

102
00:07:32,280 --> 00:07:35,529
But what if we don’t yet know the previous
samples?

103
00:07:35,529 --> 00:07:41,099
That’s a problem all recursive definitions
need to solve, there has to be a non-recursive

104
00:07:41,099 --> 00:07:42,840
starting point.

105
00:07:42,840 --> 00:07:48,139
More formally, there is an infinite number
of non-recursive functions that fulfil this

106
00:07:48,139 --> 00:07:50,169
recursive formula.

107
00:07:50,169 --> 00:07:55,800
We take the easiest way out and say that the
first couple of samples have some constant

108
00:07:55,800 --> 00:07:56,800
values.

109
00:07:56,800 --> 00:08:02,110
How many constants samples simply depends
on how many previous samples our formula asks

110
00:08:02,110 --> 00:08:03,139
for.

111
00:08:03,139 --> 00:08:07,279
So let’s revisit the procedure and introduce
some terminology.

112
00:08:07,279 --> 00:08:16,699
Out of the four different orders, we are given
one predictor as well as the warm-up samples.

113
00:08:16,699 --> 00:08:22,089
The order specifies how many samples we need
to look back, so how many constant warm-up

114
00:08:22,089 --> 00:08:23,649
samples we need.

115
00:08:23,649 --> 00:08:29,270
For the first couple of samples, we don’t
use the recursive predictor formula, only

116
00:08:29,270 --> 00:08:30,270
afterwards.

117
00:08:30,270 --> 00:08:35,870
Not only is this extremely cheap to compute,
it’s also super space-efficient.

118
00:08:35,870 --> 00:08:41,210
Because there’s only one predictor per order,
we just store the order instead of the coefficients

119
00:08:41,210 --> 00:08:42,530
themselves.

120
00:08:42,530 --> 00:08:47,460
And at the same time, the order tells us how
many warm-up samples there are.

121
00:08:47,460 --> 00:08:52,820
What we’re doing here is encoding samples
by predicting what the next sample will be,

122
00:08:52,820 --> 00:08:56,490
based on a linear combination of the previous
samples.

123
00:08:56,490 --> 00:09:02,400
That’s why we call it Linear Predictive
Coding.

124
00:09:02,400 --> 00:09:06,660
You remember how you took my word a minute
ago when I said that you have to believe in

125
00:09:06,660 --> 00:09:09,290
the greatness of these specific predictors?

126
00:09:09,290 --> 00:09:12,000
Well, let’s get to why that is.

127
00:09:12,000 --> 00:09:18,460
LPC does not always result in polynomial functions,
in fact, most of the time it doesn’t.

128
00:09:18,460 --> 00:09:22,710
And even though it doesn’t look like it
from the seemingly arbitrary coefficients,

129
00:09:22,710 --> 00:09:28,340
these predictors here are the only ones of
their order that do actually correspond to

130
00:09:28,340 --> 00:09:30,210
a polynomial function.

131
00:09:30,210 --> 00:09:32,800
It’s not magic, it’s math.

132
00:09:32,800 --> 00:09:35,410
Let’s look at this from another angle.

133
00:09:35,410 --> 00:09:40,440
We have a number of samples that were already
decoded, and we now want to predict what the

134
00:09:40,440 --> 00:09:42,120
next sample will be.

135
00:09:42,120 --> 00:09:44,110
How can we do that?

136
00:09:44,110 --> 00:09:47,570
Let’s take the simplest approach first and
try to use a line.

137
00:09:47,570 --> 00:09:53,820
In math, of course, we call that a linear
function, or a polynomial of degree 1.

138
00:09:53,820 --> 00:09:59,300
So we want to insert a line somewhere here,
and the prediction we make is where the line

139
00:09:59,300 --> 00:10:03,570
intersects the sample’s point in time, which
we called t.

140
00:10:03,570 --> 00:10:10,360
A linear function consists of only two parameters:
the slope and the vertical position; but we

141
00:10:10,360 --> 00:10:14,320
want to recursively define them depending
on the previous samples.

142
00:10:14,320 --> 00:10:16,680
First, let’s ignore the slope.

143
00:10:16,680 --> 00:10:19,910
I challenge you to come up with a position
for the sample t.

144
00:10:19,910 --> 00:10:24,060
[pause] Your solution is probably too complicated.

145
00:10:24,060 --> 00:10:29,020
Let’s do this as simple as possible and
use the previous sample.

146
00:10:29,020 --> 00:10:34,680
We can think of the previous sample as our
starting point, just something to go off from.

147
00:10:34,680 --> 00:10:36,450
Now what about the slope?

148
00:10:36,450 --> 00:10:40,340
Think about what we just did with the position,
we simply copied it.

149
00:10:40,340 --> 00:10:43,880
So how about we copy the slope too?

150
00:10:43,880 --> 00:10:49,380
The best slope to use of course is the slope
between the previous two samples.

151
00:10:49,380 --> 00:10:54,900
If you took any amount of calculus, you know
that this slope can be calculated by dividing

152
00:10:54,900 --> 00:10:58,120
the y difference by the x difference.

153
00:10:58,120 --> 00:11:04,010
Lucky for us, the x difference is 1 and the
y difference is the difference between these

154
00:11:04,010 --> 00:11:05,070
two samples.

155
00:11:05,070 --> 00:11:10,800
Now, shifting this slope triangle to the right
so that it starts at the previous sample shows

156
00:11:10,800 --> 00:11:14,120
us where we predict the next sample to be.

157
00:11:14,120 --> 00:11:18,940
In terms of our formula, we add the slope
to the position.

158
00:11:18,940 --> 00:11:22,300
And that’s already the second order predictor!

159
00:11:22,300 --> 00:11:27,940
Note that the very last step only works because
all the samples have the same distance, so

160
00:11:27,940 --> 00:11:31,930
the x portion of the slope triangle is always
1.

161
00:11:31,930 --> 00:11:36,550
This assumption of a distance of 1 is one
we generally make because it doesn’t really

162
00:11:36,550 --> 00:11:40,580
change anything but it simplifies the math.

163
00:11:40,580 --> 00:11:44,621
Now that you have seen how we can come up
with a formula for the simple case, let me

164
00:11:44,621 --> 00:11:47,890
show you a more formal mathematical method.

165
00:11:47,890 --> 00:11:53,980
This is less intuitive, but more robust, as
we can use it for even the very highest predictor

166
00:11:53,980 --> 00:11:55,170
orders.

167
00:11:55,170 --> 00:11:58,710
Our starting point again are the Taylor polynomials.

168
00:11:58,710 --> 00:12:04,850
Remember, the fundamental assumption behind
Taylor is that we can approximate some unknown

169
00:12:04,850 --> 00:12:10,790
input by adding up the function and its derivatives
at a known input.

170
00:12:10,790 --> 00:12:16,320
For the best accuracy, let’s pick the last
decoded sample as our known input.

171
00:12:16,320 --> 00:12:21,320
For the function’s value itself, that’s
of course just this sample, but we don’t

172
00:12:21,320 --> 00:12:23,620
even know the first derivative!

173
00:12:23,620 --> 00:12:29,950
After all, we don’t actually know the underlying
function, we can’t derive it with calculus.

174
00:12:29,950 --> 00:12:35,260
Instead, we have to approximate the derivative
as well, and we’re gonna use Taylor once

175
00:12:35,260 --> 00:12:36,260
more.

176
00:12:36,260 --> 00:12:42,460
First, we need to decide how many samples
we want to use to approximate the derivative.

177
00:12:42,460 --> 00:12:47,810
You can use arbitrarily many, and for reasons
outside the scope here, that will give you

178
00:12:47,810 --> 00:12:50,200
better and better approximations.

179
00:12:50,200 --> 00:12:56,470
However, just know that we need at least two
samples for the first derivative, at least

180
00:12:56,470 --> 00:13:00,480
three samples for the second derivative, and
so on.

181
00:13:00,480 --> 00:13:05,440
So for us, let’s just choose the sample
at t-1 which we’re dealing with anyways,

182
00:13:05,440 --> 00:13:08,410
and the one before that, t-2.

183
00:13:08,410 --> 00:13:13,470
To make it simple, our assumption will be
that we can calculate the discrete derivative

184
00:13:13,470 --> 00:13:21,000
at t-1 by some linear combination of the know
samples at t-1 and t-2.

185
00:13:21,000 --> 00:13:27,030
Alright, and this might seem arbitrary at
first, let’s write both those samples not

186
00:13:27,030 --> 00:13:34,040
as the actual value they are, but how we could
in theory calculate them by a Taylor approximation

187
00:13:34,040 --> 00:13:37,100
from t-1.

188
00:13:37,100 --> 00:13:41,570
And then let’s plug that into the right
side of the linear combination.

189
00:13:41,570 --> 00:13:43,890
Do you see now?

190
00:13:43,890 --> 00:13:48,940
If I write the left-hand side more explicitly
and rearrange the right side, it might be

191
00:13:48,940 --> 00:13:51,380
a bit more obvious.

192
00:13:51,380 --> 00:13:56,970
We have coefficients for both the sample and
its derivative on both sides.

193
00:13:56,970 --> 00:14:02,960
That means in order for this formula to be
correct, all the corresponding coefficients

194
00:14:02,960 --> 00:14:08,990
need to be equal, and that gives us a linear
system of equations containing a and b as

195
00:14:08,990 --> 00:14:10,590
the unknowns.

196
00:14:10,590 --> 00:14:18,100
Luckily, this system is super easy to solve,
and we get a=1 and b=-1.

197
00:14:18,100 --> 00:14:23,850
Plug that back into the very first equation
and we have an approximation for the derivative.

198
00:14:23,850 --> 00:14:25,500
Not too bad, was it?

199
00:14:25,500 --> 00:14:31,160
Of course, the steps quickly get out of hand
once we try the same thing for higher-order

200
00:14:31,160 --> 00:14:32,160
derivatives.

201
00:14:32,160 --> 00:14:37,750
However, the procedure is exactly the same,
you just have longer expansions and more equations

202
00:14:37,750 --> 00:14:38,840
in the system.

203
00:14:38,840 --> 00:14:42,810
I encourage you to try doing the second derivative
yourself.

204
00:14:42,810 --> 00:14:47,490
Remember, we need the previous three samples,
and if you know a thing or two about linear

205
00:14:47,490 --> 00:14:51,870
systems of equations, you should be able to
tell why that is.

206
00:14:51,870 --> 00:14:57,290
Finally, we need to invoke Taylor once more
and just combine these derivatives into one

207
00:14:57,290 --> 00:15:00,400
formula for the sample we actually care about.

208
00:15:00,400 --> 00:15:06,210
There’s a tradeoff here: Using more derivatives
gives us a better approximation, that’s

209
00:15:06,210 --> 00:15:09,400
just a basic property of Taylor polynomials.

210
00:15:09,400 --> 00:15:15,230
On the other hand, higher derivatives require
more samples and more time to compute.

211
00:15:15,230 --> 00:15:22,590
So depending on how much accuracy we need,
we can select zero to three derivatives, and

212
00:15:22,590 --> 00:15:28,980
simplifying these equations gives us exactly
the five predictors we know from before.

213
00:15:28,980 --> 00:15:34,279
Of course, if you’ve been calculating the
Taylor expansions along at home, these formulas

214
00:15:34,279 --> 00:15:38,380
aren’t correct, some of the higher derivatives
are missing a factor.

215
00:15:38,380 --> 00:15:42,820
That is indeed intentional, we’re not doing
exact math, we’re just trying to do some

216
00:15:42,820 --> 00:15:45,120
sample prediction to compress audio.

217
00:15:45,120 --> 00:15:50,420
Avoiding the factorial divisors makes this
entire thing cheaper to compute, which – you

218
00:15:50,420 --> 00:15:55,610
remember – was the whole point of linear
predictive coding.

219
00:15:55,610 --> 00:16:01,500
Two remarks before we continue: First, it
is important to remember that this whole polynomial

220
00:16:01,500 --> 00:16:06,450
prediction business only applies at the level
of the few previous samples.

221
00:16:06,450 --> 00:16:12,850
We’re not, in fact, trying to approximate
all of the samples with just one polynomial,

222
00:16:12,850 --> 00:16:15,430
that’s never a good idea.

223
00:16:15,430 --> 00:16:20,620
And second, in general, when we’re talking
about linear predictive coding, the coefficients

224
00:16:20,620 --> 00:16:22,690
here can be anything.

225
00:16:22,690 --> 00:16:28,060
The resulting function is then not a polynomial
anymore, but it turns out that many of them

226
00:16:28,060 --> 00:16:33,850
are even better at signal prediction than
the five simple ones we initially looked at.

227
00:16:33,850 --> 00:16:38,350
So of course FLAC supports them, the highest
order we can go to is 32.

228
00:16:38,350 --> 00:16:44,480
I have to mention though that this is extremely
computationally intensive, especially for

229
00:16:44,480 --> 00:16:45,480
encoding.

230
00:16:45,480 --> 00:16:50,460
Choosing predictor order and coefficients
for arbitrary LPC involves just way too much

231
00:16:50,460 --> 00:16:52,040
linear algebra.

232
00:16:52,040 --> 00:16:56,940
On the other hand, the polynomial predictors
are so cheap that you can just encode with

233
00:16:56,940 --> 00:17:00,810
all five of them and pick the one that compresses
best.

234
00:17:00,810 --> 00:17:04,709
Now, remember that LPC contains the word “predictive”.

235
00:17:04,709 --> 00:17:09,410
It’s predicting the sample values, not exactly
reproducing them.

236
00:17:09,410 --> 00:17:14,270
This means that no matter how hard we try,
there will always be an error.

237
00:17:14,270 --> 00:17:19,449
If we subtract the predicted signal from the
actual signal, we get something called the

238
00:17:19,449 --> 00:17:21,569
residual.

239
00:17:21,569 --> 00:17:24,089
A list of numbers, once again.

240
00:17:24,089 --> 00:17:28,049
You might say now that all this linear predictive
coding didn’t gain us much if we’re still

241
00:17:28,049 --> 00:17:31,149
left with these numbers that need to be included.

242
00:17:31,149 --> 00:17:33,490
Remember: it’s lossless.

243
00:17:33,490 --> 00:17:40,519
At this point we could invent the Free Lossy
Audio Codec and throw away most of the information.

244
00:17:40,519 --> 00:17:44,299
But that’s not today’s topic, we need
all of the data here.

245
00:17:44,299 --> 00:17:49,929
Recall that in the previous step, we didn’t
store separate data for most samples.

246
00:17:49,929 --> 00:17:55,970
Well, that turns out to not work very well
here; I’ll go ahead and assume that we need

247
00:17:55,970 --> 00:18:00,220
to store all residuals independent of each
other.

248
00:18:00,220 --> 00:18:05,869
The first idea would of course be to pick
a bit depth, probably something similar to

249
00:18:05,869 --> 00:18:10,380
the original bit depth, and just encode the
residuals with that.

250
00:18:10,380 --> 00:18:12,740
And we’re not totally off base here!

251
00:18:12,740 --> 00:18:17,379
FLAC allows you to go that route if everything
else fails.

252
00:18:17,379 --> 00:18:22,750
You have to be careful with what bit depth
you choose, as all the residuals have to fit,

253
00:18:22,750 --> 00:18:24,460
but it’s totally possible!

254
00:18:24,460 --> 00:18:29,149
Though as the astute among you have already
noticed, this is super inefficient.

255
00:18:29,149 --> 00:18:32,999
Let’s think of a very simple but common
scenario.

256
00:18:32,999 --> 00:18:39,039
We have a very good approximation of our original
samples, so all of our residuals are really

257
00:18:39,039 --> 00:18:43,929
small in magnitude, like plus or minus 32
at maximum.

258
00:18:43,929 --> 00:18:50,480
But there are these few samples towards the
end that do not fit our curve at all, and

259
00:18:50,480 --> 00:18:54,419
their residual size is ridiculously large,
like a couple thousand.

260
00:18:54,419 --> 00:19:00,850
So, just to fit those few outliers, we immediately
need a bit depth of say 10 to 12.

261
00:19:00,850 --> 00:19:04,600
Which wastes a lot of bits on the small numbers.

262
00:19:04,600 --> 00:19:08,820
An insight we need here is some information
theory fundamentals.

263
00:19:08,820 --> 00:19:13,620
3blue1brown made an excellent video on the
matter, so I’ll keep it brief.

264
00:19:13,620 --> 00:19:20,400
What I implicitly already told you is a very
important observation about the residual data:

265
00:19:20,400 --> 00:19:27,149
Because they are residuals from a function
approximation, most values are pretty small.

266
00:19:27,149 --> 00:19:32,559
To put it another way: If you are reading
through the list of residuals at random, the

267
00:19:32,559 --> 00:19:39,940
probability of hitting any specific value
is not equal: you are more likely to find

268
00:19:39,940 --> 00:19:43,369
small values than large values.

269
00:19:43,369 --> 00:19:45,909
So for an encoding scheme to use the least
amount of bits, it should use very little

270
00:19:45,909 --> 00:19:52,389
space to store common, small values, and it
can be allowed to use a bit of excessive space

271
00:19:52,389 --> 00:19:55,559
for uncommon, large values.

272
00:19:55,559 --> 00:19:57,840
As I said, a constant bit depth is out.

273
00:19:57,840 --> 00:20:00,409
How about a variable bit depth?

274
00:20:00,409 --> 00:20:04,909
If we can specify how many bits a number uses,
we can choose lower bit depths for smaller

275
00:20:04,909 --> 00:20:08,320
numbers and larger bit depths for larger numbers.

276
00:20:08,320 --> 00:20:13,299
So let’s have two numbers: one specifies
the bit depth and the other is the encoded

277
00:20:13,299 --> 00:20:16,070
value itself at that bit depth.

278
00:20:16,070 --> 00:20:18,690
This sounds like a good idea but it’s not
efficient.

279
00:20:18,690 --> 00:20:24,820
We have only moved our problem because now
we need to pick and choose another bit depth

280
00:20:24,820 --> 00:20:27,519
for the bit depth specifier!

281
00:20:27,519 --> 00:20:34,120
Our maximum bit depth still needs to support
the very large bit depths for very large numbers.

282
00:20:34,120 --> 00:20:36,130
All in all, we don’t gain much.

283
00:20:36,130 --> 00:20:40,539
The bit depth specifier needs to have a variable
size as well.

284
00:20:40,539 --> 00:20:43,999
The simplest method is to use unary encoding.

285
00:20:43,999 --> 00:20:50,129
In unary, a number is simply represented by
the number of symbols that are present.

286
00:20:50,129 --> 00:20:51,500
Tally marks.

287
00:20:51,500 --> 00:20:57,769
In computers, which only store binary, we
need a terminating symbol, so we use zeroes

288
00:20:57,769 --> 00:21:00,269
followed by a single one.

289
00:21:00,269 --> 00:21:05,919
And yes, that means that there is one symbol
more than the number we store, this is intentional

290
00:21:05,919 --> 00:21:08,669
and will come in handy later.

291
00:21:08,669 --> 00:21:13,980
Getting back to the encoding, we can then
place the number itself after that.

292
00:21:13,980 --> 00:21:18,860
Except all numbers start with a 1 in binary,
so we don’t need to store that 1 again.

293
00:21:18,860 --> 00:21:24,170
The unary-encoded bit depth can then be thought
of as the highest power of two that the number

294
00:21:24,170 --> 00:21:25,170
contains.

295
00:21:25,170 --> 00:21:30,619
So to encode: count the number of bits in
the value and store that many zeroes.

296
00:21:30,619 --> 00:21:34,730
Then, store the number itself, starting with
the highest 1 bit.

297
00:21:34,730 --> 00:21:41,059
To decode: Read zeroes until you hit a 1,
then keep reading afterwards as many bits

298
00:21:41,059 --> 00:21:42,919
as there were zeroes.

299
00:21:42,919 --> 00:21:48,820
The decoded value is this second half as well
as the leading 1.

300
00:21:48,820 --> 00:21:53,489
This encoding scheme is known as Elias gamma
coding [sidebar: idea 5], and it’s already

301
00:21:53,489 --> 00:21:54,489
great!

302
00:21:54,489 --> 00:21:57,379
I mean, it’s good enough for Pokémon Gen
1 sprites.

303
00:21:57,379 --> 00:22:04,269
But we still have two major drawbacks that
need fixing: First: gamma coding can’t encode

304
00:22:04,269 --> 00:22:05,309
a zero.

305
00:22:05,309 --> 00:22:11,269
This is easy enough to fix: we just add 1
to the number before encoding it and subtract

306
00:22:11,269 --> 00:22:13,380
that 1 after decoding.

307
00:22:13,380 --> 00:22:17,809
This method has its own name, the Exponential
Golomb code.

308
00:22:17,809 --> 00:22:22,100
Second, however, the encoded size is a problem.

309
00:22:22,100 --> 00:22:27,929
We can encode arbitrarily-sized numbers with
gamma coding, but the number of required bits

310
00:22:27,929 --> 00:22:32,289
always doubles!

311
00:22:32,289 --> 00:22:37,120
Small numbers don’t mind, but large numbers
do.

312
00:22:37,120 --> 00:22:39,529
So here’s the procedure.

313
00:22:39,529 --> 00:22:44,909
We pick a parameter k, which is called the
order of the Exponential Golomb code.

314
00:22:44,909 --> 00:22:51,309
Order 0 will give us what we previously discussed,
and higher orders give us better encoding

315
00:22:51,309 --> 00:22:55,570
of larger numbers but worse encoding of smaller
numbers.

316
00:22:55,570 --> 00:23:01,659
We’re encoding any number now as a multiple
of a base plus a remainder.

317
00:23:01,659 --> 00:23:07,740
Our base is always the kth power of 2, that’s
the “exponential” part.

318
00:23:07,740 --> 00:23:14,700
The great thing is that in binary, multiplying
or dividing by a power of two is just shifting

319
00:23:14,700 --> 00:23:16,129
bits around.

320
00:23:16,129 --> 00:23:22,549
So by splitting the number up into a multiple
of a power of two plus a remainder when dividing

321
00:23:22,549 --> 00:23:30,259
by that power of two, we just literally split
the bits of the number into two parts.

322
00:23:30,259 --> 00:23:36,630
We encode the quotient with order 0 Exponential
Golomb coding, which is just what we discussed

323
00:23:36,630 --> 00:23:38,480
beforehand, with the unary and stuff.

324
00:23:38,480 --> 00:23:46,440
Then, afterwards, we just append the remainder,
which of course always uses k bits.

325
00:23:46,440 --> 00:23:49,519
When I first understood this coding, it was
magical.

326
00:23:49,519 --> 00:23:52,830
Let’s take a moment to appreciate what this
is doing.

327
00:23:52,830 --> 00:23:58,769
We’re still making use of all the efficient
fun stuff, like variable bit depth for arbitrarily

328
00:23:58,769 --> 00:24:00,320
large numbers.

329
00:24:00,320 --> 00:24:07,139
But the k gives us a fixed number of lower
bits that are included as-is, while we perform

330
00:24:07,139 --> 00:24:12,279
Exponential Golomb on the upper, more significant
bits.

331
00:24:12,279 --> 00:24:18,759
Critically, we don’t increase the bit count
by 2 when we double the number, as the lower

332
00:24:18,759 --> 00:24:22,309
bits have nothing to do with the coding of
the upper bits.

333
00:24:22,309 --> 00:24:28,160
As we increase k, we get larger numbers of
fixed low bits, which are quite expensive

334
00:24:28,160 --> 00:24:29,769
for small numbers.

335
00:24:29,769 --> 00:24:35,840
But for larger numbers, the encoding of the
upper bits allows us to reach ridiculous values

336
00:24:35,840 --> 00:24:38,830
without the double cost from before.

337
00:24:38,830 --> 00:24:41,960
Again, we can now pick the tradeoff.

338
00:24:41,960 --> 00:24:47,429
If our residuals are good and we only have
a few large numbers, we choose k very small

339
00:24:47,429 --> 00:24:52,149
or even 0, leading to very good small number
compression.

340
00:24:52,149 --> 00:24:58,559
If our residuals are bad, we choose a larger
k and can still compress data while not paying

341
00:24:58,559 --> 00:25:01,429
double the price for large numbers.

342
00:25:01,429 --> 00:25:07,049
FLAC recognizes that even within a single
list of residuals, there are many different

343
00:25:07,049 --> 00:25:10,940
collections of residuals that need differing
treatment.

344
00:25:10,940 --> 00:25:18,269
So you can actually choose up to a sequence
of 32,768 different orders for a single residual

345
00:25:18,269 --> 00:25:19,279
list!

346
00:25:19,279 --> 00:25:25,580
And if any chunk of residuals compresses badly,
you just don’t compress it.

347
00:25:25,580 --> 00:25:29,629
The observant viewers might have noticed that
we still have a problem.

348
00:25:29,629 --> 00:25:35,340
All the numbers that Exponential Golomb can
encode are positive, but residuals, as all

349
00:25:35,340 --> 00:25:39,559
audio data, are signed, so both positive and
negative.

350
00:25:39,559 --> 00:25:45,399
It’s a similar situation to how we didn’t
have zero in Elias gamma coding.

351
00:25:45,399 --> 00:25:47,480
But again, there’s a simple fix.

352
00:25:47,480 --> 00:25:53,070
If we just store positive and negative numbers
alternatingly, we can make numbers of small

353
00:25:53,070 --> 00:25:57,929
magnitude map to few bits and keep our good
properties.

354
00:25:57,929 --> 00:26:08,279
More specifically, we map non-positive x to
-2x and positive x to 2x-1.

355
00:26:08,279 --> 00:26:12,380
Let’s take a step back and look at the bigger
picture.

356
00:26:12,380 --> 00:26:18,299
So far, we have only concerned ourselves with
one stream of audio, one list of samples,

357
00:26:18,299 --> 00:26:19,610
and one channel.

358
00:26:19,610 --> 00:26:25,580
But the reality is that most audio has at
least two channels, stereo of course.

359
00:26:25,580 --> 00:26:30,879
And it would be really wasteful to just encode
both channels independently!

360
00:26:30,879 --> 00:26:37,119
After all, most stereo audio has very similar
or even the same audio on both the left and

361
00:26:37,119 --> 00:26:39,169
right channels.

362
00:26:39,169 --> 00:26:42,830
So what we can do instead is Interchannel
Decorrelation.

363
00:26:42,830 --> 00:26:48,669
Instead of a left and right channel, we use
a mid and side channel.

364
00:26:48,669 --> 00:26:52,929
The mid channel stores the average of the
two channels, while the side channel stores

365
00:26:52,929 --> 00:26:55,100
the difference between the channels.

366
00:26:55,100 --> 00:27:00,749
To decode, we just use mid+side for the left
channel and mid-side for the right channel.

367
00:27:00,749 --> 00:27:06,669
All of this is per sample, of course, which
means that the mid and side channels are what

368
00:27:06,669 --> 00:27:09,809
actually passes through our LPC and residual
shenanigans.

369
00:27:09,809 --> 00:27:17,649
The big advantage is now that the side channel
is usually very silent or, in fact, perfectly

370
00:27:17,649 --> 00:27:18,649
silent.

371
00:27:18,649 --> 00:27:23,590
Therefore, it can usually be compressed extremely
well, all in all amounting to not much more

372
00:27:23,590 --> 00:27:27,490
than just compressed mono data.

373
00:27:27,490 --> 00:27:30,070
And that’s it for today!

374
00:27:30,070 --> 00:27:33,090
This is all that FLAC does to compress audio.

375
00:27:33,090 --> 00:27:37,789
Let’s revisit what we learned today because
it’s a lot.

376
00:27:37,789 --> 00:27:41,889
First, audio channels are decorrelated if
needed.

377
00:27:41,889 --> 00:27:48,609
Then, we approximate a channel’s data with
linear predictive coding, and we’ll often

378
00:27:48,609 --> 00:27:51,190
use a polynomial predictor.

379
00:27:51,190 --> 00:27:57,270
We store the coefficients of the LPC as well
as the warm-up and treat the difference between

380
00:27:57,270 --> 00:28:01,930
encoded and actual signal as the residual.

381
00:28:01,930 --> 00:28:08,100
This residual is then encoded with an exponential
Golomb code of arbitrary order.

382
00:28:08,100 --> 00:28:10,879
Here I want to end the second video.

383
00:28:10,879 --> 00:28:16,659
You now understand all the theory behind FLAC’s
audio compression, but in the final video,

384
00:28:16,659 --> 00:28:19,600
I want to look at how that works in practice.