6
$\begingroup$

I am working with EMG signals sampled at 2kHz and 16 bits, and noticed that they "look smooth", that is, the signals are differentiable, and if I apply a "diff" function (numpy.diff in my case) the magnitude of the values is considerably lower than the actual samples.

So I am considering to do something like:

  • Split the signal into chunks of a given size;
  • Foreach chunk, using variable length quantity (or similar), create a byte list and:
    • For the first sample of the chunk, add its absolute value;
    • For the remaining samples of the chunk, add their difference, relative to the previous value;

This way, the smoother the signal, and the closer it is to the baseline, the more I expect to decrease the byte-size of each chunk, by decreasing the individual byte-size of a large part of the samples.

Although I suspect this would improve things for me, I also suspect that this is nothing new, and perhaps it has a proper name, and even more elegant/efficient ways to implement it.

So the question is: what is the name of this compression technique, and what are its alternatives and/or variants?

$\endgroup$
  • 3
    $\begingroup$ See en.wikipedia.org/wiki/… $\endgroup$ – MBaz Apr 5 at 19:03
  • $\begingroup$ @MBaz I think your comment contains the correct answer. If you write it down I would most probably accept it. Thanks for now! $\endgroup$ – heltonbiker Apr 5 at 19:19
  • 3
    $\begingroup$ BTW: this is also done in image compresion, in PNG format, line by line (only that for each line you can choose among using difference with respect to the pixel left or up, or other two predictions - or none of them); the standard calls this "filtering", but it's actually a typical "predict and code the prediction error" scheme, of which your technique is a basic case en.wikipedia.org/wiki/Portable_Network_Graphics#Filtering $\endgroup$ – leonbloy Apr 6 at 17:19
6
$\begingroup$

Another notion you might wanna look into for lossless compression of a bandlimited signal (it's this bandlimiting that gets you this "smoother ... signal, ...closer ... to the baseline") is Linear Predictive Coding.

I think this is historically correct that LPC was first used as a variant of Delta coding where the LPC algorithm predicts $\hat{x}[n]$ from the set of samples: $x[n-1], x[n-2], ... x[n-N]$. If the prediction is good, then the real $x[n]$ is not far off from the prediction $\hat{x}[n]$ and you need store only the delta $x[n]-\hat{x}[n]$ which is smaller in magnitude and a smaller word width might be sufficient. You would need to store the LPC coefficients for each block, but there are usually no more than a dozen or so of these.

This stored difference value can be compressed further using something like Huffman coding in which you would need to either store the "codebook" along with the compressed data or have some kinda codebook standardized so that both transmitter and receiver know it.

I think it's some combination of LPC and Huffman coding that is used by various lossless audio formats. Maybe there is some perceptual stuff used to, to get almost lossless compression.

$\endgroup$
9
$\begingroup$

You can also think of delta encoding as linear predictive coding (LPC) where only the prediction residual ($x[n]-\hat{x}[n]$ in @robertbristow-johnson's notation) is stored and the predictor of the current sample is the previous sample. This is a fixed linear predictor (not with arbitrary coefficients optimized to data) that can exactly predict constant signals. Run the same linear predictive coding again on the residuals, and you have exactly predicted linear signals. Next round, quadratic signals. Or run a higher-order fixed predictor once to do the same.

Such fixed predictors are listed in Tony Robinson's SHORTEN technical report, yours in Eq. 4, and are also included in the FLAC lossless audio codec although not often used. Calculating the best prediction coefficients for each data block and storing them in a header of the compressed block results in better compression than the use of fixed predictors.

For $m$-bit input the residual is an $m+1$ -bit number, because it is the difference of an $m$-bit input and an $m$-bit prediction. However, removing the most significant bit (MSB) of the residual has no consequence in $m$-bit modular arithmetic, so the residuals can be stored as $m$-bit numbers.

The linear predictor is supposed to do the whitening, making the residuals independent. In lossless compression, what is left to do is to entropy code the residuals, instead of using run-length or other symbol-based encoding that doesn't work so well on noisy signals. Typically, entropy coding is done by a prefix code (also known as prefix-free code) that assigns longer code words to large residuals, approximately minimizing the mean encoding length for an assumed distribution of the residual values. A Rice code (also known as Golomb–Rice code or GR code) variant compatible with signed numbers can be used, as is done in FLAC (Table 1), or signed exp-Golomb code as is done in the h.264 video compression standard. Rice code has a distribution parameter that needs to be optimized for the data block and saved in the block header.

Table 1. Binary codewords of 4-bit signed integers encoded in Rice code with different Rice code parameter $p$ values, using FLAC__bitwriter_write_rice_signed (source code). This variant of Rice code is a bit wasteful in the sense that not all binary strings are recognized as a codeword.
$\begin{array}{rl} \begin{array}{r}\\-8\\-7\\-6\\-5\\-4\\-3\\-2\\-1\\0\\1\\2\\3\\4\\5\\6\\7\end{array}&\begin{array}{lllll} p=0&p=1&p=2&p=3\\ 000000000000001&000000010&000110&01110\\ 0000000000001&00000010&000100&01100\\ 00000000001&0000010&00110&01010\\ 000000001&000010&00100&01000\\ 0000001&00010&0110&1110\\ 00001&0010&0100&1100\\ 001&010&110&1010\\ 1&10&100&1000\\ 01&11&101&1001\\ 0001&011&111&1011\\ 000001&0011&0101&1101\\ 00000001&00011&0111&1111\\ 0000000001&000011&00101&01001\\ 000000000001&0000011&00111&01011\\ 00000000000001&00000011&000101&01101\\ 0000000000000001&000000011&000111&01111\end{array}\end{array}$

As a further enhancement, encoding not just one but multiple residuals into a single codeword can more accurately accommodate the true distribution of residuals and may give a better compression ratio, see asymmetric numeral systems.

$\endgroup$
  • $\begingroup$ as similar to your suggestion, Subband ADPCM would possibly be the best choice... $\endgroup$ – Fat32 Apr 5 at 21:08
6
$\begingroup$

That's used a lot. See for example https://en.wikipedia.org/wiki/Delta_encoding, https://en.wikipedia.org/wiki/Run-length_encoding.

"Looking Smooth" typically means "not a lot of high frequency content". The easiest way to take advantage of this, is to figure out what the highest frequency really need then low-pass filter and choose an lower sample rate.

IF you signal has a non-flat spectrum, it's typically advantageous to "whiten" the signal, i.e. filter it so that the average spectrum is white, then encode, decode and filter with the inverse signal to recover the signal. This way you spend more bits on the high energy frequencies and less and the low energy ones. Your quantization noise follows the spectrum of the signal.

The scheme that you suggest is one of the simplest forms of this approach: your whitening filter is a differentiator and your inverse filter is an integrator.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.