Browse Prior Art Database

Using Absolute References in Universal QIC-122 CODEC

IP.com Disclosure Number: IPCOM000108927D
Original Publication Date: 1992-Jul-01
Included in the Prior Art Database: 2005-Mar-23
Document File: 2 page(s) / 113K

Publishing Venue

IBM

Related People

Medan, Y: AUTHOR

Abstract

This article outlines an absolute address referencing scheme for LZ-1 Type algorithms such as QIC-122 Codec. The scheme preserves the same compression efficiency as in a relative addressing approach with the advantage of simplified hardware. It shows that additional hardware savings can be realized if a marginal and bounded increase in compression efficiency is tolerable. The novel feature is that it offers a simplified realization while assuring the exact same level of compression efficiency delivered by an equivalent, relative addressing QIC- 122 scheme. This is accomplished by eliminating the 11-bit address adder required in QIC-122 and its derivatives, and replacing it with either a 7-bit comparator or 128 Bytes of a shadow circular RAM buffer.

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

Using Absolute References in Universal QIC-122 CODEC

       This article outlines an absolute address referencing
scheme for LZ-1 Type algorithms such as QIC-122 Codec.  The scheme
preserves the same compression efficiency as in a relative addressing
approach with the advantage of simplified hardware.  It shows that
additional hardware savings can be realized if a marginal and bounded
increase in compression efficiency is tolerable.  The novel feature
is that it offers a simplified realization while assuring the exact
same level of compression efficiency delivered by an equivalent,
relative addressing QIC- 122 scheme.  This is accomplished by
eliminating the 11-bit address adder required in QIC-122 and its
derivatives, and replacing it with either a 7-bit comparator or 128
Bytes of a shadow circular RAM buffer.

      Significant hardware simplifications may result if an absolute,
rather than a relative, addressing scheme is used to reference the
strings in QIC-122 Codec (see (*)).  The absolute references are
coded for a circular buffer that serves as the history "window" used
to encode new strings.  The maximum size of the buffer is dictated by
the size of the "long_offset" field of QIC-122, namely, 11-bits or
2KB of addressing span.  The "long_offset" values in QIC-122 can be
substituted with absolute addresses to a 2KB circular buffer with no
loss or gain in compression efficiency.  However, a "short_offset"
field of only 7 bits may translate to either 7 or 11 bits of an
absolute address which may degrade the compression level achieved by
QIC-122.  To overcome the deficiency, it is proposed to maintain the
same field length of both the original 7-bit "short_offset" and its
absolute address reference.  This is done by having a simple 7-bit
comparator in the decoding circuitry to allow the regeneration of a
complete 11-bit absolute reference into the circular buffer without
having need for an ALU.  The object is to segment the 2KB circular
buffer into 16 logical segments of 128B each, called pages (0 to 15).
A page is referenced as a 4-bit entity that can be extracted from the
4 most significant bytes (MSBs) of a given absolute address in the
circular buffer.  Thus, each absolute address can be written as
PAGE.DISP where PAGE is the page number and DISP is a 7-bit unsigned
integer that indicates the displacement of the address relative to
address 0 of the current page.

      Denote by ADDR0=PAGE0.DISP0 the absolute (11-bit) address of
the current symbol to be encoded, while ADDR1=PAGE1.DISP1 denotes the
absolute address of the same symbol that was found in the history
buffer.  For a relative distance between the characters that is
greater than 127, the "long_offset" fiel...