Browse Prior Art Database

Most-Recent Data Search Scheme for LZ-Type Data Compression

IP.com Disclosure Number: IPCOM000116143D
Original Publication Date: 1995-Aug-01
Included in the Prior Art Database: 2005-Mar-30
Document File: 2 page(s) / 64K

Publishing Venue

IBM

Related People

Murata, H: AUTHOR [+3]

Abstract

Disclosed is a most-recent data search scheme for LZ-type data compression. In LZ compression, input data are searched for in a history buffer and replaced with the pointer to the previous occurrence and the length of the data. When several matching positions are found, the most recent position is selected. However, a priority encoder used in data compression circuit cannot be reset to select one out of several matches according to the distance from the current data.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 76% of the total text.

Most-Recent Data Search Scheme for LZ-Type Data Compression

      Disclosed is a most-recent data search scheme for LZ-type data
compression.  In LZ compression, input data are searched for in a
history buffer and replaced with the pointer to the previous
occurrence and the length of the data.  When several matching
positions are found, the most recent position is selected.  However,
a priority encoder used in data compression circuit cannot be reset
to select one out of several matches according to the distance from
the current data.

      Figs. 1 and 2 illustrate the concept of the new scheme with
examples.  The scheme includes a Content-Addressable Memory (CAM) for
the history buffer, a Priority Encoder (P-ENC), a Mask Pattern
Generator (MASK), and a Mask Controller (M-CTRL).  New input data are
searched for in the CAM and stored at the address p.  The address is
incremented by 1 from 0 to n in each cycle.  When it reaches n, it
returns to 0; thus, the CAM works as a ring buffer.  Therefore, data
in the dark hatching area are newer than those in the bright area
during searching.

      In phase 1 of Fig. 1, four addresses (w, x, y, and z) match the
search data.  Higher addresses have priority over lower addresses in
the P-ENC, and addresses on the mask bit '1' can be encoded only
while the signal ALLENBL is kept Low.  Therefore, the address x is
output as the matching address MADDR.  The entire match signal FOUND
goes high if at least one matching...