Dictionary reset performance enhancement for data compression applications
First Claim
1. A dictionary-based data compressor/decompressor system comprising:
- a memory device having L dictionary locations, each location including a first data field for storing a dictionary compression data entry to use in compressing/decompressing input data and a corresponding second data field for storing a dictionary status word comprising at least two binary digits indicating whether the corresponding dictionary data entry is in a valid or reset state;
a data compression engine having data input and output ports and input/output ports for reading and writing to the first and second fields of a selected location in the memory device, the data compression engine including means for compressing/decompressing input data and reading/writing dictionary data entries in the dictionary locations in accordance with a predetermined compression algorithm; and
a dictionary reset optimizer coupled between the memory device and the data compression engine including;
means for generating a dictionary number comprising at least two binary digits; and
means for comparing the dictionary number to the dictionary status word in one of said dictionary locations to determine whether they match in accordance with a predetermined relationship and thereby determine whether the corresponding dictionary data entry is in either a valid or reset state;
the data compression engine being responsive to the comparing means to read the dictionary compression data entry stored in the corresponding first data field if a valid state is determined and to write a new dictionary compression data entry into the corresponding first data field if a reset state is determined.
2 Assignments
0 Petitions
Accused Products
Abstract
A class of lossless data compression algorithms use a RAM-based dictionary to facilitate the compression and decompression of data. The dictionary is initialized or reset at various events, such as data file boundaries, or at specific compression ratio thresholds. The average time to perform the dictionary reset is decreased by using a dictionary reset optimizer (12) to reset the dictionary without writing the DICT-- VALID fields (19) of all dictionary locations (1,2,3, . . . L) immediately upon each reset. The DICT-- VALID field in static RAM (16) is set up as an N-bit field and the optimizer includes a counter (20) for generating an N-bit DICT-- NUMBER field (22) under control of a controller (24) responsive to reset signals. During operation to compress/decompress data after a reset, the DICT-- VALID field of a dictionary location is compared to the current DICT-- NUMBER (1). If their values are equal, the DICT-- ENTRY field (18) in such location is deemed valid. Otherwise, the DICT-- ENTRY field is rewritten with new compression data and the DICT-- VALID field is reset equal to the current DICT-- NUMBER (1). Upon each reset, the counter is incremented to provide a new DICT-- NUMBER (2) whose value will no longer match current DICT-- VALID values stored in the dictionary locations.
78 Citations
21 Claims
-
1. A dictionary-based data compressor/decompressor system comprising:
-
a memory device having L dictionary locations, each location including a first data field for storing a dictionary compression data entry to use in compressing/decompressing input data and a corresponding second data field for storing a dictionary status word comprising at least two binary digits indicating whether the corresponding dictionary data entry is in a valid or reset state; a data compression engine having data input and output ports and input/output ports for reading and writing to the first and second fields of a selected location in the memory device, the data compression engine including means for compressing/decompressing input data and reading/writing dictionary data entries in the dictionary locations in accordance with a predetermined compression algorithm; and a dictionary reset optimizer coupled between the memory device and the data compression engine including; means for generating a dictionary number comprising at least two binary digits; and means for comparing the dictionary number to the dictionary status word in one of said dictionary locations to determine whether they match in accordance with a predetermined relationship and thereby determine whether the corresponding dictionary data entry is in either a valid or reset state; the data compression engine being responsive to the comparing means to read the dictionary compression data entry stored in the corresponding first data field if a valid state is determined and to write a new dictionary compression data entry into the corresponding first data field if a reset state is determined. - View Dependent Claims (2)
-
-
3. A dictionary-based data compressor/decompressor system comprising:
-
a memory device having L dictionary locations, each location including a first data field for storing a dictionary compression data entry to use in compressing/decompressing input data and a corresponding second data field for storing a dictionary status word comprising at least two binary digits indicating whether the corresponding dictionary data entry is in a valid or reset state; a data compression engine having data input and output ports and input/output ports for reading and writing to the first and second fields of a selected location in the memory device, the data compression engine including means for compressing/decompressing input data and reading/writing dictionary data entries in the dictionary locations in accordance with a predetermined compression algorithm; and a dictionary reset optimizer coupled between the memory device and the data compression engine including; means for generating a dictionary number comprising at least two binary digits; means for comparing the dictionary number to the dictionary status word in one of said dictionary locations to determine whether the corresponding dictionary data entry is in either a valid or reset state; and controller means responsive to a reset signal for causing the generating means to generate a new dictionary number so that the comparing means subsequently determines by comparison of the new dictionary number to a prior dictionary number stored in each dictionary location that the dictionary compression data entry stored in such location is in a reset state and causes the data compression engine to write a new dictionary compression data entry into the corresponding first data field and the new dictionary number into the second data field the data compression engine being responsive to the comparing means to read the dictionary compression data entry stored in the corresponding first data field if a valid state is determined and to write a new dictionary compression data entry into the corresponding first data field if a reset state is determined. - View Dependent Claims (4, 5)
-
-
6. A dictionary-based data compressor/decompressor system
comprising: -
a memory device having L dictionary locations, each location including a first data field for storing a dictionary compression data entry to use in compressing/decompressing input data and a corresponding second data field for storing a dictionary status word comprising at least two binary digits indicating whether the corresponding dictionary data entry is in a valid or reset state; a data compression engine having data input and output ports and input/output ports for reading and writing to the first and second fields of a selected location in the memory device, and a single-bit output/input for transmitting/receiving a dictionary status signal to/from the memory device, the data compression engine including means for compressing/decompressing input data and reading/writing dictionary data entries in the dictionary locations in accordance with a predetermined compression algorithm; and a dictionary reset optimizer coupled between the memory device and the data compression engine including; means for generating a dictionary number comprising at least two binary digits; means for comparing the dictionary number to the dictionary status word in one of said dictionary locations to determine whether the corresponding dictionary data entry is in either a valid or reset state; and means interposed between the data compression engine and the memory device for translating between said single-bit output/input and said dictionary status word comprising at least two binary digits; the data compression engine being responsive to the comparing means to read the dictionary compression data entry stored in the corresponding first data field if a valid state is determined and to write a new dictionary compression data entry into the corresponding first data field if a reset state is determined.
-
-
7. A dictionary reset optimizer for a resettable dictionary-based data compressor/decompressor system which includes a memory device having L dictionary locations, each location storing a dictionary data entry and an N-bit dictionary status word, and a data compression engine for reading/writing dictionary data entries in the dictionary locations to compress/decompress input data in accordance with a predetermined compression algorithm, the dictionary reset optimizer comprising:
-
a dictionary number generator for generating an N-bit dictionary number, N being an integer equal to or greater than 2; a dictionary-valid determining means including a binary comparator for comparing the N-bit dictionary number to the N-bit dictionary status word in one of said dictionary locations to determine whether or not the dictionary number and the dictionary status word match in accordance with a predetermined relationship and providing an output signal to indicate to the data compression engine whether the data entry in said one location is valid based on whether the dictionary number and the dictionary status word match; and controller means responsive to a reset condition for causing the generating means to generate a new dictionary number so that the new dictionary number does not match a prior dictionary number stored in each dictionary location. - View Dependent Claims (8, 9, 10, 11, 12, 13, 14)
-
-
15. A dictionary reset optimization method for resetting a dictionary-based data compressor/decompressor system which includes a memory having L dictionary locations each including a multibit dictionary data entry field, and a data compression engine for reading/writing dictionary data entries in the dictionary locations to compress/decompress input data in accordance with a predetermined compression algorithm, the optimization method comprising:
-
allocating storage in each of the L dictionary locations to include an N-bit dictionary status field, N being an integer equal to or greater than 2; generating a first N-bit dictionary number; storing the dictionary number as a dictionary status word in association with a compression data entry in one or more of the L dictionary locations; reading a dictionary status word stored in the dictionary status field of a selected one of the L dictionary locations; comparing the dictionary number to the dictionary status word to determine whether or not the dictionary number and the dictionary status word match in accordance with a predetermined relationship; signalling to the data compression engine whether the data entry in said one location is valid based on whether the dictionary number and the dictionary status word match; and responsive to a reset condition, generating a second N-bit dictionary number so that the second dictionary number does not match the stored first dictionary number. - View Dependent Claims (16, 17, 18, 19, 20, 21)
-
Specification