POCKET++, An efficient, fast compression algorithm for fixed length data structures

Description:

This invention describes a method to losslessly compress and decompress repeating fixed length data structures using very little CPU power and on an individual basis i.e. each instance of a data structure is compressed and decompressed on its own rather than having to wait for a complete group of such structures to be available. It is therefore applicable to real-time compression and decompression of data as well that of the more traditional stored data target i.e. the same process can be used for either. Since it uses very little CPU it can be deployed on low power processors such as those used in spacecraft. 

The most important technical characteristic of this invention is a major adaption to the ESA POCKET+ patent (PAT 703). In that patent an automatic process is used to categorise all the bits in any repeating fixed length data structure (e.g. housekeeping packet or line of an image) into either being predictable or non-predictable. The sense of being predictable here is that those bits have a high probability of being in the same state as those in a reference data set. This reference data set is itself updated automatically. Non predictable bits are masked out of the data structure using a bit mask and the data structure XORed with the reference data to identify any bits where the predication was wrong. Whenever a predictable bit prediction is wrong, its corresponding bit is added to the mask (called a negative update). On the other hand, if a non-predictable bit does not change status for a certain number of cycles then its corresponding bit position is removed from the bit mask (called a positive update). The compressed packet therefore consists of positive and negative updates to the mask plus the states of the non-predictable bits which are sent in the clear. 

This invention introduces the idea of a third status called recently transitioned i.e. bits that have transitioned from predictable to non-predictable (or vice versa) in a configurable history span. These recently transitioned bits are determined by an automatic process. 

On the decompression side, an extra buffer is required to track the recently transitioned bits. In the uncompressed packet, the run length encoded result for this buffer is used to write the inverse state compared to the reference data for those bits that are set and the same state for those that are not. The result is then used to update the ground mask which is then used to allocate the rest of non-predictable bits their correct state in the uncompressed packet. All advantages of POCKET+ are maintained in terms of robustness apart from these extra steps.

Innovations and advantages:

The use of this technology provides the following advantages:

• it makes the compression performance much more predictable for all packets, significantly reducing important parameters such as worst compression rate and standard deviation.
• it significantly reduces the amount of design work required to select telemetry acquisitions, rates and the introduction of asynchronous events.

Domain of application:

The invention is applicable for the compression and decompression of spacecraft housekeeping telemetry data.

Outside the space field, the invention could be used in principle by any application that requires compression with low processing power and uses a central data handling system with long packets. The invention would have to be modified to adapt to this set-up.