Coded data generation or conversion – Digital code to digital code converters – Coding by table look-up techniques
Reexamination Certificate
2002-09-03
2004-04-13
JeanPierre, Peguy (Department: 2819)
Coded data generation or conversion
Digital code to digital code converters
Coding by table look-up techniques
C341S050000
Reexamination Certificate
active
06720894
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to a differential lossless compression method and system and more particularly to a method of and system for encoding instruction bit patterns using a primary dictionary for the most frequently occurring bit patterns and encoding the remaining instruction bit patterns using the differences between the remaining bit patterns and the bit patterns that are already encoded in the primary dictionary.
BACKGROUND OF THE INVENTION
In order to reduce the amount of memory needed to store data processing instructions in on-chip SRAM memory, the instructions are typically compressed to reduce the amount of memory that must be stored. Typical compression algorithms involve storing data words used in an instruction set in a look-up table and accessing the data words through the use of code words that identify the address at which the desired data word is stored. While this type of compression reduces the amount of memory needed compared to storing all of the necessary data words, it still requires a great amount of memory to operate properly.
SUMMARY OF THE INVENTION
The present invention provides a method of and system for performing lossless compression in which the most frequently accessed data words are stored in a primary dictionary and in which shortened code words are used to access these data words. Difference dictionaries are used to store difference bit streams which are accessed by code words which identify a data word in the primary dictionary and a difference bit stream in one of the difference dictionaries. An exclusive-OR operation is performed on the identified data word and the difference bit stream to calculate a decoded data word that is not stored in either the primary or difference dictionaries.
According to one aspect of the invention, a method of decompressing data words of an instruction set includes:
A. filling a primary dictionary with at least one primary data word of the instruction set, each of the at least one primary data word being stored in the primary dictionary in a location associated with a distinct primary dictionary index;
B. filling at least one secondary dictionary with at least one difference bit stream, each of the at least one difference bit stream being stored in one of the at least one secondary dictionary in a location associated with a distinct secondary dictionary index;
C. receiving a code word, the code word comprising:
a. a header which identifies the primary dictionary and a specific one of the at least one secondary dictionary;
b. a first bit stream; and
c. a second bit stream;
wherein the first bit stream comprises the distinct primary dictionary index and the second bit stream comprises the distinct secondary dictionary index;
D. retrieving the primary data word stored at the location in the primary dictionary location associated with the distinct primary dictionary index;
E. retrieving the difference bit stream stored at the location in the at least one secondary dictionary location associated with the distinct secondary dictionary index; and
F. performing a logic operation on the primary data word and the difference bit stream to obtain a resultant data word that is not stored in either the at least one primary dictionary or the at least one secondary dictionary.
The primary data words may include 32 bit words, the code words may include less than 32 bits, the first bit stream may include up to 11 bits and the second bit stream may include at least 5 bits. The logic operation may be an exclusive-OR operation. The at least one secondary dictionary may include a first secondary dictionary which includes difference bit streams which are more commonly included in the second bit stream of the code word and a second secondary dictionary which includes difference bit streams which are less commonly included in the second bit stream of the code word.
According to another aspect of the invention, a system for decompressing data words of an instruction set includes:
a computer processor which performs operations based on the instruction sets;
a memory device including:
A. a primary dictionary including at least one primary data word of the instruction set, each of the at least one primary data word being stored in the primary dictionary in a location associated with a distinct primary dictionary index; and
B. at least one secondary dictionary including at least one difference bit stream, each of the at least one difference bit stream being stored in one of the at least one secondary dictionary in a location associated with a distinct secondary dictionary index; and
a decompression engine for receiving a code word from the computer processor and accessing the memory device to decode the code word to obtain a data word requested by the computer processor;
wherein the code word includes:
a. a header which identifies the primary dictionary and a specific one of the at least one secondary dictionary;
b. a first bit stream; and
c. a second bit stream;
wherein the first bit stream comprises the distinct primary dictionary index and the second bit stream comprises the distinct secondary dictionary index; and
wherein the decompression engine retrieves the primary data word stored at the location in the primary dictionary location associated with the distinct primary dictionary index;
retrieves the difference bit stream stored at the location in the at least one secondary dictionary location associated with the distinct secondary dictionary index; and
performs a logic operation on the primary data word and the difference bit stream to obtain a resultant data word that is not stored in either the at least one primary dictionary or the at least one secondary dictionary, the resultant data word being the data word requested by the computer processor.
According to another aspect of the invention, a system for decompressing data words of an instruction set includes:
a computer processor which performs operations based on the instruction sets;
a memory device including:
A. a primary dictionary including at least one primary data word of the instruction set, each of the at least one primary data word being stored in the primary dictionary in a location associated with a distinct primary dictionary index; and
B. a first secondary dictionary including at least one difference bit stream, each of the at least one difference bit stream being stored in the first secondary dictionary in a location associated with a distinct first secondary dictionary index; and
C. a second secondary dictionary including at least one difference bit stream, each of the at least one difference bit stream being stored in the second secondary dictionary in a location associated with a distinct second secondary dictionary index; and
a decompression engine for receiving a code word from the computer processor and accessing the memory device to decode the code word to obtain a data word requested by the computer processor;
wherein the code word includes:
a. a header which identifies the primary dictionary and one of the first secondary dictionary and the second secondary dictionary;
b. a first bit stream; and
c. a second bit stream;
wherein the first bit stream comprises the distinct primary dictionary index and the second bit stream comprises the distinct secondary dictionary index for the secondary dictionary identified in the header; and
wherein the compression engine retrieves the primary data word stored at the location in the primary dictionary location associated with the distinct primary dictionary index, retrieves the difference bit stream stored at the location in the identified secondary dictionary location associated with the distinct secondary dictionary index; and
performs an exclusive-OR operation on the primary data word and the difference bit stream to obtain a resultant data word that is not stored in either the primary dictionary or the at least one secondary dictionary, the resultant data word being the data word requested by the computer processor.
According to yet another aspect of the invention, a system f
Redford John
Wilson Sophie
Jean-Pierre Peguy
Lauture Joseph
Sterne Kessler Goldstein & Fox P.L.L.C.
LandOfFree
Method of and system for performing differential lossless... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method of and system for performing differential lossless..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of and system for performing differential lossless... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3272639