A linear predictor[1] tries to "predict" the next sample as the linear
combination of previous samples as
x'[n] = SUM [i=1..k] a_i * x[n-i]
where x'[n] is the predicted sample, and a_1, a_2 ... a_k are the
prediction coefficients (weights). This is often called linear
predictive coding (LPC), and one typical application is to encode the
formants in telephone telecommunications using source-filter model of
speech[2]. Another typical application is waveform encoding in
lossless wave compression codecs[3] like Shorten, FLAC, WavPack,
MPEG-4 ALS, etc.
The simplest possible form of a linear predictor is when a_1 = 1, and
all other coefficients a_2, a_3, ... a_n = 0. So it simply predicts
the next sample as
x'[n] = x[n-1]
In other words, it predicts the next sample to be the same as the previous one.
This special case of linear prediction is called "delta encoding[4]",
where the next sample is predicted to be the same, and only the
difference between two consecutive samples are encoded. One compressed
audio file format that uses this type of encoding is the Amiga IFF
8SVX file format[5].
If we simplify this delta encoding further and apply it to the
smallest finite field GF(2), then we get:
b'[n] = b[n-1]
where b[n] is the Nth bit, and b'[n] is the prediction for the Nth
bit. In this model, if we try to estimate the prediction error, then -
since GF(2) only has two elements: 0 and 1 - the difference (delta)
between two consecutive bits can be either 0 or 1.
Since the addition operation in GF(2) is XOR, the difference (delta)
between two consecutive bits equals A XOR B, that gives 1 for 0->1 or
1->0 transition, and gives zero for two identical bits. To calculate
the total prediction error, we simply need to sum the total number of
binary transitions in the binary string:
E = SUM [i=2..N] ( b[i] XOR b[i-1] )
where N is the total number of bits, and E is the total error between
the prediction and the actual samples.
So an algorithm that counts bitflips in a binary string, can be
thought of as the sum of the errors of the simplest possible linear
predictor over GF(2) with a_1 = 1 and a_2, a_3, ... a_n = 0, that
simply "predicts" that the next bit will be the same as the previous
bit. By counting the binary transitions, we get the sum of 'deltas',
or the sum of 'prediction error' of binary delta coding.
If we think of entropy as 'unpredictability' and we expect it to
(possibly nonlinearly) correlate with the sum of errors between a
prediction and actual samples, then this simplistic linear predictor
can be thought of as a very simplistic approximation to entropy.
Of course, this is an extremely simplistic and dumb predictor - it is
the simplest possible linear predictor that can possibly exist, as
GF(2) is the smallest finite field, and it only has a single
coefficient a_1 = 1. It cannot account for periodicity, previous bits,
statistical probabilities, or other correlations. It can be thought of
as an excercise in trying to create the "simplest possible predictor".
Despite this, and however simple this predictor may seem, by extending
this idea further I could successfully create a lossless PCM wave
compression algorithm with compression ratios comparable to that of
codecs using more complex linear predictors, like FLAC or Shorten.
(More on this later.)
Best regards,
Peter
References:
[1] https://en.wikipedia.org/wiki/Linear_prediction
[2]
https://en.wikipedia.org/wiki/Source%E2%80%93filter_model_of_speech_production
[3] https://en.wikipedia.org/wiki/Linear_predictive_coding#Applications
[4] https://en.wikipedia.org/wiki/Delta_encoding
[5] https://en.wikipedia.org/wiki/8SVX
[6] https://en.wikipedia.org/wiki/GF%282%29
--
dupswapdrop -- the music-dsp mailing list and website:
subscription info, FAQ, source code archive, list archive, book reviews, dsp
links
http://music.columbia.edu/cmc/music-dsp
http://music.columbia.edu/mailman/listinfo/music-dsp
