2009

Lossless Compression of Data Into Fixed-Length Packets

A computer program effects lossless compression of data samples from a one-dimensional source into fixed-length data packets. The software makes use of adaptive prediction: it exploits the data structure in such a way as to increase the efficiency of compression beyond that otherwise achievable.

Adaptive linear filtering is used to predict each sample value based on past sample values. The difference between predicted and actual sample values is encoded using a Golomb code. The particular Golomb code used is selected using a method described in “Simpler Adaptive Selection of Golomb Power-of-Two Codes” (NPO-41336), NASA Tech Briefs, Vol. 31, No. 11 (November 2007), page 71. As noted therein, the method is somewhat suboptimal (suboptimality ≤1/2 bit per sample) but offers the advantage that it involves significantly less computation than does a prior method of adaptive selection of optimum codes through “brute force” application of all code options to every block of samples. Hence, the computer program is relatively simple and produces packets relatively rapidly.

The method and, hence, the program are robust to loss of packets: All parameters needed to decompress a packet are encoded in the packet. Therefore, the loss of one or more packets does not diminish the ability to reconstruct samples in remaining packets.

This work was done by Aaron B. Kiely and Matthew A. Klimesh of Caltech for NASA’s Jet Propulsion Laboratory.

This software is available for commercial licensing. Please contact Karina Edmonds of the California Institute of Technology at (626) 395-2322. Refer to NPO-45942.