Efficient hardware implementation of a compression algorithm

Details Efficient hardware implementation of a compression algorithm Efficient hardware implementation of a compression algorithm

2000-08-29

2002-02-19

Tokar, Michael (Department: 2819)

Coded data generation or conversion

Digital code to digital code converters

Adaptive coding

C341S050000, C341S060000, C341S059000, C341S065000, C341S087000, C341S095000, C341S106000, C375S240000

Reexamination Certificate

active

06348881

ABSTRACT:

BACKGROUND
The present invention concerns data compression and decompression. More particularly, this invention relates to efficient hardware implementation of a compression algorithm.
Data compression can be used when storing or transmitting data in which there exists redundancy. Such compression allows the effective size of data to be reduced without information loss. The density of information is increased allowing for faster transmission times and requiring less storage resources.
The speed of a data compressor is important. Therefore, data compression algorithms are often implemented in hardware in order to reduce the time required to compress and decompress data.
Jacob Ziv and Abraham Lempel proposed two adaptive data compression schemes which construct a dictionary of codes representing unique strings of previous data symbols. These algorithms have been implemented in a number of variations. See for example, the implementations in U.S. Pat. No. 5,339,076, U.S. Pat. No. 5,455,576, U.S. Pat. No. 5,469,161, U.S. Pat. No. 532,693, U.S. Pat. No. 5,532,694, U.S. Pat. No. 642,112, U.S. Pat. No. 5,771,010, U.S. Pat. No. 5,818,873, U.S. Pat. No. 5,828,324, U.S. Pat. No. 5,877,714 and U.S. Pat. No. 5,936,560.
SUMMARY OF THE INVENTION
In accordance with the preferred embodiment of the present invention, logic circuitry performs a matching algorithm function. A memory produces a match signal that indicates which memory cells contain data that matches input address data to the memory. A first logic AND function performs a logic AND between a current value of the match signal currently produced by the memory for the input address data with a prior value of the match signal produced by an immediately prior input address data. A buffer holds index data. A second logic AND function compares output of the first logic AND function with the index data. Output of the second logic AND function is returned to the buffer as new index data. Index logic generates an offset based on the index data stored in the buffer. A send byte function asserts a send byte signal when the match signal is zero and when the output of the second logic AND function is zero. A length counter is incremented for every cycle in which the send byte signal is not asserted.
In a preferred embodiment of the present invention, an offset ready logic generates an offset ready signal when the output of the second logic AND function has only one bit set to logic one. Also, substitution logic substitutes all logic ones for the index logic as input to the second logic AND function on a cycle immediately after the send byte signal is asserted.
Also, in one embodiment of the present invention, the memory is implemented as a content addressable memory (CAM) in which data is not shifted. In this case, a first shift function performs a one bit shift of the prior value before the prior value is received by the first logic AND function. Also a second shift function performs a one bit shift of the index data before the index data is received by the second logic AND function. These two functions are not required when the memory is implemented using a first-in-first-out (FIFO) CAM.
The memory can be implemented using a FIFO CAM. For example, the CAM includes an address input for receiving CAM address signals. The FIFO CAM also includes a plurality of CAM cells tiled together.
Each CAM cell includes a cell address input for receiving the CAM address signals. A data input receives data to be stored in the CAM cell. Storage logic stores the data received at the data input. A data output presents as output the data stored in the storage logic. Match logic compares the data stored in the CAM cell with the CAM address signals. The match logic produces a match signal that indicates when the data stored in the CAM cell matches the CAM address signals. The CAM cells are tiled together by connecting the data output for one CAM cell to the data input for another CAM cell.
In one preferred embodiment, the storage units are implemented using a plurality of flip-flops. The match logic includes a plurality of logic XNOR gates and a logic NAND gate. Each XNOR gate receives as input a bit of the data stored in the CAM cell, and a bit of the CAM address signals. The logic NAND gate performs a logic NAND function on output from all of the plurality of logic XNOR gates. Also, the CAM cell can additionally include a validity input for receiving a validity bit that indicates whether the data to be stored in the CAM cell is valid. The validity bit is stored in the CAM cell and is presented as output along with the associated data.
The present inventions allows for an efficient hardware implementation of a loss-less compression algorithm that is compatible with the ANSI X3.241-1994 specification (known as Stacker LZS™)


REFERENCES:
patent: 4558302 (1985-12-01), Welch
patent: 5003307 (1991-03-01), Whiting et al.
patent: 5151697 (1992-09-01), Bunton
patent: 5339076 (1994-08-01), Jiang
patent: 5455576 (1995-10-01), Clark, II et al.
patent: 5469161 (1995-11-01), Bezek
patent: 5532693 (1996-07-01), Winters et al.
patent: 5532694 (1996-07-01), Mayers et al.
patent: 5642112 (1997-06-01), Cooper
patent: 5771010 (1998-06-01), Masenas
patent: 5818873 (1998-10-01), Wall et al.
patent: 5828324 (1998-10-01), Clark, II
patent: 5877714 (1999-03-01), Satoh
patent: 5936560 (1999-08-01), Higuchi

Affiliated with

Also associated with

Rating

Efficient hardware implementation of a compression algorithm does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Efficient hardware implementation of a compression algorithm, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient hardware implementation of a compression algorithm will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2960421