Content addressable memory entry coding for error detection and correction

• US 7,689,889 B2
• Filed: 08/24/2006
• Issued: 03/30/2010
• Est. Priority Date: 08/24/2006
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Cohen, Earl T.
• Primary Examiner(s): Chase; Shelly A
• Application Number:
  US11/467,097
• Publication Number:
  US 20080049522A1
• Time in Patent Office: 1,314 Days
• Field of Search: 714763-764, 714/768
• US Class Current: 714/759
• CPC Class Codes: G11C 15/00 Digital stores in which information comprising one or more characteristic parts is written into the store and in which information is read-out by searching for one or more of these characteristic parts, i.e. associative or content-addressed stores

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.

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 provide a contribution to an associated hit indication of the entry, each entry group having associated storage bits storing an encoded comparison value, wherein the encoded comparison value of a particular entry group of a particular entry is compared with a portion of the lookup data using an error-correcting comparison to produce the contribution of the particular entry group to the associated hit indication of the particular entry; and

a match information output summarizing the hit indications from one or more of the entries.

2. The content addressable memory of claim 1, wherein the encoded comparison value of the particular entry group in the particular entry encodes at least three distinct values, each of the at least three distinct values separated from the others by a minimum distance.

3. The content addressable memory of claim 2, wherein the minimum distance is three.

4. The content addressable memory of claim 2, wherein the minimum distance is more than three.

5. The content addressable memory of claim 1,

each entry group further comprising an uncorrectable error output;

and

wherein regardless of a single-bit error in the storage bits of a particular entry group of a particular entry, the contribution of the particular entry group to the hit indication of the particular entry is correct, and no error is signaled on the uncorrectable error output of the particular entry group; and

wherein at least one error more severe than a single-bit error in the storage bits of the particular entry group is signaled on the uncorrectable error output of the particular entry group.

6. 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 provide a contribution to an associated hit indication of the entry, each entry group having associated storage bits storing an encoded comparison value, wherein the encoded comparison value of a particular entry group of a particular entry is decoded to produce match controls, the match controls being used to effect a comparison with a portion of the lookup data inputs to produce the contribution of the particular entry group to the associated hit indication of the particular entry; and

a match information output summarizing the hit indications from one or more of the entries.

7. The content addressable memory of claim 6, wherein the match controls comprise a mask value and a data value for each bit of the lookup data.

8. The content addressable memory of claim 6, wherein regardless of a correctable error in the storage bits of a particular entry group of a particular entry, the contribution of the particular entry group to the associated hit indication of the particular entry is correct.

9. The content addressable memory of claim 8, wherein the correctable error is a single-bit error.

10. 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 Error Detection And Correction (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.

11. The content addressable memory of claim 10,

wherein the lookup data is segregated into a plurality of lookup groups of bits;

and

wherein each entry group of the plurality of entry groups of each entry is coupled to a corresponding lookup group.

12. The content addressable memory of claim 11,

wherein each entry group of the plurality of entry groups of each entry further comprises decode logic to decode the EDAC-encoded comparison value information stored in the storage bits of the entry group to produce comparison value information;

and

wherein each entry group of the plurality of entry groups of each entry further comprises compare logic to compare a respective lookup group with the comparison value information.

13. The content addressable memory of claim 12, wherein results from the compare logic of all the entry groups of the plurality of entry groups of each entry are combined to produce the hit indication of each entry.

14. The content addressable memory of claim 11, wherein each entry group of the plurality of entry groups of each entry further comprises error-correcting compare logic to compare a respective lookup group with the EDAC-encoded comparison value information stored in the storage bits of the entry group.

15. The content addressable memory of claim 14, wherein results from the compare logic of all the entry groups of the plurality of entry groups of each entry are combined to produce the hit indication of each entry.

16. The content addressable memory of claim 10, wherein regardless of the presence of a correctable error in the storage bits of one or more of the plurality of entry groups of a particular entry, the hit indication of the particular entry is correct.

17. The content addressable memory of claim 16, wherein the correctable error is a single-bit error.

18. 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, wherein the hit indication output is correct even when a correctable error is contained in the particular group of bits; 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.

19. The entry of claim 18, wherein the correctable error is a single-bit error.

20. The entry of claim 18,

wherein the comparison value is a ternary comparison value;

and

wherein the entry is one of plurality of entries of a ternary content addressable memory.

21. The entry of claim 18, wherein the comparison value is a binary comparison value.

22. 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 Error Detection And Correction (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.

23. The entry of claim 22, wherein regardless of the presence of a correctable error in the storage bits of one or more entry groups, the hit indication output is correct.

24. The entry of claim 23, wherein the correctable error is a single-bit error.

25. The entry of claim 22, wherein the means for determining the contribution to the hit indication output of a particular entry group is based at least in part upon the storage bits of the particular entry group and the corresponding lookup group of the particular entry group.

26. 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;

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; and

wherein the encoded comparison value is compared with a portion of the lookup-data input using an error-correcting comparison to produce a contribution of a particular entry group to the hit indication for the compared entry.

27. The method of claim 26, wherein regardless of the presence of a correctable error in the encoded portion of the comparison value information stored in one or more entry groups of the particular entry, the comparing produces the correct hit indication of the particular entry.

28. The method of claim 27, wherein the correctable error is a single-bit error.