# US 7,412,561 B2 · Transposing of bits in input data to form a comparand within a 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 7,412,561 B2 - Document ID: US7412561B2 - Status: Granted - Kind: B2 - Application number: 10/801,462 - Filed: 2004-03-15 - Published: 2004-12-02 - Granted: 2008-08-12 - Earliest claimed: 2002-01-14 - Assignees: NetLogic Microsystems, Inc. - Inventors: Dimitri C. Argyres; Varadarajan Srinivasan - Web page: https://patentgrep.com/patent/US7412561B2 ## 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 - H04L 2012/5685: {Addressing issues} - G11C: STATIC STORES (semiconductor memory devices H10B) - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) ## Abstract An apparatus and method of transposing one or more bits in input data relative to other bits of the input data to form a compound for searching in a content addressable memory. The comparand may have one or more bits rearranged from their order appearing in the input data such that one or more bits from a first segment of the input data are replaced with, or substituted by, one or more bits from a second segment of the input data. ## Claims ### Claim 1 An apparatus, comprising: control logic comprising a plurality of logic cells, at least one of the plurality of logic cells configured to receive an A operand and a B operand and perform the following logic operations comprising ĀB, A B, and AB; and switch circuitry coupled to receive input data, the switch circuitry coupled to the control logic to receive a result of the AB logic operation from each of the plurality of logic cells and selectively enable the output of one or more bits of the input data based on the results of the AB logic operations; wherein the control logic is coupled to receive a first plurality of enable signals, each of the first plurality of enable signals corresponding to a first plurality of one or more bits of a first segment of the input data, and wherein the control logic is coupled to receive a second plurality of enable signals, each of the second plurality of enable signals corresponding to a second plurality of one or more bits of a second segment of the input data. ### Claim 2 (depends on 1) The apparatus of claim 1, wherein the plurality of logic cells are coupled in a matrix of N columns and M rows comprising: a first row of logic cells, each of the logic cells in the first row having first inputs to receive a corresponding one of the first plurality of enable signals, wherein a first one of the logic cells in the first row has an input coupled to receive a first one of the second plurality of enable signals, wherein N-1 number of succeeding logic cells in the first row have second inputs coupled to receive the result of the ĀB logic operation of a preceding logic cell in the first row as the B operand; and a first column of logic cells, each of the logic cells in the first column having first inputs to receive a corresponding one of the second plurality of enable signals, wherein a first one of the logic cells in the first column has an input coupled to receive a first one of the first plurality of enable signals, wherein M-l number of succeeding logic cells in the first column have second inputs coupled to receive the result of the A Blogic operation of a preceding logic cell in the first column as the A operand, wherein each of the logic cells in the first column provides the result of the AB logic operation. ### Claim 3 (depends on 2) The apparatus of claim 2, wherein the switch circuitry further comprises: a first plurality of multiplexers, each of the first plurality of multiplexers coupled to receive the result of the AB logic operation of the first and second columns of logic cells as control inputs, wherein each of the first plurality of multiplexers is coupled to receive the second plurality of one or more bits of the second segment of the input data, each of the first plurality of multiplexers to selectively output one of the second plurality of one or more bits of the second segment based on the result of the AB logic operation of the first and second columns of logic cells. ### Claim 4 (depends on 3) The apparatus of claim 3, wherein the switch circuitry further comprises: a second plurality of multiplexers, each of the second plurality of multiplexers coupled to receive a corresponding one of the first enable signals as a control input, wherein each of the plurality of second multiplexers is coupled to receive a corresponding one of the first plurality of one or more bits of the first segment as a first input and the selected output of a corresponding one of the first plurality of multiplexers as a second input, each of the second plurality of multiplexers to selectively output one of the first and second inputs based on the control input. ### Claim 5 (depends on 1) The apparatus of claim 1, wherein the at least one of the plurality of logic cells has a first input, a second input, a first output, a second output and a third output, and wherein the first input is coupled to receive a first one of the plurality of first enable signals as the A operand, wherein the second input is coupled to receive a first one of the plurality of second enable signals as the B operand, wherein the first output provides the result of the ĀB logic operation, wherein the second output provides the result of the A Blogic operation, and wherein the third output provides the result of the AB logic operation. ### Claim 6 (depends on 5) The apparatus of claim 5, wherein the plurality of logic cells comprises: a first logic cell comprising the at least one of the plurality of logic cells; a second logic cell, the second input of the second logic cell coupled to receive the result of the ĀB logic operation from the first logic cell as the B operand of the second logic cell, the first input of the second logic cell coupled to receive a second one of the plurality of first enable signals as the A operand of the second logic cell, the third output of the second logic cell to provide the result of the AB logic operation of the second logic cell; a third logic cell, the second input of the third logic cell coupled to receive a second one of the plurality of second enable signals as the B operand of the third logic cell, the first input of the third logic cell coupled to receive the result of the A Blogic operation of the first logic cell as the A operand of the third logic cell, the third output of the third logic cell to provide the result of the AB logic operation of the third logic cell; and a fourth logic cell, the second input of the fourth logic cell coupled to receive the result of the ĀB logic operation from the third logic cell as the B operand of the fourth logic cell, the first input of the fourth logic cell coupled to receive the result of the A Blogic operation of the second logic cell as the A operand of the fourth logic cell, the third output of the fourth logic to provide the result of the AB logic operation of the fourth logic cell. ### Claim 7 (depends on 6) The apparatus of claim 6, wherein the switch circuitry comprises: a first multiplexer having control inputs coupled to receive the result of the AB logic operation from the first and third logic cells, the first multiplexer having inputs coupled to receive the first plurality of one or more bits of the second segment of the input data, the first multiplexer to selectively output one of the first plurality of one or more bits of the second segment of the input data based on the result of the AB logic operation from the first and second logic cells; and a second multiplexer having control inputs coupled to receive the result of the AB logic operation from the fourth and second logic cells, the second multiplexer having inputs coupled to receive the first plurality of one or more bits of the second segment of the input data, the second multiplexer to selectively output one of the first plurality of one or more bits of the second segment of the input data based on the result of the AB logic operation from the first and second logic cells. ### Claim 8 (depends on 7) The apparatus of claim 7, wherein the switch circuitry further comprises: a third multiplexer having a control input coupled to receive the first one of the plurality of first enable signals, the third multiplexer having a first input coupled to receive one of the first plurality of one or more bits of the first segment of input data, the third multiplexer having a second input coupled to receive the output of the first multiplexer, the third multiplexer to selectively output either the one of the first plurality of one or more bits of the first segment of input data or the output of the first multiplexer based on the first one of the plurality of first enable signals; and a fourth multiplexer having a control input coupled to receive the second one of the plurality of first enable signals, the fourth multiplexer having a first input coupled to receive another of the first plurality of one or more bits of the first segment of input data, the fourth multiplexer having a second input coupled to receive the output of the second multiplexer, the fourth multiplexer to selectively output either the another of the first plurality of one or more bits of the first segment of input data or the output of the second multiplexer based on the second one of the plurality of first enable signals. ### Claim 9 (depends on 2) The apparatus of claim 2, wherein the control logic comprises matrix of N columns and M rows of logic cells, where N is equal to a number of the first plurality of enable signals and M is equal to a number of the second plurality of enable signals. ### Claim 10 An apparatus, comprising: control logic comprising a plurality of logic cells, at least one of the plurality of logic cells configured to receive an A operand and a B operand and perform the following logic operations comprising ĀB. A B, and AB; and switch circuitry coupled to receive input data, the switch circuitry coupled to the control logic to receive a result of the AB logic operation from each of the plurality of logic cells and selectively enable the output of one or more bits of the input data based on the results of the AB logic operations; a content addressable memory (CAM) array coupled to receive a comparand; and a filter circuit coupled to the CAM array, the filter circuit comprising the switch circuitry and the control logic, wherein the filter circuit is coupled to receive the input data and transpose the one or more bits of the input data from an initial position in the input data to a different position in the comparand relative to other bits of the input data that are transposed to the comparand. ### Claim 11 (depends on 10) The apparatus of claim 10, wherein the input data segment and a second data segment and wherein the filter circuit is configured to replace one or more bits of the first data segment with one or more bits from the second data segment to form the comparand. ### Claim 12 (depends on 11) The apparatus of claim 11, further comprising a comparand register coupled between the CAM array and the filter circuit to store the comparand. ### Claim 13 An apparatus, comprising: control logic comprising a plurality of logic cells, at least one of the plurality of logic cells configured to receive an A operand and a B operand and perform the following logic operations comprising ĀB, A B, and AB; and switch circuitry coupled to receive input data, the switch circuitry coupled to the control logic to receive a result of the AB logic operation from each of the plurality of logic cells and selectively enable the output of one or more bits of the input data based on the results of the AB logic operations; wherein at least another of the plurality of logic cells is configured to receive a result of the ĀB logic operation of the at least one logic cell and an enable signal as the B operand, and wherein the at least another of the plurality of logic cells is configured to perform the AB logic operation. ### Claim 14 A method, comprising: providing a matrix of M rows and N columns of logic cells in a content addressable memory (CAM) device, where N is equal to or greater than 1 and M is greater than 1; performing an AB logic operation in each of the logic cells; selecting among a second one or more bits of input data using a result of the AB logic operation in at least one of the logic cells; and selecting between the selected second one or more bits of input data and a first one or more bits of input data for output to a comparand in the CAM device. ### Claim 15 (depends on 14) The method of claim 14, further comprising: receiving a first enable signal as an A operand in a first one of the logic cells, the first enable signal corresponding to the first one or more bits of input data; and receiving a second enable signal as a B operand in the first one of the logic cells, the second enable signal corresponding to the second one or more bits of input data. ### Claim 16 (depends on 15) The method of claim 15, further comprising: performing an ĀB logic operation in the first logic cell and providing a result of the ĀB logic operation as a B operand to a second logic cell; and performing an A Blogic operation in the first logic cell and providing a result of the A Blogic operation as an A operand to a third logic cell. ### Claim 17 (depends on 16) The method of claim 16, wherein performing the AB logic operation in at least one of the logic cells comprises: performing the AB logic operation in the first logic cell to generate a first result; and performing the AB logic operation in the second logic cell to generate a second result. ### Claim 18 (depends on 17) The method of claim 17, wherein selecting among the second one or more bits of input data using the result of the AB logic operation comprises using at least one of the first and second results to select among the second one or more bits of input data. ### Claim 19 (depends on 18) The method of claim 18, wherein selecting between the selected second one or more bits of input data and the first one or more bits of input data for output to the comparand comprises using the received first enable signal. ### Claim 20 (depends on 15) The method of claim 15, wherein performing the AB logic operation in each of the logic cells comprises: performing the AB logic operation in each of a N number of logic cells in the first row of the matrix of logic cells using the A operand; and performing the AB logic operation in each of a M number of logic cells in a first column of the matrix of logic cells using the B operand. ### Claim 21 (depends on 20) The method of claim 20, wherein performing the AB logic operation in each of the logic cells further comprises: performing the following logic operations in each of an M-1 number of logic cells in each of the M rows and each of an N-1 number of logic cells in each of the N columns: an ĀB logic operation and an A Blogic operation; receiving a result of the ĀB logic operation of a preceding logic cell in a row of the M rows as the Boperand in a succeeding cell in the row and performing the AB logic operation in the N-1 number of succeeding logic cells in the row; and receiving a result of the A Blogic operation of a preceding logic cell in a column of the N columns as the A operand in a succeeding cell in the column and performing the AB logic operations in the M-1 number of succeeding logic cells in the column. ### Claim 22 A content addressable memory (CAM) device, comprising: a matrix of M rows and N columns of logic cells, where N is equal to or greater than 1 and M is greater than 1; means for performing an AB logic operation in each of the logic cells; means for selecting among a second one or more bits of input data using a result of the AB logic operation in at least one of the logic cells; and means for selecting between the selected second one or more bits of input data and a first one or more bits of input data for output to a comparand in the CAM device.