Detecting “almost match” in a CAM
View Patent ↗An apparatus and method is disclosed for detecting CAM words having a “near match” condition, where “near match” is defined by a CAM word having one or more mismatching bits. Each cell in a CAM word is connected to a match line, where a small known current is impressed upon the line each time a bit does not match with search data. The total current is sensed to establish a priority for each respective CAM word. Each priority for each CAM word is then decoded to determine the Cam word having the highest priority. Under an alternate embodiment, a minimum priority level select circuit is disclosed, where a user may specify an acceptable priority level that is generated from a CAM word search.
1. A circuit for prioritizing a plurality of CAM words, comprising:
a plurality of current detection circuits, each of said plurality of current detection circuits being coupled to a respective match line in each of said plurality of CAM words;
a plurality of priority converter circuits, each of said plurality of priority converter circuits being coupled to a respective one of said plurality of current detection circuits for assigning a priority to each of said plurality of CAM words; and
an encoding circuit coupled to each of said plurality of priority converter circuits, wherein said encoding circuit encodes an output from each converter circuit to determine a priority for all of said outputs.
2. The circuit according to claim 1 , wherein the current detection circuit comprises a plurality of resistors, each of said resistors being coupled to the output of each of the match lines, each of said resistors generating a respective priority voltage on an output line when a respective current flows across each resistor.
3. The circuit according to claim 2 , wherein each of the plurality of priority converter circuits comprises a plurality of comparators, each comparator having one input terminal connected to the priority voltage output line, and a second input terminal coupled to a reference voltage line.
4. The circuit according to claim 3 , wherein the plurality of comparators are sequentially arranged along the match lines and reference lines, so that a first comparator represents a highest priority, and the last comparator represents a lowest priority.
5. The circuit according to claim 4 , each of the plurality of comparators have an inverting and non-inverting output, wherein the non-inverting output of each comparator will output a logic signal “1” signal to a level priority line if the priority voltage output line is determined to be higher than the reference voltage line.
6. The circuit according to claim 5 , each of the plurality of comparators have an inverting and non-inverting output, wherein the non-inverting output of each comparator will output a logic signal “0” signal to a level priority line if the priority voltage output line is determined to be lower than the reference voltage line.
7. The circuit according to claim 6 , wherein the plurality of comparators are connected to a plurality of logic gates, each of said comparators being connected to a respective logic gate.
8. The circuit according to claim 7 , wherein the logic gates operate to allow only the highest available priority comparator logic signal to be transmitted to a word priority output, while disabling any lower priority comparator logic signals that are received.
9. The circuit according to claim 8 , wherein the word priority output from the logic gates is connected to a sense circuit.
10. The circuit according to claim 9 , wherein the sense circuit is connected to a highest priority indicator circuit.
11. The circuit according to claim 10 , wherein the output of the highest priority indicator circuit is connected to a plurality of priority logic gates associated with each CAM word.
12. The circuit according to claim 11 , wherein each of the level priority lines from each CAM word being connected with a respective plurality of priority logic gates, said logic gates arranged to indicate the CAM word having the highest priority.
13. An apparatus for converting a priority for a CAM word, comprising:
a mismatch line, said mismatch line being connected to the CAM word, wherein the mismatch line carries a signal indicating the number of mismatching bits in the CAM word;
a plurality of comparator circuits, each having an output terminal, and each of said comparator circuits having a first terminal connected to the mismatch line;
a mismatch reference voltage line, connected to a plurality of resistors, each of said plurality of resistors being coupled to a second terminal of a respective comparator circuit, wherein each comparator outputs a signal if the respective comparator determines that the mismatch line voltage is lower than the mismatch reference voltage line.
14. The apparatus according to claim 13 , wherein the comparator circuits are arranged in a sequential order along the voltage lines where each comparator has a higher priority.
15. The apparatus according to claim 14 , wherein each comparator outputs a logic “1” signal on a non-inverting output line if the voltage on the mismatch line is sensed to be higher than the voltage on the reference line.
16. The apparatus according to claim 14 , wherein each comparator outputs a logic “0” signal on a non-inverting output line if the voltage on the mismatch line is sensed to be lower than the voltage on the reference line.
17. The apparatus according to claim 14 , wherein the plurality of comparators are connected to a plurality of logic gates with output terminals, each of said comparators being connected to a respective logic gate.
18. The circuit according to claim 17 , wherein the logic gates operate to allow only the highest available priority comparator logic signal to be transmitted from an output terminal to a word priority output, while disabling any lower priority comparator logic signals.
19. The circuit according to claim 18 , wherein the word priority output from the logic gates is connected to a sense circuit.
20. The circuit according to claim 19 , wherein the sense circuit is connected to a highest priority indicator circuit.
21. The circuit according to claim 20 , wherein the output of the highest priority indicator circuit is connected to a plurality of priority logic gates associated with each CAM word.
22. The circuit according to claim 21 , wherein each of the level priority lines from each CAM word being connected with a respective plurality of priority logic gates, said logic gates arranged to indicate the CAM word having the highest priority.