Data compression for large amount of binary data

Question

In an embedded application of mine, the device generates a large amount of instrumentation data that is stored every few minutes in an NVM, such as a set of EEPROMs or a Data Flash. This data is downloaded from the device by field personnel using a slow serial(RS-232) connection at a baud rate of 9600bps. Just to give you an idea, the data for one instance is 64 bytes, stored every 15 minutes, for 180 days. With protocol overheads, this takes well over 25-30 minutes to download, which is a hassle. The data is then analysed at a central station on PC grade systems. Also the system is extremely cost sensitive, and any savings in NVM costs are welcome.

I was looking for some reasonable compression schemes that I can use for compression the data during storage. The scheme that I was thinking off was to buffer a certain number of instances in a smaller NVM device and compress them at one go after the buffer is full. I tried using an implementation of the LZW algorithm, but could not go under 75% compression rate. A sample of the data is as reproduced below. These are hexadecimal values.(Each instance is only 32 bytes in this sample.)

00 12 23 09 12 5A 69 5B 4E 5B 96 00 3B 00 21 F7
00 44 03 2F 03 B6 01 D6 00 00 5A 4B 58 00 00 FD
15 12 23 09 12 5A 0E 5A F2 5B 19 00 3B 00 24 14
00 50 03 66 03 F7 02 08 00 00 5A 4D 51 00 00 4B
30 12 23 09 12 59 DF 5B 71 5A AA 00 3C 00 27 15
00 67 03 D9 04 9C 02 7B 00 00 59 4D 53 00 00 A7
45 12 23 09 12 59 AF 5B 61 5A 97 00 3D 00 27 52
00 54 03 93 04 38 02 3A 00 00 59 4E 52 00 00 A5
00 13 23 09 12 5A 08 5B A8 5A DF 00 3B 00 27 AF
00 50 03 61 03 F2 02 03 00 00 58 4E 56 00 00 56
15 13 23 09 12 5A 7E 5C 67 5B 95 00 3B 00 28 AC
00 5B 03 A2 04 56 02 53 00 00 57 4D 50 00 00 5D
30 13 23 09 12 5B 72 5C CE 5C 35 00 3B 00 28 94
00 63 03 CA 04 A1 02 A3 00 00 57 4B 4F 00 00 95
45 13 23 09 12 5B 41 5C 3E 5C 45 00 3B 00 28 30
00 51 03 84 04 2E 02 3F 00 00 58 4C 50 00 00 C1
00 14 23 09 12 5A E8 5B ED 5B ED 00 3C 00 28 78
00 4D 03 6B 04 15 02 35 00 00 56 4D 48 00 00 0A
15 14 23 09 12 5A FA 5B EA 5B 95 00 3D 00 27 AC
00 67 03 DE 04 B5 02 A3 00 00 58 4E 49 00 00 6B
30 14 23 09 12 5A 2B 5A FD 5A F2 00 40 00 27 EF
00 5B 03 B6 04 6A 02 5D 00 00 5A 4E 50 00 00 27
45 14 23 09 12 5A 9D 5B 69 5B 43 00 23 00 16 D7
00 43 02 8F 02 FD 01 7C 00 00 62 59 56 00 00 9F
00 15 23 09 12 5B 6F 5C 2F 5B DC 00 0B 00 06 10
00 4A 01 C7 02 1C 01 18 00 00 5C 50 4F 00 00 BC
15 15 23 09 12 5B E0 5C E9 5C 37 00 0D 00 05 73
00 32 01 6D 01 A4 00 C8 00 00 64 44 3D 00 00 0E
30 15 23 09 12 5B F1 5C C1 5C 36 00 0D 00 04 71
00 30 01 59 01 8B 00 AF 00 00 57 4D 55 00 00 42
45 15 23 09 12 5B E7 5D 04 5C 3C 00 09 00 01 23
00 30 01 36 01 68 00 A5 00 00 5B 4F 56 00 00 8B
00 16 23 09 12 5C 5E 5D 57 5C A8 00 0B 00 01 2E
00 27 01 0E 01 3B 00 91 00 00 62 4F 56 00 00 F6
15 16 23 09 12 5C C1 5D AF 5C D8 00 0D 00 01 2C
00 31 01 4F 01 81 00 B4 00 00 62 48 55 00 00 4A
30 16 23 09 12 5C B2 5D 7D 5C F6 00 0C 00 02 34
00 27 01 1D 01 4A 00 9B 00 00 64 4A 3B 00 00 EC
45 16 23 09 12 5D 2D 5D 68 5D 23 00 08 00 02 8E
00 2E 01 22 01 54 00 A0 00 00 62 49 56 00 00 B9
00 17 23 09 12 5C C4 5D 76 5C C3 00 08 00 02 8F
00 22 00 F0 01 13 00 7D 00 00 59 49 57 00 00 64
15 17 23 09 12 5C E5 5D C8 5D 1B 00 08 00 02 AE
00 27 01 09 01 2C 00 87 00 00 64 4A 40 00 00 2D
30 17 23 09 12 5D 1A 5D F2 5D 0E 00 09 00 02 3F
00 28 01 0E 01 31 00 87 00 00 64 4A 57 00 00 0B
45 17 23 09 12 5D 2C 5E 09 5D 65 00 09 00 02 A9
00 25 01 09 01 2C 00 82 00 00 5C 49 40 00 00 3D
00 18 23 09 12 5D 1B 5D 4B 5D 4A 00 09 00 02 D8
00 28 01 13 01 3B 00 8C 00 00 64 4A 58 00 00 F6
15 18 23 09 12 5D 2B 5D 96 5D 97 00 09 00 02 1B
00 22 00 F0 01 13 00 78 00 00 62 4A 57 00 00 5F
30 18 23 09 12 5B C6 5B F5 5B EE 00 09 00 00 B7
00 2B 01 18 01 3B 00 8C 00 00 61 00 58 00 00 3B
45 18 23 09 12 5A E1 5B 10 5A EF 00 09 00 00 6D
00 33 01 3B 01 5E 00 96 00 00 61 00 58 00 00 E3
00 19 23 09 12 5A F3 5B 1E 5B 23 00 09 00 00 5C
00 29 01 0E 01 2C 00 7D 00 00 62 00 58 00 00 64
15 19 23 09 12 5A AC 5A DF 5A E3 00 0A 00 00 0E
00 28 01 13 01 2C 00 78 00 00 61 00 3C 00 00 82
30 19 23 09 12 5A 9C 5A B2 5A CC 00 0A 00 00 47
00 2A 01 09 01 1D 00 69 00 00 62 00 5B 00 00 88
45 19 23 09 12 5A BA 5A DB 5A EA 00 0A 00 00 CD
00 27 01 09 01 22 00 69 00 00 62 00 5A 00 00 87
00 20 23 09 12 5A EA 5B 0E 5B 41 00 0A 00 00 4F
00 1D 00 DC 00 EB 00 55 00 00 62 00 5B 00 00 0A
15 20 23 09 12 5B 5D 5B C0 5B B8 00 0A 00 00 9D
00 27 01 09 01 22 00 6E 00 00 61 00 5B 00 00 82
30 20 23 09 12 5B C0 5B AB 5B EF 00 0A 00 00 FD
00 26 01 0E 01 22 00 73 00 00 62 00 5A 00 00 79
45 20 23 09 12 5B E0 5B FC 5B F8 00 0A 00 00 6E
00 27 01 09 01 22 00 73 00 00 61 00 59 00 00 7F
00 21 23 09 12 5C 30 5C 65 5C 6E 00 0A 00 00 80
00 1D 00 D7 00 F0 00 5F 00 00 61 00 5A 00 00 02
15 21 23 09 12 5C 55 5C 93 5C 9B 00 0A 00 00 EB
00 1D 00 E1 00 F0 00 55 00 00 61 00 5A 00 00 02
30 21 23 09 12 5C EE 5D 4A 5C FE 00 0A 00 00 1C
00 23 01 04 01 1D 00 69 00 00 61 00 9D 00 00 53

Can someone point me to a suitable algorithm to compress the above data? The algorithm should have a small memory(RAM) footprint (<5kBytes or so).

The implementation that I tried is from here.

EDIT 1: I Just had an epiphany, where I lined up each 32/64 byte record one under the other and traversed it vertically. This way, that data turned out to a lot more repetitive and I am now getting much better compression rates.

I am still open to other approaches, however.

Answer 1

You have about 1 Mbyte of data to store. EEPROM is cheap in the scheme of things. The expensive part is waiting 20 minutes to capture the data. The obvious answer there is to increase the baud rate.

At 115.2 kBaud the transfer would take 12 times less, or about 2 minutes after accounting for some protocol overhead. So go fix the firmware to use a reasonable baud rate.

Answer 2

From what I can tell, the first few bytes are a date stamp, and the remaining fields have values that are somewhat similar between records.

We have had to deal with the same issue sending data over an expensive satellite connection. Some ways we reduced the number of bytes were:

One timestamp - Instead of time stamping every record, have one timestamp for the data for X number of records. You know your sample rate is fixed so you know what the times of of the next records will be. We do it every X number of records just in case there was a glitch where a record was not saved or a packet missed by the satellite. e.g.

timestamp1,A1,B1,C1
timestamp2,A3,B2,C2
timestamp3,A3,B3,C3

becomes

timestamp1,A1,B1,C1,A2,B2,C2,A3,B3,C3

Deltas - If the measurements are not changing by much between samples, then perhaps send the differences between measurements instead. e.g.

timestamp1,A1,B1,C1,(A2-A1),(B2-B1),(C2-C1),(A3-A2),(B3-B2),(C3-C2)

The differences might be able to be expressed with less bytes than the absolute values, saving space. Of course it is possible that one of the differences is too large then. In this case you may have corrupted data, but that is another reason to limit the number of records before repeating the process with a new timestamp and new deltas.

Something completely different - In another project we did something completely different. Instead of downloading the data, we attached a serial logger to the serial port, and got the instrument to output each record to it. Retrieving the data then involved removing the SD card and saving the file to disk. We also added a button to press before removing the disk, to stop the writing to the card while it was removed.

Answer 3

What about looking at the problem at a higher level?
The data you present is very raw, it seems hard to find patterns that can be used to minimize storage/transit requirements. Having a view of the higher level data and what information is intended to be retrieved (rather than what binary is presently stored) would help.

For instance, I had a similar issue (instrumentation, every 15 minutes, saved to EEPROM, slow connection, etc) and my solution passed by using the data's context: if there were missing samples in time (my data was timestamped) I would assume all missing values where the same as the last one recorded before the missing ones.
That sort of approach might get you in a different league than just compressing data a-la LZW.

Answer 4

As suggested by geometrikal, extract the timestamp and only send it once and use delta encoding. Then group the fields into those which "always" have a zero delta, those which typically have very small deltas (e.g., magnitude less than four), those which typically have small deltas (e.g., magnitude less than 16), and those which are more variable.

For the "always" zero delta group, use a run length encoding across the group encoded vertically/through time (a 16-bit count might be convenient, though 15-bits would be enough). If deviations in this group are typically singular (so two sequential deltas would be non-zero and identical in magnitude and opposite in sign), the default value (possibly a hard constant, possibly transmitted at the beginning of each data set) a one-group break should be assumed with the next runlength using the default value. I.e., this group would be encoded optional_starting_default_value, run length of default value, exceptional_value, run length of default value (note that one can have a zero run length if two exceptional values occur adjacent to each other). If deviations come in bursts which are highly variable, it may be desirable to use a run length to describe the length of the burst, which length value would be followed by the sequence of variant delta values. If deviations are not extremely rare or it is undesirable for exceptional conditions to explode bandwidth demand, runlength encoding individual fields rather than the entire group of "always" zero delta would probably be more desirable.

For the small and very small delta groups, you could use a Huffman encoding of sequences of the small delta values with one escape code. The size of the table and each entry in the table can be adjusted by changing the length of the sequence. E.g., the very small delta (-3 to 3) table with a sequence length of four would have 32 entries and the size of each entry might be 32 bits (there might be a five bit length field with upto 27 bits for the encoding); with a sequence length of eight the table would have 64 entries and the size of each entry might be 64 bits. Alternatively, you could just use the delta value/escape code sequence to completely avoid the need for a table. Any high delta values (corresponding to the escape codes) could be listed in unencoded form after the encoded value. (If you intend use LZW after this encoding step, there is probably not much benefit in Huffman encoding the sequence since LZW uses a Huffman encoding step. If simple delta or escape value encoding is used with a later LZW pass, a greater sequence length would be desirable to keep together the delta values which vary little so that substitutions are more common given that there is no concern about table size.) (Note that the data set might need to be zero padded to provide a full length sequence for the last sequence.)

For the more variable fields, if a later LZW pass is to be used, just using the delta values would probably be good enough. Huffman encoding these fields might require an excessively large table.

As you noted in your edit, each field should run as long as practical if you are using an LZW pass. (The "always" zero delta fields can be grouped together to trivially decrease the size--one run length count for the entire data set when none of the values change versus one run length count for each field--, but this is probably not a worthwhile optimization.)