Easy Analog Data Compression

A low-footprint compression technique for when efficiency really matters. When I needed to implement a lossless data compressor for 16-bit ECGs (electrocardiograms), EEGs (electroencephalograms), and other medical signals in C on a 16-bit integer processor, I discovered how little value the majority of compression techniques were for my problem. Nearly all of the techniques I found on the Internet and in computer science literature rely on two fundamental techniques. The first technique consists of repetitive patterns (known as the Lempel-Ziv family of algorithms, such as gzip) that can be encoded in an efficient way. The second technique uses a family of approaches (known as entropy coding or Huffman coding) that exploit the fact that the individual numbers/letters found in the raw data are usually not equally probable. Both techniques make use of look-up tables -- the larger the tables, the better the chance for good compression ratios. That was another challenge in my project. My algorithm should use less than 2KB of data memory for up to four independent channels and should not need more than 1,000 instruction words. I needed something very simple but effective.

To the untrained human eye, an ECG appears to be extremely repetitive (see Figure 1). Each heartbeat yields a waveform that looks very much like the preceding heartbeat, but the data values differ slightly. The barely visible differences of the high-resolution signals make the compression with standard techniques nearly impossible. In an experiment, I assessed that a standard version of gzip reduces the size of my ECG by barely five percent although I consider myself quite healthy. An EEG curve (see Figure 2) is so irregular that zip, pack, and others do an even worse job.

However, I know something that Lempel, Ziv, and Huffman do not. My data consists of digitized signals originating from an analog source. These signals are known to exhibit relatively few big jumps in their signal amplitude. For signals that change slightly over time, "delta encoding" (i.e., the coding of the signed differences between two sample values instead of the sample values themselves), saves a lot of memory. Suppose, for example, you know that the absolute difference between two adjacent samples of the 16-bit signal never exceeds 1,023; you can code the signal as one absolute value of 16 bits followed by the delta values of 11 bits each.

Adaptive Delta Encoding

If a new delta value cannot be represented by the current bit width, then iBitWidthOfCode must be increased. This time the decoder cannot anticipate the change and must be informed. The encoder does this by storing a reserved letter piOVFLCODE[] that exists for every possible delta bit width. When the decoder encounters such a reserved letter, it knows it must increase its iBitWidthOfCode by one. To reduce excessive coding of piOVFLCODE[] when iBitWidthOfCode gets so small that merely signal noise is coded, I have introduced the lower bound MIN_BIT_WIDTH.

I also have reserved two other letters: piALIGNCODE[] indicates that the next code is aligned with the next word boundary, an indication I need to implement flushing; piABSCODE[] indicates that an absolute code (a raw sample value) follows, aligned with word boundaries.

These reserved letters are chosen to flank the largest and smallest possible two's complement numbers of the delta code. If a delta value matches a reserved letter, the bit width must be increased before the value can be encoded without ambiguities. Hence, I use the reserved letters in storeDelta16 to check if iBitWidthOfCode must be increased. If this is the case, then the appropriate piOVFLCODE[] is stored, and storeDelta16() is called recursively with an increased bit width.

The function storeX, called in storeDelta16, concatenates the codes of variable bit lengths that are passed as parameters. As soon as a WORD (16 bits) is complete, it passes it to writeCode. Any code fraction that is cut off when completing a WORD is kept in the buffer iXcode. The function writeCode represents the interface of a device driver, which is supposed to accept 16-bit-entities only. In my application, data needs to be transmitted via a serial interface and written to flash memory. An additional requirement is to be able to flush the buffer iXcode at any time. This is possible by calling flushX, which checks if there is anything buffered in iXcode. If this is the case, it will add the aforementioned piALIGNCODE[] to the output and pass the content of iXcode to writeCode, although not all of its 16 bits are meaningful. When the decoding algorithm reads the reserved letter piALIGNCODE[], it knows that any undecoded remaining bits of the WORD at hand can be dismissed, and the next delta code will be found in the next WORD.

Prediction

However, if you can extrapolate the signal curve and predict the new sample value with reasonable accuracy, then you may encode the difference between the prediction and the actual sample value to further reduce the size of the delta code. The function encoder_storeADEPT shown in Listing 1 performs these compression steps.

I call the compression technique ADEPT (adaptive delta encoding with prediction). The prediction step itself may be chosen according to a model of the signal, heuristics, similarities to other signals recorded simultaneously, etc. Signal prediction is a complicated matter that could fill entire books or at least book chapters [1]. I decided to implement a simple linear extrapolator instead of spending the rest of my days trying to understand those books. The predictor given here records the history of the last three samples, tries to fit a line through them, and extrapolates linearly.

As you can see in encoder_storeADEPT, I have arranged the computations of the predictor such that first I do the division and then the multiplication. This makes an integer overflow less likely in case you rewrite the function to deal with 32-bit data. If the prediction fails completely, it may happen that the generated delta code cannot be represented as a 16-bit number anymore. Then the algorithm resets the predictor, writes the reserved letter piABSCODE[], and finally writes the sample directly, word aligned, without delta encoding. If no absolute code is needed, encoder_storeADEPT passes the delta value to storeDelta16.

Note that the simple predictor presented above assumes a rather continuous signal. It improves the compression for EEG signals or breathing curves, but performs very poorly for ECGs. Having no prediction step at all is sometimes better than having an inappropriate one: heartbeats of a very high amplitude may irritate the presented predictor so much that pure adaptive delta encoding outperforms adaptive delta encoding with prediction.

Decompression

Decode does this division into delta values in a while loop. As a bitmask for this job, it uses mpiABSCODE[]. The obtained delta code iSubword might represent a negative number, but it might be a positive 32-bit two's complement number and therefore must be sign extended. Think of the number 0xFF. In an 8-bit two's complement representation, it is interpreted as -1. It must be negative because the MSB (most significant bit) is 1. In a 32-bit system, this is interpreted as the positive number 255. Its MSB is 0. To interpret the number correctly in the 32-bit system, the bits to the left of the sign bit of the small-scale representation must hold a copy of this sign bit. In our example, 0xFF will be converted to 0xFFFFFFFF, which is interpreted as -1. This technique is called sign extension.

After the sign extension of iSubword, Decode checks if the obtained code is a reserved letter. If so, it changes the object's state to be able to react appropriately; else it reconstructs the original data by calling the member function DeltaDecode and stores the result in the vector named by the constructor.

Listing 3 shows an example program that uses ADEPT compression and decompression.

Performance and Application

ADEPT performs well if the difference between two subsequent samples is small and/or the signal form is fairly linear. In the ideal case (i.e., when a strictly linear signal is compressed), ADEPT exhibits a compression ratio of 16:MIN_BIT_WIDTH. With a reasonable value for the minimal bit width, it is obvious that the best compression ratio that can be achieved with ADEPT is between 16:3 and 16:4, or 18 and 25percent, respectively.

Obviously a noise-free, repetitive signal can be more compressed by zip and pack than by ADEPT, which cannot go beyond the mentioned threshold. However, signals coming from natural sources are rarely exactly repetitive, therefore the aforementioned bad performance of gzip on an ECG. However, a comparison of ADEPT to gzip is unfair. Each of the algorithms has a very different application domain. Hence the attempt to compress an EEG with gzip must fail, and you should compare ADEPT to other techniques.

The strengths of ADEPT are most of all simplicity, no need for floating-point arithmetic, small memory requirements, and zero delay. The latter needs explanation: compression techniques based on so-called FIR filters inherently introduce a time delay. This may be very annoying when real-time performance is desired.

An obvious weakness of the technique is its dependency on scale (i.e., on the gain factor of the analog/digital converter); a higher gain value will lead to larger delta values for the digitized data and thus needs a wider code. Simplicity pays its price when you compare ADEPT to specialized algorithms, as shown in Table 1. Note that such comparisons are very difficult, because they are hardly ever objective. This is especially true when different input data is used to assess the performance of the respective methods, which is the case here.

Changes of the signal scale may increase or decrease the compression ratio of ADEPT given in Table 1 by about five percent. Most likely, the same is true for the two reference ECG compressors, but no figures were given in [2]. The EEG compressor in [3] is probably the most powerful known, but it is so specialized that it cannot encode arbitrary signals without losses.

A nice feature of the algorithms ALZ77 and ADPCM Subband Coding is a smooth transition from lossless to lossy compression, a step that is difficult with DPCM, ADEPT, or entropy coding. When tuning ADEPT, you should note the comparatively little compression gain when improving the prediction because of the logarithmic dependency between the delta code width and the prediction error.

Conclusion

Further Reading

[2] R. Nigel Horspool and Warren J. Windels. "An LZ Approach to ECG Compression," Proceedings of the 1994 IEEE 7th Symposium on Computer-Based Medical Systems. See also <www.csr.uvic.ca/~nigelh/Publications/ECG-compression.pdf>.

[3] Zlatko Sijercic, Gyan Agarwal, and Charles Anderson. "EEG Signal Compression with ADPCM Subband Coding," Proceedings of the 39th Midwest Symposium on Circuits and Systems, Aug 1996. See also <www.cs.colostate.edu/~anderson/res/eeg/>.

[4] John G. Proakis. Digital Communications, 3rd Edition (McGraw-Hill, 1996), Chapter 3.

About the Author