Browse Prior Art Database

Packed Lempel-Ziv-Welch Compression

IP.com Disclosure Number: IPCOM000033724D
Publication Date: 2004-Dec-23
Document File: 2 page(s) / 27K

Publishing Venue

The IP.com Prior Art Database

Abstract

The LZW algorithm produces a series of tokens T that are integers within the range 0 to N, where N is a known variable. Traditionally the tokens are packed into a bit stream by writing B bits, where B is the smallest integer such that 2B ³ N. With additional logic, it is possible to improve the packing efficiency and save approximately a half a bit per code. The lowest significant bits (LSBs) of the token T are examined. If a one in the most significant bit (MSB) would result in a token larger than N, then this bit is extraneous, and may be omitted from the bit stream.

This text was extracted from a Microsoft Word document.
This is the abbreviated version, containing approximately 59% of the total text.

Packed Lempel-Ziv-Welch Compression

The LZW algorithm produces a series of tokens T that are integers within the range 0 £ T £ N, where N is a known variable.  Traditionally the tokens are packed into a bitstream by writting B bits, where B is the smallest integer such that 2B ³ N. 

The traditional encoding fails to make use of the fact that token values are bound by the upper limit N.  With a very small amount of additional logic, it is possible to improve the packing efficiency and save approximately a half a bit per code.  The lowest significant bits (LSBs) of the token T are examined.  If a one in the most significant bit (MSB) would result in a token larger than N, then this bit is extraneous, and may be omitted from the bitstream.

Writing A Token

Tokens are written to the bit stream using the following C code fragments:

Original Implementation New Implementation

/* writes the LSBs of Token to the bitstream */

WriteBits(unsigned long Token, int number_of_bits);

.

.

.

int T;  /* Token value to be written   */

int B;  /* number of bits per token    */

int N;  /* upper limit of Token values */

.

.

.

WriteBits(T,B);       /* write the token */

 

/* writes the LSBs of Token to the bitstream */

WriteBits(unsigned long Token, int number_of_bits);

.

.

.

int T;  /* Token value to be written   */

int B;  /* number of per token         */

int N;  /* upper limit of Token values */

int M;  /* mask for LSBs of the token  */

.

.

.

M=(1<<(B-1))-1;       /* calculate the mask */

WriteBits(T,B-1);     /* write one less bit */

/* only write the last bit if it’s required */

if((T&M)<=(N&M))        WriteBits(T>>(B-1),1); 

 

 

In actual code, the value of M is only recalculated when B changes values.  There are some other rather simple o...