Algorithm for compressing a stream of 12-bit ADC data in a Cortex M0 microcontroller

Question

In my application, a Cortex M0 microcontroller currently samples an ADC signal at 10 kHz and sends the result via a USB serial cable to a computer.

I want to now increase the sampling rate to over 100 kHz and add a second channel.

The USB-serial link is limited to 1-3 Mbps, so it is physically impossible to stream at this rate with a 12 bit ADC value and 2 bytes needed to transfer each sample. For two ADC channels sampling at 100 KHz, the bit rate required is approximately 4 Mbps: $$bit\_rate = 2 ch \times 2 bytes \times 10 bits\times 100\times 10^3 = 4 \times 10^6 bps$$

I am aware that I could fit 2 ADC samples into 3 bytes, but I want to compress the ADC data somewhat.

What are some compression algorithms that are suitable for running in a Cortex M0 microcontroller?

There are dozens of compression algorithms, but I'm looking for something that can run on a resource-constrained platform.

Answer 1

Is this actually an audio application? Could you replace the whole thing with a dedicated audio interface which will solve all these problems for you, or do you need the precise DC level? 96ksps stereo is quite attainable.

You do not have a lot of MIPS to work with, so I'm going to propose the following coding scheme. It is technically variable bitrate, so you'd better hope that transients are rare. It works for samples up to 15 bit.

• Keep track of previous sample
• Subtract next sample from previous sample, call the result D
• Examine bits above 7. Either they're all-ones, or all-zeroes, or a mix (indicating a transient or large slew).
• For the all-ones or all-zeroes cases: mask off the bottom 7 bits, transmit to host.
• For the transient case: transmit the upper byte of the sample (not D) with the top bit set to "1", then the lower byte.
• Periodically (e.g. every 256 samples), send the whole sample anyway with the top bit set to 1. This allows recovery from errors.

Reconstructing is simple:

• if the top bit of a byte is 0, sign-extend the remaining 7 bits and add them to the previous sample to get the next sample.
• if the top bit is 1, mask it off, read the next byte and assemble the result into a word.

Answer 2

There are a few "simple" steps you can take to reduce the needed baud rate :

1. Do you really need 12 bits resolution? If you can sacrifice the 4 least significant bits (which might be only noise), you reduce the required bandwidth by 33%, and save a few operations in the same time.

2. by which amount is the signal "usually" changing between 2 successive samples. For example, if 95% of the time, the difference is only on the 6 least significant bits, you can send :

• if the difference is less than 6 bits, the difference as encoded as a signed integer on 7 bits (with a 1 as most significant (8th) bit) -if the difference is more than 6 bits, you send the whole new value on 2 bytes (so there will be 4 heading zeros on the most significant byte, making it easy to identify)

Finally, one interesting thing you said in the comments is that you need such high sampling rate because you want to observe transients.

Therefore, I see 2 solutions, a bit more complicated, but that might reduce significantly the baud rate needed for your specific application:

3. If you need only the transients : why not to "trigger" on them? You store all your measurements in a rolling buffer (using DMA if you can). Then you use some software computation to define a transient (for example, difference greater than X between measurement N and N-N0). If you detect one, you send only the values around measurement N. If your transients are rare, your required baud rate becomes really low. NB : in this version, you see ONLY the transients, not the rest (might or not suit your needs, if not, see solution 4)

4. Another solution is not to send samplings with regular time intervals : you still sample at 100kHz (stored to internal buffer with DMA), but you only transmit part of the data : when data is changing fast, you send a lot of data, when it is changing slowly, you send few. For example :

• lets say the last measurement sent is M[N0] (measurement at sampling #N0, 12 bits)
• lets call N the current measurement (value=M[N]. If N-N0 == 16, then X, with the 12 least significant bits of X being M[N], and the 4 most significant ones being N-N0-1 = 15 = 0b1111
• else if abs(M[N]-M[N0]) > threshold : sent X (2 bytes), with M[N] for the 12 least significant bits, and N-N0-1 for the 4 most significant bits (ie the number of measurements you skipped)
• else : send nothing.

So basically, on the receiving side, you receive value in the form A[0:3].M[0:12], with A being the number of samples skipped (so (A+1)sampling_period the time since last sample), and M the value of that sample. If your signal is changing slowly enough and transients are rare, you will have an average of A between 14 and 15 (let's be conservative and say 14), so you have an average bit rate of 2ch16bits*100000Hz/15=213 kb/s : that's easily done on a 1Mb/s UART

Answer 3

Doing so will have significant computational overhead, you need to make sure you can do everything in time. You will have to go through the entire data multiple times, this is of the order O(n). Because you obviously can't do it without going through all data at least once and you need to do something with it too. Maybe you can save some time on automating send procedure - you can have a timer trigger interrupts regularly and then trigger transmission of the data with DMA. This will free up some computational power. If you need it that is, maybe you can handle it all the simpler way and still get it done. (you didn't even post MCU and frequency it operates on, as of writing this)

You can have either static or dynamic compression dictionary (what substitutes with what). If it's static, you can hardcode it on the receiving end to decompress. If it's dynamic, it will take more computation on MCU side to generate it and you will also need to transmit it as data to the receving side (PC), because it needs to decode it.

First, make a guesstimate on what kind of values your ADC returns more often. Maybe you'll want to compress most significant bits. You'll have to search for some specific algorithms, but I think there is no way to do it without giving up some bandwidth, because what you send needs to be distinguishable - are you sending actual raw data or compressed data or dictionary? For example, you can hardcode that every 16 bytes you will send a byte that will be a dictionary for the next 16 bytes (or more, but then your compression could get worse because of how various data is). Which means your compression needs to be good enough to overcome this overhead and still increase overall amount of data transmitted.

But step number 1 is always estimating if there is anything in the data to compress. If you expect all possible values to be totally random all the time, there is not much that you can do, you may want to discard some measurements then. This is simply your hardware limitation. You can only get so much with it.

Answer 4

Do your processing on the ARM and send a processed result

You only need full-bandwidth comms with the PC if you're planning on the ARM being just a dumb USB ADC and all the clever stuff happening on the PC. If you put the processing on the ARM, you can send stuff back to the PC more slowly.

You say that you're looking for transients. Essentially then we're talking differentiation (looking for a fast rate of change). Having done this recently with work (differentiating position to give velocity and acceleration, and then running closed-loop position-velocity-acceleration control), I can tell you that sampling is noisy, and you need significant levels of filtering when you're looking at rate-of-change. If you don't, then false-triggers from noise are going to kill your design. (Bessel low-pass filters FTW, because of minimal overshoot and solid group delay in the passband; and also look at the MZTi transform for a better response as your filter time constant approaches Nyquist.)

Now we have something with more useful data for the PC to work with. But also we have something which can be sent back to the PC more slowly, because if you've low-pass-filtered your data then you don't need to send that data faster than double your new bandwidth.