Back to results
US 7,003,624 B2Granted
Method and apparatus for detecting “almost match” in a CAM
AssigneeMicron Technology, Inc.
InventorsAlon Regev, Zvi Regev
Life of this patent
Estimating the term…
Abstract
A method and apparatus for expediting the searching of a CAM array to obtain a matching or near-matching word is disclosed. In those cases where no word matches any of the words contained within the CAM array, a word that “almost” matches can be quickly found.
Claims23
A content addressable memory, comprising:
- a plurality of memory storage locations, each comprising a data shift register;
- a plurality of bit matching circuits respectively coupled to an output stage of said shift registers;
- a plurality of error shift registers respectively coupled to an output of said bit matching circuits;
- and
- a plurality of error detectors respectively coupled to said error shift registers for detecting when a respective error shift register contains no errors,
- wherein each of said plurality of error shift registers shifts horizontally a predetermined data bit if an output of an associated data shift register does not match the output of a comparand shift register.
3 more elements
A method of operating a content addressable memory array, comprising:
- (a) clearing the contents of a plurality of error shift registers respectively associated with memory locations within said array;
- (b) bit-wise searching each of the memory locations of said array for a match with the contents of a comparand register;
- (c) right-shifting said error shift register once for each mismatch with a comparand, thereby storing a total number of mismatching bits in said error shift registers;
- (d) checking said error zero shift registers for zero errors;
- (e) if zero errors are not present in any of said error shift registers, left-shifting said error shift registers and rechecking said error shift registers for zero errors;
- and
- (f) repeating steps (d) and (e) until at least one of said error shift registers contains zero errors.
4 more elements
A router, comprising:
- a plurality of message receiving inputs;
- a plurality of message transmitting outputs;
- and
- a semiconductor chip containing a content addressable memory, said content addressable memory being used to route messages on said inputs to said outputs, said content addressable memory comprising:
- a plurality of memory storage locations, each having an associated match line for bit-wise indicating if a search word matches a word stored in the memory storage location, an associated shift register for tracking a number of mismatching bits, said associated shift register also shifts a predetermined data bit horizontally if said associated shift register indicates mismatching bits, and a detector for detecting when said associated shift register indicates mismatching bits;
- and
- a priority encoder circuit having a plurality of inputs respectively coupled to received signals from said detectors, and being operable to indicate the address of a highest priority detector which detects no mismatching bits in its associated tracking register.
4 more elements
A processor circuit, comprising
- a processor;
- and
- a content-addressable memory circuit for exchanging data with said processor, said content addressable memory circuit comprising:
- a plurality of memory storage locations, each having an associated match line for bit-wise indicating if a search word matches a word stored in the memory storage location, an associated shift register for tracking a number of mismatching bits, said associated shift register also shifts a predetermined data bit horizontally if said associated shift register indicates mismatching bits, and a detector for detecting when said associated shift register indicates mismatching bits;
- and
- a priority encoder circuit having a plurality of inputs respectively coupled to received signals from said detectors, and being operable to indicate the address of a highest priority detector which detects no mismatching bits in its associated tracking register.
3 more elements
Dependencies are inferred from the claim text.