# How were the coefficients for polynomial linear predictive coding derived?

FLAC uses linear predictive coding (LPC) as one of its central compression steps. While it allows for arbitrary LPC coefficients in the "FIR Linear prediction" subframe compression type, there's also the "fixed LPC" type, which consists of five different orders of LPC predictors. Those predictors are lifted straight from Shorten except for the last one. I was intrigued as to how the seemingly arbitrary coefficients in those predictors came about. After some messing around, I found out that all of the recursive formulas are fulfilled by any polynomial with corresponding degree; for example the second-order predictor $$s[t] = 2s[t-1] - s[t-2]$$ is fulfilled by any polynomial $$s(t) = at + b$$ where a and b are arbitrary coefficients and which are implicitly encoded in FLAC as the warm-up samples.

Now I was wondering: How could you derive these coefficients (in the example, $$2, -1$$)? I figured out a way of thinking about the second order: Because it's a linear function, the sample at $$t$$ can be thought of the sample at $$t-1$$ plus the "step" between samples, which can be obtained with $$s[t-1] - s[t-2]$$, all in all giving $$s[t] = s[t-1] + (s[t-1] - s[t-2])$$ as expected. I tried expanding that to the third order predictor, which is quadratic, but had no luck messing about with derivatives and second derivatives. The internet is also not helping. How does this work, then?

With the new IETF standards document, this seems pretty obvious now. It's a problem of polynomial interpolation at n+1 points or samples, where n is the order of the predictor, and using the interpolation polynomial to predict the next sample. Here's Newton's polynomial method for order 2

Let us calculate the sample at $$t_3$$ given $$t_0,t_1,t_2$$. In the second column of divided differences, all denominators are 1 and in the third column the denominators are 2. That’s because we define the samples to have a distance of one. We obtain (arrows omitted):

$$\begin{matrix}[t_0 ]s&&\\ [t_1 ]s&[t_0,t_1 ]s&\\ [t_2 ]s&[t_1,t_2 ]s&[t_0,t_1,t_2 ]s\end{matrix}= \begin{matrix}s[t_0]&&\\s[t_1 ]&s[t_1 ]-s[t_0 ]=s' [t_1]&\\ s[t_2 ]&s[t_2 ]-s[t_1 ]=s' [t_2]&\frac{s' [t_2 ]-s' [t_1 ]}{2}=s[t_2 ]/2-s[t_1 ]+s[t_0 ]/2=s'' [t_2] \end{matrix}$$

Then we can derive the full function with the standard algorithm:

$$s[t]=(s'' [t_2 ]⋅(t-t_1 )+s' [t_1 ])⋅(t-t_0 )+s[t_0]$$

Now remember that we’re evaluating at $$t_3$$ and the samples are all 1 apart, so this formula simplifies greatly ($$t_3-t_1=2,t_3-t_0=3$$):

$$s[t_3 ]=3(2s'' [t_2 ]+s' [t_1 ])+s[t_0 ]=6s'' [t_2 ]+3s' [t_1 ]+s[t_0 ]=3s[t_2 ]-6s[t_1 ]-3s[t_0 ]+3s[t_1 ]+3s[t_0 ]+s[t_0 ]=3s[t_2 ]-3s[t_1 ]+s[t_0]$$

Renaming the variables and calculate $$s[n] = 3s[n-1] - 3s[n-2] + s[n-3]$$, and that’s the solution.