Error-correcting content addressable memory

• US 6,978,343 B1
• Filed: 08/05/2002
• Issued: 12/20/2005
• Est. Priority Date: 08/05/2002
• Status: Active Grant

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Netlogic Microsystems Incorporated (Broadcom, Inc.)
• Inventors: Ichiriu, Michael E.
• Primary Examiner(s): MOAZZAMI, NASSER G
• Application Number:
  US10/213,244
• Time in Patent Office: 1,233 Days
• Field of Search: 711/108, 711/114, 365/49, 365/200, 714 1- 7, 714/766, 714/800
• US Class Current: 711/108
• 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
• CPC Class Codes: G11C 2029/0409 Online test

Abstract

A content addressable memory (CAM) device having an error correction function. The CAM device includes an array of CAM cells, row parity storage elements and column parity storage elements. The row parity storage elements store row parity values that correspond to contents of respective rows of the CAM cells, and the column parity storage elements store column parity values that correspond to respective columns of the CAM cells. A bit error in the array is detected through row and column parity checking that uniquely identifies the row and column location of the error and enables correction of the error.

Claims

1. A content addressable memory (CAM) device comprising:

a plurality of CAM cells;

a plurality of row parity storage elements to store row parity values that correspond to contents of respective rows of the CAM cells;

a plurality of column parity storage elements to store column parity values that correspond to contents of respective columns of the CAM cells; and

a write circuit to provide an input value to a selected row of the CAM cells, the write circuit including a row parity generator to generate an updated row parity value based on the input value, wherein the write circuit is adapted to provide the updated row parity value to one of the row parity storage elements that corresponds to the selected row of the CAM cells, and wherein the write circuit is adapted to provide the updated row parity value to the one of the row parity storage elements concurrently with providing the input value to the selected row of the CAM cells.

2. A content addressable memory (CAM) device comprising:

a plurality of CAM cells;

a plurality of row parity storage elements to store row parity values that correspond to contents of respective rows of the CAM cells;

a plurality of column parity storage elements to store column parity values that correspond to contents of respective columns of the CAM cells; and

a parity control circuit to remove, in response to a write request, a parity contribution of a value stored within a selected row of the CAM cells from a column parity word stored within the column parity storage elements, the column parity word being formed by the column parity values.

3. The CAM device of claim 2 wherein the parity control circuit comprises circuitry to exclusive-OR the column parity word with the value stored within the selected row to remove the parity contribution of the value stored within the selected row from the column parity word.

4. The CAM device of claim 2 further comprising a write circuit to store an input value in the selected row of the CAM cells in response to the write request.

5. The CAM device of claim device of claim 4 wherein the parity control circuit is adapted to apply a parity contribution of the input value to the column parity word after the parity contribution of the value stored within the selected row of the CAM cells has been removed from the column parity word.

6. The CAM device of claim 5 wherein the parity control circuit comprises circuitry to apply the parity contribution of the input value to the column parity word by exclusive-ORing the input value with the column parity word.

7. A content addressable memory (CAM) device comprising:

a plurality of CAM cells;

a plurality of row parity storage elements to store row parity values that correspond to contents of respective rows of the CAM cells;

a plurality of column parity storage elements to store column parity values that correspond to contents of respective columns of the CAM cells; and

a parity control circuit to read rows of the CAM cells in a predetermined sequence and to logically combine values read from the rows to generate a column parity word, the column parity word comprising the column parity values.

8. The CAM device of claim 7 wherein the parity control circuit comprises an exclusive-OR circuit to exclusive-OR the values read from the rows with one another to generate the column parity word.

9. The CAM device of claim 7 wherein the parity control circuit comprises an address sequencer to generate a sequence of addresses that define the predetermined sequence.

10. The CAM device of claim 9 wherein the parity control circuit comprises:

a partial column parity storage circuit coupled to store a partial column parity word; and

an exclusive-OR circuit coupled to the partial column parity storage circuit and coupled to receive each of the values read from the rows of the CAM cells, the exclusive-OR circuit being adapted to exclusive-OR, in succession, each of the values read from the rows with the partial column parity word stored within the partial column parity storage circuit to generate an updated partial column parity word.

11. The CAM device of claim 10 wherein the parity control circuit is adapted to transfer the partial column parity word from the partial column parity storage circuit to the plurality of column parity storage elements after a value read from a final row in the scan sequence is exclusive-ORed with the partial column parity word.

12. The CAM device of claim 7 wherein the parity control circuit is adapted to remove a parity contribution of a first value from the column parity word in response to an indication that the first value is to be overwritten in a write operation.

13. The CAM device of claim 12 wherein the parity control circuit comprises a circuit to remove the parity contribution of the first value from the column parity word by exclusive-ORing the first value with the column parity word.

14. The CAM device of claim 12 wherein the parity control circuit comprises:

an address sequencer to output addresses one after another according to the predetermined sequence;

a compare circuit to compare one of the addresses output by the address sequencer with an address on the first value to determine whether the address sequencer has progressed beyond the address of the first value; and

a logic circuit to exclusive-OR the first value with the column parity word if the compare circuit indicates that the address sequencer has progressed beyond the address of the first value.

15. The CAM device of claim 14 further comprising a write driver circuit to store a write data value at the address of the first value, and wherein the logic circuit is adapted to exclusive-OR the column parity word with the write data value if the compare circuit indicates that the address sequencer has progressed beyond the address of the first value.

16. The CAM device of claim 7 wherein at least one of the values read from the rows of the CAM cells comprises a mask value.

17. A content addressable memory (CAM) device comprising:

a CAM array including a plurality of CAM cells arranged in rows and columns, each row of CAM cells having a row address; and

a scan controller coupled to the plurality of CAM cells to read a respective row value from each row of CAM cells in succession to determine whether the row value contains a row parity error, the scan control circuit including circuitry to combine the bits within each column of the CAM cells to determine whether the column contains a column parity error, and wherein, in response to determining that a first row value read from the CAM array contains a row parity error, and that a first column of bits within the CAM array contains a column parity error, the scan controller is adapted to correct a selected bit within the first row value to generate a corrected row value.

18. The CAM device of claim 17 further comprising a write circuit coupled to receive the corrected row value from the scan controller and coupled to the CAM array to provide the corrected row value thereto.

19. The CAM device of claim 18 wherein the scan controller comprises an error address register to store, as an error address, an address of the first row value in response to determining that the first row value comprises a row parity error.

20. The CAM device of claim 19 further comprising an address circuit coupled to receive the error address from the error address register and coupled to select a row of the CAM cells indicated by the error address, the corrected row value being provided by the write circuit to the row of CAM cells selected by the address circuit.

21. A method of operation within a content addressable memory (CAM) device, the method comprising:

storing a plurality of row parity values, each row parity value indicating a parity for a respective row of CAM cells within the CAM device; and

storing a plurality of column parity values, each column parity value indicating a parity for a respective column of the CAM cells, wherein storing a plurality of column parity values comprises logically combining values stored within the rows of CAM cells to generate the column parity values, and wherein logically combining values stored within the rows of CAM cells to generate the column parity values comprises;

reading row values from the rows of the CAM cells; and

exclusive-ORing the row values with one another to generate a column parity word, the column parity values being constituent bits of the column parity word.

22. The method of claim 21 wherein exclusive-ORing the row values with one another to generate the column parity word comprises exclusive-ORing each bit of each of the row values with a corresponding bit of a partial column parity word.

23. A method of operation within a content addressable memory (CAM) device, the method comprising:

storing a plurality of row parity values, each row parity value indicating a parity for a respective row of CAM cells within the CAM device;

storing a plurality of column parity values, each comprise parity values indicating a parity for a respective column of the CAM cells; and

storing an input value within a selected row of the CAM cells after storing the plurality of row parity values and the plurality of column parity values, wherein storing the input value within the selected row of the CAM cells comprises;

reading a stored value from the selected row of the CAM cells;

removing a parity contribution of the stored value from the plurality of column parity values;

storing the input value within the selected row of the CAM cells; and

applying a parity contribution of the input value to the plurality of column parity values.

24. The method of claim 23 wherein removing a parity contribution of the stored value from the plurality of column parity values comprises exclusive-ORing each bit of the stored value with a respective one of the column parity values.

25. The method of claim 23 wherein applying a parity contribution of the input value to the plurality of column parity values comprises exclusive-ORing each bit of the input value with a respective one of the column parity values.

26. A method of operation within a content addressable memory (CAM) device, the method comprising:

determining that a row value stored in a first row of CAM cells within the CAM device is a corrupted row value;

combining the corrupted row value with row values stored in other rows of CAM cells within the CAM device to generate an updated column parity word;

comparing the updated column parity word with a previously generated column parity word to determine a bit in error in the corrupted row value;

correcting the bit in error in the corrupted row value to generate a corrected row value; and

wherein comparing the updated column parity word with a previously generated column parity word to determine the bit in error comprises exclusive-ORing the updated column parity word with the previously generated column parity word to produce a column syndrome value indicative of a location of the bit in error in the corrupted row value.

27. The method of claim 26 wherein correcting the bit in error in the corrupted row value to generate the corrected row value comprises exclusive-ORing the column syndrome value with the corrupted row value.

28. A method of operation within a content addressable memory (CAM) device, the method comprising:

determining that a row value stored in a first row of CAM cells within the CAM device is a corrupted row value;

combining the corrupted row value with row values stored in other rows of CAM cells within the CAM device to generate an updated column parity word;

comparing the updated column parity word with a previously generated column parity word to determine a bit in error in the corrupted row value; and

wherein determining that a row value is a corrupted value comprises;

reading each row value stored within the CAM device;

for each row value, exclusive-ORing each of the constituent bits of the row value with one another to generate a parity-check bit that corresponds to the row value; and

determining that the parity-check bit does not match a row parity bit associated with the corresponding row value.

29. The method of claim 28 wherein reading each row value stored within the CAM device comprises generating a sequence of scan addresses, each scan address corresponding to a respective row of CAM cells within the CAM device and having a row value stored therein.

30. The method of claim 29 further comprising storing, as an error address, a scan address that corresponds to the row of CAM cells having the corrupted row value stored therein.

31. The method of claim 30 further comprising:

correcting the bit in error in the compared row value to generate a corrected row value; and

storing the corrected row at the error address.

32. A method of operation within a content addressable memory (CAM) device, the method comprising:

receiving a request to store a write value in a selected row of CAM cells in a CAM array;

reading a row value from the selected row of CAM cells in response to the request;

removing a parity contribution of the row value from a column parity word;

applying a parity contribution of the write value to the column parity word; and

storing the write value in the selected row of CAM cells.

33. The method of claim 32 further comprising:

reading contents of each row of CAM cells in the CAM array; and

logically combining the contents of each row of CAM cells with each other to generate an updated column parity word.

34. The method of claim 33 wherein reading contents of each row of CAM cells comprises reading each row of CAM cells one after another in a predetermined scan sequence.

35. The method of claim 34 wherein logically combining the contents of each row of CAM cells with each other comprises exclusive-ORing the contents of each row of CAM cells with a partial column parity word to generate an updated partial column parity word, wherein the updated partial column parity word becomes the updated column parity word when exclusive-ORed with the contents of a final row of CAM cells in the scan sequence.

36. The method of claim 35 further comprising exclusive-ORing the contents of the selected row of CAM cells with the partial column parity word if the contents of the selected row of CAM cells has been exclusive-ORed with the contents of the partial column parity word.

37. The method of claim 36 further comprising:

determining if the contents of the selected row of CAM cells has been exclusive-ORed with the contents of the partial column parity word; and

exclusive-ORing the write value with the partial column parity word if the contents of the selected row of CAM cells has been exclusive-ORed with the contents of the partial column parity word.

38. A content addressable memory (CAM) device comprising:

a CAM array;

means for receiving a request to store a write value in a selected row of CAM cells in the CAM array;

means for reading a row value from the selected row of CAM cells in response to the request;

means for removing a parity contribution of the row value from a column parity word;

means for applying a parity contribution of the write value to the column parity word; and

means for storing the write value in the selected row of CAM cells.

39. The CAM device of claim 38 further comprising:

means for reading contents of each row of CAM cells in the CAM array; and

means for logically combining the contents of each row of CAM cells with each other to generate an updated column parity word.

40. The CAM device of claim 39 wherein the means for reading contents of each row of CAM cells comprises means for reading each row of CAM cells one after another in a predetermined scan sequence.

41. The CAM device of claim 40 wherein the means for logically combining the contents of each row of CAM cells with each other comprises means for exclusive-ORing the contents of each row of CAM cells with a partial column parity word to generate an updated partial column parity word, wherein the updated partial column parity word becomes the updated column parity word when exclusive-ORed with the contents of a final row of CAM cells in the scan sequence.

42. The CAM device of claim 41 further comprising means for exclusive-ORing the contents of the selected row of CAM cells with the partial column parity word if the contents of the selected row of CAM cells has been exclusive-ORed with the contents of the partial column parity word.

43. The CAM device of claim 42 further comprising:

means for determining if the contents of the selected row of CAM cells has been exclusive-ORed with the contents of the partial column parity word; and

means for exclusive-ORing the write value with the partial column parity word if the contents of the selected row of CAM cells has been exclusive-ORed with the contents of the partial column parity word.