Correspondence from Francois Charleton.  To the place in my page where I link to this ../#Francois .

Hello,

Over the last month, I have been working on lossless audio coding, as a “pet project”. This is not my trade, but I am a heavy music listener, own a lot of recordings which I sometime save on a hard disc, and work in a field (the processing of media audience surveys) which makes heavy use of compression algorithms.

As many others, probably, I was surprised by the fairly low rate of compression achieved by all audio compressors. This might be a theoretical limit, or something important that was missed so far. Anyway, it is interesting to study. So far, I have been experimenting with “classical” techniques (Linear Prediction plus Rice coding, basically), and have been acheving results which are close (3-8% larger than FLAC at maximal compression level, with much simpler algorithms). Now is when the fun part begins : either I have already hit the theoretical wall, and I will need a lot of work to get a few % improvement, or this is where to start to get much better rates.

I want to try several ideas (this is fairly sketchy, as it is not the purpose of this email, I can provide more details if you are interested) :

1-       improving on Linear Predictive Coding : so far, all algorithms seem to use low order predictors, ie they make use of the correlations between one sample and the N previous, N being typically between 1 and 10. Thinking of it in terms of filters, LPC takes advantage of the fact that very high frequencies (over 5khz, say) are not very important in audio files (due, IMO, to recording constraints). Now it would be interesting to take into account lower (hearing range) frequencies : this is musical sound, after all, and there has to be higher order correlations which could be exploited.

2-       Improving on variance calculations : all the statistical methods used to derive predictors select the one which minimise variance, and probably tend to overajust to big residuals (stragglers in your terminology)

3-       Rethinking stereo decorrelation : I just cannot admit that there is little to be gained from stereo decorrelation... I think the main problem comes from the fact (observed by looking at audio data) that even when the left and right channel are correlated, they tend to be dephased, again there is room for improvement

4-       Thinking in terms of interpolation : there are modern and efficient ways to sparsely interpolate a series of data (using sparse splines, for instance, but this is what transform coding does, implicitly), could they be applied to audio compression.

Anyway, during my experiments with classical methods, I tried to improve on rice coding, and have noticed most simple ideas were very counterproductive... I did try your Elias codes, which seemed to degrade to overall bitrate. Thinking about it, I believe I have an explanation of why this is so. So, here goes...

Once you have derived (through modelling) the residuals you need to encode, and provided you have eliminated all correlations between them, the best bit rate you can achieve on them only depends on their distribution. More precisely, the length of the shortest representation you can derive is the entropy of the distribution :  sum { -f(x)Log2( f(x) ) } where f(x) is the probability of value x appearing in the residuals. This can be done explicitly, through arithmetic coding, at the expense of having a complex coder/decoder (arithmetic coding is hard to program when the number of possible residuals is large), and maybe some overhead. However, it is known that simpler schemes can result in lengths close to optimal, in the specific cases when the distribution has a known form. Rice, Elias, and all these schemes can be thought as “specific implementations” of arithmetic/huffman codes, for special distributions.

On a specific set of residual, their ability to compress mostly depends on whether the actual distribution of residuals fits the implicit distributions these codes were designed to operate on.

Now, Rice codes are optimal on Laplacian-distributed residuals (see below for more on this), ie if for any x and n, the probability of a residual being between nx and (n+1)x is half that of being between (n-1)x and nx (more on this below). If you apply an Elias code to such a distribution,  the gain for long stragglers will be offset by the fact that short (and very short) stragglers tend to appear much more often. In a nutshell, the Elias codes would be better if the residual distribution fell more sharply than the Laplacian does (actually, if it were a gamma distribution)...

On the real life cases I have tested : the Elias codes seem to be less efficient than the Rice code, which tends to prove that the actual distribution of the residuals is closer to a Laplacian, than to a more peaked Elias. As a result, the few cases where Elias is less efficient than Rice happen too often to make the improvement over longer codes valuable.

Now, apart from empirical observations, there are good theoretical reasons why the residual distribution should be laplacian : the laplacian distribution corresponds to the maximal entropy distribution (the most random one) when one knows the means of a distribution (zero in the audio case), but not its variance (ie the volume of the sound can vary as much as one wants). If the variance was normalised (ie the model could account for volume variations), then the distribution would be a gaussian (and both Elias and Rice code would be less efficient). For the residuals to follow a gamma distribution, there should be more ‘large residuals” than normally, ie a number of “unnacounted for” stragglers, which is just what the predictor approach tries to avoid. To sum up, the better your modelling, the less efficient elias codes will be.

This leaves us with one question : can we improve on Rice coding? In my opinion, the answer is yes, but not much, except if a breakthrough is found in sound modelling.

If the residuals do follow a Laplace distribution, we could first calculate the difference between the Entropy of the Laplace distribution, and that of the corresponding rice code. This can be done by calculating the integral entropy of the Laplace distribution, which is :

Integral of f(x) Log2(x) dx, where f(x)=1/2a exp( |-x/a|) (Laplace distribution), which is equal to 2,44 + Log2(a) (where a can be estimated as the average absolute deviation of the sample)

The rice code entropy (for the same a), for parameter k, is 1+k+ 1/ ( 1 - exp(-2**k/a)), tabulating it in excel, one can find out that the best value of k est the integral part of Log2(a), and that the entropy of the corresponding rice code is over the theoretical Laplace entropy varies between 0,14 bits and 0,03 bits (maximum when a is a power of 2). This is because the rice code estimates the continuous Laplace probabilities with discrete values, which are less efficient than “real entropy” coding. This could be improved by using arithmetic coding for the laplace distribution instead of the rice code.

On a typical audio file (16 bits, with a compression ratio around 50%), this would means some improvement between 0,5 and 2%, small but not negligible (apparently, LA uses such a scheme, although the description they give for it is not very clear).

A second improvement could come from the observation that audio residues are usually coded on a frame basis, ie estimated over a small number of samples. This means that the empirical distribution of the residues will not be that close to a laplacian (there will be a few large outliers, not a lot of small probability values). It might therefore be a good idea to exclude a number of “bad samples” from the rice coding. I think FLAC does something like this, by having a “rice escape code”, which tells the decoder that the next sample is coded in clear (over 16 bits...). As the rice escape code will be fairly long, and as the corresponding “bad samples” will be fairly rare, I am not sure this will bring a lot onf improvement, but there might be some better ways to perform this hybrid coding.

A last possibility (which is what I aim at) would be to find a better model, which would still reduce the randomness in the residual (and actually make them gaussian). My impression is that the residuals are Laplacian (as are the original samples) because :

- sound signals have an average value of zero

- their variance (volume) varies a lot over the time

Now, LPC coders seem to have a lot of difficulty to model the volume : the louder a recording, the worse it compresses. We clearly need models which can predict volume variations... Such models exist in speech modelling : in speech signals, high volumes are caused by “voicing” (ie vowels), whereas unvoiced signals (consonants) tend to have low volumes. Voicing seems to result from low frequency (100-1000 Hz) high amplitude components in the signal, which LPC coders cannot detect. If the predictor could model such “voiced” situations in musical files (which more or less correspond to the actual notes on the score), then the variance could be reduced, resulting in better compression, the residual distribution might evolve from a Laplace towards a Gaussian, and a better code might be used...

I hope these ramblings can be of some interest to you. Please feel free to react (or let me know it was plain silly and drop it in the appropriate electronic waste basket...).