Error Protection For Lookup Operations in Content-Addressable Memory Entries
First Claim
1. A method for identifying matching values in a content-addressable memory, the method comprising:
- determining a plurality of extended values based on a plurality of values, each of the plurality of extend values including a particular value of the plurality values and an error-correcting or error-detecting code generated based on the particular value, wherein each of the plurality of extend values are guaranteed to differ each other by at least n bits;
programming a plurality of content-addressable memory entries with the plurality of extended values; and
performing a lookup operation on said content-addressable memory entries based on a lookup word to determine whether or not a hit results, wherein the hit is determined if an entry of said content-addressable memory entries matches the lookup word in all or all but k bit positions;
wherein n and k are integers, n>
k, and k>
0.
1 Assignment
0 Petitions
Accused Products
Abstract
Error protection for lookup operations in a content-addressable memory (CAM) entries is disclosed. Values extended to include error protection or error protection fields are stored in CAM entries and a lookup operation is performed on a similarly extended lookup word to determine whether or not an entry is matched, that is, if all or all but some predetermined number of bits match one of the extended entries. For example, one implementation includes multiple CAM entries and logic configured to perform a lookup operation in parallel on each of the CAM entries based on a lookup word to determine whether or not a hit results, where the hit is determined if an entry matches the lookup word in all or all but k bit positions, where n and k are integers, n>k, and k>0.
95 Citations
34 Claims
-
1. A method for identifying matching values in a content-addressable memory, the method comprising:
-
determining a plurality of extended values based on a plurality of values, each of the plurality of extend values including a particular value of the plurality values and an error-correcting or error-detecting code generated based on the particular value, wherein each of the plurality of extend values are guaranteed to differ each other by at least n bits;
programming a plurality of content-addressable memory entries with the plurality of extended values; and
performing a lookup operation on said content-addressable memory entries based on a lookup word to determine whether or not a hit results, wherein the hit is determined if an entry of said content-addressable memory entries matches the lookup word in all or all but k bit positions;
wherein n and k are integers, n>
k, and k>
0. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
-
10. A method for identifying matching values in a content-addressable memory, the method comprising:
-
determining a plurality of extended values based on a plurality of values, each of the plurality of extend values including a particular value of the plurality values and an error-correcting or error-detecting code determined based on the particular value, wherein each of the plurality of extend values are guaranteed to differ each other by at least three bits;
programming a plurality of content-addressable memory entries with the plurality of extended values; and
performing a lookup operation on said content-addressable memory entries based on a lookup word to determine whether or not a hit results, wherein the hit is determined if an entry of said content-addressable memory entries matches the lookup word in all or all but one bit position. - View Dependent Claims (11, 12, 13, 14, 15, 16, 17, 18)
-
-
19. An apparatus for identifying matching values in a content-addressable memory, the apparatus comprising:
-
means for determining a plurality of extended values based on a plurality of values, each of the plurality of extend values including a particular value of the plurality values and an error-correcting or error-detecting code determined based on the particular value, wherein each of the plurality of extend values are guaranteed to differ each other by at least n bits;
means for programming a plurality of content-addressable memory entries with the plurality of extended values; and
means for performing a lookup operation on said content-addressable memory entries based on a lookup word to determine whether or not a hit results, wherein the hit is determined if an entry of said content-addressable memory entries matches the lookup word in all or all but k bit positions;
wherein n and k are integers, n>
k, and k>
0. - View Dependent Claims (20, 21, 22, 23, 24, 25)
-
-
26. An apparatus comprising:
-
a plurality of content-addressable memory entries;
logic configured to perform a lookup operation on said content-addressable memory entries based on a lookup word to determine whether or not a hit results, wherein the hit is determined if an entry of said content-addressable memory entries matches the lookup word in all or all but k bit positions;
wherein n and k are integers, n>
k, and k>
0. - View Dependent Claims (27, 28, 29, 30, 31, 32, 33, 34)
-
Specification