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...