Electrical computers and digital processing systems: memory – Address formation – Varying address bit-length or size
Reexamination Certificate
2000-07-21
2002-05-14
Peikari, B. James (Department: 2186)
Electrical computers and digital processing systems: memory
Address formation
Varying address bit-length or size
C711S128000, C365S189070, C365S049130
Reexamination Certificate
active
06389524
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to associative memory devices outputting stored data in response to comparison results between input retrieval data and the stored data, and more particularly, to an associative memory device which can change at a software level the length of data being compared, and a variable length code decoding device utilizing the same associative memory device.
2. Description of the Background Art
An associative memory device is known as a memory device which retrieves data having a tag that matches a specific keyword. Such an associative memory device is disclosed, for example, in Japanese Laid-Open Patent No. 10-50076. The associative memory device is configured to compare a part (hereinafter, referred to as a “tag” or a “tag portion”) of data stored within the device with an input keyword, and to automatically read out data having the tag portion that matches the keyword.
In a conventional associative memory device, however, the data length of the tag portion, or the length of a keyword being compared, has been fixed normally at a hardware level. On the other hand, for data coded employing a variable length coding system, for example, the length of the keyword for comparison cannot necessarily be fixed. Therefore, it is usually difficult to process such data with the associative memory device.
Here, assume that a tag that should be compared is shorter than a data length predetermined at the hardware level, and all the tags stored have the same data length. In such a case, it is possible to fill up every remaining bit of the tag with a specific value and to fix a corresponding bit of the retrieval keyword to the same value, so that a proper retrieval can be conducted.
However, such an approach cannot be utilized for decoding of the variable length code data, because, in the variable length code data, the tag portions to be compared have various data lengths, and the data lengths of the tags cannot be determined before decoding.
Another approach is to modify a data storing method of the associative memory such that a proper retrieval can be conducted whatever value is included in a bit being unused as a tag. For example, assume that an associative memory device having a tag length of 8 bits, which is determined at a hardware level, is being used for retrieval of data having a tag of 6 bits. In such a case, data are stored such that the retrieval can be done without failure whatever values are contained in the remaining 2 bits of the retrieval keyword.
Specifically, a tag originally having 6 bits therein is extended for 2 bits by adding data of “00”, “01”, “10” and “11”, respectively, so that four tags with 8 bits each are created based on the one tag with 6 bits. These four tags created are then made to correspond to the same data. In this manner, it becomes possible to conduct proper retrieval even with retrieval data having a length that is shorter than the data length of the tag predetermined at the hardware level.
In such a case, however, it is necessary to create a plurality of (4, in the above-mentioned case) entries with respect to one code. This poses a problem that data storage efficiency is considerably degraded.
SUMMARY OF THE INVENTION
An object of the present invention is to provide an associative memory device which is capable of changing the length of a keyword being compared at a software level and also applicable to decoding of a variable-length code efficiently, and to provide a variable-length code decoding device utilizing the same associative memory device.
In summary, the present invention is directed to an associative memory device outputting data according to an input of retrieval data having a plurality of bits, which includes a keyword comparison array and a data storage array.
The keyword comparison array retains a plurality of tag data each having a plurality of bits, and performs matching between the retrieval data input and each of the plurality of tag data. The keyword comparison array includes a plurality of matching circuits provided corresponding to the plurality of tag data, each comparing the retrieval data and corresponding one of the plurality of tag data. Each of the plurality of matching circuits includes: an n number (n is an integer at least 0) of first comparison memory units provided corresponding to n bits of the corresponding tag data, each retaining corresponding one bit and performing a matching operation between the retaining bit and a corresponding bit of the retrieval data; and an m number (m is a natural number) of second comparison memory units provided corresponding to respective parts of remaining bits of the corresponding tag data other than the n bits, each performing the matching operation between corresponding one part of the remaining bits and a corresponding bit of the retrieval data, a matching result of which is invalidated dependent on an externally set comparison condition signal. The keyword comparison array further includes a plurality of matching detection signal lines provided corresponding to the plurality of matching circuits. Each of the plurality of matching detection signal lines has a potential level that is determined according to the matching results of the n number of first comparison memory units and of an (m−k) number (k is an integer from 0 to m) among the m number of second comparison memory units other than the k number thereof having the comparison results invalidated, included in the corresponding matching circuit.
The data storage array responds to the potential level of each of the plurality of matching detection signal lines and outputs data corresponding to one of the plurality of tag data that matches the retrieval data.
Another aspect of the present invention is directed to a variable-length code decoding device for decoding variable-length code data, which includes a retrieval data setting circuit, an associative memory circuit, and a decoding target pointer circuit.
The retrieval data setting circuit receives a bit stream of the variable-length code data input as a decoding target, and outputs retrieval data including a fixed number of bits being decoded in one decoding process.
The associative memory circuit responds to input of the retrieval data, and outputs decoded data corresponding to the variable-length code data and code length data indicating the number of bits of the decoded data. The associative memory circuit includes: a keyword comparison array which retains coded variable-length code data as a plurality of tag data, and performs matching between the retrieval data input and each of the plurality of tag data. The keyword comparison array includes a plurality of matching circuits provided corresponding to the plurality of tag data, each comparing the retrieval data and corresponding one of the plurality of tag data. Each of the plurality of matching circuits has an m number (m is a natural number) of first comparison memory units provided corresponding to respective parts of bits of the corresponding tag data. Each of the first comparison memory units retains corresponding one part of bits and a comparison condition signal externally supplied in advance, and performs a matching operation between the part of bits and a corresponding bit of the retrieval data, a matching result of which is invalidated dependent on the comparison condition signal. The keyword comparison array further includes a plurality of matching detection signal lines provided corresponding to the plurality of matching circuits. Each of the plurality of matching detection signal lines has a potential level that is determined according to the matching results of an (m−k) number (k is an integer from 0 to m) among the m number of the first comparison memory units other than the k number thereof having the matching results invalidated, included in the corresponding matching circuit.
The associative memory circuit further includes a data storage array which, in response to the potential level of each of the plurality of matc
LandOfFree
Decoding device with associative memory permitting... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Decoding device with associative memory permitting..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Decoding device with associative memory permitting... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2851175