# US 9,520,194 B2 · Pre-computation based ternary content addressable memory

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 9,520,194 B2
- Document ID: US9520194B2
- Status: Granted
- Kind: B2
- Application number: 14/700,715
- Filed: 2015-04-30
- Published: 2015-08-20
- Granted: 2016-12-13
- Earliest claimed: 2012-09-27
- Assignees: Broadcom Corporation
- Applicants: Broadcom Corporation
- Inventors: Vinay Iyengar
- Web page: https://patentgrep.com/patent/US9520194B2

## CPC

- 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
- G11C 15/04: using semiconductor elements
- G11C: STATIC STORES (semiconductor memory devices H10B)

## Abstract

A pre-computation based TCAM configured to reduce the number of match lines being pre-charged during a search operation to save power is disclosed. The pre-computation based TCAM stores additional information in a secondary TCAM that can be used to determine which match lines in a primary TCAM storing data words to be searched need not be pre-charged because they are associated with data words guaranteed to not match. The additional information stored in secondary TCAM can include a pre-computation word that represents a range inclusive of a lower and upper bound of a number of ones or zeroes possible in a corresponding data word stored in the primary TCAM.

## Claims

### Claim 1

A pre-computation based ternary content addressable memory (TCAM), comprising:
a primary TCAM comprising a match line associated with a data word in the primary TCAM; and
a secondary TCAM comprising a match line associated with a pre-computation word in the secondary TCAM,
wherein the pre-computation word represents a range inclusive of a lower bound of a number of ones or zeros possible in the data word and an upper bound of the number of ones or zeros possible in the data word, and
wherein the match line associated with the pre-computation word in the secondary TCAM is configured to disable pre-charging of the match line associated with the data word in the primary TCAM.

### Claim 2 (depends on 1)

The pre-computation based TCAM of claim 1, further comprising:
a counter configured to generate a count of a number of ones or zeros in a search word.

### Claim 3 (depends on 2)

The pre-computation based TCAM of claim 2, wherein the search word is loaded into a search register included in the primary TCAM.

### Claim 4 (depends on 2)

The pre-computation based TCAM of claim 2, wherein the count is loaded into a search register included in the secondary TCAM.

### Claim 5 (depends on 2)

The pre-computation based TCAM of claim 2, wherein the match line associated with the pre-computation word in the secondary TCAM is configured to disable pre-charging of the match line associated with the data word in the primary TCAM if the count of the number of ones or zeroes in the search word does not fall within a range represented by the pre-computation word.

### Claim 6 (depends on 1)

The pre-computation based TCAM of claim 1, wherein the range represented by the pre-computation word is not equal to a range defined by the lower bound of the number of ones or zeros possible in the data word and the upper bound of the number of ones or zeros possible in the data word.

### Claim 7 (depends on 1)

The pre-computation based TCAM of claim 1, wherein the match line associated with the pre-computation word is configured to gate a control signal coupled to a pull-up transistor used to pre-charge the match line associated with the data word.

### Claim 8 (depends on 1)

The pre-computation based TCAM of claim 1, further comprising:
an encoder configured to convert a range defined by the lower bound of the number of ones or zeros possible in the data word and the upper bound of the number of ones or zeros possible in the data word into the pre-computation word.

### Claim 9

A pre-computation based ternary content addressable memory (TCAM), comprising:
a primary TCAM comprising a match line associated with a data word in the primary TCAM; and
a secondary TCAM comprising a match line associated with a pre-computation word in the secondary TCAM,
wherein the matchline associated with the pre-computation word in the secondary TCAM is configured to disable pre-charging of the match line associated with the data word in the primary TCAM based on a count of a number of ones or zeroes in only a portion of a search word used to search the primary TCAM.

### Claim 10 (depends on 9)

The pre-computation based TCAM of claim 9, further comprising:
a counter configured to generate the count of the number of ones or zeros in the portion of the search word.

### Claim 11 (depends on 9)

The pre-computation based TCAM of claim 9, wherein the search word is loaded into a search register included in the primary TCAM.

### Claim 12 (depends on 9)

The pre-computation based TCAM of claim 9, wherein the count is loaded into a search register included in the secondary TCAM.

### Claim 13 (depends on 9)

The pre-computation based TCAM of claim 9, wherein the match line associated with the pre-computation word in the secondary TCAM is configured to disable pre-charging of the match line associated with the data word in the primary TCAM if the count of the number of ones or zeroes in the portion of the search word does not fall within a range represented by the pre-computation word.

### Claim 14 (depends on 9)

The pre-computation based TCAM of claim 9, wherein the pre-computation word represents a range inclusive of a lower bound of the number of ones or zeros possible in the portion of the data word and an upper bound of a number of ones or zeros possible in the portion of the data word.

### Claim 15 (depends on 14)

The pre-computation based TCAM of claim 14, wherein the range represented by the pre-computation word is not equal to a range defined by the lower bound of the number of ones or zeros possible in the portion of the data word and the upper bound of the number of ones or zeros possible in the portion of the data word.

### Claim 16

A method for performing pre-computation in a ternary content addressable memory (TCAM), the method comprising:
storing a data word in a primary TCAM;
storing a pre-computation word in a secondary TCAM; and
disabling pre-charging of a match line associated with the data word if a count of a number of ones or zeroes in at least a portion of a search word does not fall within a range represented by the pre-computation word.

### Claim 17 (depends on 16)

The method of claim 16, further comprising:
searching for stored data words in the primary TCAM that match the search word.

### Claim 18 (depends on 16)

The method of claim 16, further comprising:
loading the search word into a search register included in the primary TCAM.

### Claim 19 (depends on 16)

The method of claim 16, further comprising:
loading the count into a search register included in the secondary TCAM.

### Claim 20 (depends on 16)

The method of claim 16, wherein the pre-computation word represents a range inclusive of a lower bound of the number of ones or zeros possible in at least a portion of the data word and an upper bound of the number of ones or zeros possible in the at least a portion of the data word.