CONTENT ADDRESSABLE MEMORY ENTRY CODING FOR ERROR DETECTION AND CORRECTION
First Claim
1. A content addressable memory comprising:
- lookup-data inputs receiving lookup data;
a plurality of entries, each entry including a plurality of entry groups that each s contribute to an associated hit indication of the entry, each entry group having associated storage bits storing an encoded comparison value; and
a match information output summarizing the hit indications from one or more of the entries.
1 Assignment
0 Petitions
Accused Products
Abstract
A Content Addressable Memory (CAM) or Ternary CAM (TCAM) provides error detection and correction (EDAC). EDAC codes are chosen based on logical and physical properties of the CAM/TCAM. An entry in the CAM/TCAM comprises a plurality of groups, each group comprising a plurality of storage bits. Writes to the storage bits are encoded to enable EDAC. Lookup data is divided into lookup groups of one or more bits, and is applied to corresponding groups of entries to be searched. In one embodiment, storage bits in a group are first decoded to detect and/or to correct errors and then compared with a lookup group to produce a hit indication. In another embodiment, storage bits in a group are logically combined with a lookup group to produce a hit indication, wherein a correctable error in the storage bits does not affect correctness of the hit indication.
94 Citations
30 Claims
-
1. A content addressable memory comprising:
-
lookup-data inputs receiving lookup data; a plurality of entries, each entry including a plurality of entry groups that each s contribute to an associated hit indication of the entry, each entry group having associated storage bits storing an encoded comparison value; and a match information output summarizing the hit indications from one or more of the entries. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
11. A content addressable memory comprising:
-
lookup-data inputs receiving lookup data; write-data inputs receiving write data; a plurality of entries, each entry including a hit indication and a plurality of entry groups, each entry group including storage bits storing EDAC-encoded comparison value information; a match information output summarizing the hit indications from at least some of the plurality of entries; and a data encoder encoding the write data to produce the EDAC-encoded comparison value information of each entry group. - View Dependent Claims (12, 13, 14, 15, 16, 17, 18)
-
-
19. An entry of a content addressable memory comprising:
-
a plurality of storage bits holding a comparison value, the plurality of storage bits comprised of a plurality of groups of bits, each group of bits separately encoded; a lookup input for entry-level comparison with the comparison value, the lookup input having a number of bits associated with each of the groups of bits; a hit indication output indicating a hit when the lookup input corresponds with the comparison value; and logic associated with a particular group of bits to, at least in part, perform a group-level comparison between the bits of the lookup input associated with the particular group of bits and a portion of the comparison value held in an encoded form in the particular group of bits, the group-level comparison being a sub-portion of the entry-level comparison. - View Dependent Claims (20, 21, 22, 23)
-
-
24. An entry of a content addressable memory comprising:
-
comparison value information; a lookup input for entry-level comparison with the comparison value information, the lookup input segregated into a plurality of lookup groups of bits; a hit indication output indicating a hit when the lookup input compares properly with the comparison value information; a plurality of entry groups, each entry group coupled to a corresponding lookup group, each entry group comprising a contribution to the hit indication output and a plurality of EDAC-encoded storage bits, the storage bits among all entry groups holding the comparison value information of the entry; and means for determining the contribution to the hit indication output of each entry group. - View Dependent Claims (25, 26, 27)
-
-
28. A method for data lookup in a content addressable memory comprising:
-
comparing a lookup-data input against one or more entries of the content addressable memory and generating a hit indication of the compared entry when comparison value information maintained in the compared entry agrees with the lookup-data input; summarizing the hit indications of each compared entry to produce a match indication output; and wherein the comparing against a particular entry is done in parts by multiple entry groups that each process a number of bits of the lookup-data input, each entry group storing an encoded portion of the comparison value information for the particular entry. - View Dependent Claims (29, 30)
-
Specification