Low-Complexity Audio Compression?

What options exist for discrete audio compression that is good quality, moderate compression (e.g. 3+:1), and low complexity (e.g. hundreds of processing cycles to encode each sample without the use of floating point), especially ones that are not patent-encumbered? The specific application is ambient sound - vocal and nonvocal audio.

I'm not very well-versed in this space of algorithms. I'm familiar with the high quality high compression algorithms, but even MP3 is too expensive for my purposes. The only low complexity moderate compression algorithm family I know is ADPCM, and I have no idea if any implementations of that could be considered good quality.

EDIT: Relevant question: what is the highest quality fixed-point ADPCM algorithm?

• Justin, can you describe the nature of the original audio data going in? stuff like sample rate, float vs. fixed point, word width? being audio, can we make some assumptions about the typical spectrum? then the last question is, how lossy can you allow your compression and reconstitution of the audio to be? – robert bristow-johnson May 4 '14 at 16:07
• also, do you have MATLAB or Octave or something you can use to try out algs and visualize (plot) the data? – robert bristow-johnson May 4 '14 at 17:12
• It is ambient sound sampled at 16 khz 16-bit fixed point. Mainly voice and "sound effects". At this point it's mainly seeing what the best quality available is for the requisite level of compression and very low complexity. – Justin Olbrantz May 4 '14 at 17:29
• Look up the new Opus codec. – Emre May 5 '14 at 0:50
• I actually looked at that a bit last night, though the impression I got was that it would not be able to fit an encoder into the available processing power. My impression could be wrong; do you have any numbers to present on how low in MIPS you can build an encoder around? – Justin Olbrantz May 5 '14 at 1:10

SBC was specifically created for this purpose. See http://en.wikipedia.org/wiki/SBC_(codec). I don't know what the current legal situation is.

Other alternatives depend on your application: what is your target bandwidth and what type of artifacts and errors can you tolerate and which ones not.

• Hmm. Interesting. But I am not so sure it could be encoded in like 35 MIPS with no floating point. – Justin Olbrantz May 3 '14 at 19:27

given that the data is audio sampled at 16 kHz and that the data is already "reduced" to 16-bit words, probably the simplest low-complexity compression would be to use Differential PCM ("DPCM" without the "A") and apply Huffman coding (with a fixed code book) on the result of that. the result is lossless.

lossly compression would be okay, except it requires analysis of the audio, which is not low complexity.

DPCM is a simple special case of Linear Predictive Coding (LPC) which combines the previous samples of the signal to predict the next sample, and then encode only the difference between the prediction and the actual sample.

let $x[n]$ be the audio samples. with general LPC differential coding you linearly combine the previous $K$ samples to make a good guess at what the next sample will be: $$\hat{x}[n] = \sum_{k=1}^{K} a_k x[n-k]$$

where the $a_k$ coefficients are somehow optimally chosen. that's what LPC is about.

with simple Delta modulation, $a_1 = 1$ and all other $a_k = 0$, so the guess for the next sample is simply the previous sample: $\hat{x}[n] = x[n-1]$.

then, in the first step, you encode only the difference: $$d[n] = x[n] - \hat{x}[n]$$

of course, you can reconstruct the signal from its previous values and the difference with $$x[n] = \hat{x}[n] + d[n] = \sum_{k=1}^{K} a_k x[n-k] + d[n]$$

Note #1: except for the simple Delta modulation, $\hat{x}[n]$ will likely have more bits than your original $x[n]$, so part of computing $\hat{x}[n]$ (for both encoding and decoding) will include rounding to the nearest 16-bit value.

now, why do this? the reason is that the difference signal $d[n]$ will be a smaller, lower-amplitude signal, if your prediction is good. it's possible that a signed 8-bit word can represent that difference 90% of the time. but even if there are the occasional difference value that exceeds the 8-bit range, there are a couple of different things you can do about it.

one is to Adapt a gain or scaling value to that difference: $$d[n] = \frac{1}{g[m]} \left( x[n] - \hat{x}[n] \right)$$ $$x[n] = \hat{x}[n] + g[m]d[n] = \sum_{k=1}^{K} a_k x[n-k] + g[m]d[n]$$ where $m \triangleq \mathrm{floor}(n/N) \$ and $g[m] \ge 1$

so there are fewer $g[m]$ values to encode, one for every $N$ samples. that's ADPCM. this is slightly lossy if $g[m]$ ever exceeds 1.

another scheme (Huffman) is to encode the difference values $d[n]$ with fewer bits than 16 bits (on average) using a little bit of Shannon Information Theory. this is lossless and is essentially what file compression programs like PKZIP did originally. the idea is that values of $d[n]$ that are 0 or +1 or -1 or +2 or -2, etc., will appear far more often than differences like +65535 or -65535 (which would be possible, just not likely, with 17-bit integer values of $d[n]$). Huffman coding, which assigns fewer bits to the most common messages and more bits to the more rare messages, is another big topic that i will leave for later.

• You know, the very first thing I tried was delta + huffman encoding, though that did not achieve good compression (only about 15% compression). It sounds like DPCM is more complicated than that, so I'll have to look into it. How do you go about finding good coefficients? That sounds non-straightforward. – Justin Olbrantz May 5 '14 at 0:31
• On the delta + huffman encoding topic, I was quite surprised how wide the variability was of the delta values, resulting in the poor compression ratio. Presumably it would be much more efficient with 8-bit samples. – Justin Olbrantz May 5 '14 at 0:32
• well, 8-bit samples are pretty compressed the way they are. how big were the deltas? and, with Huffman, how was your "code book" derived, and was it fixed (so you need not transmit it along with the data)? – robert bristow-johnson May 5 '14 at 2:09
• look up LPC to find out how to find good predictive coefficients. it has to do with the auto-correlation of the data. the more "white" your signal is, the less that LPC can do to predict the next sample. – robert bristow-johnson May 5 '14 at 2:11
• The comment about 8-bit was saying I expect 8-bit would delta-compress better than 16-bit because the number of possibilities and the distance between samples is smaller (i.e. huffman encoding would be more effective) – Justin Olbrantz May 5 '14 at 4:10