ROM-based multiple match circuit
View Patent ↗A ROM-based multiple match system and method for producing a match signal in an addressable memory system are described. In various embodiments of the present invention, a ROM is used to generate single match and multiple match signals, as well as encoded address signals indicating a matching location(s) within the memory. The ROM is provided with specific entries in the form of a lookup table, which are used to signal combinational logic that provides an output to the system. In certain embodiments of the invention, the ROM may be divided into hierarchical sub-blocks that provide more efficient processing of a digital data related to matching of an input word, improved usage of space within a chip or better scalability across the multiple match system.
1. A ROM-based multiple match system comprising:
a plurality of input hitlines that communicate digital information related to whether an input word matches at least one stored word within an addressable memory;
a ROM, coupled to the input hitlines, that processes the digital information using a plurality of column pairs, each column pair having a first column that is complimentary to a second column; and
a combinational logic, coupled to the ROM, that digitally processes data from the ROM and provides a multiple match output signal identifying an occurrence of a multiple match to the input word.
2. The system of claim 1 wherein the addressable memory is a content addressable memory device.
3. The system of claim 1 wherein the plurality of input hitlines is an array of eight hitlines communicating an eight bit word.
4. The system of claim 1 wherein the first column is an “A” column comprising a series of zeroes and the second column is a “B” column comprising a series of ones.
5. The system of claim 1 wherein the combinational logic comprises a match output and a plurality of address outputs that indicate a physical address of at least one match to the input word.
6. The system of claim 5 wherein the combinational logic comprises a plurality of AND gates, coupled to the plurality of column pairs, that combines each column pair into single signal using an AND operation.
7. The system of claim 6 wherein the combination logic further comprises a multi-input OR gate, coupled to the plurality of AND gates, that generates a multiple match output signal.
8. The system of claim 2 wherein each column within the plurality of column pairs in the ROM comprises a plurality of transistors that generate data vectors associated with the plurality of input hitlines.
9. The system of claim 8 wherein the plurality of transistors comprises a plurality of NMOS transistors.
10. The system of claim 1 wherein the plurality of input hitlines is 64hitlines and the ROM comprises 6 column pairs.
11. A method for identifying multiple matches to an input word within an addressable memory, the method comprising:
receiving a digital data stream indicating whether a match occurred between an input word and stored data within an addressable memory;
creating a first data vector, using a ROM, identifying a first match of the input word;
creating a second data vector, using the ROM, identifying a second match of the input word, wherein the ROM comprises a plurality of complimentary columns that creates the first and second data vectors; and
providing a multiple match signal indicating the first and second matches of the input word.
12. The method of claim 11 wherein a combination logic receives the first and second data vectors and generates the multiple match signal.
13. A method for identifying multiple matches to an input word within an addressable memory, the method comprising;
receiving a digital data stream indicating whether a match occurred between an input word and stored data within an addressable memory;
providing a hierarchical processing of the digital data stream across a primary Rom and a plurality of sub-block ROMs;
creating a first data vector, using a ROM, identifying a first match of the input word;
creating a second data vector, using the ROM, identifying a second match of the input word; and,
providing a multiple match signal indicating the first and second matches of the input word.
14. The method of claim 13 wherein the plurality of sub-block ROMs are coupled to receive the digital data stream, process the digital data stream, and provide a plurality of output signals to the primary ROM.
15. A hierarchical ROM-based multiple match system comprising:
a plurality of hitlines that communicate digital information indicating whether an input word matches at least one stored word within an addressable memory;
a plurality of ROM sub-blocks, coupled to the plurality of hitlines, that identify a match to the input word using a sub-set of the plurality of hitlines and that generates a plurality of ROM sub-block outputs indicating the match;
a primary ROM, coupled to the plurality of ROM sub-blocks, that process the plurality of ROM sub-block outputs and that identify a multiple match of the input word within the addressable memory; and
a multiple match output signal, coupled to the primary ROM, that indicates the multiple match.
16. The system of claim 15 further comprising a match output signal, coupled to the primary ROM, that indicates a match of the input word in the addressable memory.
17. The system of claim 15 further comprising at least one encoded address signals, coupled to the primary ROM, that provides at least one address within the addressable memory associated with a match of the input word.
18. The system of claim 15 wherein the addressable memory is a content addressable memory device.